Nettoyage perpétuel de réseaux

Lélia Blin (1) , Janna Burman (2) , Nicolas Nisse (3)

1 NPA - Networks and Performance Analysis
2 GRAND-LARGE - Global parallel and distributed computing
3 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications

Dans le cadre du nettoyage de graphes contaminés ( graph searching), des agents mobiles se déplacent successivement le long des arêtes du graphe afin de les nettoyer. Le but général est le nettoyage en utilisant le moins d'agents possible. Nous plaçons notre étude dans le modèle de calcul distribué CORDA minimaliste. Ce modèle est muni d'hypothèses très faibles : les nœuds du réseau et les agents sont anonymes, n'ont pas de mémoire du passé ni sens commun de l'orientation et agissent par cycles Voir-Calculer-Agir de manière asynchrone. Un intérêt de ce modèle vient du fait que si le nettoyage peut être fait à partir de positions arbitraires des agents (par exemple, après pannes ou recontamination), l'absence de mémoire implique un nettoyage perpétuel et donc fournit une première approche de nettoyage de graphe tolérant aux pannes. Les contraintes dues au modèle CORDA minimaliste nous amènent à définir une nouvelle variante de nettoyage de graphes - le nettoyage sans collision, autrement dit, plusieurs agents ne peuvent occuper simultanément un même sommet. Nous montrons que, dans un contexte centralisé, cette variante ne satisfait pas certaines propriétés classiques de nettoyage comme par exemple la monotonie. Nous montrons qu'interdire les ''collisions'' peut augmenter le nombre d'agents nécessaires d'un facteur au plus $\Delta$ le degré maximum du graphe et nous illustrons cette borne. De plus, nous caractérisons complètement le nettoyage sans collision dans les arbres. Dans le contexte distribué, la question qui se pose est la suivante. Existe-t-il un algorithme qui, étant donné un ensemble d'agents mobiles arbitrairement répartis sur des sommets distincts d'un réseau, permet aux agents de nettoyer perpétuellement le graphe ? Dans le cas des chemins, nous montrons que la réponse est négative si le nombre d'agents est pair dans un chemin d'ordre impair, ou si il y a au plus deux agents dans un chemin d'ordre au moins $3$. Nous proposons un algorithme qui nettoie les chemins dans tous les cas restants, ainsi qu'un algorithme pour nettoyer les arbres lorsqu'un nombre suffisant d'agents est disponible initialement.

Domaines: Mathématique discrète [cs.DM]; Algorithme et structure de données [cs.DS]

Lélia Blin, Janna Burman, Nicolas Nisse. Nettoyage perpétuel de réseaux. 14èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel), 2012, La Grande Motte, France. pp.4. ⟨hal-00687134⟩