Conservative parallel simulation for systems with no lookahead prediction

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.