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.
Impossibility of Distributed Consensus with One Faulty Process [link]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