[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Log in

Iterative approximate Byzantine consensus in arbitrary directed graphs

  • Published:
Distributed Computing Aims and scope Submit manuscript

Abstract

This paper identifies necessary and sufficient conditions for the existence of iterative algorithms that achieve approximate Byzantine consensus in arbitrary directed graphs, where each directed link represents a communication channel between a pair of nodes. The class of iterative algorithms considered in this paper ensures that, after each iteration of the algorithm, the state of each fault-free node remains in the convex hull of the states of the fault-free nodes at the end of the previous iteration. We present the necessary and sufficient condition for the existence of such iterative consensus algorithms in synchronous arbitrary point-to-point networks in presence of Byzantine faults in two different equivalent forms. We prove the necessity using an indistinguishability argument. For sufficiency, we develop a proof framework, which first uses a series of “transition matrices” to model the state evolution of the fault-free nodes using our algorithm, and then proves the correctness by identifying important properties of the matrices. The proof framework is useful for other iterative fault-tolerant algorithms. We discuss the extensions to asynchronous systems and the Byzantine links fault model.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Fig. 1
Fig. 2
Algorithm 1
Fig. 3
Algorithm 2

Similar content being viewed by others

Data availibility

Data sharing not applicable to this article as no datasets were generated or analysed during the current study.

Notes

  1. For sets X and Y, \(X-Y\) contains elements that are in X but not in Y. That is, \(X-Y=\{i\,|\, i\in X,\;i\not \in Y\}\).

  2. Note that we allow sets C and F to be empty. Sets LCRF are such that the intersection of any two of these sets is empty, and \(L\cup R\cup C\cup F=\mathcal {V}\).

  3. Note that in addition to t, the row vector \({\textbf{M}}_i[t]\) may depend on the state vector \({\textbf{v}}[t-1]\) as well as the behavior of the faulty nodes in \(\mathcal {F}\). For simplicity, the notation \({\textbf{M}}_i[t]\) does not explicitly represent this dependence.

  4. Such a non-zero column will exist in \({\textbf{H}}^{n-\phi -1}\) too. We use the loose bound of \(n-\phi \) to simplify the presentation.

  5. The superscript ‘a’ stands for asynchronous systems. \(R^{a}_{F}\) is defined with respect to the graph G, since it is only used for the purpose of analysis and is not used in the algorithm executed by the nodes.

  6. For example, the described case is possible in wireless network, if node i’s transmitter is broken while node i’s receiver and node j’s transmitter and receiver all function correctly.

  7. The superscript ‘l’ stands for link faults. \(R^{l}_{F}\) is defined with respect to the graph G, since it is only used for the purpose of analysis and is not used in the algorithm executed by the nodes.

References

  1. Antoniadis, K., Guerraoui, R., Malkhi, D., Seredinschi, D.: State machine replication is more expensive than consensus. In: Schmid, U., Widder, J. (eds.) 32nd International Symposium on Distributed Computing, DISC 2018, New Orleans, LA, USA, October 15–19, 2018, LIPIcs, vol. 121, pp. 7:1–7:18. Schloss Dagstuhl-Leibniz-Zentrum für Informatik (2018). https://doi.org/10.4230/LIPIcs.DISC.2018.7

  2. Attiya, H., Welch, J.: Distributed Computing: Fundamentals, Simulations, and Advanced Topics. Wiley Series on Parallel and Distributed Computing (2004)

  3. Azadmanesh, A., Bajwa, H.: Global convergence in partially fully connected networks (PFCN) with limited relays. In: Industrial Electronics Society, 2001. IECON ’01. The 27th Annual Conference of the IEEE, vol. 3(3), pp. 2022–2025 (2001). https://doi.org/10.1109/IECON.2001.975602

  4. Azadmanesh, M.H., Kieckhafer, R.: Asynchronous approximate agreement in partially connected networks. Int. J. Parallel Distrib. Syst. Netw. 5(1), 26–34 (2002)

    Google Scholar 

  5. Bénézit, F., Blondel, V.D., Thiran, P., Tsitsiklis, J.N., Vetterli, M.: Weighted gossip: distributed averaging using non-doubly stochastic matrices. In: IEEE International Symposium on Information Theory, ISIT 2010, June 13–18, 2010, Austin, Texas, USA, Proceedings, pp. 1753–1757. IEEE (2010). https://doi.org/10.1109/ISIT.2010.5513273

  6. Bertsekas, D.P., Tsitsiklis, J.N.: Parallel and Distributed Computation: Numerical Methods. Optimization and Neural Computation Series. Athena Scientific (1997)

  7. Biely, M., Widder, J., Charron-Bost, B., Gaillard, A., Hutle, M., Schiper, A.: Tolerating corrupted communication. In: Gupta, I., Wattenhofer, R. (eds.) Proceedings of the Twenty-Sixth Annual ACM Symposium on Principles of Distributed Computing, PODC 2007, Portland, Oregon, USA, August 12–15, 2007, pp. 244–253. ACM (2007). https://doi.org/10.1145/1281100.1281136

  8. Charron-Bost, B., Függer, M., Nowak, T.: Approximate consensus in highly dynamic networks: the role of averaging algorithms. In: Halldórsson, M.M., Iwama, K., Kobayashi, N., Speckmann, B. (eds.) Automata, Languages, and Programming—42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6–10, 2015, Proceedings, Part II, Lecture Notes in Computer Science, vol. 9135, pp. 528–539. Springer, Berlin (2015). https://doi.org/10.1007/978-3-662-47666-6_42

  9. Charron-Bost, B., Schiper, A.: The heard-of model: computing in distributed systems with benign faults. Distrib. Comput. 22(1), 49–71 (2009). https://doi.org/10.1007/s00446-009-0084-6

    Article  Google Scholar 

  10. Dasgupta, S., Papadimitriou, C., Vazirani, U.: Algorithms. McGraw-Hill Higher Education (2006)

  11. 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, 499–516 (1986). https://doi.org/10.1145/5925.5931

    Article  MathSciNet  Google Scholar 

  12. Fekete, A.D.: Asymptotically optimal algorithms for approximate agreement. In: Proceedings of the Fifth Annual ACM Symposium on Principles of Distributed Computing, PODC’86, pp. 73–87. ACM, New York (1986). https://doi.org/10.1145/10590.10597

  13. 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’85, pp. 59–70. ACM, New York (1985). https://doi.org/10.1145/323596.323602

  14. Fischer, M.J., Lynch, N.A., Paterson, M.S.: Impossibility of distributed consensus with one faulty process. J. ACM 32, 374–382 (1985). https://doi.org/10.1145/3149.214121

    Article  MathSciNet  Google Scholar 

  15. Függer, M., Nowak, T., Schwarz, M.: Tight bounds for asymptotic and approximate consensus. J. ACM 68(6), 46:1-46:35 (2021). https://doi.org/10.1145/3485242

    Article  MathSciNet  Google Scholar 

  16. Hajnal, J.: Weak ergodicity in non-homogeneous Markov chains. Proc. Camb. Philos. Soc. 54, 233–246 (1958)

    Article  MathSciNet  Google Scholar 

  17. Jadbabaie, A., Lin, J., Morse, A.S.: Coordination of groups of mobile autonomous agents using nearest neighbor rules. IEEE Trans. Autom. Control 48(6), 988–1001 (2003). https://doi.org/10.1109/TAC.2003.812781

    Article  MathSciNet  Google Scholar 

  18. Kieckhafer, R.M., Azadmanesh, M.H.: Low cost approximate agreement in partially connected networks. J. Comput. Inf. 3(1), 53–85 (1993)

    MathSciNet  Google Scholar 

  19. Lamport, L., Shostak, R., Pease, M.: The byzantine generals problem. ACM Trans. Program. Lang. Syst. (1982)

  20. LeBlanc, H., Koutsoukos, X.: Consensus in networked multi-agent systems with adversaries. In: 14th International conference on Hybrid Systems: Computation and Control (HSCC) (2011)

  21. LeBlanc, H., Koutsoukos, X.: Low complexity resilient consensus in networked multi-agent systems with adversaries. In: 15th International conference on Hybrid Systems: Computation and Control (HSCC) (2012)

  22. LeBlanc, H., Zhang, H., Koutsoukos, X., Sundaram, S.: Resilient asymptotic consensus in robust networks. IEEE J. Sel. Areas Commun. Special Issue Netw. Comput. 31, 766–781 (2013)

    Article  Google Scholar 

  23. Lynch, N.A.: Distributed Algorithms. Morgan Kaufmann (1996)

  24. Santoro, N., Widmayer, P.: Time is not a healer. In: Proceedings of the 6th Annual Symposium on Theoretical Aspects of Computer Science on STACS 89, pp. 304–313. Springer-Verlag New York, Inc., New York (1989). http://dl.acm.org/citation.cfm?id=73228.73254

  25. Santoro, N., Widmayer, P.: Agreement in synchronous networks with ubiquitous faults. Theor. Comput. Sci. 384(2–3), 232–249 (2007). https://doi.org/10.1016/j.tcs.2007.04.036

    Article  MathSciNet  Google Scholar 

  26. Su, L., Vaidya, N.H.: Reaching approximate byzantine consensus with multi-hop communication. In: Pelc, A., Schwarzmann, A.A. (eds.) Stabilization, Safety, and Security of Distributed Systems—17th International Symposium, SSS 2015, Edmonton, AB, Canada, August 18–21, 2015, Proceedings, Lecture Notes in Computer Science, vol. 9212, pp. 21–35. Springer, Berlin (2015). https://doi.org/10.1007/978-3-319-21741-3_2

  27. Tseng, L., Vaidya, N.H.: Asynchronous convex hull consensus in the presence of crash faults. In: Proceedings of the 2014 ACM Symposium on Principles of Distributed Computing, PODC’14, pp. 396–405. ACM, New York (2014). https://doi.org/10.1145/2611462.2611470

  28. Tseng, L., Vaidya, N.H.: Iterative approximate byzantine consensus under a generalized fault model. In: In International Conference on Distributed Computing and Networking (ICDCN) (2013)

  29. Vaidya, N.H.: Matrix representation of iterative approximate byzantine consensus in directed graphs. CoRR. arXiv:1203.1888 (2012)

  30. Vaidya, N.H.: Iterative byzantine vector consensus in incomplete graphs. In: In International Conference on Distributed Computing and Networking (ICDCN) (2014)

  31. Vaidya, N.H., Garg, V.K.: Byzantine vector consensus in complete graphs. In: Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing, PODC’13, pp. 65–73. ACM, New York (2013). https://doi.org/10.1145/2484239.2484256

  32. Vaidya, N.H., Tseng, L., Liang, G.: Iterative approximate byzantine consensus in arbitrary directed graphs. In: Proceedings of the Thirty-First Annual ACM Symposium on Principles of Distributed Computing, PODC’12. ACM (2012)

  33. Vaidya, N.H., Tseng, L., Liang, G.: Iterative approximate byzantine consensus in arbitrary directed graphs. CoRR arXiv:1201.4183 (2012)

  34. Vaidya, N.H., Tseng, L., Liang, G.: Iterative approximate byzantine consensus in arbitrary directed graphs—part II: Synchronous and asynchronous systems. CoRR arXiv:1202.6094 (2012)

  35. Wolfowitz, J.: Products of indecomposable, aperiodic, stochastic matrices. Proc. Am. Math. Soc. 14, 733–737 (1963)

    Article  MathSciNet  Google Scholar 

  36. Zhang, H., Sundaram, S.: Robustness of information diffusion algorithms to locally bounded adversaries. CoRR arXiv:1110.3843 (2011)

  37. Zhang, H., Sundaram, S.: Robustness of complex networks with implications for consensus and contagion. In: Proceedings of CDC 2012, the 51st IEEE Conference on Decision and Control (2012)

Download references

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Lewis Tseng.

Ethics declarations

Conflict of interest

This research is supported in part by National Science Foundation award CNS 1059540 and Army Research Office grant W-911-NF-0710287. Any opinions, findings, and conclusions or recommendations expressed here are those of the authors and do not necessarily reflect the views of the funding agencies or the U.S. government. The preliminary work was conducted while all three authors were affiliated with University of Illinois at Urbana-Champaign (UIUC).

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

A preliminary version of this work appeared at [32].

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Tseng, L., Liang, G. & Vaidya, N.H. Iterative approximate Byzantine consensus in arbitrary directed graphs. Distrib. Comput. 37, 225–246 (2024). https://doi.org/10.1007/s00446-024-00468-2

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00446-024-00468-2

Keywords

Navigation