A key result of distributed computing in asynchronous systems is a characterization for the wait-free solvability of colorless tasks by the existence of a continuous map from the task's input complex (representing the valid input configurations) to its output complex (representing the valid output configurations) which respects that task's specification. This natural characterization led to many proofs, mainly of impossibility: showing that a colorless task is not wait-free solvable, can be done by proving that there is no continuous map (respecting the task's specification) between two simplicial complexes, which can be done using classical topological machinery.

We consider a stochastic network model consisting of a set of n synchronous processes communicating by message passing. In each round, processes send messages directly to each other over a complete communication graph. The processes do not fail, but messages can be lost. Each message is delivered with probability p, for a given parameter p ∈ [0,1]. We study the following optimization version of approximate agreement in this model. We assume that processes start with binary input values, execute an algorithm for a fixed number of rounds, and decide values in [0,1] satisfying the usual validity requirement stating that if all processes start with the same input value, then they should all decide that value. We propose deterministic algorithms that minimize the expected discrepancy, namely, the expected maximum distance between the decided values. We also present lower bounds on the expected discrepancy, which demonstrate the optimality of our algorithms for two processes. Finally, we present applications of our algorithms to solve randomized consensus and randomized approximate agreement.

Abstract We study two fundamental problems of distributed computing, consensus and approximate agreement, through a novel approach for proving lower bounds and impossibility results, that we call the asynchronous speedup theorem. For a given n-process task $$\Pi $$ Π and a given computational model M, we define a new task, called the closure of $$\Pi $$ Π with respect to M. The asynchronous speedup theorem states that if a task $$\Pi $$ Π is solvable in $$t\ge 1$$ t ≥ 1 rounds in M, then its closure w.r.t. M is solvable in $$t-1$$ t - 1 rounds in M. We prove this theorem for iterated models, as long as the model allows solo executions. We illustrate the power of our asynchronous speedup theorem by providing a new proof of the wait-free impossibility of consensus using read/write registers, and a new proof of the wait-free impossibility of solving consensus using registers and test&set objects for $$n>2$$ n > 2 . The proof is merely by showing that, in each case, the closure of consensus (w.r.t. the corresponding model) is consensus itself. Our main application is the study of the power of additional objects, namely test&set and binary consensus, for wait-free solving approximate agreement faster. By analyzing the closure of approximate agreement w.r.t. each of the two models, we show that while these objects are more powerful than read/write registers from the computability perspective, they are not more powerful as far as helping solving approximate agreement faster is concerned.

The celebrated Asynchronous Computability Theorem of Herlihy and Shavit (JACM 1999) provided a topological characterization of the tasks that are wait-free solvable by processes communicating through writing and reading shared registers. This characterization assumes the use of full-information protocols, in which each time a process writes in the shared memory, it communicates everything it learned since the beginning of the execution. Thus, each register in the shared memory is of unbounded size. Whether unbounded size registers are unavoidable for the model of computation to be universal is the central question studied in this paper. More generally, when at most t out of n processes can crash, is the model with bounded size registers universal?

The topological view on distributed computing represents a task T as a relation Δ between the complex ℐ of its inputs and the complex 𝒪 of its outputs. A cornerstone result in the field is an elegant computability characterization of the solvability of colorless tasks in terms of ℐ, 𝒪 and Δ. Essentially, a colorless task is wait-free solvable if and only if there is a continuous map from the geometric realization of ℐ to that of 𝒪 that respects Δ. This paper makes headway towards providing an analogous characterization for general tasks, which are not necessarily colorless, by concentrating on the case of three-process inputless tasks. Our key contribution is identifying local articulation points as an obstacle for the solvability of general tasks, and defining a topological deformation on the output complex of a task T, which eliminates these points by splitting them, to obtain a new task T', with an adjusted relation Δ' between the input complex ℐ and an output complex 𝒪' without articulation points. We obtain a new characterization of wait-free solvability of three-process general tasks: T is wait-free solvable if and only if there is a continuous map from the geometric realization of ℐ to that of 𝒪' that respects Δ'.

In recent years, a new class of models for multi-agent epistemic logic has emerged, based on simplicial complexes. Since then, many variants of these simplicial models have been investigated, giving rise to different logics and axiomatizations. In this paper, we present a further generalization, which encompasses all previously studied variants of simplicial models. Geometrically, this is achieved by generalizing beyond simplicial complexes, and considering instead semi-simplicial sets. By doing so, we define a new semantics for epistemic logic with distributed knowledge, where a group of agents may distinguish two worlds, even though each individual agent in the group is unable to distinguish them. As it turns out, these models are the geometric counterpart of a generalization of Kripke models, called "pseudo-models". We show how to recover the previously defined variants of simplicial models as sub-classes of our models; and give a sound and complete axiomatization for each of them.

The paper compares two generic techniques for deriving lower bounds and impossibility results in distributed computing. First, we prove a speedup theorem (a-la Brandt, 2019), for wait-free colorless algorithms, aiming at capturing the essence of the seminal round-reduction proof establishing a lower bound on the number of rounds for 3-coloring a cycle (Linial, 1992), and going by backward induction. Second, we consider FLP-style proofs, aiming at capturing the essence of the seminal consensus impossibility proof (Fischer, Lynch, and Paterson, 1985) and using forward induction. We show that despite their very different natures, these two forms of proof are tightly connected. In particular, we show that for every colorless task $Π$, if there is a round-reduction proof establishing the impossibility of solving $Π$ using wait-free colorless algorithms, then there is an FLP-style proof establishing the same impossibility. For 1-dimensional colorless tasks (for an arbitrary number $n\geq 2$ of processes), we prove that the two proof techniques have exactly the same power, and more importantly, both are complete: if a 1-dimensional colorless task is not wait-free solvable by $n\geq 2$ processes, then the impossibility can be proved by both proof techniques. Moreover, a round-reduction proof can be automatically derived, and an FLP-style proof can be automatically generated from it. Finally, we illustrate the use of these two techniques by establishing the impossibility of solving any colorless covering task of arbitrary dimension by wait-free algorithms.

Abstract The safe-consensus task was introduced by Afek, Gafni and Lieber (DISC’ 09) as a weakening of the classic consensus. When there is concurrency, the consensus output can be arbitrary, not even the input of any process. They showed that safe-consensus is equivalent to consensus, in a wait-free system. We study the solvability of consensus in three shared memory iterated models extended with the power of safe-consensus black boxes. In the first iterated model, for thei-th iteration, the processes write to memory, then they snapshot it and finally they invoke safe-consensus boxes. We prove that in this model, consensus cannot be implemented. In a second iterated model, processes first invoke safe-consensus, then they write to memory and finally they snapshot it. We show that this model is equivalent to the previous model and thus consensus cannot be implemented. In the last iterated model, processes write to the memory, invoke safe-consensus boxes and finally they snapshot the memory. We show that in this model, any wait-free implementation of consensus requires $$\Omega (n^{2})$$ Ω(n2) safe-consensus black-boxes and this bound is tight.

The celebrated 1999 Asynchronous Computability Theorem (ACT) of Herlihy and Shavit characterized distributed tasks that are wait-free solvable and uncovered deep connections with combinatorial topology. We provide an alternative characterization of those tasks by means of the novel concept of continuous tasks, which have an input/output specification that is a continuous function between the geometric realizations of the input and output complex: We state and prove a precise characterization theorem (CACT) for wait-free solvable tasks in terms of continuous tasks. Its proof utilizes a novel chromatic version of a foundational result in algebraic topology, the simplicial approximation theorem, which is also proved in this paper. Apart from the alternative proof of the ACT implied by our CACT, we also demonstrate that continuous tasks have an expressive power that goes beyond classic task specifications, and hence open up a promising venue for future research: For the well-known approximate agreement task, we show that one can easily encode the desired proportion of the occurrence of specific outputs, namely, exact agreement, in the continuous task specification.

We study two fundamental problems of distributed computing, consensus and approximate agreement, through a novel approach for proving lower bounds and impossibility results, that we call the asynchronous speedup theorem. For a given n-process task Ρ and a given computational model M, we define a new task, called the closure of Ρ with respect to M. The asynchronous speedup theorem states that if a task Ρ is solvable in t ≥ 1 rounds in M, then its closure w.r.t. M is solvable in t ≥ 1 rounds in M. We prove this theorem for iterated models, as long as the model allows solo executions. We illustrate the power of our asynchronous speedup theorem by providing a new proof of the wait-free impossibility of consensus using read/write registers, and a new proof of the wait-free impossibility of solving consensus using registers and test&set objects for > 2. The proof is merely by showing that, in each case, the closure of consensus (w.r.t. the corresponding model) is consensus itself. Our main application is the study of the power of additional objects, namely test&set and binary consensus, for wait-free solving approximate agreement faster. By analyzing the closure of approximate agreement w.r.t. each of the two models, we show that while these objects are more powerful than read/write registers from the computability perspective, they are not more powerful as far as helping solving approximate agreement faster is concerned.

Baryshnikov presented a remarkable algebraic topology proof of Arrow's impossibility theorem trying to understand the underlying reason behind the numerous proofs of this fundamental result of social choice theory. We present here a novel combinatorial topology approach that does not use advanced mathematics, while giving a geometric intuition of the impossibility. This exposes a remarkable connection with distributed computing techniques.

The standard semantics of multi-agent epistemic logic S5_n is based on Kripke models whose accessibility relations are reflexive, symmetric and transitive. This one dimensional structure contains implicit higher-dimensional information beyond pairwise interactions, that we formalized as pure simplicial models in a previous work in Information and Computation 2021 [Éric Goubault et al., 2021]. Here we extend the theory to encompass simplicial models that are not necessarily pure. The corresponding class of Kripke models are those where the accessibility relation is symmetric and transitive, but might not be reflexive. Such models correspond to the epistemic logic KB4_n. Impure simplicial models arise in situations where two possible worlds may not have the same set of agents. We illustrate it with distributed computing examples of synchronous systems where processes may crash.

Runtime verification is a lightweight method for monitoring the formal specification of a system during its execution. It has recently been shown that a given state predicate can be monitored consistently by a set of crash-prone asynchronous distributed monitors observing the system, only if each monitor can emit verdicts taken from a large enough finite set. We revisit this impossibility result in the concrete context of linear-time logic ( ltl ) semantics for runtime verification, that is, when the correctness of the system is specified by an ltl formula on its execution traces. First, we show that monitors synthesized based on the 4-valued semantics of ltl ( rv-ltl ) may result in inconsistent distributed monitoring, even for some simple ltl formulas. More generally, given any ltl formula φ, we relate the number of different verdicts required by the monitors for consistently monitoring φ, with a specific structural characteristic of φ called its alternation number . Specifically, we show that, for every k ≥ 0 , there is an ltl formula φ with alternation number k that cannot be verified at runtime by distributed monitors emitting verdicts from a set of cardinality smaller than k + 1. On the positive side, we define a family of logics, called distributed ltl (abbreviated as dltl ), parameterized by k ≥ 0, which refines rv-ltl by incorporating 2k + 4 truth values. Our main contribution is to show that, for every k ≥ 0, every ltl formula φ with alternation number k can be consistently monitored by distributed monitors, each running an automaton based on a (2 ⌈ k /2 ⌉ +4)-valued logic taken from the dltl family.

An elegant strategy for proving impossibility results in distributed computing was introduced in the celebrated FLP consensus impossibility proof. This strategy is local in nature as at each stage, one configuration of a hypothetical protocol for consensus is considered, together with future valencies of possible extensions. This proof strategy has been used in numerous situations related to consensus, leading one to wonder why it has not been used in impossibility results of two other well-known tasks: set agreement and renaming. This paper provides an explanation of why impossibility proofs of these tasks have been of a global nature. It shows that a protocol can always solve such tasks locally, in the following sense. Given a configuration and all its future valencies, if a single successor configuration is selected, then the protocol can reveal all decisions in this branch of executions, satisfying the task specification. This result is shown for both set agreement and renaming, implying that there are no local impossibility proofs for these tasks.

Considering asynchronous shared memory systems in which any number of processes may crash, this work identifies and formally defines relaxations of queues and stacks that can be non-blocking or wait-free while being implemented using only read/write operations. Set-linearizability and Interval-linearizability are used to specify the relaxations formally, and precisely identify the subset of executions which preserve the original sequential behavior. The relaxations allow for an item to be returned more than once by different operations, but only in case of concurrency; we call such a property multiplicity. The stack implementation is wait-free, while the queue implementation is non-blocking. Interval-linearizability is used to describe a queue with multiplicity, with the additional relaxation that a dequeue operation can return weak-empty, which means that the queue might be empty. We present a read/write wait-free interval-linearizable algorithm of a concurrent queue. As far as we know, this work is the first that provides formalizations of the notions of multiplicity and weak-emptiness, which can be implemented on top of read/write registers only.

We present an implementation of an eventually perfect failure detector in an arbitrarily connected, partitionable network. We assume ADD channels: for each one there exist constants K, D, not known to the processes, such that for every K consecutive messages sent in one direction, at least one is delivered within time D. The best previous implementation used messages of bounded size, but exponential in n, the number of nodes. The main contribution of this paper is a novel use of time-to-live values in the design of failure detectors, obtaining a flexible implementation that uses messages of size O(n log n).

More than two decades ago, combinatorial topology was shown to be useful for analyzing distributed fault-tolerant algorithms in shared memory systems and in message passing systems. In this work, we show that combinatorial topology can also be useful for analyzing distributed algorithms in networks of arbitrary structure. To illustrate this, we analyze consensus, set-agreement, and approximate agreement in networks, and derive lower bounds for these problems under classical computational settings, such as the LOCAL model and dynamic networks.

We introduce a family of tasks for n processes, as a generalization of the two process equality negation task of Lo and Hadzilacos (SICOMP 2000). Each process starts the computation with a private input value taken from a finite set of possible inputs. After communicating with the other processes using immediate snapshots, the process must decide on a binary output value, 0 or 1. The specification of the task is the following: in an execution, if the set of input values is large enough, the processes should agree on the same output; if the set of inputs is small enough, the processes should disagree; and in-between these two cases, any output is allowed. Formally, this specification depends on two threshold parameters k and l, with k<l, indicating when the cardinality of the set of inputs becomes "small" or "large", respectively. We study the solvability of this task depending on those two parameters. First, we show that the task is solvable whenever k+2 <= l. For the remaining cases (l = k+1), we use various combinatorial topology techniques to obtain two impossibility results: the task is unsolvable if either k <= n/2 or n-k is odd. The remaining cases are still open.

The Dijkstra Prize Committee has decided to grant the 2018 Edsger W. Dijkstra Prize in Distributed Computing to Bowen Alpern and Fred B. Schneider for their paper:

Tasks and objects are two predominant ways of specifying distributed problems where processes should compute outputs based on their inputs. Roughly speaking, a task specifies, for each set of processes and each possible assignment of input values, their valid outputs. In contrast, an object is defined by a sequential specification. Also, an object can be invoked multiple times by each process, while a task is a one-shot problem. Each one requires its own implementation notion, stating when an execution satisfies the specification. For objects, linearizability is commonly used, while tasks implementation notions are less explored. The article introduces the notion of interval-sequential object, and the corresponding implementation notion of interval-linearizability , to encompass many problems that have no sequential specification as objects. It is shown that interval-sequential specifications are local , namely, one can consider interval-linearizable object implementations in isolation and compose them for free, without sacrificing interval-linearizability of the whole system. The article also introduces the notion of refined tasks and its corresponding satisfiability notion. In contrast to a task, a refined task can be invoked multiple times by each process. Also, objects that cannot be defined using tasks can be defined using refined tasks. In fact, a main result of the article is that interval-sequential objects and refined tasks have the same expressive power and both are complete in the sense that they are able to specify any prefix-closed set of well-formed executions. Interval-linearizability and refined tasks go beyond unifying objects and tasks; they shed new light on both of them. On the one hand, interval-linearizability brings to task the following benefits: an explicit operational semantics, a more precise implementation notion, a notion of state, and a locality property. On the other hand, refined tasks open new possibilities of applying topological techniques to objects.

The LOOK-COMPUTE-MOVE model for a set of autonomous robots has been thoroughly studied for over two decades. Each robot repeatedly LOOKS at its surroundings and obtains a snapshot containing the positions of all robots; based on this information, the robot COMPUTES a destination and then MOVES to it. Previous work assumed all robots are present at the beginning of the computation. What would be the effect of robots appearing asynchronously? This paper studies thisquestion, for problems of bringing the robots close together, andexposes an intimate connection with combinatorial topology. A central problem in the mobile robots area is the gathering problem. In its discrete version, the robots start at vertices in some graph G known to them, move towards the same vertex and stop. The paper shows that if robots are asynchronous and may crash, then gathering is impossible for any graph G with at least two vertices, even if robots can have unique IDs, remember the past, know the same names for the vertices of G and use an arbitrary number of lights to communicate witheach other. Next, the paper studies two weaker variants of gathering: edge gathering and 1-gathering. For both problems we present possibility and impossibility results. The solvability of edge gathering is fully characterized: it is solvable for three or more robots on a given graph if and only if the graph is acyclic. Finally, general robot tasks in a graph are considered. A combinatorial topology characterization for the solvable tasks is presented, by a reduction of the asynchronous fault-tolerant LOOK-COMPUTE-MOVE model to a wait-free read/write shared-memory computing model, bringing together two areas that have been independently studied for a long time into a common theoretical foundation.

Distributed snapshots, as introduced by Chandy and Lamport in the context of asynchronous failure-free message-passing distributed systems, are consistent global states in which the observed distributed application might have passed through. It appears that two such distributed snapshots cannot necessarily be compared (in the sense of determining which one of them is the “first”). Differently, snapshots introduced in asynchronous crash-prone read/write distributed systems are totally ordered, which greatly simplify their use by upper layer applications. In order to benefit from shared memory snapshot objects, it is possible to simulate a read/write shared memory on top of an asynchronous crash-prone message-passing system, and build then snapshot objects on top of it. This algorithm stacking is costly in both time and messages. To circumvent this drawback, this paper presents algorithms building snapshot objects directly on top of asynchronous crash-prone message-passing system. “Directly” means here “without building an intermediate layer such as a read/write shared memory”. To the authors knowledge, the proposed algorithms are the first providing such constructions. Interestingly enough, these algorithms are efficient and relatively simple.

Adaptive renaming can be viewed as a coordination task involving a set of asynchronous agents, each aiming at grabbing a single resource out of a set of resources totally ordered by their desirability. We consider a generalization of adaptive renaming to take into account scenarios in which resources are not independent.

Processes in a concurrent system need to coordinate using an underlying shared memory or a message-passing system in order to solve agreement tasks such as, for example, consensus or set agreement. However, coordination is often needed to break the symmetry of processes that are initially in the same state---for example, to get exclusive access to a shared resource, to get distinct names, or to elect a leader. This paper introduces and studies the family of generalized symmetry breaking (GSB) tasks, which includes election, renaming, and many other symmetry breaking tasks, and studies how nondeterminism properties of objects solving tasks affects the computability power of GSB tasks. The aim is to develop the understanding of symmetry breaking tasks and their relation with agreement tasks and to study nondeterminism properties of objects solving tasks and how these properties affect the computability power of symmetry breaking tasks. Among various results characterizing the family of GSB tasks, it is shown that perfect renaming, i.e., $(n,n)$-renaming, is universal for all GSB tasks. The paper also shows that there is a large family of GSB tasks, which includes perfect renaming, that is strictly more powerful than $(n,n-1)$-set agreement. Some of these tasks are equivalent to perfect renaming, while others lie strictly between perfect renaming and $(n,n+1)$-renaming. Results comparing renaming and set agreement are proved, and the results in this paper complement known results. This paper sheds new light on the relations linking set agreement and symmetry breaking. The proofs are based on combinatorial topology techniques and new ideas about different notions of nondeterminism that can be associated with shared objects.

This paper is on the relative power and the relations linking two important synchronization problems in n-process wait-free shared memory models, namely, set agreement and renaming, which are two of the most studied subconsensus tasks. Since the 2006 seminal paper of Gafni, Rajsbaum and Herlihy, it is known that some renaming instances are strictly weaker than set agreement. Indeed, it was later on shown that not even (n + 1)-renaming (the strongest task in the renaming family, after perfect n-renaming) can implement (n - 1)-set agreement (the weakest non-trivial task in the set agreement family). These and other results seem to imply that renaming and, more generally, the tasks called generalized symmetry breaking tasks (GSB) are weaker than agreement tasks. This paper shows that this is not the case, namely, it shows that there is a large family of GSB tasks that are more powerful than (n - 1)-set agreement. Some of these tasks are equivalent to n-renaming, while others lie strictly between n-renaming and (n+1)-renaming. Moreover, none of these GSB tasks can solve (n - 2)-set agreement. Hence, these subconsensus tasks have a rich structure and are interesting in their own. The proofs of these results are based on algebraic topology techniques and new ideas about different notions of nondeterminism that can be associated with shared objects. Interestingly, this paper sheds a new light on the relations linking set agreement and renaming.

In the asynchronous wait-free shared memory model, two families of tasks play a central role because of their implications in theory and in practice: k-set agreement and M-renaming. Let n denote the number of processes in the system. Previous research shows that (n-1)-set agreement can solve (2n-2)-renaming, for any value of n, while (2n-2)-renaming cannot solve (n-1)-set agreement, when n is odd. It is also known that, for every n ≥ 3, n-renaming, also called perfect renaming, is strictly stronger than (n-1)-set agreement. This paper shows that when n ≥ 4, there is a family of tasks that are strictly stronger than (n-1)-set agreement and strictly weaker than perfect renaming. This enlarges our view of both the nature and the structure of what are distributed computing tasks.

If one model of computation can simulate another, then the existence (or non-existence) of an algorithm in the simulated model reduces to a related question about the simulating model. The BG-simulation algorithm uses this approach to prove that k-set agreement cannot be solved when t processes can crash, 1≤t≤k, by reduction to the wait-free case, where it is known that n+1 processes cannot solve n-set agreement, and similarly for any other colorless task. We give a definition, expressed in the language of combinatorial topology, for what it means for one model of distributed computation to simulate another with respect to the ability to solve colorless tasks. This definition is not linked to specific models or specific protocols. We show how to exploit elementary topological arguments to show when a simulation exists, without the need for an explicit construction. We use this approach to generalize the BG-simulation and to unify a number of simulation relations linking various models, some previously known, some not.

In the renaming task, n +1 processes start with unique input names from a large space and must choose unique output names taken from a smaller name space, 0,1,…, K . To rule out trivial solutions, a protocol must be anonymous : the value chosen by a process can depend on its input name and on the execution, but not on the specific process ID. Attiya et al. [1990] showed that renaming has a wait-free solution when K ≥ 2 n . Several algebraic topology proofs of a lower bound stating that no such protocol exists when K < 2 n have been published. In a companion article, we present the first completely combinatorial renaming lower bound proof stating if n + 1 is a primer power, then renaming is not wait-free solvable when K < 2 n . In this article, we show that if n + 1 is not a primer power, then there exists a wait-free renaming protocol for K = 2 n −1. Therefore the renaming lower bound for K < 2 n is incorrect. More precisely, our main theorem states that there exists a wait-free renaming protocol for K < 2 n if and only if n + 1 is not a prime power. We prove this result using the known equivalence of K -renaming for K = 2 n − 1 and the weak symmetry breaking task: processes have no input values and the output values are 0 or 1, and it is required that in every execution in which all processes participate, at least one process decides 1 and at least one process decides 0.

The recent deployment of multiprocessors (such as multicores) as the mainstream computing platform has given rise to a new concurrent programming impetus. In such a context it becomes extremely important to be able to design shared objects that can cope with the net effect of asynchrony and process crashes. This paper is a theory-oriented introduction to wait-free synchronization for such systems. It uses the adaptive renaming problem as a paradigm to explain the difficulties and subtleties of synchronization in presence of process crashes. Renaming is one of the most famous coordination problems studied in distributed computability. It consists in assigning new names to processes in such a way that no two processes obtain the same new name and the new name space be as small as possible. The paper visits the problem by presenting three solutions. This paper, that has a strong survey/short tutorial flavor, can consequently be considered as an introduction to both there naming problem and progress conditions for synchronization in presence of process crashes in the context of multiprocessor systems.

This brief announcement introduces the family of generalized symmetry breaking (GSB) tasks, that includes election, renaming and many other symmetry breaking tasks. Differently from agreement tasks, a GSB task is "inputless", in the sense that processes do not propose values; the task specifies only the symmetry breaking requirement, independently of the system's initial state (where processes differ only on their identifiers). Among various results characterizing the family of GSB tasks, it is shown that (non adaptive) perfect renaming is universal for all GSB tasks.

Failure patterns in modern parallel and distributed system are not necessarily uniform. The notion of an adversary scheduler is a natural way to extend the classical wait-free and t-faulty models of computation. A well-established way to characterize an adversary is by its set of cores, where a core is any minimal set of processes that cannot all fail in any execution. We show that the protocol complex associated with an adversary is (c-2)-connected, where c is the size of the adversary's smallest core. This implies, among other results, that such an adversary can solve c-set agreement, but not (c-1)-set agreement. The proofs are combinatorial, relying on a novel application of the Nerve Theorem of modern combinatorial topology.

In the k-set agreement task, n processes propose values, and have to decide on at most k of these values. In particular, consensus is 1-set agreement. In PODC 2008 Zieliński showed that the anti-Ω failure detector is necessary and sufficient to solve (n − 1)-set agreement in an asynchronous read/write shared memory system where at most n − 1 processes can fail by crashing.

In the renaming task n+1 processes start with unique input names from a large space and must choose unique output names taken from a smaller name space, namely 0,1,...,K. To rule out trivial solutions, a protocol must be anonymous: the value chosen by a process can depend on its input name and on the execution, but not on the specific process id. Attiya et al. showed in 1990 that renaming has a wait-free solution when K<=2n. Several proofs of a lower bound stating that no such protocol exists when K<2n have been published. In this paper we prove that, for certain values of n, this lower bound is incorrect, exhibiting a wait-free renaming protocol for K=2n-1. For the other values of n, we present the first completely combinatorial lower bound proof stating that no such protocol exists when K<2n. More precisely, our main theorem states that there exists a wait-free renaming protocol for K<2n if and only if the set of integers (n+1 choose i+1) | 0 <= i <= floor((n-1)/2)} are relatively prime. Thus, such protocol exists for six processes, and not for less. The proof of the theorem uses combinatorial topology techniques, both for the lower bound and to derive the renaming protocol.

We consider a failure-free, asynchronous message passing network with n links, where the processors are arranged on a ring or a chain. The processors are identically programmed but have distinct identities, taken from {0, 1,… , M − 1}. We investigate the communication costs of three well studied tasks: Consensus, Leader, and MaxF (finding the maximum identity). We show that in chain and ring topologies, the message complexities of all three tasks are the same. Hence, we study a finer measure of complexity: the number of transmitted bits required to solve a task T , denoted BitC ( T ). We prove several new lower bounds (and some simple upper bounds) that imply the following results: For the two processors case, BitC (Consensus) = 2 and BitC (Leader) = BitC (MaxF) = 2log 2 M ± O (1), where the gap between the lower and upper bounds is almost always 1. For a chain, BitC (Consensus) = Θ( n ), BitC (Leader) = Θ( n + log M ), and BitC (MaxF) = Θ( n log M ). For the ring topology, we prove the lower bound of Ω( n log M ) for Leader, and (hence) MaxF. We consider also a chain where the intermediate processors have no identities. We prove that BitC (Leader) = Θ( n log M ), which is equal to n times the bit complexity of the problem for two processors. For the specific case when the chain length is even, we prove that BitC (Leader) = Θ( n ), for both above settings. In addition, we show that for any algorithm solving MaxF, there exists an input, for which every execution has the bit complexity Ω( n log M ) (this is not the case for Leader). In our proofs, we use both methods of distributed computing and of communication complexity theory, establishing new links between the two areas.

To cope with the impossibility of solving agreement problems in asynchronous systems made up of n processes and prone to t process crashes, system designers tailor their algorithms to run fast in “normal” circumstances. Two orthogonal notions of “normality” have been studied in the past through failure detectors that give processes information about process crashes, and through conditions that restrict the inputs to an agreement problem. This paper investigates how the two approaches can benefit from each other to solve the k-set agreement problem, where processes must agree on at most k of their input values (when $k=1$ we have the famous consensus problem). It proposes novel failure detectors for solving k-set agreement and a protocol that combines them with conditions, establishing a new bridge among asynchronous, synchronous, and partially synchronous systems with respect to agreement problems. The paper also proves a lower bound when solving the k-set agreement problem with a condition.

No abstract available.

Multivalued consensus functions defined from a vector of inputs over the set V of possible input values (and possibly from the previous input and output values) to a single output are investigated. The consensus functions are designed to tolerate t faulty inputs. Two classes of multivalued consensus functions are defined, the exact value and the range value, which require the output to be one of the nonfaulty inputs or in the range of the nonfaulty inputs, respectively. The instability of consensus functions is examined, counting the maximal number of output changes along a geodesic path of input changes, a path in which each input is changed at most once. Lower and upper bounds for the instability of multivalued consensus functions as a function of n, the number of sensors, t, and $|V|$ are presented. A new technique for obtaining such lower bounds, using edgewise simplex subdivision, is presented.

The condition-based approach identifies sets of input vectors, called conditions, for which it is possible to design an asynchronous protocol solving a distributed problem despite process crashes. This paper establishes a direct correlation between distributed agreement problems and error-correcting codes. In particular, crash failures in distributed agreement problems correspond to erasure failures in error-correcting codes and Byzantine and value domain faults correspond to corruption errors. This correlation is exemplified by concentrating on two well-known agreement problems, namely, consensus and interactive consistency, in the context of the condition-based approach. Specifically, the paper presents the following results: first, it shows that the conditions that allow interactive consistency to be solved despite fccrashes and fcvalue domain faults correspond exactly to the set of error-correcting codes capable of recovering from fcerasures and fccorruptions. Second, the paper proves that consensus can be solved despite fccrash failures if the condition corresponds to a code whose Hamming distance is fc+ 1 and Byzantine consensus can be solved despite fbByzantine faults if the Hamming distance of the code is 2 fb+ 1. Finally, the paper uses the above relations to establish several results in distributed agreement that are derived from known results in error-correcting codes and vice versa.

A failure detector is a device that provides the processes with information on failures. The accuracy property of a failure detector defines the type of mistakes it is not allowed to make. The limited scope of the accuracy property restricts it to only a part of the system. /spl diams/S/sub k/ is a class of unreliable failure detectors with a limited scope accuracy. Eventually each process that crashes is suspected by every correct process, and there is a time after which some correct process is never suspected by only k processes. An eventual leader facility (usually denoted /spl Omega/)is a device that eventually provides all the processes with the identity of one of them that is correct. Such a facility is used as a basic service in a lot of fault-tolerant distributed protocols (e.g., asynchronous consensus protocols). This paper proposes a protocol that builds an eventual leader service from any unreliable failure detector of the class /spl diams/S/sub t+1/ where t is the maximum number of processes that can crash during a run. The fact that /spl diams/S/sub t+1/ is easier to build than /spl diams/S or /spl Omega/ and the design simplicity of the proposed protocol makes it attractive.

Solving agreement problems (such as consensus and k-set agreement) in asynchronous distributed systems prone to process failures has been shown to be impossible. To circumvent this impossibility, distributed oracles (also called unreliable failure detectors) have been introduced. A failure detector provides information on failures, and a failure detector class is defined by a set of abstract properties that encapsulate (and hide) synchrony assumptions. Some failure detector classes have been shown to be the weakest to solve some agreement problems (e.g., Ω is the weakest class of failure detectors that allow solving the consensus problem in asynchronous systems where a majority of processes do not crash).This paper considers several failure detector classes and focuses on their additivity or their irreducibility. It mainly investigates two families of failure detector classes (denoted ◊ Sx and ◊ φy, 0≤ x, y ≤ n), shows that they can be "added" to provide a failure detector of the class Ωz (a generalization of Ω). It also characterizes the power of such an "addition", namely, ◊ Sx + ◊ φy ➝ Ωz ⇔ x+y+z>t+1, where t is the maximum number of processes that can crash in a run. As an example, the paper shows that, while ◊ St allows solving 2-set agreement (and not consensus) and ◊ φ1 allows solving t-set agreement (but not (t-1)-set agreement), their "addition" allows solving consensus. More generally, the paper studies the failure detector classes ◊ Sx, ◊ φy and Ωz, and shows which reductions among these classes are possible and which are not. The paper presents also an Ωk-based k-set agreement protocol. In that sense, it can be seen as a step toward the characterization of the weakest failure detector that allows solving the k-set agreement problem.

Given a set V of active components in charge of a distributed execution, a storage scheme is a sequence B0, B1,..., Bb-1of subsets of V, where successive global states are recorded. The subsets, also called blocks, have the same size and are scheduled according to some fixed and cyclic calendar of b steps. During the ith step, block Biis selected. Each component takes a copy of its local state and sends it to one of the components in Bi, in such a way that each component stores (approximately) the same number of local states. Afterward, if a component of Bicrashes, all of its stored data is lost and the computation cannot continue. If there exists a block with no failed components in it, then a recent global state can be retrieved and the computation does not need to start over from the very beginning. The goal is to design storage schemes that tolerate as many crashes as possible, while trying to have each component participating in as few blocks as possible and, at the same time, working with large blocks (so that a component in a block stores a small number of local states). In this paper, several such schemes are described and compared in terms of these measures

We prove two theorems saying that no distributed system in which processes coordinate using reliable registers and f-resilient services can solve the consensus problem in the presence of f + 1 undetectable process stopping failures. (A service is f-resilient if it is guaranteed to operate as long as no more than f of the processes connected to it fail.) Our first theorem assumes that the given services are atomic objects, and allows any connection pattern between processes and services. In contrast, we show that it is possible to boost the resilience of systems solving problems easier than consensus: the k-set consensus problem is solvable for 2k - 1 failures using 1-resilient consensus services. The first theorem and its proof generalize to the larger class of failure-oblivious services. Our second theorem allows the system to contain failure-aware services, such as failure detectors, in addition to failure-oblivious services; however, it requires that each failure-aware service be connected to all processes. Thus, f + 1 process failures overall can disable all the failure-aware services. In contrast, it is possible to boost the resilience of a system solving consensus if arbitrary patterns of connectivity are allowed between processes and failure-aware services: consensus is solvable for any number of failures using only 1-resilient 2-process perfect failure detectors

An approach to cope with the impossibility of solving agreement problems in asynchronous systems made up of n processes and prone to t process crashes is to use failure detectors. An orthogonal approach that has been used is to consider conditions that restrict the possible inputs to such a problem. This paper considers a system with both failure detectors and conditions. The aim is to identify the failure detector class that abstracts away the synchrony needed to solve k-set agreement for a given condition.Three main contributions are presented. The first is a new class of failure detectors denoted Φty, 0≤ y≤ t. The processes can invoke a primitive queryy(S) with a set of process ids S. Roughly speaking, queryy(S) returns true only when all processes in S have crashed, provided t-y

No abstract available.

This article introduces and explores the condition-based approach to solve the consensus problem in asynchronous systems. The approach studies conditions that identify sets of input vectors for which it is possible to solve consensus despite the occurrence of up to f process crashes. The first main result defines acceptable conditions and shows that these are exactly the conditions for which a consensus protocol exists. Two examples of realistic acceptable conditions are presented, and proved to be maximal, in the sense that they cannot be extended and remain acceptable. The second main result is a generic consensus shared-memory protocol for any acceptable condition. The protocol always guarantees agreement and validity, and terminates (at least) when the inputs satisfy the condition with which the protocol has been instantiated, or when there are no crashes. An efficient version of the protocol is then designed for the message passing model that works when f < n /2, and it is shown that no such protocol exists when f ≥ n /2. It is also shown how the protocol's safety can be traded for its liveness.

Investigates a modular and versatile approach to solve the consensus problem in asynchronous distributed systems in which up to f processes may crash (f<n/2), but equipped with appropriate oracles. It presents a generic protocol that proceeds by consecutive asynchronous rounds. Each round follows a "two-phase" pattern. The modularity and the versatility of the protocol appear at each phase of a round. The first phase is a selection phase that allows to use any combination merging random oracle, leader oracle and condition. Its aim is to ensure termination by allowing the processes to start the second phase with the same value. The aim of the second phase is to ensure that the agreement property cannot be violated. Its cost depends on the value of f: two communication steps when f<n/2, that reduce to a single communication step when f

No abstract available.

This paper presents a self-contained study of wait-free solvable tasks. A new necessary condition for wait-free solvability, based on a restricted set of executions, is proved. This set of executions induces a very simple-to-understand structure, which is used to prove tight bounds for k-set consensus and renaming. The framework is based on topology, but uses only elementary combinatorics, and, in contrast to previous works, does not rely on algebraic or geometric arguments.

This paper introduces a simple notion of layering as a tool for analyzing well-behaved runs of a given model of distributed computation. Using layering, a model-independent analysis of the consensus problem is performed and then applied to proving lower bounds and impossibility results for consensus in a number of familiar and less familiar models. The proofs are simpler and more direct than existing ones, and they expose a unified structure to the difficulty of reaching consensus. In particular, the proofs for the classical synchronous and asynchronous models now follow the same outline. A new notion of connectivity among states in runs of a consensus protocol, called potence connectivity, is introduced. This notion is more general than previous notions of connectivity used for this purpose and plays a keyrole in the uniform analysis of consensus.

In a previous paper we introduced the condition-based approach, consisting of identifying sets of input vectors, called conditions, for which there exists an asynchronous protocol solving consensus despite the occurrence of up to f process crashes, and characterized this set of conditions, @@@@wkf. Here, we investigate @@@@wkf from the complexity perspective, and show that this class consists of a hierarchy of classes of conditions, @@@@[d]f, where d, 0 ⪇ d ⪇ f, is the degree of the condition, each one strictly contained in the previous one. The value f - d represents the “difficulty” of the class @@@@[d]f: we present a generic condition-based protocol that can be instantiated with any C ∈ @@@@[d]f, and solve consensus with (2n + 1) [log2([(f - d)/2] + 1)] shared memory read/write operations per process. For each d we present two natural conditions, C1[d]f and C2[d]f, that might be useful in practice, and we use them to show that the class containments stated above are strict. Various properties of the hierarchy are also derived. Mainly, it is shown that a class can be characterized in two equivalent but complementary ways: one is convenient for designing protocols while the other is for analyzing the class properties.

This paper introduces and explores a new condition based approach to solve the consensus problem in asynchronous systems. The approach consists of identifying sets of input vectors, called conditions, for which it is possible to design a protocol solving consensus despite the occurrence of up to f process crashes.

This paper introduces the notion stability for a long-lived consensus system. This notion reflects how sensitive to changes the decisions of the system are, from one invocation of the consensus algorithm to the next, with respect to input changes. Stable long-lived consensus systems are proposed, and tight lower bounds on the achievable stability are proved, for several different scenarios. The scenarios include systems that keep memory from one invocation of consensus to the next versus memoryless systems; systems that take their decisions based on the number of different inputs but not on the source identities of those inputs versus non-symmetric systems. These results intend to study essential aspects of stability, and hence are independent of specific models of distributed computing. Applications to particular asynchronous and synchronous system are described.

Ye m Dinitz Shlomo Moran Sergio Rajsbaum Abstract We consider a failure-free, asynchronous message passing network, with n processors arranged on a ring or a chain. The processes are identically programmed but have distinct identities, taken from f1; : : : ; Mg. We investigate the communication costs of three well studied tasks: Consensus, Leader, and MaxF ( nding the maximum identity, a restricted version of Leader). We show that in both chain and ring topologies, somewhat surprisingly, the message complexities of all three tasks are the same. Hence, we suggest as a ner measure of complexity the number of bits transmitted, BitC(). We show that in chains, w.r.t. this measure, Consensus is easier than Leader, which is easier than MaxF. More speci cally, we prove several new lower bounds (and some simple upper bounds) that imply the following results: For the two processors case, BitC(Consensus) = 2 and BitC(Leader) = BitC(MaxF) = 2 log 2 M O(1). For a chain, BitC(Consensus) = (n), and BitC(MaxF) = (n log M ). When the length is even BitC(Leader) = (n), while if the length is odd BitC(Leader) = (n + log M ).

We take a significant step toward unifying the synchronous, semi-synchronous, and asynchronous message-passing models of distributed computation.The key idea is the concept of a pseudosphere, a new combinatorial structure in which each process from a set of processes is independently assigned a value from a set of values.Pseudospheres have a number of nice combinatorial properties, but their principal interest lies in the observation that the behavior of protocols in the three models can be characterized as simple unions of pseudospheres, where the exact structure of these unions is determined by the timing properties of the model.We use this pseudosphere construction to derive new and remarkably succinct proofs of bounds on consensus and k-set agreement in the asynchronous and synchronous models, as well as the first lower bound on wait-free k-set agreement in the semi-synchronous model.

We introduce a simple notion of layering that provides a tool for defining submodels of a given model of distributed computation.We describe two layerings, the synchronic and the permutation layering, and show that they induce appropriate submodels of several asynchronous models of computation.The synchronic layering applies to the synchronous model too.We perform a model-independent analysis of the consensus problem in terms of abstract connectivity properties of layering functions.By defining particular layerings in specific models, we derive several popular (and some new) lower bounds and impossibility results for consensus in various classical models.These results are often stronger in the sense that they apply to the subrnodel induced by the layering.The proofs obtained in this way are also simpler and more direct than existing ones.Moreover, the analysis is done in a uniform fashion and demonstrates the fundamental common structure of the consensus problem in the presence of failures.The analysis is then extended to general decision problems (l-resilient in the asynchronous models, t-rounds in the t-resilient synchronous model), providing a characterization of solvability of decision problems in the style of [8] which, for some of the models, is given for the first time.1 introduction For almost two decades now, the consensus problem has played a central role in the study of fault-tolerant distributed computing, e.g.123, 13, 12, 10, 14, 20, 16, 8, 91.It has clearly received the greatest amount of attention in the theoretical literature on distributed computing, and has been studied in a large variety of models and under many types of failure assumptions.Work on different variants often in-*This work has been supported by a Helen and Milton A. Kimmelman career development chair.

A task is a distributed coordination problem in which each process starts with a private input value taken from a tlnite set, communicates with the other processes by applying operations to shared objects, and eventually halts with a private output value, also taken from a finite set.A protocol is a distributed program that solves a task.A protocol is t-resikent if it tolerates failures by t or fewer processes.A task is solvable in a given model of computation if it has a t-resilientprotocol in that model.A set of tasks is decidable in a given model of computation if there exists an effective procedure for deciding whether any task in that set has a t-resilient protocol.This paper gives the first necessary and sufficient conditions for task decidability in a range of different models and resilience levels.We prove undecidability by exploiting classical decidabilit y results from algebraic topology, and we prove decidability by explicit construction.

No abstract available.

No abstract available.

The problem of achieving optimal clock synchronization in a communication network with arbitrary topology and perfect clocks (that do not drift) is studied. Clock synchronization algorithms are presented for a large family of delay assumptions. Our algorithms are modular and consist of three major components. The first component holds for any type of delay assumptions; the second component holds for a large, natural family of local delay assumptions; the third component must be tailored for each specific delay assumption. Optimal clock synchronization algorithms are derived for several types of delay assumptions by appropriately tuning the third component. The delay assumptions include lower and upper delay bounds, no bounds at all, and bounds on the difference of the delay in opposite directions. In addition, our model handles systems where some processors are connected by broadcast networks in which every message arrives at all the processors at approximately the same time. A composition theorem allows combinations of different assumptions for different links or even for the same link; such mixtures are common in practice. Our results achieve the best possible precision in each execution. This notion of optimality is stronger than the more common notion of worst-case optimality. The new notion of optimality applies to systems where the worst-case behavior of any clock synchronization algorithm is inherently unbounded.

Topological methods have yielded a variety of lower bounds and impossibility results for distributed computing.In this paper, we introduce a new tool for proving impossibility results, based on a core theorem of algebraic topology, the acyclic carrier theorem, which unifies, generalizes, and extends earlier results.q

Article Free Access Share on Set consensus using arbitrary objects (preliminary version) Authors: Maurice Herlihy Digital Equipment Corporation, Cambridge Research Laboratory, One Kendall Square, Cambridge, MA Digital Equipment Corporation, Cambridge Research Laboratory, One Kendall Square, Cambridge, MAView Profile , Sergio Rajsbaum MIT Laboratory for Computer Science, 545 Technology Square, Cambridge, MA and Instituto de Matemáticas, U. N. A.M., México MIT Laboratory for Computer Science, 545 Technology Square, Cambridge, MA and Instituto de Matemáticas, U. N. A.M., MéxicoView Profile Authors Info & Claims PODC '94: Proceedings of the thirteenth annual ACM symposium on Principles of distributed computingAugust 1994 Pages 324–333https://doi.org/10.1145/197917.198119Published:14 August 1994Publication History 37citation313DownloadsMetricsTotal Citations37Total Downloads313Last 12 Months18Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We consider the problem of clock synchronization with uncertain message delays and bounded clock drifts. To analyze this classical problem we introduce a characterization theorem for the tightest achievable estimate of the readings of a remote clock in any given execution of the system. Using this theorem, we obtain the first optimal on-line distributed algorithms for clock synchronization. The algorithms are optimal for all executions, rather than only worst cases. The general algorithm for systems with drifting clocks has high space overhead, which is unavoidable, as we show. For systems with drift-free clocks (i.e., clocks that run at the rate of real time), we present a remarkably simple and efficient algorithm. The discussion focuses on the variant where one of the clocks shows real time, but we present results also for the case where real time...

A synchronizer is a compiler that transforms a program designed to run in a synchronous network into a program that runs in an asynchronous network. The behavior of a simple synchronizer, which also represents a basic mechanism for distributed computing and for the analysis of marked graphs, was studied by S. Even and S. Rajsbaum (1990) under the assumption that message transmission delays and processing times are constant. We study the behavior of the simple synchronizer when processing times and transmission delays are random. The main performance measure is the rate of a network, i.e., the average number of computational steps executed by a processor in the network per unit time. We analyze the effect of the topology and the probability distributions of the random variables on the behavior of the network. For random variables with exponential distribution, we provide tight (i.e., attainable) bounds and study the effect of a bottleneck processor on the rate.>

The problem of achieving optimal clock synchronization in a communication network with arbitrary topology and perfect clocks (that do not drift) is studied. Clock synchronization algorithms are presented for a large family of delay assumptions. Our algorithms are modular and consist of three major components. The first component holds for any type of delay assumptions; the second component holds for a large, natural family of local delay assumptions; the third component has to be tailored for each specific delay assumption. Optimal clock synchronization algorithms are derived for several types of delay assumptions by appropriately tuning the third component. The delay assumptions include lower and upper delay bounds, no bounds at all, and bounds on the difference of the delay in opposite directions. In addition, our model handles systems where some processors are connected by broadcast networks in which every message arrives to all processors at approximately the same time. A composition theorem allows combinations of different assumptions for different lins or even for the same link; such mixtures are common in practice. Our results acheive the best possible precision in each execution. This notion of optimality is stronger than the more common notion of worst case optimality. The new notion of optimality applied to systems where the worst case behavior of any clock synchronization algorithm is inherently unbounded.

In a previous paper we analyzed the performance of networks with negligible transmission delay, who~ operation is controlled by a simple synchronizer.It was shown that full speed is achieved, for any wake-up pattern, by letting the netwonk run free, without the use of a "firing squad" mechanism or a scheduler.In this paper we investigate the effect of fixed delays in the communication channels on the performance of a netwo~ in which there is a global clock, but there is no global start-up signal.We show that here too, maximum rate of computation is always reached, just by using the synchronizer and letting the network run free.To a certain extent, the wake-up pattern may influence the length of the transitory stage and the periodicity of the steady state, but not the ultimate rate.