Applications such as the design of digital hardware, queueing networks, and aircraft and banking systems require the use of distributed discrete-event simulation. The current approaches (synchronous, rollback, and asynchronous) fall short of attaining acceptable performance, freedom from deadlock, and provable correctness. The authors of this paper discuss an approach to distributed discrete-event simulation that appears to eliminate deadlock problems and provides levels of performance that are to some extent independent of time and complexity constraints. The authors also provide, through an example and supporting experimental data, some evidence of the correctness of their approach.
The technique presented in this paper is called Yaddes (“yet another asynchronous distributed discrete-event simulation algorithm”). The Yaddes approach is centered around the identification and simulation of the cyclic components of a system. These components, represented by cyclic directed graphs, are modeled as equivalent components that remove feedback loops by adding acyclic pseudocomponents that enable system execution in a deadlock-free environment. Although the Yaddes algorithm is rather complex and its full understanding requires some background in and experience with discrete simulation, the paper’s style and level make it accessible to a wide range of computer professionals.