Reaching approximate Byzantine consensus with multi-hop communication

被引：22
作者：
Su, Lili [1 ]
Vaidya, Nitin H.
机构：
[1] Univ Illinois, Dept Elect & Comp Engn, Urbana, IL 61801 USA
来源：
INFORMATION AND COMPUTATION | 2017年 / 255卷
基金：
美国国家科学基金会;
关键词：
Approximate agreement; Bounded length communication paths; Byzantine protocols; Synchronous systems; ALGORITHMS; AGREEMENT;
D O I：
10.1016/j.ic.2016.12.003
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We are interested in approximate Byzantine consensus problem, wherein all the fault-free processes reach consensus asymptotically (approximately in finite time). In particular, we focus on the algorithms under which each process communicates with other processes that are up to l hops away and maintains minimal states across iterations. For a given l, we identify a necessary and sufficient condition on the network structure for the existence of iterative algorithms of interest. Our necessary and sufficient condition generalizes the tight condition identified in prior work for l = 1. For l > l*, where l* is the length of a longest cycle-free path in the given network, our condition is equivalent to the necessary and sufficient conditions for exact consensus in undirected and directed networks both. (C) 2016 Elsevier Inc. All rights reserved.
引用
收藏
页码：352 / 368
页数：17
相关论文
共 20 条
  • [11] Hajnal J., 1958, P CAMBRIDGE PHILOS S, V54, P233, DOI DOI 10.1017/S0305004100033399
  • [12] Coordination of groups of mobile autonomous agents using nearest neighbor rules
    Jadbabaie, A
    Lin, J
    Morse, AS
    [J]. IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 2003, 48 (06) : 988 - 1001
  • [13] LeBlanc HJ, 2012, HICONS 12: PROCEEDINGS OF THE 1ST ACM INTERNATIONAL CONFERENCE ON HIGH CONFIDENCE NETWORKED SYSTEMS, P1
  • [14] Lili Su, 2015, Stabilization, Safety and Security of Distributed Systems. 17th International Symposium, SSS 2015. Proceedings: LNCS 9212, P21, DOI 10.1007/978-3-319-21741-3_2
  • [15] REACHING AGREEMENT IN THE PRESENCE OF FAULTS
    PEASE, M
    SHOSTAK, R
    LAMPORT, L
    [J]. JOURNAL OF THE ACM, 1980, 27 (02) : 228 - 234
  • [16] Information consensus in multivehicle cooperative control
    Ren, Wei
    Beard, Randal W.
    Atkins, Ella M.
    [J]. IEEE CONTROL SYSTEMS MAGAZINE, 2007, 27 (02): : 71 - 82
  • [17] Fault-Tolerant Consensus in Directed Graphs
    Tseng, Lewis
    Vaidya, Nitin H.
    [J]. PODC'15: PROCEEDINGS OF THE 2015 ACM SYMPOSIUM ON PRINCIPLES OF DISTRIBUTED COMPUTING, 2015, : 451 - 460
  • [18] Vaidya N. H., ARXIV12031888
  • [19] Wolfowitz J., 1963, Proceedings of the American Mathematical Society, V14, P733, DOI [10.1090/S0002-9939-1963-0154756-3, DOI 10.1090/S0002-9939-1963-0154756-3, 10.1090/ S0002-9939-1963-0154756-3]
  • [20] Zhang HT, 2012, P AMER CONTR CONF, P5855
12