Exact Byzantine Consensus in Directed Graphs
Exact Byzantine Consensus in Directed Graphs
复制标题
有向图中的精确拜占庭共识
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
N. Vaidya
中科院分区：
文献类型：
--
作者：
Lewis Tseng;N. Vaidya
对于无向链接的同步点对点N节点网络，先前已显示，为了在最多达到F拜占庭断层的情况下达成共识，以下两个条件是必要且足够的：（i）N≥3F + 1和（ii）网络连接大于2F，即n≥3f + 1也是有向图所必需的。对于迄今为止，在有向图中的拜占庭共识中，尚未开发出拜占庭式共识的足够紧密的条件通过提出新的拜占庭共识算法，为有向图提供了建设性的证明。拜占庭共识的开销。
For synchronous point-to-point n-node networks of undirected links, it has been previously shown that, to achieve consensus in presence of up to f Byzantine faults, the following two conditions are together necessary and sufficient: (i) n ≥ 3f + 1 and (ii) network connectivity greater than 2f . The first condition, that is, n ≥ 3f + 1, is known to be necessary for directed graphs as well. On the other hand, the second condition on connectivity is not necessary for directed graphs. So far, tight necessary and sufficient condition for Byzantine consensus in directed graphs has not been developed. This paper presents tight necessary and sufficient condition for achieving Byzantine consensus in synchronous networks that can be represented as directed graphs. We provide a constructive proof of sufficiency by presenting a new Byzantine consensus algorithm for directed graphs. Further work is needed to improve the message overhead of Byzantine consensus in directed graphs.