License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2017.40
URN: urn:nbn:de:0030-drops-79673
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7967/
Go to the corresponding LIPIcs Volume Portal

Spiegelman, Alexander ; Keidar, Idit ; Malkhi, Dahlia

Dynamic Reconfiguration: Abstraction and Optimal Asynchronous Solution

pdf-format:
LIPIcs-DISC-2017-40.pdf (0.6 MB)

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).

BibTeX - Entry

@InProceedings{spiegelman_et_al:LIPIcs:2017:7967,
  author =	{Alexander Spiegelman and Idit Keidar and Dahlia Malkhi},
  title =	{{Dynamic Reconfiguration: Abstraction and Optimal Asynchronous Solution}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{40:1--40:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Andr{\'e}a W. Richa},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7967},
  URN =		{urn:nbn:de:0030-drops-79673},
  doi =		{10.4230/LIPIcs.DISC.2017.40},
  annote =	{Keywords: Reconfiguration, Dynamic Objects, Optimal Algorithm}
}

Keywords: Reconfiguration, Dynamic Objects, Optimal Algorithm
Collection: 31st International Symposium on Distributed Computing (DISC 2017)
Issue Date: 2017
Date of publication: 12.10.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI