Towards a Restrained Use of Non-equivocation for Achieving Iterative Approximate Byzantine Consensus - Archive ouverte HAL Access content directly
Conference Papers Year :

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

Vers une utilisation modérée de la diffusion non-équivoque pour résoudre itérativement le consensus approximé en présence de Byzantins

(1) , (1) , (2) , (3)
1
2
3

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.
Fichier principal
Vignette du fichier
ipdps2016.pdf (667.15 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01339477 , version 1 (29-06-2016)

Identifiers

Cite

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. pp.10, ⟨10.1109/IPDPS.2016.62⟩. ⟨hal-01339477⟩
297 View
375 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More