Les Seigneurs des Anneaux Dangereux

Overview & Synopsis

Nous étudions une variante du problème classique de recherche de trou noir dans les graphes (_Black Hole Search_), où le nœud destructeur n'est pas présent initialement mais peut apparaître à tout instant durant l'exécution. Ce modèle capture des défaillances critiques soudaines dans des réseaux distribués (nœud compromis, panne fatale silencieuse). Nous nous concentrons sur des réseaux en anneau et analysons l'impact de cette émergence tardive sur la conception d'algorithmes à agents mobiles. Nous montrons que les stratégies classiques basées uniquement sur des marches prudentes ne suffisent plus et présentons plusieurs algorithmes pour agents synchrones et asynchrones sous différentes hypothèses (nombre d'agents, connaissance de la taille, usage de cailloux). Nous mettons en évidence les compromis entre nombre d'agents et complexité temporelle, ainsi que des impossibilités fondamentales induites par l'apparition tardive du danger.