The problem. We consider the problem of implementing a consistent replicated object in a partially synchronous message passing distributed system susceptible to process and communication failures. The object is a generic shared resource, such as a data structure, a file, or a lock. The processes implementing the replicated object access it by applying operations to it at unpredictable times and potentially concurrently.1 The object should be linearizable: it should behave as if each operation applied to it takes effect at a distinct instant in time during the interval between its invocation and its response.

We describe our experience in building a fault-tolerant data-base using the Paxos consensus algorithm. Despite the existing literature in the field, building such a database proved to be non-trivial. We describe selected algorithmic and engineering problems encountered, and the solutions we found for them. Our measurements indicate that we have built a competitive system.

We study the consensus problem, which requires multiple processes with different input values to agree on one of these values, in the context of asynchronous shared memory systems. Prior research focussed either on t-resilient solutions of this problem (which must be correct even if up to t processes crash) or on wait-free solutions (which must be correct despite the crash of any number of processes). In this paper, we show that these two forms of solvability are closely related. Specifically, for all $n > t \ge 2$ and all sets ${\mathcal{S}}$ of shared object types (that include simple read/write registers), there is a t-resilient solution to n-process consensus using objects of types in ${\mathcal{S}}$ if and only if there is a wait-free solution to (t + 1)-process consensus using objects of types in ${\mathcal{S}}$. Our proof of this equivalence uses another result derived in this paper, which is of independent interest. Roughly speaking, this result states that a wait-free solution to (n - 1)-process consensus is never necessary in designing a wait-free solution to n-process consensus, regardless of the types of objects available. More precisely, for all $n \ge 2$ and all sets ${\mathcal{S}}$ of shared object types (that include simple read/write registers), if there is a wait-free solution to n-process consensus that uses a wait-free solution to (n - 1)-process consensus and objects of types in ${\mathcal{S}}$, then there is a wait-free solution to n-process consensus that uses only objects of types in ${\mathcal{S}}$.

Process groups in distributed applications and services rely on failure detectors to detect process failures completely, and as quickly, accurately, and scalably as possible, even in the face of unreliable message deliveries. In this paper, we look at quantifying the optimal scalability, in terms of network load, (in messages per second, with messages having a size limit) of distributed, complete failure detectors as a function of application-specified requirements. These requirements are 1) quick failure detection by some non-faulty process, and 2) accuracy of failure detection. We assume a crash-recovery (non-Byzantine) failure model, and a network model that is probabilistically unreliable (w.r.t. message deliveries and process failures). First, we characterize, under certain independence assumptions, the optimum worst-case network load imposed by any failure detector that achieves an application's requirements. We then discuss why traditional heart beating schemes are inherently unscalable according to the optimal load. We also present a randomized, distributed, failure detector algorithm that imposes an equal expected load per group member. This protocol satisfies the application defined constraints of completeness and accuracy, and speed of detection on an average. It imposes a network load that differs frown the optimal by a sub-optimality factor that is much lower than that for traditional distributed heartbeating schemes. Moreover, this sub-optimality factor does not vary with group size (for large groups).

The publish/subscribe (or pub/sub) paradigm is an increasingly popular model for interconnecting applications in a distributed environment. Many existing pub/sub systems are based on pre-defined subjects, and hence are able to exploit multicast technologies to provide scalability and availability. An emerging alternative to subject-based systems, known as content-based systems, allow information consumers to request events based on the content of published events. This model is considerably more flexible than subject-based pub/sub. However, it was previously not known how to efficiently multicast published events to interested content-based subscribers within a large and geographically distributed network of broker (or router) machines. We develop and evaluate a novel and efficient distributed algorithm for this purpose, called -link matching". Link matching performs just enough computation at each node to determine the subset of links to which an event should be forwarded. We show via simulations that: link matching yields higher throughput than flooding when subscriptions are selective; and the overall CPU utilization of link matching is comparable to that of centralized matching.

Content-based subscription systems are an emerging alternative to traditional publish-subscribe systems, because they permit more flexible subscriptions along multiple dimensions. In these systems, each subscription is a predicate which may test arbitrary attributes within an event. However, the matching problem for content-based systems — determining for each event the subset of all subscriptions whose predicates match the event — is still an open problem. We present an efficient, scalable solution to the matching problem. Our solution has an expected time complexity that is sub-linear in the number of subscriptions, and it has a space complexity that is linear. Specifically, we prove that for predicates reducible to conjunctions of elementary tests, the expected time to match a random event is no greater than O(N 1;) where N is the number of subscriptions, and is a closed-form expression that depends on the number and type of attributes (in some cases, 1=2). We present some optimizations to our algorithms that improve the search time. We also present the results of simulations that validate the theoretical bounds and that show acceptable performance levels for tens of thousands of subscriptions. 1

An implementation of a shared object O is t-tolerant if the object remains correct and wait-free even when up to t base objects (objects used in the implementation of O) fail. The implementation is gracefully degrading if, no matter how many base objects fail, O does not fail more severely than its base objects. For the omission failure mode, we derive a lower bound on the space complexity of a gracefully degrading t-tolerant implementation. This result lets us conclude that, for omission failures, graceful degradation can be achieved only at the cost of increased space complexity.

A (wait-free) universal construction is attractive because, no matter what types of wait-free objects are needed by applications, they can be implemented simply by instantiating the universal construction with the appropriate types. However, the worst-case time complexity of every existing n-process universal construction is # n): that is, in any implementation obtained by instantiating a universal construction, in the worst-case a process performs# n) computation in order to complete a single operation on the implemented object. In fact, a lower bound of # n) has been proved for the worst-case local time complexity of any oblivious universal construction [12]. Since universal constructions with sublinear time complexity do not seem possible, it is natural to explore "semiuniversal " constructions that can e#ciently implement large classes of objects (as opposed to all objects). We present such a construction in this paper. Our construction implements a large class of objects, that ...

Wait-free implementations of shared objects tolerate the failure of processes, but not the failure of base objects from which they are implemented. We consider the problem of implementing shared objects that tolerate the failure of both processes and base objects. We identify two classes of object failures: responsive and nonresponsive . With responsive failures, a faulty object responds to every operation, but its responses may be incorrect. With nonresponsive failures, a faulty object may also “hang” without responding. In each class, we define crash, omission, and arbitrary modes of failure. We show that all responsive failure modes can be tolerated. More precisely, for all responsive failure modes ℱ, object types T , and t ≥ 0, we show how to implement a shared object of type T which is t -tolerant for ℱ. Such an object remains correct and wait-free even if up to t base objects fail according to ℱ. In contrast to responsive failures, we show that even the most benign non-responsive failure mode cannot be tolerated. We also show that randomization can be used to circumvent this impossibility result. Graceful degradation is a desirable property of fault-tolerant implementations: the implemented object never fails more severely than the base objects it is derived from, even if all the base objects fail. For several failure modes, we show wheter this property can be achieved, and, if so, how.

I present the first randomized wait-free implementation of consensus from multiple writer zmltiple reader register in which each process takes polylog (0(log2 n)) expected steps.To achieve this result, I assume a non-standard type of adversary (from [Abr88]).I argue that this type of adversary (which is more powerful than the oblivious adversary, but weaker than the strong adversary) is powerful enough to model practical systems.Even though different processes may concurrently access a shared object, it is desirable that the object behave as if all these accesses occur in some sequential order.More precisely, the behavior of a shared object must be keaTizab/e [H W90].one way to ensure

Projet REFLECS

We determine what information about failures is necessary and sufficient to solve Consensus in asynchronous distributed systems subject to crash failures. In Chandra and Toueg [1996], it is shown thatW, a failure detector that provides surprisingly little information about which processes have crashed, is sufficient to solve Consensus in asynchronous systems with a majority of correct processes. In this paper, we prove that to solve Consensus, any failure detector has to provide at least as much information as W. Thus, W is indeed the weakest failure detector for solving Consensus in asynchronous systems with a majority of correct processes.

We introduce the concept of unreliable failure detectors and study how they can be used to solve Consensus in asynchronous systems with crash failures. We characterise unreliable failure detectors in terms of two properties—completeness and accuracy. We show that Consensus can be solved even with unreliable failure detectors that make an infinite number of mistakes, and determine which ones can be used to solve Consensus despite any number of crashes, and which ones require a majority of correct processes. We prove that Consensus and Atomic Broadcast are reducible to each other in asynchronous systems with crash failures; thus, the above results also apply to Atomic Broadcast. A companion paper shows that one of the failure detectors introduced here is the weakest failure detector for solving Consensus [Chandra et al. 1992].

We seek two properties in such a hierarchy:(1) If a type T is at level N, then, for all types T',

The authors classify object failures into two broad categories: responsive and non-responsive. They require that wait-free objects subject to responsive failures continue to respond (in finite time) to operation invocations. The responses may be incorrect. In contrast, wait-free objects subject to non-responsive failures are exempt from responding to operation invocations. Such objects may 'hang' on the invoking process. They divide responsive failures into three models: R-crash,R-omission, and R-arbitrary. They divide non-responsive failures into crash, omission, and arbitrary. An object subject to crash failure behaves correctly until it fails, and once it fails, it never responds to operation invocations. An object subject to omission failures may fail to respond to the invocations of an arbitrary subset of processes, but continue to respond to the invocations of the remaining processes (forever).>

We determine what information about failures is necessary and sufficient to solve Consensus in asynchronous distributed systems subject to crash failures.In [CT91], we proved that OVV, a failure