101. An Impossibility Result on Strong Linearizability in Message-Passing Systems
- Author
-
Chan, David Yu Cheng, Hadzilacos, Vassos, Hu, Xing, and Toueg, Sam
- Subjects
Computer Science - Distributed, Parallel, and Cluster Computing - Abstract
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 \emph{write} strongly-linearizable implementation of a 2-writer 1-reader (2W1R) register in asynchronous message-passing systems., Comment: 12 pages
- Published
- 2021