Contributors: Networks and Performance Analysis (NPA); Laboratoire d'Informatique de Paris 6 (LIP6); Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS); Global parallel and distributed computing (GRAND-LARGE); Laboratoire de Recherche en Informatique (LRI); Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Laboratoire d'Informatique Fondamentale de Lille (LIFL); Université de Lille, Sciences et Technologies-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lille, Sciences Humaines et Sociales-Centre National de la Recherche Scientifique (CNRS)-Université de Lille, Sciences et Technologies-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lille, Sciences Humaines et Sociales-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France; Institut National de Recherche en Informatique et en Automatique (Inria); Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE); Inria Sophia Antipolis - Méditerranée (CRISAM); Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED); Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S); Université Nice Sophia Antipolis (1965 - 2019) (UNS)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UniCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UniCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S); Université Nice Sophia Antipolis (1965 - 2019) (UNS)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UniCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UniCA); Mathieu, Fabien; Hanusse, Nicolas; ANR-09-BLAN-0159,AGAPE,Algorithmes de graphes parametres et exacts(2009)
نبذة مختصرة : International audience ; 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 ...
Processing Request
No Comments.