Multidimensional Byzantine Agreement in a Synchronous Setting
This work addresses consensus in distributed systems for applications requiring agreement on multiple data points, but it is incremental as it generalizes existing protocols to a multidimensional case.
The paper tackles the problem of achieving consensus on a vector of information in synchronous networks with Byzantine faults, presenting the Multidimensional Byzantine Agreement (MBA) Protocol which probabilistically halts and ensures security with less than one-third malicious nodes.
In this paper we will present the Multidimensional Byzantine Agreement (MBA) Protocol, a leaderless Byzantine agreement protocol defined for complete and synchronous networks that allows a network of nodes to reach consensus on a vector of relevant information regarding a set of observed events. The consensus process is carried out in parallel on each component, and the output is a vector whose components are either values with wide agreement in the network (even if no individual node agrees on every value) or a special value $\bot$ that signals irreconcilable disagreement. The MBA Protocol is probabilistic and its execution halts with probability 1, and the number of steps necessary to halt follows a Bernoulli-like distribution. The design combines a Multidimensional Graded Consensus and a Multidimensional Binary Byzantine Agreement, the generalization to the multidimensional case of two protocols by Micali and Feldman. We prove the correctness and security of the protocol assuming a synchronous network where less than a third of the nodes are malicious.