Conservative Parallel Simulation Of Continuous Time Markov Chains Using Uniformization

This paper describes parallel algorithms for simulating certain continuous time Markov Chains such as those arising in queueing network models of distributed computing systems, or communications systems. The algorithms are based on the technique of uniformization. Two variations of a conservative parallel simulation algorithm are presented. In each algorithm, a relatively short “presimulation” is performed to identify those times, and only those times, at which the simulation algorithm requires processor pairs to synchronize. Speedup studies of the algorithms, performed on a 16 node Intel iPSC/2 hypercube, are presented and discussed.