Document Open Access Logo

Optimal Register Construction in M&M Systems

Authors Vassos Hadzilacos, Xing Hu, Sam Toueg

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2019.28.pdf
  • Filesize: 0.7 MB
  • 16 pages

Document Identifiers

Author Details

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

Funding

This research was partially funded by the Natural Sciences and Engineering Research Council of Canada.

Cite AsGet BibTex

Vassos Hadzilacos, Xing Hu, and Sam Toueg. Optimal Register Construction in M&M Systems. In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 28:1-28:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.OPODIS.2019.28

Abstract

Motivated by recent distributed systems technology, Aguilera et al. introduced a hybrid model of distributed computing, called message-and-memory model or m&m model for short [Marcos K. Aguilera et al., 2018]. In this model, processes can communicate by message passing and also by accessing some shared memory. We consider the basic problem of implementing an atomic single-writer multi-reader (SWMR) register shared by all the processes in m&m systems. Specifically, we give an algorithm that implements such a register in m&m systems and show that it is optimal in the number of process crashes that it can tolerate. This generalizes the well-known implementation of an atomic SWMR register in a pure message-passing system [Attiya et al., 1995].

Subject Classification

ACM Subject Classification
  • Theory of computation → Concurrency
  • Theory of computation → Parallel computing models
  • Theory of computation → Distributed computing models
Keywords
  • asynchronous distributed system
  • shared memory
  • message passing

Metrics

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

References

  1. Marcos K. Aguilera, Naama Ben-David, Irina Calciu, Rachid Guerraoui, Erez Petrank, and Sam Toueg. Passing Messages while Sharing Memory. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC 2018, Egham, United Kingdom, July 23-27, 2018, pages 51-60, 2018. URL: https://doi.org/10.1145/3212734.3212741.
  2. 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., pages 409-418, 2019. URL: https://doi.org/10.1145/3293611.3331601.
  3. Cristiana Amza, Alan L. Cox, Shandya Dwarkadas, Pete Keleher, Honghui Lu, Ramakrishnan Rajamony, Weimin Yu, and Willy Zwaenepoel. TreadMarks: Shared memory computing on networks of workstations. IEEE Computer, 29(2):18-28, February 1996. Google Scholar
  4. 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
  5. Andrew Baumann, Paul Barham, Pierre-Evariste Dagand, Tim Harris, Rebecca Isaacs, Simon Peter, Timothy Roscoe, Adrian Schüpbach, and Akhilesh Singhania. The Multikernel: A New OS Architecture for Scalable Multicore Systems. In ACM Symposium on Operating Systems Principles, pages 29-44, October 2009. Google Scholar
  6. John K. Bennett, John B. Carter, and Willy Zwaenepoel. Munin: Distributed Shared Memory Based on Type-specific Memory Coherence. In ACM Symposium on Principles and Practice of Parallel Programming, pages 168-176, March 1990. Google Scholar
  7. Tudor David, Rachid Guerraoui, and Maysam Yabandeh. Consensus Inside. In International Middleware Conference, pages 145-156, December 2014. Google Scholar
  8. Aleksandar Dragojević, Dushyanth Narayanan, Miguel Castro, and Orion Hodson. FaRM: Fast remote memory. In Symposium on Networked Systems Design and Implementation, pages 401-414, April 2014. Google Scholar
  9. Gen-Z Draft Core Specification - December 2016. URL: http://genzconsortium.org/draft-core-specification-december-2016.
  10. Gen-Z DRAM and Persistent Memory Theory of Operation. URL: https://genzconsortium.org/wp-content/uploads/2019/03/Gen-Z-DRAM-PM-Theory-of-Operation-WP.pdf.
  11. Alan J. Hoffman and Robert R. Singleton. On Moore Graphs with Diameters 2 and 3. IBM Journal of Research and Development, 4(5):497-504, 1960. URL: https://doi.org/10.1147/rd.45.0497.
  12. InfiniBand. URL: http://www.infinibandta.org/content/pages.php?pg=about_us_infiniband.
  13. iWARP. URL: https://en.wikipedia.org/wiki/IWARP.
  14. Anuj Kalia, Michael Kaminsky, and David G. Andersen. Using RDMA Efficiently for Key-value Services. In ACM SIGCOMM Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, pages 295-306, August 2014. Google Scholar
  15. Anuj Kalia, Michael Kaminsky, and David G. Andersen. FaSST: Fast, scalable and simple distributed transactions with two-sided (RDMA) datagram RPCs. In Symposium on Operating Systems Design and Implementation, pages 185-201, November 2016. Google Scholar
  16. Stefanos Kaxiras, David Klaftenegger, Magnus Norgren, Alberto Ros, and Konstantinos Sagonas. Turning Centralized Coherence and Distributed Critical-Section Execution on Their Head: A New Approach for Scalable Distributed Shared Memory. In IEEE International Symposium on High Performance Distributed Computing, pages 3-14, June 2015. Google Scholar
  17. David Kranz, Kirk Johnson, Anant Agarwal, John Kubiatowicz, and Beng-Hong Lim. Integrating Message-passing and Shared-memory: Early Experience. In ACM Symposium on Principles and Practice of Parallel Programming, pages 54-63, 1993. Google Scholar
  18. Leslie Lamport. On interprocess communication Part I-II. Distributed Computing, 1(2):77-101, May 1986. Google Scholar
  19. Kevin Lim, Jichuan Chang, Trevor Mudge, Parthasarathy Ranganathan, Steven K. Reinhardt, and Thomas F. Wenisch. Disaggregated Memory for Expansion and Sharing in Blade Servers. In International Symposium on Computer Architecture, pages 267-278, June 2009. Google Scholar
  20. Jacob Nelson, Brandon Holt, Brandon Myers, Preston Briggs, Luis Ceze, Simon Kahan, and Mark Oskin. Latency-tolerant Software Distributed Shared Memory. In USENIX Annual Technical Conference, pages 291-305, July 2015. Google Scholar
  21. Marius Poke and Torsten Hoefler. DARE: High-Performance State Machine Replication on RDMA Networks. In Proceedings of the 24th International Symposium on High-Performance Parallel and Distributed Computing, HPDC '15, pages 107-118, New York, NY, USA, 2015. ACM. URL: https://doi.org/10.1145/2749246.2749267.
  22. RDMA over converged ethernet. URL: https://en.wikipedia.org/wiki/RDMA_over_Converged_Ethernet.
  23. Daniel J. Scales, Kourosh Gharachorloo, and Chandramohan A. Thekkath. Shasta: A Low Overhead, Software-only Approach for Supporting Fine-grain Shared Memory. In International Conference on Architectural Support for Programming Languages and Operating Systems, pages 174-185, October 1996. Google Scholar
  24. Shin-Yeh Tsai and Yiying Zhang. LITE kernel RDMA support for datacenter applications. In ACM Symposium on Operating Systems Principles, pages 306-324, October 2017. Google Scholar
  25. Figure by Uzyel - Own work, CC BY-SA 3.0. URL: https://commons.wikimedia.org/w/index.php?curid=10378641.
  26. Jian Yang, Joseph Izraelevitz, and Steven Swanson. Orion: A Distributed File System for Non-Volatile Main Memory and RDMA-Capable Networks. In 17th USENIX Conference on File and Storage Technologies (FAST 19), pages 221-234, Boston, MA, February 2019. USENIX Association. URL: https://www.usenix.org/conference/fast19/presentation/yang.
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