Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadatas

Cited literature [16 references]  Display  Hide  Download
Contributor : Michel Hurfin <>
Submitted on : Wednesday, June 29, 2016 - 5:53:31 PM
Last modification on : Thursday, January 7, 2021 - 4:39:57 PM


Files produced by the author(s)



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⟩



Record views


Files downloads