ComputingComputer EngineeringComputer ScienceFault ToleranceFault-tolerant ComputingFault-tolerant SystemsClock SynchronizationData SynchronizationDistributed SynchronizationReliable Distributed SystemsAgreement AlgorithmsAgreement ProtocolsClock Synchronization Algorithms
An Inexact Agreement protocol alows processors that each have a value approximating $\hat{\nu}$ to compute new values that are closer to each other and close to $\hat{\nu}$. Two fault-tolerant protocols for Inexact Agreement are described. As long as fewer than 1/3 of the processors are faulty, the protocols give the required convergence; they also permit iteration and thus convergence to any desired precision. When between 1/3 and 2/3 of the processors are faulty, the protocols may not converge. However, then processors either detect that too many faults have occurred or the new values computed by processors remain close to each other and to $\hat{\nu}$. In this case, the divergence is bounded. Use of the protocols for clock synchronization in a distributed system is explained.
9
The Byzantine generals strike again
Danny Dolev · Journal of Algorithms · 1982 · 573 citations
Synchronizing clocks in the presence of faults
Leslie Lamport, P. M. Melliar‐Smith · Journal of the ACM · 1985 · 543 citations · Full text
Reaching approximate agreement in the presence of faults
Danny Dolev, Nancy Lynch, Shlomit S. Pinter et al. · Journal of the ACM · 1986 · 522 citations · Full text
Fred B. Schneider · ACM Transactions on Computer Systems · 1984 · 264 citations · Full text