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
CentraleSupélec, Inria Rennes – Bretagne Atlantique , IRISA-D1 - SYSTÈMES LARGE ÉCHELLE
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

https://hal.inria.fr/hal-01339477
Contributor : Michel Hurfin <>
Submitted on : Wednesday, June 29, 2016 - 5:53:31 PM
Last modification on : Wednesday, April 8, 2020 - 4:11:51 PM

File

ipdps2016.pdf
Files produced by the author(s)

Identifiers

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

Share

Metrics

Record views

683

Files downloads

658