On the computability power and the robustness of set agreement-oriented failure detector classes

Solving agreement problems deterministically, such as consensus and k-set agreement, in asynchronous distributed systems prone to an unbounded number of process failures has been shown to be impossible. To circumvent this impossibility, unreliable failure detectors for the crash failure model have been widely studied. These are oracles that provide information on failures. The exact nature of such information is defined by a set of abstract properties that a particular class of failure detectors satisfy. The weakest class of such failure detectors that allow to solve consensus is Ω. This paper considers failure detector classes from the literature that solve k-set agreement in the crash failure model, and studies their relative power. It shows that the family of failure detector classes (1 ≤ x ≤ n), and (0 ≤ y ≤ n), can be “added” to provide a failure detector of the class Ω ^z (1 ≤ z ≤ n, a generalization of Ω). It also characterizes the power of such an “addition”, namely, , can construct Ω ^z iff y + z > t, and can construct Ω ^z iff x + 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 allows solving 2-set agreement (but not consensus) and allows solving t-set agreement (but not (t − 1)-set agreement), a system with failure detectors of both classes can solve consensus for any value of t. More generally, the paper studies the failure detector classes , and Ω ^z , and shows which reductions among these classes are possible and which are not. The paper also presents a message-passing Ω ^k -based k-set agreement protocol and shows that Ω ^k is not enough to solve (k − 1)-set agreement. In that sense, it can be seen as a step toward the characterization of the weakest failure detector class that allows solving the k-set agreement problem. An extended abstract of this paper has appeared in the proceedings of PODC 2006 [20]. This work has been supported partially by a grant from LAFMI (Franco-Mexican Lab in Computer Science), the European Network of Excellence ReSIST and PAPIIT-UNAM.     

An Equivariance Theorem with Applications to Renaming

In the renaming problem, each process in a distributed system is issued a unique name from a large namespace, and the processes must coordinate with one another to choose unique names from a much smaller name space. We show that lower bounds on the solvability of renaming can be formulated as a purely topological question about the existence of an equivariant chain map from a “topological disk” to a “topological annulus”. Proving the non-existence of such a map implies the non-existence of a distributed renaming algorithm in several related models of computation.     

An Overview of Synchronous Message-Passing and Topology

A slowly-growing number of computer scientists have found that ideas from topology can be used to analyze and understand problems in distributed computing. In this paper, we review one approach we have used in the past to write a succinct proof of the lower bound for the number of rounds needed to solve the k-set agreement problem in a synchronous, message-passing model of computation. The central idea in this approach is a simple combinatorial structure we call a pseudosphere, 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 global states that arise in the synchronous, message-passing model can be viewed as simple unions of pseudospheres, and the fact that topological properties of unions of pseudospheres are so easy to prove. We choose this work to review because it is a simple example of how we model distributed systems with topology, and because it is the basis of on-going work to simplify the proof of this result.     

Condition-based consensus solvability: a hierarchy of conditions and efficient protocols

The condition-based approach for consensus solvability consists 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. This paper investigates , the largest set of conditions which allow us to solve the consensus problem in an asynchronous shared memory system.The first part of the paper shows that is made up of a hierarchy of classes of conditions, where d is a parameter (called degree of the condition), starting with and ending with d = 0, where . We prove that each one is strictly contained in the previous one: . Various properties of the hierarchy are also derived. 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. The paper also defines a linear family of conditions that can be used to derive many specific conditions. In particular, for each d, two natural conditions are presented.The second part of the paper is devoted to the design of efficient condition-based protocols. A generic condition-based protocol is presented. This protocol can be instantiated with any condition C, , and requires at most shared memory read/write operations per process in the synchronization part of the protocol. Thus, the value (f-d) represents the difficulty of the class . An improvement of the protocol for the conditions in is also presented.Received: 15 November 2001, Accepted: 15 April 2003, Published online: 6 February 2004Parts of it have previously appeared in [23] and [25].     

Unison,canon, and sluggish clocks in networks controlled by a synchronizer

The effect of using a simple synchronizer on the performance of a directed, strongly connected, distributed network, is analysed. In this paper we assume that the time of message transmission is positive but negligible. It is shown that the synchronizer is sufficient to assure that a full rate of computation is achieved in networks with a global clock, in spite of the absence of a global start-up signal. In fact,unison is reached within linear time. A similar phenomenon occurs if there is no global clock, but all local clocks have the same rate. In case the local clocks do not have the same rate, it is shown that the computational rate is not slower than anysluggish clock; i.e., a clock such that between any two of its ticks, every local clock ticks at least once.The first author was supported by the Fund for the Promotion of Research at the Technion. The work of the second author was done while he was in the Computer Science Department of the Technion; he is presently visiting the Laboratory for Computer Science, MIT.     

The topology of distributed adversaries

Roughly speaking, a simplicial complex is shellable if it can be constructed by gluing a sequence of n-simplexes to one another along $(n-1)$ ( n ? 1 ) -faces only. Shellable complexes have been widely studied because they have nice combinatorial properties. It turns out that several standard models of concurrent computation can be constructed from shellable complexes. We consider adversarial schedulers in the synchronous, asynchronous, and semi-synchronous message-passing models, as well as asynchronous shared memory. We show how to exploit their common shellability structure to derive new and remarkably succinct tight (or nearly so) lower bounds on connectivity of protocol complexes and hence on solutions to the $k$ k -set agreement task in these models. Earlier versions of material in this article appeared in the 2010 ACM Symposium on Principles of Distributed Computing (Herlihy and Rajsbaum 2010), and the International Conference on Distributed Computing (Herlihy and Rajsbaum 2010, doi:10.1145/1835698.1835724).     

New combinatorial topology bounds for renaming: the lower bound

In the renaming task n + 1 processes start with unique input names taken 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. 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. We presented in the ACM PODC 2008 conference the following two results. First, we presented the first completely combinatorial lower bound proof stating that no such a protocol exists when K < 2n. This bound holds for infinitely many values of n. Second, for the other values of n, we proved that the lower bound for K < 2n is incorrect, exhibiting a wait-free renaming protocol for K = 2n?1. More precisely, we presented a theorem stating 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 \leq i \leq \lfloor \frac{n-1}{2} \rfloor \}}$ are relatively prime. This paper is the first part of the full version of the results presented in the ACM PODC 2008 conference. It includes only the lower bound. Namely, we show here that no protocol for renaming exists when K <  2n, if n is such that ${\{ {n+1 \choose i+1} | 0 \leq i \leq \lfloor \frac{n-1}{2}\rfloor \}}$ are not relatively prime. We prove this result using the known equivalence of K-renaming for K = 2n?1 and the weak symmetry breaking task. In this 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 0 and at least one process decides 1. The full version of the upper bound appears in a companion paper [10].     

The use of a synchronizer yields the maximum computation rate in distributed networks

We study the performance of networks whose operation is controlled by a simple synchronizer. In a previous paper we analyzed the performance of networks with negligible transmission delay. It was shown that full speed is achieved, for any wake-up pattern, by letting the network 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 network in which there is a global clock, but there is no global start-up signal. We show that here, too, the 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. In any case, the length of the transitory stage is bounded polynomially, and the bound is tight, while the period may be of exponential length. An extended abstract of this paper appeared in STOC ’90. Part of this work was done while the authors visited the Computer Science Program, University of Texas at Dallas, Richardson, TX, USA. The first author is now visiting Bell Laboratories, Lucent Technologies, Murray Hill, NJ, USA, and was supported by the Fund for the Promotion of Research at the Technion. The second author’s current address is Instituto de Matematicas — U.N.A.M., Ciudad Universitaria, D.F. 04510, Mexico. rajsbaum@servidor.unam.mx