License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2023.15
URN: urn:nbn:de:0030-drops-191417
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/19141/
Coutouly, Yannis ;
Godard, Emmanuel
A Topology by Geometrization for Sub-Iterated Immediate Snapshot Message Adversaries and Applications to Set-Agreement
Abstract
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.
BibTeX - Entry
@InProceedings{coutouly_et_al:LIPIcs.DISC.2023.15,
author = {Coutouly, Yannis and Godard, Emmanuel},
title = {{A Topology by Geometrization for Sub-Iterated Immediate Snapshot Message Adversaries and Applications to Set-Agreement}},
booktitle = {37th International Symposium on Distributed Computing (DISC 2023)},
pages = {15:1--15:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-301-0},
ISSN = {1868-8969},
year = {2023},
volume = {281},
editor = {Oshman, Rotem},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/19141},
URN = {urn:nbn:de:0030-drops-191417},
doi = {10.4230/LIPIcs.DISC.2023.15},
annote = {Keywords: topological methods, geometric simplicial complex, set-agreement}
}
Keywords: |
|
topological methods, geometric simplicial complex, set-agreement |
Collection: |
|
37th International Symposium on Distributed Computing (DISC 2023) |
Issue Date: |
|
2023 |
Date of publication: |
|
05.10.2023 |