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.
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.
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.
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.
1921101
An introduction to oracles for asynchronous distributed systems
This paper is an introduction to oracles the aim of which is to help solving distributed computing problems in asynchronous distributed systems prone to process crash failures and fair lossy channels. Actually, the combination of asynchrony and failures makes a lot of problems impossible to solve in unreliable asynchronous distributed systems. Hence, those systems have to be extended with appropriate oracles in order these problems become solvable. Using two such problems (namely, the design of a quiescent uniform reliable broadcast facility, and the consensus problem), this paper presents appropriate oracles allowing to solve these problems. In that sense, the paper is a guided tour to the definition of oracles suited to unreliable asynchronous distributed systems.
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.
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).
32842522
A generic framework for indulgent consensus
Consensus is a fundamental distributed agreement problem that has to be solved when one has to design or implement reliable applications. As consensus cannot be solved in pure asynchronous distributed systems, those systems have to be equipped with appropriate oracles to circumvent the impossibility. Several oracles (unreliable failure detector leader capability, random number generator) have been proposed, and consensus protocols based on such ad hoc oracles have been designed This paper presents a generic consensus framework that can be instantiated with any oracle, or combination of oracles, that satisfies a set of properties. This generic framework provides indulgent consensus protocols that are particularly simple and efficient both in well-behaved runs (i.e., when there are no failures), and in stable runs (i.e., when there is no failure during the execution although some processes can be initially crashed). In those runs, the protocols terminate in two communication steps (which is optimal). Indulgence means that the resulting protocol never violates its safety property even when the underlying oracle behaves arbitrarily. Interestingly, the protocol can also allow processes to decide in one communication step in some specific configurations.
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.
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
41622968
Building Responsive TMR-Based Servers in Presence of Timing Constraints
This paper is on the construction of a fault-tolerant and responsive server subsystem in an application context where the subsystem is accessed through an asynchronous network by a large number of clients. The server is made fault-tolerant by the triple modular redundancy (TMR) technique: at least two server processes behave correctly, while the third one can behave arbitrarily. An essential requirement for process replication is that the client inputs be delivered to server replicas for processing in an identical order. Moreover, in order to cope with process' memory requirement, a time bound constraint is imposed: no client input can stay in the local memory of server process more than /spl Sigma/ units of time. Based on known technologies, two assumptions are made: (1) the network delivers a given client input to any two server processes within a known bounded time (D), and (2), there is an Ordered Timed Atomic Broadcast protocol built on top of the TMR system with timeliness A. The paper presents two results. The first is a protocol that delivers an ordered stream of client inputs, such that every client input is delivered exactly once to each correct server, thus eliminating redundant verification. It works under the assumption /spl Sigma/>D+/spl Delta/. The second is an impossibility result, namely there can be no ordering protocol when /spl Sigma/<D+/spl Delta/_, where /spl Delta/_ is the minimum timeliness of any reliable broadcast protocol that can be implemented on top of the TMR server (/spl Delta/_ < /spl Delta/).