Direction de recherche : Franck PETIT

Co-encadrement : DIEUDONNÉ Yoann, DUBOIS Swan

À propos du rassemblement déterministe d'agents mobiles

Les systèmes distribués sont un modèle théorique capable de représenter une multitude de systèmes bâtis autour de la coopération d'entités autonomes dans le but d'accomplir une tâche commune. Leur champ applicatif est immense, et s'étend de l'informatique ou de la robotique, en modélisant des processus partageant la mémoire d'un ordinateur, des ordinateurs communiquant par envois de messages, ou encore des cohortes de robots, à la compréhension du comportement des animaux sociaux.
Les agents mobiles font partie des entités étudiées dans ce domaine. Ils se distinguent des autres notamment par leur capacité à se déplacer spontanément. L'une des tâches les plus étudiées les mettant en scène est celle du rassemblement. Les agents mobiles sont dispersés dans un environnement inconnu. Aucun d'eux n'a d'informations à propos des autres, ou la capacité de communiquer avec eux, à moins de se trouver au même endroit. Chacun d'eux découvre peu à peu les environs, rencontre d'autres agents et se coordonne avec eux jusqu'à ce que tous soient rassemblés et le détectent. Une fois tous les agents rassemblés, ils peuvent communiquer et se coordonner pour une autre tâche.
Cette thèse s'intéresse à la faisabilité et à l'efficience du rassemblement, en particulier face à deux difficultés majeures: l'asynchronie et l'occurrence de fautes Byzantines. Dans un contexte asynchrone, les agents n'ont aucun contrôle sur leur vitesse, qui peut varier arbitrairement et indépendamment des autres. Se coordonner est alors un défi. Quand une partie des agents subit des fautes Byzantines, on peut considérer ces agents comme malicieux, se fondant parmi les autres (bons) agents pour les induire en erreur et empêcher que le rassemblement ait lieu.

Publications 2016-2023

• 2023
  • S. Bouchard, Y. Dieudonné, A. Labourel, A. Pelc : “Almost-Optimal Deterministic Treasure Hunt in Unweighted Graphs”, ACM Transactions on Algorithms, vol. 19 (3), pp. 1-32, (Association for Computing Machinery) (2023)
• 2022
  • E. Blanchard, S. Bouchard, T. Selker : “Visual Secrets : A recognition-based security primitive and its use for boardroom voting”, (2022)
  • S. Bouchard, Y. Dieudonné, A. Lamani : “Byzantine gathering in polynomial time”, Distributed Computing, vol. 35 (3), pp. 235-263, (Springer Verlag) (2022)
• 2020
  • S. Bouchard, Y. Dieudonné, A. Pelc, F. Petit : “Almost Universal Anonymous Rendezvous in the Plane”, (2020)
  • S. Bouchard, Y. Dieudonné, A. Pelc : “Want to Gather? No Need to Chatter!”, (2020)
  • S. Bouchard, Y. Dieudonné, A. Pelc, F. Petit : “Deterministic Treasure Hunt in the Plane with Angular Hints”, Algorithmica, vol. 82 (11), pp. 3250-3281, (Springer Verlag) (2020)
  • S. Bouchard, Y. Dieudonné, A. Pelc : “Want to Gather? No Need to Chatter!”, PODC '20 - 39^th Symposium on Principles of Distributed Computing, Salerno / Virtual, Italy, pp. 253-262, (ACM) (2020)
  • S. Bouchard, Y. Dieudonné, A. Pelc, F. Petit : “Almost Universal Anonymous Rendezvous in the Plane”, SPAA '20: Proceedings of the 32^nd ACM Symposium on Parallelism in Algorithms and Architectures, Virtual Event, United States, pp. 117-127, (ACM) (2020)
• 2019
  • S. Bouchard : “À propos du rassemblement déterministe d’agents mobiles”, soutenance de thèse, soutenance 26/09/2019, direction de recherche Petit, Franck, co-encadrement : Dieudonné, Yoann, Dubois, Swan (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)
  • S. Bouchard, Y. Dieudonné, A. Pelc, F. Petit : “Trouver un trésor plus rapidement avec des conseils angulaires”, ALGOTEL 2019 - 21^es Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, Saint Laurent de la Cabrerisse, France (2019)
• 2018
  • S. Bouchard, Y. Dieudonné, A. Lamani : “Byzantine Gathering in Polynomial Time”, 45^th International Colloquium on Automata, Languages, and Programming (ICALP 2018), Prague, Czechia (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)
  • S. Bouchard, Y. Dieudonné, B. Ducourthial : “Rassemblement byzantin dans les réseaux”, 20^es Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications(ALGOTEL 2018), Roscoff, France (2018)
  • S. Bouchard, Y. Dieudonné, F. Petit, A. Pelc : “On Deterministic Rendezvous at a Node of Agents with Arbitrary Velocities”, Information Processing Letters, vol. 133, pp. 39-43, (Elsevier) (2018)
  • S. Bouchard, Y. Dieudonné, A. Pelc, F. Petit : “Deterministic Treasure Hunt in the Plane with Angular Hints”, 29^th International Symposium on Algorithms and Computation, ISAAC 2018, vol. 123, Leibniz International Proceedings in Informatics (LIPIcs), Jiaoxi Township, Taiwan, Province of China, pp. 48:1-48:13, (Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik) (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)
• 2016
  • S. Bouchard, Y. Dieudonné, B. Ducourthial : “Byzantine gathering in networks”, Distributed Computing, vol. 29 (6), pp. 435-457, (Springer Verlag) (2016)