Limit Theory for Performance Modeling of Future Event Set Algorithms

In a discrete-event simulation, the information related to the events scheduled to occur in the future is kept in a data structure called the future event set (FES). In this paper, we study the interaction hold model, a popular stochastic model for FES performance analysis, corresponding to the superposition of a (fixed) number of renewal processes. The general state-space Markov chain formed by the discrete-time process that keeps track, at event times, of the residual lifetimes is shown here to be recurrent in the sense of Harris, and its stationary distribution is obtained. Linked lists and indexed lists, two popular FESs, are investigated using this model. For the interaction hold model, we make rigorous certain published results as well as introduce new ones. For example, we derive the distribution of the relative position of the event to be inserted in the data structure. In the exponential case, our analytic and empirical results confirm that when events with relatively short lifetimes often get regenerated upon their occurrence, it is better to scan a list (or sublist) from its head rather than tail. In the same context and for indexed lists with sublists with constant sizes, our results suggest that subsequent sublists should be of larger sizes, i.e., the first sublist should contain the smallest number of records, the second sublist the second smallest number of records, etc.