Accession Number : ADA154770


Title :   The Byzantine Firing Squad Problem.


Descriptive Note : Technical memo.,


Corporate Author : MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR COMPUTER SCIENCE


Personal Author(s) : Burns,J E ; Lynch,N A


Full Text : https://apps.dtic.mil/dtic/tr/fulltext/u2/a154770.pdf


Report Date : Apr 1985


Pagination or Media Count : 21


Abstract : A new problem, the Byzantine Firing Squad problem, is defined and solved in two versions, Permissive and Strict. Both problems provide for synchronization of initially unsynchronized processors in a synchronous network, in the absence of a common clock and in the presence of a limited number of faulty processors. Solution are given which take the same number of rounds as Byzantine Agreement but might transmit r times as many bits, where r is the number of rounds used. Additional solutions are provided which use at most one (Permissive) or two (Strict) additional rounds and send at most n sub 2 bits plus four times the number of bits sent by a chosen Byzantine Agreement algorithm. Additional keywords: Computer communications. (Author)


Descriptors :   *ALGORITHMS , COMPUTER COMMUNICATIONS , CLOCKS


Subject Categories : Theoretical Mathematics


Distribution Statement : APPROVED FOR PUBLIC RELEASE