Search Results

Documents authored by Godard, Emmanuel

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}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2016.8
k-Set Agreement in Communication Networks with Omission Faults

Authors: Emmanuel Godard and Eloi Perdereau

Published in: LIPIcs, Volume 70, 20th International Conference on Principles of Distributed Systems (OPODIS 2016)

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

Emmanuel Godard and Eloi Perdereau. k-Set Agreement in Communication Networks with Omission Faults. In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, pp. 8:1-8:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{godard_et_al:LIPIcs.OPODIS.2016.8,
  author =	{Godard, Emmanuel and Perdereau, Eloi},
  title =	{{k-Set Agreement in Communication Networks with Omission Faults}},
  booktitle =	{20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
  pages =	{8:1--8:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-031-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{70},
  editor =	{Fatourou, Panagiota and Jim\'{e}nez, Ernesto and Pedone, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2016.8},
  URN =		{urn:nbn:de:0030-drops-70775},
  doi =		{10.4230/LIPIcs.OPODIS.2016.8},
  annote =	{Keywords: k-set agreement, message passing, dynamic networks, message adversary, omission faults}
}
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