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 a computation 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 I corrupt processors, then any randomised protocol which has probability at least 1/2 -h 1/ log u of loss less
than t 2/3 / 16fn1/3log5/3n requires at least f rounds.
| Identifer | oai:union.ndltd.org:uvic.ca/oai:dspace.library.uvic.ca:1828/2069 |
| Date | 12 January 2010 |
| Creators | Holtby, Dan |
| Contributors | King, Valerie |
| Source Sets | University of Victoria |
| Language | English, English |
| Detected Language | English |
| Type | Thesis |
| Rights | Available to the World Wide Web |
Page generated in 0.0111 seconds