LIPIcs.DISC.2022.36.pdf
- Filesize: 0.89 MB
- 19 pages
Document
On Implementing SWMR Registers from SWSR Registers in Systems with Byzantine Failures
Authors
-
Part of:
Volume:
36th International Symposium on Distributed Computing (DISC 2022)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Distributed Computing (DISC) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2022-10-17
File
Document Identifiers
Acknowledgements
We thank Vassos Hadzilacos for his helpful comments on this paper.
Cite AsGet BibTex
Xing Hu and Sam Toueg. On Implementing SWMR Registers from SWSR Registers in Systems with Byzantine Failures. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 36:1-36:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.DISC.2022.36
https://doi.org/10.4230/LIPIcs.DISC.2022.36
Abstract
The implementation of registers from (potentially) weaker registers is a classical problem in the theory of distributed computing. Since Lamport’s pioneering work [Leslie Lamport, 1986], this problem has been extensively studied in the context of asynchronous processes with crash failures. In this paper, we investigate this problem in the context of Byzantine process failures, with and without process signatures. In particular, we first show a strong impossibility result, namely, that there is no wait-free linearizable implementation of a 1-writer n-reader register from atomic 1-writer (n-1)-reader registers. In fact, this impossibility result holds even if all the processes except the writer are given atomic 1-writer n-reader registers, and even if we assume that the writer can only crash and at most one reader is subject to Byzantine failures. In light of this impossibility result, we give two register implementations. The first one implements a 1-writer n-reader register from atomic 1-writer 1-reader registers. This implementation is linearizable (under any combination of Byzantine process failures), but it is wait-free only under the assumption that the writer is correct or no reader is Byzantine - thus matching the impossibility result. The second implementation assumes process signatures; it is wait-free and linearizable under any number and combination of Byzantine process failures.
Subject Classification
ACM Subject Classification
- Theory of computation → Distributed computing models
- Theory of computation → Distributed algorithms
Keywords
- distributed computing
- concurrency
- linearizability
- shared registers
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Marcos K. Aguilera, Naama Ben-David, Rachid Guerraoui, Virendra Marathe, and Igor Zablotchi. The impact of RDMA on agreement. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29 - August 2, 2019, PODC '19, pages 409-418, 2019. URL: https://doi.org/10.1145/3293611.3331601.
-
James H Anderson and Mohamed G Gouda. The virtue of patience: Concurrent programming with and without waiting. Citeseer, 1990.
- Hagit Attiya, Amotz Bar-Noy, and Danny Dolev. Sharing memory robustly in message-passing systems. Journal of the ACM, 42(1):124-142, 1995. URL: https://doi.org/10.1145/200836.200869.
-
B. Bloom. Constructing two-writer atomic registers. IEEE Trans. Comput., 37(12):1506-1514, December 1988.
- James E. Burns and Gary L. Peterson. Constructing multi-reader atomic values from non-atomic values. In Proceedings of the Sixth Annual ACM Symposium on Principles of Distributed Computing, PODC '87, pages 222-231, 1987. URL: https://doi.org/10.1109/12.9729.
- Shir Cohen and Idit Keidar. Tame the Wild with Byzantine Linearizability: Reliable Broadcast, Snapshots, and Asset Transfer. In 35th International Symposium on Distributed Computing (DISC 2021), volume 209, pages 18:1-18:18, 2021. URL: https://doi.org/10.4230/LIPIcs.DISC.2021.18.
- Jim Gray. Notes on data base operating systems. In Operating Systems, An Advanced Course, pages 393-481, 1978. URL: https://doi.org/10.1007/3-540-08755-9_9.
- S. Haldar and K. Vidyasankar. Constructing 1-writer multireader multivalued atomic variables from regular variables. J. ACM, 42(1):186-203, January 1995. URL: https://doi.org/10.1145/200836.200871.
- Maurice P. Herlihy. Impossibility and universality results for wait-free synchronization. In Proceedings of the Seventh Annual ACM Symposium on Principles of Distributed Computing, PODC '88, pages 276-290, 1988. URL: https://doi.org/10.1145/62546.62593.
- Maurice P. Herlihy and Jeannette M. Wing. Linearizability: A correctness condition for concurrent objects. ACM Trans. Program. Lang. Syst., 12(3):463-492, 1990. URL: https://doi.org/10.1145/78969.78972.
- Xing Hu and Sam Toueg. On implementing swmr registers from swsr registers in systems with byzantine failures, 2022. URL: https://doi.org/10.48550/arXiv.2207.01470.
- Amos Israeli and Amnon Shaham. Optimal multi-writer multi-reader atomic register. In Proceedings of the Eleventh Annual ACM Symposium on Principles of Distributed Computing, PODC '92, pages 71-82, 1992. URL: https://doi.org/10.1145/135419.135435.
- Prasad Jayanti, Tushar Deepak Chandra, and Sam Toueg. Fault-tolerant wait-free shared objects. J. ACM, 45(3):451-500, May 1998. URL: https://doi.org/10.1145/278298.278305.
- Leslie Lamport. On interprocess communication Parts I-II. Distributed Computing, 1(2):77-101, 1986. URL: https://doi.org/10.1007/BF01786227.
- Achour Mostéfaoui, Matoula Petrolia, Michel Raynal, and Claude Jard. Atomic read/write memory in signature-free byzantine asynchronous message-passing systems. Theory of Computing Systems, 60, May 2017. URL: https://doi.org/10.1007/s00224-016-9699-8.
- Richard Newman-Wolfe. A protocol for wait-free, atomic, multi-reader shared variables. In Proceedings of the Sixth Annual ACM Symposium on Principles of Distributed Computing, PODC '87, pages 232-248, 1987. URL: https://doi.org/10.1145/41840.41860.
- Gary L. Peterson. Concurrent reading while writing. ACM Trans. Program. Lang. Syst., 5(1):46-55, January 1983. URL: https://doi.org/10.1109/SFCS.1986.11.
- Gary L. Peterson and James E. Burns. Concurrent reading while writing ii: The multi-writer case. In 28th Annual Symposium on Foundations of Computer Science, Los Angeles, California, USA, 27-29 October 1987, SFCS '87, pages 383-392, 1987. URL: https://doi.org/10.1109/SFCS.1987.15.
- Ambuj K. Singh, James H. Anderson, and Mohamed G. Gouda. The elusive atomic register revisited. In Proceedings of the Sixth Annual ACM Symposium on Principles of Distributed Computing, PODC '87, pages 206-221, 1987. URL: https://doi.org/10.1145/41840.41858.
- K. Vidyasankar. Converting Lamport’s regular register to atomic register. Inf. Process. Lett., 28(6):287-290, August 1988. URL: https://doi.org/10.1016/0020-0190(88)90175-5.
- K. Vidyasankar. A very simple construction of 1-writer multireader multivalued atomic variable. Inf. Process. Lett., 37(6):323-326, March 1991. URL: https://doi.org/10.1016/0020-0190(91)90149-C.
-
Paul M. B. Vitanyi and Baruch Awerbuch. Atomic shared register access by asynchronous hardware. In 27th Annual Symposium on Foundations of Computer Science (sfcs 1986), pages 233-243, 1986.