Multidimensional agreement in Byzantine systems

Authors : Hammurabi Mendes , Maurice Herlihy , Nitin Vaidya , Vijay K. Garg Authors Info & Claims

New Citation Alert added!

This alert has been successfully added and will be sent to:

You will be notified whenever a record that you have chosen has been cited.

To manage your alert preferences, click on the button below.

New Citation Alert!

• Information & Contributors
• Bibliometrics & Citations
• View Options
• References
• Media
• Tables
• Share

Abstract

Consider a network of $$n$$n processes, where each process inputs a $$d$$d-dimensional vector of reals. All processes can communicate directly with others via reliable FIFO channels. We discuss two problems. The multidimensional Byzantine consensus problem, for synchronous systems, requires processes to decide on a single $$d$$d-dimensional vector $$v \in <\mathbb >^d$$v Rd, inside the convex hull of $$d$$d-dimensional vectors that were input by the non-faulty processes. Also, the multidimensional Byzantine approximate agreement (MBAA) problem, for asynchronous systems, requires processes to decide on multiple $$d$$d-dimensional vectors in $$<\mathbb >^d$$Rd, all within a fixed Euclidean distance $$\epsilon $$∈ of each other, and inside the convex hull of $$d$$d-dimensional vectors that were input by the non-faulty processes. We obtain the following results for the problems above, while tolerating up to $$f$$f Byzantine failures in systems with complete communication graphs: (1) In synchronous systems, $$n > \max \$$n>max is necessary and sufficient to solve the multidimensional consensus problem. (2) In asynchronous systems, $$n > (d+2)f$$n>(d+2)f is necessary and sufficient to solve the multidimensional approximate agreement problem. Our sufficiency proofs are constructive, giving explicit protocols for the problems. In particular, for the MBAA problem, we give two protocols with strictly different properties and applications.

References

Abraham, I., Amit, Y., Dolev, D.: Optimal resilience asynchronous approximate agreement. In: Higashino, T. (ed.) Principles of Distributed Systems. Lecture Notes in Computer Science, vol. 3544, pp. 229---239. Springer, Berlin (2005)

Agarwal, P.K., Sharir, M., Welzl, E.: Algorithms for center and Tverberg points. In: Proceedings of the 20th Annual Symposium on Computational Geometry (SCG), pp. 61---67. ACM, New York, NY, USA (2004)

Attiya, H., Welch, J.: Distributed Computing: Fundamentals, Simulations and Advanced Topics, 2nd edn. Wiley, New York (2004)

Ben-Or, M., Dolev, D., Hoch, E.: Brief announcement: simple gradecast based algorithms. In: Lynch, N., Shvartsman, A. (eds.) Distributed Computing. Lecture Notes in Computer Science, vol. 6343, pp. 194---197. Springer, Berlin (2010)

Bouzid, Z., Potop-Butucaru, M.G., Tixeuil, S.: Optimal Byzantine-resilient convergence in uni-dimensional robot networks. Theor. Comput. Sci. 411(34---36), 3154---3168 (2010)