Relatore : Franck PETIT

Co-relazione : DUBOIS Swan, DIEUDONNÉ Yoann

Graceful Degradation and Speculation for Robots in Highly Dynamic Environments

Distributed systems are systems composed of multiple communicant processes cooperating to solve a common task. This is a generic model for numerous real systems as wired or mobile networks, shared-memory multiprocessor systems, and so on. From an algorithmic point of view, it is well-known that strong assumptions (as asynchronism or mobility) on such systems lead often to impossibility results or high lower bounds on complexity. In this thesis, we study algorithms that adapt themselves to their environment (i.e., the union of all assumptions on the system) by focusing on the two following approaches. Graceful degradation circumvents impossibility results by degrading the properties offered by the algorithm as the environment become stronger. Speculation allows to bypass high lower bounds on complexity by optimizing the algorithm only on more probable environments.
Robot networks are a particular case of distributed systems where processes are endowed with sensors and able to move from a location to another. We consider dynamic environments in which this ability may evolve with time. This thesis answers positively to the open question whether it is possible and attractive to apply gracefully degrading and speculative approaches to robot networks in dynamic environments. This answer is obtained through contributions on gracefully degrading gathering (where all robots have to meet on the same location in finite time) and on speculative perpetual exploration (where robots must visit infinitely often each location).

Pubblicazioni 2015-2019

• 2019
  • M. Bournat : “Graceful Degradation and Speculation for Robots in Highly Dynamic Environments”, these, difesa 06/27/2019, relatore Petit, Franck, co-relazione : Dubois, Swan, Dieudonné, Yoann (2019)
  • S. Bouchard, M. Bournat, Y. Dieudonné, S. Dubois, F. Petit : “Asynchronous approach in the plane: a deterministic polynomial algorithm”, Distributed Computing, vol. 32 (4), pp. 317-337, (Springer Verlag) (2019)
  • M. Bournat, A. Datta, S. Dubois : “Self-stabilizing robots in highly dynamic environments”, Theoretical Computer Science, vol. 772, pp. 88-110, (Elsevier) (2019)
• 2018
  • M. Bournat, S. Dubois, F. Petit : “Gracefully Degrading Gathering in Dynamic Rings”, Stabilization, Safety, and Security of Distributed Systems - 20^th International Symposium, SSS 2018, vol. 11201, Lecture Notes in Computer Science, Tokyo, Japan, pp. 349-364, (Springer) (2018)
  • S. Bouchard, M. Bournat, Y. Dieudonné, S. Dubois, F. Petit : “Approche asynchrone dans le plan : un algorithme déterministe polynomial”, ALGOTEL 2018 - 20^es Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, Roscoff, France (2018)
  • M. Bournat, S. Dubois, F. Petit : “Gracefully Degrading Gathering in Dynamic Rings”, (2018)
• 2017
  • S. Bouchard, M. Bournat, Y. Dieudonné, S. Dubois, F. Petit : “Asynchronous Approach in the Plane: A Deterministic Polynomial Algorithm”, 31^st International Symposium on Distributed Computing, DISC 2017, Vienna, Austria (2017)
  • M. Bournat, S. Dubois, F. Petit : “Computability of Perpetual Exploration in Highly Dynamic Rings”, The 37^th IEEE International Conference on Distributed Computing Systems (ICDCS 2017), Atlanta, United States (2017)
  • M. Bournat, S. Dubois, F. Petit : “Quel est le nombre optimal de robots pour explorer un anneau hautement dynamique ?”, ALGOTEL 2017 - 19^es Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, Quiberon, France (2017)
• 2016
  • M. Bournat, S. Dubois, F. Petit : “Computability of Perpetual Exploration in Highly Dynamic Rings”, (2016)
  • M. Bournat, A. Datta, S. Dubois : “Self-Stabilizing Robots in Highly Dynamic Environments”, SSS 2016 - 18^th International Symposium Stabilization, Safety, and Security of Distributed Systems, vol. 10083, Lecture Notes in Computer Science, Lyon, France, pp. 54-69, (Springer) (2016)
  • M. Bournat, Ajoy K. Datta, S. Dubois : “Self-Stabilizing Robots in Highly Dynamic Environments”, (2016)
• 2015
  • L. Arantes, M. Bournat, R. Friedman, O. Marin, P. Sens : “Elastic Management of Byzantine Faults”, 11^th European Dependable Computing Conference (EDCC 2015), Proceedings of Fast Abstract - EDCC 2015, Paris, France (2015)