Yoann Dieudonné et Stéphane Devismes (domaine ALCO) et Arnaud Labourel (LIS, Aix-Marseille université), ont publié leurs travaux dans l'édition 2026 de la conférence STOC - The 58th ACM Symposium on Theory of Computing. Cette conférence est unanimement reconnue comme la plus prestigieuse en informatique théorique. L'édition 2026 a d'ailleurs battu un record historique avec 752 soumissions.
L'article, intitulé « Can Like Attract Like? A Study of Homonymous Gathering in Networks », s'intéresse au problème du rassemblement d'agents dans un graphe, un problème fondamental en algorithmique distribuée mobile. Une hypothèse classique de la litérature sur ce problème consiste à supposer que chaque agent dispose d'un identifiant unique, appelé label. Ces labels jouent un rôle central pour briser les symétries potentielles qui, si elles persistent, rendent le rassemblement impossible.
Dans cet article, cette hypothèse est assouplie en autorisant l'existence d'agents homonymes, c'est-à-dire partageant le même label. Les auteurs établissent tout d'abord des conditions nécessaires et suffisantes pour que le problème du rassemblement soit solvable dans ce cadre. Ils proposent ensuite un algorithme qui résout le problème, dans tous les cas où ces conditions sont satisfaites, et dont la complexité est polynomiale en fonction de la taille n du réseau et du logarithme l du plus petit label. Cet algorithme repose sur une information initiale, appelée conseil, fournie à chaque agent et dont la taille est extrêmement réduite. Malgré sa petitesse, cette quantité d'information est essentielle : les auteurs démontrent en effet que la taille utilisée est nécessaire pour garantir un rassemblement en temps polynomial en fonction de n et de l.
Une conséquence majeure de ces travaux est l'obtention du premier algorithme déterministe résolvant le problème du rassemblement en un temps polynomial (en n et l), sans aucune connaissance préalable, dans le cas classique où les agents possèdent des labels distincts. Bien que la littérature sur le problème du rassemblement soit très abondante, cet algorithme constitue à ce jour la solution la plus efficace connue pour le résoudre.
