2026-07-25T12:26:00Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14838 2024-03-06T10:54:58Z ddc:004 open_access

Extension-Based Proofs for Synchronous Message Passing Sheng, Yilun Ellen, Faith Set agreement lower bounds valency arguments There is no wait-free algorithm that solves k-set agreement among n ≥ k+1 processes in asynchronous systems where processes communicate using only registers. However, proofs of this result for k ≥ 2 are complicated and involve topological reasoning. To explain why such sophisticated arguments are necessary, Alistarh, Aspnes, Ellen, Gelashvili, and Zhu recently introduced extension-based proofs, which generalize valency arguments, and proved that there are no extension-based proofs of this result. In the synchronous message passing model, k-set agreement is solvable, but there is a lower bound of t rounds for any k-set agreement algorithm among n > kt processes when at most k processes can crash each round. The proof of this result for k ≥ 2 is also a complicated topological argument. We define a notion of extension-based proofs for this model and we show there are no extension-based proofs that t rounds are necessary for any k-set agreement algorithm among n = kt+1 processes, for k ≥ 2 and t > 2, when at most k processes can crash each round. In particular, our result shows that no valency argument can prove this lower bound. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yilun Sheng and Faith Ellen 2021 Is Part Of LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2021.36 urn:nbn:de:0030-drops-148380 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.36 eng https://creativecommons.org/licenses/by/4.0/legalcode