Contention-related crash failures: Definitions, agreement algorithms, and impossibility results

Anaïs Durand, Michel Raynal, Gadi Taubenfeld

نتاج البحث: نشر في مجلةمقالةمراجعة النظراء


This article explores an interplay between process crash failures and concurrency. Namely, it aims at answering the question, “Is it possible to cope with more crash failures when some number of crashes occur before some predefined contention point happened?”. These crashes are named λ-constrained crashes, where λ is the predefined contention point (known by the processes). Hence, this article considers two types of process crashes: λ-constrained crashes and classical crashes (which can occur at any time and are consequently called any-time crashes). Considering a system made up of n asynchronous processes communicating through atomic read/write registers, the article focuses on the design of two agreement-related algorithms. Assuming λ=n−1 and no any-time failure, the first algorithm solves the consensus problem in the presence of one λ-constrained crash failure, thereby circumventing the well-known FLP impossibility result. The second algorithm considers k-set agreement for k≥2. It is a k-set agreement algorithm such that λ=n−ℓ and ℓ≥k=m+f that works in the presence of up to (2m+ℓ−k) λ-constrained crashes and (f−1) any-time crashes, i.e., up to t=(2m+ℓ−k)+(f−1) process crashes. It follows that considering the timing of failures with respect to a predefined contention point enlarges the space of executions in which k-set agreement can be solved despite the combined effect of asynchrony, concurrency, and process crashes. The paper also presents agreement-related impossibility results for consensus and k-set agreement in the context of λ-constrained process crashes (with or without any-time crashes).

اللغة الأصليةالإنجليزيّة
الصفحات (من إلى)76-86
عدد الصفحات11
دوريةTheoretical Computer Science
مستوى الصوت909
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 28 مارس 2022
منشور خارجيًانعم

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

Funding Information:
The authors want to thank the reviewers whose constructive comments helped improve the article's content and presentation.

Publisher Copyright:
© 2022 Elsevier B.V.


أدرس بدقة موضوعات البحث “Contention-related crash failures: Definitions, agreement algorithms, and impossibility results'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا