Document Open Access Logo

Reconfigurable Lattice Agreement and Applications

Authors Petr Kuznetsov, Thibault Rieutord, Sara Tucci-Piergiovanni

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2019.31.pdf
  • Filesize: 0.55 MB
  • 17 pages

Document Identifiers

Author Details

Petr Kuznetsov
  • LTCI, Télécom Paris, Institut Polytechnique Paris, Paris, France
Thibault Rieutord
  • CEA LIST, PC 174, Gif-sur-Yvette, 91191, France
Sara Tucci-Piergiovanni
  • CEA LIST, PC 174, Gif-sur-Yvette, 91191, France

Cite AsGet BibTex

Petr Kuznetsov, Thibault Rieutord, and Sara Tucci-Piergiovanni. Reconfigurable Lattice Agreement and Applications. In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 31:1-31:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.OPODIS.2019.31

Abstract

Reconfiguration is one of the central mechanisms in distributed systems. Due to failures and connectivity disruptions, the very set of service replicas (or servers) and their roles in the computation may have to be reconfigured over time. To provide the desired level of consistency and availability to applications running on top of these servers, the clients of the service should be able to reach some form of agreement on the system configuration. We observe that this agreement is naturally captured via a lattice partial order on the system states. We propose an asynchronous implementation of reconfigurable lattice agreement that implies elegant reconfigurable versions of a large class of lattice abstract data types, such as max-registers and conflict detectors, as well as popular distributed programming abstractions, such as atomic snapshot and commit-adopt.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
Keywords
  • Reconfigurable services
  • lattice agreement

Metrics

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

Related Versions

References

  1. Yehuda Afek, Hagit Attiya, Danny Dolev, Eli Gafni, Michael Merritt, and Nir Shavit. Atomic Snapshots of Shared Memory. jacm, 40(4):873-890, 1993. Google Scholar
  2. Marcos Kawazoe Aguilera, Idit Keidar, Dahlia Malkhi, and Alexander Shraer. Dynamic atomic storage without consensus. J. ACM, 58(2):7:1-7:32, 2011. Google Scholar
  3. Eduardo Alchieri, Alysson Bessani, Fabíola Greve, and Joni da Silva Fraga. Efficient and Modular Consensus-Free Reconfiguration for Fault-Tolerant Storage. In OPODIS, pages 26:1-26:17, 2017. Google Scholar
  4. James Aspnes, Hagit Attiya, and Keren Censor. Max Registers, Counters, and Monotone Circuits. In PODC, pages 36-45, 2009. Google Scholar
  5. James Aspnes and Faith Ellen. Tight Bounds for Adopt-Commit Objects. Theory Comput. Syst., 55(3):451-474, 2014. URL: https://doi.org/10.1007/s00224-013-9448-1.
  6. Hagit Attiya, Amotz Bar-Noy, and Danny Dolev. Sharing Memory Robustly in Message Passing Systems. Journal of the ACM (JACM), 42(2):124-142, 1995. Google Scholar
  7. Hagit Attiya, Hyun Chul Chung, Faith Ellen, Saptaparni Kumar, and Jennifer L. Welch. Emulating a Shared Register in a System That Never Stops Changing. IEEE Trans. Parallel Distrib. Syst., 30(3):544-559, 2019. Google Scholar
  8. Hagit Attiya, Maurice Herlihy, and Ophir Rachman. Atomic Snapshots Using Lattice Agreement. Distributed Comput., 8(3):121-132, 1995. Google Scholar
  9. Roberto Baldoni, Silvia Bonomi, Anne-Marie Kermarrec, and Michel Raynal. Implementing a Register in a Dynamic Distributed System. In ICDCS, pages 639-647, 2009. Google Scholar
  10. Elizabeth Borowsky and Eli Gafni. Generalized FLP impossibility result for t-resilient asynchronous computations. In STOC, pages 91-100, 1993. Google Scholar
  11. Christian Cachin, Rachid Guerraoui, and Luís Rodrigues. Introduction to reliable and secure distributed programming. Springer Science & Business Media, 2011. Google Scholar
  12. Armando Castañeda, Sergio Rajsbaum, and Michel Raynal. Unifying Concurrent Objects and Distributed Tasks: Interval-Linearizability. J. ACM, 65(6):45:1-45:42, 2018. Google Scholar
  13. Miguel Castro and Barbara Liskov. Practical byzantine fault tolerance and proactive recovery. ACM Trans. Comput. Syst., 20(4):398-461, 2002. Google Scholar
  14. Gregory V. Chockler, Rachid Guerraoui, Idit Keidar, and Marko Vukolic. Reliable Distributed Storage. IEEE Computer, 42(4):60-67, 2009. Google Scholar
  15. Jose Faleiro, Sriram Rajamani, Kaushik Rajan, Ganesan Ramalingam, and Kapil Vaswani. Generalized lattice agreement. In PODC, pages 125-134, 2012. Google Scholar
  16. Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson. Impossibility of Distributed Consensus with one Faulty Process. jacm, 32(2):374-382, 1985. Google Scholar
  17. Eli Gafni. Round-by-round fault detectors: Unifying synchrony and asynchrony. In PODC, pages 143-152, 1998. Google Scholar
  18. Eli Gafni and Dahlia Malkhi. Elastic Configuration Maintenance via a Parsimonious Speculating Snapshot Solution. In DISC, pages 140-153, 2015. Google Scholar
  19. David K. Gifford. Weighted Voting for Replicated Data. In SOSP, pages 150-162, 1979. Google Scholar
  20. Seth Gilbert, Nancy A. Lynch, and Alexander A. Shvartsman. Rambo: a robust, reconfigurable atomic memory service for dynamic networks. Distributed Comput., 23(4):225-272, 2010. Google Scholar
  21. Maurice Herlihy. Wait-free synchronization. ACM Trans. Program. Lang. Syst., 13(1):123-149, 1991. Google Scholar
  22. Maurice Herlihy and Jeannette M. Wing. Linearizability: A Correctness Condition for Concurrent Objects. ACM Trans. Program. Lang. Syst., 12(3):463-492, 1990. Google Scholar
  23. Leander Jehl, Roman Vitenberg, and Hein Meling. SmartMerge: A New Approach to Reconfiguration for Atomic Storage. In DISC, pages 154-169, 2015. Google Scholar
  24. Petr Kuznetsov, Thibault Rieutord, and Sara Tucci-Piergiovanni. Reconfigurable Lattice Agreement and Applications. CoRR, abs/1910.09264, 2019. URL: http://arxiv.org/abs/1910.09264.
  25. Leslie Lamport. The Part-Time Parliament. ACM Trans. Comput. Syst., 16(2):133-169, 1998. Google Scholar
  26. Leslie Lamport, Dahlia Malkhi, and Lidong Zhou. Reconfiguring a state machine. SIGACT News, 41(1):63-73, 2010. Google Scholar
  27. Matthieu Perrin. Concurrency and Consistency. In Distributed Systems. Elsevier, 2017. URL: https://doi.org/10.1016/B978-1-78548-226-7.50008-2.
  28. Fred B. Schneider. Implementing Fault-Tolerant Services Using the State Machine Approach: A Tutorial. ACM Comput. Surv., 22(4):299-319, 1990. Google Scholar
  29. Marc Shapiro, Nuno M. Preguiça, Carlos Baquero, and Marek Zawirski. Conflict-Free Replicated Data Types. In SSS, pages 386-400, 2011. Google Scholar
  30. Jan Skrzypczak, Florian Schintke, and Thorsten Schütt. Linearizable State Machine Replication of State-Based CRDTs without Logs. CoRR, abs/1905.08733, 2019. URL: http://arxiv.org/abs/1905.08733.
  31. Alexander Spiegelman, Idit Keidar, and Dahlia Malkhi. Dynamic Reconfiguration: Abstraction and Optimal Asynchronous Solution. In DISC, pages 40:1-40:15, 2017. 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