Document Open Access Logo

Dynamic Reconfiguration: Abstraction and Optimal Asynchronous Solution

Authors Alexander Spiegelman, Idit Keidar, Dahlia Malkhi

PDF
Thumbnail PDF

File

LIPIcs.DISC.2017.40.pdf
  • Filesize: 0.61 MB
  • 15 pages

Document Identifiers

Author Details

Alexander Spiegelman
Idit Keidar
Dahlia Malkhi

Cite AsGet BibTex

Alexander Spiegelman, Idit Keidar, and Dahlia Malkhi. Dynamic Reconfiguration: Abstraction and Optimal Asynchronous Solution. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 40:1-40:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.DISC.2017.40

Abstract

Providing clean and efficient foundations and tools for reconfiguration is a crucial enabler for distributed system management today. This work takes a step towards developing such foundations. It considers classic fault-tolerant atomic objects emulated on top of a static set of fault-prone servers, and turns them into dynamic ones. The specification of a dynamic object extends the corresponding static (non-dynamic) one with an API for changing the underlying set of fault-prone servers. Thus, in a dynamic model, an object can start in some configuration and continue in a different one. Its liveness is preserved through the reconfigurations it undergoes, tolerating a versatile set of faults as it shifts from one configuration to another. In this paper we present a general abstraction for asynchronous reconfiguration, and exemplify its usefulness for building two dynamic objects: a read/write register and a max-register. We first define a dynamic model with a clean failure condition that allows an administrator to reconfigure the system and switch off a server once the reconfiguration operation removing it completes. We then define the Reconfiguration abstraction and show how it can be used to build dynamic registers and max-registers. Finally, we give an optimal asynchronous algorithm implementing the Reconfiguration abstraction, which in turn leads to the first asynchronous (consensus-free) dynamic register emulation with optimal complexity. More concretely, faced with n requests for configuration changes, the number of configurations that the dynamic register is implemented over is n; and the complexity of each client operation is O(n).
Keywords
  • Reconfiguration
  • Dynamic Objects
  • Optimal Algorithm

Metrics

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

References

  1. Yehuda Afek, Hagit Attiya, Danny Dolev, Eli Gafni, Michael Merritt, and Nir Shavit. Atomic snapshots of shared memory. Journal of the ACM (JACM), 40(4):873-890, 1993. Google Scholar
  2. Marcos K. Aguilera, Idit Keidar, Dahlia Malkhi, Jean-Philippe Martin, and Alexander Shraer. Reconfiguring replicated atomic storage: A tutorial. Bulletin of the EATCS, 2010. Google Scholar
  3. Marcos K. Aguilera, Idit Keidar, Dahlia Malkhi, and Alexander Shraer. Dynamic atomic storage without consensus. J. ACM, 58(2):7:1-7:32, April 2011. Google Scholar
  4. James Aspnes, Hagit Attiya, and Keren Censor. Max registers, counters, and monotone circuits. In PODC 2009, pages 36-45. ACM, 2009. Google Scholar
  5. Hagit Attiya, Amotz Bar-Noy, and Danny Dolev. Sharing memory robustly in message-passing systems. Journal of the ACM (JACM), 42(1):124-142, 1995. Google Scholar
  6. Hagit Attiya, Hyun Chul Chung, Faith Ellen, Saptaparni Kumar, and Jennifer L Welch. Simulating a shared register in an asynchronous system that never stops changing. In International Symposium on Distributed Computing, pages 75-91. Springer, 2015. Google Scholar
  7. Roberto Baldoni, Silvia Bonomi, and Michel Raynal. Implementing a regular register in an eventually synchronous distributed system prone to continuous churn. Parallel and Distributed Systems, IEEE Transactions on, 2012. Google Scholar
  8. Ken Birman, Dahlia Malkhi, and Robbert Van Renesse. Virtually synchronous methodology for dynamic service replication. Appears as Appendix A in [4], 2010. Google Scholar
  9. Vita Bortnikov, Gregory Chockler, Dmitri Perelman, Alexey Roytman, Shlomit Shachor, and Ilya Shnayderman. Frappé: Fast replication platform for elastic services. LADIS, 2011. Google Scholar
  10. Gregory Chockler, Seth Gilbert, Vincent Gramoli, Peter M Musial, and Alex A Shvartsman. Reconfigurable distributed storage for dynamic networks. Journal of Parallel and Distributed Computing, 69(1):100-116, 2009. Google Scholar
  11. Gregory Chockler and Dahlia Malkhi. Active disk paxos with infinitely many processes. Distributed Computing, 18(1):73-84, 2005. Google Scholar
  12. Gregory Chockler and Alexander Spiegelman. Space complexity of fault-tolerant register emulations. In Proceedings of PODC'17. ACM, 2017. Google Scholar
  13. Eli Gafni and Dahlia Malkhi. Elastic configuration maintenance via a parsimonious speculating snapshot solution. In DISC 2015, pages 140-153. Springer, 2015. Google Scholar
  14. Seth Gilbert, Nancy Lynch, and Alex Shvartsman. RAMBO II: Rapidly reconfigurable atomic memory for dynamic networks. In DSN 2013. IEEE Computer Society, 2003. Google Scholar
  15. Seth Gilbert, Nancy A Lynch, and Alexander A Shvartsman. RAMBO: A robust, reconfigurable atomic memory service for dynamic networks. Distributed Computing, 23(4), 2010. Google Scholar
  16. Prasad Jayanti, Tushar Deepak Chandra, and Sam Toueg. Fault-tolerant wait-free shared objects. J. ACM, 45(3):451-500, May 1998. Google Scholar
  17. Leander Jehl and Hein Meling. The case for reconfiguration without consensus. In Proceedings of the 2016 ACM symposium on Principles of distributed computing. ACM, 2016. Google Scholar
  18. Leander Jehl, Roman Vitenberg, and Hein Meling. SmartMerge: A new approach to reconfiguration for atomic storage. In Proceedings of DISC 2015. Springer, 2015. Google Scholar
  19. Leslie Lamport, Dahlia Malkhi, and Lidong Zhou. Reconfiguring a state machine. SIGACT News, 41(1):63-73, March 2010. Google Scholar
  20. Nancy Lynch and Alex A Shvartsman. RAMBO: A reconfigurable atomic memory service for dynamic networks. In Distributed Computing, pages 173-190. Springer, 2002. Google Scholar
  21. Alexander Shraer, Jean-Philippe Martin, Dahlia Malkhi, and Idit Keidar. Data-centric reconfiguration with network-attached disks. In LADIS. ACM, 2010. Google Scholar
  22. Alexander Spiegelman and Idit Keidar. Dynamic atomic snapshots. In Proceedings of the 2016 ACM symposium on Principles of distributed computing. ACM, 2016. Google Scholar
  23. Alexander Spiegelman and Idit Keidar. On liveness of dynamic storage. In Proceedings of SIROCCO 2017, 2017. Google Scholar
  24. Alexander Spiegelman, Idit Keidar, and Dahlia Malkhi. Dynamic reconfiguration: A tutorial. In International Conference on Principles of Distributed Systems, 2016. Google Scholar
  25. Alexander Spiegelman, Idit Keidar, and Dahlia Malkhi. Dynamic reconfiguration: Abstraction and optimal asynchronous solution, 2017. URL: https://alexanderspiegelman.github.io/alexanderspiegelman.github.io/DynamicTasks.pdf.
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