Limit Theory for Performance Modeling of Future Event Set Algorithms
研究未来事件集性能分析的交互保持模型，证明其马尔可夫链的Harris递归性并得到平稳分布，为链表和索引表两种常见结构提供了插入位置分布等新结果，对仿真系统设计有指导意义。
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.