| In this thesis we present efficient algorithms for distributed simulation, and for the related problems of termination detection and sequential simulation. We present distributed simulation algorithms applicable to the simulation of special classes of systems such that almost no overhead messages are required. By contrast, previous distributed simulation algorithms, although applicable to the general class of any discrete event system, usually require too many overhead messages. First, we define a simple distributed simulation algorithm with nearly zero overhead messages for simulating feedforward systems. We develop an approximate method to predict its performance in simulating a class of feedforward queuing networks. We evaluate the performance of the scheme in simulating specific subclasses of these queuing networks. We show that the scheme offers a high performance for serial-parallel networks. Next we define another distributed simulation scheme for a class of distributed systems who topologies may have cycles. One important problem in devising distributed simulation algorithms is that of efficient detection of termination. With this in mind, we devise a class of termination detection algorithms using markers. Finally, we develop a new sequential simulation algorithm based on a distributed one. This algorithm often reduces the event list manipulations of traditional event list driven simulation. |
