What is a Franta-Maly event list?

Question

The top answer to this question references a Franta-Maly event list. What is a Franta-Maly event list and what are its use cases?

Answer 1

The Franta-Maly event list (or event set) was described in a 1977 paper by W.R. Franta and Kurt Maly, An Efficient Data Structure for the Simulation Event Set. In this paper, they presented a new event scheduling algorithm that improves on previously published algorithms. According to the abstract:

First, the new algorithm's performance is quite insensitive to skewed distributions, and second, its worst-case complexity is O(sqrt(n)), where n is the number of events in the set. Furthermore, tests conducted to estimate the average complexity showed it to be nearly independent of n.

The paper presents what the authors call a TL (two-level) algorithm for inserting an event into the event set:

Stripped of its simulation terminology, we require an efficient solution to the following problem: devise a physical data structure for a dynamically changing collection of records which supports retrieval of the record with the minimally valued key. In the simulation environment, the records are event notices, each containing information identifying an event, and the key is the scheduled time for its occurrence. The scheduled time is known as the event time, and the collector¹ of records is called the event set.

...

The basic idea of the TL algorithm is to limit the number of notices which must be scanned for an insertion. This requirement is met by dynamically creating for each interval a list of secondary keys and associating them with the right boundary dummy key. Each secondary key points to the beginning of a sublist of notices within an interval... Whenever one of these sublists becomes unbalanced, i.e. too large, the structure is adjusted by either moving the notice to the adjacent list or creating a new sublist with its associated secondary key.

^{1 I would like to suggest that perhaps "collector of records" is a typo in the original paper, and that "collection of records" may be what was intended here.}

Link to the Franta-Maly paper: http://staff.ii.pw.edu.pl/~gjb/aal/index_lists.pdf

---

^{Note: The quoted sections of this answer are subject to the following copyright notice:}

^{Communications of the ACM, August 1977, Volume 20, Number 8. Copyright (c) 1977, Association for Computing Machinery, Inc. General permission to republish, but not for profit, all or part of this material is granted provided that ACM's copyright notice is given and that reference is made to the publication, to its date of issue, and to the fact that reprinting privileges were granted by permission of the Association for Computing Machinery. Authors' address: Department of Computer Science, University of Minnesota, Minneapolis, MN 55455.}