Short Note on Complexity of Multi-Value Byzantine Agreement

摘要

Inspired by (4), and the deterministic multi-valued Byzantine agreement algorithm in our recent technical report (5), we derive a randomized algorithm that achieves multi-valued Byzantine agreement with high probability, and achieves optimal complexity. The discussion in this note is not self- contained, and relies heavily on the material in (5) please refer to (5) for the necessary background. Consider a synchronous fully connected network with n nodes, namely 0; 1; : : : ; n-1. Let node 0 be the source; the other n 1 nodes are called peers. At most t is less than n=3 nodes can be faulty. The goal here is for the n 1 peers to agree on the values sent by the source (similar to the Byzantine Generals problem in the work of Pease, Shostak and Lamport). This is also known as the broadcast problem. Our algorithm achieves agreement on a long message of l bits with high probability. Similar to the algorithm in (5), the proposed randomized Byzantine agreement algorithm progresses in generations. In each generation, D bits are being agreed upon, with the total number of generations being l=D. For convenience, we assume l to be an integral multiple of D.