Impossibility of Distributed Consensus with One Faulty Process. Fischer, M. J., Lynch, N. A., & Paterson, M. S. J. ACM, 32(2):374–382, Association for Computing Machinery, New York, NY, USA, apr, 1985.
Paper doi abstract bibtex 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{fischer85_impos_distr_consen_one_fault_proces,
author = {Fischer, Michael J. and Lynch, Nancy A. and Paterson, Michael
S.},
title = {Impossibility of Distributed Consensus with One Faulty
Process},
year = 1985,
issue_date = {April 1985},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = 32,
number = 2,
issn = {0004-5411},
url = {https://doi.org/10.1145/3149.214121},
doi = {10.1145/3149.214121},
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.},
journal = {J. ACM},
month = {apr},
pages = {374–382},
numpages = 9
}
Downloads: 0
{"_id":"u9GTsYrZLtgBMHYDS","bibbaseid":"fischer-lynch-paterson-impossibilityofdistributedconsensuswithonefaultyprocess-1985","downloads":0,"creationDate":"2018-07-03T04:50:27.002Z","title":"Impossibility of Distributed Consensus with One Faulty Process","author_short":["Fischer, M. J.","Lynch, N. A.","Paterson, M. S."],"year":1985,"bibtype":"article","biburl":"https://git.sr.ht/~p0mf/bibliography/blob/main/bibliography.bib","bibdata":{"bibtype":"article","type":"article","author":[{"propositions":[],"lastnames":["Fischer"],"firstnames":["Michael","J."],"suffixes":[]},{"propositions":[],"lastnames":["Lynch"],"firstnames":["Nancy","A."],"suffixes":[]},{"propositions":[],"lastnames":["Paterson"],"firstnames":["Michael","S."],"suffixes":[]}],"title":"Impossibility of Distributed Consensus with One Faulty Process","year":"1985","issue_date":"April 1985","publisher":"Association for Computing Machinery","address":"New York, NY, USA","volume":"32","number":"2","issn":"0004-5411","url":"https://doi.org/10.1145/3149.214121","doi":"10.1145/3149.214121","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.","journal":"J. ACM","month":"apr","pages":"374–382","numpages":"9","bibtex":"@article{fischer85_impos_distr_consen_one_fault_proces,\n author =\t {Fischer, Michael J. and Lynch, Nancy A. and Paterson, Michael\n S.},\n title =\t {Impossibility of Distributed Consensus with One Faulty\n Process},\n year =\t 1985,\n issue_date =\t {April 1985},\n publisher =\t {Association for Computing Machinery},\n address =\t {New York, NY, USA},\n volume =\t 32,\n number =\t 2,\n issn =\t {0004-5411},\n url =\t\t {https://doi.org/10.1145/3149.214121},\n doi =\t\t {10.1145/3149.214121},\n abstract =\t {The consensus problem involves an asynchronous system of\n processes, some of which may be unreliable. The problem is\n for the reliable processes to agree on a binary value. In\n this paper, it is shown that every protocol for this problem\n has the possibility of nontermination, even with only one\n faulty process. By way of contrast, solutions are known for\n the synchronous case, the “Byzantine Generals” problem.},\n journal =\t {J. ACM},\n month =\t {apr},\n pages =\t {374–382},\n numpages =\t 9\n}\n\n","author_short":["Fischer, M. J.","Lynch, N. A.","Paterson, M. S."],"key":"fischer85_impos_distr_consen_one_fault_proces","id":"fischer85_impos_distr_consen_one_fault_proces","bibbaseid":"fischer-lynch-paterson-impossibilityofdistributedconsensuswithonefaultyprocess-1985","role":"author","urls":{"Paper":"https://doi.org/10.1145/3149.214121"},"metadata":{"authorlinks":{}},"html":""},"search_terms":["impossibility","distributed","consensus","one","faulty","process","fischer","lynch","paterson"],"keywords":[],"authorIDs":[],"dataSources":["FWsPTwsmjtrBtRS3B","mt9b5ir7GnHzHywGs"]}