ISSN:
1432-0452
Keywords:
Byzantine Agreement
;
Distributed Consensus
;
Distributed systems
;
Early stopping
;
Fault-tolerance
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
Summary The problem of fault-tolerant agreement is fundamental to distributed computing. When agreement is to be reached in spite of arbitrary behavior by faulty processors, this problem is calledDistributed Consensus. By requiring that the number of faulty processors be $$O(\sqrt n )$$ , wheren is the number of processors in the system, we are able to derive two new protocols forDistributed Consensus. Both are simple and use messages that are only one bit in length, and both provide forearly stopping: the fewer failures there are, the fewer rounds of communication are required. One protocol is optimal with respect to the number of rounds of communication required, and the other is asymptotically optimal with respect to the total number of message bits exchanged.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02280828
Permalink
