Connaissance vs. Synchronie pour l'Accord Tolérant aux Pannes dans les Réseaux Inconnus

Fabiola Greve (1) , Sebastien Tixeuil (2, 3)

1 DCC - Computer Science Department [Bahía]
2 LRI - Laboratoire de Recherche en Informatique
3 GRAND-LARGE - Global parallel and distributed computing

Dans les réseaux auto-organisés, tels que les réseaux mobiles ad hoc et les réseaux pair-à-pair, le consensus est une brique fondamentale pour résoudre les problèmes d'accord. Il permet de coordoner les actions de noeuds répartis de manière ad hoc de telle sorte que des décisions cohérentes peuvent être prises. Il est notoire que dans les environnements classiques, où les entités se comportent de manière asynchrone et où les identités de chacun sont connues, le consensus ne peut être résolu dès qu'une panne crash est susceptible de se produire. Les systèmes auto-organisés renforcent ce résultat d'impossibilité car les identifiants des participants ne sont pas connus. Nous définissons des conditions nécessaires et suffisantes pour que le consensus puisse être résolu dans de tels environnements. Ces conditions sont liées aux hypothèses de synchronie sur l'environnement, ainsi qu'à la connectivité du graphe des connaissances induit par les noeuds qui souhaitent communiquer avec leurs pairs.

Domaines: Algorithme et structure de données [cs.DS]; Réseaux et télécommunications [cs.NI]

Fabiola Greve, Sebastien Tixeuil. Connaissance vs. Synchronie pour l'Accord Tolérant aux Pannes dans les Réseaux Inconnus. 9ème Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, May 2007, Ile d'Oléron, France. pp.67-70. ⟨inria-00176959⟩