The Byzantine Firing Squad Problem
A new problem, the Byzanntine Firing Squad problem, is defined and solved in two versions, Permissive and Strict. Both problems provide for synchronization of initially unsychronized processors in a synchronous network, in the absense of a common clock and in the presence of a limited number of faul...
| Main Authors: | , |
|---|---|
| Published: |
2023
|
| Online Access: | https://hdl.handle.net/1721.1/149085 |
| _version_ | 1826193169399676928 |
|---|---|
| author | Burns, James E. Lynch, Nancy A. |
| author_facet | Burns, James E. Lynch, Nancy A. |
| author_sort | Burns, James E. |
| collection | MIT |
| description | A new problem, the Byzanntine Firing Squad problem, is defined and solved in two versions, Permissive and Strict. Both problems provide for synchronization of initially unsychronized processors in a synchronous network, in the absense of a common clock and in the presence of a limited number of faulty processors. Solutions 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^2 bits plus four times the number of bits sent by a chosen Byzantine Agreement algorithm. |
| first_indexed | 2024-09-23T09:34:49Z |
| id | mit-1721.1/149085 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T09:34:49Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | mit-1721.1/1490852023-03-30T04:10:23Z The Byzantine Firing Squad Problem Burns, James E. Lynch, Nancy A. A new problem, the Byzanntine Firing Squad problem, is defined and solved in two versions, Permissive and Strict. Both problems provide for synchronization of initially unsychronized processors in a synchronous network, in the absense of a common clock and in the presence of a limited number of faulty processors. Solutions 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^2 bits plus four times the number of bits sent by a chosen Byzantine Agreement algorithm. 2023-03-29T14:25:55Z 2023-03-29T14:25:55Z 1985-04 https://hdl.handle.net/1721.1/149085 14574398 MIT-LCS-TM-275 application/pdf |
| spellingShingle | Burns, James E. Lynch, Nancy A. The Byzantine Firing Squad Problem |
| title | The Byzantine Firing Squad Problem |
| title_full | The Byzantine Firing Squad Problem |
| title_fullStr | The Byzantine Firing Squad Problem |
| title_full_unstemmed | The Byzantine Firing Squad Problem |
| title_short | The Byzantine Firing Squad Problem |
| title_sort | byzantine firing squad problem |
| url | https://hdl.handle.net/1721.1/149085 |
| work_keys_str_mv | AT burnsjamese thebyzantinefiringsquadproblem AT lynchnancya thebyzantinefiringsquadproblem AT burnsjamese byzantinefiringsquadproblem AT lynchnancya byzantinefiringsquadproblem |