Conservative Parallel Simulation Of Continuous Time Markov Chains Using Uniformization

Philip Heidelberger, David M. Nicol

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)906-921
Number of pages16
JournalIEEE Transactions on Parallel and Distributed Systems
Issue number8
StatePublished - Aug 1993
Externally publishedYes


  • Distributed simulation
  • Markov chain
  • parallel
  • queueing network
  • simulation
  • uniformization

ASJC Scopus subject areas

  • Signal Processing
  • Hardware and Architecture
  • Computational Theory and Mathematics


Dive into the research topics of 'Conservative Parallel Simulation Of Continuous Time Markov Chains Using Uniformization'. Together they form a unique fingerprint.

Cite this