15901717
From failure detectors with limited scope accuracy to system-wide leadership
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.
14362073
The Alpha of Indulgent Consensus
This paper presents a simple framework unifying a family of consensus algorithms that can tolerate process crash failures and asynchronous periods of the network, also called indulgent consensus algorithms. Key to the framework is a new abstraction we introduce here, called Alpha, and which precisely captures consensus safety. Implementations of Alpha in shared memory, storage area network, message passing and active disk systems are presented, leading to directly derived consensus algorithms suited to these communication media. The paper also considers the case where the number of processes is unknown and can be arbitrarily large.
39476661
The Committee Decision Problem
We introduce the (b,n)-Committee Decision Problem (CD) – a generalization of the consensus problem. While set agreement generalizes consensus in terms of the number of decisions allowed, the CD problem generalizes consensus in the sense of considering many instances of consensus and requiring a processor to decide in at least one instance. In more detail, in the CD problem each one of a set of n processes has a (possibly distinct) value to propose to each one of a set of b consensus problems, which we call committees. Yet a process has to decide a value for at least one of these committees, such that all processes deciding for the same committee decide the same value. We study the CD problem in the context of a wait-free distributed system and analyze it using a combination of distributed algorithmic and topological techniques, introducing a novel reduction technique. 
 
We use the reduction technique to obtain the following results. We show that the (2,3)-CD problem is equivalent to the musical benches problem introduced by Gafni and Rajsbaum in [10], and both are equivalent to (2,3)-set agreement, closing an open question left there. Thus, all three problems are wait-free unsolvable in a read/write shared memory system, and they are all solvable if the system is enriched with objects capable of solving (2,3)-set agreement. While the previous proof of the impossibility of musical benches was based on the Borsuk-Ulam (BU) Theorem, it now relies on Sperner's Lemma, opening intriguing questions about the relation between BU and distributed computing tasks.
20003649
Synchronous condition-based consensus
AbstractThe condition-based approach studies restrictions on the inputs to a distributed problem, called conditions, that facilitate its solution. Previous work considered mostly the asynchronous model of computation. This paper studies conditions for consensus in a synchronous system where processes can fail by crashing. It describes a full classification of conditions for consensus, establishing a continuum between the asynchronous and synchronous models, with the following hierarchy $${\cal S}_t^{[-t]}\subset\cdots\subset {\cal S}_t^{[0]}\subset\cdots\subset {\cal S}_t^{[t]}$$ where $${\cal S}_t^{[t]}$$ includes all conditions (and in particular the trivial one made up of all possible input vectors). For a condition $$C \in{\cal S}_t^{[d]}$, $-t \leq d \leq t$$, we have:
For values of $$d \leq 0$$ consensus is solvable in an asynchronous system with t failures, and we obtain the known hierarchy of conditions that allows solving asynchronous consensus with more and more efficient protocols as we go from d = 0 to d = −t.For values of $$d \leq 0$$ consensus is solvable in an asynchronous system with t failures, and we obtain the known hierarchy of conditions that allows solving asynchronous consensus with more and more efficient protocols as we go from d = 0 to d = −t.For values of d<0 consensus is known not solvable in an asynchronous system with t failures, but we obtain a hierarchy of conditions that allows solving synchronous consensus with protocols that can take more and more rounds, as we go from d = 0 to d = t.d = 0 is the borderline case where consensus can be solved in an asynchronous system with t failures, and can be solved optimally in a synchronous system.
 After having established the complete hierarchy, the paper concentrates on the two last items: $$0\leq d\leq t$$. The main result is that the necessary and sufficient number of rounds needed to solve uniform consensus for a condition $$C \in {\cal S}_t^{[d]}$$ (such that $$C\notin {\cal S}_t^{[d-1]}$$) is d +1.In more detail, the paper presents a generic synchronous early-deciding uniform consensus protocol that enjoys the following properties. Let f be the number of actual crashes, I the input vector and $$C \in {\cal S}_t^{[d]}$$ the condition the protocol is instantiated with. The protocol terminates in two rounds when $$I\in C$$ and $$f\leq t-d$$, and in at most d +1 rounds when $$I\in C$$ and $$f>t-d$$. (It also terminates in one round when $$I\in C$$ and $$d=f=0$$.) Moreover, whether I belongs or not to C, no process requires more than min$$(t+1,f+2)$$ rounds to decide. The paper then proves a corresponding lower bound stating that at least d +1 rounds are necessary to get a decision in the worst case when $$I\in C$$ (for $$C \in {\cal S}_t^{[d]}$$ and $$C \notin {\cal S}_t^{[d-1]}$$).
46587799
Strongly Terminating Early-Stopping k-Set Agreement in Synchronous Systems with General Omission Failures
The k-set agreement problem is a generalization of the consensus problem: considering a system made up of n processes where each process proposes a value, each non-faulty process has to decide a value such that a decided value is a proposed value, and no more than k different values are decided. It has recently be shown that, in the crash failure model, min$(\lfloor \frac{f}{k} \rfloor+2,\lfloor \frac{t}{k} \rfloor +1)$ is a lower bound on the number of rounds for the non-faulty processes to decide (where t is an upper bound on the number of process crashes, and f, 0 ≤f ≤t, the actual number of crashes) 
 
This paper considers the k-set agreement problem in synchronous systems where up to t < n /2 processes can experience general omission failures (i.e., a process can crash or omit sending or receiving messages). It first introduces a new property, called strong termination. This property is on the processes that decide. It is satisfied if, not only every non-faulty process, but any process that neither crashes nor commits receive omission failures decides. The paper then presents a k-set agreement protocol that enjoys the following features. First, it is strongly terminating (to our knowledge, it is the first agreement protocol to satisfy this property, whatever the failure model considered). Then, it is early deciding and stopping in the sense that a process that either is non-faulty or commits only send omission failures decides and halts by round min$(\lfloor \frac{f}{k} \rfloor+2,\lfloor \frac{t}{k} \rfloor +1)$. To our knowledge, this is the first early deciding k-set agreement protocol for the general omission failure model. Moreover, the protocol provides also the following additional early stopping property: a process that commits receive omission failures (and does not crash) executes at most min$(\lceil \frac{f}{k} \rceil +2,\lfloor \frac{t}{k} \rfloor +1)$ rounds. It is worth noticing that the protocol allows each property (strong termination vs early deciding/stopping vs early stopping) not to be obtained at the detriment of the two others 
 
The combination of the fact that min$(\lfloor \frac{f}{k} \rfloor+2,\lfloor \frac{t}{k} \rfloor +1)$ is lower bound on the number of rounds in the crash failure model, and the very existence of the proposed protocol has two very interesting consequences. First, it shows that, although general omission failure model is more severe than the crash failure model, both models have the same lower bound for the non-faulty processes to decide. Second, it shows that, in the general omission failure model, that bound applies also the processes that commit only send omission failures
3212723
In Search of the Holy Grail: Looking for the Weakest Failure Detector for Wait-Free Set Agreement
Asynchronous failure detector-based set agreement algorithms proposed so far assume that all the processes participate in the algorithm. This means that (at least) the processes that do not crash propose a value and consequently execute the algorithm. It follows that these algorithms can block forever (preventing the correct processes from terminating) when there are correct processes that do not participate in the algorithm. This paper investigates the wait-free set agreement problem, i.e., the case where the correct participating processes have to decide a value whatever the behavior of the other processes (i.e., the processes that crash and the processes that are correct but do not participate in the algorithm). The paper presents a wait-free set agreement algorithm. This algorithm is based on a leader failure detector class that takes into account the notion of participating processes. Interestingly, this algorithm enjoys a first class property, namely, design simplicity.
10131958
An optimal atomic broadcast protocol and an implementation framework
Atomic broadcast (where all processes deliver broadcast messages in the same order) is a very useful group communication primitive for building fault-tolerant distributed systems. This paper presents an atomic broadcast protocol that can be claimed to be optimal in terms of failure detection, resilience, and latency. The protocol requires only the weakest of the useful failure detectors for liveness, and permits up to (n-1)/2 processes to crash in a system of n processes; at most two communication steps and n broadcasts are needed in a run during which process crashes and failure-suspicions do not occur. We also introduce the notion of notifying broadcast which can reduce the message overhead further in 'nice' runs in which all processes are operational and communication delays do not exceed the bound assumed. If nice runs persist, the average message overhead is just one broadcast. That is, the protocol extracts no message overhead for providing crash-tolerance if process failures and unanticipated fluctuations in communication delays do not occur. We are currently implementing our protocol as a CORBA (Common Object Request Broker Architecture) component. All known ORBs use IIOP as the standard protocol for inter-process communication, which in turn uses TCP/IP (transmission control protocol/Internet protocol) as the common transport protocol. It turns out that the notifying broadcast is easy to implement on top of the TCP transport layer.
10492741
Sequential consistency as lazy linearizability
This revue shows that, from an implementation point of view, sequential consistency can be considered as a form of lazy linearizability. This claim is supported by a versatile protocol that can be tailored to implement any of them.
10936330
Uniform agreement despite process omission failures
A process fails by omission if it "forgets" to send or receive messages. Considering omission failures is crucial for distributed systems, as such failures model both crash failures and incorrect behavior of process input/output buffers (such as buffer overflow). So, designing protocols that cope not only with crash failures but also with omission failures is a real challenge as soon as one is interested in obtaining real-time dependable distributed systems. While the consensus problem has received a lot of attention in the crash failure model and in the Byzantine failure model, it has received less attention in the omission failure model. This paper presents a simple uniform consensus protocol for synchronous systems made up of n processes where up to t can commit crash or omission failures. This protocol requires t+1 communication steps. Interestingly, as this bound is tight for crash failures and those are included in omission failures, this shows that t+1 is a tight lower bound for protocols solving uniform consensus in synchronous systems prone to process omission failures. The protocol assumes t<n/2 that is a necessary requirement on the maximum number of faulty processes that can be tolerated by any uniform consensus protocol in presence of omission failures. The proposed protocol is then extended, at no additional cost, to solve the interactive consistency problem.
28621306
Early Stopping in Global Data Computation
The Global Data Computation problem consists of providing each process with the same vector (with one entry per process) such that each entry is filled by a value provided by the corresponding process. This paper presents a protocol that solves this problem in an asynchronous distributed system where processes can crash, but equipped with a perfect failure detector. This protocol requires that processes execute asynchronous computation rounds. The number of rounds is upper bounded by min(f+2, t+1, n), where n, t, and f represent the total number of processes, the maximum number of processes that can crash, and the number of processes that actually crash, respectively. This value is a lower bound for the number of rounds when t<n-1. To our knowledge, this protocol is the first to achieve this lower bound. Interestingly, this protocol meets the same lower bound as the one required in synchronous systems.
1238245
A simple protocol offering both atomic consistent read operations and sequentially consistent read operations
A concurrent object is an object that can be concurrently accessed by several processes. Two well-known consistency criteria for such objects are atomic consistency (also called linearizability) and sequential consistency. Both criteria require that all the operations on the concurrent objects can be totally ordered in such a way that each read operation obtains the last value written into the corresponding object. They differ in the meaning of the word "last" that refers to physical time for atomic consistency, and to logical time for sequential consistency. This paper investigates the merging of these consistency criteria in a multiprocess program. The proposed combination offers two read operations to the processes, namely, an atomic read operation and a sequentially consistent read operation. While the first provides a process with the last "physical" value of an object, the second provides it with a value that is approximate with respect to real-time but whose semantics is perfectly well defined. A protocol that implements the combination on top of an asynchronous distributed system is described. The protocol provides a better understanding of the similarities and differences between these consistency criteria. Moreover, the protocol is generic in the sense that it can be tailored to provide only one of these consistency criteria.