Accelerating Markovian analysis of asynchronous systems using state compression

This paper presents a methodology to speed up the stationary analysis of la rge Markov chains that model asynchronous systems, Instead of directly work ing on the original Markov chain, we propose to analyze a smaller Markov ch ain obtained via a novel technique called state compression. Once the small er chain is solved, the solution to the original chain is obtained via a pr ocess called expansion, The method is especially powerful when the Markov c hain has a small feedback vertex set, which happens often in asynchronous s ystems that contain mostly bounded-delay components, Our experimental resul ts show that the method can yield reductions of more than an order of magni tude in CPU time and facilitate the analysis of larger systems than possibl e using traditional techniques.