Simulating Colliding Rigid Disks in Parallel Using Bounded Lag Without Time Warp.

The task of simulating systems of colliding rigid disks or billiard balls is considered an important benchmark for parallel event driven simulation schemes. Progress in parallelizing a recently proposed fast serial rigid-disk simulation algorithm is reported. The proposed parallel algorithm proceeds in iterations, maintains a bounded lag restriction, and pretends that certain upper bounds on the event propagation speed hold. Sometimes events propagate faster than these bounds and an out-of-order event processing can occur. In such cases, rather than using the flexible Time Warp mechanism, the algorithm resorts to a crude but simple recovery using the global state saved at a recent successfully passed check-point. The check-pointing rollback is asymptotically non-scalable: the time to simulate a larger system on a proportionally larger parallel processor grows asymptotically very quickly. However, this paper shows that the simulation time increase might still be bearable when several thousands processing elements are involved.