2021/08/03 by David Chan, Chan, David Yu Cheng, Vassos Hadzilacos +5
Computer Science · #Distributed #Distributed systems and fault tolerance #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.2108.01651
openalex publication_date 2021/08/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We prove that in asynchronous message-passing systems where at most one process may crash, there is no lock-free strongly linearizable implementation of a weak object that we call Test-or-Set (ToS). This object allows a single distinguished process to apply the set operation once, and a different distinguished process to apply the test operation also once. Since this weak object can be directly implemented by a single-writer single-reader (SWSR) register (and other common objects such as max-register, snapshot and counter), this result implies that there is no 1-resilient lock-free strongly linearizable implementation of a SWSR register (and of these other objects) in message-passing systems. We also prove that there is no 1-resilient lock-free write strongly-linearizable implementation of a 2-writer 1-reader (2W1R) register in asynchronous message-passing systems.