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
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 28 מרץ 2022
פורסם באופן חיצוניכן

הערה ביבליוגרפית

Publisher Copyright:
© 2022 Elsevier B.V.

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Contention-related crash failures: Definitions, agreement algorithms, and impossibility results'. יחד הם יוצרים טביעת אצבע ייחודית.

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