Name
Abstract | ||
|---|---|---|
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 uncorrupt 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 an execution to be the number of uncorrupt processors whose output does not agree with the output of the majority of uncorrupt
processors. We show that if there are t corrupt processors, then any randomised protocol which has probability at least 1/2 + 1/ logn of loss less than $${\frac{t^{2/3}}{16fn^{1/3}\log^{5/3}{n}}}$$ requires at least f rounds. This also shows that lossless protocols require both $${{\tilde\Omega(n^{1/3})}}$$ rounds, and for at least one uncorrupt processor to send $${{\tilde\Omega(n^{1/3})}}$$ messages during the protocol. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1145/1146381.1146424 | Symposium on Principles of Distributed Computing |
Keywords | Field | DocType |
Byzantine Agreement,Scalable distributed protocol,Lower bounds,Malicious adversary | Binary logarithm,Computer science,Upper and lower bounds,Theoretical computer science,Probabilistic logic,Quantum Byzantine agreement,Synchronous network,Scalability,Distributed computing,Computation | Journal |
Volume | Issue | ISSN |
21 | 4 | 0178-2770 |
ISBN | Citations | PageRank |
1-59593-384-0 | 9 | 0.66 |
References | Authors | |
11 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Dan Holtby | 1 | 9 | 0.66 |
| Bruce M. Kapron | 2 | 308 | 26.02 |
| Valerie King | 3 | 1276 | 99.39 |