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
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 1 أكتوبر 2017
الحدث31st International Symposium on Distributed Computing, DISC 2017 - Vienna, النمسا
المدة: ١٦ أكتوبر ٢٠١٧٢٠ أكتوبر ٢٠١٧

سلسلة المنشورات

الاسمLeibniz International Proceedings in Informatics, LIPIcs
مستوى الصوت91

!!Conference

!!Conference31st International Symposium on Distributed Computing, DISC 2017
الدولة/الإقليمالنمسا
المدينةVienna
المدة١٦/١٠/١٧٢٠/١٠/١٧

All Science Journal Classification (ASJC) codes

  • !!Software

بصمة

أدرس بدقة موضوعات البحث “Dynamic reconfiguration: Abstraction and optimal asynchronous solution'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا