The Life in 1-Consensus

2017/09/20 by Yehuda Afek, Afek, Yehuda, Eli Daian +3
Computer Science · #C.1.4 #C.2.4 #Distributed #Distributed systems and fault tolerance #E.1 #FOS: Computer and information sciences #Interconnection Networks and Systems #Parallel #Parallel Computing and Optimization Techniques #and Cluster Computing (cs.DC)

paper · pdf · doi:10.48550/arxiv.1709.06808

openalex publication_date 2017/09/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

This paper introduces the atomic Write and Read Next (WRN_k) deterministic shared memory object, that for any k≥3, is stronger than read-write registers, but is unable to implement 2-processor consensus. In particular, it refutes the conjecture claiming that every deterministic object of consensus number 1 is computationally equivalent to read-write registers.

Related

• Reducing Compare-and-Swap to Consensus Number One Primitives
• Simple CHT: A New Derivation of the Weakest Failure Detector for Consensus
• A Simple Object that Spans the Whole Consensus Hierarchy
• Randomized Consensus with Regular Registers
• On Atomic Registers and Randomized Consensus in M&M Systems