2001/08/02 by Sibsankar Haldar, S. Haldar, Haldar, Sibsankar +3
Computer Science · #B.3.2 #B.4.3 #C.2.4 #D.1.3 #D.4.1 #D.4.4 #Distributed #Distributed systems and fault tolerance #F.1.2 #FOS: Computer and information sciences #Optimization and Search Problems #Parallel #Real-Time Systems Scheduling #and Cluster Computing (cs.DC) #cs.DC
paper · pdf · doi:10.48550/arxiv.cs/0108002
LaTeX source, 35 pages; To apper in: J. Assoc. Comp. Mach
arxiv created 2001/08/02 · openalex publication_date 2001/08/02 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Shared registers are basic objects used as communication mediums in asynchronous concurrent computation. A concurrent timestamp system is a higher typed communication object, and has been shown to be a powerful tool to solve many concurrency control problems. It has turned out to be possible to construct such higher typed objects from primitive lower typed ones. The next step is to find efficient constructions. We propose a very efficient wait-free construction of bounded concurrent timestamp systems from 1-writer multireader registers. This finalizes, corrects, and extends, a preliminary bounded multiwriter construction proposed by the second author in 1986. That work partially initiated the current interest in wait-free concurrent objects, and introduced a notion of discrete vector clocks in distributed algorithms.