KAAOUACHI Mohamed Hamza

PhD graduated
Team : REGAL
Departure date : 01/18/2016

Supervision : Franck PETIT

Co-supervision : JOUEN François, DUBOIS Swan

A distributed approach for covering problems in highly dynamic systems

A distributed system is a system of autonomous computing components endowed with communication abilities. This is a common model for the study of networks. The quick evolution of wireless and mobile network both in everyday life and in research gradually leads to take in account the dynamics (i.e. the evolution over time) in distributed systems. Concretely, this means to add the assumption that the communication abilities of the components of the system may vary over time.
Many models consider the dynamics as an integral component of the system (and not as a fault). Recently, a new approach, called time-varying graph, attempts to unify all these models in a common formalism which allows the classification systems based on their temporal connectivity properties. In this thesis, we are interested in highly dynamic distributed systems with minimal connectivity assumptions. Specifically, we focus on connected over time systems where the only guarantee is that any element of the system can infinitely often send a message to any other (no guarantee are provided on the sustainability of the used path nor on the time communication). We are particularly interested in covering problems (e.g., minimal dominanting set, maximal matching, maximal independent set, ...) in these highly dynamic distributed systems.
The contributions of this thesis in this context are as follows. We first propose a new definition for the covering problems which is more suited to highly dynamic distributed systems that the existing definitions. Secondly, we provide a generic tool to simplify proof of impossibility results in dynamic distributed systems. We use this tool to prove some impossibility results of covering problems. Then, we propose a new time complexity measure to fairly compare the algorithms performance in dynamic distributed systems. Finally, we give an algorithm that compute a minimal dominating set in highly dynamic distributed systems.

Defence : 01/12/2016

Jury members :

M. Vincent Villain, Laboratoire Modélisation, Information & Systèmes, Université de Picardie Jules Verne [Rapporteur]
M. Eddy Caron, Laboratoire de l'Informatique du Parallélisme, ENS de Lyon [Rapporteur]
Mme. Lélia Blin, LIP6, UPMC
M. Marc Bui, Laboratoire Cognition Humaine et Artificielle, École Pratique des Hautes Études
M. Arnaud Casteigts, LaBRI, Université de Bordeaux
M. Swan Dubois, LIP6, UPMC
M. Franck Petit, LIP6, UPMC
M. François Jouen, Laboratoire Cognition Humaine et Artificielle, École Pratique des Hautes Études

Departure date : 01/18/2016

2014-2016 Publications