Approximate Agreement.
Abstract
This paper studies the problem of Approximate Agreement a generalization of Byzantine Agreement, where processors are only required to obtain values that are close together, rather than identical. We offer new multi-round algorithms in several different models of computation, distinguished by the degree of synchrony in the system and the malevolence allowed to faulty processors. For each model we also examine the theoretical limits on attainable performance (measured by the reduction in the range of values), and show that our algorithm is asymptotically optimal with increasing ratio of non-faulty processors to faulty ones. There are two main conclusions we can draw from these algorithms and lower bounds. First, if process failures are restricted to faults of omission only (that is, a faulty processor is not allowed to send a wrong message, although it is allowed to crash, and therefore not send any message) then twice as much reduction can be achieved in each round of the algorithm as in a model where faults of commission are possible. This relationship holds in both synchronous and asynchronous systems. Second, we show that in synchronous systems algorithms that combine information from different rounds of message exchange can perform better than algorithms that treat each round separately. This extra performance is obtained by detecting which processors are faulty, and removing them from the system. In contrast, in asynchronous systems with faults of omission only there is no way to improve performance by using multiple rounds together.
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 01, 1987
- Accession Number
- ADA191030
Entities
People
- Alan D. Fekete
Organizations
- Massachusetts Institute of Technology