Simulation Pending-Event-Set Implementations

by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

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.

Other Event Sets and Priority Queues