Erich P. Stuntebeck, John S. Davis II, et al.
HotMobile 2008
We introduce concurrent time-stamping, a paradigm that allows processes to temporally order concurrent events in an asynchronous shared-memory system. Concurrent time-stamp systems are powerful tools for concurrency control, serving as the basis for solutions to coordination problems such as mutual exclusion, ℓ-exclusion, randomized consensus, and multiwriter multireader atomic registers. Unfortunately, all previously known methods for implementing concurrent time-stamp systems have been theoretically unsatisfying since they require unbounded-size time-stamps - in other words, unbounded-size memory. This work presents the first bounded implementation of a concurrent time-stamp system, providing a modular unbounded-to-bounded transformation of the simple unbounded solutions to problems such as those mentioned above. It allows solutions to two formerly open problems, the bounded-probabilistic-consensus problem of Abrahamson and the fifo-ℓ-exclusion problem of Fischer, Lynch, Burns and Borodin, and a more efficient construction of multireader multiwriter atomic registers.
Erich P. Stuntebeck, John S. Davis II, et al.
HotMobile 2008
Lixi Zhou, Jiaqing Chen, et al.
VLDB
Minkyong Kim, Zhen Liu, et al.
INFOCOM 2008
Robert E. Donovan
INTERSPEECH - Eurospeech 2001