Document Open Access Logo

On Implementing SWMR Registers from SWSR Registers in Systems with Byzantine Failures

Authors Xing Hu, Sam Toueg

PDF
Thumbnail PDF

File

LIPIcs.DISC.2022.36.pdf
  • Filesize: 0.89 MB
  • 19 pages

Document Identifiers

Author Details

Xing Hu
  • Department of Computer Science, University of Toronto, Canada
Sam Toueg
  • Department of Computer Science, University of Toronto, Canada

Funding

This work was partially funded by the Natural Sciences and Engineering Research Council of Canada (Grant number: RGPIN-2014-05296).

Acknowledgements

We thank Vassos Hadzilacos for his helpful comments on this paper.

Cite As Get 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

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)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. 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.
  2. James H Anderson and Mohamed G Gouda. The virtue of patience: Concurrent programming with and without waiting. Citeseer, 1990. Google Scholar
  3. 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.
  4. B. Bloom. Constructing two-writer atomic registers. IEEE Trans. Comput., 37(12):1506-1514, December 1988. Google Scholar
  5. 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.
  6. 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.
  7. 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.
  8. 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.
  9. 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.
  10. 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.
  11. 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.
  12. 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.
  13. 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.
  14. Leslie Lamport. On interprocess communication Parts I-II. Distributed Computing, 1(2):77-101, 1986. URL: https://doi.org/10.1007/BF01786227.
  15. 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.
  16. 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.
  17. 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.
  18. 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.
  19. 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.
  20. 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.
  21. 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.
  22. 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. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact