2026-07-22T01:43:18Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7077 2024-03-06T10:39:29Z ddc:004 open_access

k-Set Agreement in Communication Networks with Omission Faults Godard, Emmanuel Perdereau, Eloi k-set agreement message passing dynamic networks message adversary omission faults We consider an arbitrary communication network G where at most f messages can be lost at each round, and consider the classical k-set agreement problem in this setting. We characterize exactly for which f the k-set agreement problem can be solved on G. The case with k = 1, that is the Consensus problem, has first been introduced by Santoro and Widmayer in 1989, the characterization is already known from [Coulouma/Godard/Peters, TCS, 2015]. As a first contribution, we present a detailed and complete characterization for the 2-set problem. The proof of the impossibility result uses topological methods. We introduce a new subdivision approach for these topological methods that is of independent interest. In the second part, we show how to extend to the general case with k in N. This characterization is the first complete characterization for this kind of synchronous message passing model, a model that is a subclass of the family of oblivious message adversaries. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Emmanuel Godard and Eloi Perdereau 2017 Is Part Of LIPIcs, Volume 70, 20th International Conference on Principles of Distributed Systems (OPODIS 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.OPODIS.2016.8 urn:nbn:de:0030-drops-70775 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2016.8 eng https://creativecommons.org/licenses/by/3.0/legalcode