
Accession Number : ADA113241
Title : A Simple and Efficient Byzantine Generals Algorithm.
Descriptive Note : Interim technical rept.,
Corporate Author : GEORGIA INST OF TECH ATLANTA SCHOOL OF INFORMATION AND COMPUTER SCIENCE
Personal Author(s) : Lynch,Nancy A ; Fischer,Michael J ; Fowler,Robert
PDF Url : ADA113241
Report Date : Feb 1982
Pagination or Media Count : 15
Abstract : The Byzantine Generals problem involves a system of N processes, t of which may be unreliable. The problem is for the reliable processes to agree on a binary value sent by a general, which may itself be one of the N processes. If the general sends the same value to each process, then all reliable processes must agree on that value, but in any case, they must agree on the same value. We give an explicit solution for N=3t+1 processes, using 2t+4 rounds and 0(tcubed log t) message bits, where t bounds the number of faulty processes. This solution is easily extended to the general case of N or = 3t+1 to give a solution using 2t+5 rounds and 0(tN+Tcubed log t) message bits. (Author)
Descriptors : *ALGORITHMS, PROBLEM SOLVING, MESSAGE PROCESSING, AUTOMATION, POLYNOMIALS, BINARY NOTATION, SET THEORY, VALUE, RELIABILITY
Subject Categories : Theoretical Mathematics
Distribution Statement : APPROVED FOR PUBLIC RELEASE