Supervision : Franck PETIT

Co-supervision : DIEUDONNÉ Yoann, DUBOIS Swan

On the Deterministic Gathering of Mobile Agents

Distributed systems are a theoretical model with a huge application field. It can represent a multitude of systems in which several autonomous entities cooperate to achieve a common task. The applications range from computer science related ones like processes sharing memory inside a computer, computers exchanging messages, and cohorts of robots to understanding social animals behavior.
When the entities involved are able to move spontaneously, they are called mobile agents, and one of the most studied problems regarding mobile agents is gathering. The mobile agents are spread in an unknown environment, with no a priori information about the others and without the ability to communicate with other agents, unless colocated. Each of them gradually discovers its surroundings, meets some other agents, coordinates with them, until all agents are gathered and detect it. Once all agents gathered, they can communicate and coordinate for some future task.
This thesis addresses the feasibility and complexity of gathering, in particular when facing two major difficulties: asynchrony and occurrence of Byzantine faults. When tackling the former, the agents have no control over their speed, which can vary arbitrarily and independently from each other. This makes coordination more challenging. When facing the latter, some of the agents are Byzantine, they can be viewed as malicious and using the difficulty to distinguish them from other (good) agents to try to prevent the gathering.

2016-2023 Publications

• 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”, thesis, defence 09/26/2019, supervision Petit, Franck, co-supervision : 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)