Bounded Concurrent Time-Stamp Systems Are Constructible
Danny Dolev, Nir Shavit · 1989
Concurrent time stamping is at the heart of solu-tions to some of the moe,t fundamental problems in distributed computing. Based on concurrent-time-stamp-systems, elegant and simple solu-tions to core problems such as fcfs-mutual-exclusion, construction of a multi-reader-multi-writer atomic register, probabilistic consensus,... were developed. Unfortunately, the only known implementation of a concurrent time stamp sys-tem 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 con-structing complicated problem-specific solutions to replace the simple unbounded ones. In this work, for the first time, a bounded implemen-tation of a concurrent-t:ime-stamp-system is pre-