Search Results

Documents authored by Coutouly, Yannis

Document
DOI: 10.4230/LIPIcs.DISC.2024.16
A Simple Computability Theorem for Colorless Tasks in Submodels of the Iterated Immediate Snapshot

Authors: Yannis Coutouly and Emmanuel Godard

Published in: LIPIcs, Volume 319, 38th International Symposium on Distributed Computing (DISC 2024)

Abstract
The Iterated Immediate Snapshot model (IIS) is a central model in distributed computing. We present our work in the message adversary setting. We consider general message adversaries whose executions are arbitrary subsets of executions M of the IIS message adversary. We present a complete and explicit characterization of solvable colorless tasks given any submodel of IIS. Based upon the geometrization mapping geo introduced in [Yannis Coutouly and Emmanuel Godard, 2023] to investigate set-agreement in general submodels, we give a simple necessary and sufficient condition for computability. The geometrization geo associates to any execution a point in R^N. A colorless task (I, O, Δ) is solvable under M if and only if there is a continuous function f : geo(skelⁿ(I) × M) ⟶ | O| carried by Δ. This necessary and sufficient condition for colorless tasks was already known for full models like the Iterated Immediate Snapshot model [Maurice Herlihy et al., 2013] so our result is an extension of the characterization to any arbitrary submodels. It also shows the notion of continuity that is relevant for distributed computability of submodels is not the one from abstract simplicial complexes but the standard one from R^N. As an example of its effectiveness, we can now derive the characterization of the computability of set-agreement on submodels from [Yannis Coutouly and Emmanuel Godard, 2023] by a direct application of the No-Retraction theorem of standard topology textbook. We also give a new fully geometric proof of the known characterization of computable colorless tasks for t-resilient layered snapshot model by using cross-sections of fiber bundles, a standard tool in algebraic topology.
Cite as

Yannis Coutouly and Emmanuel Godard. A Simple Computability Theorem for Colorless Tasks in Submodels of the Iterated Immediate Snapshot. In 38th International Symposium on Distributed Computing (DISC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 319, pp. 16:1-16:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{coutouly_et_al:LIPIcs.DISC.2024.16,
  author =	{Coutouly, Yannis and Godard, Emmanuel},
  title =	{{A Simple Computability Theorem for Colorless Tasks in Submodels of the Iterated Immediate Snapshot}},
  booktitle =	{38th International Symposium on Distributed Computing (DISC 2024)},
  pages =	{16:1--16:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-352-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{319},
  editor =	{Alistarh, Dan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2024.16},
  URN =		{urn:nbn:de:0030-drops-212422},
  doi =		{10.4230/LIPIcs.DISC.2024.16},
  annote =	{Keywords: topological methods, geometric simplicial complex, set-agreement}
}
Document
DOI: 10.4230/LIPIcs.DISC.2023.15
A Topology by Geometrization for Sub-Iterated Immediate Snapshot Message Adversaries and Applications to Set-Agreement

Authors: Yannis Coutouly and Emmanuel Godard

Published in: LIPIcs, Volume 281, 37th International Symposium on Distributed Computing (DISC 2023)

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.
Cite as

Yannis Coutouly and Emmanuel Godard. A Topology by Geometrization for Sub-Iterated Immediate Snapshot Message Adversaries and Applications to Set-Agreement. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 15:1-15:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.DISC.2023.15},
  URN =		{urn:nbn:de:0030-drops-191417},
  doi =		{10.4230/LIPIcs.DISC.2023.15},
  annote =	{Keywords: topological methods, geometric simplicial complex, set-agreement}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact