Dynamic reconfiguration: Abstraction and optimal asynchronous solution

Alexander Spiegelman, Idit Keidar, Dahlia Malkhi

פרסום מחקרי: פרק בספר / בדוח / בכנספרסום בספר כנסביקורת עמיתים


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

שפה מקוריתאנגלית
כותר פרסום המארח31st International Symposium on Distributed Computing, DISC 2017
עורכיםAndrea W. Richa
מסת"ב (אלקטרוני)9783959770538
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 1 אוק׳ 2017
אירוע31st International Symposium on Distributed Computing, DISC 2017 - Vienna, אוסטריה
משך הזמן: 16 אוק׳ 201720 אוק׳ 2017

סדרות פרסומים

שםLeibniz International Proceedings in Informatics, LIPIcs


כנס31st International Symposium on Distributed Computing, DISC 2017

ASJC Scopus subject areas

  • ???subjectarea.asjc.1700.1712???

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Dynamic reconfiguration: Abstraction and optimal asynchronous solution'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי