Contention-related crash failures: Definitions, agreement algorithms, and impossibility results - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Theoretical Computer Science Année : 2022

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

Résumé

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)
Fichier principal
Vignette du fichier
TCS2022.pdf (241.54 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03746704 , version 1 (05-01-2023)

Identifiants

Citer

Anaïs Durand, Michel Raynal, Gadi Taubenfeld. Contention-related crash failures: Definitions, agreement algorithms, and impossibility results. Theoretical Computer Science, 2022, 909, pp.76-86. ⟨10.1016/j.tcs.2022.01.029⟩. ⟨hal-03746704⟩
104 Consultations
46 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More