Pseudosimulation in distributed simulations : a deadlock prevention algorithm with fixed memory requirements

Distributing discrete event simulations among several processors appears to be a promising approach to speed up simulations and reduce the complexity of the tasks to be accomplished by each processor. Processing the events in parallel requires a synchronization technique which would insure the simulation correctness while keeping the overhead relatively low. In a distributed simulation, the simulation progresses at a different speed in every processor. The main problem consists in enabling a processor to know if it holds all the information needed to correctly make a further step in the simulation. We describe an algorithm having fixed memory requirements and allowing a processor to know if it holds a complete set of information in order to correctly continue the simulation. The algorithm also forces missing information to arrive at a processor that requested it