article

Free access

Impossibility of distributed consensus with one faulty process

Authors:

Michael J. Fischer,

Nancy A. Lynch,

Michael S. PatersonAuthors Info & Claims

Journal of the ACM (JACM), Volume 32, Issue 2

Pages 374 - 382

https://doi.org/10.1145/3149.214121

Published: 01 April 1985 Publication History

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.

References

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[11]

FISCHER, M., AND LYNCH. N.A lower bound for the time to assure interactive consistency. Inf. Proc. Lett. 14, 4 (1982), 183-186.

[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.

[13]

GARCIA-MOLINA, H.Elections in a distributed computing system. IEEE Trans. Comput. C-31, 1 (1982), 48-59.

[14]

LAMPORT, L., SHOSTAK, R., AND PEASE, M.The Byzantine Generals problem. ACM Trans. Prog. Lang. Syst. 4, 3 (July 1982), 382-40I.

[15]

LAMPSON, B.Replicated Commit. CSL Notebook Entry, Xerox Palo Alto Research Center, Palo Alto, Calif., 1981.

[16]

LAMPSON, B., AND STURGIS, H.Crash recovery in a distributed data storage system. Manuscript, Xerox Palo Alto Research Center, Palo Alto, Calif., 1979.

[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.

[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.

[19]

PEASE, M., SHOSTAK, R., AND LAMPORT, L.Reaching agreement in the presence of faults. J. ACM 27, 2 (Apr. 1980), 228-234.

[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.

[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.

[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.

[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.

[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.

[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.

Cited By

Delporte-Gallet CFauconnier HFraigniaud PRabie M(2025)Distributed computing in the asynchronous LOCAL modelTheoretical Computer Science10.1016/j.tcs.2024.1149521025(114952)Online publication date: Feb-2025
https://doi.org/10.1016/j.tcs.2024.114952
Hao RDing CDai XFan HXiang J(2025)High-performance BFT consensus for Metaverse through block linking and shortcut loopComputer Communications10.1016/j.comcom.2024.107990229(107990)Online publication date: Jan-2025
https://doi.org/10.1016/j.comcom.2024.107990
Liu XTheriault SWu JYue Y(2024)Algebraic topology and distributed computingFoundations of Data Science10.3934/fods.2024008(0-0)Online publication date: 2024
https://doi.org/10.3934/fods.2024008
Show More Cited By

Index Terms

Impossibility of distributed consensus with one faulty process

Recommendations

IMPOSSIBILITY OF DISTRIBUTED CONSENSUS WITH ONE FAULTY PROCESS
Impossibility of distributed consensus with one faulty process
PODS '83: Proceedings of the 2nd ACM SIGACT-SIGMOD symposium on Principles of database systems

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. 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

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 32, Issue 2

April 1985

254 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/3149

Issue’s Table of Contents

Copyright © 1985 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 April 1985

Published in JACM Volume 32, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3,283
Total Citations
View Citations
17,320
Total Downloads

Downloads (Last 12 months)1,981
Downloads (Last 6 weeks)425

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Delporte-Gallet CFauconnier HFraigniaud PRabie M(2025)Distributed computing in the asynchronous LOCAL modelTheoretical Computer Science10.1016/j.tcs.2024.1149521025(114952)Online publication date: Feb-2025
https://doi.org/10.1016/j.tcs.2024.114952
Hao RDing CDai XFan HXiang J(2025)High-performance BFT consensus for Metaverse through block linking and shortcut loopComputer Communications10.1016/j.comcom.2024.107990229(107990)Online publication date: Jan-2025
https://doi.org/10.1016/j.comcom.2024.107990
Liu XTheriault SWu JYue Y(2024)Algebraic topology and distributed computingFoundations of Data Science10.3934/fods.2024008(0-0)Online publication date: 2024
https://doi.org/10.3934/fods.2024008
Dong HLiu S(2024)Asynchronous Consensus Quorum Read: Pioneering Read Optimization for Asynchronous Consensus ProtocolsElectronics10.3390/electronics1303048113:3(481)Online publication date: 23-Jan-2024
https://doi.org/10.3390/electronics13030481
Song AZhou C(2024)FlexBFT: A Flexible and Effective Optimistic Asynchronous BFT ProtocolApplied Sciences10.3390/app1404146114:4(1461)Online publication date: 10-Feb-2024
https://doi.org/10.3390/app14041461
Nagda HSinghal SAmiri MLoo B(2024)Rashnu: Data-Dependent Order-FairnessProceedings of the VLDB Endowment10.14778/3665844.366586117:9(2335-2348)Online publication date: 1-May-2024
https://dl.acm.org/doi/10.14778/3665844.3665861
Zarnstorff JLebow LSiems CRemuck DRuiz CTseng L(2024)Racos: Improving Erasure Coding State Machine Replication using Leaderless ConsensusProceedings of the 2024 ACM Symposium on Cloud Computing10.1145/3698038.3698511(600-617)Online publication date: 20-Nov-2024
https://dl.acm.org/doi/10.1145/3698038.3698511
Murat ABurgelin CXygkis AZablotchi IAguilera MGuerraoui RWitchel EArpaci-Dusseau ARossbach CKeeton K(2024)SWARM: Replicating Shared Disaggregated-Memory Data in No TimeProceedings of the ACM SIGOPS 30th Symposium on Operating Systems Principles10.1145/3694715.3695945(24-45)Online publication date: 4-Nov-2024
https://dl.acm.org/doi/10.1145/3694715.3695945
Giridharan NSuri-Payer FAbraham IAlvisi LCrooks NWitchel EArpaci-Dusseau ARossbach CKeeton K(2024)Autobahn: Seamless high speed BFTProceedings of the ACM SIGOPS 30th Symposium on Operating Systems Principles10.1145/3694715.3695942(1-23)Online publication date: 4-Nov-2024
https://dl.acm.org/doi/10.1145/3694715.3695942
Nowak TSchmid UWinkler K(2024)Topological Characterization of Consensus in Distributed SystemsJournal of the ACM10.1145/368730271:6(1-48)Online publication date: 22-Aug-2024
https://dl.acm.org/doi/10.1145/3687302
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents