Reaching Approximate Agreement in the Presence of Faults
This paper considers a variant of the Byzantine Generals problem, in which processes start with arbitrary real values rather than Booleann values or values from some bounded range, and in which approximate, rather than exact, agreement is the desired goal. Algorithms are presented to reach approxima...
| Main Authors: | , , , , |
|---|---|
| Published: |
2023
|
| Online Access: | https://hdl.handle.net/1721.1/149061 |
| _version_ | 1826190140703244288 |
|---|---|
| author | Dolev, Danny Lynch, Nancy A. Pinter, Shlomit S. Stark, Eugene W. Weihl, William E. |
| author_facet | Dolev, Danny Lynch, Nancy A. Pinter, Shlomit S. Stark, Eugene W. Weihl, William E. |
| author_sort | Dolev, Danny |
| collection | MIT |
| description | This paper considers a variant of the Byzantine Generals problem, in which processes start with arbitrary real values rather than Booleann values or values from some bounded range, and in which approximate, rather than exact, agreement is the desired goal. Algorithms are presented to reach approximate agreement in aynchronous, as well as synchornous systems. The asynchronous agreement algorithm is an interesting contrast to a result of Fischer, Lynch, and Paterson, who show that exact agreement is not attainable in an asychronous system with as few as one fault process. The algorithms work by successive approximation, with a provable convergence rate that depends on the ratio between the number of faulty processes and the total number of processes. Lower bounds on the convergence rate for algorithms of this form are proven, and the algorithms presented are shown to be optimal. |
| first_indexed | 2024-09-23T08:35:39Z |
| id | mit-1721.1/149061 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T08:35:39Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | mit-1721.1/1490612023-03-30T04:20:18Z Reaching Approximate Agreement in the Presence of Faults Dolev, Danny Lynch, Nancy A. Pinter, Shlomit S. Stark, Eugene W. Weihl, William E. This paper considers a variant of the Byzantine Generals problem, in which processes start with arbitrary real values rather than Booleann values or values from some bounded range, and in which approximate, rather than exact, agreement is the desired goal. Algorithms are presented to reach approximate agreement in aynchronous, as well as synchornous systems. The asynchronous agreement algorithm is an interesting contrast to a result of Fischer, Lynch, and Paterson, who show that exact agreement is not attainable in an asychronous system with as few as one fault process. The algorithms work by successive approximation, with a provable convergence rate that depends on the ratio between the number of faulty processes and the total number of processes. Lower bounds on the convergence rate for algorithms of this form are proven, and the algorithms presented are shown to be optimal. 2023-03-29T14:23:55Z 2023-03-29T14:23:55Z 1985-10 https://hdl.handle.net/1721.1/149061 13340620 MIT-LCS-TM-251 application/pdf |
| spellingShingle | Dolev, Danny Lynch, Nancy A. Pinter, Shlomit S. Stark, Eugene W. Weihl, William E. Reaching Approximate Agreement in the Presence of Faults |
| title | Reaching Approximate Agreement in the Presence of Faults |
| title_full | Reaching Approximate Agreement in the Presence of Faults |
| title_fullStr | Reaching Approximate Agreement in the Presence of Faults |
| title_full_unstemmed | Reaching Approximate Agreement in the Presence of Faults |
| title_short | Reaching Approximate Agreement in the Presence of Faults |
| title_sort | reaching approximate agreement in the presence of faults |
| url | https://hdl.handle.net/1721.1/149061 |
| work_keys_str_mv | AT dolevdanny reachingapproximateagreementinthepresenceoffaults AT lynchnancya reachingapproximateagreementinthepresenceoffaults AT pintershlomits reachingapproximateagreementinthepresenceoffaults AT starkeugenew reachingapproximateagreementinthepresenceoffaults AT weihlwilliame reachingapproximateagreementinthepresenceoffaults |