ON TERMINATING A DISTRIBUTED DISCRETE-EVENT SIMULATION

This paper studies the termination problem for a distributed discrete event simulation in a computing environment where message sending does not preserve FIFO property (i.e., the messages may not be delivered in the order they are sent). The distributed simulation considered is synchronized by a rollback mechanism. A termination detection algorithm is proposed. The algorithm can be easily integrated with the rollback mechanism. The effects of termination on the time complexity of distributed simulation is also studied. A quantitative relationship between the speedup of distributed simulation and the parameters that introduce overhead for termination is derived. The study indicates that, due to the termination overhead, adding extra processors to the distributed simulation may degrade the performance (speedup). © 1993 Academic Press. All rights reserved.