TY - JOUR

T1 - Multidimensional agreement in Byzantine systems

AU - Mendes, Hammurabi

AU - Herlihy, Maurice

AU - Vaidya, Nitin

AU - Garg, Vijay K.

N1 - Funding Information:
(M. Herlihy) Supported by NSF 0830491. (N. Vaidya and V. K. Garg) This research is supported in part by National Science Foundation awards CNS-1059540 and CNS-1115808, and the Cullen Trust for Higher Education. 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.
Publisher Copyright:
© 2014, Springer-Verlag Berlin Heidelberg.

PY - 2015/12/1

Y1 - 2015/12/1

N2 - Consider a network of n processes, where each process inputs a 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-dimensional vector ∈Rd, inside the convex hull of 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-dimensional vectors in Rd, all within a fixed Euclidean distance ϵ of each other, and inside the convex hull of 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 Byzantine failures in systems with complete communication graphs: (1) In synchronous systems, n>max{3f,(d+1)f} is necessary and sufficient to solve the multidimensional consensus problem. (2) In asynchronous systems, 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.

AB - Consider a network of n processes, where each process inputs a 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-dimensional vector ∈Rd, inside the convex hull of 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-dimensional vectors in Rd, all within a fixed Euclidean distance ϵ of each other, and inside the convex hull of 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 Byzantine failures in systems with complete communication graphs: (1) In synchronous systems, n>max{3f,(d+1)f} is necessary and sufficient to solve the multidimensional consensus problem. (2) In asynchronous systems, 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.

KW - Approximate agreement

KW - Byzantine protocols

KW - Higher dimension

KW - Vector inputs

UR - http://www.scopus.com/inward/record.url?scp=84947616271&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84947616271&partnerID=8YFLogxK

U2 - 10.1007/s00446-014-0240-5

DO - 10.1007/s00446-014-0240-5

M3 - Article

AN - SCOPUS:84947616271

SN - 0178-2770

VL - 28

SP - 423

EP - 441

JO - Distributed Computing

JF - Distributed Computing

IS - 6

ER -