Reaching Approximate Byzantine Consensus in Partially-Connected Mobile Networks

Chuanyou Li 1 Michel Hurfin 2 Yun Wang 1
2 CIDRE - Confidentialité, Intégrité, Disponibilité et Répartition
IRISA-D1 - SYSTÈMES LARGE ÉCHELLE, Inria Rennes – Bretagne Atlantique , CentraleSupélec
Résumé : Nous considérons le problème du consensus approximatif dans des réseaux mobiles contenant des nœuds byzantins. Nous supposons que chaque nœud correct ne peut communiquer qu'avec ses voisins et n'a pas connaissance de la topologie globale. Comme tous les nœuds ont la possibilité de se déplacer, la topologie est dynamique. Le nombre de nœuds byzantins est borné par f et est connu de tous les nœuds corrects. Nous présentons tout d'abord un protocole de consensus approximatif byzantine qui est fondé sur la méthode d'itération linéaire. Comme les nœuds sont autorisés à collecter des informations lors de plusieurs tours consécutifs, le fait de se déplacer leur donne l'occasion de recueillir plus de valeurs. Nous proposons une nouvelle condition nécessaire et suffisante pour garantir la convergence finale du protocole de consensus. La contrainte exprimée par notre condition n'est pas "universelle": lors de chaque phase, elle ne concerne qu'un seul nœud correct. Plus précisément, au moins un nœud correct parmi ceux qui proposent la valeur minimale ou la valeur maximale présente dans le réseau, doit recevoir suffisamment de messages (contrainte sur la quantité) contenants des valeurs supérieures ou inférieures (contrainte sur la la qualité). Bien entendu, les déplacements des nœuds doivent permettre à cette condition d'être remplie. Notre conclusion montre que la condition proposée peut être satisfaite si le nombre total de nœuds est plus grand que 3f +1.
Type de document :
Rapport
[Research Report] RR-7985, INRIA. 2012, pp.17
Liste complète des métadonnées

Littérature citée [15 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00703111
Contributeur : Michel Hurfin <>
Soumis le : jeudi 31 mai 2012 - 20:19:28
Dernière modification le : mercredi 16 mai 2018 - 11:23:34
Document(s) archivé(s) le : jeudi 15 décembre 2016 - 10:18:00

Fichiers

RR-7985.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00703111, version 1
  • ARXIV : 1206.0089

Citation

Chuanyou Li, Michel Hurfin, Yun Wang. Reaching Approximate Byzantine Consensus in Partially-Connected Mobile Networks. [Research Report] RR-7985, INRIA. 2012, pp.17. 〈hal-00703111〉

Partager

Métriques

Consultations de la notice

610

Téléchargements de fichiers

200