A Background on Failure Detectors and Dynamic Systems

Keywords: systèmes distribués, détecteurs de fautes, systèmes dynamiques, k-accord, exclusion mutuelle distributed systems, failure detectors, dynamic systems, k-set agreement, mutual exclusion v

Dans le problème du consensus, tous les processus corrects du système doivent se mettre d'accord sur une unique valeur. Le problème du k-accord est une généralisation du consensus dans laquelle les processus peuvent se mettre d'accord sur au plus k valeurs. Le problème de l'exclusion mutuelle nécessite de permettre aux processus l'accès à une section critique, tout en garantissant qu'au plus un processus peut se trouver en section critique à tout moment. Ces problèmes fondamentaux de l'algorithmique distribuée ont été largement étudiés, mais la plupart des solutions existantes s'appuient sur l'hypothèse implicite que le système n'est pas dynamique.

Traditionellement, l'algorithmique distribuée consiste à étudier des systèmes distribués dans lesquels la liste des participants est statique et le graphe de communication est connecté, voire complet. Mais afin de modéliser les réseaux modernes, tels que les réseaux pair-à-pair ou sans fil, il est nécessaire de considérer une nouvelle sorte de systèmes distribués. Les systèmes dynamiques sont des systèmes distribués dans lesquels (1) les processus peuvent rejoindre ou quitter le système en cours d'exécution, et (2) le graphe de communication évolue au fil du temps.

L'abstraction des détecteurs de fautes a été introduite afin de contourner l'impossibilité de résoudre le consensus dans les systèmes asynchrones sujets aux pannes franches. Un détecteur de fautes est un oracle local fournissant aux processus des informations non fiables sur les pannes de processus. Mais un détecteur de fautes qui est suffisant pour résoudre un problème donné dans un système statique n'est pas nécessairement suffisant pour résoudre le même problème dans un système dynamique. De plus, certains détecteurs de fautes ne peuvent pas être implémentés dans un système dynamique. Par conséquent, il est nécessaire de redéfinir les détecteurs de fautes existants et de concevoir de nouveaux algorithmes.

Dans cette thèse, nous fournissons une nouvelle définition d'un détecteur de fautes pour le kaccord, et nous prouvons qu'il est suffisant pour résoudre le k-accord dans un système dynamique. Nous définissons également un modèle de système dynamique, ainsi qu'un algorithme capable d'implémenter ce nouveau détecteur de fautes dans notre modèle.

De plus, nous adaptons un détecteur existant pour l'exclusion mutuelle et nous prouvons que même dans les systèmes dynamiques, il s'agit toujours du détecteur de fautes le plus faible pour résoudre l'exclusion mutuelle. Cela signifie que ce détecteur est plus faible que tous les autres détecteurs capables de résoudre l'exclusion mutuelle.

Distributed systems are made of processes that attempt to solve distributed problems by cooperating. These processes can communicate with each other by using shared memory or by exchanging messages. Distributed algorithms describe the steps taken by each process, in particular the read/write operations (in the case of shared memory systems) or the send/receive operations (in the case of message passing systems). The field of distributed computing consists in designing algorithms that solve problems in distributed systems.

A process in a distributed system might fail during the run, and therefore stop following the steps described in its algorithm. A process that fails is called a "faulty" process, while a process that always behaves according to its algorithm is called a "correct" process. Different failure models can be considered: in the crash failure model, a process that fails (crashes) simply stops taking steps for the rest of the run. In the crash/recovery model, a process can crash but might later resume its algorithm. Finally, in the Byzantine model [START_REF] Lamport | The Byzantine Generals Problem[END_REF], faulty processes can exhibit any arbitrary behaviour, and might even actively work against the algorithm.

A distributed algorithm that solves a problem despite process failures is said to be faulttolerant.

In message passing systems, some communication models assume that communication is synchronous, which means that there is a bound on message transfer delays and processes are aware of this bound. Other models consider communication to be partially synchronous, which means that either processes are not aware of the bound on message transfer delays, or the bound is only guaranteed to hold after some unknown time. Finally, some models make no assumption on communication synchrony and consider that there is no bound on message transfer delays: communication is therefore asynchronous.

There are many different models for distributed systems, each making different communication or failure assumptions. A distributed problem can only be solved in certain models. Determining which system assumptions are necessary and/or sufficient to solve a given problem is an important challenge of distributed computing.

A well-known distributed problem is the consensus. In the consensus problem, each process proposes a value, and each correct process must decide a value such that no two different values are decided, and every decided value is a proposed value. The consensus is a fundamental problem in the field of distributed computing. It is used in distributed databases to replicate data while maintaining consistency. A notorious solution to the consensus is the Paxos algorithm [START_REF] Lamport | The Part-Time Parliament[END_REF], which is used, for instance, by Google to maintain consistency between its duplicated indexes.

It was proved in [START_REF] Michael | Impossibility of Distributed Consensus with One Faulty Process[END_REF] that in the presence of even a single crash failure, it is impossible to solve consensus deterministically in an asynchronous system.

Many articles in the literature have proposed ways to circumvent this impossibility. The partial synchrony model [START_REF] Dwork | Consensus in the presence of partial synchrony[END_REF] was introduced as a way to detect crashes and solve consensus without the costly assumption of full communication synchrony. The Paxos algorithm [START_REF] Lamport | The Part-Time Parliament[END_REF] tolerates asynchrony while solving a weaker version of consensus where termination is not guaranteed. Another approach is the failure detector abstraction [START_REF] Deepak | Unreliable Failure Detectors for Reliable Distributed Systems[END_REF].

A failure detector is a distributed oracle that provides each process in the system with information, that is not always reliable, on process failures. This information is unreliable in the sense that some correct processes might be falsely suspected of being faulty, while some faulty processes might be believed to be correct. Different classes of failure detectors provide different guarantees on the reliability of the information provided.

A failure detector is said to be weaker than another one if it is possible to implement the first by using the information provided by the second. A failure detector is said to be the weakest to solve a given problem if (1) the information it provides is sufficient to solve the problem and (2) it is weaker than every other detector that solves the problem. By identifying which failure detector class is the weakest to solve a given distributed problem, it is possible to abstract the minimum assumptions needed to solve the problem (such as communication synchrony, or a limitation on the number of failures).

Although many papers in the literature have identified failure detectors sufficient and/or necessary to solve various distributed problems, these results have mostly been confined to static and known systems. However, networks such as wireless, peer-to-peer or ad-hoc networks are inherently dynamic and cannot be modeled as static systems.

In dynamic systems, processes can join or leave the system during the run. Additionally, the communication channels between processes might be intermittent, meaning that the connections between processes can vary during the run, and therefore the communication graph will evolve over time.

In unknown systems, processes do not know the number nor the identities of the participants in the system at the start of the run. Indeed, in a dynamic system where processes might join the system later in the run, it is unreasonable to expect that every process would know the list of processes from the start.

Unknown dynamic systems pose new challenges that existing algorithms in the literature are not able to deal with. As a result, some existing failure detector definitions cannot be implemented in these new systems, while other failure detectors are no longer sufficient to solve some problems.

Traditionally, failure detectors are used in system models considering static and fully connected communication graphs. These connectivity properties are usually presented as properties of the system model rather than the failure detector augmenting it. When considering a much weaker system model such as a dynamic network, solving any non-trivial problem still requires the assumption of a certain degree of graph connectivity, as not much can be done in a system where no communication link is ever active. Studying dynamic systems means considering the level of temporal connectivity required to solve a specific problem, and using a generic and strong connectivity assumption would defeat that purpose. Instead, the goal should be to use a weak connectivity assumption that is still sufficient to solve the problem. Therefore, to solve a given agreement problem, two things are necessary: (1) a failure detector and (2) connectivity assumptions.

But if connectivity assumptions must be added to the system model in addition to the failure detector, then an argument could be made that the failure detector is not sufficient to solve the problem. For this reason, and because in a dynamic system the required level of connectivity is as dependent on the problem as the required failure detector, it makes sense to include connectivity properties in the failure detector definition. Adding these properties should not be seen as strengthening the failure detector, they are still weaker than the assumption of a fully connected, static communication graph.

Another approach is to keep the connectivity properties as part of the system model, separate from the failure detector definition. The advantage of this solution is that the resulting failure detector is only defined in terms of the information it provides on failures. It is therefore closer and more easily comparable to the definitions of existing failure detectors in static systems.

Contributions

This thesis aims to extend some existing failure detector results, providing new definitions which are more suitable to unknown dynamic systems. Additionally, it provides algorithms that use these new versions of existing failure detectors to solve distributed problems in unknown dynamic systems.

The main contributions of this thesis focus on failure detectors for unknown dynamic systems related to two distributed problems: k-set agreement and mutual exclusion. The first contribution defines a failure detector for k-set agreement that includes connectivity properties, while the second considers connectivity assumptions to be part of the model and defines a failure detector for mutual exclusion strictly in terms of the information it provides on failures.

A third contribution concerns an asynchronous reliable broadcast over an hypercube overlay.

A Failure Detector for k-Set Agreement in Unknown Dynamic Systems

The k-set agreement problem is a generalization of the consensus problem. Every process proposes a value and every correct process must eventually decide a value, such that at most k different values are decided, and every decided value is a proposed value. In static, known systems made of n processes, it has been proved that the ΠΣ x,y failure detector [START_REF] Mostéfaoui | Chasing the weakest failure detector for k-set agreement in message-passing systems[END_REF] is sufficient to solve k-set agreement in the general case of 1 ≤ k < n provided that k ≥ xy, while being the weakest failure detector for the cases of k = 1 [START_REF] Deepak | The Weakest Failure Detector for Solving Consensus[END_REF] and k = n -1 [START_REF] Delporte-Gallet | The weakest failure detector for message passing set-agreement[END_REF].

This thesis provides a new definition of ΠΣ x,y called ΠΣ ⊥,x,y [START_REF] Jeanneau | Solving kset agreement using failure detectors in unknown dynamic networks[END_REF]. This new failure detector includes connectivity properties to deal with the dynamics of the system, and uses a default return value ⊥ to deal with the lack of initial information in an unknown system. An algorithm implementing ΠΣ ⊥,x,y in unknown dynamic systems, relying on message pattern assumptions along with connectivity assumptions modeled using the Time-Varying Graph formalism [START_REF] Casteigts | Time-varying graphs and dynamic networks[END_REF], is presented. Finally, this thesis also provides an algorithm that solves the k-set agreement problem using ΠΣ ⊥,x,y , with k ≥ xy, thus proving that ΠΣ ⊥,x,y is sufficient to solve k-set agreement in unknown dynamic systems.

A Failure Detector for Mutual Exclusion in Unknown Dynamic Systems

Mutual exclusion is an important distributed problem that is notably used to protect a shared object from being concurrently accessed by multiple processes. In the mutual exclusion problem, processes attempt to access a critical section of their code in such a way that (1) no two processes can be in their critical section at the same time, and (2) whenever some correct process tries to enter its critical section, some correct process must later succeed at entering its critical section. In static, known systems, it has been proved that (T , Σ l ) is the weakest failure to solve mutual exclusion [START_REF] Delporte-Gallet | Mutual exclusion in asynchronous systems with failure detectors[END_REF][START_REF] Bhatt | Extracting quorum failure detectors[END_REF].

This thesis provides a new definition of (T , Σ l ) called T Σ lr [START_REF] Mauffret | The weakest failure detector to solve the mutual exclusion problem in an unknown dynamic environment[END_REF]. This new failure detector is capable of dealing with the lack of information in an unknown system, along with processes that leave the system and rejoin it later (this is modeled as crash/recovery failures). The dynamics of the communication graph are abstracted with the use of connectivity properties defined as part of the system model, and not the failure detector.

An algorithm solving mutual exclusion using T Σ lr is proposed, along with a reduction algorithm showing that any mutual exclusion algorithm can be transformed into T Σ lr , thus proving that it is the weakest failure detector to solve mutual exclusion in an unknown dynamic system model.

An Asynchronous Reliable Broadcast Algorithm over a Hypercube Topology

The reliable broadcast abstraction enables each process to reliably communicate information to every other process while preventing situations where only some processes receive the information. More formally, a reliable broadcast is a communication primitive allowing a process to send a message to all other processes, such that (1) if a correct process broadcasts a message, then it eventually delivers that message; (2) every correct process delivers a message at most once, and only if that message was previously broadcast by some process; and (3) every correct process delivers the same set of messages [START_REF] Hadzilacos | Fault-tolerant broadcasts and related problems. chapter Distributed systems[END_REF].

The VCube [START_REF] Elias | VCube: A provably scalable distributed diagnosis algorithm[END_REF] is a distributed overlay that organizes the processes in the system in a virtual hypercube-like topology and includes a diagnosis layer that provides failure detection. A reliable broadcast algorithm leveraging the VCube topology in order to ensure desirable logarithmic properties was provided in [START_REF] Luiz | An autonomic implementation of reliable broadcast based on dynamic spanning trees[END_REF], but it requires the system to be synchronous. This thesis introduces a reliable broadcast algorithm for asynchronous systems with a VCube [START_REF] Jeanneau | An autonomic hierarchical reliable broadcast protocol for asynchronous distributed systems with failure detector[END_REF], that also preserves logarithmic properties depending on the rate of false suspicions.

This work was done as part of the joint project CNRS -Fundação Araucária between the LIP6 (Delys team), the Universidade Federal do Paraná (UFPR) and the Universidade Estadual do Oeste do Paraná (UNIOESTE) in Brazil. Because this contribution does not concern dynamic systems, it will only be presented in the appendix of this thesis.

Publications

The following articles were published during this thesis.

Papers in International Conferences

Organization of the Manuscript

The rest of this thesis is organized as follows.

Chapter 2 first provides definitions for some common terms, models and problems used throughout this thesis, then summarizes the related work around failure detectors and dynamic systems.

Chapter 3 presents a failure detector for k-set agreement in unknown dynamic systems. It includes the definition of the ΠΣ ⊥,x,y failure detector, along with an algorithm implementing the failure detector in an unknown dynamic system and, finally, an algorithm solving k-set agreement using ΠΣ ⊥,x,y (provided that k ≤ xy).

Likewise, Chapter 4 presents a failure detector for mutual exclusion in unknown dynamic systems. It includes the definition of the T Σ lr failure detector, along with an algorithm that solves mutual exclusion using T Σ lr and a reduction algorithm proving that it is the weakest failure detector to solve mutual exclusion in unknown dynamic systems.

Chapter 5 concludes this thesis and proposes some future research directions. Finally, Appendix A presents an algorithm implementing an asynchronous reliable broadcast over the VCube overlay.

Chapter 2. A Background on Failure Detectors and Dynamic Systems

This thesis focuses on failure detectors for unknown dynamic systems. Thus, it covers two different fields of distributed computing: failure detectors and dynamic systems. In order to provide context, this chapter first summarizes some common definitions used in distributed systems (Section 2.1) along with the definitions of k-set agreement and fault-tolerant mutual exclusion (Section 2.2). Section 2.3 provides a history of failure detectors used to solve consensus, k-set agreement and fault-tolerant mutual exclusion. Finally, Section 2.4 lists different articles attempting to model dynamic distributed systems.

Distributed Systems

This section describes some existing distributed system models for static and known systems.

Processes

A distributed system is made up of a set of n processes, denoted Π = {p 1 , ..., p n }. Unless specified otherwise, each process knows its own identity, along with the value of n and the set Π.

Each process executes a sequence of steps described by its local algorithm. A step can be the execution of an instruction that only affects the internal state of the process, the sending or reception of a message, or a read/write operation on a shared variable. The set of all local algorithms is called the distributed algorithm.

A run is a sequence of steps executed by the processes while respecting the order of local operations as well as the causality of operations (each received message has been previously sent, each value read in a shared variable has been previously written).

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).

Failure Models

Distributed systems are prone to failures. A process that fails in a run is said to be faulty in that run. Conversely, a process that never fails during the run is said to be correct in that run. C denotes the set of all correct processes, while F is the set of all faulty processes.

The maximum number of faulty processes in a run is denoted f . While the most generic models consider f ≤ n -1, some models further restrict the number of failures.

The literature considers different types of failures.

In the crash failure model, a process that fails stops taking steps for the rest of the run.

In the crash/recovery failure model, a process that fails stops taking steps but may recover and resume taking steps later in the run. Processes might have lost part or all of their memory after recovering from a crash: it is therefore important to distinguish between volatile memory (which is lost after a crash) and stable memory (which is preserved even after a crash).

In the Byzantine failure model [START_REF] Lamport | The Byzantine Generals Problem[END_REF], a process that fails may exhibit arbitrary behaviour, and might even attempt to work against the algorithm.

Similarly to processes, communication links can be subject to failures: messages sent through them can be lost, altered or created. Most papers make the assumptions that links are reliable (there is no loss, alteration or creation of messages) or fair-lossy (if a same message is sent on a channel infinitely often, the recipient will receive it infinitely often).

Timing Models

Processes can be synchronous (there is a bound on the relative speed of processes) or asynchronous (there is no such bound).

Similarly, communication can be synchronous (there is a known bound on message transfer delays) or asynchronous (there is no such bound). Additionally, communication can be partially synchronous (the bound on message transfer delays is either unknown, or it only applies after an unknown time) [START_REF] Dwork | Consensus in the presence of partial synchrony[END_REF].

The system is said to be asynchronous (or time-free) if both processes and communication are asynchronous.

Even though model properties are often described with the use of a global clock, the processes themselves do not have access to such a global clock and each process has its own notion of time.

Notations

In this chapter, the AMP n,f [A] notation is used to designate the asynchronous message passing model comprised of n processes and prone to up to f failures, augmented with assumption A. Similarly, ASM n,f [A] designates the asynchronous shared memory model. A = ∅ means that there is no extra assumption. These notations were introduced by Raynal in [START_REF] Raynal | Communication and Agreement Abstractions for Fault-Tolerant Asynchronous Distributed Systems[END_REF].

Distributed Problems

Although many distributed problems have been studied in the literature, this thesis focuses on two of them: the k-set agreement problem and the mutual exclusion problem.

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 [START_REF] Michael | Impossibility of Distributed Consensus with One Faulty Process[END_REF] 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 [START_REF] Dwork | Consensus in the presence of partial synchrony[END_REF]. Another approach consists in abstracting the timing assumptions made (synchrony or partial synchrony) through the use of failure detectors [START_REF] Deepak | Unreliable Failure Detectors for Reliable Distributed Systems[END_REF]. Finally, one last approach consists in considering a weaker version of the problem: this is the solution chosen for the Paxos algorithm [START_REF] Lamport | The Part-Time Parliament[END_REF], where the termination property is not ensured.

A weaker problem than the consensus is the k-set agreement problem, introduced by Chaudhuri in [START_REF] Chaudhuri | More Choices Allow More Faults: Set Consensus Problems in Totally Asynchronous Systems[END_REF]. 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.

Only the agreement property differs from the consensus. Note that 1-set agreement is equivalent to consensus, and that the greater the value of k, the easier the problem. If the system is made of n processes, then the greatest value of k to be considered is n -1, since n-set agreement can be trivially solved without any communication.

A main feature of k-set agreement compared to consensus is that it can be solved in a system composed of k partitions.

In a generalization of the [START_REF] Michael | Impossibility of Distributed Consensus with One Faulty Process[END_REF] result, it was shown in [START_REF] Borowsky | Generalized FLP impossibility result for tresilient asynchronous computations[END_REF] that k-set agreement can only be solved in asynchronous systems if f < k, where f is the maximum number of process failures.

Fault-Tolerant Mutual Exclusion

The mutual exclusion problem was introduced by Dijkstra in [START_REF] Dijkstra | Solution of a problem in concurrent programming control[END_REF] and has since been widely studied in the literature [START_REF] Lamport | A new solution of dijkstra's concurrent programming problem[END_REF][START_REF] Lamport | The mutual exclusion problem: part I&II[END_REF][START_REF] Raynal | Algorithms for Mutual Exclusion[END_REF]. 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 [START_REF] Delporte-Gallet | Mutual exclusion in asynchronous systems with failure detectors[END_REF] 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 [START_REF] Chang | A fault tolerant algorithm for distributed mutual exclusion[END_REF], relying on the assumption that failures do not occur in adjacent connected processes.

Failure Detectors

The failure detector abstraction has been investigated as a way to circumvent the impossibility result of [START_REF] Michael | Impossibility of Distributed Consensus with One Faulty Process[END_REF] and solve consensus in asynchronous systems prone to crash failures [START_REF] Deepak | The Weakest Failure Detector for Solving Consensus[END_REF].

Failure detectors [START_REF] Deepak | Unreliable Failure Detectors for Reliable Distributed Systems[END_REF] are distributed oracles that provide processes with information on process failures, often either as a list of suspected process identities, or as a list of trusted ones. This information is unreliable in the sense that the failure detector may erroneously consider a correct process as faulty, or vice versa, but will attempt to correct these mistakes later. Each failure detector class ensures some properties on the reliability of the failure information. A failure detector is an abstraction of the system assumptions that are necessary and/or sufficient to solve a given problem.

A process p is said to suspect another process q if p has detected q as faulty. Conversely, p is said to trust q if p has not detected q as faulty.

In [START_REF] Deepak | Unreliable Failure Detectors for Reliable Distributed Systems[END_REF], Chandra and Toueg define failure detector classes using completeness and accuracy properties:

• Strong Completeness: Eventually, every process that crashes is suspected by every correct process.

• Weak Completeness: Eventually, every process that crashes is suspected by some correct process.

• Strong Accuracy: No process is suspected before it crashes.

• Weak Accuracy: Some correct process is never suspected.

The accuracy properties can be declined into the eventually strong accuracy and eventually weak accuracy, where the property only applies after some unknown time.

Using these properties, Chandra and Toueg defined eight classes of failure detectors: P, S, P, S, Q, W, Q and W.

The notation D p (t) is used to designate the output of failure detector D at time t on process p.

The Failure Detector Hierarchy

Failure detectors can be partially ordered based on their "power". A stronger failure detector can be used to solve more difficult problems.

A failure detector D 1 is said to be weaker than D 2 if there exists a distributed algorithm that can implement D 1 using the information on failures provided by D 2 . Intuitively, this means that the computing power provided to the system by D 2 is stronger than the computing power provided by D 1 . A failure detector that is sufficient to solve a given problem while being weaker than every other failure detector that can solve it, is said to be the weakest failure detector to solve that problem. It follows that the weakest failure detector to solve a problem can be implemented in any system in which the problem can be solved.

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 AMP n,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, [START_REF] Biely | Easy impossibility proofs for k-set agreement in message passing systems[END_REF] 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 [START_REF] Raynal | Failure detectors to solve asynchronous k-set agreement: a glimpse of recent results[END_REF] 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".

FD class

Article Section Property Failure pattern S was introduced by Chandra and Toueg in [START_REF] Deepak | Unreliable Failure Detectors for Reliable Distributed Systems[END_REF]. It provides processes with a list of processes suspected of being faulty, such that:

S, Ω [CHT96] 2.3.2.1 Weakest for consensus f < n/2 (Ω k , Σ k ) [BR09] 2.3.2.2 Insufficient for k-set agreement f ≤ n -1 S x [MR99] 2.3.2.3 Solves k-set agreement f < k + x -1 S x [MR99] 2.3.2.3 Solves k-set agreement See 2.3.2.3 Σ [DFG10] 2.3.2.4 Weakest for registers f ≤ n -1 (Ω, Σ) [DFG10] 2.3.2.4 Weakest for consensus f ≤ n -1 Σ k [BR09] 2.3.2.5 Necessary for k-set agreement f ≤ n -1 Π k (2009) [BR09] 2.3.2.5 Same power as (Ω k , Σ k ) f ≤ n -1 L [DFGT08] 2.3.2.6 Weakest for (n -1)-set agreement f ≤ n -1 L k [BRS09] 2.3.2.7 Solves k-set agreement with k ≥ n/2 f ≤ n -1 ΠΣ x,y [MRS12] 2.3.2.8 Solves k-set agreement, weaker than (Ω x , Σ y ) f ≤ n -1 Π k (2007) [CZCL07] 2.3.2.9 Solves k-set agreement, weaker than (Ω k , Σ) f ≤ n -1 Π s k [CZCL07] 2.3.2.9 Solves k-set agreement, weaker than Π k (2007) f ≤ n -1 ( S bl , Σ bl ) [FMR05] 2.3.2.10 Same power as (Ω, Σ) f ≤ n -1
• Strong completeness: ∀p ∈ F, ∃τ ∈ T , ∀t > τ, ∀q ∈ C : p ∈ S q (t) • Eventual weak accuracy: ∃l ∈ C, ∃τ ∈ T , ∀t > τ, ∀p ∈ C : l / ∈ S p (t)
Strong completeness means that eventually, all faulty processes are suspected by all correct processes. Eventual weak accuracy means that there is at least one correct process which is eventually not suspected by any correct process. The eventual leader detector Ω provides each process with a process identity such that the following property is ensured:

• Eventual leadership: ∃l ∈ C, ∃τ ∈ T , ∀p ∈ C, ∀t ≥ τ : Ω p (t) = l
Eventual leadership means that after a certain time τ , all processes will trust the same correct process. The detector eventually provides the processes with a correct leader, but there is no way to know τ .

Ω was proven in [START_REF] Deepak | The Weakest Failure Detector for Solving Consensus[END_REF] to be the weakest failure detector with which to enrich ASM n,n-1 [∅] in order to solve consensus. Since Attiya et al. proved in [START_REF] Attiya | Sharing Memory Robustly in Message-Passing Systems[END_REF] that read/write registers can be simulated in a message passing system if and only if f < n/2, it follows that Ω is also the weakest failure detector to solve consensus in

AMP n,f [f < n/2].
The Ω failure detector is equivalent to S, provided that the membership of the system is known [START_REF] Jiménez | Implementing unreliable failure detectors with unknown membership[END_REF].

The Ω k Eventual Leader Detector Family

Although Ω is minimal for the

case k = 1 in ASM n,n-1 [∅] and AMP n,f [f < n/2], it is too strong for k-set agreement with 1 < k ≤ n -1.
The eventual leader detector family Ω k was introduced in [Nei95] as a generalization of Ω aimed to solve k-set agreement. It provides processes with a set of process identities such that:

• Eventual leadership: ∃L ⊆ Π, |L| ≤ k, L ∩ C = ∅, ∃τ ∈ T , ∀p ∈ C, ∀t ≥ τ : Ω kp (t) = L
The eventual leadership property implies that every correct process will ultimately trust the same process group, in which there is at least one correct process. Note that Ω 1 is equivalent to Ω. In [START_REF] Raynal | In search of the holy grail: Looking for the weakest failure detector for wait-free set agreement[END_REF], the author conjectured that Ω k was the weakest failure detector to solve k-set agreement in the shared memory model, but this conjecture was disproved in [START_REF] Chen | Weakening failure detectors for k -set agreement via the partition approach[END_REF].

The S x and S x Limited Scope Accuracy Failure Detectors

Failure detectors with limited scope accuracy were introduced in [MR99], denoted S k and S k . Since the k parameter is unrelated to the k-set agreement problem, in this chapter they will be denoted S x and S x . They are defined relatively to the Strong failure detector S and the eventually Strong failure detector S, respectively. S x relies on the following properties:

• Strong completeness: ∀p ∈ F, ∃τ ∈ T , ∀t > τ, ∀q ∈ C : p ∈ S x,q (t) • x-Accuracy: ∃Q ⊆ Π, |Q| = x, Q ∩ C = ∅, ∃p ∈ Q ∩ C : ∀q ∈ Q, ∀t ∈ T : p / ∈ S x,q (t).
The strong completeness property is the same as the one of S and S: eventually, all faulty processes are suspected by all correct processes. The x-accuracy property means that there is one correct process that is not suspected by a set of x processes (including itself). S x ensures the strong completeness and the x-accuracy properties. S x ensures the strong completeness and eventually ensures the x-accuracy property.

[MR99] provides an algorithm extracting S from S x and S from S x , if f < x. It also presents an algorithm solving consensus with S x , provided that f < min(x, n/2).

Algorithms for k-set agreement with this family of failure detectors can be found in [MR00]: a first algorithm requires S x and f < k + x -1. Another algorithm makes use of S x and requires f < max(k, max 1≤α≤k (min(n -α n/(α + 1) , α + x -1))).

The Σ Quorum Detector

The quorum detector Σ, introduced in [DFG10] by Delporte-Gallet, Fauconnier and Guerraoui provides each process p i with a quorum of process identities Σ p i such that the following properties hold:

• Intersection: ∀t 1 , t 2 ∈ T , ∀p 1 , p 2 ∈ Π : Σ p 1 (t 1 ) ∩ Σ p 2 (t 2 ) = ∅ • Completeness: ∃τ ∈ T , ∀p ∈ C, ∀t ∈ T , t ≥ τ : Σ p (t) ⊆ C
Intersection ensures that all the quorums formed by any two process at any two distinct times intersect. Completeness guarantees that at some point in time, all the quorums will only contain correct processes. [START_REF] Delporte-Gallet | Tight failure detection bounds on atomic object implementations[END_REF] proves that Σ is the weakest failure detector to implement read/write registers in AMP n,n-1 [∅]. Such a result also implies that the pair (Ω, Σ) is the weakest failure detector to solve consensus in AMP n,n-1 [∅]. Contrarily to Ω (or S), it does not require a majority of correct processes. It is, however, too strong for k-set agreement with k > 1.

The Σ k Quorum Detector Family

The quorum detector family Σ k was introduced by Bonnet and Raynal in [START_REF] Bonnet | Looking for the Weakest Failure Detector for k-Set Agreement in Message-Passing Systems: Is Π k the End of the Road? In Stabilization, Safety, and Security[END_REF]. Similarly to Σ, it provides each process with a list of process identities such that the following properties are satisfied:

• Intersection: ∀t 1 , ..., t k+1 ∈ T , ∀p 1 , ..., p k+1 ∈ Π, ∃i, j : 1 ≤ i = j ≤ k + 1 : Σ kp i (t i ) ∩ Σ kp j (t j ) = ∅ • Completeness: ∃τ ∈ T , ∀p ∈ C, ∀t ∈ T , t ≥ τ : Σ kp (t) ⊆ C
The intersection property ensures that out of any k + 1 quorums formed on any processes at any time, at least two will intersect. The completeness ensures that eventually quorums contain only correct processes. Intuitively, Σ k prevents the network from partitioning into more than k independent subsets.

[BR09] also proved that Σ k is necessary for k-set agreement and introduced Π k (unrelated to the Π k of [START_REF] Chen | Weakening failure detectors for k -set agreement via the partition approach[END_REF]), a class of failure detectors proved to have the same computational power as (Ω k , Σ k ).

Given that (Ω, Σ) is the weakest failure detector to solve consensus in AMP n,n-1 [∅], (Ω k , Σ k ) was conjectured in [START_REF] Bonnet | Looking for the Weakest Failure Detector for k-Set Agreement in Message-Passing Systems: Is Π k the End of the Road? In Stabilization, Safety, and Security[END_REF] to be the weakest failure detector to solve k-set agreement in the message passing model, but it was proved that (Ω k , Σ k ) is not sufficient to solve it with 1 < k < n-1 [START_REF] Bouzid | anti-Ω x × Σ z )-Based k-Set Agreement Algorithms[END_REF][START_REF] Biely | Easy impossibility proofs for k-set agreement in message passing systems[END_REF]. More specifically, [START_REF] Bouzid | anti-Ω x × Σ z )-Based k-Set Agreement Algorithms[END_REF] proves that (Ω x , Σ z ) cannot solve k-set agreement if k ≥ xz. Later, [START_REF] Mostéfaoui | Chasing the weakest failure detector for k-set agreement in message-passing systems[END_REF] also proved that Ω k is not necessary for k-set with 1 < k < n -1.

The L Loneliness Detector

As a first step to find tight bounds on generic k-set resolvability for 1 ≤ k ≤ n -1, researchers started by working on the other extreme case: (n -1)-set agreement, also called set agreement. Although Σ is not sufficient to solve consensus and was conjectured by Zielinski in [START_REF] Zielinski | Anti-omega: the weakest failure detector for set agreement[END_REF] to be the weakest failure detector to solve set-agreement, it was proved in [START_REF] Delporte-Gallet | Sharing is harder than agreeing[END_REF] that it is too strong for set agreement in message passing systems. Therefore, a weaker detector than Σ is required.

The loneliness detector L was first introduced in [START_REF] Delporte-Gallet | The weakest failure detector for message passing set-agreement[END_REF]. It is a very weak failure detector, as it only provides processes with the information that they are alone. Intuitively, L detects the situation where a process is the only remaining correct process in the system. More formally, L provides each process with a boolean variable such that:

• Stability: ∃p ∈ Π, ∀t ∈ T : L p (t) = f alse • Loneliness: ∀p ∈ Π, (C = {p}) ⇒ ∃τ ∈ T , ∀t ∈ T , t ≥ τ : L p (t) = true
The stability property ensures that there is at least one process that never considers itself alone. The loneliness property guarantees that if a correct process is alone, it will eventually know that it is alone. [START_REF] Delporte-Gallet | The weakest failure detector for message passing set-agreement[END_REF] proved that L is the weakest failure detector to solve set agreement in [START_REF] Biely | The generalized loneliness detector and weak system models for k-set agreement[END_REF] as a generalization of the loneliness detector L (L is L n-1 ) to detect (n -k)-loneliness. Similarly to L, it outputs to each process a boolean value such that the following properties hold:

AMP n,n-1 [∅]. 2.3.2.7 The L k Generalized Loneliness Detector L k is introduced in [BRS09,
• Stability: ∃Π 0 ⊆ Π, |Π 0 | = n -k, ∀p ∈ Π 0 , ∀t ∈ T : L kp (t) = f alse • Loneliness: (f ≥ k) ⇒ ∃τ ∈ T , ∃p ∈ C, ∀t ≥ τ : L kp (t) = true
The stability property imposes that there is a set of n -k processes that always know that they are not alone. The loneliness property ensures that if there are fewer than n-k correct processes, then at least one correct process returns true.

L k solves k-set agreement but is not minimal. As shown in [START_REF] Mostéfaoui | Relations linking failure detectors associated with k-set agreement in message-passing systems[END_REF], L k is only realistic (meaning it can be implemented in a synchronous system with f = n -1) if and only if k ≥ n/2.

The same paper introduced L k , the eventual loneliness detector, and showed that it is equivalent to Ω k .

The ΠΣ x,y Failure Detector

This failure detector was introduced by Mostéfaoui, Raynal and Stainer in [START_REF] Mostéfaoui | Chasing the weakest failure detector for k-set agreement in message-passing systems[END_REF] and defined incrementally. The paper starts by defining the intermediary failure detector ΠΣ x , which provides each process with a quorum following the properties of Σ k , plus a variable leader providing the following additional property:

• Eventual partial leadership: ∃l ∈ C, ∀p ∈ C : (∀τ ∈ T , ∃τ p , τ l ≥ τ : ΠΣ x,p (τ p ) ∩ ΠΣ x,l (τ l ) = ∅) ⇒ (∃τ ∈ T , ∀t ≥ τ : leader p (t) = l)
The eventual partial leadership property means that there is a process l such that, for every process p whose quorum intersects infinitely often with l's quorum, eventually l is forever the leader of p.

ΠΣ x,y can be seen as a set of y detectors of class ΠΣ x of which only one has to follow the eventual leadership property. It is weaker than (Σ x , Ω y ) and solves k-set agreement in the message passing model for k ≥ xy (which is a necessity proved in [START_REF] Bouzid | anti-Ω x × Σ z )-Based k-Set Agreement Algorithms[END_REF]).

The authors in [START_REF] Mostéfaoui | Chasing the weakest failure detector for k-set agreement in message-passing systems[END_REF] provide an intuitive description of ΠΣ x,y . ΠΣ x,1 (1) prevents the system from partitioning into more than x partitions with the properties of Σ x and (2) guarantees that the processes of at least one of these subsets agree on a common leader. ΠΣ x,y can be seen as y independent instances of ΠΣ x in which the guarantee (2) has to be hold in only one of these instances.

2.3.2.9

The Π k and Π s k Partitioned Failure Detectors

The partitioned failure detectors are a set of failure detectors introduced in [START_REF] Chen | Weakening failure detectors for k -set agreement via the partition approach[END_REF]. 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 AMP n,f [Π s k ] and inspired from the Paxos algorithm of [START_REF] Lamport | The Part-Time Parliament[END_REF] is provided in [START_REF] Chen | Weakening failure detectors for k -set agreement via the partition approach[END_REF].

2.3.2.10

The S bl and Σ bl Bounded Lifetime Failure Detectors

The bounded lifetime failure detectors were introduced by Friedman et al. in [START_REF] Friedman | Asynchronous bounded lifetime failure detectors[END_REF]. These failure detectors provide the upper layer application with a f d_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.

S bl 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 t e such that from t until t e , there is a process that is alive at t e and that is not suspected by all the processes that have not crashed at time t e .

t e is the time at which f d_end() is invoked. After t e , the accuracy property no longer applies. In the article, the authors show that an existing S-based consensus algorithm can be adapted to use S bl . The algorithm is modified so that every process invokes f d_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 f d_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 f d_end() at the end of every read or write operation. ΠΩ k is the partitioned variant of Ω k . The article provides an algorithm solving k-set agreement in ASM n,n-1 [ΠΩ k ] and proves that it is weaker than Ω k , thus disproving the conjecture in [START_REF] Raynal | In search of the holy grail: Looking for the weakest failure detector for wait-free set agreement[END_REF] that Ω k is the weakest failure detector to solve k-set agreement in shared memory systems.

ΠΩΥ k is a partitioned failure detector combining features of ΠΩ k and Υ, while being weaker than both of them. It solves (n -1)-set agreement in the shared memory model.

The Ω Anti-Omega Failure Detector

Inspired by the Υ detector introduced in [GHK + 07], Zielinski introduced in [START_REF] Zielinski | Anti-omega: the weakest failure detector for set agreement[END_REF] the Ω failure detector that solves the set agreement problem in shared memory systems.

Υ provides each process with a non-empty set of process identities which is eventually ensured to be the same for every process and different from C.

Ω is strictly weaker than Υ and provides each process with a process identity, with only the guarantee that there is one correct process whose id will be output a finite number of times. [START_REF] Zielinski | Anti-omega: the weakest failure detector for set agreement[END_REF] proves that Ω is the weakest failure detector to solve set agreement in ASM n,n-1 [∅].

2.3.3.3

The Ω k Failure Detector Ω k is a generalization of Ω such that Ω is Ω n-1 and Ω is Ω 1 . It was introduced in [Ray07] and conjectured to be the weakest failure detector for k-set agreement in the shared memory model. This conjecture was later proved to be true in [START_REF] Gafni | The weakest failure detector for solving k-set agreement[END_REF]. Ω k provides each process with a list of process identities such that:

• Validity: ∀p ∈ Π, ∀t ∈ T , Ω kp (t) ⊆ Π : |Ω kp (t)| = k • Weak eventual leadership: ∃τ ∈ T , ∃l ∈ C, ∀t ∈ T , t ≥ τ, ∀p ∈ Π : l ∈ Ω kp (t)
Weak eventual leadership implies that there is a correct process l that will ultimately be in the set output by Ω k for every process. This characteristic makes Ω k slightly different from Ω k .

Failure Detectors for Mutual Exclusion

This section presents the failure detectors used to solve the FTME problem in message passing systems.

The Trusting Failure Detector

In [START_REF] Delporte-Gallet | Mutual exclusion in asynchronous systems with failure detectors[END_REF], Delporte-Gallet et al. introduced the trusting failure detector T and proved that it is the weakest failure detector with which to enrich AMP n,f [f < n/2] to solve FTME. T provides each process p with a list of trusted processes. The following properties must be verified.

• Eventually strong accuracy: Every correct process p is eventually trusted forever by every correct process.

• Strong completeness: Every faulty process p is eventually suspected forever by every correct process.

• Trusting accuracy: For any processes p and q, if there exist times t and t > t such that p trusts q at time t and p suspects q at time t , then q is faulty.

The Σ l Failure Detector

Bhatt et al. introduce in [START_REF] Bhatt | Extracting quorum failure detectors[END_REF] the Σ l quorum failure detector. Σ l is a variant of the Σ quorum failure detector adapted for the FTME problem. It provides each process p with a quorum of process identities. Σ l verifies the following properties.

• Strong completeness: Every faulty process p is eventually suspected forever by every correct process.

• Live pairs intersection: If two processes p and q are both alive at time t, then for any couple of time instants t 1 ≤ t and t 2 ≤ t, Σ l p (t 1 ) ∩ Σ l q (t 2 ) = ∅.

Bhatt et al. show in [BCJ09

] that T and Σ l used together, denoted (T , Σ l ), constitute the weakest failure detector with which to enrich AMP n,n-1 [∅] to solve FTME.

Dynamic Networks

All the articles discussed in the previous sections made the assumption that the distributed system is composed of a finite set of processes, that the membership of the system only changes due to failures, and that the communication graph is static during the run. These assumptions do not apply to dynamic systems.

There is no consensual formal definition of a dynamic network. Some papers define a dynamic system as a distributed system in which the communication graph evolves over time, while others define it as a model where processes can join and leave the system during a run. Some articles mix both of those proposals in the same model. A few articles have attempted to regroup other authors' proposals in order to formalize common models [BF03, Agu04, KLO10, CFQS12, BRS12].

Increasing and Decreasing Systems with a Static Communication Graph

In increasing and decreasing systems, processes can join or leave the system during the run, but the communication graph is static over time. This section regroups a number of papers which consider such systems.

Infinitely Many Processes.

In [START_REF] Kawazoe | A pleasant stroll through the land of infinitely many creatures[END_REF], Aguilera defines models where processes can join or leave the system during the run:

• In the finite arrival model, the system has infinitely many processes, but each run has only finitely many. As a result, algorithms do not know the bound on the number of processes.

• In the infinite arrival model, the system has infinitely many processes and each run can have infinitely many processes, but in each finite time interval, only finitely many processes take steps.

• In the infinite concurrency model, the system has infinitely many processes, each run can have infinitely many processes and each finite time interval can have infinitely many processes.

A number of papers have explored these models [MRT + 05, CRTW07, BBRT07, AGSS13], sometimes combining them with a communication model addressing graph dynamics (e.g. TVG, see section 2.4.5).

Mostéfaoui et al. make use in [MRT

+ 05] of the query-response mechanism, in which processes broadcast a query to their neighbours and wait for a certain number of responses. Each process waits for α responses to its query, where α is the number of processes eventually guaranteed to respond. With this mechanism, processes are not required to know the number of processes in the system, which allows for a finite arrival model. The paper provides a Ω algorithm for an asynchronous finite arrival model using query-response.

[CRTW07] uses a model composed of two sets of nodes: fixed support stations forming a static complete graph, asynchronous but entirely known, and mobile hosts which follow the finite arrival model and attach themselves to support stations. Using this model, the paper provides an algorithm for Ω using message pattern assumptions.

In [START_REF] Abboud | Agreement Without Knowing Everybody: A First Step to Dynamicity[END_REF], Abboud et al. consider that processes cannot crash, but can join the system during the run and those that did not join the system yet at a given time are considered faulty at that time. The paper shows that consensus cannot be solved in this model but can be solved provided that the model is enriched with Σ. The authors remark that Σ can be implemented with an estimation m of the number of processes such that n/2 + 1 ≤ m ≤ n.

2.4.1.2

The Dynamic Eventual Leader Failure Detector ∆Ω.

[LRAC12] introduces ∆Ω as an eventual leader definition adapted for dynamic networks. It is defined by the following properties, where Π(t) is the system membership at time t ∈ T and join i is the time at which process p i joined the system:

• Eventual Leadership in Non-Increasing systems:

[∃τ ∈ T : ∀τ 1 , τ 2 ≥ τ : (τ 1 ≥ τ 2 ) ⇒ (Π(τ 1 ) ⊆ Π(τ 2 ))] ⇒ [∃p l ∈ τ ≥τ Π(τ ) : ∃τ 1 ≥ τ : ∀τ 2 ≥ τ 1 : ∀p i ∈ Π(τ 2 ) : Ω i (τ 2 ) = l]
• Eventual Leadership in Non-Decreasing systems:

[∃τ ∈ T : ∀τ 1 , τ 2 ≥ τ : (τ 1 ≤ τ 2 ) ⇒ (Π(τ 1 ) ⊆ Π(τ 2 ))] ⇒ [∃τ 1 ≥ τ, ∃p l ∈ Π(τ 1 ) : [∀τ 2 ≥ τ 1 : ∀p i ∈ Π(τ ) : Ω i (τ 2 ) = l]∧ [∀τ ≥ τ : (p i ∈ Π(τ )\Π(τ )) ⇒ (∃τ 0 ≥ join i : ∀τ ≥ τ 0 : Ω i (τ ) = l)]]
Intuitively, the first property ensures that if after some time no new process joins the system (finite arrival), then a leader is eventually elected. The second property ensures that if after some time no process leaves the system, then a leader is eventually elected and new processes eventually adopt it.

The paper provides two algorithms implementing ∆Ω: the first one assumes that processes synchronize their local clocks with others when first entering the system, the second one assumes reliable channels. An extension of ∆Ω accounting for an evolving communication graph is presented in [START_REF] Gómez-Calzado | Faulttolerant leader election in mobile dynamic distributed systems[END_REF]. It uses exclusively assumptions on "good periods", and includes a survey and comparison of different models and algorithms, mostly with partial synchrony assumptions.

The Dynamic Graph Model

Kuhn, Lynch and Oshman present in [START_REF] Kuhn | Distributed computation in dynamic networks[END_REF] the Dynamic Graph Model that considers a fixed set of nodes although the authors remark that this is not a fundamental characteristic of the model, which could be extended for a dynamic set of participants. Algorithms in this model work in synchronous rounds (i.e., communication links are synchronous) and make use of broadcasts as a communication primitive. Nodes are assumed reliable (crash failures are not considered). The dynamics of the system lie in the communication graph which changes in each round. Connectivity assumptions are expressed around the concept of T -interval connectivity, which imposes the existence of a stable connected subgraph for every T consecutive rounds. The stable subgraph is not known to the nodes in advance. In every round the active communication links are chosen by an adversary which abstracts above assumptions. Other than the model itself, the paper presents solutions to several distributed problems such as counting and k-token dissemination, but not consensus.

In [START_REF] Kuhn | Coordinated consensus in dynamic networks[END_REF], the authors extend the model and propose algorithms for consensus, simultaneous consensus (all the nodes decide in the same round) and ∆-coordinated consensus (all the correct processes decide within ∆ rounds of each other).

[SS14] studies the problem of k-set agreement in the Dynamic Graph Model of [START_REF] Kuhn | Distributed computation in dynamic networks[END_REF] while considering p -partitioned networks (at each round, the communication graph consists of at most p connected components). The paper proves the necessity of knowing at least an upper bound on the number of processes if the graph is at least 2-partitioned, and provides an algorithm solving k-set agreement under that condition.

Directed Dynamic Networks

In [START_REF] Biely | Agreement in directed dynamic networks[END_REF], 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 vertexstable 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 [START_REF] Coulouma | A characterization of dynamic networks where consensus is solvable[END_REF] 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 [START_REF] Biely | Agreement in directed dynamic networks[END_REF] with similar assumptions on vertex-stable root components. The article also gives minimality results regarding temporal stability and information flow.

Evolving Graphs

The Evolving Graphs model was introduced by Bhadra and Ferreira in [START_REF] Bhadra | Complexity of connected components in evolving graphs and the computation of multicast trees in dynamic networks[END_REF]. An evolving graph is defined as

a system G = (G, S G ) where G(V, E) is a digraph and S G = G 0 , G 1 , ...G τ , τ ∈ T is an ordered sequence of its subgraphs G i (V i , E i ).
This formalism enables nodes to join or leave the system, as well as a dynamic communication graph.

If P is a path in G, then let F (P ) be its source and L(P ) its destination. A path in G is a sequence P G (u, v) = P t 1 , P t 2 , ..., p tx with t 1 < t 2 < ... < t x , such that P t i is a defined path in G t i and F (P t 1 ) = u, L(P tx ) = v, and ∀i < x :

L(P t i ) = F (P t i+1 ).
This definition is extended in [START_REF] Bhadra | Complexity of connected components in evolving graphs and the computation of multicast trees in dynamic networks[END_REF][START_REF] Bui-Xuan | Computing shortest, fastest, and foremost journeys in dynamic networks[END_REF] with the concept of journey. Let ζ(e, t) be the transfer delay of edge e at time t. A journey is similar to a path in G, except that it accounts for link traversal times: a path P G is a journey only if the message transfer delays between nodes ensures the traversal from u to v. More formally, a journey is a sequence of couples J = {(e 1 , t 1 ), ..., (e k , t k )} such that {e 1 , ..., e k } is a walk in G and

∀1 ≤ i < k, e i ∈ E t i ∧ t i+1 ≥ t i + ζ(e i , t i ). t 1 is denoted departure(J ) and t k + ζ(e k , t k ) is denoted arrival(J ).
Intuitively, a journey is a path over time. As such, it has both a topological length (the length of the path in G) and a temporal length (arrival(J ) -departure(J )).

[BFJ03] also analyze the problem of least cost journeys, for different metrics:

• Foremost journey: the journey which arrives at the earliest possible time;

• Shortest journey: the journey with the the minimum topological length;

• Fastest journey: the journey with the minimum temporal length.

[CCF11] combines evolving graphs with the graph relabelings of [START_REF] Litovsky | Graph Relabelling Systems and Distributed Algorithms[END_REF] in order to obtain a dynamic model which can abstract the communication models such as the message passing model or the shared memory model.

[FGA11] provides necessary and sufficient conditions for mutual exclusion and k-mutual exclusion in evolving graphs.

Time-Varying Graphs (TVG)

Time-Varying Graphs are a communication model introduced by Casteigts et al. in [START_REF] Casteigts | Time-varying graphs and dynamic networks[END_REF] with the goal of providing a very generic and modular model for dynamic networks, such that previous models can be simulated in it. Using definitions from the Evolving Graphs of [START_REF] Bhadra | Complexity of connected components in evolving graphs and the computation of multicast trees in dynamic networks[END_REF], it defines a dynamic system as a TVG G = (V, E, T , ρ, ζ) where:

• V = Π is the set of nodes in the system;

• E ⊆ V × V is the set of edges (communication links); • T = N is a time span; • ρ : E × T → {0, 1}
is the edge presence function, indicating whether an edge is active or not at a given time;

• ζ : E × T → T is the latency function, indicating the time taken by a message to cross a given edge if starting at a given time.

TVGs are used to model the communication graph of dynamic systems, including those presented in Sections 2.4.2 and 2.4.3. Additionally, the model offers optional parameters:

• ψ : V × T → {0, 1}
is the node presence f unction, indicating whether or not a node is present in the system at a given time;

• ϕ : V × T → T is the node latency f unction, indicating the local processing time on a given node at a given time.

ψ allows the representation of processes joining and leaving (or failing) the system, and is necessary for the models defined in Sections 2.4.1 and 2.4.4.

The underlying graph G = (V, E) is the footprint of G, indicating which nodes have a relation at some time in T . Most applications require G to be connected.

Journeys

The definition of a journey in [START_REF] Bhadra | Complexity of connected components in evolving graphs and the computation of multicast trees in dynamic networks[END_REF] is adapted for the TVG model as follows: a journey is a sequence of couples J = {(e 1 , t 1 ), ..., (e k , t k )} such that {e 1 , ..., e k } is a walk in G and

∀1 ≤ i < k, ρ(e i , t i ) = 1 ∧ t i+1 ≥ t i + ζ(e i , t i ). If a journey exists between two nodes u and v, it is said that u can reach v, which is denoted u v.
The set of all journeys from node u to node v is denoted J * u,v . Additionally, a direct journey is a journey such that ∀1 ≤ i < k, ρ(e i+1 , t i + ζ(e i , t i )) = 1, meaning that it does not include any waiting time.

In [CFG + 15], the expressivity of different variants of TVG is studied, in particular in regard to direct or indirect journeys.

TVG Classes

Various TVG connectivity assumptions are classified according to the level of graph connectivity they provide. A total of thirteen TVG classes are defined. Here are the definitions of some of the most important classes:

• Class 1 ∃u ∈ V : ∀v ∈ V, u v.
There is a node that can reach all others.

• Class 2 ∃u ∈ V : ∀v ∈ V, v u.
There is a node that can be reached by all others.

• Class 3 (Connectivity over time): ∀u, v ∈ V, u v. Every node can reach all others.

• Class 4 (Round connectivity): ∀u, v ∈ V, ∃J 1 ∈ J * (u,v) , ∃J 2 ∈ J * (v,u) : arrival(J 1 ) ≤ departure(J 2 ).
Every node can reach all others and be reached back afterwards.

• Class 5 (Recurrent connectivity): ∀u, v ∈ V, ∀t ∈ T , ∃J ∈ J * (u,v) : departure(J ) > t. Every node can reach all others infinitely often.

Timely Journeys

[GCLL15] adds to the TVG notions of ∆-journey, β-journey and (α, β)-journey. With ∆ ∈ T, J is a ∆-journey at time t if and only if J is a journey and t+arrival(J )-departure(J ) ≥ ∆. A β-edge is an edge such that latency is bounded by ζ max and the edge is active for at least β time, a β-journey at time t is a ∆-journey such that:

• ζ max < β ≥ ∆. • ∀i ∈ [0, k), e i is a β-edge.
• ∀i ∈ [0, k), t i+1 ≥ t i + β (the times when edges are activated and their corresponding latencies allow a bounded sequential traversal).

A (α, β)-journey is a β-journey such that:

• The appearance of e 1 is bounded by t 1 ≤ t + α.

• ∀i ∈ [1, k), t i+1 ≤ t i + ζ(e i , t i ) + α (the
appearances of the subsequent edges are also bounded by α).

These new definitions allow for the usage of partial synchrony assumptions in a TVG.

Unknown Asynchronous Dynamic Networks

This section regroups papers considering an asynchronous dynamic network, in the sense of an evolving communication graph, with unknown membership, meaning that even if n is finite, processes are not aware of its value and the identity of the participants.

[SAB + 08] proposes a query-response-based implementation of failure detector S in a model where f is known from processes, along with the minimal cardinality d of the neighbourhood of any node in the system. It does not use synchrony assumptions and requires behavioural properties instead:

• Membership Property: Let range i be the set of the neighbours of process p i in the underlying static graph and K t i be the set of processes that received a query from p i at time t ∈ T . p i satisfies the property if ∃t ≥ 0 ∈ T :

|K t i | > f + 1.
• Responsiveness Property: Let rec_f rom t j the set of processes from which p j has received responses from its query message that terminated at or before t. Process p i verifies the property if ∃u ∈ T : ∀t > u, ∀p j ∈ range i , p i ∈ rec_f rom t j .

[AST + 10] introduces and implements the perfect partition participant detector PD which detects the nodes participating in stable partitions in a unknown directed dynamic network.

In [START_REF] Friedman | Evaluating failure detection in mobile ad-hoc networks[END_REF], Friedman and Tcharny propose a failure detection protocol that probabilistically ensures completeness and accuracy properties in a mobile ad-hoc network. Each process can only communicate with the processes that are currently in its wireless range. The failure detection delay and the number of false suspicions depend on the network connectivity.

A model for unknown dynamic networks suited for implementations of failure detectors is presented in [START_REF] Greve | What model and what conditions to implement unreliable failure detectors in dynamic networks?[END_REF][START_REF] Greve | A failure detector for wireless networks with unknown membership[END_REF]. It combines the f inite arrival model of [START_REF] Kawazoe | A pleasant stroll through the land of infinitely many creatures[END_REF] with the TVG of [START_REF] Casteigts | Time-varying graphs and dynamic networks[END_REF] (class 5, recurrent connectivity), and introduces the eventually strong failure detector with unknown membership S M . If Known is the set of processes known by any other process at any point in time, Stable is the set of processes who never crash and Faulty is the set of faulty processes, then S M is defined by the following properties:

• Strong completeness: ∃t ∈ T , ∀t ≥ t, ∀p i ∈ Known ∩ Faulty ⇒ ∀p j ∈ Known ∩ Stable, p i ∈ S M p j (t)
• Eventual weak accuracy:

∃t ∈ T , ∀t ≥ t, ∃p i ∈ Known ∩ Stable ⇒ ∀p j ∈ Known ∩ Stable, p i / ∈ S M p j (t)
The properties correspond to the original properties of S, but only consider processes in the Known set. [START_REF] Greve | Eventually Strong Failure Detector with Unknown Membership[END_REF] presents an implementation of S M in the model of [START_REF] Greve | What model and what conditions to implement unreliable failure detectors in dynamic networks?[END_REF] using a query-response mechanism along with message pattern assumptions. It relies on the following properties:

• Stable Termination Property (SatP): Let p i be a node which issues a query. Thus, ∃p j ∈ Stable, p j = p i , which receives that query.

• Stable Responsiveness Property (SRP): Let X t j be the set of processes from which p j has received responses to its last query sent before t. stable t (p i ) ⇔ ∀t > t, ψ(p i , t ) = 1.

SRP t (p i ) def = stable t (p i ) ∧ ∀p j ∈ Π, (∃e i,j , ∃t ≥ t, ρ(e i,j , t ) = 1) ⇒ ∀t ≥ t + ζ(e i,j , t ), p i ∈ X t j .
SatP guarantees that every query is received by at least one stable process. SRP ensures that eventually, all the neighbors of one stable process p i will receive its response to every one of their query among the α i first responses.

[AGSS13] presents an algorithm for Ω in the same model. It uses a similar query-response mechanism and depends on the SatP and SRP properties, along with a TVG of class 5 (recurrent connectivity).

An algorithm for S M in the model of [START_REF] Greve | What model and what conditions to implement unreliable failure detectors in dynamic networks?[END_REF] tolerating Byzantine failures is given in [START_REF] Greve | A timefree byzantine failure detector for dynamic networks[END_REF].

In [START_REF] Taheri | Byzantine consensus for unknown dynamic networks[END_REF], Taheri and Izadi propose a protocol solving Byzantine consensus in an asynchronous dynamic system, using the necessary assumption that no more than n-1 3 processes are faulty. Benchi et al. provided in [START_REF] Benchi | Solving consensus in opportunistic networks[END_REF] an algorithm for consensus in asynchronous opportunistic networks with assumptions on the failure pattern.

[RAS15] introduces the initial knowledge-free quorum failure detector Σ ⊥ as a redefinition of Σ suited to unknown networks, where the intersection property cannot possibly be fulfilled from the beginning of the run. The quorums returned by Σ ⊥ can also contain the special value ⊥, which is used as a marker to indicate that the minimum knowledge about process identities has not been reached yet and, therefore, the intersection property is not expected to hold yet. Σ ⊥ is defined by the following properties:

• ⊥-Limited intersection property:

∀t 1 , t 2 ∈ T , ∀p 1 , p 2 , ∈ Π, Σ ⊥p 1 (t 1 ) = ⊥, Σ ⊥p 2 (t 2 ) = ⊥ : Σ ⊥p 1 (t 1 ) ∩ Σ ⊥p 2 (t 2 ) = ∅ • ⊥-Extended completeness property: ∃τ ∈ T , ∀p ∈ C, ∀t ∈ T , t ≥ τ : Σ ⊥p (t) = ⊥ ∧ Σ ⊥p (t) ⊆ C
Compared to the traditional properties of Σ, the intersection property only checks the intersection of non-⊥ quorums, and the completeness property ensures that eventually, ⊥ is not returned anymore. The paper also gives an implementation of Σ ⊥ using message pattern assumptions similar to the SRP property, but regarding the distant communications inside a set of processes instead of the neighborhood of a single process.

Summary of Failure Detector Results in Unknown and/or Dynamic Systems

Table 2.3 summarizes the article presented in this chapter that studied failure detectors in unknown and/or dynamic systems. For each article, the table also specifies if the model used considers a dynamic system membership, a dynamic communication graph, and whether the system is unknown or not.

Conclusion

This chapter presented the failure detector results in the literature around the k-set agreement and FTME problems. The ΠΣ x,y failure detector is sufficient to solve k-set agreement problem in static and known message passing systems, provided that k ≤ xy. Under this condition, it is the weakest failure detector to solve consensus and set agreement, and is weaker than other failure detectors for the cases of 2 ≤ k < n -1. Additionally, the (T , Σ l ) failure detector of [START_REF] Delporte-Gallet | Mutual exclusion in asynchronous systems with failure detectors[END_REF][START_REF] Bhatt | Extracting quorum failure detectors[END_REF] is the weakest failure detector to solve FTME in static and known message passing systems.

FD class

Many dynamic system models have been proposed, but few failure detectors have been studied in such models, as seen in Table 2.3. In particular, the results around ΠΣ x,y and (T , Σ l ) have not been extended to dynamic systems: this is, therefore, the focus of this thesis. This chapter focuses on the k-set agreement problem, which is a generalization of the consensus problem such that 1-set agreement is consensus. In the k-set agreement problem, each process proposes a value, and some processes eventually decide a value while respecting the properties Chapter 3. A Failure Detector for k-Set Agreement in Unknown Dynamic Systems of validity (a decided value is a proposed value), termination (every correct process eventually decides a value) and agreement (at most k values are decided).

As described in Section 2.4, protocols solving consensus or k-set agreement have been proposed for dynamic systems, but they assume synchronous communications (as in [BRS12, BRS + 18, KMO11, SS14]) or make strong assumptions on the number of process failures [START_REF] Benchi | Solving consensus in opportunistic networks[END_REF].

The ΠΣ x,y failure detector (presented in Section 2.3.2.8) was introduced in [MRS12] and is sufficient to solve k-set agreement in static networks (if and only if k ≥ xy) while being weaker than other known failure detectors which solve the same problem. However, this failure detector relies on information about the set of participants which is not available in unknown networks. Additionally, traditional failure detectors rely on a full connectivity of the network graph, which is not available in a dynamic network.

In this chapter, the definition of ΠΣ x,y is extended in order to obtain the ΠΣ ⊥,x,y failure detector, which is capable of solving k-set agreement in unknown dynamic systems, and provide implementations of this new detector. Additionally, this chapter provides an adaptation of the k-set agreement algorithm of [START_REF] Bouzid | anti-Ω x × Σ z )-Based k-Set Agreement Algorithms[END_REF][START_REF] Mostéfaoui | Chasing the weakest failure detector for k-set agreement in message-passing systems[END_REF] to solve k-set agreement using ΠΣ ⊥,x,y .

The model assumptions proposed to implement ΠΣ ⊥,x,y are generic and expressed in terms of message pattern, which allows the model to be applied to a range of systems. Concrete examples of partial synchrony and failure pattern properties which are sufficient to ensure the more generic message pattern assumptions are also presented.

The system is modeled using the formalism of the Time-Varying Graph (TVG), as defined in [START_REF] Casteigts | Time-varying graphs and dynamic networks[END_REF] (see Section 2.4.5).

This chapter thus brings the following main contributions:

1. The definition of the ΠΣ ⊥,x,y failure detector as an adaptation of ΠΣ x,y to solve k-set agreement in unknown dynamic systems (Section 3.2).

2. An algorithm implementing ΠΣ ⊥,x,y in unknown dynamic systems, with connectivity and message pattern assumptions (Section 3.4).

3. An algorithm solving k-set agreement in unknown dynamic systems enriched with ΠΣ ⊥,x,y (Section 3.5).

System Model

Process Model

A finite set of n processes Π = {p 1 , ...p n } participate in the system. The processes are synchronous (there is a bound on the relative speed of processes) and uniquely identified, although initially they are only aware of their own identities. Processes are not required to know the value of n.

A run is a sequence of steps executed by the processes while respecting the causality of operations (each received message has been previously sent). Processes can join and leave the system during the run (Π is the set of all processes that participate in the system at some point in time). Processes may also crash, and no difference is made between a process that crashes permanently and a process that leaves the system permanently: in both cases the process is considered faulty in that run. A process that is not faulty is called correct. Note that this definition of faulty and correct processes is not exactly the traditional one. Indeed, correct processes can crash or leave the system, as long as they recover or come back later. Only processes that crash or leave permanently are considered faulty.

Correct processes can leave the system and come back infinitely often, but they can only crash and recover a finite number of times. The critical difference is that a process that leaves the system keeps its memory intact, whereas a crashed process does not.

The set of all correct processes is called C. There is a bound f < n on the number of faulty processes in a run.

Communication Model

Processes communicate by sending and receiving messages. Communications are asynchronous: there is no bound on message transfer delays. Therefore, even though processes are synchronous, they do not cooperate in a synchronous way.

Time-Varying Graphs

The system is dynamic, which means that nodes and communication links can appear or disappear during the run: therefore, the communication graph will change over time. The usual notion of path in the graph is not sufficient to define reachability in such a dynamic graph. To solve this issue, in this chapter, the Time-Varying Graph (TVG) formalism defined by Casteigts et al. in [START_REF] Casteigts | Time-varying graphs and dynamic networks[END_REF] (Section 2.4.5) is used to model the communication graph.

Note that processes do not know the values of the ζ latency function, which is only introduced for the simplicity of presentation. Since communications are asynchronous, the values of ζ are finite but not necessarily bounded.

Consider the following example: a graph where E = V × V and every edge in the system is active infinitely often (longer than the message transfer time), but no more than one edge is ever active at a time. In such a system, there are journeys infinitely often between every node and the connectivity is sufficient to solve complex problems such as consensus. However, at any given instant, the graph is partitioned into at least n -1 independent subsets. This shows that similarly to paths, the usual notion of graph partitioning loses relevancy in TVGs, since the number of partitions at a particular instant in the run is not a very useful parameter. Instead, the number of partitions over time is relevant. In the rest of the chapter, the word partition is used to refer to a subset of the network that is isolated from the rest of the network for an arbitrarily long duration, and not just temporarily.

Communication Primitive

Processes communicate exclusively by sending messages with a very simple broadcast primitive. When a process p i calls the broadcast primitive, the message is simply sent to the processes that are currently in p i 's neighborhood, including p i . The broadcast is not required to provide advanced features such as message forwarding, routing, message ordering or any guarantee of delivery.

Channels

Channels are fair-lossy. Messages may be lost but, if the edge is active for the entire time of the message transfer, a message sent infinitely often will be received infinitely often. Messages may be duplicated, but a message may only be duplicated a finite number of times. No message can be created or altered. No assumption is made on message ordering and channels are not required to be FIFO.

Failure Detectors for k-Set Agreement in Unknown Dynamic Systems

The goal of this chapter is to adapt existing failure detectors to solve k-set agreement in dynamic systems.

In order to deal with the dynamics of the system, some connectivity properties are required in addition to the information on failures provided by the failure detector.

Furthermore, the system model considers an unknown network where processes have no information on system membership at the beginning of the run. A way to circumvent this issue was proposed in [START_REF] Thibault Rieutord | Détecteur de défaillances minimal pour le consensus adapté aux réseaux inconnus[END_REF] in the form of the Σ ⊥ failure detector (see Section 2.4.6).

The ΠΣ x,y failure detector of [START_REF] Mostéfaoui | Chasing the weakest failure detector for k-set agreement in message-passing systems[END_REF] (see Section 2.3.2.8) will be augmented with connectivity properties and extended with the method of [START_REF] Thibault Rieutord | Détecteur de défaillances minimal pour le consensus adapté aux réseaux inconnus[END_REF] in order to obtain a failure detector sufficient to solve the k-set agreement problem in unknown dynamic systems.

The Σ ⊥,k Failure Detector

As explained in Sections 2.3.2.4 and 2.3.2.5, the intersection property of both Σ and Σ k must hold over time, which means that if a process queries its failure detector before any communication has taken place, the returned quorum must intersect with the quorums formed by processes later in the run. In known networks, implementations of Σ traditionally solve this issue by returning Π as a quorum at the beginning of the run [START_REF] Delporte-Gallet | Tight failure detection bounds on atomic object implementations[END_REF]. This is not an option in unknown networks where system membership knowledge is only established through communication.

The Σ ⊥ failure detector ( [START_REF] Thibault Rieutord | Détecteur de défaillances minimal pour le consensus adapté aux réseaux inconnus[END_REF]) is an adaptation of Σ for unknown networks. Instead of returning a quorum, Σ ⊥ can also output the default value ⊥ whenever the knowledge necessary to form a quorum has not been gathered yet.

In order to solve k-set agreement in unknown dynamic networks, Σ ⊥,k failure detector is defined to combine the properties of Σ k and Σ ⊥ . It also includes a connectivity property which replaces (and is weaker than) the assumption of a static and complete network.

The Σ ⊥,k failure detector provides each process p i with a quorum denoted qr τ i (which is either a set of process identities or the special value ⊥) at any time instant τ .

The following definition is introduced for the convenience of the presentation: definition: Definition 3.1 (Recurrent neighborhood). The recurrent neighborhood of a correct process p i , denoted R i , is the set of all correct processes whose quorums intersect infinitely often with p i 's quorums.

∀p i ∈ C, R i = {p j ∈ C |∀τ , ∃τ i , τ j ≥ τ : qr τ i i = ⊥ ∧ qr τ j j = ⊥ ∧ qr τ i i ∩ qr τ j j = ∅}.
Note that p j ∈ R i is an equivalence relation between p i and p j . By definition, ∀p i ∈ C :

p i ∈ R i , therefore R i = ∅.
A correct process p i can reach another correct process p j if, provided that p i sends messages infinitely often, p j receives them infinitely often.

Σ ⊥,k is defined by the self-inclusion, quorum liveness, quorum intersection and quorum connectivity properties.

• Self-inclusion: Every process includes itself in its non-⊥ quorums.

∀p i ∈ Π, ∀τ : (qr τ i = ⊥) =⇒ (p i ∈ qr τ i ) .
• Quorum liveness: Eventually, every correct process stops returning ⊥ and its quorums only contain correct processes.

∃τ , ∀p i ∈ C, ∀τ ≥ τ :

qr τ i = ⊥ ∧ qr τ i ⊆ C .
• Quorum intersection: Out of any k + 1 non-⊥ quorums, at least two intersect.

∀τ 1 , ..., τ k+1 ∈ T , ∀id 1 , ..., id k+1 ∈ Π, ∃i, j : 1 ≤ i = j ≤ k + 1 : (qr τ i id i = ⊥ ∧ qr τ j id j = ⊥) =⇒ (qr τ i id i ∩ qr τ j id j = ∅) .
• Quorum connectivity: Every correct process p i can reach every process in R i .

As presented in Sections 2.3.2.5 and 2.4.6, Σ k and Σ ⊥ were defined with only 2 properties (liveness and intersection). Self-inclusion is a property added to Σ x and ΠΣ x by the authors in [START_REF] Mostéfaoui | Chasing the weakest failure detector for k-set agreement in message-passing systems[END_REF] for the sake of the simplicity of algorithm proofs, and it is trivially implemented by the algorithms presented in this chapter. Quorum connectivity is the property added to deal with network dynamics.

Intuitively, the quorum connectivity property means that processes belong to the same partition as their recurrent neighborhood. Note that ∀p i , p j ∈ C : p i ∈ R j =⇒ p j ∈ R i , thus quorum connectivity enables two-way communication between p i and p j . This property is not very costly, since most failure detector implementations already require some level of connectivity between processes in a quorum in order to form the quorums themselves. This is the case for the Σ ⊥,k algorithm presented in Section 3.4, which does not require any additional assumption to implement quorum connectivity.

3.2.2

The Family of Failure Detectors ΠΣ ⊥,x,y ΠΣ ⊥,x,y is defined as an extension of ΠΣ x,y that includes the properties of Σ ⊥,x and is capable of solving k-set agreement in unknown dynamic systems.

Similarly to [START_REF] Mostéfaoui | Chasing the weakest failure detector for k-set agreement in message-passing systems[END_REF], ΠΣ ⊥,x,y is defined incrementally: ΠΣ ⊥,x is defined firstly.

The Failure Detector ΠΣ ⊥,x

At any time instant τ , ΠΣ ⊥,x provides each process p i with a quorum denoted qr τ i (which is either a set of process identities or the special value ⊥) and a leader denoted leader τ i (which is a process identity).

ΠΣ ⊥,x is defined by the following properties:

• Self-inclusion

• Quorum liveness • Quorum intersection • Quorum connectivity • Eventual partial leadership Σ ⊥,x
First, an eventual partial leader is defined as follows:

Definition 3.2 (Eventual partial leader). An eventual partial leader p l is a correct process such that every process in the recurrent neighborhood of p l eventually recognizes p l as its leader forever.

p l ∈ C ∧ ∀p i ∈ R l , ∃τ , ∀τ ≥ τ : leader τ i = p l .
The set of all eventual partial leaders is denoted L.

• Eventual partial leadership: For every correct process p i , there is an eventual partial leader p l that can reach p i .

The original eventual partial leadership property used in [START_REF] Mostéfaoui | Chasing the weakest failure detector for k-set agreement in message-passing systems[END_REF] simply requires the existence of an eventual partial leader in the system. The new version of the property similarly implies that L = ∅ (since C = ∅), but also implies that each correct process must be reachable by one eventual partial leader (which, depending on the level of connectivity, may require more than one leader). In a static and connected network, both properties are equivalent: a single eventual partial leader is necessary and sufficient to fulfill the property, since the connected communication graph enables this single leader to reach every correct process.

In a k-set agreement algorithm, the eventual partial leaders are those processes that eventually decide. In order to ensure termination, the deciding leaders must, therefore, be able to inform the rest of the system of their decision. However, in a dynamic network, the mere existence of an eventual partial leader does not provide the latter with the necessary connectivity to guarantee termination. This is why in dynamic networks, the new eventual partial leadership property is stronger than the original one and imposes the required connectivity.

The eventual partial leadership property implies a trade-off between the number of eventual partial leaders in the system and graph connectivity. On the one hand, if there is a single leader in the system, then this leader must be able to reach every correct process in the system. On the other hand, if the communication graph is partitioned, then there must be at least one local leader per partition.

Such a trade-off implies that the eventual partial leadership property does not prevent the system from being partitioned into up to n partitions over time, provided that every correct process identifies itself as its own eventual partial leader. However in this scenario it would be impossible to verify the quorum intersection and quorum connectivity properties.

The Failure Detector ΠΣ ⊥,x,y

The definition of ΠΣ ⊥,x,y is the same as ΠΣ x,y in [START_REF] Mostéfaoui | Chasing the weakest failure detector for k-set agreement in message-passing systems[END_REF], except that it uses ΠΣ ⊥,x instead of ΠΣ x . ΠΣ ⊥,x,y can be seen as y instances of ΠΣ ⊥,x running concurrently.

ΠΣ ⊥,x,y provides each process p i with an array

F D i [1..y] such that for each j, 1 ≤ j ≤ y, F D i [j] is a pair containing a quorum F D i [j]
.qr and a process index F D i [j].leader. The array satisfies the following properties:

• Vector safety: ∀j ∈ [1..y] : F D i [j]
.qr satisfies the self-inclusion, liveness, intersection and quorum connectivity properties of ΠΣ ⊥,x .

• Vector liveness: ∃j ∈ [1..y] :

F D i [j] satisfies the eventual partial leadership property of ΠΣ ⊥,x .
The idea is to reduce the cost of the system assumptions: the liveness property only needs to be verified by one out of a set of y instances of the detector.

The authors in [START_REF] Mostéfaoui | Chasing the weakest failure detector for k-set agreement in message-passing systems[END_REF] prove that for 1 ≤ y ≤ n -1, ΠΣ 1,y is as strong as Σ 1 , Ω y . This shows that the y parameter of ΠΣ x,y (and ΠΣ ⊥,x,y ) is comparable to the y of Ω y .

ΠΣ ⊥,x,y is sufficient to solve the k-set agreement problem in unknown dynamic systems if k ≥ xy. This will be proved by providing a k-set agreement algorithm relying on ΠΣ ⊥,x,y in Section 3.5.

Assumptions

This section presents three system assumptions. The algorithms presented in Section 3.4 will then list the assumptions from this section on which they rely.

Time-Varying Graph Classes

In addition to defining the formalism of the TVG, Casteigts et al. present in [START_REF] Casteigts | Time-varying graphs and dynamic networks[END_REF] a number of TVG classes which provide different levels of connectivity assumptions. Class 5 is particularly relevant to this chapter:

Definition 3.3 (Class 5: recurrent connectivity [CFQS12]). All processes can reach each other infinitely often through journeys. ∀u, v ∈ Π, ∀τ , ∃J ∈ J * (u,v) : departure(J ) > τ .
This connectivity assumption does not exactly fit the requirements of the proposed algorithms. On the one hand, it is too strong. It implies a global connectivity between any two processes in the system, which is not necessary to solve k-set agreement, since the problem can be solved in a system partitioned into k subsets. On the other hand, class 5 is too weak since it relies on the notion of journey, which is insufficient to ensure the transmission of messages. Even if a journey exists between p i and p j , there is no guarantee that a message sent by p i can reach p j . In fact, even if the edge between p i and p j is active infinitely often and the message is sent infinitely often, the message might always be sent in between two activation periods of the edge, thus never crossing it. To solve this problem, Gómez-Calzado et al. defined in [START_REF] Gómez-Calzado | A connectivity model for agreement in dynamic systems[END_REF] the notion of timely journeys for the case of synchronous systems. This solution can be extended into γ-journeys for the case of asynchronous communications. Definition 3.4 (γ-Journey). A γ-journey J (where γ > 0 is a time duration) is a journey such that every node on the path can wait up to γ units of time after the next edge becomes active before forwarding the message. Since the message may be sent at any time within the γ time window and the channel latency may vary during that time, the edge must remain active long enough for the worst case duration. -∀i, 1 ≤ i ≤ |J |, e i stays active from time t i until, at least, time

t i +max 0≤j≤γ {j + ζ(e i , t i + j)} . -∀i, 1 ≤ i < |J |, t i+1 ≥ t i + max 0≤j≤γ {j + ζ(e i , t i + j)} .
With a γ-journey, processes are given an additional time window of γ units of time to send the message. In [START_REF] Gómez-Calzado | A connectivity model for agreement in dynamic systems[END_REF], this time was used to detect the activation of the edge. This solution is appropriate for point-to-point communications in a known network, since it allows the sender of the message to resend the message to the receiver whenever the edge appears again. However, this is not helpful in an unknown non-complete network where processes have to rely on blind broadcasts and forwarding to propagate information.

Instead, the time window provided by γ-journeys is used as an upper bound on the time between two transmissions of the message. This explains the need for synchronous processes: each process should be able to repeatedly send every message at least once every γ units of time.

Provided that processes receive their own broadcasts within γ units of time and then rebroadcast it, it is ensured that every message is sent at least once every γ units of time. If there is infinitely often a γ-journey from p i to p j , then p i can reach p j .

The set of all the γ-journeys from u to v is called J γ (u,v) . Using class 5 as a starting point, TVGs of class 5-(α, γ) are defined as follows. γ is the time duration parameter of γ-journeys, and α is a parameter defining the number of correct processes that each correct process is ensured to communicate with. Assumption 3.1 (Class 5-(α, γ): (α, γ)-recurrent connectivity). Every correct process can reach and be reached through γ-journeys infinitely often by at least α correct processes.

∀p i ∈ C, ∃P i ⊆ C, |P i | ≥ α, ∀t ∈ T , ∀p j ∈ P i , ∃J i ∈ J γ (p i ,p j ) : departure(J i ) ≥ t ∧ ∃J j ∈ J γ (p j ,p i ) : departure(J j ) ≥ t .
This assumption is parametrized by the two values α and γ. A low γ value weakens the connectivity assumption by allowing shorter time windows for the journeys, but implies that processes must be able to send messages more often to ensure that a message is sent within the shorter window. On the other hand, a high γ value reduces the number of journeys that are qualified as γ-journeys, thus strengthening the connectivity assumption, but accepts slower processes.

The α parameter also presents a trade-off: class 5-(α, γ) indirectly implies that there must be at least α correct processes in the system. As a result, a high α value will result in a strong assumption on the number of process failures which can be costly in a dynamic system. A low α value would strengthen the message pattern assumptions presented in the next section.

Class 5-(α, γ) also implies that all correct processes must know a lower bound for α.

To summarize, the assumption of a TVG of class 5-(α, γ) means that correct processes are able to communicate infinitely often with a subset of α correct processes. This property ensures that correct processes will not wait for messages forever, which enables the failure detector algorithm to ensure the quorum liveness property. Additionally, if the algorithm ensures that every correct process p i eventually only forms quorum from the P i set, then class 5-(α, γ) also ensures quorum connectivity.

Message Pattern Assumptions

This section presents message pattern assumptions, as defined by Mostéfaoui et al. in [START_REF] Mostéfaoui | Asynchronous implementation of failure detectors[END_REF]. The message pattern model consists in assuming some properties on the relative order of message deliveries. If processes periodically wait for a certain number of messages, the idea is to assume that the message sent by some specific process will periodically be among the first ones to be received.

In order to express the message pattern assumptions used to implement ΠΣ ⊥,x,y , it is necessary to assume that the distributed algorithm executed by processes uses a query-response mechanism. Processes periodically issue query messages, to which other processes respond.

The principle of the failure detector algorithm revolves around processes repeatedly issuing a query and then waiting for responses from α processes. The α parameter is therefore the minimum size of quorums returned by the algorithm, which does not necessarily constitute an assumption on the number of failures, since α might be equal to 1. Note that α is the same parameter used to define TVGs of class 5-(α, γ) which ensures that correct processes will not wait for messages infinitely.

The first α processes whose response to a given query from process p i are received by p i are called a response set.

Assumption for Quorum Intersection

The assumption of a TVG of class 5-(α, γ) is not sufficient to ensure the quorum intersection property. In [START_REF] Bouzid | anti-Ω x × Σ z )-Based k-Set Agreement Algorithms[END_REF], Bouzid and Travers proposed a method to implement quorums: if processes repeatedly wait for messages from at least n k+1 + 1 processes before outputting these processes as their new quorum, then the size of quorums alone is sufficient to ensure intersection. This method implies that there must be at least n k+1 + 1 correct processes in the system, otherwise processes would wait forever, thus preventing liveness. In a dynamic system where processes are expected to join and leave the system, an assumption on the number of process failures seems too costly. For this reason, the failure detector algorithms presented in the next section rely on the message pattern approach.

The following assumption is sufficient for the ΠΣ ⊥,x,y algorithm to implement quorum intersection. It was obtained by generalizing the assumption used for the case k = 1 in [START_REF] Thibault Rieutord | Détecteur de défaillances minimal pour le consensus adapté aux réseaux inconnus[END_REF].

Assumption 3.2 (Generalized winning quorums). ∃m ∈ [1, k] and ∃Q w1 , ..., Q wm ⊆ Π (called winning quorums). Each winning quorum Q wi is associated with a number w i ≥ 1 (called the weight of Q wi ) such that m i=1 w i ≤ k. ∀p ∈ Π, every time p issues a new query, ∃i ∈ [1, m] such that Q wi = ∅ and out of the first α processes from which p receives a response, at least |Q wi | w i +1 + 1 of them are in Q wi .

Intuitively, Assumption 3.2 requires that there are m sets of processes, the winning quorums, that answer faster than others, i.e., faster enough for subsets of these sets to be always included in every response set. In addition, every time a correct process issues a query, connectivity must allow for a subset of one of these winning quorums to receive and respond to the query. Note that winning quorums do not necessarily correspond to quorums returned by the failure detector at some point: instead they are sets of processes that have a tendency to be included in response sets.

The weight w i of a winning quorum is a parameter which states which proportion of the winning quorum must be included in response sets. A winning quorum of weight 1 must be included in strict majority in a response set, whereas winning quorums of higher weights can be included in smaller proportions. The sum of all winning quorum weights is limited by k.

It is interesting to consider some extreme instances of this assumption. The first extreme is m = k. In this particular case, all winning quorums are necessarily of weight 1, and therefore each response set must include a strict majority of one of the winning quorums. Since each response set includes the strict majority of one out of k winning quorums, it is easy to see that out of any k + 1 response sets, at least two will necessarily intersect. Another extreme case is m = 1 and w 1 = k. In this particular case, all response sets must contain a small part of a single winning quorum. The flexibility in the second example lies in which subset of the winning quorum will be included in each response set, while the flexibility in the first example lies in which winning quorum would be included in majority by each response set. Assumption 3.2 implies that there is at least one winning quorum Q wi such that at least

|Q wi | w i +1 + 1 of the processes in Q wi are correct. If α = |Q wi | w i +1 + 1 = 1
, there is no assumption on the number of failures but |Q wi | < w i + 1, which leaves minimal flexibility on the processes that must be included in every response set, thus strengthening the message pattern assumption. On the other hand, if |Q wi | (and therefore α) is high, the number of failures is limited but each response set must contain a subset of a larger set, which allows for more flexibility in the message pattern.

Assumption for Eventual Partial Leadership

In order to ensure the eventual partial leadership property, processes need to identify a local leader. Since the eventual partial leadership property is supposed to be implemented on top of Σ ⊥,x , the notion of quorum can be used to define this new assumption.

Additionally, the order of processes in quorums is used to single out the leader. For this purpose, processes in a quorum are assumed to be totally ordered. Any specific ordering can be used. A natural choice would be to use the order in which the processes were added to the quorum. Another simple choice would be to order according to process identifiers. For a process p i and a quorum qr, if p i ∈ qr, then pos(p i , qr) denotes the position of p i in qr according to the chosen total order. If p i is the first process in qr τ j , then pos(p i , qr τ j ) = 1. In this particular case, p i is said to be the candidate of p j at time τ .

Eventual partial leaders are defined as follows:

Definition 3.5 (Eventually winning process). A correct process p l is called an eventually winning process if there is a time τ such that after τ, ∀τ ≥ τ , ∀p i ∈ R l \{p l } : 1) p l is present in every quorum formed by p i . p l ∈ qr τ i . 2) p l 's identity is always positioned in p i 's quorum before the identities of other processes in R i . ∀p j ∈ R i \{p l , p i } : pos(p l , qr τ i ) < pos(p j , qr τ i ) . 3) In every quorum formed by p i , there is another process that also belongs to R l . ∃p j ∈ R l \{p l , p i } :

p j ∈ qr τ i .
Point (1) means that after some time, p l must be fast enough to ensure that its responses arrive in time to take part in every local quorum.

The implication behind (2) depends on the chosen ordering method. If processes are ordered by date of addition to the quorum, then (2) implies that after some time, p l must be faster than the rest of the recurrent neighborhood of p i . If processes are ordered by process identities, p l must have the smallest process identity in the recurrent neighborhood.

It is easy to see how (1) and ( 2) can be used: if p l belongs to every quorum and is singled out by the quorum order, processes in R l can reliably select their candidate as leader.

Note that (2) excludes the case p i = p j , since otherwise p l would have to be placed before p i in p i 's quorums. If processes are ordered by date of addition to the quorum, this expectation would be very unrealistic since receiving its own message is a local computation and should therefore be faster than receiving p l 's message.

Point (3) requires that processes in R l must not only communicate with p l but also with each other to some extent, which enables them to share the information that p l is their candidate. Note that (3) also requires the processes p l , p i and p j to be distinctly defined: therefore, in order for an eventually winning process to exist, there must be at least 3 correct processes in the system (f ≤ n -3). Since p l , p i and p j must be included in the same quorums, α must also be equal to 3 or greater.

The set of all eventually winning processes is called W .

The following assumption enables the failure detector algorithm to ensure the eventual partial leadership property. Assumption 3.3 (Eventually winning γ-sources). For every correct process p i , there is an eventually winning process p l such that there is infinitely often a γ-journey from p l to p i .

∀p i ∈ C, ∃p l ∈ W , ∀τ : ∃J ∈ J γ (p l ,p i ) ∧ departure(J ) > τ .
The ΠΣ ⊥,x algorithm will ensure that eventually winning processes are eventual partial leaders. As a result, this assumption will be sufficient to ensure the eventual partial leadership property.

Summary of Assumptions

Table 3.1 summarizes the assumptions presented in this section and the failure detector properties that rely on them for implementation. The self-inclusion property of Σ ⊥,k is absent from this table because it does not require any assumption and will simply be ensured through algorithmic properties.

Implementation of Message Pattern Assumptions

Assumptions 3.2 and 3.3 are very abstract and it can be difficult to judge at first glance how likely they are of being verified in a real network. This is because the assumptions presented in this section are meant to be as close as possible to the minimum model strength required to ensure that the algorithm implements the ΠΣ ⊥,x,y failure detector. The message pattern model enables such an implementation while keeping the model generic and applicable to different networks. In the following, examples of more traditional assumptions that are sufficient to ensure Assumptions 3.2 and 3.3 are presented.

Implementation of Assumption 3.2

A simple and intuitive method is to assume that |C| ≥ n k+1 + 1. In this case, Assumption 3.2 is trivially verified with m = 1, w 1 = k and Q w1 = Π. This implies that α ≥ n k+1 + 1, and, thus, the minimal size of quorums is sufficient to ensure intersection. This particular case is the method used to implement Σ k in static networks in [START_REF] Bouzid | anti-Ω x × Σ z )-Based k-Set Agreement Algorithms[END_REF].

Another approach would be to use a partial synchrony assumption. For a given duration ∆, let us call ∆-journey a γ-journey J such that arrival(J ) -departure(J ) ≤ ∆. Π is then separated into two subsets: slow processes and fast processes. A slow process p i is a process such that there is never a ∆-journey from p i to any correct process p j ∈ C\{p i }. Fast processes are all other processes and Q is the set of all correct fast processes. The assumption is that for any correct process p i and at any time, there are ∆-journeys linking p i to at least |Q| k+1 + 1 processes from Q. Assumption 3.2 is verified with m = 1, w 1 = k and Q w1 = Q.

Implementation of Assumption 3.3

One way to ensure Assumption 3.3 is that there is a correct subset Q of the system that is constantly connected and recognizes a leader p l ∈ Q, that can reach the entire system infinitely often. The leader must be known from the other processes in Q from the start (it can simply be the lowest process identifier in Q, for example). When a process in Q issues a query, the communication layer for that process will then wait for a response from p l and a response from another process in Q before delivering any other response. This is sufficient to ensure that p l is the first process in every quorum formed in Q, and that processes in Q communicate with each other to a sufficient extent.

Practical Issues

From a practical point of view, some types of networks are particularly adapted to ensure Assumptions 3.2 and 3.3. In wireless mesh networks ([AWW05]), the nodes move around a fixed set of nodes and each mobile node eventually connects to a fixed node. Wireless sensor networks ([ASSC02]) can be organized in clusters; one node in each cluster is designated the cluster head. Messages sent between clusters are routed through the cluster heads of the sending and receiving clusters. An infra-structured mobile network ( [START_REF] Cao | The eventual leadership in dynamic mobile networking environments[END_REF]) is composed of Mobile Hosts (MH) and Mobile Support Stations (MSS). A MH is connected to a MSS if it is located in its transmission range, and two MHs can communicate only through MSSs.

In each of these network models, there is a privileged subset of powerful nodes (fixed nodes, cluster heads, MSSs) that can be used as a winning quorum to satisfy Assumption 3.2 or as the neighborhood R l of an eventual winning process p l for Assumption 3.3.

Both assumptions can also be ensured from a probabilistic perspective. If a subset Q of the system is made of powerful nodes that respond to queries much faster than the rest of the nodes, then there is a high probability that Assumption 3.2 will be verified. Similarly, Assumption 3.3 can be verified in a probabilistic way with a leader that is simply a powerful process benefiting from very small communication delays with the processes around it.

Comparable Assumptions in the Literature

This section attempts to put the strength of Assumptions 3.2 and 3.3 into perspective by comparing them to some other existing models.

In [START_REF] Afek | Asynchrony from synchrony[END_REF], Afek and Gafni propose an implementation of read and write operations in a dynamic synchronous message passing system. Although the underlying network is assumed to be complete, in each synchronous round a subset of edges lose their messages. Therefore, such a system can be modeled as a TVG where the edges that successfully deliver their message in a round are considered active in that round. As a result, the message adversary that decides which messages will go through can be compared to a connectivity assumption. The paper defines the Traversal Path (TP) adversary as a model in which, for every synchronous round, the directed graph defined by the successfully delivered messages in this round contains a directed path passing through all the nodes. This connectivity assumption is weaker than a TVG of class 5, because traversal paths are directed paths, which implies that every process can not necessarily communicate with every other. The comparison with class 5-(α, γ) is less straightforward. On the one hand, class 5-(α, γ) implies two-way connectivity whereas a TP adversary only requires oneway connectivity. On the other hand, class 5(α, γ) only requires connectivity between a limited number of nodes (as defined by the α parameter) and allows network partitioning, whereas a TP adversary connects the entire system.

In [START_REF] Biely | The generalized loneliness detector and weak system models for k-set agreement[END_REF], Biely et al. define and implement the generalized loneliness failure detector L k in a static and connected network. For this purpose, the authors use the M anti(x) message pattern model, which is defined by the x-Anti-Source. An x-Anti-Source is a process which is ensured to receive responses from x processes to every query it issues before it issues the next query. This definition could be used in unknown dynamic systems: if every process in the system is an x-Anti-Source for x ≥ n k+1 + 1, then Assumption 3.2 (with α = x) and the quorum intersection property are ensured. However, the M anti(x) model only requires x processes to be x-Anti-Sources, which is only sufficient to implement quorums if x = n, since the intersection property must apply to every process in the system.

In [START_REF] Arantes | Eventual leader election in evolving mobile networks[END_REF], Arantes et al. present an algorithm that implements the Ω failure detector in an asynchronous TVG of class 5. To this end, the authors define the Stable Responsiveness Property (SRP). A correct process p satisfies the SRP at time t if and only if, after t, all nodes in p's neighborhood receive a response from p to every one of their queries within the first α responses.

The definition of the SRP can be compared to the definition of an eventually winning process. Both properties enable a leader election mechanism by assuming that after some time, some process is among the first to respond to the queries of its neighbors. However, SRP applies to every process that shares a link with the leader after t, even for a moment, whereas the property of an eventually winning process p l only applies to the processes of R l , meaning those processes that interact infinitely often with p l . Thus, a process can join the neighborhood of an eventually winning leader and leave it later on, which is not possible with a process satisfying the SRP. But while the properties of an eventually winning leader can apply to a smaller subset of processes, those properties are stronger. Process p l is not only required to respond to every query from its neighbors in time, it must also be the fastest to respond. Additionally, the processes within R l are expected to communicate with each other to some extent, which is not necessary in the SRP.

Failure Detector Algorithms

In this section a Σ ⊥,k algorithm is first presented, then extended into a P iΣ ⊥,x,y algorithm.

An Algorithm for Σ ⊥,k

Algorithm 1 implements the Σ ⊥,k failure detector in unknown dynamic systems with asynchronous communications. It uses a query/response mechanism with round numbers in order to ensure quorum liveness.

Assumptions

Algorithm 1 implements Σ ⊥,k in unknown dynamic systems, provided that the following assumptions hold: 1. The system is a Time-Varying Graph of class 5-(α, γ) where α is the minimal size of a quorum and γ is the maximal time taken by a process to receive its own broadcasts (Assumption 3.1).

2. The run follows a generalized winning quorums message pattern (Assumption 3.2).

Algorithm 1 Implementation of Σ ⊥,k for process p i .

1: init 2:

r i ← 0 // Local
last_known i ← last_known i ∪ { src, r_src } 20: bcast(src, r_src, Q ∪ {p i }) 21:
else if src, -/ ∈ last_known i then 22:

last_known i ← last_known i ∪ { src, r_src } 23: bcast(src, r_src, Q ∪ {p i }) 24:
else 25:

do nothing

Notations

Each process p i uses the following local variables: r i is the local round number of process p i . qr i is the quorum currently returned by the failure detector for process p i . recv_f rom i is the quorum buffer, containing all the identities of the processes whose response has been received by p i since the time it last formed a new (complete) quorum. When the buffer contains enough information (i.e., at least α process identities), it becomes the new quorum and recv_f rom i is reinitialized. last_known i is the knowledge p i has of other processes round numbers. This variable and the associated mechanisms are not necessary for the correctness of the algorithm, they are simply used to improve performance by limiting the number of useless transmitted messages.

Process p i calls the bcast(src, r_src, Q) primitive to broadcast a message to the processes currently in its neighborhood. A message contains the following values: src is the identity of the original sender of the query (which is not necessarily the immediate sender of the message, since queries are forwarded multiple times). r_src is the round number of src when this query was issued. Process src ignores responses to previous rounds.

Q is the set of the identities of processes who responded to the current query. When the query goes back to process src, it will add the content of this set to its quorum buffer.

Algorithm Description

The principle behind the algorithm is the following: every process p i keeps broadcasting queries for round r i until it receives enough responses to form a quorum of size at least α, then it increments r i and proceeds with the next round.

Contrarily to most query/response algorithms, Algorithm 1 only uses one type of messages. A message is both a query and a response, depending on which process receives it. Every message travels from process to process, until it goes back to the original message sender. If the test on line 8 is true, the message is considered as a response to the current round query. If instead the test on line 15 is true, the message is considered as a query from another process.

Every process identity received in a response for the current round is added to the recv_f rom i buffer (line 9), and when the buffer size gets superior or equal to α, then a new quorum is formed by copying recv_f rom i into qr i and resetting the buffer (lines 10 -13).

If a received message is a query from another process, p i updates its local knowledge and then adds its own identity to the message and rebroadcasts it unless another query for a higher round has been previously received from the same emitter (lines 15 -25).

At first glance it might look like process p i only broadcasts its queries once (lines 6 and 14), but keep in mind that processes receive their own broadcasts. Therefore, after initially broadcasting a new query, p i will receive it at most γ instants later and broadcast it again (line 14).

The same rebroadcasting approach applies for queries from other processes. Once p i has received a message from src for round r_src, it will keep rebroadcasting it (lines 20 and 23) until it is informed that src moved on past round r_src (the test on lines 16 -17).

Based on the assumption of generalized winning quorums, the only action necessary to ensure quorum intersection is to make sure that quorums are formed from at least α process identities, which is guaranteed by line 10.

Quorum liveness is ensured because (1) correct processes keep forming new quorums from fresh information infinitely often thanks to class 5-(α, γ) and (2) the identities of crashed processes are excluded from new quorums since the r_src in their responses are eventually outdated (line 8).

Proof of Correctness

Lemma 3.1. In a TVG of class 5-(α, γ) where Assumption 3.2 holds, Algorithm 1 ensures the quorum intersection property of Σ ⊥,k .

Proof. Assumption 3.2 implies that m i=1 w i ≤ k. For any number w ∈ [1, k], n w denotes the number of winning quorums of weight w. It follows that k w=1 w × n w ≤ k. Additionally, Assumption 3.2 imposes that every response set includes responses from a winning quorum Q wi of weight w i such that at least |Q wi | w i +1 + 1 processes from Q wi are part of that response set. It follows that, if w i + 1 response sets are formed from the same winning quorum Q wi , at least two of these response sets intersect.

If no two response sets are to intersect, then at most w i response sets can be formed from a given winning quorum Q wi . Therefore, for any number w ∈ [1, k], at most w × n w response sets can be formed from the set of all winning quorums of weight w. It follows finally that at most k w=1 w × n w response sets can be formed from the set of all winning quorums without any two of them intersecting. Since k w=1 w × n w ≤ k, at least two out of any k + 1 response sets intersect.

Lines 10 and 11 of Algorithm 1 ensure that quorums include the first α responses (response set) to the current query. Therefore every quorum includes a response set, and the quorum intersection property of Σ ⊥,k is ensured. Lemma 3.2. In a TVG of class 5-(α, γ), every correct process executing Algorithm 1 forms a new quorum infinitely often.

Proof. Since it uses a query-response mechanism, Algorithm 1 requires every correct process to reach and be reached back by α processes, which is ensured by a TVG of class 5-(α, γ) infinitely often. Even if a journey includes waiting time during which the process holding the message is isolated, the process keeps memory of the message by rebroadcasting it to itself, and transmits it to other processes as soon as it it stops being isolated. As a result, every correct process will receive responses from α processes infinitely often, and therefore pass the test on line 10 infinitely often.

Lemma 3.3. In a TVG of class 5-(α, γ), Algorithm 1 ensures the quorum liveness property of Σ ⊥,k .

Proof. By definition, faulty processes will crash or leave the system forever in a finite time. Let t ∈ T be the time at which the last faulty process crashes or leaves the system forever. Since f < n, there are correct processes in the system. Lemma 3.2 ensures that each of these processes forms a new quorum sometime after t. Let τ ∈ T be a time such that τ > t and every remaining process has formed a quorum between t and τ . Therefore, every quorum being currently built at τ has been started after t, which means no faulty process can possibly respond to the corresponding query message. As a result, every new quorum formed after τ contains only correct processes. It follows that Algorithm 1 ensures the quorum liveness property of Σ ⊥,k .

Lemma 3.4. In a TVG of class 5-(α, γ), Algorithm 1 ensures the quorum connectivity property of Σ ⊥,k .

Proof. The properties of a TVG of class 5-(α, γ) ensure that every correct process will always receive enough messages to pass the test on line 10 and keep forming new quorums infinitely often. The test on line 8 ensures that processes only form quorums from messages from the current round. It follows that eventually, every correct process p i only includes in its quorums processes which receive its queries and respond to it infinitely often. Therefore, p i can send and receive messages infinitely often to and from the processes that are infinitely often in its quorums.

Let p i ∈ C and p j ∈ R i . By definition of R i , p i and p j 's quorums intersect infinitely often and thus there must exist a correct process p m such that p m is infinitely often in p i 's quorums and p m is infinitely often in p j 's quorums. As a result, p m can receive messages from p i infinitely often and p j can receive messages from p m infinitely often. Therefore if messages are routed through p m , p j can receive messages from p i infinitely often.

Theorem 3.1. In a TVG of class 5-(α, γ) where Assumption 3.2 holds, Algorithm 1 implements a Σ ⊥,k failure detector.

Proof. It follows from Lemmas 3.1, 3.3 and 3.4 that the algorithm ensures the quorum intersection, quorum liveness and quorum connectivity properties respectively.

Self-inclusion is ensured by the fact that every quorum is formed from the buffer recv_f rom i (line 11), and the buffer is always initialized with p i (lines 4 and 12).

An Algorithm for ΠΣ ⊥,x

Algorithm 2 is an extension of Algorithm 1 aiming at implementing ΠΣ ⊥,x in unknown dynamic systems. It adds an election mechanism to the original algorithm in order to identify an eventual partial leader.

This leader election mechanism relies on the quorum order, as defined in Section 3.3.2.2. Every time a process forms a new quorum, it selects the first process in the quorum as candidate for the leader election. If a process is the candidate of every other process in its quorum, then it selects itself as leader; otherwise it selects its candidate as leader.

Assumptions

Algorithm 2 implements ΠΣ ⊥,x in unknown dynamic systems, provided that the following assumptions hold: 1. The system is a Time-Varying Graph of class 5-(α, γ) where α is the minimal size of a quorum and γ is the maximal time taken by a process to receive its own broadcasts (Assumption 3.1).

2. The run follows a generalized winning quorums message pattern (Assumption 3.2).

3. The system verifies the eventually winning γ-sources assumption (Assumption 3.3).

Notations

Algorithm 2 uses the same notations as Algorithm 1. Additionally, each process p i uses the following local variables: leader i is the leader returned by the failure detector for process p i . leader i is initially p i , and is later updated on lines 21 or 23.

Algorithm 2 Implementation of ΠΣ ⊥,x for process p i .

1: init 2: do nothing candidate i is the first process in p i 's most recent quorum (excluding p i itself). It is affected in lines 18 -19. candidate i is initialized to ⊥ and is added to sets (lines 31 and 34). As a convention, ∅ ∪ {⊥} = ∅. candidates i is the set of the candidates of the processes in recv_f rom i (except p i ). p i will only elect itself as leader (line 21) if candidates i only contains p i (i.e., p i is the candidate of every process in recv_f rom i \{p i }) or if candidates i is empty (i.e., p i considers itself alone).

r i ← 0 // Local
r i ← r i + 1 18: candidate i ← p l | (pos(p l , qr i ) = 1 ∧ p l = p i ) 19: ∨(pos(p i , qr i ) = 1 ∧ pos(p l , qr i ) = 2) 20: if candidates i = {p i }
In addition to the message parameters described for Algorithm 1, messages sent by processes contain the cands parameter, which is the set of the candidates of the processes in Q, at the time when they responded to the query. It carries the information necessary for process p i to build its candidates i set on line 13.

Algorithm Description

Algorithm 2 follows the same structure and uses the same mechanisms to build quorums as Algorithm 1. Its additional code aims to select partial leaders according to the eventual partial leadership property of ΠΣ ⊥,x . The extension added to Algorithm 1 is composed of two parts: candidate selection and leader selection.

Candidate selection revolves around the notion of quorum order presented in Section 3.3.2.2. The first process in every quorum is selected as the candidate. Whenever a process p i completes a new quorum (meaning it passes the test on line 14), it handles the end of the round similarly to Algorithm 1 (lines 15 -17). It then identifies the first process in the new quorum (excluding itself) according to the chosen ordering method in lines 18 -19 and selects it as its candidate i . If it was possible for p i to be its own candidate, and if quorums were ordered by date of response, then p i would always be its own candidate.

By virtue of Assumption 3.3, an eventually winning process p l will eventually be forever the candidate of every process in R l \{p l }. However, p l cannot be its own candidate. Therefore, information about p l 's own quorum order is not sufficient for p l to select itself as the leader. It must take into account the candidates of other processes. This is the purpose of the candidates i variable. Other processes inform p i of their respective candidates by including it in their responses (lines 31 and 34), and p i gathers this information in candidates i in line 13. When p i completes a quorum, candidates i contains the candidates of the processes currently in qr i \{p i }.

If every process in qr i agrees on p i as the candidate (or if p i is the only process in qr i ), then p i selects itself as the leader (line 21). Otherwise, p i selects candidate i (line 23).

Note that point (3) of Definition 3.5 prevents the problematic case where a process p i only includes in its quorums an eventually winning process p l and processes in Π\R l . In this scenario, it would be possible for every process in R i (including p l ) to chose p i as its candidate, thus misleading p i into selecting itself as the leader infinitely often.

Proof of Correctness

This proof will show that, if Assumptions 3.1, 3.2 and 3.3 hold, then Algorithm 2 ensures the 5 properties of ΠΣ ⊥,x . Lemma 3.5. In a TVG of class 5-(α, γ) where Assumption 3.2 holds, Algorithm 2 ensures the self-inclusion, quorum intersection, quorum liveness and quorum connectivity properties of ΠΣ ⊥,x .

Proof. The added code from Algorithm 1 does not modify the way the qr i variable is initialized and updated. Therefore, the proof for Theorem 3.1 holds for Algorithm 2.

Lemma 3.6. Every eventually winning process p l is eventually forever the candidate i of every process p i ( = p l ) of its recurrent neighborhood. ∀p l ∈ W , ∀p i ∈ R l \{p l } : ∃τ : ∀τ ≥ τ : candidate i = p l at time τ .

Proof. It follows from the properties of a TVG of class 5-(α, γ) that correct processes will keep passing the test on line 14, and therefore form new quorums infinitely often.

By contradiction, assume the following:

∃p l ∈ W , ∃p i ∈ R l \{p l }, ∃p m ∈ Π\{p l }, ∀τ : ∃τ ≥ τ : candidate i = p m at time τ
There are, thus, two cases: p m / ∈ R i . By definition of R i , there is a time after which p i 's quorums never intersect with p m 's quorum. By construction of the algorithm (lines 4 and 16), self-inclusion is ensured (every process belongs to its own quorums). Thus, there is a time after which p m is never in p i 's quorums, and therefore it can never be selected as candidate i on lines 18 -19 after this time.

p m ∈ R i . Since p l is an eventually winning process, there is a time after which (1) p l is in every quorum formed by p i and (2) in every quorum formed by p i that includes p m , p l is positioned before p m . As a result, p m can never be selected as candidate i on lines 18 -19 after this time.

W is the set of all eventually winning processes, and L is the set of all eventual partial leaders.

Lemma 3.7. Every eventually winning process is an eventual partial leader. W ⊆ L.

Proof. Let p l ∈ W . p l is an eventual partial leader if and only if, for every p i ∈ R l , eventually leader i = p l forever. There are two cases: p i = p l . It follows from the definition of R l and from self-inclusion that there is a time after which every process that is not in R l will stop appearing in the quorums formed by p l . It follows that there is a time τ 1 such that ∀τ 1 > τ 1 , qr τ 1 l ⊆ R l . If α = 1, then qr τ 1 l = {p l } and therefore candidates l = ∅ at time τ 1 (by construction of candidates l ). If α > 1, since the definition of R l is symmetrical, ∀τ 1 > τ 1 , ∀p j ∈ qr τ 1 l : p l ∈ R j . It then follows from Lemma 3.6 that ∃τ 2 ≥ τ 1 , ∀τ 2 > τ 2 , ∀p j = p l ∈ qr τ 2 l : candidate j = p l at time τ 2 . Since p l will keep forming new quorums with fresh information, ∃τ 3 ≥ τ 2 such that every time after τ 3 that p l completes a round, then candidates l = {p l }. As a result, after time τ 3 , p l will always pass the test on line 20 and, therefore, will forever identify itself as the leader.

p i = p l . According to point (3) of the eventually winning process definition, ∃τ 1 , ∀τ 1 > τ 1 , ∃p j ∈ R l : p j ∈ qr τ 1 i . It follows from Lemma 3.6 that ∃τ 2 ≥ τ 1 , ∀τ 2 > τ 2 , candidate j = candidate i = p l at time τ 2 . Since p i will keep forming new quorums with fresh information received from p j , ∃τ 3 ≥ τ 2 such that every time after τ 3 that p l completes a round, then p l ∈ candidates i . As a result, after τ 3 , p i will always fail the test on line 20 and will forever identify candidate i = p l as the leader.

In both cases, p i selects p l as leader forever, which makes p l an eventual partial leader.

Lemma 3.8. If the eventually winning γ-sources assumption (Assumption 3.3) holds, then Algorithm 2 ensures the eventual partial leadership property of ΠΣ ⊥,x .

Proof. It follows from Assumption 3.3 that ∀p i ∈ C, ∃p l ∈ W , ∀τ : ∃J ∈ J γ (p l ,p i ) ∧departure(J ) > τ . It follows from Lemma 3.7 that p l ∈ L. Since fair-lossy channels are assumed, then if p l sends messages infinitely often, then p i will receive messages from p l infinitely often. Theorem 3.2. In a TVG of class 5-(α, γ) where Assumptions 3.2 and 3.3 hold, Algorithm 2 implements a ΠΣ ⊥,x failure detector.

Proof. Follows directly from Lemmas 3.5 and 3.8.

An Algorithm for ΠΣ ⊥,x,y

An algorithm for ΠΣ ⊥,x,y simply consists in executing y instances of Algorithm 2 simultaneously. This algorithm relies on Assumptions 3.1 , 3.2 and 3.3. However, Assumption 3.3 is only required to apply for one out of the y instances of the algorithm.

A k-Set Agreement Algorithm

In [START_REF] Mostéfaoui | Chasing the weakest failure detector for k-set agreement in message-passing systems[END_REF], the authors proposed an algorithm for k-set agreement using ΠΣ x,y for static networks. The k-set algorithm itself is very simple. It only deals with the liveness property of k-set agreement (termination) and encapsulates the safety properties (validity and agreement) into the Alpha x sub protocol. This section will adapt the Alpha x and k-set agreement algorithms for dynamic networks.

The Alpha x Sub Protocol

Alpha was introduced in [GR07] as a way to exactly capture the safety properties of consensus (that is, validity and agreement). It is thus complementary to the Ω failure detector, which is necessary to ensure liveness (the termination property). Alpha was later generalized in [START_REF] Raynal | In search of the holy grail: Looking for the weakest failure detector for wait-free set agreement[END_REF] into KA for the k-set agreement problem.

In [START_REF] Mostéfaoui | Chasing the weakest failure detector for k-set agreement in message-passing systems[END_REF], Mostéfaoui, Raynal and Stainer define Alpha x as an extended, weaker version of the KA of [START_REF] Raynal | In search of the holy grail: Looking for the weakest failure detector for wait-free set agreement[END_REF]. Alpha x is a distributed object used to store values proposed by processes. It initially stores the default value ⊥. It provides processes with an operation Alpha.propose x (r, v) that returns a value (possibly ⊥). The round number r is a logical time and v is a proposed value. It is assumed that (a) each process will use increasing round numbers in successive invocations of Alpha.propose x () and (b) distinct processes use different round numbers. An Alpha x object is defined by the following properties:

• Termination: Any invocation of Alpha.propose x () by a correct process terminates.

• Validity: If Alpha.propose x (r, v) returns v = ⊥, then Alpha.propose x (r , v ) has been invoked with r ≤ r.
• Quasi-agreement: At most x different non-⊥ values can be returned by different invocations of Alpha.propose x ().

• Obligation: Let p l be a correct process and Q(l, τ ) = {p i ∈ C|∀τ i , τ l ≥ τ : qr τ i i ∩ qr τ l l = ∅}. If, after time τ , (a) only p l and processes of Q(l, τ ) invoke Alpha.propose x () and (b) p l invokes Alpha.propose x () infinitely often, then at least one invocation issued by p l returns a non-⊥ value.

Note that the termination property of Alpha x is not related to the termination property of the k-set agreement.

In order to ensure the safety properties of k-set agreement, it is not necessary to make use of the eventual partial leadership property of ΠΣ ⊥,x and therefore, the Alpha x algorithm presented here does not make use of the leader i variable. However, the k-set agreement algorithm implements the termination property of k-set agreement by relying on the obligation property of Alpha x and the eventual partial leadership property of ΠΣ ⊥,x .

The definitions in [START_REF] Bouzid | anti-Ω x × Σ z )-Based k-Set Agreement Algorithms[END_REF] and [START_REF] Mostéfaoui | Chasing the weakest failure detector for k-set agreement in message-passing systems[END_REF], that propose k-set agreement algorithms for static networks, use different obligation properties. The Alpha x in this thesis is the one defined in [START_REF] Mostéfaoui | Chasing the weakest failure detector for k-set agreement in message-passing systems[END_REF], which is weaker than the one in [START_REF] Bouzid | anti-Ω x × Σ z )-Based k-Set Agreement Algorithms[END_REF] by being Σ x -aware.

Alpha x Algorithm

This section proposes an algorithm implementing Alpha x for unknown dynamic systems model enriched with ΠΣ ⊥,x , adapted from the algorithm in [START_REF] Mostéfaoui | Chasing the weakest failure detector for k-set agreement in message-passing systems[END_REF].

The algorithm gives each proposed value a priority. Each process p i keeps a value est i , which is its current estimation of the value it will decide, and a pair (lre i , pos i ) which defines the priority of value est i . lre i is the highest round seen by p i and pos i is the position of value est i within round lre i . The position is used to fix priority on proposed values.

The function g(ρ, δ) = 2 δ (ρ -1) + 1 where ρ is the position of value v on round r and δ = r -r, with r ≥ r, is used to compute the position of v on round r .

If value v has priority ρ at round r and value v has priority ρ at round r with r ≤ r , v has lower priority than v at round r if and only if g(ρ, r -r) < ρ or (g(ρ, r -r) = ρ ) ∧ (v < v ).

The Alpha.propose x () function is composed of two phases. In the read phase (lines 4 -9), the process attempts to gather knowledge on the values proposed by other processes in a quorum (as defined by Σ ⊥,x ) by sending REQ_R messages and receiving RSP _R messages. If a process in the quorum is already computing a higher round, p i returns ⊥ (line 7). Otherwise, it selects the highest priority value it knows of (lines 8 -8), and proceeds to the write phase.

In the write phase (lines 10 -16), the process attempts to raise the priority of its current estimated value by communicating it to other processes in a quorum with REQ_W messages and receiving RSP _W messages. Once again, if any process in the quorum is computing a higher round, p i returns ⊥ (line 15). If another process has a value of higher priority for the current round, p i adopts it as its new estimated value (lines 16 -16). p i then raises pos i by 1 (line 11) and repeats the write phase until it manages to raise a value to position 2 r (line 10) or until it encounters a process in a higher round (line 15).

The following modifications were made to the original algorithm in [START_REF] Mostéfaoui | Chasing the weakest failure detector for k-set agreement in message-passing systems[END_REF] in order for the algorithm to ensure the properties of Alpha x in dynamic networks:

The original algorithm assumed a complete, static communication graph with reliable channels and therefore every message was only sent once. In an unknown dynamic system, messages need to be rebroadcast (lines 22, 23, 31 and 33). This mechanism ensures that (1) the emitting process will rebroadcast its own message every γ units of time; and (2) the reception of the message will not be restricted to the neighbors of the emitting process. The message will be received by every process that can be reached through a γ-journey.

Since messages are rebroadcast, the direct emitter of a message is not necessarily the source of the message. For this reason, the process identifier of the responding process was added in message types RSP_R and RSP_W.

Algorithm 3 Implementation of Alpha x using ΠΣ ⊥,x in dynamic networks for process p i .

1: init 2: lre i ← 0; est i ← ⊥; pos i ← 0 3: function Alpha.propose X (r,v i ) 4: repeat Q i ← qr i ; bcast REQ_R(r, Q i ) 5:
until Q i = ⊥ and ∀p j ∈ Q i : RSP_R(r, p j , lre j , pos j , val j ) received 6: rcv i ← { lre j , pos j , est j : p j ∈ Q i ∧ RSP_R(r, p j , lre j , pos j , est j ) received} 7:

if ∃ lre, -, -∈ rcv i : lre > lre i then return(⊥) 8:

pos i ← max{pos | r, pos, v ∈ rcv i }; est i ← max{v | r, pos i , v ∈ rcv i } 9: if est i = ⊥ then est i ← v i 10:
while pos i < 2 r do 11:

pos i ← pos i + 1; pst i ← pos i 12: repeat Q i ← qr i ; bcast REQ_W(r, pst i , est i , Q i ) 13:
until Q i = ⊥ and ∀p j ∈ Q i : RSP_W(r, pst i , p j , lre j , pos j , val j ) received 14: rcv i = { lre j , pos j , est j : p j ∈ Q i ∧ RSP_W(r, pst i , p j , lre j , pos j , est j ) received} 15:

if ∃lre : lre, -, -∈ rcv i : lre > lre i then return(⊥) 16:

pos i ← max{pos | r, pos, v ∈ rcv i }; est i ← max{v | r, pos i , v ∈ rcv i } 17: return(est i ) 18: upon reception of REQ_R(rd, Q) do 19: if p i ∈ Q then 20:
if rd > lre i then pos i ← g(pos i , rd -lre i ); lre i ← rd 21:

bcast RSP_R(rd, p i , lre i , pos i , est i )

22:

bcast REQ_R(rd, Q) 23: upon reception of RSP_R(rd, p j , lre j , pos j , est j ) do bcast RSP_R(rd, p j , lre j , pos j , est j ) bcast REQ_W(rd, pos, est, Q) 32: upon reception of RSP_W(rd, pos, p j , lre j , pos j , est j ) do 33:

bcast RSP_W(rd, pos, p j , lre j , pos j , est j )

The original algorithm uses a selective multicast for both the read and write phases, i.e., messages are sent only to the processes in a quorum Q i . This new algorithm uses broadcasts as defined in Section 3.1 (lines 4 and 12) and transmits Q i with the message. All receiving processes will rebroadcast the message, but only the processes within Q i will deliver it (lines 19 and 25).

Theorem 3.3. In unknown dynamic systems augmented with ΠΣ ⊥,x , Algorithm 3 ensures the properties of Alpha x .

Proof. The modifications added to the original algorithms from [START_REF] Bouzid | anti-Ω x × Σ z )-Based k-Set Agreement Algorithms[END_REF] and [START_REF] Mostéfaoui | Chasing the weakest failure detector for k-set agreement in message-passing systems[END_REF] do not allow the algorithm to add new values, therefore the proof for validity in the original papers holds. Similarly, the proofs for obligation in [START_REF] Mostéfaoui | Chasing the weakest failure detector for k-set agreement in message-passing systems[END_REF] and quasi-agreement in [START_REF] Bouzid | anti-Ω x × Σ z )-Based k-Set Agreement Algorithms[END_REF] do not rely on any static connectivity assumption, and instead rely on algorithm behavioural properties which were not altered in this new version. Therefore, the original proofs hold for Algorithm 3.

Concerning termination, the only possibility for an invocation not to terminate is that process p i waits forever for a response message in one of the repeat loops (lines 4-5 and 12-13). Assume by contradiction that p i waits forever for responses. The liveness property of ΠΣ ⊥,x ensures that eventually p i only sends queries to correct processes and waits for responses from correct processes. Given that the set of correct processes is finite, the set of possible correct quorums is finite too. It follows that there is a correct quorum Q such that infinitely often, qr i = Q, and therefore according to the quorum connectivity and self-inclusion properties of ΠΣ ⊥,x , there are recurrent journeys between any process in Q and p i . As a result, all the processes from Q will eventually receive the queries from p i , and p i will eventually receive the responses from the processes in Q, and, therefore, exit the repeat loop.

k-Set Agreement Algorithm

Given an Alpha x object and a ΠΣ ⊥,x,y failure detector, solving k-set agreement is simple. The algorithm given here is an adaptation of the one given in [START_REF] Mostéfaoui | Chasing the weakest failure detector for k-set agreement in message-passing systems[END_REF] for dynamic networks. x-Set agreement is first solved with ΠΣ ⊥,x (Algorithm 4), and then k-set agreement with ΠΣ ⊥,x,y for k ≥ xy.

Algorithm 4 x-Set agreement with Alpha x using ΠΣ ⊥,x in dynamic networks for process p i .

while dec i = ⊥ do 7: if leader i = p i then 8: dec i ← Alpha.propose x (r i , v i ) 9: r i ← r i × prime

bcast DECISION(d)

A well formed invocation of Alpha.propose x (r, v) is an invocation such that two processes cannot use the same round number r, and successive round numbers for a given process are increasing. To this end, each process p i initially computes prime i , the i th prime number. p i then uses prime i as its first round number, and multiplies it by prime i after every round. As a result, the round number of p i increases and is always a power of prime i , which ensures that two distinct processes always use distinct round numbers.

Theorem 3.4. In unknown dynamic systems augmented with ΠΣ ⊥,x and with an Alpha x object, Algorithm 4 solves the x-set agreement problem.

Proof. The test on line 6 ensures that the ⊥ value is never decided. From this point on, the validity of the Alpha x object is enough to ensure the validity of x-set agreement. Similarly, the quasi-agreement property of Alpha x is enough to ensure the agreement property of x-set agreement.

The eventual partial leadership property of ΠΣ ⊥,x ensures that if every leader in L decides, then eventually every correct process will receive a DECISION message from a process in L. As a result, the proof for the termination property provided in [START_REF] Mostéfaoui | Chasing the weakest failure detector for k-set agreement in message-passing systems[END_REF] holds for Algorithm 4.

Similarly to [START_REF] Mostéfaoui | Chasing the weakest failure detector for k-set agreement in message-passing systems[END_REF], a simple k-set algorithm can be obtained by running y instances of Algorithm 4, the j th one (1 ≤ j ≤ y) relying on the component F D i [j] of failure detector ΠΣ ⊥,x,y for every process p i . A process decides the same value decided by the first of the y instances that terminates. As there are y instances of the algorithm and each of them can decide x values at most, it follows that at most xy values can be decided. Therefore, the algorithm solves k-set agreement for k ≥ xy.

Conclusion

This chapter adapted the existing ΠΣ x,y failure detector to unknown dynamic systems by using the ⊥ default value to deal with missing information and by adding connectivity properties to the failure detector definition. The result is the ΠΣ ⊥,x,y failure detector, which is sufficient to solve k-set agreement in unknown dynamic systems with k ≥ xy.

An algorithm implementing ΠΣ ⊥,x,y in a Time-Varying Graph of class 5-(α, γ), relying on connectivity and message pattern assumptions, was presented.

Finally, an existing algorithm to solve k-set agreement was adapted for unknown dynamic systems augmented with ΠΣ ⊥,x,y (k ≥ xy). 58Chapter 4. The Weakest Failure Detector for Mutual Exclusion in Unknown Dynamic Systems other process may enter the critical section until p re-enters it after its recovery. Intuitively, this means that the lock on the critical section is not released in the case of a temporary crash.

This chapter considers RME on top of a message passing model, where each process has access to a volatile memory of unbounded size, which is lost after a crash and recovery, and a non-volatile memory (stable storage) of bounded size. This model is called the partial memory loss model.

In [START_REF] Delporte-Gallet | Mutual exclusion in asynchronous systems with failure detectors[END_REF], the T failure detector was shown to be the weakest failure detector to solve fault-tolerant mutual exclusion in message passing systems with a majority of correct processes (see Section 2.3.4.1). Then, in [START_REF] Bhatt | Extracting quorum failure detectors[END_REF], the (T , Σ l ) failure detector was shown to be the weakest failure detector to solve the same problem with no assumption on the number of process failures (see Section 2.3.4.2).

Both of these results are restricted to known, static systems without recovery. This chapter aims to extend these results to unknown dynamic systems where crashed processes can recover, with partial memory loss.

(T , Σ l ) is the sum of two failure detectors. It provides two outputs, one of which verifies the properties of T , and another one which verifies the properties of Σ l . Let T Σ l be the detector which provides a single output verifying the properties of both T and Σ l .

The contributions of this chapter are as follows:

1. A proof that (T , Σ l ) is equivalent to T Σ l (Section 4.2);
2. The definition of the T Σ lr failure detector, which is equivalent to T Σ l in known, static systems without recovery, and is the weakest failure detector to solve RME in unknown dynamic systems (Section 4.2); 3. A RME algorithm that runs on top of the proposed model using the T Σ lr failure detector and which tolerates crashes and recovery of processes, thus proving that T Σ lr is sufficient to solve RME in unknown dynamic systems (Section 4.3); 4. A reduction algorithm proving the necessity of T Σ lr to solve RME in unknown dynamic systems (Section 4.4).

Model and Problem Definition

This section presents the distributed system model used throughout the rest of the chapter and the definition of the Recoverable Mutual Exclusion (RME) problem.

System Model

The system is composed of a finite set of processes, denoted Π. Each process is uniquely identified. Additionally, processes are asynchronous (there is no bound on the relative speed of processes). They communicate by sending each other messages with a point-to-point send/receive primitive.

Communications are asynchronous (there is no bound on message transfer delay).

Failure Model

A process can crash (stop executing) during the run, and may recover from the crash, or not. A process can begin the run crashed, and start participating later in the run by recovering. Each process has access to both a volatile memory and a stable storage of bounded size. After a crash and recovery, the variables in volatile memory are reset to their initial default values. As each process has access to stable storage, this model is called the partial memory loss model. In the rest of the chapter, the names of variables in stable storage is underlined.

A process is said to be alive at time t if it never stopped executing before t or if it recovered since the last time it stopped executing. A process which is not alive at time t is said to be crashed at time t.

In the traditional crash failure model, processes are grouped into faulty processes, which eventually crash, and correct processes, which never crash. However, in a crash-recovery model, in any run, three types of processes are considered[ACT00]:

1. Eventually up processes, which stop crashing after some time and remain alive forever.

This type also includes processes that never crash (always up).

2. Eventually down processes, which eventually crash and never recover. This type also includes processes that crashed immediately at the start of the run and never recovered (always down).

3.

Unstable processes, which crash and recover infinitely often. It is assumed that, infinitely often, each unstable process manages to stay alive long enough to at least send a message to each other process of which it is aware.

Connectivity Model

The system is dynamic in the sense that the edges in the communication graph can appear and disappear during the run. In other words, at any given time instant, each edge in the graph might or might not be available. Without any further assumption, a system in which no edge is ever available would fit this model. Since nothing can be computed in such a system, additional assumptions are needed. Therefore, the following properties are assumed to be verified:

• Dynamic connectivity: Every message sent by a process that is not eventually down to a process that is not eventually down is received at least once.

• Uniqueness of reception: Every message sent is received at most once.

• First in, first out: If process p sends a message m 1 to q and then sends m 2 to q, if q receives m 2 then it received m 1 first.

These properties imply not only that channels are reliable, but also that each pair of processes that are not eventually down is connected infinitely often by a path over time. This means that when a process p sends a message to process q, then there is a path from p to q such that at some point in the future, every edge on this path will be available in the correct order, and sufficiently long for the message to cross the edge. Note that it is not necessary that all the 60Chapter 4. The Weakest Failure Detector for Mutual Exclusion in Unknown Dynamic Systems edges on the path to be available at the same time, and the path that a pair of processes uses to communicate is not required to be the same every time. This connectivity assumption is referred to as a Time-Varying Graph of class C 5 in [START_REF] Casteigts | Time-varying graphs and dynamic networks[END_REF].

The algorithms presented in this chapter assume that the underlying send/receive implementation handles message forwarding and, therefore, behaves the same way that it would in a complete communication graph with reliable channels.

Knowledge Model

The system is unknown, i.e., processes initially have no information on system membership or the number of processes of the system, and are only aware of their own identity. The identities of other processes can only be learned through exchanging messages. More practically, each process p has access to a local variable known p (in stable storage) that initially contains only p. Eventually, known p contains the set of all processes that are not eventually down. For the sake of simplicity, the algorithms in this chapter do not attempt to define the known p variable and simply assume that an underlying discovery algorithm eventually fills it with the necessary process identities. This is not a strong assumption, since the dynamic connectivity property ensures that all processes will be able to communicate (and therefore learn of each other's existence) infinitely often.

Problem Definition

This chapter considers the Recoverable Mutual Exclusion (RME) problem, which is defined as follows. At any point in time, a process is either in the remainder, try, critical, or exit section. Every user is well-formed, that is that a user will go through the remainder, try, critical and exit sections in the correct order. In case of a crash and recovery, a well-formed user will restart in the critical section if it was in the critical section when it crashed, and will restart in the remainder section, otherwise (the critical section re-entry property of [START_REF] Golab | Recoverable mutual exclusion in sublogarithmic time[END_REF]).

A RME algorithm must provide a try section and an exit section procedures such that the following properties are satisfied:

• Safety: Two distinct alive processes p and q can not be in CS at the same time.

• Liveness: If an eventually up process p stopped crashing and is in the try section, then at some time later some process that is not eventually down is in CS.

Additionally, the following fairness property is considered:

• Starvation Freedom: If no process stays in its critical section forever, then every eventually up process that stopped crashing and reaches its try section will eventually enter its CS.

Note that stable storage is necessary to solve this problem. Indeed, if a process p is in the critical section when all processes simultaneously crash, without stable storage there is no way for p to re-enter critical section after recovery since no process in the system remembers that p was in the critical section in the first place.

Failure Detectors for Mutual Exclusion in Unknown Dynamic Systems

4.2.1 The T Σ l Failure Detector (T , Σ l ) provides two outputs, tr p and qr p , with tr p verifying the properties of T and qr p verifying the properties of Σ l . T Σ l is the failure detector that provides a single output tq p verifying the properties of both T and Σ l .

Theorem 4.1. (T , Σ l ) is equivalent to T Σ l .
Proof. (T , Σ l ) can be implemented using the output of T Σ l : it suffices to always return the value of tq p as both tr p and qr p . Therefore, (T , Σ l ) is weaker than T Σ l . (T , Σ l ) is sufficient to solve mutual exclusion, as shown in [START_REF] Bhatt | Extracting quorum failure detectors[END_REF]. Section 4.4 will prove that it is possible to use RME to implement the T Σ lr failure detector (defined in Section 4.2.2). The same reasoning and algorithms that are used in Section 4.4 can be used to show that it is possible to use FTME to implement T Σ l . It follows that (T , Σ l ) is sufficient to implement T Σ l , and as a result, T Σ l is weaker than (T , Σ l ).

The T Σ lr Failure Detector

The existing definition of T Σ l is for static, known networks, and therefore new definitions, suitable for unknown dynamic networks, must be provided.

In an unknown system, the lack of initial information renders difficult the implementation of some failure detector properties which must apply from the start of the run, in particular the intersection property. To circumvent this problem, the ⊥ concept introduced in [RAS15] is used.

Additionally, the traditional properties of T Σ l are expressed in terms of correct and faulty processes. T Σ lr was rewritten using the concepts of eventually up and eventually down processes instead.

The T Σ lr failure detector provides each process p with a set of trusted process identities, denoted tq p , and a flag denoted rdy p . rdy p is initially set to ⊥ and changes to once the failure detector has gathered enough information to verify the live pairs intersection property. tq t p denotes the value of tq p at time t, and rdy t p the value of rdy p at time t. Process p is said to trust process q at time t if q ∈ tq t p , p is said to suspect q at time t if q / ∈ tq t p , and process p is said to be ready at time t if rdy t p = . The following properties must be verified.

• Eventually strong accuracy: Every eventually up process p is eventually trusted forever by every process that is not eventually down.

• Strong completeness: Every eventually down process p is eventually suspected forever by every process that is not eventually down.

• Trusting accuracy: For any process p, if there exist times t and t > t such that q ∈ tq t p and q / ∈ tq t p , then q is eventually down and will never be alive after t .

• Quorum readiness: Every eventually up process is eventually ready forever.

Algorithm 5 Solving RME with T Σ lr : code for process p 1: procedure try section if req p = true then send(request, round p , q) 33: when q removed from tq p 34:

grants p ← grants p \ {q} 35: requests p ← requests p \ {( * , q)} 36: update p ← update p \ {q} 37:
if gid p = q then 38:

(gid p , grnd p ) ← (-1, -1) if crit_src = f alse and gid p = src then 59:

(gid p , grnd p ) ← (-1, -1) round p ← 0: the local round number of p, which is used to number its requests. It is also used to define the current priority of p to access the critical section.

last_round p ← ∅: a table associating each known process identity with its last known round number. It is used to restore the round number of other processes after they crash and recover.

req p ← f alse: a flag indicating that p is currently in the try section. requests p ← ∅: the set of requests received by p which are pending. Each request is a couple (round, pid).

gid p ← -1: the identity of the last process to which p granted its permission, or -1 if p did not grant it. It indicates that p sent a grant message to gid p , and that this permission was not canceled by the reception of a done or reject message yet.

grnd p ← -1: the current round number of the process to which p granted its permission, or -1 if p did not grant it.

grants p ← {p}: the set of processes from which p received a grant message. recovering p ← f alse: a flag indicating that p is currently attempting to rebuild its volatile memory after a crash. Calls to try section and exit section will be delayed while recovering p = f alse. update p ← ∅: the set of processes from which p waits for an update message. This variable is only used during the recovery phase, i.e., while recovering p = true.

All of these local variables, except for crit p , are stored in volatile memory. This means that after a crash and recovery, they are reinitialized to the above default value.

Requests are totally ordered by their priority, which is defined as follows: priority(round p , p) > priority(round q , q) ⇔ round p < round q or [round p = round q and p < q]. The highest function takes a list of requests and returns the couple (round, id) of the request with the highest priority among the trusted processes according to tq p .

The check requests procedure is extensively used in Algorithm 5. Provided that process p did not already grant its permission to another process and is not in CS, check requests compares the requests that p received so far by calling the highest function (line 18), and sends a grant message to the process with the highest priority (line 19). In case p received grants from other processes before granting its own permission, it will send reject messages to the processes in grants p in order to prevent a deadlock (lines 20 -22).

Whenever process p wants to access the critical section, it executes the try section: p increments its round p , resets its grants p set (line 4), and then broadcasts a request to every process in tq p (line 5). If p gets knowledge of a new process while it is still in the try section, the request will also be sent to this process (line 32). Process p adds its own request to its requests p before calling check requests (lines 6 -7), and finally waits for permissions from every process in tq p (and its own permission, line 8) before entering CS.

Upon reception of a request message from process q (lines 40 -43), process p updates its knowledge about q's round number and adds the new request to its requests p set. It then calls check requests to decide if it should send a grant to the new requester.

When receiving a grant message from process q, if p already granted its permission to some other process then it informs q by responding with a reject message to prevent deadlocks (line 46). Otherwise, if p is not in the recovery phase, it accepts q's permission by adding it to its grants p set. Upon finishing the critical section and calling exit section, p sends to all trusted processes a done message (line 13). Then, p resets its grants p set and cancels its request (line 50) before calling check requests to grant its permission to the next process.

If p receives a done or reject message from process gid p , it cancels the permission granted to gid p (lines 51 and 54) and calls check requests. In the case of a done message, the request from gid p is also deleted from requests p (line 50), since gid p is not requesting CS anymore. However, in the case of a reject, the request from gid p is still valid and must be kept, even if it is not the highest priority request.

If p crashes and recovers, the reconnection procedure will be called first. This procedure initiates the recovery phase (lines 24 -29) by switching the recovering p flag to true, which will temporarily prevent the algorithm from going into the try or exit sections (lines 2 and 11) and from sending or accepting a grant (lines 17 and 47). During the recovery phase, p attempts to recover the information it lost during the crash by sending a comeback message to every process in tq p . Other processes will send update messages in response, which enables p to restore its last_round p , round p , gid p , grnd p , and requests p variables (lines 63 -71). The recovery phase ends when every process to which p sent a comeback has either responded with an update message (line 71), or crashed (line 36). After recovering, p calls check requests in order to choose a process to which it will grant its permission (line 30).

If p receives a comeback message from a process q, it cancels any request previously received from q, since a process in recovery phase can only be in the remainder or critical section (by definition of a well-formed process). If q is in its remainder section (crit p = f alse), then p cancels any permission it might have granted to q previously (lines 58 -60). Finally, p sends an update message to q.

Whenever p is informed by the failure detector that a process q is eventually down (lines 33 -39), p deletes q from its requests p , grants p and update p sets. If q was the process to which p granted permission, then p cancels the permission (line 38) and calls check requests to grant its permission to another process, if appropriate.

Proof of Correctness

This section will prove, through the following claims, that any run of Algorithm 5 solves the RME problem.

Claim 4.1 (Safety). Two distinct alive processes p and q can not be in CS at the same time.

In order to prove Claim 4.1, the following lemmata are required. Lemma 4.1 (Uniqueness of the permission). Let p, q 1 , q 2 be three distinct alive processes. If p ∈ grants q 1 at a time t then p cannot send a grant message to q 2 at time t.

Proof. The only way that p can send a grant message to a process q is on line 19, after it selected q as its gid p . Note that the definition of the highest function also implies that q ∈ tq p at the time when the grant message is sent.

Suppose that p has sent a grant message at time t G to another process q 1 (and therefore at time t G , gid p = q 1 ). Assume that there is a time t > t G such that p ∈ grants q 1 . Then suppose that p sends a grant message to another process q 2 at time t.

In order to send a grant message to q 2 , p has to set gid p to -1 or to p at some time t ∈ [t G , t] (otherwise p cannot pass the test on line 17). This affectation can only be done in one of the following lines:

Line 38: then q 1 / ∈ tq t p . Since q 1 ∈ tq t G p , according to the trusting accuracy property of T Σ lr , q 1 has crashed at some time before t and will never recover. It is therefore impossible that p ∈ grants q 1 at time t.

By resetting gid p to -1 after a crash. If p crashed between t G and t , then its gid p got reset to -1. This also means that p entered the recovery phase (lines 24 -29) at some time t ∈ [t G , t ]. Since q 1 ∈ tq t G p , then according to the trusting accuracy property of T Σ lr , either q 1 crashed before t and will never recover (which is a contradiction), or q 1 ∈ tq t p . p will therefore send a comeback message to q 1 on line 27, and q 1 will respond with a update message with the grant_src parameter set to true, which will cause p to set its gid p back to q 1 . Since p cannot have sent a grant message while in the recovery phase (because of the test on line 17), then p cannot send the grant to q 2 at time t which is a contradiction.

Line 59: then p received a comeback message from q 1 at some time t ∈ [t G , t ]. This means that q 1 crashed and went into the recovery phase. p will respond with an update message to q 1 . Since q 1 cannot leave the recovery phase until it receives p's update and because of the first in, first out property, then p's grant message to q 1 was received either (1) before q 1 crashed, in which case the grant was forgotten, or (2) during the recovery phase, in which case q 1 will ignore the grant because of the test on line 47. In both cases, p / ∈ grants q 1 after t , which is a contradiction.

Line 51 or 54: then p received a done or reject message from q 1 at time t . There are two cases. If q 1 sent the done or reject message after receiving the grant, then q 1 removed p from grants q 1 on line 14 (resp. line 21) and did not add it back in afterwards, which is a contradiction. Otherwise, q 1 sent the done or reject message before receiving p's grant. Since q 1 only sends done or reject messages to processes from which it previously received a grant, then p sent another grant message to q 1 before t G . This means that p sent two consecutive grant messages to q 1 without receiving a done or reject message in between. The only way this could happen is if p set its gid p to -1 or p between sending the two grant messages without receiving a done or reject, which is a contradiction since this proof eliminated every other way of doing that.

Hence, p can not be grants q 1 while p sends a grant message to q 2 at the same time, which conclude the proof of Lemma 4.1 . Lemma 4.2 (Self permission). Let p, q be two distinct alive processes. If p ∈ grants q then p can not enter CS.

Proof. If p ∈ grants q , then p sent a grant message to q and therefore set its gid p to q. The reasoning of the proof for Lemma 4.1 can be used to show that p cannot change the value of its gid p until q has removed p from its grants q .

Since p is required to have its gid p set to p in order to enter CS (line 8), then it is impossible for p to enter CS until after q removed p from grants q . Claim 4.1 can now be proved by contradiction.

Proof. Let p 1 , p 2 be two alive, distinct processes. Suppose that p 1 enters CS at time t 1 , and p 2 enters CS at time t 2 . Suppose that neither process leaves CS until after the other process has entered it. According to the live pairs intersection property of T Σ lr , there is a process q such that q ∈ tq t 1 p 1 ∩ tq t 2 p 2 . It follows from the wait condition on line 8 that q ∈ grants p 1 at time t 1 and q ∈ grants p 2 at time t 2 . There are two cases:

First case: p 1 , p 2 and q are all distinct. Therefore, q sent a grant message to p 1 before t 1 and a grant message to p 2 before t 2 . Additionally, neither process removed q from their grants set before entering CS. Without loss of generality, assume that q sent the grant message to p 1 first. There could be a run in which p 1 received the message immediately, and therefore added q to grants p 1 before q sent the second grant to p 2 . In this run, q sends a grant message to p 2 while q ∈ grants p 1 at the same time, which is in contradiction with Lemma 4.1.

Second case: q = p 1 or q = p 2 . Without loss of generality, assume that q = p 1 . Since q ∈ grants p 2 at time t 2 , q sent a grant message to p 2 before t 2 . Since it is impossible for q to send a grant message while in CS (because of the test on line 17), it follows that q sent the grant before entering CS. There could be a run in which p 2 received the grant immediately after it was sent, therefore adding q to grants p 2 before q entered CS, which is in contradiction with Lemma 4.2.

Claim 4.2 (Starvation freedom). If no process stays in its critical section forever, then every eventually up process that stopped crashing and reaches its try section will eventually enter its CS.

To prove the Claim 4.2, the following lemmata is required: Lemma 4.3 (Deadlock-free). Assuming that no process stays in CS forever, if a process p, which does not have the highest priority among the requesting processes, receives at least one grant from another process q, p will eventually either crash forever or remove q from grants p , and q will eventually either crash forever or set gid q to -1.

Proof. Let p be a process in its try section at time t. There exists a distinct process p h which is also in its try section at time t and has the highest priority among requesting processes.

Let q be a process distinct from p that sends a grant message that p receives at time t. It follows that p sent a request message to q at some time t R < t.

One of the following cases applies: 1) p is eventually down, and q is not. Then according to the strong completeness property of T Σ lr , p will eventually be removed from tq q and q will set gid q to -1 on line 38.

2) q is eventually down, and p is not. Then according to the strong completeness property of T Σ lr , q will eventually be removed from tq p and p will remove q from grants p on line 34.

3) At time t, gid p = -1 and gid p = p. Then when p receives q's grant message, it will never add q to grants p and will send q a reject message instead (line 46). When q receives the reject message, it will set gid q to -1 (line 54). 4) At time t, gid p = -1. When p calls check requests, it will pass the test one line 17 since requests p contains at least p's request, and crit p and recovering p cannot be true while in CS. p will then set gid p to something different from -1 on line 18. 68Chapter 4. The Weakest Failure Detector for Mutual Exclusion in Unknown Dynamic Systems It follows from the cases above that the only way Lemma 4.3 could be false is if neither p nor q are eventually down, and gid p = p at time t. Since p is not eventually down, then p will eventually receive p h 's request at some time t > t. Then one of the following cases applies:

1) During [t R , t ], p does not crash, receives grant messages from every process in tq p , and rdy p is set to . Then p will end the wait on line 8 and enter CS. When p leaves CS, it will remove q from grants p on line 14 and send a done message to q on line 13. When q receives the done message, it will set gid q to -1 on line 51.

2) During [t R , t ], p does not crash and does not receive enough grant messages to enter CS (or rdy p stays equal to ⊥). Then at time t when p receives p h 's request, it will call check requests on line 43. p will pass the test on line 17 and, since p h is the requesting process with the highest priority, p will set gid p to p h . It will then remove q from grants p on line 21 and send a reject message to q on line 22. When q receives the reject message, it will set gid q to -1 on line 54.

3) During [t R , t ], p crashes before receiving enough grant messages to enter CS. When p recovers, its grants p set is reinitialized and does not contain q. Since q was previously in tq p and q is not eventually down, it follows from the trusting accuracy property of T Σ lr that q is still in tq p after p recovers. p will therefore send a comeback message to q on line 27 with the crit_src parameter set to f alse. When q receives the comeback message, it will set gid q to -1 on line 59. Note that because of the first in, first out property, q will necessarily receive p's request before the comeback message. Additionally, p will receive q's grant message before q's update message, and will ignore the grant because of the test on line 47. Lemma 4.4 (Decreasing priority). Assuming that no process stays in the CS forever, if an unstable process p is in the try section infinitely often, then the value of round p increases infinitely often (and therefore, p's priority decreases infinitely often).

Proof. Let p be an unstable process that is in the try section infinitely often. By definition, p also crashes infinitely often. Let q be any eventually up process. According to the eventually strong accuracy property of T Σ lr , p will eventually trust q forever. Let t 0 be a time after which every eventually down process crashed permanently, every eventually up process stopped crashing, and p started trusting q. According to the strong completeness property of T Σ lr , there is a time t 1 ≥ t 0 such that ∀t > t 1 , tq t p does not contain any eventually down process. Let t 2 > t 1 be the first time after t 1 that p crashes, and let t 3 > t 2 be the first time after t 2 that p enters the try section.

Every request sent by p after t 3 is sent only to processes that are not eventually down, including q. According to the dynamic connectivity property, q will receive every request sent by p after t 3 . Every time that p crashes after t 3 , p will send a comeback message to q. Because of the first in, first out property, q will receive p's last request before receiving the comeback message, and therefore when q receives the comeback its last_round q [p] will be up to date with q's latest round p value from before the crash. q will then respond with an update message, and p will update its round p value on line 63 before leaving the recovery phase. As a result, crashes after t 3 do not reduce or reset p's round p value.

At any time t > t 3 , there are three possibilities:

1) p is in the exit or remainder section at time t. By assumption, p will eventually enter the try section, and therefore increase its round p value on line 4.

2) p is in the CS at time t. Since by assumption no process stays in the section forever, p will eventually leave CS and the case above applies.

3) p is in the try section at time t. Eventually, p will either enter CS (and the case above applies), or p will crash before entering the CS and therefore it will be in the remainder section after recovery (and the first case applies).

In all cases, there is a time t > t such that round p increases at time t .

Lemma 4.5 (Highest priority starvation freedom). Let t be a time after all eventually up processes stopped crashing. Assuming that no process stays in CS forever, if an eventually up process p is in the try section and has the highest priority among requesting eventually up processes at time t, then eventually p enters CS.

Proof. Let p be an eventually up process that is in the try section with the highest priority among requesting eventually up processes at time t. By contradiction, assume that p never enters CS after t. It follows that p will never leave the try section, since it will neither crash nor enter CS. Therefore, p will never re-enter the try section and increase its round p value on line 4. It follows that p's priority will never change after t. Let q 1 be any unstable process. According to Lemma 4.4, q 1 will either eventually stop entering the try section (in which case its priority becomes irrelevant), or q 1 's priority will be reduced infinitely often, in which case p's priority will eventually be higher than q 1 's. As a result, there is a time t ≥ t after which p has the highest priority of all requesting processes in the system.

If gid p = q 2 with q 2 distinct from q after t , then according to Lemma 4.3, eventually p will set its gid p to -1 and then call check requests. p will then set itself as gid p on line 18 and will never change gid p again.

According to the dynamic connectivity property, eventually every process in tq p will have received p's request. Let q 3 be any process that received p's request. If gid q 3 = -1 and gid q 3 = q 3 , then after t , according to Lemma 4.3, q 3 will eventually set gid q 3 to -1. When gid q 3 is equal to -1 or q 3 after t , then q 3 will set it to p on line 18 and send a grant message to p on line 19. As a result, p will receive a grant message from every process in tq p .

Since p is eventually up, according to the quorum readiness property of T Σ lr , the eventually rdy p = .

Finally, p will pass the wait condition on line 8 and enter CS, which is a contradiction.

Claim 4.2 can now be proved.

Proof. Let p be an eventually up process that stopped crashing and is in its try section at time t. By contradiction, assume that p never enters CS after t. It follows that p will never leave the try section, since it will neither crash nor enter CS. Therefore, p will never re-enter the try section and increase its round p value on line 4. It follows that p's priority will never change after t, and that every requesting unstable process will eventually have a lower priority than p. Let Q be the set of all requesting eventually up processes with higher priority than p. Let q be the process in Q with the highest priority. It follows from Lemma 4.5 that eventually, q will 70Chapter 4. The Weakest Failure Detector for Mutual Exclusion in Unknown Dynamic Systems enter CS. After q leaves CS, it will either (1) stop requesting forever (and therefore leave Q) or (2) enter the try section again and therefore decrease its priority. By induction, q will eventually not have the highest priority amongst requesting processes anymore, and another process in Q will take its place. As a result, eventually Q will become empty since every process in it will either stop requesting or increase its priority infinitely often.

Finally, p will become the requesting eventually up process with the highest priority, and according to Lemma 4.5, will enter CS, which is a contradiction. Claim 4.3 (Liveness). If an eventually up process p stopped crashing and is in the try section, then at some time later some process that is not eventually down is in CS.

Proof. Let p be an eventually up process that stopped crashing and is in the try section. There are two possibilities:

• Some process eventually stays in CS forever. In this case, liveness is ensured.

• Otherwise, according to Claim 4.2, p will eventually enter CS, thus ensuring liveness.

Necessity of T Σ lr to solve Fault-Tolerant Mutual Exclusion

This section proves that the T Σ lr failure detector is necessary to solve the RME problem in any unknown dynamic system with partial memory loss. For this purpose, it can be assumed that there is an unknown dynamic system model M RME with partial memory loss, in which RME can be solved with some algorithm A RME . The following proof will then show that the properties of T Σ lr can be implemented in M RME .

Although the purpose of this section is to show that T Σ lr can be implemented with RME in M RME , the same arguments and algorithms used here can also be used to show that T Σ l can be implemented with fault-tolerant mutual exclusion in a static, known system without recovery. As a result, this section is also a part of the proof for Theorem 4.1.

The following proof is inspired by the proofs for the necessity of T and Σ l in [DGFGK05] and [START_REF] Bhatt | Extracting quorum failure detectors[END_REF], respectively. The main additional challenge is to merge the two proofs, since both trusting and quorum properties must apply for a same set tq p .

The proof uses two algorithms, both of which share the following local variables: trust p ← {p} is the set of all processes that process p has heard of and that it does not suspect. This variable is in stable storage.

start p ← f alse is a flag used to delay the start of the RME algorithm. Proof. The only difference between A RME and B RME that could prevent B RME from solving RME is the wait on lines 2 and 5. A process that never sets start p to true cannot participate in the algorithm. By assumption, this is only a problem for processes that are not eventually up. If a process never sets start p to true, then for the purpose of B RME , that process behaves exactly as an always down process would behave in a run of A RME .

Algorithm 7 can now be introduced, which makes use of A RME and B RME to implement the properties of T Σ lr .

In addition to trust p and start p , Algorithm 7 uses following local variables: known p ← {p}: as discussed in Section 4.1, known p represents the knowledge that p has of other processes in the system. The algorithm does not show how known p is kept up to date, but simply expects that known p will eventually contain the process identities of (at least) all eventually up processes. crash p ← ∅: the set of all processes that p is certain have crashed forever. Note that this variable is in stable storage.

tq p ← ∅: the output of the T Σ lr failure detector, which verifies the trusting and quorum properties.

rdy p ← ⊥: the other output variable of T Σ lr , which verifies the quorum properties. waitlist p ← ∅: the set of processes to which p must grant permission for CS. This is used to ensure starvation freedom. Note that this variable is in stable storage.

donelist p ← ∅: the set of processes to which p already granted permission for CS. It prevents p from always being passed over for CS access.

Algorithm 7 initially starts two tasks in parallel: task 1 and task 2. Later on, whenever process p gets knowledge of a process q, it starts a new task for q (denoted task 3 + q).

Each process p has its own CS, which is handled by algorithm for q ∈ trust p do 30:

Start task 3 + q 31: when q = p is added to trust p 32:

Start task 3 + q 33: upon reception of alive (req, trust_src) from src do if rdy p = ⊥ then 43:

tq p ← trust p \ crash p
In task 1, p enters its own CS and then never leaves it. Since in this case a well-formed process restarts in the CS after a recovery, this means that a recovering process will restart task 1 directly after line 2 if it previously managed to enter its own CS. This enables other processes to detect p's failure if it crashes permanently (if another process manages to access p's CS in task 3 + p, it means that p crashed forever). In task 1, p also sends information to the rest of the system about its own identity and whether or not p is trying to access the global CS. These alive messages are used by other processes to keep trust p , waitlist p , and donelist p up to date.

In task 2, p tries infinitely often to access the global CS. The wait on line 9 helps to ensure that the global CS starvation freedom property is satisfied. After entering and leaving the global CS, if p entered it using only messages from processes that are not crashed (test on line 15), then p updates its T Σ lr output variables and informs other processes with quorum messages. However, if p used information from crashed processes to enter CS, it removes them from its trust p set. task 3 + q is started by p when q is added to trust p , and is used to detect q's permanent crash.

When a process p receives a quorum message, it updates its local trust p and crash p information and, if rdy p is currently ⊥ (and therefore p is not currently trying to verify the live pairs intersection property), then p updates its tq p . Lemma 4.7 (Starvation freedom). Every eventually up process passes the lines 12 -13 infinitely often.

Proof. By contradiction, assume that there is an eventually up process p which does not go through CS infinitely often. There are two ways this could happen: p is either stuck in the wait on line 9 forever, or p is stuck in try section on line 12 forever.

First assume that p is stuck in try section forever. Since the liveness property of RME is verified, and since no process can stay in CS forever (since the CS has no code), it follows that there is a process q that enters CS infinitely often.

Eventually, p ∈ known q and q ∈ known p . Since p set req p to true on line 11, then eventually q will receive an alive message from p with req set to true, and q will add p to waitlist q . Because of the first in, first out property, q will eventually stop receiving any alive message from p that has the req value set to f alse. Since q passes the line 10 infinitely often, eventually p / ∈ donelist. Since p ∈ waitlist q \ donelist q , then eventually q will wait forever on line 9, which is a contradiction. Now assume that p is stuck on line 9 forever. Let W be the set of processes that stay in waitlist p \ donelist p for infinitely long. Note that a process q that is not stuck forever in the try section on line 12 would have their req set to f alse and therefore would send an alive message to p with req set to f alse, and would be removed from waitlist p \ donelist p as a result. It follows that every q ∈ W is stuck forever on line 12. If q is eventually down, it eventually crashes forever and therefore cannot be in W . If q is eventually up, according to the previous paragraph it eventually enters CS and therefore cannot be in W . If q is unstable, it eventually crashes and resets its req q to f alse, and therefore cannot be in W . As a result, W is empty and p eventually ends the wait on line 9. Lemma 4.8 (Crashed completeness). A process can only be added to crash p if it crashed forever.

Proof. A process can only be added to crash p on lines 26 and 41. In order for p to add a process to crash p on line 41, some other process q must have added it to crash q on line 26 first.

In order for p to add a process q to crash p on line 26, p must first have started task 3 + q. This can only happen if p added q to trust p . A process can be added to trust p on lines 34 and 40, or by receiving information from q as part of algorithm B RME . If q sent a quorum message, then it must have passed the CS on lines 12 -13 and therefore sent or received information as part of algorithm B RME , which means that start q was set to true. Whether q set start q to true on line 3 or sent an alive message on line 6, it had to enter its own CS on line 2 first.

Since q entered its own CS before p started task 3 + q and will never leave it, the only way that p can reach line 26 and add q to crash p is if q crashed forever. Proof. Let p be an eventually down process, and q be a process that is not eventually down. Note that by construction, a process can never be added to tq q without being added to trust q first. There are two cases:

p was never added to trust q . Then the property is immediately verified. p was added to trust q . Let r be some eventually up process. Eventually, q will send an alive message to r which contains trust q . Therefore, r will eventually add p to its trust r and will then start task 3 + p. After p crashes forever, eventually r will reach line 26 and add p to crash r .

Let t 1 be a time after which all eventually down processes have crashed. Let t 2 ≥ t 1 be a time after which there are no more messages sent by eventually down processes in the system. After t 2 , neither q nor r will ever add an eventually down process into their trust set again. According to Lemma 4.7, r will then eventually remove all eventually down processes from trust r on line 21. Since according to Lemma 4.8 only eventually down processes can be in crash r , after this time r will always pass the test on line 15 and therefore r will send a quorum message to q infinitely often.

If q goes through the loop in task 1 infinitely often, it will act like r and eventually never have p in its tq q . If q is unstable and does not go through the loop in task 1 infinitely often, then after it stops going through the loop it will crash and reset its rdy q to ⊥. Then, the next time that q receives a quorum message from r, it will add p to crash q and remove it from tq q on line 43 Claim 4.5 (Eventually strong accuracy). Algorithm 7 ensures the eventually strong accuracy property of T Σ lr in M RME .

Proof. Let p be an eventually up process, and q a process that is not eventually down. Eventually, q ∈ known p . According to the liveness property of RME, p will eventually enter its own CS and send an alive message to q on line 6. When q receives the message, it will add p to its trust q set on line 34. It follows from Lemma 4.8 that p will never be in crash q . According to the proof for Claim 4.4, q will update its tq p infinitely often with trust q , either on line 16 or on line 43. As a result, p ∈ tq q forever. Claim 4.6 (Trusting accuracy). By construction, the only way that a process can be removed from tq p is by being added to crash p . The proof then follows directly from Lemma 4.8. Claim 4.7 (Quorum readiness). Algorithm 7 ensures the quorum readiness property of T Σ lr in M RME .

Proof. Let p be an eventually up process. According to the proof for Claim 4.4, p will pass the test on line 15 infinitely often. After p stops crashing, the next time it reaches line 17, it will set rdy p to forever. Lemma 4.9 (Message reception intersection). Let p 1 and p 2 be two processes that enter the CS of B RME at time t 1 (resp. t 2 ). Let Q 1 (resp. Q 2 ) be the set of all processes from which p 1 (resp. p 2 ) received information from (directly or through forwarding) since the last time it entered the try section before t 1 (resp. t 2 ). Then either one of the process crashed permanently before the other entered CS, or

Q 1 ∩ Q 2 = ∅. Proof. By contradiction, assume that Q 1 ∩ Q 2 = ∅.
First assume that in B RME , a process r might send a message to a process s to authorize s to enter CS before s has entered the try section. In this case, it is possible that every process in the system would send such a message to s before s enters the try section. Now consider a run in which a process s different from s later enters the try section. If B RME allows some process to authorize s , then all other processes might do the same thing. As a result, if s is not permanently crashed, s and s might enter CS at the same time, thus violating the safety property. If B RME does not allow any process to authorize s , then s might never enter the try section, thus violating the liveness property. It follows that in B RME , only messages received after entering the try section can authorize a process to enter CS. Now consider a run in which every message between Q 1 and Q 2 is delayed until after both p 1 and p 2 have left CS. This means that the system is partitioned, and therefore algorithm B RME cannot possibly prevent a run in which both p 1 and p 2 enter CS at the same time, thus violating the safety property of RME. Proof. The live pairs intersection property only applies when rdy p is set to , and the only way to set rdy p to is on line 17. Since lines 28 and 43 can only be reached when rdy p is set to ⊥, it follows that at any time rdy p is equal to , the current value of tq p was set on line 16.

Note that tq p is set from trust p on line 16 after p recently went through the global try, critical, and exit sections with B RME on lines 12 -13. By construction, every process from which p received information (even indirectly) in B RME since last entering the try section is in trust p at that time. Observe also that the only way to remove a process identity from trust p is on line 21, which cannot be reached between lines 12 and 16.

Let p 1 and p 2 be two processes, and let t be some time at which both are alive. Then for any time t 1 ≤ t when p 2 reached line 16 and any time t 2 ≤ t when p 2 reached line 16, it follows from Lemma 4.9 that trust p 1 at time t 1 and trust p 2 at time t 2 intersect.

From Claims 4.4 to 4.8, the following theorem can be deduced:

Conclusion

This chapter adapted the (T , Σ l ) failure detector into the T Σ lr failure detector adapted to unknown dynamic systems with partial memory loss and where faulty processes may recover. T Σ lr was proved to be both necessary and sufficient to solve the RME problem in such systems and it is, therefore, the weakest failure detector to solve RME in unknown dynamic systems with partial memory loss.

Additionally, this chapter showed that the properties of (T , Σ l ) can apply to two separate output variables or to a single one, without changing the strength of the failure detector. Unknown dynamic systems pose new challenges to the field of distributed computing, and failure detectors in particular. The lack of initial information in an unknown system, along with the dynamics of the set of processes and the communication graph, prevent existing failure detector results from being applied to these new systems. For instance, some detectors, such as Σ and Σ l , can not be implemented without initial information on the participants in the system. Additionally, in order to be implemented, all failure detectors require a specific level of temporal graph connectivity. Furthermore, even in a system enriched with a failure detector, no problem can be solved without the assumption of some level of temporal graph connectivity that is specific to the problem. In other words, if the processes in the upper layer application can not communicate with each other, then no problem can be solved even with perfect information on failures.

This thesis addressed these challenges by providing new definitions of previously existing failure detectors that are suitable to unknown dynamic systems, and used them to solve two fundamental problems of distributed computing: k-set agreement and RME. To circumvent the lack of initial information, the ⊥ default value was added as a way to delay the failure detector outputs. In Chapter 3, a failure detector implementation was proposed which makes use of the TVG model of [START_REF] Casteigts | Time-varying graphs and dynamic networks[END_REF] to express the required level of temporal graph connectivity. Finally, the necessity of temporal graph connectivity assumptions to solve problems was addressed differently in Chapters 3 and 4.

Chapter 5. Conclusion

In Chapter 3, the connectivity assumptions used to solve k-set agreement were integrated into the definition of the failure detector itself. This approach presents the advantage of preserving the role of the failure detector as a complete abstraction layer: no other assumption than the failure detector is used to solve the problem. Conversely, in Chapter 4, the connectivity assumptions used to solve RME were presented as part of the base system model. While this approach limits the applicability of the results to systems making the same connectivity assumptions, it presents the advantage of making the new failure detector definition closer to its existing definition for static and known systems. This allowed Chapter 4 to be a direct translation of the existing results of [START_REF] Delporte-Gallet | Mutual exclusion in asynchronous systems with failure detectors[END_REF] and [START_REF] Bhatt | Extracting quorum failure detectors[END_REF] for unknown dynamic systems.

Contributions

This section summarizes the contributions presented in this thesis.

A Failure Detector for k-Set Agreement in Unknown Dynamic Systems

Chapter 3 adapted the definition of the ΠΣ x,y failure detector into the ΠΣ ⊥,x,y failure detector. This new detector differs from the original in two ways: it makes use of the ⊥ default value to deal with the lack of initial information about the participants in the system, and it includes two connectivity properties (one is the quorum connectivity property, and the other is integrated into the eventual partial leadership property).

Using the TVG formalism enriched with message pattern assumptions to model an unknown dynamic system, an implementation of ΠΣ ⊥,x,y was then presented.

Additionally, an algorithm adapted from the k-set agreement algorithm of [BT10, MRS12] was proposed. This algorithm solves the k-set agreement problem in any unknown dynamic system enriched with ΠΣ ⊥,x,y with k ≤ xy, thus proving that this failure detector is sufficient to solve k-set agreement in unknown dynamic systems.

A Failure Detector for Recoverable Mutual Exclusion in Unknown Dynamic Systems

In Chapter 4, graph connectivity issues were abstracted into model assumptions. As a result, this work focused on process mobility, which was modeled using the crash-recovery failure model. The chapter first discussed the differences between (T , Σ l ) and T Σ l (which requires the properties of T and Σ l to apply to a same output set), and proved that both failure detectors are equivalent.

Based on that result, T Σ l was then extended into the T Σ lr failure detector, which modifies the former in two ways: it uses of the ⊥ default value (in the form of the rdy p variable) and is defined in terms of eventually up, eventually down and unstable processes, instead of correct and faulty processes.

An algorithm that solves RME using T Σ lr was proposed, thus proving that it is sufficient to solve RME in unknown dynamic systems. Finally, a reduction algorithm transforming any failure detector sufficient to solve RME into T Σ lr was also presented, thus proving that T Σ lr is the weakest failure detector to solve RME in unknown dynamic systems. [START_REF] Bonomi | Intrusion-tolerant reliable broadcast[END_REF]. Formally, reliable broadcast is defined in terms of two primitives: broadcast(m), which is defined by the broadcast algorithm and called by the application to disseminate m to all processes, and deliver(m), which is defined by the application and called by the broadcast algorithm when message m has been received. The broadcast algorithm that offers these primitives must ensure that, if a correct 1 process broadcasts a message, then it eventually delivers the message (validity property). Furthermore, every correct process delivers a message at most once and only if that message was previously broadcast by some process (integrity property).

From an implementation point of view, the broadcast primitive sends point-to-point messages to each process of the system. However, if the sender fails during the execution of the broadcast primitive, some processes might not receive the broadcast message. In order to circumvent this problem, reliable broadcast ensures, besides the validity and integrity properties, that even if the sender fails, every correct process delivers the same set of messages (agreement property) [START_REF] Hadzilacos | Fault-tolerant broadcasts and related problems. chapter Distributed systems[END_REF].

There exists a considerable amount of literature on reliable broadcast algorithms, such as the one where all correct receivers retransmit all received messages guaranteeing then the delivery of all broadcast messages by the other correct processes of the system [START_REF] Guerraoui | Introduction to reliable distributed programming[END_REF]. We are particularly interested in solutions that use failure detectors [START_REF] Deepak | Unreliable Failure Detectors for Reliable Distributed Systems[END_REF] which notify the broadcast algorithm about processes failures. Upon receiving such an information, the algorithm reacts in accordance to tolerate the failure. Another important feature of reliable broadcast algorithms concerns performance, which is related to how broadcast messages are diffused to processes. Aiming at scalability and message complexity efficiency, many reliable broadcasts organize processes on logical spanning trees. Messages are then diffused over the constructed tree, therefore providing logarithmic performance [START_REF] Schneider | Fault-tolerant broadcasts[END_REF], [START_REF] Fragopoulou | Edge-disjoint spanning trees on the star network with applications to fault tolerance[END_REF], [START_REF] Kim | FaRe-Cast: Fast, reliable application layer multicast for flash dissemination[END_REF], [START_REF] Ramanathan | Reliable broadcast in hypercube multicomputers[END_REF], [START_REF] Raynal | A simple broadcast algorithm for recurrent dynamic systems[END_REF] (see Section A.2).

This work presents an autonomic reliable broadcast algorithm where messages are transmitted over spanning trees dynamically built on top of a logical hierarchical hypercube-like topology. Autonomic systems constantly monitor themselves and automatically adapt to changes [START_REF] Kephart | The vision of autonomic computing[END_REF]. The logical topology is maintained by the underlying VCube monitoring system which also detects failures [DBR14] [START_REF] Duarte | A hierarchical adaptive distributed system-level diagnosis algorithm[END_REF]. VCube is a distributed diagnosis layer responsible for organizing processes of the system in a virtual hypercube-like cluster-based topology which is dynamically re-organized in case of process failure. When invoked, the VCube gives information about the liveness of the processes that compose the system.

We assume a fully-connected asynchronous system in which processes can fail by crashing, and crashes are permanent. Links are reliable. A process that invokes the reliable broadcast primitive starts the construction of a spanning tree. This tree is built with information obtained from the VCube, and is dynamically reconstructed upon detection of a node crash (process failure).

In a previous work [START_REF] Luiz | An autonomic implementation of reliable broadcast based on dynamic spanning trees[END_REF], we proposed an autonomic reliable broadcast algorithm on top of the Hi-ADSD, a previous version of the VCube. The algorithm guarantees several logarithmic properties, even when nodes fail, and allows transparent and efficient spanning tree reconstructions. However, for this solution, we considered a synchronous model for the system, i.e., there exist known bounds on message transmission delays and processors' speed and, consequently, the VCube needs to provide perfect process failure detections. On the one hand, the advantage of such synchronous assumption is that there was no false failure suspicions and, thus, if the VCube notifies the broadcast algorithm that a given process is faulty, the algorithm is sure that it can stop sending message to this faulty process and then removes it forever from the spanning tree constructions. On the other hand, the synchronous assumption considerably restrains the distributed systems and applications that can use the broadcast protocol since many of the current network environments are considered asynchronous (there exist no bounds on message transmission delay or on processors' speed).

Hence, considering the above constraints, we propose in this article a new autonomic reliable broadcast algorithm, using the VCube in an asynchronous model. We assume that the failure detection service provided by the VCube is unreliable since it can make mistakes by erroneously suspecting a correct process (false suspicion) or by not suspecting a node that has actually crashed. However, upon detection of its mistake, the VCube corrects it. Furthermore, it also ensures that eventually all failures are detected (strong completeness property). Note that such false suspicions render a broadcast algorithm much more complex than the previous one since it can induce violation of the properties. For instance, the algorithm must ensure that a falsely suspected process must receive and deliver, only once, all broadcast messages, otherwise the agreement and integrity properties would be violated. In our solution, false suspicions are tolerated by sending special messages to those processes suspected of having failed. We must also emphasize that our aim is to provide a reliable broadcast algorithm which is efficient, i.e., that keeps, as much as possible, the logarithmic properties of the spanning tree diffusion over the hypercube-like topology. Our algorithm tolerates up to n-1 node crashes.

The rest of this paper is organized as follows. Section A.2 discusses some related work. In Section A.3 we describe the system model while Section A.4 briefly describes the VCube diagnosis algorithm and the hypercube-like topology. In Section A.5, we present the autonomic reliable broadcast algorithm for asynchronous systems while Section A.6 discuss some performance issue of the algorithm. Finally, Section A.7 concludes the paper.

A.2 Related Work

Many reliable broadcast algorithms of the literature exploit spanning trees such as [SGS84, FA96, KMV10, RS88, RSCW14].

Schneider et. al. introduced in[SGS84] a tree-based fault-tolerant broadcast algorithm whose root is the process that starts the broadcast. Each node forwards the message to all its successors in the tree. If one process p that belongs to the tree fails, another process assumes the responsibility of retransmitting the messages that p should have transmitted if it were correct. Like to our approach, processes can fail by crashing and the crash of any process is detected after a finite but unbounded time interval by a failure detection module. However, the authors do not explain how the algorithm rebuilds or reorganizes the tree after a process failure.

In [START_REF] Fragopoulou | Edge-disjoint spanning trees on the star network with applications to fault tolerance[END_REF], a reliable broadcast algorithm is provided by exploiting disjoint paths between pairs of source and destination nodes. Multiple-path algorithms are particularly useful in systems that cannot tolerate the time overhead for detecting faulty processors, but there is an overhead in the number of duplicated messages. On a star network with n edges, the algorithm constructs n -1 directed edge-disjoint spanning trees. Fault tolerance is achieved by retransmitting the same messages through a number of edge-disjoint spanning trees. The algorithm tolerates up to n -2 failure of nodes or edges and can be adjusted depending on the network reliability. Similarly, Kim et al. propose in [START_REF] Kim | FaRe-Cast: Fast, reliable application layer multicast for flash dissemination[END_REF] a tree-based solution to disseminate a message to a large number of receivers using multiple data paths in a context of time-constrained dissemination of information. Thus, arguing that reliable extensions using ack-based failure recovery protocols cannot support reliable dissemination with time constraints, the authors exploit the use of multiple data paths trees in order to conceive a fast and reliable multicast dissemination protocol. Basically the latter is a forest-based (multiple parents-to-multiple children) tree structure where each participant node has multiple parents as well as multiple children. A third work that exploits multi-paths spanning trees is [START_REF] Ramanathan | Reliable broadcast in hypercube multicomputers[END_REF] where the authors present a reliable broadcast algorithm that runs on a hypercube and uses disjoint spanning trees for sending a message through multiple paths.

Raynal et. al. proposed in [START_REF] Raynal | A simple broadcast algorithm for recurrent dynamic systems[END_REF] a reliable tree-based broadcast algorithm suited to dynamic networks in which message transfer delays are bounded by a constant of δ unit of times. Whenever a link appears, its lifetime is at least δ units of time. The broadcast is based on a spanning-tree on top of which processes forward received messages to their respective neighbors. However, as the system is dynamic, the set of current neighbors of a process p may consists of a subset of all its neighbors and, therefore, p has to additionally execute specific statements when a link re-appears, i.e., forwards the message on this link if it is not sure that the destination process already has a copy of it.

Similarly to our approach, many existing reliable broadcast algorithms exploit spanning trees constructed on hypercube-like topologies [START_REF] Ramanathan | Reliable broadcast in hypercube multicomputers[END_REF][START_REF] Wu | Optimal broadcasting in hypercubes with link faults using limited global information[END_REF][START_REF] Liebeherr | Hypercast: A protocol for maintaining multicast group members in a logical hypercube topology[END_REF]. In [START_REF] Wu | Optimal broadcasting in hypercubes with link faults using limited global information[END_REF], the authors present a fault-tolerant broadcast algorithm for hypercubes based on binomial trees. The algorithm can recursively regenerate a faulty subtree, induced by a faulty node, through one of the leaves of the tree. On the other hand, unlike our approach, there is a special message for advertising that the tree must be reconstructed and, in this case, broadcast messages are not treated by the nodes until the tree is rebuilt. The HyperCast protocol proposed by [START_REF] Liebeherr | Hypercast: A protocol for maintaining multicast group members in a logical hypercube topology[END_REF] organizes the members of a multicast group in a logical tree embedded in a hypercube. Labels are assigned to nodes and the one with the highest label is considered to be the root of the tree. However, due to process failures, multiple nodes may consider themselves to be the root and/or different nodes may have different views of which node is the root. [START_REF] Leitão | Hyparview: A membership protocol for reliable gossip-based broadcast[END_REF] the HyParView, a hybrid broadcast solution that combines a tree-based strategy with a gossip protocol. A broadcast tree is created embedded on a gossipbased overlay. Broadcast is performed by using gossip on the tree branches. Later, some of the authors proposed a second work [START_REF] Mário | Thicket: A protocol for building and maintaining multiple trees in a P2P overlay[END_REF] where they introduced Thicket, a decentralized algorithm to build and maintain multiple trees over a single unstructured P2P unstructured overlay for information diffusion. The authors argue that multiple trees approach allow that each node to be an internal node in just a few trees and a leaf node in the remaining of the trees providing, thus, load distribution as well as redundant information for fault-tolerance.

Leitão et al. present in

In [START_REF] Luiz | An autonomic implementation of reliable broadcast based on dynamic spanning trees[END_REF], we presented a reliable broadcast solution based on dynamic spanning trees on top of the Hi-ADSD, a previous version of the VCube. Multiple trees are dynamically built, including all correct nodes, where each tree root corresponds to the node that called a broadcast primitive. Contrarily to the current work, this solution considers that the system model is synchronous and that the VCube offers a perfect failure detection. Let's consider process p 0 and that there are no failures. The clusters of p 0 are shown in the same figure. Each cluster c 0,1 , c 0,2 , and c 0,3 is tested once, i.e., p 0 only performs tests on nodes 1, 2, 4 which will then inform p 0 about the state of the other nodes of the respective cluster.

In order to avoid that several processes test the same processes in a given cluster, process i executes a test on process j ∈ c i,s only if process i is the first faulty-free process in c j,s . Thus, any process (faulty or fault-free) is tested at most once per round, and the latency, i.e., the number of rounds required for all fault-free processes to identify that a process has become faulty is log 2 n in average and log 2 2 n rounds in the worst case.

A.5 Reliable Broadcast Algorithm for Asynchronous System

A reliable broadcast algorithm ensures that the same set of messages is delivered by all correct processes, even if the sender fails during the transmission. Reliable broadcast presents three properties [GR06]:

• Validity: if a correct process broadcasts a message m, then it eventually delivers m.

• Integrity: every correct process delivers the same message at most once (no duplication) and only if that message was previously broadcast by some process (no creation).

• Agreement: if a message m is delivered by some correct process p i , then m is eventually delivered by every correct process p j . Note that the agreement property still holds if m is not delivered by any process.

Our reliable broadcast algorithm exploits the virtual topology maintained by VCube, whenever possible. Each process creates, thus, a spanning tree rooted at itself to broadcast a message. The message is forwarded over the tree and, for every message that a node of the tree sends to one of its correct neighbor, it waits for the corresponding acknowledge from this neighbor, confirming the reception of the message. Algorithm 8 presents the pseudo-code of our proposal reliable broadcast protocol for an asynchronous system with n=2 d processes. The dimension of the VCube is, therefore, d. A process gets information, not always reliable, about the liveness of the other processes by invoking the VCube. Hence, the trees are dynamically built and autonomically maintained using the hierarchical cluster structure and the knowledge about faulty (or falsely faulty suspected) nodes. The algorithm tolerates up to n-1 failures.

Let i and j be two different processes of the system. The function cluster i (j) = s returns the identifier s of the cluster of process i that contains process j, 1 ≤ s ≤ d. For instance, in the 3-cube as shown in Fig. A.1, cluster 0 (1) = 1, cluster 0 (2) = cluster 0 (3) = 2 and cluster 0 (4) = cluster 0 (5) = cluster 0 (6) = cluster 0 (7) = 3.

A.5.1 Message types and local variables

Let m be the application message to be transmitted from a sender process, denoted source, to all other processes in the system. We consider three types of messages:

• T REE, m : message broadcast by the application that should be forwarded over the VCube to all processes considered to be correct by the sender;

• DELV, m : message sent to processes suspected of being faulty in order to avoid that false suspicions induce the no delivery of the message by correct processes. The recipient of the message should deliver it but not forward it;

• ACK, m : used as an acknowledgement to confirm that a TREE message related to m was received.

For the sake of simplicity, we use TREE, DELV, and ACK to denote these messages. Every message m keeps two parameters: (1) the identifier of the process that broadcast m and (2) a timestamp generated by the process local counter which uniquely identifies the m. The first message broadcast by a process i has timestamp 0 and at every new broadcast, i increments the timestamp by 1. The algorithm can extract these two parameters from m by respectively calling the functions source(m) and ts(m).

Process i keeps the following local variables:

• correct i : the set of processes considered correct by process i;

• last i [n]: an array of n elements to keep the last messages delivered by i (last i [j] is the last message broadcast by j that was delivered by i);

• ack_set i : a set with all pending acknowledgement messages of process i. For each message T REE, m received by i from process j and retransmitted to process k, an element j, k, m is added to this set; The symbol ⊥ represents a null element. The asterisk is used as a wildcard. For instance, j, * , m means all pending acks for a message m received from process j and re-sent to any other process;

• pending i : list of the messages received by i that where not delivered yet because they are "out of order" with regard to their timestamp, i.e., ts(m) > ts(last i (source(m)) + 1;

• history i : the history of messages that were already broadcast by i. This set is used to prevent sending the same message to the same cluster more than once. j, m, h ∈ history i indicates that the message m received from process j was already sent by i to the clusters c i,s for all s ∈ [1, h].

A.5.2 Algorithm description

Process i broadcasts a message by calling the broadcast(m) function. Line 7 ensures that a new broadcast starts only after the previous one has been completed, i.e., there is no pending acks for the last i [i] message. Note that some processes might not have received the previous message yet because of false suspicions. Then, the received message m is locally delivered to i (line 9) and, by calling the function broadcast_tree (line 10), i forwards m to its neighbors in the VCube. To this end, it calls, for each cluster s ∈ [1, log 2 n], the function broadcast_cluster that sends a TREE message to the first process k which is correct in the cluster (line 27). To those processes that are not correct, i.e, suspected of being crashed, and placed before k in the cluster, a DELV message (line 31) is sent to them. Notice that in both cases, the messages are sent provided i has not already forwarded m, received from j, to k. For every sent TREE message the corresponding ack is included in the list of pending acks (line 28). Let's consider the 3-VCube topology of Figure A.2. Figure A.2(a) shows a fault-free scenario where process 0 (p 0 ) broadcasts a message. After delivering the message to itself, p 0 sends a copy of the message to p 1 , p 2 , and p 4 , which are neighbors of p 0 and the first correct process on each of i's clusters.

Upon reception of a message T REE, m from process j (line 45), process i calls the function handle_message. In this function, m is added to the set of pending messages and then all pending messages which were broadcast by the same process that broadcast m (source(m)) are

• i is correct. It can be shown by induction that every correct process receives m.

As a basis of the induction, let us consider the case where n = 2 and P = {i, j}. It follows that c i,1 = {j}. Therefore i will send m to j on line 31 if i suspects j or on line 27 otherwise. If j is correct, it will eventually receive m since the links are reliable, and will deliver m on line 42. i will also deliver m, by virtue of the validity property.

We now have to prove that if every correct process receives m for n = 2 k , it is also the case for n = 2 k+1 . The system of size 2 k+1 can be seen as two subsystems P 1 = {i} ∪ k x=1 c i,x and P 2 = c i,k+1 such that

|P 1 | = |P 2 | = 2 k .
The broadcast_tree and broadcast_cluster procedures ensure that for every s ∈ [1, k + 1], i will send m to at least one process in c i,s . Let j be the first process in c i,k+1 . If j is correct, it will eventually receive m. If j is faulty and i detected the crash prior to the broadcast, i will send the message to j anyway in case it is a false suspicion (line 31) but it will also send it to another process in c i,k+1 as a precaution (line 27). i will keep doing so until it has sent the T REE message to a non-suspected process in c i,k+1 , or until it has sent the message to all the processes in c i,k+1 . If j is faulty and i only detects the crash after the broadcast, the broadcast_cluster procedure will be called again on line 58, which ensures once again that i will send the message to a non-suspected process in c i,k+1 . As a result, unless all the processes in c i,k+1 are faulty, at least one correct process in c i,k+1 will eventually receive m. This correct process will then broadcast m to the rest of the P 2 subsystem on line 47.

Since a correct process broadcasts m in both subsystems P 1 and P 2 , and since both subsystems are of size 2 k , it follows that every correct process in P will eventually receive m.

• i is faulty. If i crashes before sending m to any process, then no correct process delivers m and the agreement property is verified. If i crashes after the broadcast is done, then everything happens as if i was correct. If i crashes after sending m to some processes and a correct process j receives m, then j will eventually detect the failure of i. If j detects the crash before receiving m, when it receives m it will restart a full broadcast of m on line 44. If j only detects the crash of i after receiving m, it will also restart a full broadcast of m on line 62. Since j is correct, every correct process will eventually receive m.

Theorem A.1. Algorithm 8 implements a reliable broadcast.

Proof. The proof follows directly from Lemmas A.1, A.3, and A.4.

A.6 Performance Discussion

The goal of exploiting the VCube overlay in our solution is to provide an efficient broadcast where each process sends at most log 2 n messages. However, this complexity cannot be ensured at all times in an asynchronous system where false suspicions can arise. Algorithm 8 aims to take advantage of the VCube whenever possible while still ensuring the properties of a reliable broadcast despite false suspicions.

In the best case scenario where no process is ever suspected of failure, each process will send at most one message per cluster (line 27). Therefore n -1 T REE messages will be sent in total (since no process will be sent the same message twice) with no single process sending more than log 2 n messages. This is the example presented in If a process other than the source of the broadcast is suspected before the broadcast, there will be n -2 T REE messages and one DELV message sent. A single process might send up to log 2 n T REE messages plus one DELV message per suspected process. This is the example of If the source of the broadcast suspects everyone else, then it will send n -1 DELV messages. In this case, Algorithm 8 is equivalent to a one-to-all algorithm where one process sends the message directly to all others, losing, thus, the advantages of tree topology properties, such as scalability.

The main cost of suspicions lies in the fact that when a process is suspected, its last broadcast must be resent. This is the purpose of lines 44 and 62. Such a re-broadcast is an unavoidable consequence of the existence of false suspicions, necessary in order to ensure the agreement property of reliable broadcast.

Note that the fact that the information about a node failure is false or true has no difference in the impact on the performance of the broadcast algorithm in terms of message complexity.

A.7 Conclusion and Future Work

This article presented a reliable broadcast algorithm for message-passing distributed systems prone to crash failures on asynchronous environments. It tolerates up to n-1 failures. For broadcasting a message, the algorithm dynamically builds a spanning tree over a virtual hypercube topology provided by the underlying monitor system VCube. In case of failure, the tree is dynamically reconstructed. To this end, the VCube provides information about node failures. However, as the system is asynchronous, it can make mistake falsely suspecting no faulty nodes. Such false suspicions are tolerated by the algorithm by sending special messages to those processes suspected of having failed. In summary, whenever possible, the algorithm exploits the hypercube properties offered by the VCube while ensuring the properties of the reliable broadcast, even in case of false suspicions.

As future work, we intend to implement our algorithm and conduct extensive simulation experiments in order to compare its performance in terms of latency and number of messages in different scenarios with and without failure of nodes as well as false suspicions.

  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1.1 A Failure Detector for k-Set Agreement in Unknown Dynamic Systems 4 1.1.2 A Failure Detector for Mutual Exclusion in Unknown Dynamic Systems 4 1.1.3 An Asynchronous Reliable Broadcast Algorithm over a Hypercube Topology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2 Publications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2.1 Papers in International Conferences . . . . . . . . . . . . . . . . . . . . 5 1.2.2 Papers in International Journals . . . . . . . . . . . . . . . . . . . . . . 5 1.3 Organization of the Manuscript . . . . . . . . . . . . . . . . . . . . . . 6

Chapter 2 .

 2 A Background on Failure Detectors and Dynamic Systems

Figure 2 .

 2 Figure 2.1: A simple TVG, with V = {a, b, c, d}. The intervals on each edge represent the periods of time when it is available and constitute the edge presence function ρ. This representation of the communication graph was initially introduced for evolving graphs in [BF03].

Figure 2 .

 2 Figure 2.2 presents the relative strength of the different TVG classes. An arrow from one class to another indicates that the second class strictly includes the first one.

Figure 2 . 2 :

 22 Figure 2.2: Relations of inclusion between TVG classes

Chapter 3 A

 3 Failure Detector for k-Set Agreement in Unknown Dynamic Systems Contents 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 Alpha x Sub Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5.2 Alpha x Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5.3 k-Set Agreement Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 3.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Fig. 3 .

 3 Fig. 3.1 shows an example for m = k = 3 in which winning quorums are represented by dashed red circles. Each solid black circle represents a response set. Note that out of any 4 response sets, at least 2 intersect.

Fig. 3 .

 3 Fig. 3.2 shows an example for m = 1 and k = 3. Similarly to Fig. 3.1, the winning quorum is represented by a dashed red circle, and response sets are represented by solid black circles. Once again, 2 out of any 4 response sets intersect.

  upon reception of request (round) from src do 41: requests p ← requests p ∪ {(round, src)} 42: last_round p [src] ← round 43: check requests() 44: upon reception of grant () from src do 45: if gid p = -1 and gid p = p then 46: send(reject, src) 47: else if recovering p = f alse then 48: grants p ← grants p ∪ {src} 49: upon reception of done () from src do 50: requests p ← requests p \ {( * , src)} 51: (gid p , grnd p ) ← (-1, -1) 52: check requests() 53: upon reception of reject () from src do 54: (gid p , grnd p ) ← (-1, -1) 55: check requests() 56: upon reception of comeback (crit_src) from src do 57: requests p ← requests p \ {( * , src)} 58:

  Theorem 4.2 follows From Claim 4.1 and Claim 4.3: Theorem 4.2 (Correctness). The Algorithm 5 solves the RME using T Σ lr in any unknown dynamic environment.

  Corollary 4.1 (Sufficiency). The T Σ lr failure detector is sufficient to solve the RME in any unknown dynamic environment with partial memory loss.

  34: trust p ← trust p ∪ trust_src 35: if req = true then waitlist p ← waitlist p ∪ {src} 36: else 37: waitlist p ← waitlist p \ {src} 38: donelist p ← donelist p ∪ {src} 39: upon reception of quorum (trust_src, crash_src) from src do 40: trust p ← trust p ∪ trust_src 41: crash p ← crash p ∪ crash_src 42:

  Claim 4.4 (Strong completeness). Algorithm 7 ensures the strong completeness property of T Σ lr in M RME .

  Claim 4.8 (Live pairs intersection). Algorithm 7 ensures the live pairs intersection property of T Σ lr in M RME .

76Chapter 4 .

 4 The Weakest Failure Detector for Mutual Exclusion in Unknown Dynamic Systems Theorem 4.3 (Correctness). The Algorithm 7 implements T Σ lr in M RME . Corollary 4.2 (Necessity). The T Σ lr failure detector is necessary to solve the RME in any unknown dynamic environment with partial memory loss.

Figure

  Figure A.1: VCube hierarchical organization.

Figure A. 2 :

 2 Figure A.2: Reliable broadcast -process 0 (p 0 )

  Figure A.2(a).

Figure A. 2

 2 (b).

  The weakest failure detector to solve the mutual exclusion problem in an unknown dynamic environment. In Proceedings of the 20th International Conference on Distributed Computing and Networking, ICDCN 2019, Bangalore, India, January 4-7, 2019 (to be published), 2019.

	1.2.2 Papers in International Journals
	• [JRAS17] Denis Jeanneau, Thibault Rieutord, Luciana Arantes, and Pierre Sens. Solving k-
	set agreement using failure detectors in unknown dynamic networks. IEEE Trans. Parallel
	Distrib. Syst., 28(5):1484-1499, 2017.

• [JRAS15] Denis Jeanneau, Thibault Rieutord, Luciana Arantes, and Pierre Sens. A failure detector for k-set agreement in dynamic systems. In 14th IEEE International Symposium on Network Computing and Applications, NCA 2015, Cambridge, MA, USA, September 28-30, 2015, pages 176-183, 2015. • [JRAJ16] Denis Jeanneau, Luiz A. Rodrigues, Luciana Arantes, and Elias Procópio Duarte Jr. An autonomic hierarchical reliable broadcast protocol for asynchronous distributed systems with failure detector. In 2016 Seventh Latin-American Symposium on Dependable Computing, LADC 2016, Cali, Colombia, October 19-21, 2016, pages 91-98, 2016. • [MJAS19] Etienne Mauffret, Denis Jeanneau, Luciana Arantes, and Pierre Sens. • [JRAJ17] Denis Jeanneau, Luiz A. Rodrigues, Luciana Arantes, and Elias Procópio Duarte Jr. An autonomic hierarchical reliable broadcast protocol for asynchronous distributed systems with failure detection. J. Braz. Comp. Soc., 23(1):15:1-15:14, 2017.

Table 2

 2

.1: A global view of failure detectors solving agreement problems in message passing systems 2.3.2.1 The S Eventually Strong Failure Detector and the Ω Eventual Leader Detector

Table 2 .

 2 3: A global view of failure detectors studied in unknown and/or dynamic systems

		Article	Section Dynamic membership Dynamic graph	Unknown
	Ω	[MRT + 05] 2.4.1.1	Yes	No	Yes
	Ω	[CRTW07] 2.4.1.1	Yes (Mobile Hosts),	Yes (MH)	Yes (MH)
				No (Support Stations)	No (SS)	No (SS)
	Σ	[ADGF08] 2.4.1.1	Yes	No	Yes
	∆Ω	[LRAC12] 2.4.1.2	Yes	No	Yes
	∆Ω	[GLLR13] 2.4.1.2	Yes	Yes	Yes
	S	[SAB + 08]	2.4.6	No	Yes	Yes
	PD	[AST + 10]	2.4.6	Yes	Yes	Yes
	S M	[GSAS11]	2.4.6	Yes	Yes	Yes
	Ω	[AGSS13]	2.4.6	Yes	Yes	Yes
	Σ ⊥	[RAS15]	2.4.6	No	No	Yes

Table 3

 3

	.1: Assumptions for failure detector implementations
	Assumption	Failure detector property
	Assumption 3.1 Σ ⊥,

k : quorum liveness Σ ⊥,k : quorum connectivity Assumption 3.2 Σ ⊥,k : quorum intersection Assumption 3.3 ΠΣ ⊥,x : eventual partial leadership

  leader i ← p i //The leader returned by ΠΣ ⊥,x for p i : upon reception of (src, r_src, Q, cands) from p j do 11:if src = p i and r_src = r i then // Response

		round number
	3:	qr i ← ⊥ // The quorum returned by ΠΣ ⊥,x for p i
	4:	recv_f rom i ← {p i } // Quorum buffer
	5:	last_known i ← ∅ // Round numbers of known processes
	6:
	7:	candidate i ← ⊥ // p i 's current candidate for leadership
	8:	candidates i ← ∅ // Candidates of processes in recv_f rom i
	9:	bcast(p i , 0, ∅, ∅)
	12:	recv_f rom i ← recv_f rom i ∪ Q
	13:	candidates i ← candidates i ∪ cands
	14:	if |recv_f rom i | ≥ α then
	15:	qr i ← recv_f rom i
	16:	recv_f rom i ← {p i }
	17:

10

  or ∅ then

	21:	leader i ← p i
	22:	else
	23:	leader i ← candidate i
	24:	candidates i ← ∅
	25:	bcast(p i , r i , ∅, ∅)
	26:	else if src = p i then // Query
	27:	if ∃last_r | src, last_r ∈ last_known i
	28:	∧ last_r ≤ r_src then
	29:	last_known i ← last_known i \{ src, last_r }
	30:	last_known i ← last_known i ∪ { src, r_src }
	31:	bcast(src, r_src, Q ∪ {p i }, cands ∪ {candidate i })
	32:	else if src, -/ ∈ last_known i then
	33: last_known 35: else
	36:

i ← last_known i ∪ { src, r_src } 34: bcast(src, r_src, Q ∪ {p i }, cands ∪ {candidate i })

  pos i ← g(pos i , rd -lre i ); lre i ← rd 28: if pos > pos i then est i ← est; pos i ← pos 29: else if pos = pos i then est i ← max{est i , est} 30: bcast RSP_W(rd, pos, p i , lre i , pos i , est i )

	25:	if p i ∈ Q then
	26:	if rd ≥ lre i then
	27:
	31:

24: upon reception of REQ_W(rd, pos, est, Q) do

  dec i ← ⊥ // The value decided by p i (⊥ if p i has not decided)

	1: init
	2:
	3:	prime

i ← the i th prime number // Constant 4: r i ← prime i // The current round number 5: function propose(v i ) 6:

  for ∀q ∈ grants p \ {p} do send(done, q) if (gid p = -1 or gid p = p) and requests p = ∅ and crit p = f alse and recovering p = f alse then (grnd p , gid p ) ← highest(requests p ) if gid p = p then send(grant, gid p )

	2:	wait for recovering p = f alse
	3:	req p ← true
	4:	round p ← round p + 1; grants p ← {p}
	5:	for ∀q ∈ tq p do send(request, round p , q)
	6:	requests p ← requests p ∪ {(round p , p)}
	7:	check requests()
	8:	wait for gid p = p and rdy p =	and
		tq p ⊆ grants p
	9:	crit p ← true; req p ← f alse
	10: procedure exit section
	11:	wait for recovering p = f alse
	12:	crit p ← f alse
	13:
	14:	grants p ← {p}; requests p ← requests p \
		{( * , p)}
	15:	check requests()
	16: procedure check requests
	17:
	18:
	19:
	20:	for ∀q ∈ grants p \ {p} do
	21:	grants p ← grants p \ {q}
	22:	send(reject, q)
	23: procedure reconnection
	24:	recovering p ← true
	25:	update p ← tq p
	26:	for ∀q ∈ update p do
	27:	send(comeback, crit p , q)
	28:	wait for update p = ∅
	29:	recovering p ← f alse
	30:	check requests()
	31: when q added to tq p
	32:

  The Weakest Failure Detector for Mutual Exclusion in Unknown Dynamic Systems

	64Chapter 4.
	60:	check requests()
	63:	last_round p [src] ← round
	64:	round p ←max(round p , last_rnd)
	65:	if grant_src = true then	p previously
		granted src
	66:	(gid p , grnd p ) ← (src, round)
	67:	if grant_p = true then	src previously
		granted p
	68:	grants p ← grants p ∪ {src}
	69:	if req = true then	src is requesting
	70:	requests p ← requests p ∪ {(round, src)}
	71:	update p ← update p \ {src}

61:

send(update, gid p = src, last_round p [src], src ∈ grants p , round p , req p , src) 62: upon reception of update (grant_p, last_rnd, grant_src, round, req) from src do

  Algorithm 6 Modified send primitive for B RME 1: procedure B RME _send(msg, dest) First, algorithm B RME is introduced. B RME has exactly the same code as A RME , except that every call to the send primitive is replaced by a call to B RME _send, as defined in Algorithm 6. Algorithm 6 serves two purposes: (1) by using trust p , it enables p to keep track of which processes it heard of while trying to access CS; (2) by using start p , it enables p to delay the start of the RME algorithm. Lemma 4.6. Provided that each eventually up process p eventually sets start p to true, Algorithm B RME solves the RME problem in M RME .

	2:	wait for start p = true
	3:	send(msg, trust p , dest)
	4: upon reception of (msg, trust_src) from src do
	5:	wait for start p = true
	6:	trust p ← trust p ∪ trust_src
	7:	B RME _deliver(msg)

  A RME and accessed with A RME .try(p). Additionally, there is a global CS which is handled by algorithm B RME and accessed with B RME .try. 72Chapter 4. The Weakest Failure Detector for Mutual Exclusion in Unknown Dynamic Systems Algorithm 7 Reduction Algorithm T A RME →T Σ lr : code for process p

	1: procedure task 1
	2:	A RME .try(p)
	3:	start p ← true
	4:	loop forever:
	5:	for q ∈ known p do
	6:	send(alive, req p , trust p , q)
	7: procedure task 2
	8:	loop forever:
	9:	wait for waitlist p \ donelist p = ∅
	10:	donelist p ← ∅
	11:	req p ← true
	12:	B RME .try
	13:	B RME .exit
	14:	req p ← f alse
	15:	if trust p ∩ crash p = ∅ then
	16:	tq p ← trust p
	17:	rdy p ←
	18:	for q ∈ known p do
	19:	send(quorum, trust p , crash p , q)
	20:	else
	21:	trust p ← trust p \ crash p
	22: procedure task 3 + q
	23:	known p ← known p ∪ {q}
	24:	A RME .try(q)
	25:	A RME .exit(q)
	26:	crash p ← crash p ∪ {q}
	27: procedure reconnection
	28:	tq p ← trust p \ crash p
	29:

  Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 5.1.1 A Failure Detector for k-Set Agreement in Unknown Dynamic Systems 78 5.1.2 A Failure Detector for Recoverable Mutual Exclusion in Unknown Dy-

	Chapter 5
	Conclusion
	Contents
	5.1

namic Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 5.2 Perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 5.2.1 On the Necessity of Synchronous Processes in Dynamic Systems . . . . 79 5.2.2 The Weakest Failure Detector for k-Set Agreement . . . . . . . . . . . . 79 5.2.3 Defining the Mutual Exclusion Problem in Crash-Recovery Systems . . 79

Acknowledgements

I am first grateful to Lucana Arantes and Pierre Sens for their guidance, feedback and support during the three years of this thesis.

I would like to thank Carole Delporte, Roy Friedman, Arnaud Casteigts and Sébastien Tixeuil for accepting to be part of the jury for this thesis. Additionally, I want to thank Carole Delporte and Roy Friedman for accepting to review this manuscript.

Of course, I want to thank my co-authors, Thibault Rieutord, Etienne Mauffret, Luiz A. Rodrigues and Elias P. Duarte Jr., for their collaboration without which none of the publications in this thesis could have happened.

I would also like to thank all the colleagues at LIP6, which is a great work environment, and in particular the members of teams DELYS and Whisper for their friendship.

Finally, I want to thank my family for their moral support through this thesis and everything else.

Chapter 4

The Weakest Failure Detector for Mutual Exclusion in Unknown Dynamic Systems As discussed in Section 2.2.2, the majority of existing FTME algorithms consider static and known distributed systems without recovery. Hence, the conception of mutual exclusion in unknown dynamic distributed systems where crashed processes can recover presents great challenges.

A definition of recoverable mutual exclusion (RME) for systems with crash-recovery was presented in [START_REF] Golab | Recoverable mutual exclusion[END_REF] and further studied in [START_REF] Golab | Recoverable mutual exclusion in sublogarithmic time[END_REF] and [START_REF] Jayanti | Recoverable FCFS mutual exclusion with wait-free recovery[END_REF]. A main change with regard to previous definitions of fault-tolerant mutual exclusion is the critical section re-entry property, which specifies that if a process p crashes while in the critical section and later recovers, then no • Live pairs intersection: If two processes p and q are both alive at time t, then for any couple of time instants t 1 ≤ t and t 2 ≤ t, (rdy t 1 p = ∧ rdy t 2 q = ) =⇒ tq t 1 p ∩ tq t 2 q = ∅.

The eventually strong accuracy, strong completeness and trusting accuracy properties are the original properties of T , adapted for a crash-recovery model. These properties are referred to as the trusting properties of T Σ lr .

Similarly, the strong completeness and live pairs intersection properties are the original properties of Σ l , adapted for unknown dynamic systems. The new quorum readiness property, along with the rdy p output variable, was added to deal with the lack of initial information in an unknown system. These properties are referred to as the quorum properties of T Σ lr .

Note that the strong completeness is both a trusting property and a quorum property, since both T and Σ l make use of this same property.

Both trusting and quorum properties apply to the same set tq p , which is different from preexisting definitions in which T and Σ l are two separate oracles with separate outputs. Section 4.4, will prove that this combined version of the detector is necessary to solve RME.

Note that in a static, known system with reliable channels and prone to crash failures without recovery, T Σ lr is equivalent to T Σ l , and therefore (T , Σ l ).

Sufficiency of T Σ lr to solve Fault-Tolerant Mutual Exclusion

This section introduces Algorithm 5 and proves that it solves the RME in any unknown dynamic environment enriched with the T Σ lr failure detector.

Algorithm Description

Let's consider p the sender (source) of a message. The following types of messages are used by Algorithm 5: request: p has asked for permission to enter CS. The message contains the round number of the sender.

grant: p has granted permission to a requesting process to enter CS. done: notifies other processes that p has just exited its CS. reject: warns that p has already given its permission to another process different from itself, thus preventing deadlocks. comeback: notifies processes that p has just recovered from a crash. update: p gives information to a recently recovered process q about p's requesting state, previously given permissions that p granted to q and vice-versa, and q's last round number of which p is aware.

In Algorithm 5, each request to enter the CS, issued by p, is tagged by a sequence round number.

Besides having access to the output, tq p and rdy p , of its local failure detector, process p also keeps the following local variables, initialized with the indicated value: crit p ← f alse: a flag indicating that p is currently in CS. It is the only variable kept in stable storage. Thus, crit p is not reinitialized after a crash and recovery.

Perspectives

On the Necessity of Synchronous Processes in Dynamic Systems

Chapter 3 made the assumption that processes are synchronous. This assumption ensures that processes send their messages often enough to take advantage of the communication link availability windows. If this synchrony assumption is removed, even if a journey between two processes is available infinitely often, there is no guarantee that processes will ever manage to take advantage of this journey to get messages through.

Some papers in the literature have made a different assumption for the same purpose, like in [START_REF] Gómez-Calzado | A connectivity model for agreement in dynamic systems[END_REF], where it is assumed that new edges appearing in the graph are detected fast enough by processes to make use of the edge availability window. Such an assumption also implies some common timing between processes, since the definition of "fast enough" must be the same system-wide.

It would seems, therefore, that some sort of process synchrony assumption is necessary to reliably exploit communication opportunities in dynamic systems, but no such result has been proved so far.

The Weakest Failure Detector for k-Set Agreement

There is no proof that ΠΣ x,y (in static and known systems) or ΠΣ ⊥,x,y (in unknown dynamic systems) is the weakest failure detector for k-set agreement in the general case of 1 ≤ k < n.

Although the weakest failure detectors for consensus (k = 1) and set agreement (k = n -1) have been identified, the weakest failure detector for 2 ≤ k < n -1 has yet to be found. This issue has been the object of many of the papers presented in Section 2.3, and is still an open problem.

Defining the Mutual Exclusion Problem in Crash-Recovery Systems

Chapter 4 focused on a definition of RME that allows temporarily down processes to stay in the critical section until they recover and finish it. On the other hand, a process that crashes permanently must release the critical section in order to ensure liveness. This version of the problem is difficult to solve, since it implies that processes must be able to detect whether the crash of another process is temporary or permanent.

This version of RME is powerful because it ensures that process can always execute their critical section without being interrupted by other processes which is important, for example, to preserve the consistency of a shared resource. However, some applications might not require this level of consistency.

Another, weaker version of RME could be defined in which a process that crashes always leaves the critical section, whether the crash is temporary or permanent. This version of the problem is easier to solve, and requires a weaker version of the trusting accuracy property, since distinguishing a permanent crash from a temporary one would no longer be necessary.

Further research could aim to define the weakest failure detector for this weaker mutual exclusion problem.

Appendix A

A Reliable Broadcast Protocol for Asynchronous Systems with a Hypercube Topology

The following is an article [START_REF] Jeanneau | An autonomic hierarchical reliable broadcast protocol for asynchronous distributed systems with failure detector[END_REF]

A.1 Introduction

Numerous distributed applications with information dissemination requirements rely on a broadcast communication primitive to send messages to all processes that compose the application

A.3 System Model

We consider a distributed system that consists of a finite set P of n > 1 processes. Each process has a unique address. Processes {p 0 , .., p n-1 } communicate only by message passing. Each single process executes one task and runs on a single processor. Therefore, the terms node and process are used interchangeably in this work. The system is asynchronous, i.e., relative processor speeds and message transmission delay are unbounded. Links are reliable, and, thus, messages exchanged between any two correct processes are never lost, corrupted or duplicated. There is no network partitioning.

Processes communicate by sending and receiving messages. The network is fully connected: each pair of processes is connected by a bidirectional point-to-point channel. Processes are organized in a virtual hypercube-like topology, called VCube. In a d-dimensional hypercube (dcube) each process is identified by a binary address i d-1 , i d-2 , i 0 . Two processes are connected if their addresses differ by only one bit. Processes can fail by crashing and, once a process crashes, it does not recover. If a process never crashes during the run, it is considered correct or fault-free; otherwise it is considered to be faulty. After any crash, the topology changes, but the logarithmic properties of the hypercube are kept.

We consider that the primitives to send and receive a message are atomic, but the broadcast primitives are not.

A.4 The VCube

Let n be the number of processes in the system P . VCube [START_REF] Elias | VCube: A provably scalable distributed diagnosis algorithm[END_REF] is a distributed diagnosis algorithm that organizes the correct processes of the system P in a virtual hypercube-like topology. In a hypercube of d dimensions, called d-VCube, there are 2 d processes. A process i groups the other n -1 processes in log 2 n clusters, such that cluster number s has size 2 s-1 . The ordered set of processes in each cluster s is denoted by c i,s as follows, in which ⊕ denotes the bitwise exclusive or operator (xor).

A process i tests another process in the c i,s to check whether it is correct or faulty. It executes a test procedure and waits for a reply. If the correct reply is received within an expected time interval, the monitored process is considered to be alive. Otherwise, it is considered to be faulty. We should point out that in an asynchronous model, which is the case in the current work, VCube provides an ureliable failure detection since it can erroneously suspect a correct process (false suspicion). If later it detects its mistake, it corrects it. On the other hand, according to the properties proposed by Chandra and Toueg [START_REF] Deepak | Unreliable Failure Detectors for Reliable Distributed Systems[END_REF] for unreliable failure detectors, the VCube ensures the strong completeness property: eventually every process that crashes is permanently suspected by every correct process. Since there are false suspicions, the VCube does not provide any accuracy property. A VCube providing both completeness and accuracy could not possibly be implemented in a fully asynchronous system, according to Fischer, Lynch and Paterson [START_REF] Michael | Impossibility of Distributed Consensus with One Faulty Process[END_REF].

Timestamps are used to identify the latest state of the tested processes. Based on the replies of the tests, process i connects itself to one fault-free process of each cluster s, if it exists. If Algorithm 8 Reliable broadcast -process i

deliver(m) for all k = x : x, j, m ∈ ack_set i do 53:

check_acks(k, m) 55: when notifying crash(j) 56:

for all p = x, m = y : x, j, y ∈ ack_set i ∩ { * , j, * } do 58:

broadcast_cluster(p, m, cluster i (j)) 59:

A Reliable Broadcast Protocol for Asynchronous Systems with a Hypercube Topology delivered in increasing order of timestamps, provided no message is missing in the sequence of timestamps (lines 36 -42). In the same handle_message function, if i suspects that source(m) failed, it restarts the broadcast of last i [source(m)] (line 44) to ensure that every correct process receives the message even if source(m) crashed in the middle of the broadcast. Otherwise, by calling the function broadcast_tree with parameter h = cluster i (j) -1 (line 47), m is forwarded to all neighbors of i in each sub-cluster of i that should receive m. If process i is a leaf in the spanning tree of the broadcast (cluster i (j) -1 = 0) or if all neighbors of i (i.e., children of i in the tree) that should receive the message are suspected of being crashed, i sends an ACK message to the process which sent m to it, by calling function check_acks (line 34).

If process i receives a DELV, m message from j (line 49), it means that j falsely suspects i of being crashed and has decided to trust another process with the forwarding of the message to the rest of the tree. Therefore i can simply call the handle_message function to deliver the message and does not need to call broadcast_tree.

Whenever i receives a message ACK, m , it removes the corresponding ack from set of pending acks (line 53) and, by calling the function check_acks, if there are no more pending acks for message m, i sends an ACK message to the process j which sent m to it (line 34). If j = ⊥, the ACK message has reached the process that has broadcast m (source(m)) and the ACK message does not need to be forwarded.

The detection of the failure of process j is notified to i (crash(j)). It is worth pointing out that this detection might be a false suspicion. Three actions are taken by i upon receiving such a notification: (1) update of the set of processes that it considers correct (line 56); (2) removal from the set of pending acks of those acks whose related message m has been retransmitted to j (line 59); (3) re-sending to k, the next neighbor of j in the cluster of j (if k exists), of those messages previously sent to j. The re-sending of these messages triggers the propagation of messages over a new spanning tree (line 58). For instance, in Figure A.2(b), after the notification of the failure of p 4 , p 0 sends message m to p 5 since the latter is the next fault-free neighbor of p 4 in c 0,3 = {4, 5, 6, 7} (cluster s = 3) The message is then propagated to the other correct processes of the cluster, i.e., processes p 6 and p 7 . Notice that if p 4 is considered faulty by p 0 before the start of the broadcast, p 0 sends a DELV message to p 4 in order to ensure the reception and handle of m by p 4 . Finally, in case of crash of j, i has to re-broadcast the last message broadcast by j (line 62). Notice that, in this case, the history variable is used in order to prevent i from re-rebroadcasting the message to those clusters that i has already sent the same message.

If VCube detects that it had falsely suspected process j, it corrects its mistake and notifies i which then includes j in its set of correct processes (line 64).

A.5.3 Proof of correctness

In this section we will prove that Algorithm 8 implements a reliable broadcast.

Lemma A.1. Algorithm 8 ensures the validity property of reliable broadcast.

Proof. If a process i broadcasts a message m, the only way that i would not deliver m is if i waits forever on line 7. This wait is interrupted when the set ack_set i contains no more pending acknowledgements related to the message last i [i] previously broadcast by i.

For any process j that i sent last i [i] to, i added a pending ack in ack_set i (line 28). If j is correct, then it will eventually answer with an ACK message (line 34) and i will remove ⊥, j, last i [j] from ack_set i on line 53. If j is faulty, then i will eventually detect the crash and remove the pending ack on line 59.

As a result, all of the pending acks for last i [i] will eventually be removed from ack_set i and i will deliver m on line 9. Line 9 then ensures that i will deliver the message before broadcasting it.

Lemma A.2. For any processes i and j, the value of ts(last i [j]) only increases over time.

Proof. For the sake of simplicity, we take the convention that ts(⊥) = -1. The last i array is only modified on lines 8 and 40.

The first case can only happen when i broadcasts a new message m, and since timestamps of new messages sent by a same processes have to be increasing, ts(m) > ts(last i [i]). When i calls the broadcast procedure with m, ts(last i [i]) will therefore increase on line 8.

The other way for last i to be modified is on line 40. last i [source(l)] will then be updated with message l if last i [source(l)] = ⊥ and ts(l) = 0 (and therefore ts(last i [source(l)]) = -1 < ts(l)), or if ts(l) = ts(last i [source(l)]) + 1. It follows that last i [source(l) is only updated if the new value of ts(last i [source(l)]) would be superior to the old one.

Lemma A.3. Algorithm 8 ensures the integrity property of reliable broadcast.

Proof. Processes only deliver a message if they are broadcasting it themselves (line 9) or if the message is in their pending i set (line 42). Messages are only added to the pending i set on line 36, after they have been received from another process. Since the links are reliable and do not create messages, it follows that a message is delivered only if it was previously broadcast (there is no creation of messages).

To show that there is no duplication of messages, let us consider two cases:

• source(m) = i. Process i called the broadcast procedure with parameter m. As proved in Lemma A.1, i will deliver m on line 9. Since the broadcast procedure is only called once with a given message, the only way that i would deliver m a second time is on line 42. Since last i [i] was set to m on line 8, it follows from Lemma A.2 that m will never qualify to pass the test on lines 37 -39.

• source(m) = i. Process i is not the emitter of message m, and did not call the broadcast procedure with m. Therefore the only way for i to deliver m is on line 42. Before i delivers m for the first time, it sets last i [source(m)] to m on line 40. It then follows from Lemma A.2 that m will never again qualify to pass the test on lines 37 -39, and therefore i can deliver m at most once.

Lemma A.4. Algorithm 8 ensures the agreement property of reliable broadcast.

Proof. Let m be a message broadcast by a process i. We consider two cases: