Reaching Approximate Byzantine Consensus with Multi-hop Communication

详细信息    查看全文

• 关键词：Approximate byzantine consensus ; Iterative algorithm ; Synchronous system ; Incomplete network ; Bounded length communication paths
• 刊名：Lecture Notes in Computer Science
• 出版年：2015
• 出版时间：2015
• 年：2015
• 卷：9212
• 期：1
• 页码：21-35
• 全文大小：266 KB
• 参考文献：1.Ali, J., Jie, L., Morse, A.S.: Coordination of groups of mobile autonomous agents using nearest neighbor rules. IEEE Transactions on Automatic Control 48(6), 988鈥?001 (2003)View Article
  2.Bnzit, F., Blondel, V., Thiran, P., Tsitsiklis, J., Vetterli, M.: Weighted gossip:Distributed averaging using non-doubly stochastic matrices. In: 2010 IEEE International Symposium on Information Theory Proceedings (ISIT), pp. 1753鈥?757, June 2010
  3.Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C., et al.: Introduction toalgorithms, vol. 2. MIT Press Cambridge (2001)
  4.Dolev, D., Lynch, N.A., Pinter, S.S., Stark, E.W., Weihl, W.E.: Reaching approximate agreement in the presence of faults. J. ACM 33(3), 499鈥?16 (1986)MathSciNet View Article
  5.Fekete, A.D.: Asymptotically optimal algorithms for approximate agreement. Distributed Computing 4(1), 9鈥?9 (1990)MathSciNet View Article
  6.Fischer, M.J., Lynch, N.A., Merritt, M.: Easy impossibility proofs for distributed consensus problems. In: Proceedings of the Fourth Annual ACM Symposium on Principles of Distributed Computing, PODC 1985, pp. 59鈥?0. ACM, New York (1985)
  7.Fischer, M.J., Lynch, N.A., Paterson, M.S.: Impossibility of distributed consensus with one faulty process. J. ACM 32, 374鈥?82 (1985)MathSciNet View Article
  8.LeBlanc, H.J., Zhang, H., Sundaram, S., Koutsoukos, X.: Consensus of multi-agent networks in the presence of adversaries using only local information. In: Proceedings of the 1st International Conference on High Confidence Networked Systems, HiCoNS 2012, pp. 1鈥?0. ACM, New York (2012)
  9.Pease, M., Shostak, R., Lamport, L.: Reaching agreement in the presence of faults. J. ACM 27(2), 228鈥?34 (1980)MathSciNet View Article
  10.Su, L., Vaidya, N.: Reaching approximate byzantine consensus with multi-hop communication (2014). arXiv preprint arXiv:鈥?411.鈥?282
  11. Tseng, L., Vaidya, N.: Iterative approximate consensus in the presence of byzantine link failures. In: Noubir, G., Raynal, M. (eds.) NETYS 2014. LNCS, vol. 8593, pp. 84鈥?8. Springer, Heidelberg (2014)
  12.Tseng, L., Vaidya, N.H.: Fault-tolerant consensus in directed graphs. In: Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing. ACM (to appear, 2015)
  13.Vaidya, N.H.: Matrix representation of iterative approximate byzantine consensus in directed graphs. CoRR, arXiv:鈥?203.鈥?888 (2012)
  14.Vaidya, N.H., Tseng, L., Liang, G.: Iterative approximate byzantine consensus in arbitrary directed graphs. In: Proceedings of the 2012 ACM Symposium on Principles of Distributed Computing, pp. 365鈥?74. ACM (2012)
  15.West, D.B., et al.: Introduction to graph theory, vol. 2. Prentice Hall, Upper Saddle River (2001)
  16.Zhang, H., Sundaram, S.: Robustness of information diffusion algorithms to locally bounded adversaries. In: American Control Conference (ACC 2012), pp. 5855鈥?861 (2012)
  
• 作者单位：Lili Su (15)
  Nitin Vaidya (15)
  
  15. Department of Electrical and Computer Engineering, University of Illinois at Urbana-Champaign, Urbana, USA
  
• 丛书名：Stabilization, Safety, and Security of Distributed Systems
• ISBN：978-3-319-21741-3
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

We address the problem of reaching approximate consensus in the presence of Byzantine faults in a synchronous system. We analyze iterative algorithms that maintain minimal state, and impose the constraint that in each iteration the nodes may only communicate with other nodes that are up to l hops away. For a given l, we prove a necessary and sufficient condition on the network structure for the existence of correct iterative algorithms that achieve approximate Byzantine consensus. We prove sufficiency of the condition by designing a correct algorithm, which uses a trim function based on a minimal messages cover property introduced in this paper. Our necessary and sufficient condition generalizes the tight condition identified in prior work for \(l=1\). For \(l\ge 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.