Exact Byzantine Consensus on Undirected Graphs under Local Broadcast Model
Exact Byzantine Consensus on Undirected Graphs under Local Broadcast Model
复制标题
本地广播模型下无向图的精确拜占庭共识
DOI：
10.1145/3293611.3331619
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Vaidya, Nitin H.
中科院分区：
文献类型：
--
作者：
Khan, Muhammad Samir;Naqvi, Syed Shalan;Vaidya, Nitin H.
This paper considers the Byzantine consensus problem for nodes with binary inputs. The nodes are interconnected by a network represented as an undirected graph, and the system is assumed to be synchronous. Under the classical point-to-point communication model, it is well-known that the following two conditions are both necessary and sufficient to achieve Byzantine consensus among n nodes in the presence of up to ƒ Byzantine faulty nodes: n & 3 #8805; 3 ≥ ƒ+ 1 and vertex connectivity at least 2 ƒ + 1. In the classical point-to-point communication model, it is possible for a faulty node to equivocate, i.e., transmit conflicting information to different neighbors. Such equivocation is possible because messages sent by a node to one of its neighbors are not overheard by other neighbors.This paper considers the local broadcast model. In contrast to the point-to-point communication model, in the local broadcast model, messages sent by a node are received identically by all of its neighbors. Thus, under the local broadcast model, attempts by a node to send conflicting information can be detected by its neighbors. Under this model, we show that the following two conditions are both necessary and sufficient for Byzantine consensus: vertex connectivity at least ⌋ 3 fƒ / 2 ⌊ + 1 and minimum node degree at least 2 ƒ. Observe that the local broadcast model results in a lower requirement for connectivity and the number of nodes n, as compared to the point-to-point communication model.We extend the above results to a hybrid model that allows some of the Byzantine faulty nodes to equivocate. The hybrid model bridges the gap between the point-to-point and local broadcast models, and helps to precisely characterize the trade-off between equivocation and network requirements.
登录
查看更多内容
本地广播模型下的精确拜占庭共识
DOI：
--
发表时间：
2018
期刊：
arXiv.org
影响因子：
--
作者：
Syed Shalan Naqvi;M. S. Khan;N. Vaidya
通讯作者：
N. Vaidya
DOI：
10.1016/0196-6774(82)90004-9
发表时间：
1981-03
期刊：
J. Algorithms
影响因子：
--
作者：
D. Dolev
通讯作者：
D. Dolev
有向图中的精确拜占庭共识
DOI：
--
发表时间：
2012
期刊：
arXiv.org
影响因子：
--
作者：
Lewis Tseng;N. Vaidya
通讯作者：
N. Vaidya
限制使用明确性来实现迭代近似拜占庭共识
DOI：
--
发表时间：
2016
期刊：
IEEE International Parallel and Distributed Processing Symposium
影响因子：
--
作者：
Chuanyou Li;Michel Hurfin;Yun Wang;Lei Yu
通讯作者：
Lei Yu
DOI：
--
发表时间：
2003
期刊：
ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing
影响因子：
--
作者：
S. Amitanand;I. Sanketh;K. Srinathan;V. Vaikuntanathan;C. Rangan
通讯作者：
C. Rangan