14083759
Efficient Causality-Tracking Timestamping
Vector clocks are the appropriate mechanism used to track causality among the events produced by a distributed computation. Traditional implementations of vector clocks require application messages to piggyback a vector of n integers (where n is the number of processes). This paper investigates the tracking of the causality relation on a subset of events (namely, the events that are defined as "relevant" from the application point of view) in a context where communication channels are not required to be FIFO, and where there is no a priori information on the connectivity of the communication graph or the communication pattern. More specifically, the paper proposes a suite of simple and efficient implementations of vector clocks that address the reduction of the size of message timestamps, i.e., they do their best to have message timestamps whose size is less than n. The relevance of such a suite of protocols is twofold. From a practical side, it constitutes the core of an adaptive timestamping software layer that can used by underlying applications. From a theoretical side, it provides a comprehensive view that helps better understand distributed causality-tracking mechanisms.
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.
53225819
Conditions on input vectors for consensus solvability in asynchronous distributed systems
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.
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).
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.
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.
7058731
Approximate real-time clocks for scheduled events
This paper presents a simple protocol that provides application processes with an approximate real-time notion. This time notion is very versatile. At one extreme, it behaves at least as virtual time (being thereby consistent with causality). At the other extreme, it behaves as real-time. More precisely, with respect to approximate real-time all scheduled events are always executed at their scheduled time. If local computations took no time, approximate real-time would always be real-time. The system facilitates the rescheduling of events to bring real-time and approximate time closer together if local computations take too much time. A time-slotted leader election protocol using the proposed approximate time notion is described.
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.
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
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
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.