A Background on Failure Detectors and Dynamic Systems 

Get Complete Project Material File(s) Now! »

Communication Models

There are two main communication models. In the shared memory model, processes communicate by reading and writing from/in shared variables. In the message passing model, processes communicate by exchanging messages.
The solutions presented in this thesis are based on message passing models. However, because the history of failure detectors in both models is closely intertwined, this chapter also presents failure detectors for shared memory systems.
In a message passing system, processes are connected by communication links (or channels). Links are often assumed to be bidirectional, although some works consider directed links. A process can only send a message to another process if it is connected to that process by a communication link.
The graph G = (V;E), where V = and E is the set of all links in the system, is called the communication graph of the system. The majority of the works in the literature make the assumption that the communication graph is connected or complete, meaning that every process can communicate with every other process (through the use of message forwarding in the case of a non-complete but connected graph).

Consensus and k-Set Agreement

In the consensus problem, processes attempt to agree on a common value. Each process has access to two functions: propose(value) and decide(value). Each process calls the propose(value) function once to submit a value to the agreement of the other processes. A process calls decide(value) when it has finally chosen a value. In order to solve the problem, the following properties must be verified:
Integrity: A process decides at most once.
Validity: Any decided value is a proposed value.
Agreement: No two different values are decided.
Termination: Every correct process eventually decides.
The consensus problem is one of the fundamental problems of distributed computing. In many distributed applications, processes have to agree on the state of the application. Such an agreement can be reached with consensus in the following manner: each process proposes its local view of the system to a consensus instance, and the properties of consensus then ensure that all the processes that are alive will eventually adopt the same, consistent view. As a result, consensus is used to implement state machine replication, to provide an atomic broadcast abstraction, or to consistently manage distributed databases.
Fischer, Lynch and Paterson proved in [FLP85] that it is impossible to solve consensus deterministically in an asynchronous system prone to crash failures, even if a single crash failure can occur. Many solutions have been proposed in the literature to circumvent this impossibility. One
approach is to consider a partially synchronous system, which is more realistic than a fully synchronous system while still allowing to solve consensus [DLS88]. Another approach consists in abstracting the timing assumptions made (synchrony or partial synchrony) through the use of failure detectors [CT96]. Finally, one last approach consists in considering a weaker version of the problem: this is the solution chosen for the Paxos algorithm [Lam98], where the termination property is not ensured.
A weaker problem than the consensus is the k-set agreement problem, introduced by Chaudhuri in [Cha93]. It is a generalization of the consensus. Similarly to the consensus, each process has access to the propose(value) and the decide(value) functions, and the following properties must be verified:
Integrity: A process decides at most once.
Agreement: At most k different values are decided.
Termination: Every correct process eventually decides.
Validity: Any decided value is a proposed value.

Fault-Tolerant Mutual Exclusion

The mutual exclusion problem was introduced by Dijkstra in [Dij65] and has since been widely studied in the literature [Lam74, Lam86, Ray86]. Mutual exclusion algorithms are used by many distributed applications that access shared resources. They must prevent a shared resource from being concurrently accessed by multiple processes.
In the mutual exclusion problem, the code of each process is divided in four sections: remainder section, try section, critical section and exit section. The remainder and critical sections are defined by the higher level application, while the try and exit sections are defined by the mutual exclusion algorithm. A process is said to be well-formed if executes its sections of code in the correct order. Provided that all processes are well-formed, the fault-tolerant mutual exclusion (FTME) problem is solved if the following properties are verified:
Safety: Two distinct processes cannot be in their critical section at the same time.
Liveness: If a correct process enters its try section, then at some time later some correct process enters the critical section. Additionally, if a correct process is in its exit section, at some time later it enters it remainder section.
The following additional fairness property is often considered along with FTME:
Starvation Freedom: If no process stays forever in its critical section, then every correct process that reaches its try section eventually enters its critical section.
It was proved in [DGFGK05] that, if a majority of processes are correct, then any algorithm solving FTME can be transformed into an algorithm that also verifies the starvation freedom property. Several mutual exclusion algorithms that tolerate crash failures have been proposed in the literature [NLM90, AEA91, SAS06]. Furthermore, mutual exclusion algorithms that tolerate crash-recovery failures in the shared memory model were proposed in [GR16, GH17, JJ17], with shared variables being stored in stable memory. One crash-recovery mutual exclusion algorithm for message passing systems was proposed in [CSL90], relying on the assumption that failures do not occur in adjacent connected processes.

Failure Detectors for Consensus and k-Set Agreement in Message Passing Systems

While the weakest failure detectors to solve consensus and set agreement have been identified, the generic case of k-set agreement for 1 k n􀀀1 in AMPn;f [;] seems to be a harder problem, as to this day the weakest failure detector to solve it has not yet been identified. Although most of the results take the form of sufficient failure detectors, [BRS11] proved that the assumption that k > n􀀀1 n􀀀f is necessary to solve k-set agreement in message passing systems. Table 2.1 (along with Table 2.2 in the next section) is an updated extension of the table presented by Raynal in [Ray11] and summarizes the failure detectors used to solve consensus and k-set agreement in the literature. The “Failure pattern” column in Table 2.1 indicates the additional assumption on the number of failures necessary for the failure detector to ensure the property of column “Property”.

The k and s k Partitioned Failure Detectors

The partitioned failure detectors are a set of failure detectors introduced in [CZCL07]. The goal is to weaken existing failure detectors by separating their safety and liveness properties. While it is necessary to always ensure the safety property for all processes, the liveness property is only required to be ensured for one component of the graph. Based on this approach, the authors deduce several new failure detectors and prove that they are weaker than the existing ones. k is the partitioned variant of ( k; ). s k is a weaker version of k using dynamic partitioning during the run. An algorithm solving k-set agreement in AMPn;f[s k] and inspired from the Paxos algorithm of [Lam98] is provided in [CZCL07].

The Sbl and bl Bounded Lifetime Failure Detectors

The bounded lifetime failure detectors were introduced by Friedman et al. in [FMR05]. These failure detectors provide the upper layer application with a fd_end() primitive, which can be invoked by the latter to inform the failure detector that it no longer requires the failure detector output. As a result, some failure detector properties are not required to be verified all the time. Sbl is the bound lifetime variant of S. Similarly to the original, it outputs a list of suspected processes, and must verify the same strong completeness property. Additionally, the following property must be verified: Bounded lifetime eventual weak accuracy: There is a time t and a time te such that from t until te, there is a process that is alive at te and that is not suspected by all the processes that have not crashed at time te. te is the time at which fd_end() is invoked. After te, the accuracy property no longer applies. In the article, the authors show that an existing S-based consensus algorithm can be adapted to use Sbl. The algorithm is modified so that every process invokes fd_end() after it decides. Such an algorithm still solves consensus, while allowing the failure detector to only ensure the accuracy property for some time.
The bl failure detector is also introduced, in the same article, as the bounded lifetime variant of . The local output history of bl for each process is delimited in time intervals, such that a new interval starts every time fd_end() is invoked. The intersection property only applies to pairs of quorums that were formed during consecutive or concurrent time intervals. The paper adapts an existing based atomic register protocol for bl by invoking fd_end() at the end of every read or write operation.

Directed Dynamic Networks

In [BRS12], Biely, Robinson and Schmid present a dynamic model close but weaker than the Dynamic Graph Model. This new model also revolves around synchronous rounds, but considers directed communication graphs that do not need to be connected at every round (therefore excluding the concept of T-interval connectivity) and uses the weaker assumption of vertex- stable root components instead. In every round, there must be exactly one strongly connected component that has only out-going links to some of the remaining processes and can reach every process in the system. The paper presents an algorithm for consensus under this assumption.
An algorithm for binary consensus (consensus with binary values) is provided in [CG13] in a similar model with directed communication graphs. The paper proposes an algorithm for consensus with a connectivity assumption which is proven necessary: there exists a same process that has a directed path towards all other processes for every round of the run. In [BRS+18] Biely et al. introduce the concept of gracefully degrading consensus: instead of solving k-set agreement for a preset value of k, the algorithm adapts to the network conditions it encounters during the run and attempts to provide agreement with the lowest possible value of k. To this end, the authors present both an algorithm and its proof using the same model as [BRS12] with similar assumptions on vertex-stable root components. The article also gives minimality results regarding temporal stability and information flow.

Table of contents :

1 Introduction 
1.1 Contributions
1.1.1 A Failure Detector for k-Set Agreement in Unknown Dynamic Systems
1.1.2 A Failure Detector for Mutual Exclusion in Unknown Dynamic Systems .
1.1.3 An Asynchronous Reliable Broadcast Algorithm over a Hypercube Topology
1.2 Publications
1.2.1 Papers in International Conferences
1.2.2 Papers in International Journals
1.3 Organization of the Manuscript
2 A Background on Failure Detectors and Dynamic Systems 
2.1 Distributed Systems
2.1.1 Processes
2.1.2 Communication Models
2.1.3 Failure Models
2.1.4 Timing Models
2.1.5 Notations
2.2 Distributed Problems
2.2.1 Consensus and k-Set Agreement
2.2.2 Fault-Tolerant Mutual Exclusion
2.3 Failure Detectors
2.3.1 The Failure Detector Hierarchy
2.3.2 Failure Detectors for Consensus and k-Set Agreement in Message Passing Systems
2.3.3 Failure Detectors for Consensus and k-Set Agreement in Shared Memory Systems
2.3.4 Failure Detectors for Mutual Exclusion
2.4 Dynamic Networks
2.4.1 Increasing and Decreasing Systems with a Static Communication Graph .
2.4.2 The Dynamic Graph Model
2.4.3 Directed Dynamic Networks
2.4.4 Evolving Graphs
2.4.5 Time-Varying Graphs (TVG)
2.4.6 Unknown Asynchronous Dynamic Networks
2.4.7 Summary of Failure Detector Results in Unknown and/or Dynamic Systems
2.5 Conclusion
3 A Failure Detector for k-Set Agreement in Unknown Dynamic Systems 
3.1 System Model
3.1.1 Process Model
3.1.2 Communication Model
3.2 Failure Detectors for k-Set Agreement in Unknown Dynamic Systems
3.2.1 The ?;k Failure Detector
3.2.2 The Family of Failure Detectors ?;x;y
3.3 Assumptions
3.3.1 Time-Varying Graph Classes
3.3.2 Message Pattern Assumptions
3.3.3 Summary of Assumptions
3.3.4 Implementation of Message Pattern Assumptions
3.3.5 Comparable Assumptions in the Literature
3.4 Failure Detector Algorithms
3.4.1 An Algorithm for ?;k
3.4.2 An Algorithm for ?;x
3.4.3 An Algorithm for ?;x;y
3.5 A k-Set Agreement Algorithm
3.5.1 The Alphax Sub Protocol
3.5.2 Alphax Algorithm
3.5.3 k-Set Agreement Algorithm
3.6 Conclusion
4 The Weakest Failure Detector for Mutual Exclusion in Unknown Dynamic Systems 
4.1 Model and Problem Definition
4.1.1 System Model
4.1.2 Failure Model
4.1.3 Connectivity Model
4.1.4 Knowledge Model
4.1.5 Problem Definition
4.2 Failure Detectors for Mutual Exclusion in Unknown Dynamic Systems
4.2.1 The T l Failure Detector
4.2.2 The T lr Failure Detector
4.3 Sufficiency of T lr to solve Fault-Tolerant Mutual Exclusion
4.3.1 Algorithm Description
4.3.2 Proof of Correctness
4.4 Necessity of T lr to solve Fault-Tolerant Mutual Exclusion
5 Conclusion 
5.1 Contributions
5.1.1 A Failure Detector for k-Set Agreement in Unknown Dynamic Systems
5.1.2 A Failure Detector for Recoverable Mutual Exclusion in Unknown Dynamic Systems
5.2 Perspectives
5.2.1 On the Necessity of Synchronous Processes in Dynamic Systems
5.2.2 The Weakest Failure Detector for k-Set Agreement
5.2.3 Defining the Mutual Exclusion Problem in Crash-Recovery Systems
A A Reliable Broadcast Protocol for Asynchronous Systems with a Hypercube Topology 
A.1 Introduction
A.2 Related Work
A.3 System Model
A.4 The VCube
A.5 Reliable Broadcast Algorithm for Asynchronous System
A.5.1 Message types and local variables
A.5.2 Algorithm description
A.5.3 Proof of correctness
A.6 Performance Discussion
A.7 Conclusion and Future Work
Bibliography 

GET THE COMPLETE PROJECT