Search Results

Documents authored by Coutouly, Yannis

Document
DOI: 10.4230/LIPIcs.OPODIS.2025.13
A General Input-Dependent Colorless Computability Theorem and Applications to Core-Dependent Adversaries

Authors: Yannis Coutouly and Emmanuel Godard

Published in: LIPIcs, Volume 361, 29th International Conference on Principles of Distributed Systems (OPODIS 2025)

Abstract
Distributed computing tasks can be presented with a triple (ℐ,𝒪,Δ). The solvability of a colorless task on the Iterated Immediate Snapshot model (IIS) has been characterized by the Colorless Computability Theorem [Maurice Herlihy et al., 2013]. A recent paper [Yannis Coutouly and Emmanuel Godard, 2024] generalizes this theorem for any message adversaries ℳ ⊆ IIS by geometric methods. In 2001, Mostéfaoui, Rajsbaum, Raynal, and Roy [Achour Mostéfaoui et al., 2002] introduced condition-based adversaries. This setting considers a particular adversary that will be applied only to a subset of input configurations. In this setting, they studied the k-set agreement task with condition-based t-resilient adversaries and obtained a sufficient condition on the conditions that make k-Set Agreement solvable. In this paper we have three contributions: 1) We generalize the characterization of [Yannis Coutouly and Emmanuel Godard, 2024] to input-dependent adversaries, which means that the adversaries can change depending on the input configuration. 2) We show that core-resilient adversaries of IIS_n have the same computability power as the core-resilient adversaries of IIS_n where crashes only happen at the start. 3) Using the two previous contributions, we provide a necessary and sufficient characterization of the condition-based, core-dependent adversaries that can solve k-Set Agreement. We also distinguish four settings that may appear when presenting a distributed task as (ℐ,𝒪,Δ). Finally, in a later section, we present structural properties on the carrier map Δ. Such properties allow simpler proof, without changing the computability power of the task. Most of the proofs in this article leverage the topological framework used in distributed computing by using simple geometric constructions.
Cite as

Yannis Coutouly and Emmanuel Godard. A General Input-Dependent Colorless Computability Theorem and Applications to Core-Dependent Adversaries. In 29th International Conference on Principles of Distributed Systems (OPODIS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 361, pp. 13:1-13:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{coutouly_et_al:LIPIcs.OPODIS.2025.13,
  author =	{Coutouly, Yannis and Godard, Emmanuel},
  title =	{{A General Input-Dependent Colorless Computability Theorem and Applications to Core-Dependent Adversaries}},
  booktitle =	{29th International Conference on Principles of Distributed Systems (OPODIS 2025)},
  pages =	{13:1--13:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-409-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{361},
  editor =	{Arusoaie, Andrei and Onica, Emanuel and Spear, Michael and Tucci-Piergiovanni, Sara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2025.13},
  URN =		{urn:nbn:de:0030-drops-251862},
  doi =		{10.4230/LIPIcs.OPODIS.2025.13},
  annote =	{Keywords: colorless task, topological methods, geometric simplicial complex, k-set-agreement, t-resilient model, condition-based computability}
}
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}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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