On the Distribution of Event Times for the notices in a Simulation Event List

Abstract

The time required to insert event notices in a simulation event list has a critical effect on the speed of execution of simulation programs. Even though several event list data structures and algorithms have been proposed to reduce this overhead, these attempts have neglected the theoretical aspects of the problem ; and no analysis has ever been made for even the simplest event list algorithms. In this paper, renewal theory is used to obtain the steady-state distribution for the scheduled event times. With the results, one can compute the performance of the standard implementation of the event list algorithm. More significantly, the results provide insight into the operation of event list algorithms and suggest strategies for their improvement. Also given, is an approximate expression for the duration of the transition period preceding steady state.