Simulation and Pending-Event-Set Implementations

Splay Trees

Splay-trees, a form of self-adjusting binary search tree invented by Dan Sleator and analyzed by Bob Tarjan, have proven to be one of the fastest and most robust implementations of the pending-event set, the central abstraction underlying the sequential discrete event simulation algorithm.

The pending-event set is basically a priority queue, where the act of scheduling an event to take place at some future time inserts an event notice in the priority queue, and the main simulation loop proceeds by repeatedly extracting from the pending-event set the event notice with minimum time.

• the original Pascal code. Most implementations of splay trees in use today are descended from this code.
• Dave Brower's C code. A widely used C transliteration of the above Pascal code. Dave Brower's book on data structures has a chapter based on this.
• An Ada generic package. This is also derived from the above, and has seen considerable use. See also: Kennisaw Iowa State

Other Event Sets and Priority Queues

• Twisted trees, transparencies for a May 5, 1983 brown-bag lunch talk on a new priority queue algorithm based on self-balancing heap-ordered trees. The algorithm worked pretty well and led me into the whole world of priority-queue research.

• Eleven algorithms in Pascal. This collection of algorithms was the basis of the paper An Empirical Comparison of Priority Queue and Event Set Implementations in Communications of the ACM, 29, April 1986, pages 300-311. This paper was the first to show the speed and stability of the splay-tree data structure. The following data structures are included here: Linear linked list, leftist trees, Blackstone's two-list structure, implicit heaps, Henriksen's indexed list, binomial queues, pagodas, bottom-up skew heaps, top-down skew heaps, splay trees, and pairing heaps.

• A Note on Bottom-Up Skew Heaps, SIAM Journal of Computing, Feb. 1987. The original version of skew heaps developed by Sleator and Robert only worked if all keys in the heap were distinct. Since equal keys occur in many practical applications, including the tests reported above, I took the time to fix document skew-heap variants that allow equal keys.

Other Discrete Event Simulation

• The Iowa Logic Simulator is a digital logic simulator originally written in Pascal that uses a discrete-event simulation model implemented using pairing heaps.

• An Epidemic Simulator is a discrete-event simulation written in Java, including a simulation framework based on Java's class PriorityQueue using lambda expressions to pass the events associated with events.

• Concurrent Simulation: an Alternative to Distributed Simulation and Experience with Concurrent Simulatio presented at the 1986 Winter Simulation Conference, an approach to using shared-memory multiprocessors for simulation. Chien-Chun Chou, Debra Renk and Steven C. Bruell were coauthors on the second paper.

• A Conservative Distributed Concurrent Discrete-Event Simulator on a Shared Memory by my PhD student Herbert R. Hoeger, presented at the 1992 IASTED International Conference on Modelling and Optomization; this paper bridges the gap between the concurrent simulation work described above and work by others on distributed simulation.