PhD graduated
Team : DELYS
Departure date : 12/25/2018

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é

2015-2019 Publications