ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Impossibility of Distributed Consensus with One Faulty Process.

Michael J. Fischer, Nancy A. Lynch, Mike Paterson: Impossibility of Distributed Consensus with One Faulty Process. PODS 1983: 1-7
@inproceedings{DBLP:conf/pods/FischerLP83,
  author    = {Michael J. Fischer and
               Nancy A. Lynch and
               Mike Paterson},
  title     = {Impossibility of Distributed Consensus with One Faulty Process},
  booktitle = {Proceedings of the Second ACM SIGACT-SIGMOD Symposium on Principles
               of Database Systems, March 21-23, 1983, Colony Square Hotel,
               Atlanta, Georgia},
  publisher = {ACM},
  year      = {1983},
  isbn      = {0-89791-097-4},
  pages     = {1-7},
  ee        = {http://doi.acm.org/10.1145/588058.588060, db/conf/pods/FischerLP83.html},
  crossref  = {DBLP:conf/pods/83},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

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

Copyright © 1983 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ... BibTeX

Printed Edition

Proceedings of the Second ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, March 21-23, 1983, Colony Square Hotel, Atlanta, Georgia. ACM 1983, ISBN 0-89791-097-4
Contents BibTeX

Online Edition: ACM Digital Library

References

[DFFLS]
...
[DLM]
Richard A. DeMillo, Nancy A. Lynch, Michael Merritt: Cryptographic Protocols. STOC 1982: 383-400 BibTeX
[DS1]
...
[DS2]
Danny Dolev, H. Raymond Strong: Polynomial Algorithms for Multiple Processor Agreement. STOC 1982: 401-407 BibTeX
[FL]
Michael J. Fischer, Nancy A. Lynch: A Lower Bound for the Time to Assure Interactive Consistency. Inf. Process. Lett. 14(4): 183-186(1982) BibTeX
[G]
Hector Garcia-Molina: Elections in a Distributed Computing System. IEEE Trans. Computers 31(1): 48-59(1982) BibTeX
[LFF]
...
[La]
...
[Le]
...
[Li]
...
[LS]
...
[LSP]
Leslie Lamport, Robert E. Shostak, Marshall C. Pease: The Byzantine Generals Problem. ACM Trans. Program. Lang. Syst. 4(3): 382-401(1982) BibTeX
[PSL]
Marshall C. Pease, Robert E. Shostak, Leslie Lamport: Reaching Agreement in the Presence of Faults. J. ACM 27(2): 228-234(1980) BibTeX
[R]
...
[RSL]
Daniel J. Rosenkrantz, Richard Edwin Stearns, Philip M. Lewis II: System Level Concurrency Control for Distributed Database Systems. ACM Trans. Database Syst. 3(2): 178-198(1978) BibTeX
[S]
...
[SS]
Dale Skeen, Michael Stonebraker: A Formal Model of Crash Recovery in a Distributed System. Berkeley Workshop 1981: 129-142 BibTeX

Referenced by

  1. Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987, ISBN 0-201-10715-5
    Contents
  2. Philip A. Bernstein, Nathan Goodman: An Algorithm for Concurrency Control and Recovery in Replicated Distributed Databases. ACM Trans. Database Syst. 9(4): 596-615(1984)
  3. Nathan Goodman, Dale Skeen, Arvola Chan, Umeshwar Dayal, Stephen Fox, Daniel R. Ries: A Recovery Algorithm for a Distributed Database System. PODS 1983: 8-15
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:33:41 2009