DROPS

Document

Brief Announcement

DOI: 10.4230/LIPIcs.DISC.2026.61

Brief Announcement: Stone Duality Proofs for Colorless Distributed Computability Theorems

Authors: Cameron Calk and Emmanuel Godard

Published in: LIPIcs, Volume 397, 40th International Symposium on Distributed Computing (DISC 2026)

Abstract

Herlihy and Shavit [Herlihy and Shavit, 1999], Saks and Zaharoglou [M. Saks and F. Zaharoglou, 2000], building on the work of Borowsky and Gafni [Borowsky and Gafni, 1997], have shown that questions of distributed computability were amenable to a topological approach by encoding distributed systems as simplicial complexes. We present an extension of the simplicial semantics for distributed computing by identifying spectral topology as a natural generalization thereof. In particular, we extend the topological approach of the Asynchronous Computability Theorem to any round-based, content-neutral, full-information protocol, a family of models containing the Iterated Immediate Snapshot protocol. The main insight of this work is in considering global states obtained after finite executions of a distributed protocol Π not as abstract simplicial complexes as was previously done, but as finite posets. This extension enables us to prove a new general distributed computability theorem : a protocol Π solves a colorless task (ℐ,𝒪,Δ) if and only if there exists a spectral map f:Π^∞(ℐ) → 𝒪 compatible with Δ, where Π^∞(ℐ) is a spectral space associated to the protocol Π. This space is introduced in this work. From this general characterization, many known colorless computability theorems can be directly derived. In particular, we provide new insights into the previously established connection between colorless task-solvability and continuous maps between geometric realizations. Our proofs rely on Stone duality, a well established tool in semantics theory which links spectral spaces with distributive lattices. In this semantics, spaces correspond to program behaviours and lattices to program specifications, related by a crucial "ingredient" (see [Mai Gehrke, 2016]), namely topology.

Cite as

Cameron Calk and Emmanuel Godard. Brief Announcement: Stone Duality Proofs for Colorless Distributed Computability Theorems. In 40th International Symposium on Distributed Computing (DISC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 397, pp. 61:1-61:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{calk_et_al:LIPIcs.DISC.2026.61,
  author =	{Calk, Cameron and Godard, Emmanuel},
  title =	{{Brief Announcement: Stone Duality Proofs for Colorless Distributed Computability Theorems}},
  booktitle =	{40th International Symposium on Distributed Computing (DISC 2026)},
  pages =	{61:1--61:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-454-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{397},
  editor =	{Moses Jr., William K. and Censor-Hillel, Keren},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2026.61},
  URN =		{urn:nbn:de:0030-drops-281679},
  doi =		{10.4230/LIPIcs.DISC.2026.61},
  annote =	{Keywords: simplicial complex, partial order, spectral spaces, Stone duality, categorical semantics}
}

Document

Track B: Automata, Logic, Semantics, and Theory of Programming

DOI: 10.4230/LIPIcs.ICALP.2026.173

Stone Duality Proofs for Colorless Distributed Computability Theorems

Authors: Cameron Calk and Emmanuel Godard

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract

Twenty years ago, Herlihy/Shavit and Saks/Zaharoglou won the Gödel prize for the introduction of a simplicial semantics for distributed computing. This line of work culminated in a characterization of the distributed tasks which can be solved by asynchronous wait-free systems, resulting in the Asynchronous Computability Theorem (ACT). In this paper, we extend this semantics by identifying spectral topology as the natural generalization of the finite combinatorial topology they employed. In particular, we extend the topological approach of ACT to any round-based, content-neutral, full-information protocol. This family of protocols contains the Iterated Immediate Snapshot model (IIS), to which many distributed computation models can be reduced. In this sense, our work provides first steps towards a unified topological framework for distributed computing. The main insight of this work is in considering global states obtained after finite executions of a distributed protocol not as abstract simplicial complexes as was previously done, but as finite spectral spaces, considering the Alexandrov topology on the associated face posets. Using this point-set topological approach, coupled with the interpretation of a distributed protocol as an endofunctor Π on the category of simplicial complexes, we show that any initial configuration ℐ can be associated to a projective limit system of finite complexes. The limit thereof is a spectral space Π^∞(ℐ) which precisely encodes the behavior of the protocol presented by Π. This leads us to derive a new general distributed computability theorem using Stone duality: a protocol Π solves a colorless task (ℐ,𝒪,Δ) if and only if there exists a spectral map f:Π^∞(ℐ) → 𝒪 compatible with Δ. From this general characterization, we derive known colorless computability theorems, and provide new insights into the previously established connection between task-solvability and continuous maps between geometric realizations. This is achieved through Stone duality, a well established tool for such tight correspondences in computer science.

Cite as

Cameron Calk and Emmanuel Godard. Stone Duality Proofs for Colorless Distributed Computability Theorems. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 173:1-173:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{calk_et_al:LIPIcs.ICALP.2026.173,
  author =	{Calk, Cameron and Godard, Emmanuel},
  title =	{{Stone Duality Proofs for Colorless Distributed Computability Theorems}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{173:1--173:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.173},
  URN =		{urn:nbn:de:0030-drops-265615},
  doi =		{10.4230/LIPIcs.ICALP.2026.173},
  annote =	{Keywords: simplicial complex, partial order, spectral spaces, Stone duality, categorical semantics}
}

Search Results

Documents authored by Calk, Cameron

Brief Announcement: Stone Duality Proofs for Colorless Distributed Computability Theorems

Abstract

Cite as

Stone Duality Proofs for Colorless Distributed Computability Theorems

Abstract

Cite as

Thanks for your feedback!

Could not send message