15195790
Core Persistence in Peer-to-Peer Systems: Relating Size to Lifetime
Distributed systems are now both very large and highly dynamic Peer to peer overlay networks have been proved efficient to cope with this new deal that traditional approaches can no longer accommodate While the challenge of organizing peers in an overlay network has generated a lot of interest leading to a large number of solutions, maintaining critical data in such a network remains an open issue In this paper, we are interested in defining the portion of nodes and frequency one has to probe, given the churn observed in the system, in order to achieve a given probability of maintaining the persistence of some critical data More specifically, we provide a clear result relating the size and the frequency of the probing set along with its proof as well as an analysis of the way of leveraging such an information in a large scale dynamic distributed system.
14362073
The Alpha of Indulgent Consensus
This paper presents a simple framework unifying a family of consensus algorithms that can tolerate process crash failures and asynchronous periods of the network, also called indulgent consensus algorithms. Key to the framework is a new abstraction we introduce here, called Alpha, and which precisely captures consensus safety. Implementations of Alpha in shared memory, storage area network, message passing and active disk systems are presented, leading to directly derived consensus algorithms suited to these communication media. The paper also considers the case where the number of processes is unknown and can be arbitrarily large.
20003649
Synchronous condition-based consensus
AbstractThe condition-based approach studies restrictions on the inputs to a distributed problem, called conditions, that facilitate its solution. Previous work considered mostly the asynchronous model of computation. This paper studies conditions for consensus in a synchronous system where processes can fail by crashing. It describes a full classification of conditions for consensus, establishing a continuum between the asynchronous and synchronous models, with the following hierarchy $${\cal S}_t^{[-t]}\subset\cdots\subset {\cal S}_t^{[0]}\subset\cdots\subset {\cal S}_t^{[t]}$$ where $${\cal S}_t^{[t]}$$ includes all conditions (and in particular the trivial one made up of all possible input vectors). For a condition $$C \in{\cal S}_t^{[d]}$, $-t \leq d \leq t$$, we have:
For values of $$d \leq 0$$ consensus is solvable in an asynchronous system with t failures, and we obtain the known hierarchy of conditions that allows solving asynchronous consensus with more and more efficient protocols as we go from d = 0 to d = −t.For values of $$d \leq 0$$ consensus is solvable in an asynchronous system with t failures, and we obtain the known hierarchy of conditions that allows solving asynchronous consensus with more and more efficient protocols as we go from d = 0 to d = −t.For values of d<0 consensus is known not solvable in an asynchronous system with t failures, but we obtain a hierarchy of conditions that allows solving synchronous consensus with protocols that can take more and more rounds, as we go from d = 0 to d = t.d = 0 is the borderline case where consensus can be solved in an asynchronous system with t failures, and can be solved optimally in a synchronous system.
 After having established the complete hierarchy, the paper concentrates on the two last items: $$0\leq d\leq t$$. The main result is that the necessary and sufficient number of rounds needed to solve uniform consensus for a condition $$C \in {\cal S}_t^{[d]}$$ (such that $$C\notin {\cal S}_t^{[d-1]}$$) is d +1.In more detail, the paper presents a generic synchronous early-deciding uniform consensus protocol that enjoys the following properties. Let f be the number of actual crashes, I the input vector and $$C \in {\cal S}_t^{[d]}$$ the condition the protocol is instantiated with. The protocol terminates in two rounds when $$I\in C$$ and $$f\leq t-d$$, and in at most d +1 rounds when $$I\in C$$ and $$f>t-d$$. (It also terminates in one round when $$I\in C$$ and $$d=f=0$$.) Moreover, whether I belongs or not to C, no process requires more than min$$(t+1,f+2)$$ rounds to decide. The paper then proves a corresponding lower bound stating that at least d +1 rounds are necessary to get a decision in the worst case when $$I\in C$$ (for $$C \in {\cal S}_t^{[d]}$$ and $$C \notin {\cal S}_t^{[d-1]}$$).
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/).
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
39476661
The Committee Decision Problem
We introduce the (b,n)-Committee Decision Problem (CD) – a generalization of the consensus problem. While set agreement generalizes consensus in terms of the number of decisions allowed, the CD problem generalizes consensus in the sense of considering many instances of consensus and requiring a processor to decide in at least one instance. In more detail, in the CD problem each one of a set of n processes has a (possibly distinct) value to propose to each one of a set of b consensus problems, which we call committees. Yet a process has to decide a value for at least one of these committees, such that all processes deciding for the same committee decide the same value. We study the CD problem in the context of a wait-free distributed system and analyze it using a combination of distributed algorithmic and topological techniques, introducing a novel reduction technique. 
 
We use the reduction technique to obtain the following results. We show that the (2,3)-CD problem is equivalent to the musical benches problem introduced by Gafni and Rajsbaum in [10], and both are equivalent to (2,3)-set agreement, closing an open question left there. Thus, all three problems are wait-free unsolvable in a read/write shared memory system, and they are all solvable if the system is enriched with objects capable of solving (2,3)-set agreement. While the previous proof of the impossibility of musical benches was based on the Borsuk-Ulam (BU) Theorem, it now relies on Sperner's Lemma, opening intriguing questions about the relation between BU and distributed computing tasks.
20443923
The Renaming Problem as an Introduction to Structures for Wait-Free Computing
The aim of this introductory survey paper is twofold: to be an introduction to wait-free computing and present the renaming problem. “Wait-free” means that the progress of a process depends only on it, regardless of the other processes (that can progress slowly or even crash). It is shown that the design of wait-free algorithms rests on the definition and the use of appropriate data/control structures. To illustrate such structures, the paper considers the renaming problem where the processes have to acquire new names from a small bounded space despite possible process crashes. Two renaming algorithms are presented. The first is a protocol due to Moir and Anderson; it is based on a grid of splitters. The second is due to Attiya and Fouren; it is based on a network of reflectors. It appears that splitters and reflectors are basic data/control structures that permit to define switching networks well-suited to wait-free computing.
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.
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.
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.
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.