An Analysis of Rollback-Based Simulation

Abstract

We present and analyze a general model of rollback in parallel processing. The analysis points out three possible modes where rollback may become excessive; we provide an example of each type. We identify the parameters which determine a stability, or efficiency region for the simulation. Our analysis suggests the possibility of a dangerous "phase-transition" from stability to instability in the parameter space. In particular, a rollback algorithm may work efficiently for a small system but become inefficient for a large system. Moreover, for a given system, it may work quickly for a while and then suddely slow down.<P>On the positive side, we give a tunable algorithm, Filtered Rollback, that is designed to avoid the failure modes. Under appropriate assumptions, we provide a rigorous mathematical proof that Filtered Rollback is efficient, if implemented on a reasonably efficient multiprocessor. In particular: we show that the average time t to complete the simulation of a system with N nodes and R events on a p -processor PRAM satisfies t = 0 ((R/p) + (R/N) log p).<P>The analysis is based on recent work by the authors on Branching Random Walks with a barrier.