Name
Title | ||
|---|---|---|
Towards a Restrained Use of Non-Equivocation for Achieving Iterative Approximate Byzantine Consensus |
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. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1109/IPDPS.2016.62 | 2016 IEEE International Parallel and Distributed Processing Symposium (IPDPS) |
Keywords | Field | DocType |
Approximate Consensus,Byzantine failure,Equivocation,Partial multicast,Iterative algorithm | Consensus,Asynchronous communication,Computer science,Iterative method,Byzantine fault tolerance,Network topology,Theoretical computer science,Multicast,Equivocation,Quantum Byzantine agreement,Distributed computing | Conference |
ISSN | ISBN | Citations |
1530-2075 | 978-1-5090-2141-3 | 1 |
PageRank | References | Authors |
0.36 | 13 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Chuanyou Li | 1 | 9 | 4.31 |
| Michel Hurfin | 2 | 266 | 29.30 |
| Yun Wang | 3 | 107 | 20.55 |
| Lei Yu | 4 | 1 | 0.36 |