Reaching Consensus in the Presence of Contention-Related Crash Failures

Anaïs Durand, Michel Raynal, Gadi Taubenfeld

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


While consensus is at the heart of many coordination problems in asynchronous distributed systems prone to process crashes, it has been shown to be impossible to solve in such systems where processes communicate by message-passing or by reading and writing a shared memory. Hence, these systems must be enriched with additional computational power for consensus to be solved on top of them. This article presents a new restriction of the classical basic computational model that combines process participation and a constraint on failure occurrences that can happen only while a predefined contention threshold has not yet been bypassed. This type of failure is called λ -constrained crashes, where λ defines the considered contention threshold. It appears that when assuming such contention-related crash failures and enriching the system with objects whose consensus number is k≥ 1, consensus for n processes can be solved for any n≥ k assuming up to k failures. The article proceeds incrementally. It first presents an algorithm that solves consensus on top of read/write registers if at most one crash occurs before the contention threshold λ= n- 1 has been bypassed. Then, it shows that if the system is enriched with objects whose consensus number is k≥ 1, then when λ= n- k, consensus can be solved despite up to kλ -constrained crashes, for any n≥ k, andwhen λ= n- 2 k+ 1, consensus can be solved despite up to 2 k- 1 λ -constrained crashes, assuming k divides n. Finally, impossibility results are presented for the number of λ -constrained failures that can be tolerated.

اللغة الأصليةالإنجليزيّة
عنوان منشور المضيفStabilization, Safety, and Security of Distributed Systems - 24th International Symposium, SSS 2022, Proceedings
المحررونStéphane Devismes, Franck Petit, Karine Altisen, Giuseppe Antonio Di Luna, Antonio Fernandez Anta
ناشرSpringer Science and Business Media Deutschland GmbH
عدد الصفحات13
رقم المعيار الدولي للكتب (المطبوع)9783031210167
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 2022
منشور خارجيًانعم
الحدث24th International Symposium on Stabilization, Safety, and Security of Distributed Systems, SSS 2022 - Clermont-Ferrand, فرنسا
المدة: ١٥ نوفمبر ٢٠٢٢١٧ نوفمبر ٢٠٢٢

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

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


!!Conference24th International Symposium on Stabilization, Safety, and Security of Distributed Systems, SSS 2022

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

Publisher Copyright:
© 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.


أدرس بدقة موضوعات البحث “Reaching Consensus in the Presence of Contention-Related Crash Failures'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا