Michael J. Fischer
Nancy A. Lynch
Michael S. Paterson
Skip Abstract Section
Abstract
The consensus problem involves an asynchronous system of processes, some of which may be unreliable. The problem is for the reliable processes to agree on a binary value. In this paper, it is shown that every protocol for this problem has the possibility of nontermination, even with only one faulty process. By way of contrast, solutions are known for the synchronous case, the “Byzantine Generals” problem.
- 1 ATTIYA,C DOLEV D AND GIL Asynchronous Byzantine consensus. In Proceedings of the 3rd Annual ACM Symposium on Principles of Distributed Computing (Vancouver, B.C., Canada, Aug. 27-29). ACM, New York, 1984, pp. 119-133. Google Scholar
- 2 BEN-OR, M.Another advantage of free choice: Completely asynchronous agreement protocols. In Proceedings of the 2nd Annual ACM Symposium on Principles of Distributed Computing (Montreal, Quebec, Canada, Aug. 17-19). ACM, New York, 1983, pp. 27-30. Google Scholar
- 3 BRACHA, G. An asynchronous t(n - 1)/3J-resilient consensus protocol. In Proceedings of the 3rd Annual ACM Symposium on Principles of Distributed Computing (Vancouver, B.C., Canada, Aug. 27-29). ACM, New York, 1984, pp. 154-162. Google Scholar
- 4 BRACHA, G., AND TOUEG, S.Resilient consensus protocols. In Proceedings of the 2nd Annual ACM Symposium on Principles of Distributed Computing (Montreal, Quebec, Canada, Aug. 17- 19). ACM, New York, 1983, pp. 12-26. Google Scholar
- 5 DEMILLO, R. A., LYNCH, N. A., AND MERRITT, M. J.Cryptographic protocols. In Proceedings of the 14th Annual ACM Symposium on Theory of Computing (San Francisco, Calif., May 5-7). ACM, New York, 1982, pp. 383-400. Google Scholar
- 6 DOLEV, D., AND STRONG, H. R.Distributed commit with bounded waiting. In Proceedings of the 2nd Annual IEEE Symposium on Reliability in Distributed Software and Database Systems. IEEE, New York, 1982, pp. 53-60.Google Scholar
- 7 DOLEV, D., AND STRONG, H. R.Polynomial algorithms for multiple processor agreement. In Proceedings of the 14th Annual ACM Symposium on Theory of Computing (San Francisco, Calif., May 5-7). ACM, New York, 1982, pp. 401-407. Google Scholar
- 8 DOLEV, D., FISCHER, M., FOWLER, R., LYNCH, N., AND STRONG, H. R.An efficient algorithm for Byzantine agreement without authentication. Inf. Control 52, 3 (1983), 257-274.Google Scholar
- 9 DOLEV, D., LYNCH, N., PINTER, S., STARK, E., AND WEIHL, W.Reaching approximate agreement in the presence of faults. In Proceedings of the 3rd Annual IEEE Symposium on Reliability in Distributed Software and Database Systems. IEEE, New York, 1983, pp. 145-154.Google Scholar
- 10 DWORK, C., LYNCH, N., AND STOCKMEYER, L.Consensus in the presence of partial synchrony. In Proceedings of the 3rd Annual ACM Symposium on Principles of Distributed Computing (Vancouver, B.C., Canada, Aug. 27-29). ACM, New York, 1984, pp. 103-118.Google Scholar
- 11 FISCHER, M., AND LYNCH. N.A lower bound for the time to assure interactive consistency. Inf. Proc. Lett. 14, 4 (1982), 183-186.Google Scholar
- 12 FISCHER, M., LYNCH, N., AND PATERSON, M.mpossibility of distributed consensus with one faulty process. In Proceedings of the 2nd Annual ACM SIGA CT-SIGMOD Symposium on Principles of Database Systems (Atlanta, Ga., Mar. 21-23). ACM, New York, 1983, pp. 1-7. Google Scholar
- 13 GARCIA-MOLINA, H.Elections in a distributed computing system. IEEE Trans. Comput. C-31, 1 (1982), 48-59.Google Scholar
- 14 LAMPORT, L., SHOSTAK, R., AND PEASE, M.The Byzantine Generals problem. ACM Trans. Prog. Lang. Syst. 4, 3 (July 1982), 382-40I. Google Scholar
- 15 LAMPSON, B.Replicated Commit. CSL Notebook Entry, Xerox Palo Alto Research Center, Palo Alto, Calif., 1981.Google Scholar
- 16 LAMPSON, B., AND STURGIS, H.Crash recovery in a distributed data storage system. Manuscript, Xerox Palo Alto Research Center, Palo Alto, Calif., 1979.Google Scholar
- 17 LINDSAY, B. G., SELINGER, P. G., GALTIERI, C., GRAY, J. N., LORIE, R. A., PRICE, T. G., PUTZOLU, F., TRAIGER, I. L., AND WADE, B.W. Notes on distributed databases. IBM Res. Rep. RJ2571, IBM Research Division, San Jose, Calif., 1979.Google Scholar
- 18 LYNCH, N., FISCHER, M., AND FOWLER, R. A simple and efficient Byzantine Generals algorithm. In Proceedings of the 2nd Annual IEEE Symposium on Reliability in Distributed Software and Database Systems. IEEE, New York, 1982, pp. 46-52.Google Scholar
- 19 PEASE, M., SHOSTAK, R., AND LAMPORT, L.Reaching agreement in the presence of faults. J. ACM 27, 2 (Apr. 1980), 228-234. Google Scholar
- 20 RABIN, M.Randomized Byzantine Generals. In Proceedings of the 24th Annual IEEE Symposium on Foundations of Computer Science. IEEE, New York, 1983, pp. 403-409.Google Scholar
- 21 REED, D.Naming and synchronization in a decentralized computer system. Ph.D. dissertation, Technical Report MIT/LCS/TR-205, Massachusetts Institute of Technology, Cambridge, Mass., 1978. Google Scholar
- 22 ROSENKRANTZ, D. J., STEARNS, R. E., AND LEWIS, P. M., II.System level concurrency control for distributed database systems. ACM Trans. Database Syst. 3, 2 (June 1978), 178-198. Google Scholar
- 23 SKEEN, D.A decentralized termination protocol. In Proceedings of the 2nd Annual IEEE Symposium on Reliability in Distributed Software and Database Systems. IEEE, New York, 1982, pp. 27-32.Google Scholar
- 24 SKEEN, D., AND STONEBRAKER, M.A formal model of crash recovery in a distributed system. IEEE Trans. Sofiw. Engineering SE-9, 3 (May 1983), 219-228.Google Scholar
- 25 TOUEG, S.Randomized Byzantine Agreements. In Proceedings of the 3rd Annual ACM Symposium on Principles of Distributed Computing (Vancouver, B.C., Canada, Aug. 27-29). ACM, New York, I984, pp. 163-178. Google Scholar
Index Terms
- Impossibility of distributed consensus with one faulty process
Recommendations
Impossibility of distributed consensus with one faulty process
PODS '83: Proceedings of the 2nd ACM SIGACT-SIGMOD symposium on Principles of database systemsThe consensus problem involves an asynchronous system of processes, some of which may be unreliable. The problem is for the reliable processes to agree on a binary value. We show that every protocol for this problem has the possibility of nontermination,...
The gap in circumventing the impossibility of consensus
The impossibility of reaching deterministic consensus in an asynchronous and crash prone system was established for a weak variant of the problem, usually called weak consensus, where a set of processes need to decide on a common value in {0,1}, so that ...
Comments