12635880
Token-based sequential consistency in asynchronous distributed systems
A concurrent object is an object that can be concurrently accessed by several processes. Sequential consistency is a consistency criterion for such objects. It informally states that a multiprocess program executes correctly if its results could have been produced by executing that program on a single processor system. (Sequential consistency is weaker than atomic consistency-the usual consistency criterion-as it does not refer to real-time.) The paper proposes a new, surprisingly simple protocol that ensures sequential consistency when the shared memory abstraction is supported by the local memories of nodes that can communicate only by exchanging messages through reliable channels. The protocol nicely combines, in a simple way, the use a of token with cached values. It has the noteworthy property to never invalidate cached values, thereby providing fast read operations (i.e., a process has never to wait to get a correct value of a shared object). Additionally, The paper presents a simple token navigation protocol.
52866155
Atomic Broadcast in Asynchronous Crash-Recovery Distributed Systems and Its Use in Quorum-Based Replication
Atomic broadcast is a fundamental problem of distributed systems: It states that messages must be delivered in the same order to their destination processes. This paper describes a solution to this problem in asynchronous distributed systems in which processes can crash and recover. A consensus-based solution to atomic broadcast problem has been designed by Chandra and Toueg for asynchronous distributed systems where crashed processes do not recover. We extend this approach: it transforms any consensus protocol suited to the crash-recovery model into an atomic broadcast protocol suited to the same model. We show that atomic broadcast can be implemented requiring few additional log operations in excess of those required by the consensus. The paper also discusses how additional log operations can improve the protocol in terms of faster recovery and better throughput. To illustrate the use of the protocol, the paper also describes a solution to the replica management problem in asynchronous distributed systems in which processes can crash and recover. The proposed technique makes a bridge between established results on weighted voting and recent results on the consensus problem.
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.
34685653
Token-based sequential consistency
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.
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.
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.
30548621
Interval Consistency of Asynchronous Distributed Computations
An interval of a sequential process is a sequence of consecutive events of this process. The set of intervals defined on a distributed computation defines an abstraction of this distributed computation, and the traditional causality relation on events induces a relation on the set of intervals that we call I-precedence. An important question is then, “Is the interval-based abstraction associated with a distributed computation consistent?” To answer this question, this paper introduces a consistency criterion named interval consistency (IC). Intuitively, this criterion states that an interval-based abstraction of a distributed computation is consistent if its I-precedence relation does not contradict the sequentiality of each process. More formally, IC is defined as a property of a precedence graph. Interestingly, the IC criterion can be operationally characterized in terms of timestamps (whose values belong to a lattice). The paper uses this characterization to design a versatile protocol that, given intervals defined by a daemon whose behavior is unpredictable, breaks them (in a nontrivial manner) in order to produce an abstraction satisfying the IC criterion. Applications to communication-induced checkpointing are suggested.
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.
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.
6481763
Decision optimal early-stopping k-set agreement in synchronous systems prone to send omission failures
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 focuses on the k-set agreement problem in the context of synchronous systems where up to t < n processes can experience crash or send omission failures (n being the total number of processes). The paper presents a k-set agreement protocol for this failure model (the first to our knowledge) which has two main outstanding features. (1) It provides the following early deciding and stopping property: no process decides or halts after the round min(/spl lfloor/f/k/spl rfloor/ + 2, /spl lfloor/t/k/spl rfloor/ + 1) where f is the number of actual crashes (0 /spl les/ f /spl les/ t). (2) It is decision-optimal. This new optimality criterion, suited to the omission failure model, concerns the number of processes that decide, namely, the protocol forces all the processes that do not crash to decide (regardless of whether they commit omission faults or not). It is noteworthy that each of these properties (early deciding/stopping vs decision-optimality) is not obtained at the detriment of the other. Last but not least, the protocol enjoys another first-class property, namely, simplicity.