The Cost of Conservative Synchronization in Parallel Discrete Event Simulations

Research output: Contribution to journalArticlepeer-review


This paper analytically studies the performance of a synchronous conservative parallel discrete-event simulation protocol. The class of models considered simulates activity in a physical domain, and possesses a limited ability to predict future behavior. Using a stochastic model, it is shown that as the volume of simulation activity in the model increases relative to a fixed architecture, the complexity of the average per-event overhead due to synchronization, event list manipulation, lookahead calculations, and processor idle time approaches the complexity of the average per-event overhead of a serial simulation, sometimes rapidly. The method is therefore within a constant factor of optimal. The result holds for the worst case “fully-connected” communication topology, where an event in any other portion of the domain can cause an event in any other protion of the domain. Our analysis demonstrates that on large problems—those for which parallel processing is ideally suited— there is often enough parallel workload so that processors are not usually idle. It also demonstrated the viability of the method empirically, showing how good performance is achieved on large problems using a thirty-two node Intel iPSC/2 distributed memory multiprocessor.

Original languageEnglish (US)
Pages (from-to)304-333
Number of pages30
JournalJournal of the ACM (JACM)
Issue number2
StatePublished - Jan 4 1993
Externally publishedYes


  • conservative
  • synchronization

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence


Dive into the research topics of 'The Cost of Conservative Synchronization in Parallel Discrete Event Simulations'. Together they form a unique fingerprint.

Cite this