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

Fabiola Greve 1 Sebastien Tixeuil 2, 3
3 GRAND-LARGE - Global parallel and distributed computing
LRI - Laboratoire de Recherche en Informatique, LIFL - Laboratoire d'Informatique Fondamentale de Lille, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8623
Résumé : 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.
Complete list of metadatas

Cited literature [6 references]  Display  Hide  Download

https://hal.inria.fr/inria-00176959
Contributor : David Coudert <>
Submitted on : Friday, October 5, 2007 - 1:40:28 AM
Last modification on : Thursday, February 21, 2019 - 10:52:50 AM
Long-term archiving on : Monday, September 24, 2012 - 1:11:45 PM

File

57-algotel07_final.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : inria-00176959, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

279

Files downloads

192