Simple Optimal Wait-free Multireader Registers

2002/02/04 by Paul Vitányi, Vitanyi, Paul
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 #Interconnection Networks and Systems #Optimization and Search Problems #Parallel #and Cluster Computing (cs.DC)

paper · pdf · doi:10.48550/arxiv.cs/0202003

openalex publication_date 2002/02/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Multireader shared registers are basic objects used as communication medium in asynchronous concurrent computation. We propose a surprisingly simple and natural scheme to obtain several wait-free constructions of bounded 1-writer multireader registers from atomic 1-writer 1-reader registers, that is easier to prove correct than any previous construction. Our main construction is the first symmetric pure timestamp one that is optimal with respect to the worst-case local use of control bits; the other one is optimal with respect to global use of control bits; both are optimal in time.

Citations

• Linearizability: a correctness condition for concurrent objects
• Time, clocks, and the ordering of events in a distributed system

Related

• Bounded Concurrent Timestamp Systems Using Vector Clocks
• Two-Bit Messages are Sufficient to Implement Atomic Read/Write Registers in Crash-prone Systems
• Fine-grained Analysis on Fast Implementations of Distributed Multi-writer Atomic Registers
• Time-Efficient Read/Write Register in Crash-prone Asynchronous Message-Passing Systems
• The Space Complexity of Long-lived and One-Shot Timestamp Implementations