7695617
A Hierarchy of Conditions for Asynchronous Interactive Consistency
The condition based approach consists in identifying sets of input vectors, called conditions, for which it is possible to design a protocol solving a distributed computing problem despite failures. In a recent work we have applied the condition based approach to the interactive consistency (IC) problem (the agreement problem where the processes have to agree on the vector of proposed values), and provided a characterization of the conditions that allow us to solve it in presence of up to f c process crashes and f e erroneous proposals. We have shown that these conditions correspond exactly to error correcting codes, where the errors can be erasures or modified values. Here, we investigate this set of conditions from a complexity perspective, and show that it actually consists of a hierarchy of classes of conditions, \(\mathcal{E}^{[\delta]}_{f_c,f_e}\), where δ is the degree of the condition (0 ≤ δ ≤ f c ), each class being contained in the previous one (intuitively, the value f c -δ represents the “difficulty” of a class).
14420908
A necessary and sufficient condition for transforming limited accuracy failure detectors
Unreliable failure detectors are oracles that give information about process failures. Chandra and Toueg were first to study such failure detectors for distributed systems, and they identified a number that enabled the solution of the Consensus problem in asynchronous distributed systems. This paper focuses on two of these, denoted J (strong) and ♦J (eventually strong). The characteristics of a given unreliable failure detector are usually described by its completeness and accuracy properties. Completeness is a requirement on the actual detection of failures, while accuracy limits the mistakes a failure detector can make. Let the scope of the accuracy property of an unreliable failure detector be the minimum number (k) of processes that may not erroneously suspect a correct process to have crashed. Usual failure detectors implicitly consider a scope equal to n (the total number of processes). Accuracy properties with limited scope give rise to the classes of failure detectors that we call Jk and ♦Jk. This paper investigates the following question: "Given Jk and ♦Jk, under which condition is it possible to transform their failure detectors into their counterparts with unlimited accuracy, i.e., AP and J ♦J?". The paper answers this question in the following way. It first presents a particularly simple protocol that realizes such a transformation when f > k (where f is the maximum number of processes that may crash). Then, it shows that there is no reduction protocol when f ≥ k.
2957922
Simple and efficient oracle-based consensus protocols for asynchronous Byzantine systems
This paper is on the consensus problem in asynchronous distributed systems where (up to f) processes (among n) can exhibit a Byzantine behavior, i.e., can deviate arbitrarily from their specification. A way to solve the consensus problem in such a context consists of enriching the system with additional oracles that are powerful enough to cope with the uncertainty and unpredictability created by the combined effect of Byzantine behavior and asynchrony. Considering two types of such oracles, namely, an oracle that provides processes with random values, and a failure detector oracle, the paper presents two families of Byzantine asynchronous consensus protocols. Two of these protocols are particularly noteworthy: they allow the processes to decide in one communication step in favorable circumstances. The first is a randomized protocol that assumes n > 5f. The second one is a failure detector-based protocol that assumes n > 6f. These protocols are designed to be particularly simple and efficient in terms of communication steps, the number of messages they generate in each step, and the size of messages. So, although they are not optimal in the number of Byzantine processes that can be tolerated, they are particularly efficient when we consider the number of communication steps they require to decide, and the number and size of the messages they use. In that sense, they are practically appealing.
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.
14022316
Conditions on input vectors for consensus solvability in asynchronous distributed systems
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.
The first main result is a generic consensus protocol for the shared memory model. It always guarantees agreement, and also termination (at least) when the inputs satisfy the condition with which the protocol has been instantiated, or when there are no crashes. Then, two particular realistic conditions are defined, and proved to be maximal.
The second main result is a characterization of the conditions that allow to solve consensus. The consensus protocol works for any such condition. An efficient version of the protocol is then designed for the message passing model that works when f\geq, and it is shown that no such protocol exists when f\geq n/2. It is also shown how the protocol's safety can be traded for its liveness.
13166562
Using Conditions to Expedite Consensus in Synchronous Distributed Systems
The condition-based approach to solve consensus has initially been developed in the context of asynchronous systems. It identifies a class of acceptable conditions on the set of input vectors that, when satisfied by the actual input vector, are exactly the conditions that allow to solve consensus despite up to t faulty processes. This paper investigates the use of conditions to solve consensus in synchronous systems prone to process crash failures. It first shows that for any acceptable condition there is a condition-based protocol solving uniform consensus that enjoys the following property: when the input vector belongs to the condition, it terminates in a single round if no process crashes, and in two rounds otherwise. When the input vector does not belong to the condition, the actual number of rounds is upper bounded by t+1 (it actually depends on both the crash pattern and the input vector). The paper then extends the previous protocol to combine early decision with the condition-based approach. It presents a general protocol that enjoys the previous properties (decision in one or two rounds) when the input vector belongs to the condition and terminates in at most (t + 1, f + 2) rounds when the input vector does not belong to the condition (where f is the actual number of faulty processes). Finally, the paper presents corresponding matching lower bounds. It shows that acceptable conditions are the only ones for which a consensus protocol can enjoy the previous properties.
32302413
Sequential Consistency as Lazy Linearizability
This paper shows that actually sequential consistency is a form of "lazy" atomic consistency. More precisely, it proposes a new particularly simple sequential consistency protocol that orders the conflicting operations on each object separately, and appropriately invalidates object copies to prevent consistency violation. When compared to invalidation-based protocols that ensure atomic consistency (such as Li-Hudak's protocol), the proposed protocol can be seen as using lazy invalidation. Hence, in addition to a new consistency protocol, the paper provides a new insight into the concepts and mechanisms that underlie consistency protocols: while atomic consistency is based on physical time and requires eager invalidation, sequential consistency is based on logical time and needs only lazy invalidation.
5355347
An introduction to the renaming problem
The aim of this paper is to provide a brief introduction to the renaming problem for unfamiliar readers. In the renaming problem the processes have to acquire new names from a small bounded space despite possible process crashes and asynchrony. The problem is first introduced. Then two solutions are presented. One considers the shared memory model, while the second considers the message-passing model.
207104353
A Note on the Determination of the Immediate Predecessors in a Distributed Computation
A distributed computation can be modeled as a partially ordered set (poset) of relevant events (the relevant events are the subset of the primitive events that are meaningful for an observer). This short note presents a general protocol that, when superimposed on a distributed computation, provides each relevant event with a timestamp that identifies exactly its immediate predecessors in the poset. This determination is done on the fly and without using additional control messages. So, the proposed protocol provides an on the fly computation of the Hasse diagram (transitive reduction) of the event graph produced by a distributed computation. The protocol is particularly simple and efficient. It is based on a general condition that allows application messages to piggyback control information whose size can be smaller than n (the number of processes). Interestingly, when one is not interested in tracking the immediate predecessors, the proposed protocol can be simplified to get an efficient vector clock protocol that does not require particular channel assumptions.
6896229
The Power and Limit of Adding Synchronization Messages for Synchronous Agreement
This paper investigates the use of additional synchronization messages in round-based message-passing synchronous systems. It first presents a synchronous computation model allowing a process to send such messages. The difference with respect to the traditional round-based synchronous model lies in the sending phase, where a process can first send a data message to each other process, and then, without a break, a synchronization message (their sendings can be pipelined). This model is suited to the class of local area networks where communication channels are reliable. (It is not for networks where unreliable communication requires message retransmission.) To illustrate the model, the paper presents a uniform consensus algorithm suited to this model. This algorithm, based on the rotating coordinator paradigm, allows the processes to decide in at most f + 1 rounds where f is the actual number of processes that crash in the corresponding run. (This improves the f + 2 lower bound of the traditional synchronous model.) In addition to its efficiency, the algorithm enjoys another first class property, namely, design simplicity. The paper focuses also on lower bound results, and shows that any uniform consensus algorithm designed for the proposed model, requires at least f + 1 rounds in the worst case. The proposed algorithm is consequently optimal. In that sense the paper has to be seen as an investigation of both the power and the limit of adding synchronization messages to synchronous systems built on top of local networks with reliable communication
35647117
Early-Stopping k-Set Agreement in Synchronous Systems Prone to Any Number of Process Crashes
The k-set agreement problem is a generalization of the consensus problem: each process proposes a value, and 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.

This paper presents a surprisingly simple protocol that solves the k-set agreement problem in synchronous systems prone to up to t<n processes can crash (where n is the total number of processes). The proposed protocol is the first early stopping k-set agreement protocol that does not impose a constraint on t. It allows the processes to decide and stop by min $(\lfloor f/k \rfloor +2,\lfloor t/k \rfloor+1)$ rounds where f is the number of actual crashes (0≤ f ≤ t). In addition to its conceptual simplicity, the protocol has an additional noteworthy feature, namely, it is particularly efficient in common case scenarios. This comes from the fact that it is based on a mechanism that allows the processes to take into account the actual pattern of failures and not only their number, thereby allowing the processes to decide in much less than ${\lfloor f/k \rfloor +2}$ coding from an InlineMediaObject here! rounds in a lot of cases.