2026-07-23T20:16:42Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19130 2024-03-06T11:03:29Z ddc:004 open_access

One Step Forward, One Step Back: FLP-Style Proofs and the Round-Reduction Technique for Colorless Tasks Attiya, Hagit Fraigniaud, Pierre Paz, Ami Rajsbaum, Sergio Wait-free computing lower bounds The paper compares two generic techniques for deriving lower bounds and impossibility results in distributed computing. First, we prove a speedup theorem (a-la Brandt, 2019), for wait-free colorless algorithms, aiming at capturing the essence of the seminal round-reduction proof establishing a lower bound on the number of rounds for 3-coloring a cycle (Linial, 1992), and going by backward induction. Second, we consider FLP-style proofs, aiming at capturing the essence of the seminal consensus impossibility proof (Fischer, Lynch, and Paterson, 1985) and using forward induction. We show that despite their very different natures, these two forms of proof are tightly connected. In particular, we show that for every colorless task Π, if there is a round-reduction proof establishing the impossibility of solving Π using wait-free colorless algorithms, then there is an FLP-style proof establishing the same impossibility. For 1-dimensional colorless tasks (for an arbitrarily number n ≥ 2 of processes), we prove that the two proof techniques have exactly the same power, and more importantly, both are complete: if a 1-dimensional colorless task is not wait-free solvable by n ≥ 2 processes, then the impossibility can be proved by both proof techniques. Moreover, a round-reduction proof can be automatically derived, and an FLP-style proof can be automatically generated from it. Finally, we illustrate the use of these two techniques by establishing the impossibility of solving any colorless covering task of arbitrary dimension by wait-free algorithms. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hagit Attiya and Pierre Fraigniaud and Ami Paz and Sergio Rajsbaum 2023 Is Part Of LIPIcs, Volume 281, 37th International Symposium on Distributed Computing (DISC 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2023.4 urn:nbn:de:0030-drops-191304 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2023.4 eng https://creativecommons.org/licenses/by/4.0/legalcode