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.

2014-2016 Publications

• 2016
  • M. Kaaouachi : “Une approche distribuée pour les problèmes de couverture dans les systèmes hautement dynamiques”, thesis, phd defence 01/12/2016, supervision Petit, Franck, co-supervision : Jouen, François, Dubois, Swan (2016)
  • N. Braud‑Santoni, S. Dubois, M. Kaaouachi, F. Petit : “The Next 700 Impossibility Results in Time-Varying Graphs”, International Journal of Networking and Computing, vol. 6 (1), pp. 27-41, (Higashi Hiroshima : Dept. of Computer Engineering, Hiroshima University) (2016)
• 2015
  • S. Dubois, M. Kaaouachi, F. Petit : “Dynamisme et Domination”, ALGOTEL 2015 — 17^es Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, Beaune, France (2015)
  • N. Braud‑Santoni, S. Dubois, M. Kaaouachi, F. Petit : “A Generic Framework for Impossibility Results in Time-Varying Graphs”, Parallel and Distributed Processing Symposium Workshop (IPDPSW), 2015 IEEE International, Hyderabad, India, pp. 483-489, (IEEE) (2015)
  • S. Dubois, M. Kaaouachi, F. Petit : “Enabling Minimal Dominating Set in Highly Dynamic Distributed Systems”, 17^th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS'15), vol. 9212, Lecture Notes in Computer Science, Edmonton, AB, Canada, pp. 51-66, (Springer) (2015)
• 2014
  • N. Braud‑Santoni, S. Dubois, M. Kaaouachi, F. Petit : “The Next 700 Impossibility Results in Time-Varying Graphs”, (2014)