Stone Duality Proofs for Colorless Distributed Computability Theorems
For researchers in distributed computing, this work provides a unifying topological framework that recasts known results and offers new insights, though the main results are not novel in terms of task solvability.
The authors introduce a new topological encoding of distributed protocol executions using spectral spaces, and prove a characterization of solvability for colorless tasks against compact adversaries via Stone duality. This yields new proofs of known computability theorems and shows that colored and uncolored Iterated Immediate Snapshot models have equivalent computational power.
We introduce a new topological encoding of executions of round-based, full-information distributed protocols via spectral spaces. Such protocols constitute a model of distributed computations which are functorially presented and englobe message adversaries. We give a characterization of the solvability of colorless tasks against compact adversaries. Colorless tasks are an important class of distributed tasks, examples thereof including the ubiquitous agreement tasks. Therefore, our result is a significant step toward unifying topological methods in 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 spectral spaces, considering the Alexandrov topology on the associated face posets. Given an adversary $\mathcal{M}$ with a set of inputs $\mathcal{I}$, we define a limit object $Π^\infty_{\mathcal{M}}(\mathcal{I})$ by a projective limit in the category of spectral spaces. This encodes all distributed information about the adversary, allowing us to derive a new distributed computability theorem using Stone duality: there exists an algorithm solving a colorless task $(\mathcal{I},\mathcal{O},Δ)$ against the compact adversary $\mathcal{M}$ if and only if there exists a spectral map $Π^\infty_{\mathcal{M}}(\mathcal{I})\rightarrow\mathcal{O}$ compatible with $Δ$. From this characterization, we derive the known colorless computability theorems for (colored or uncolored) Iterated Immediate Snapshot. Quite surprisingly, colored and uncolored models have the same distributed computability power, i.e. they solve the same tasks. Our new proofs give topological reasons for this equivalence, previously known through algorithmic reductions.