2026-08-08T00:33:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19141 2024-03-06T11:03:31Z ddc:004 open_access

A Topology by Geometrization for Sub-Iterated Immediate Snapshot Message Adversaries and Applications to Set-Agreement Coutouly, Yannis Godard, Emmanuel topological methods geometric simplicial complex set-agreement The Iterated Immediate Snapshot model (IIS) is a central model in the message adversary setting. We consider general message adversaries whose executions are arbitrary subsets of the executions of the IIS message adversary. We present a complete and explicit characterization and lower bounds for solving set-agreement for general sub-IIS message adversaries. In order to have this characterization, we introduce a new topological approach for such general adversaries, closely associating executions to geometric simplicial complexes. This way, it is possible to define and explicitly construct a topology directly on the considered sets of executions. We believe this topology by geometrization to be of independent interest and a good candidate to investigate distributed computability in general sub-IIS message adversaries, as this could provide both simpler and more powerful ways of using topology for distributed computability. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yannis Coutouly and Emmanuel Godard 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.15 urn:nbn:de:0030-drops-191417 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2023.15 eng https://creativecommons.org/licenses/by/4.0/legalcode