Description
Date depot: 1 octobre 2019
Titre: Distributed coordination algorithms in dynamic networks
Encadrante :
Luciana ARANTES (LIP6)
Directeur de thèse:
Pierre SENS (LIP6)
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Systèmes et réseaux
Resumé:
Distributed algorithms are traditionally conceived for message-passing distributed environments which are static and whose membership is known. However, new environments such as ad-hoc mobile wireless network (MANET) or sensor wireless network (WSN), peer-to peer networks, and opportunist grids or clouds provide access to services or information regardless of node location, mobility pattern, or global view of the system.
These new systems are dynamic, which means that the communication graph evolves over time, processes might join or leave the system, or crash and recover during the run. Additionally these systems are unknown, which means that processes do not initially know the membership of the system, and only discover it during the run. Therefore, distributed algorithms that run on top of these new systems cannot use prior distributed
models for static known systems.
This thesis focuses on building block algorithms for distributed systems in dynamic topologies, studying fundamental problems such as consensus [1, 2] and mutual exclusion [3]. For modeling the dynamics of the system and evolving communication between nodes, we will exploit the formalism of the Time-Varying Graphs (TVG) [4]. Delys has also been interested in failure detector (FD) [5] which is a fundamental abstraction for distributed algorithms. FDs have been widely used to solve agreement and locking problems in asynchronous systems prone to crash failures, but usually conceived for static environments and known network topologies. Hence, the objective in this thesis is also to propose efficient FDs algorithms for dynamic unknown networks which will be used
to solve agreement and mutual exclusion problems.
Proposed algorithms will be evaluated both on simulation using OMNet ++ tool and in real mobile sensor testbeds using FIT platform.
Doctorant.e: Favier Arnaud