Pseudosimulation: an algorithm for distributed simulation with limited memory (Q1822491)

In this paper we present a new algorithm for the distributed simulation of systems that may be modeled as a network of processes which exchange event messages (e.g. computer networks, telephone systems). We focus upon the case of fully distributed processes with limited memory available to simulate each process. The synchronization algorithm employed is a blocking algorithm. The simulation of different processes is allowed to proceed in parallel until deadlock occurs, at which time a deadlock- breaking algorithm is invoked as in the Chandy/Misra scheme. A central controller is employed to detect and aid in the efficient resolution of deadlocks. We solve some problems which were not clearly addressed in the Chandy/Misra scheme. Our deadlock-breaking algorithm, christened Pseudosimulation, is a ''look-ahead'' algorithm, which undertakes to fill empty buffers with future event messages. Correctness and termination of the algorithm are proven. An analysis of the memory requirements and running is performed. A lower bound on the memory requirements is also established which simplifies the deadlock-breaking algorithm.