Supervision : Pierre SENS

Co-supervision : ARANTES Luciana

Failure Detectors in Dynamic Distributed Systems

In the consensus problem, all correct processes in the system must agree on a same value. The k-set agreement problem is a generalization of consensus where processes can agree on up to k different values. The mutual exclusion problem requires processes to be able to access a critical section, such that no two processes can be in the critical section at the same time. These fundamental problems of distributed computing have been widely studied, but most existing solutions assume that the system is not dynamic.
Traditionally, distributed computing considers distributed systems where the system membership is static and the communication graph is connected or fully connected. But in order to model modern networks such as wireless or peer-to-peer networks, it is necessary to consider another kind of distributed systems. Dynamic systems are distributed systems in which (1) processes can join or leave the system during the run, and (2) the communication graph evolves over time.
The failure detector abstraction was introduced as a way to circumvent the impossibility of solving consensus in asynchronous systems prone to crash failures. A failure detector is a local oracle that provides processes in the system with unreliable information on process failures. But a failure detector that is sufficient to solve a given problem in a static system is not necessarily sufficient to solve the same problem in a dynamic system. Additionally, some existing failure detectors cannot be implemented in dynamic systems. Therefore, it is necessary to redefine existing failure detectors and provide new algorithms.
In this thesis, we provide a new definition of a failure detector for k-set agreement, and prove that it is sufficient to solve k-set agreement in dynamic systems. We also design a dynamic system model and an algorithm that implements this new failure detector.
Additionally, we adapt an existing failure detector for mutual exclusion and prove that it is still the weakest failure detector to solve mutual exclusion in dynamic systems, which means that it is weaker than any other failure detector capable of solving mutual exclusion.

2015-2019 Publications

• 2019
  • E. Mauffret, É. Jeanneau, L. Arantes, P. Sens : “The Weakest Failure Detector to Solve the Mutual Exclusion Problem in an Unknown Dynamic Environment”, 20^th International Conference on Distributed Computing and Networking (ICDCN 2019), Bangalore, India (2019)
• 2018
  • D. Jeanneau : “Détecteurs de fautes pour les systèmes distribués dynamiques”, thesis, phd defence 12/07/2018, supervision Sens, Pierre, co-supervision : Arantes, Luciana (2018)
  • E. Mauffret, É. Jeanneau, L. Arantes, P. Sens : “The Weakest Failure Detector to Solve the Mutual Exclusion Problem in an Unknown Dynamic Environment”, (2018)
• 2017
  • É. Jeanneau, Th. Rieutord, L. Arantes, P. Sens : “Détecteur de fautes pour le k-accord dans les systèmes inconnus et dynamiques”, ALGOTEL 2017 - 19^es Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, Quiberon, France (2017)
• 2016
  • É. Jeanneau, L. Rodrigues, E. Duarte Júnior, L. Arantes : “An Autonomic Hierarchical Reliable Broadcast Protocol for Asynchronous Distributed Systems with Failure Detector”, Latin-American Symposium on Dependable Computing (LADC), Cali, Colombia (2016)
  • É. Jeanneau, Th. Rieutord, L. Arantes, P. Sens : “Solving k-Set Agreement Using Failure Detectors in Unknown Dynamic Networks”, IEEE Transactions on Parallel and Distributed Systems, (Institute of Electrical and Electronics Engineers) (2016)
• 2015
  • É. Jeanneau, Th. Rieutord, L. Arantes, P. Sens : “A Failure Detector for k-Set Agreement in Dynamic Systems”, NCA 2015 - 14^th IEEE International Symposium on Network Computing and Applications, Cambridge, United States, pp. 176-183, (IEEE) (2015)
  • É. Jeanneau, Th. Rieutord, L. Arantes, P. Sens : “A Failure Detector for k-Set Agreement in Asynchronous Dynamic Systems”, (2015)