Impossibility of distributed consensus with one faulty process Export

by: Michael J. Fischer, Nancy A. Lynch, Michael S. Paterson

J. ACM, Vol. 32, No. 2. (April 1985), pp. 374-382.

[Posts]

View FullText article

ACM, DOI, Rent at DeepDyve

elsantosneto's tags for this article

asynchronous channels consensus distributed flp systems

Reviews [Write a review of this article]

Find related articles from these CiteULike users

adit262, laurobeltrao, pedagand, mercutio, kistijantoro, elsantosneto, nigini, ejones, tea4two, pverstra, thiagomanel, ljcamargos, uwmesh (group), ARTI (group), macc (group), HenryR, adriancolesa

Find related articles with these CiteULike tags

1985, agent, algorithms, asynchronous, channels, computing, consensus, dependability, dependable, distconsensus, distributed, distributedsystems, distributed-systems, failure, fault, flp, flp_impossibility, impossibility, impossibility-result, lecture-dac, no-tag, process, systems

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.

@article{citeulike:92799, 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.}, address = {New York, NY, USA}, author = {Fischer, Michael J. and Lynch, Nancy A. and Paterson, Michael S.}, citeulike-article-id = {92799}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=214121}, citeulike-linkout-1 = {http://dx.doi.org/10.1145/3149.214121}, doi = {10.1145/3149.214121}, issn = {0004-5411}, journal = {J. ACM}, keywords = {asynchronous, channels, consensus, distributed, flp, systems}, month = {April}, number = {2}, pages = {374--382}, posted-at = {2007-01-30 19:50:41}, priority = {0}, publisher = {ACM}, title = {Impossibility of distributed consensus with one faulty process}, url = {http://dx.doi.org/10.1145/3149.214121}, volume = {32}, year = {1985} }

RIS record

TY - JOUR ID - citeulike:92799 L3 - citeulike-article-id:92799 N2 - 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. IS - 2 JF - J. ACM SN - 0004-5411 AD - New York, NY, USA EP - 382 TI - Impossibility of distributed consensus with one faulty process PB - ACM VL - 32 SP - 374 KW - asynchronous KW - channels KW - consensus KW - distributed KW - flp KW - systems AU - Fischer, Michael AU - Lynch, Nancy AU - Paterson, Michael PY - 1985/04// UR - http://dx.doi.org/10.1145/3149.214121 ER -

Impossibility of distributed consensus with one faulty process Export

Citation Format