Efficient Management of Multiple Outstanding Timeouts
Guillermo A. Alvarez |
Marcelo O. Fernández |
Abstract
The timeout management service allows client applications to start timers initially set to arbitrary intervals, and notifies their expiration back to the clients when the timeout intervals elapse. This service is a general building block for the implementation of software systems whose behavior depends on the passage of time.
In this work, we present a group of algorithms and data structures that solve the timeout management problem. For a set of n simultaneously outstanding timeouts, the asymptotic worst-case running time is O(log n) using O(n) space. These algorithms are asymptotically better than other solutions described in the literature. Moreover, the operations involved in the manipulation of timers can be carried out efficiently.