Conservative parallel simulation for systems with no lookahead prediction

Yi-Bing Lin*, Edward D. Lazowska, Jean Loup Baer

*Corresponding author for this work

Research output: Contribution to journalConference articlepeer-review

9 Scopus citations

Abstract

The most popular conservative parallel simulation approach is the Chandy-Misra approach, referred to here as the Chandy-Misra basic scheme (CMB). When a CMB simulation includes a feedback loop (i.e., when a message may 'circulate' in a loop of processes), there is the probability that deadlocks will occur. To deal with deadlocks in Chandy-Misra simulations, two modified algorithms, the Chandy-Misra deadlock avoidance (DA) and deadlock recovery (DR) algorithms, have been proposed. The DA algorithm is widely used for simulating systems with lookahead prediction. The DR algorithm has been recognized, up to this point, as the only conservative approach for simulating systems with no lookahead prediction. This paper shows that a better approach for simulating systems with no lookahead prediction is to reconfigure the system such that there is no feedback loop, and use the CMB algorithm to perform the simulation. We identify the overheads of this approach, and devise both an analytical model and a number of simulation experiments to estimate its performance.

Original languageEnglish
Pages (from-to)144-149
Number of pages6
JournalSimulation Series
Volume22
Issue number1
StatePublished - Jan 1990
EventProceedings of the SCS Multiconference on Distributed Simulation - San Diego, CA, USA
Duration: 17 Jan 199019 Jan 1990

Fingerprint

Dive into the research topics of 'Conservative parallel simulation for systems with no lookahead prediction'. Together they form a unique fingerprint.

Cite this