Set agreement and renaming in the presence of contention-related crash failures

Anaïs Durand, Michel Raynal, Gadi Taubenfeld

نتاج البحث: فصل من :كتاب / تقرير / مؤتمرمنشور من مؤتمرمراجعة النظراء

ملخص

A new notion of process failure explicitly related to contention has recently been introduced by one of the authors (NETYS 2018). More precisely, given a predefined contention threshold λ, this notion considers the executions in which process crashes are restricted to occur only when process contention is smaller than or equal to λ. If crashes occur after contention bypassed λ, there are no correctness guarantees (e.g., termination is not guaranteed). It was shown that, when λ = n-1, consensus can be solved in an n-process asynchronous read/write system despite the crash of one process, thereby circumventing the well-known FLP impossibility result. Furthermore, it was shown that when λ = n-k and k≥2, k-set agreement can be solved despite the crash of 2k-2 processes. This paper considers two types of process crash failures: “ λ -constrained” crash failures (as previously defined), and classical crash failures (that we call “any time” failures). It presents two algorithms suited to these types of failures. The first algorithm solves k-set agreement, where k = m+f,, in the presence of t = 2m+f -1 crash failures, 2m of them being (n-k) -constrained failures, and (f-1) being any time failures. The second algorithm solves (n + f) -renaming in the presence of t = m + f crash failures, m of them being (n - t - 1) -constrained failures, and f being any time failures. It follows that the differentiation between λ -constrained crash failures and any time crash failures enlarges the space of executions in which the impossibility of k-set agreement and renaming in the presence of asynchrony and process crashes can be circumvented. In addition to its behavioral properties, both algorithms have a noteworthy first class property, namely, their simplicity.

اللغة الأصليةالإنجليزيّة
عنوان منشور المضيفStabilization, Safety, and Security of Distributed Systems - 20th International Symposium, SSS 2018, Proceedings
المحررونTaisuke Izumi, Petr Kuznetsov
ناشرSpringer Verlag
الصفحات269-283
عدد الصفحات15
رقم المعيار الدولي للكتب (المطبوع)9783030032319
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 2018
منشور خارجيًانعم
الحدث20th International Symposium on Stabilization, Safety, and Security of Distributed Systems, SSS 2018 - Tokyo, اليابان
المدة: ٤ نوفمبر ٢٠١٨٧ نوفمبر ٢٠١٨

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

الاسمLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
مستوى الصوت11201 LNCS
رقم المعيار الدولي للدوريات (المطبوع)0302-9743
رقم المعيار الدولي للدوريات (الإلكتروني)1611-3349

!!Conference

!!Conference20th International Symposium on Stabilization, Safety, and Security of Distributed Systems, SSS 2018
الدولة/الإقليماليابان
المدينةTokyo
المدة٤/١١/١٨٧/١١/١٨

ملاحظة ببليوغرافية

Publisher Copyright:
© Springer Nature Switzerland AG 2018.

بصمة

أدرس بدقة موضوعات البحث “Set agreement and renaming in the presence of contention-related crash failures'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا