The Byzantine Firing Squad Problem.
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Apr 01, 1985
- Accession Number
- ADA154770
Entities
People
- J. E. Burns
- N. A. Lynch
Organizations
- Massachusetts Institute of Technology