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.
Defence : 12/07/2018 - 10h - Site Jussieu 26-00/101
Jury members :
Carole Delporte, Professeur à l'Université Paris Diderot [Rapporteur]
Roy Friedman, Professeur au Technion, Israel Institute of Technology [Rapporteur]
Arnaud Casteigts, MdC HDR à l'Université de Bordeaux
Sébastien Tixeuil, Professeur à Sorbonne Université
Luciana Arantes, MdC à Sorbonne Université
Pierre Sens, Professeur à Sorbonne Université
- E. Mauffret, D. Jeanneau, L. Arantes, P. Sens : “The Weakest Failure Detector to Solve the Mutual Exclusion Problem in an Unknown Dynamic Environment”, 20th International Conference on Distributed Computing and Networking (ICDCN 2019), Bangalore, India (2019)
- D. Jeanneau : “Détecteurs de fautes pour les systèmes distribués dynamiques”, thesis, defence 12/07/2018, supervision Sens, Pierre, rapporteurs : ARANTES Luciana (2018)
- E. Mauffret, D. Jeanneau, L. Arantes, P. Sens : “The Weakest Failure Detector to Solve the Mutual Exclusion Problem in an Unknown Dynamic Environment”, (2018)
- D. Jeanneau, Th. Rieutord, L. Arantes, P. Sens : “Détecteur de fautes pour le k-accord dans les systèmes inconnus et dynamiques”, ALGOTEL 2017 - 19es Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, Quiberon, France (2017)
- D. 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)
- D. 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)
- D. Jeanneau, Th. Rieutord, L. Arantes, P. Sens : “A Failure Detector for k-Set Agreement in Dynamic Systems”, NCA 2015 - 14th IEEE International Symposium on Network Computing and Applications, Cambridge, United States, pp. 176-183, (IEEE) (2015)
- D. Jeanneau, Th. Rieutord, L. Arantes, P. Sens : “A Failure Detector for k-Set Agreement in Asynchronous Dynamic Systems”, (2015)