On the Deterministic Gathering of Mobile Agents

PhD Thesis defended by Sébastien Bouchard (LIP6 Lab.)

On September 26th, 2019 (2:00pm)
Room 24.25.105 (Sorbonne Université)

Abstract:
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.

Jury:

  • Shantanu Das, McF, Aix-Marseille Université (examinateur)
  • Yoann Dieudonné, McF, Université de Picardie Jules Verne (encadrant)
  • Swan Dubois, McF, Sorbonne Université (encadrant)
  • Paola Flocchini, Pr, Univ. Ottawa (rapporteur)
  • Pierre Fraigniaud, DR, CNRS/IRIF (examinateur)
  • David Ilcinkas, McF HDR, Univ de Bordeaux (examinateur)
  • Franck Petit, Pr. des universités à Sorbonne Université (directeur)
  • Maria Poptop-Butucaru, Pr, Univ. Sorbonne (présidente du jury)