Towards a Restrained Use of Non-Equivocation for Achieving Iterative Approximate Byzantine Consensus
Towards a Restrained Use of Non-Equivocation for Achieving Iterative Approximate Byzantine Consensus
复制标题
限制使用明确性来实现迭代近似拜占庭共识
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Lei Yu
中科院分区：
文献类型：
--
作者：
Chuanyou Li;Michel Hurfin;Yun Wang;Lei Yu
我们考虑了N节点部分连接的网络中的近似共识问题，其中最多可能会遭受拜占庭断层的影响。我们研究了可以使用迭代算法解决此问题的条件。拜占庭节点可以等效：它可以为其邻居提供不同的值。为了限制模棱两可的可能性，考虑了三个派系原始原始。当（正确或错误的）节点使用此通信原始性时，它必须与两个已确定的接收器提供相同的值。基于这种通信原始的，提出了一种称为F-韧性的新型条件，并且被证明是必要的，足以解决同步网络中近乎拜占庭共识问题。该条件考虑了两个不同的通信原始词：单媒体和三个派系多播。它表示可以解决问题的两种已知方法之间的权衡（增加邻居的数量或/和增加了通信原始人的力量）。条件F-韧性不需要消除模棱两可的所有可能性。此外，只有大多数正确的节点就可以满足。研究了条件F-韧性与条件H-Dischoint（由Alexander Jaffe等人提出的2012年提出的解决另一个问题，即确切的拜占庭共识）之间的关系。获得了两个初步结论。当网络不满足H-Dischoint时，它也无法满足F弹性。但是，当网络满足H-Dischoint时，不一定会满足F弹性。最后，该条件扩展到应对异步网络。
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.