Towards a Restrained Use of Non-equivocation for Achieving Iterative Approximate Byzantine Consensus

Chuanyou Li 1 Michel Hurfin 1 Yun Wang 2 Lei Yu 3
1 CIDRE - Confidentialité, Intégrité, Disponibilité et Répartition
IRISA-D1 - SYSTÈMES LARGE ÉCHELLE, Inria Rennes – Bretagne Atlantique , CentraleSupélec
Abstract : We consider the approximate consensus problem in a partially connected network of n nodes where at most f nodes may suffer from Byzantine faults. We study under which conditions this problem can be solved using an iterative algorithm. A Byzantine node can equivocate: it may provide different values to its neighbors. To restrict the possibilities of equivocation, the 3-partial multicast primitive is considered. When a (correct or faulty) node uses this communication primitive, it provides necessarily the same value to the two identified receivers. Based on this communication primitive, a novel condition called f-resilient is proposed and proved to be necessary and sufficient to solve the approximate Byzantine consensus problem in a synchronous network. This condition takes into account two different communication primitives: unicast and 3-partial multicast. It expresses a trade-off between the two known approaches that make the problem solvable (increasing the number of neighbors or/and increasing the power of the communication primitives). The condition f-resilient does not require to eliminate all the possibilities of equivocation. Furthermore, it can be satisfied when there is just a majority of correct nodes. The relationships between the condition f-resilient and the condition h-disjoint (proposed by Alexander Jaffe et al. in 2012 to solve another problem, namely exact Byzantine consensus) are investigated. Two preliminary conclusions are obtained. When a network does not satisfy h-disjoint, it also does not satisfy f-resilient. But when a network satisfies h-disjoint, f-resilient is not necessarily satisfied. Finally, the condition is extended to cope with asynchronous networks.
Type de document :
Communication dans un congrès
30th IEEE International Parallel and Distributed Processing Symposium (IPDPS), May 2016, Chicago, United States. 2016 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pp.10, 〈http://www.ipdps.org/ipdps2016/〉. 〈10.1109/IPDPS.2016.62〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01339477
Contributeur : Michel Hurfin <>
Soumis le : mercredi 29 juin 2016 - 17:53:31
Dernière modification le : mercredi 16 mai 2018 - 11:23:35

Fichier

ipdps2016.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Chuanyou Li, Michel Hurfin, Yun Wang, Lei Yu. Towards a Restrained Use of Non-equivocation for Achieving Iterative Approximate Byzantine Consensus. 30th IEEE International Parallel and Distributed Processing Symposium (IPDPS), May 2016, Chicago, United States. 2016 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pp.10, 〈http://www.ipdps.org/ipdps2016/〉. 〈10.1109/IPDPS.2016.62〉. 〈hal-01339477〉

Partager

Métriques

Consultations de la notice

521

Téléchargements de fichiers

295