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(t-cubed 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+T-cubed 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