lower bound for scalable byzantine agreement
We consider the problem of computing Byzantine Agreement in a synchronous network with n processors each with a private random string, where each pair of processors is connected by a private communication line. The adversary is malicious and non-adaptive, i.e., it must choose the processors to corrupt at the start of the algorithm. Byzantine Agreement is known to be computable in this model in an expected constant number of rounds.We consider a scalable model where in each round each uncorrupted processor can send to any set of log n other processors and listen to any set of log n processors. We define the loss of a computation to be the number of uncorrupted processors whose output does not agree with the output of the majority of uncorrupted processors. We show that if there are t corrupted processors, then any protocol which has probability at least 1/2 +1/log n of loss less than t 2/3 32 fn 1/3 log 5/3 n requires at least f rounds.
lower bounds scalable byzantine agreement randomized probabilistic malicious adversary non-adaptive adversary distributed computing