Stone Duality Proofs for Colorless Distributed Computability Theorems

Cameron Calk (LIS)

Summary

We introduce a new topological encoding by spectral spaces of executions of round-based full-information adversaries, a model of distributed computations that is functorially presented and that contains many message adversaries. We give a characterization of the solvability of colorless tasks against compact adversaries. Message adversaries are distributed models that are known to be very expressive despite being round-based and crash-free. Colorless tasks are an important class of distributed tasks. For a colorless task, the specification does not depend upon the multiplicity of input or output values, like the ubiquitous agreement tasks. Therefore, our result is a significant step toward unifying topological methods in distributed computing. The main insight is to consider global states obtained after finite executions of a distributed protocol not as abstract simplicial complexes as previously done, but as spectral spaces, considering the Alexandrov topology on the faces poset. Given an adversary $\mathcal M$ with a set of inputs $\mathcal I$, we define a limit object $\Pi^\infty_\mathcal M(\mathcal I)$ by projective limit in the category of spectral spaces. We derive a new general distributed computability theorem using Stone duality: there exists an algorithm solving a colorless task $(\mathcal I,\mathcal O,\Delta)$ against the compact adversary $\mathcal M$ if and only if there exists a spectral map $f:\Pi^\infty_\mathcal M(\mathcal I)\longrightarrow\mathcal O$ compatible with $\Delta$. From this general characterization are derived many known colorless computability theorems. Quite surprisingly, colored and uncolored models have the same computability power (they solve the same colorless tasks). Our new proofs give topological reasons for this equivalence, previously known through algorithmic reductions.

Joint work with Emmanuel Godard.