Danny Dolev
Nancy A. Lynch
Abstract
This paper considers a variant of the Byzantine Generals problem, in which processes start with arbitrary real values rather than Boolean 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 asynchronous, as well as synchronous systems. The asynchronous agreement algorithm is an interesting contrast to a result of Fischer et al, who show that exact agreement with guaranteed termination is not attainable in an asynchronous system with as few as one faulty 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 proved, and the algorithms presented are shown to be optimal.
- 1 BENOR, M. Another advantage of free choice: Completely asynchronous agreement protocol. In Proceedings of the 2nd Annual ACM Symposium on Principles of Distributed Computing (Montreal, Ontario, Canada, Aug. 17-19). ACM, New York, 1983, pp. 27-30. Google Scholar
- 2 BRACHA, G. An asynchronous t(n - 1)/3J-resilient consensus protocol. In Proceedings of the 3rd ACM Symposium on Principles of Distributed Computing (Vancouver, B.C., Canada, Aug. 27-29). ACM, New York, 1984, pp. 154-162. Google Scholar
- 3 BRACHA, G., AND TOUEG, S. Asynchronous consensus and broadcast protocols. J. ACM 32, 4 (Oct. 1985), 824-840. Google Scholar
- 4 DOLEV, D., AND STRONG, H. R. Polynomial algorithms for multiple processor agreement. In Proceedings of the 14th ACM Symposium on Theory of Computing (San Francisco, Calif., May 5-7). ACM, New York, 1982, pp. 401-407. Google Scholar
- 5 DOLEV, D., DWORK, C., AND STOCKMEYER, L. On the minimal synchronism needed for distributed consensus. In Proceedings of 24th Annual Symposium on Foundations of Computer Science (Nov.). IEEE, New York, 1983, pp. 393-402.Google Scholar
- 6 DOLEV, D., LYNCH, N. A., PINTER, S., STARK, E. W., AND WEIHL, W.E. Reaching approximate agreement in the presence of faults. In Proceedings of 3rd Annual IEEE Symposium on Reliability in Distributed Software and Database Systems (Oct.). IEEE, New York, 1983, pp. 145-154.Google Scholar
- 7 FISCHER, M., AND LYNCH, N.A. A lower bound for the time to assure interactive consistency. Inf. Proc. Left 14, 4 (June 1982), 183-186.Google Scholar
- 8 FISCHER, M., LYNCH, N. A., AND MERRITT, M. Easy impossibility proofs for distributed consensus problems. Distr. Comput. 1, 1 (1986). Google Scholar
- 9 FISCHER, M. J., LYNCH, N. A., AND PATERSON, M.S. Impossibility of distributed consensus with one faulty process. J. ACM 32, 2 (Apr. 1985), 374-382. Google Scholar
- 10 LAMPORT, L., SHOSTAK, R., AND PEASE, M. The Byzantine generals problems. ACM Trans. Program. Lang. Syst. 4, 2 (1982), 382-401. Google Scholar
- 11 LUNDELIUS, J., AND LYNCH, N.A. A new fault-tolerant algorithm for clock synchronization. In Proceedings of 3rd ACM Symposium on Principles of Distributed Computing (Vancouver, B.C., Canada, Aug. 27-29). ACM, New York, 1984, pp. 75-88. Google Scholar
- 12 PEASE, M., SHOSTAK, R., AND LAMPORT, L. Reaching agreement in the presence of faults. J. ACM 27, 2 (1980), 228-234. Google Scholar
Index Terms
- Reaching approximate agreement in the presence of faults
Recommendations
Multidimensional approximate agreement in Byzantine asynchronous systems
STOC '13: Proceedings of the forty-fifth annual ACM symposium on Theory of ComputingThe problem of ε-approximate agreement in Byzantine asynchronous systems is well-understood when all values lie on the real line. In this paper, we generalize the problem to consider values that lie in Rm, for m ≥ 1, and present an optimal protocol in ...
Reaching Agreement in the Presence of Faults
The problem addressed here concerns a set of isolated processors, some unknown subset of which may be faulty, that communicate only by means of two-party messages. Each nonfaulty processor has a private value of information that must be communicated to ...
Reaching Approximate Agreement with Mixed-Mode Faults
In a fault-tolerant distributed system, different non-faulty processes may arrive atdifferent values for a given system parameter. To resolve this disagreement, processesmust exchange and vote upon their respective local values. Faulty processes ...
Reviews
Greg Speegle
The Byzantine generals problem is one of the most famous problems in computer science. The problem is for processes to reach agreement on some value despite the malicious effects of faulty processes. This paper presents a solution for a variant of this problem in which agreement is defined as all nonfaulty processes being within some previously defined bound. A solution is given for both the synchronous and asynchronous cases. The basic idea of the solution is to discard enough values from a set of messages that the range of responses is within the range generated by the nonfaulty processes. The most interesting aspect of this paper is the solid theoretical basis presented for the algorithms. This theoretical basis allows the authors to generate solutions for both asynchronous and synchronous communications without substantial changes to the algorithm itself. The only weakness of this paper is a lack of examples, which could clarify the theory and the algorithms. Otherwise, it is a strong paper that serves as a good example of solid techniques for solving distributed problems.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments