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.

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.

An anonymous shared memory REG can be seen as an array of atomic registers such that there is no a priori agreement among the processes on the names of the registers. As an example a very same physical register can be known as REG[x] by a process p and as REG[y] (where y ≠ x) by another process q. Moreover, the register known as REG[a] by a process p and the register known as REG[b] by a process q can be the same physical register. It is assumed that each process has a unique identifier that can only be compared for equality. This article is on solving the d-election problem, in which it is required to elect at least one and at most d leaders, in such an anonymous shared memory system. We notice that the 1-election problem is the familiar leader election problem. Let n be the number of processes and m the size of the anonymous memory (number of atomic registers). The article shows that the condition gcd(m, n) ≤ d is necessary and sufficient for solving the d-election problem, where communication is through read/write or read+modify+write registers. The algorithm used to prove the sufficient condition relies on Bezout's Identity - a Diophantine equation relating numbers according to their Greatest Common Divisor. Furthermore, in the process of proving the sufficient condition, it is shown that 1-leader election can be solved using only a single read/write register (which refutes a 1989 conjecture stating that three non-anonymous registers are necessary), and that the exact d-election problem, where exactly d leaders must be elected, can be solved if and only if gcd(m, n) divides d.

Abstract We consider the well-known Coordinated Attack Problem, where two generals have to decide on a common attack, when their messengers can be captured by the enemy. Informally, this problem represents the difficulties to agree in the presence of communication faults. We consider here only omission faults (loss of message), but contrary to previous studies, we do not to restrict the way messages can be lost, i.e., we make no specific assumption, we use no specific failure metric. In the large subclass of message adversaries where the double simultaneous omission can never happen, we characterize which ones are obstructions for the Coordinated Attack Problem. We give two proofs of this result. One is combinatorial and uses the classical bivalency technique for the necessary condition. The second is topological and uses simplicial complexes to prove the necessary condition. We also present two different Consensus algorithms that are combinatorial (resp. topological) in essence. Finally, we analyze the two proofs and illustrate the relationship between the combinatorial approach and the topological approach in the very general case of message adversaries. We show that the topological characterization gives a clearer explanation of why some message adversaries are obstructions or not. This result is a convincing illustration of the power of topological tools for distributed computability.

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.

We consider infrastructure-less highly dynamic networks, where connectivity does not necessarily hold, and the network may actually be disconnected at every time instant. These networks are naturally modeled as time-varying graphs. 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. We provide a quantitative corroboration of this fact 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 Lnowait when no waiting is allowed contains all computable languages. On the other end, we prove that Lwait is just the family of regular languages. This 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] = Lnowait.

We consider the well known Coordinated Attack Problem, where two generals have to decide on a common attack, when their messengers can be captured by the enemy. Informally, this problem represents the difficulties to agree in the present of communication faults. We consider here only omission faults (loss of message), but contrary to previous studies, we do not to restrict the way messages can be lost, ie. we use no specific failure metric. Our contribution is threefold. First, we introduce the study of arbitrary patterns of failure ("omission schemes"), proposing notions and notations that revealed very convenient to handle. In the large subclass of omission schemes where the double simultaneous omission can never happen, we characterize which one are obstructions for the Coordinated Attack Problem. We present then some interesting applications. We show for the first time that the well studied omission scheme, where at most one message can be lost at each round, is a kind of least worst case environment for the Coordinated Attack Problem. We also extend our study to networks of arbitrary size. In particular, we address an open question of Santoro and Wid mayer about the Consensus Problem in communication networks with omission faults.