Bounded Concurrent Time-Stamp Systems Are Constructible
Abstract
Concurrent time stamping is at the heart of the solutions to some of the most fundamental problems in distributed computing. Based on concurrent-time-stamp-systems, elegant and simple solutions to core problems such as fcfs-mutual-exclusion, construction of a multi-writer-multi-writer atomic register, probabilistic consensus,...were developed. Unfortunately, the only known implementation of a concurrent time stamp system has been theoretically unsatisfying, since it requires unbounded size time-stamps, in other words, unbounded memory. Not knowing if bounded concurrent-time-stamp-systems are at all constructible, researchers were led to constructing complicated problem-specific solutions to replace the simple unbounded ones. In this work, for the first time, a bounded implementation of a concurrent-time-stamp-system is presented. It provides a modular unbounded-to-bound transformations of the simple unbounded solutions to problems such as above. It allows solutions to two formerly open problems, the bounded-probabilistic-consensus problem of Abrahamson (A88) and the fifo-1-exclusion problem of (FLBB85), and a more efficient construction of mrmw atomic registers.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 01, 1989
- Accession Number
- ADA213853
Entities
People
- Danny Dolev
- Nir Shavit
Organizations
- Massachusetts Institute of Technology