Document Open Access Logo

Optimal Resilience in Systems That Mix Shared Memory and Message Passing

Authors Hagit Attiya , Sweta Kumari, Noa Schiller

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2020.16.pdf
  • Filesize: 0.54 MB
  • 16 pages

Document Identifiers

Author Details

Hagit Attiya
  • Department of Computer Science, Technion, Haifa, Israel
Sweta Kumari
  • Department of Computer Science, Technion, Haifa, Israel
Noa Schiller
  • Department of Computer Science, Technion, Haifa, Israel

Funding

This research was supported by ISF grant 380/18.

Acknowledgements

We thank Vassos Hadzilacos, Xing Hu, Sam Toueg and the anonymous reviewers for helpful comments.

Cite AsGet BibTex

Hagit Attiya, Sweta Kumari, and Noa Schiller. Optimal Resilience in Systems That Mix Shared Memory and Message Passing. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, pp. 16:1-16:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.OPODIS.2020.16

Abstract

We investigate the minimal number of failures that can partition a system where processes communicate both through shared memory and by message passing. We prove that this number precisely captures the resilience that can be achieved by algorithms that implement a variety of shared objects, like registers and atomic snapshots, and solve common tasks, like randomized consensus, approximate agreement and renaming. This has implications for the m&m-model of [Aguilera et al., 2018] and for the hybrid, cluster-based model of [Damien Imbs and Michel Raynal, 2013; Michel Raynal and Jiannong Cao, 2019].

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed computing models
  • Theory of computation → Concurrent algorithms
  • Computing methodologies → Distributed algorithms
Keywords
  • fault resilience
  • m&m model
  • cluster-based model
  • randomized consensus
  • approximate agreement
  • renaming
  • register implementations
  • atomic snapshots

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Gen-Z draft core specification. https://genzconsortium.org/specification/gen-z-core-specification-1-1-draft/. Accessed: 2020-08-26.
  2. InfiniBand. https://www.infinibandta.org/about-infiniband/. Accessed: 2020-08-26.
  3. iWARP. https://en.wikipedia.org/wiki/IWARP. Accessed: 2020-08-26.
  4. RDMA over converged ethernet. https://en.wikipedia.org/wiki/RDMA_over_Converged_Ethernet. Accessed: 2020-08-26.
  5. Marcos K. Aguilera, Naama Ben-David, Irina Calciu, Rachid Guerraoui, Erez Petrank, and Sam Toueg. Passing messages while sharing memory. In PODC, page 51–60, 2018. Google Scholar
  6. James Aspnes and Maurice Herlihy. Fast randomized consensus using shared memory. Journal of Algorithms, 11(3):441-461, September 1990. Google Scholar
  7. Hagit Attiya, Amotz Bar-Noy, and Danny Dolev. Sharing memory robustly in message-passing systems. Journal of the ACM, 42(1):124-142, January 1995. Google Scholar
  8. Hagit Attiya, Amotz Bar-Noy, Danny Dolev, David Peleg, and Rüdiger Reischuk. Renaming in an asynchronous environment. Journal of the ACM, 37(3):524-548, 1990. Google Scholar
  9. Hagit Attiya and Constantin Enea. Putting strong linearizability in context: Preserving hyperproperties in programsthat use concurrent objects. In DISC, pages 2:1-2:17, 2019. Google Scholar
  10. Hagit Attiya and Arie Fouren. Adaptive and efficient algorithms for lattice agreement and renaming. SIAM J. Comput., 31(2):642-664, 2001. URL: https://doi.org/10.1137/S0097539700366000.
  11. Hagit Attiya, Arie Fouren, and Eli Gafni. An adaptive collect algorithm with applications. Distributed Computing, 15(2):87-96, 2002. Google Scholar
  12. Hagit Attiya, Nancy A. Lynch, and Nir Shavit. Are wait-free algorithms fast? J. ACM, 41(4):725-763, 1994. URL: https://doi.org/10.1145/179812.179902.
  13. Hagit Attiya and Ophir Rachman. Atomic snapshots in O(n log n) operations. SIAM J. Comput., 27(2):319-340, 1998. Google Scholar
  14. Amotz Bar-Noy and Danny Dolev. A partial equivalence between shared-memory and message-passing in an asynchronous fail-stop distributed environment. Math. Syst. Theory, 26(1):21-39, 1993. URL: https://doi.org/10.1007/BF01187073.
  15. Michael Ben-Or. Another advantage of free choice: Completely asynchronous agreement protocols. In PODC, pages 27-30, 1983. Google Scholar
  16. Martin Biely, Peter Robinson, and Ulrich Schmid. Easy impossibility proofs for k-set agreement in message passing systems. In OPODIS, pages 299-312, 2011. Google Scholar
  17. Elizabeth Borowsky and Eli Gafni. Generalized FLP impossibility result for t-resilient asynchronous computations. In STOC, pages 91-100, 1993. Google Scholar
  18. Gabriel Bracha and Sam Toueg. Asynchronous consensus and broadcast protocols. Journal of the ACM, 32(4):824-840, 1985. Google Scholar
  19. Soma Chaudhuri. More choices allow more faults: Set consensus problems in totally asynchronous systems. Inf. Comput., 105(1):132-158, 1993. URL: https://doi.org/10.1006/inco.1993.1043.
  20. Faith E. Fich, Maurice Herlihy, and Nir Shavit. On the space complexity of randomized synchronization. Journal of the ACM, 45(5):843-862, 1998. URL: https://doi.org/10.1145/290179.290183.
  21. Michael J. Fischer, Nancy A. Lynch, and Mike Paterson. Impossibility of distributed consensus with one faulty process. Journal of the ACM, 32(2):374-382, 1985. URL: https://doi.org/10.1145/3149.214121.
  22. Wojciech Golab, Lisa Higham, and Philipp Woelfel. Linearizable implementations do not suffice for randomized distributed computation. In STOC, page 373–382, 2011. Google Scholar
  23. Vassos Hadzilacos, Xing Hu, and Sam Toueg. Optimal register construction in m&m systems. In OPODIS, pages 28:1-28:16, 2019. Google Scholar
  24. Vassos Hadzilacos, Xing Hu, and Sam Toueg. Optimal register construction in m&m systems (version 3). CoRR, abs/1906.00298, 2020. URL: http://arxiv.org/abs/1906.00298.
  25. Vassos Hadzilacos, Xing Hu, and Sam Toueg. Randomized consensus with regular registers. CoRR, abs/2006.06771, 2020. URL: http://arxiv.org/abs/2006.06771.
  26. Maurice Herlihy and Nir Shavit. The asynchronous computability theorem for t-resilient tasks. In STOC, pages 111-120, 1993. Google Scholar
  27. Maurice P. Herlihy and Jeannette M. Wing. Linearizability: A correctness condition for concurrent objects. ACM Trans. Program. Lang. Syst., 12(3):463-492, July 1990. Google Scholar
  28. Damien Imbs and Michel Raynal. The weakest failure detector to implement a register in asynchronous systems with hybrid communication. Theor. Comput. Sci., 512:130-142, 2013. URL: https://doi.org/10.1016/j.tcs.2012.06.030.
  29. Leslie Lamport. On interprocess communication - part I: Basic formalism. Distributed Computing, pages 77-85, 1986. Google Scholar
  30. Kevin Lim, Jichuan Chang, Trevor Mudge, Parthasarathy Ranganathan, Steven K. Reinhardt, and Thomas F. Wenisch. Disaggregated memory for expansion and sharing in blade servers. SIGARCH Comput. Archit. News, 37(3):267–278, June 2009. URL: https://doi.org/10.1145/1555815.1555789.
  31. Michel Raynal and Jiannong Cao. One for all and all for one: Scalable consensus in a hybrid communication model. In ICDCS, pages 464-471, 2019. Google Scholar
  32. Michael E. Saks and Fotios Zaharoglou. Wait-free k-set agreement is impossible: the topology of public knowledge. In STOC, pages 101-110, 1993. Google Scholar
  33. Paul M. B. Vitányi and Baruch Awerbuch. Atomic shared register access by asynchronous hardware. In FOCS, 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 Imprint Privacy Contact