Emmanuel Godard

Cameron Calk, Emmanuel Godard

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.

Arnaud Casteigts, Paola Flocchini, Emmanuel Godard et al.

In infrastructure-less highly dynamic networks, computing and performing even basic tasks (such as routing and broadcasting) is a very challenging activity due to the fact that connectivity does not necessarily hold, and the network may actually be disconnected at every time instant. Clearly the task of designing protocols for these networks is less difficult if the environment allows waiting (i.e., it provides the nodes with store-carry-forward-like mechanisms such as local buffering) than if waiting is not feasible. No quantitative corroborations of this fact exist (e.g., no answer to the question: how much easier?). In this paper, we consider these qualitative questions about dynamic networks, modeled as time-varying (or evolving) graphs, where edges exist only at some times. We examine the difficulty of the environment in terms of the expressivity of the corresponding time-varying graph; that is in terms of the language generated by the feasible journeys in the graph. We prove that the set of languages $L_{nowait}$ when no waiting is allowed contains all computable languages. On the other end, using algebraic properties of quasi-orders, we prove that $L_{wait}$ is just the family of regular languages. In other words, we prove that, when waiting is no longer forbidden, the power of the accepting automaton (difficulty of the environment) drops drastically from being as powerful as a Turing machine, to becoming that of a Finite-State machine. This (perhaps surprisingly large) gap is a measure of the computational power of waiting. We also study bounded waiting; that is when waiting is allowed at a node only for at most $d$ time units. We prove the negative result that $L_{wait[d]} = L_{nowait}$; that is, the expressivity decreases only if the waiting is finite but unpredictable (i.e., under the control of the protocol designer and not of the environment).