2026-07-21T14:14:04Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7967 2024-03-06T10:41:42Z ddc:004 open_access

Dynamic Reconfiguration: Abstraction and Optimal Asynchronous Solution Spiegelman, Alexander Keidar, Idit Malkhi, Dahlia Reconfiguration Dynamic Objects Optimal Algorithm 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Alexander Spiegelman and Idit Keidar and Dahlia Malkhi 2017 Is Part Of LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2017.40 urn:nbn:de:0030-drops-79673 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.40 eng https://creativecommons.org/licenses/by/3.0/legalcode