Multidimensional approximate agreement in Byzantine asynchronous systems

The problem of ε-approximate agreement in Byzantine asynchronous systems is well-understood when all values lie on the real line. In this paper, we generalize the problem to consider values that lie in R m , for m ≥ 1, and present an optimal protocol in regard to fault tolerance. Our scenario is the following. Processes start with values in R m , for m ≥ 1, and communicate via message-passing. The system is asynchronous : there is no upper bound on processes' relative speeds or on message delay. Some faulty processes can display arbitrarily malicious (i.e. Byzantine) behavior. Non-faulty processes must decide on values that are: (1) in R m ; (2) within distance ε of each other; and (3) in the convex hull of the non-faulty processes' inputs. We give an algorithm with a matching lower bound on fault tolerance: we require n > t(m+2), where n is the number of processes, t is the number of Byzantine processes, and input and output values reside in R m . Non-faulty processes send O(n 2 d log(m/ε max{δ(d): 1 ≤ d ≤ m})) messages in total, where δ(d) is the range of non-faulty inputs projected at coordinate d. The Byzantine processes do not affect the algorithm's running time.

Authors

• Hammurabi Mendes
• Maurice Herlihy

Keywords

• approximate agreement
• asynchronous systems
• byzantine protocols
• higher dimension