| Reaching Agreement in the Presence of Faults |
| Full text |
 Pdf
(521 KB)
|
| Source
|
Journal of the ACM (JACM)
archive
Volume 27 , Issue 2 (April 1980)
table of contents
Pages: 228 - 234
Year of Publication: 1980
ISSN:0004-5411
|
|
Authors
|
|
M. Pease
|
Computer Science Laboratory, SRI International, 333 Ravenswood Avenue, Menlo Park, CA
|
|
R. Shostak
|
Computer Science Laboratory, SRI International, 333 Ravenswood Avenue, Menlo Park, CA
|
|
L. Lamport
|
Computer Science Laboratory, SRI International, 333 Ravenswood Avenue, Menlo Park, CA
|
|
| Publisher |
|
| Bibliometrics |
Downloads (6 Weeks): 22, Downloads (12 Months): 190, Citation Count: 253
|
|
|
 ABSTRACT
The problem addressed here concerns a set of isolated processors, some unknown subset of which may be faulty, that communicate only by means of two-party messages. Each nonfaulty processor has a private value of information that must be communicated to each other nonfaulty processor. Nonfaulty processors always communicate honestly, whereas faulty processors may lie. The problem is to devise an algorithm in which processors communicate their own values and relay values received from others that allows each nonfaulty processor to infer a value for each other processor. The value inferred for a nonfaulty processor must be that processor's private value, and the value inferred for a faulty one must be consistent with the corresponding value inferred by each other nonfaulty processor.
It is shown that the problem is solvable for, and only for, n ≥ 3m + 1, where m is the number of faulty processors and n is the total number. It is also shown that if faulty processors can refuse to pass on information but cannot falsely relay information, the problem is solvable for arbitrary n ≥ m ≥ 0. This weaker assumption can be approximated in practice using cryptographic methods.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
DAvIEs, D, AND WAKEH~Y, J. Synchronization and matching m redundant systems IEEE Trans on Comptrs. C-27, 6 (June 1978), 531-539.
|
| |
2
|
DIFFIE, W, AND BELLMAN, M. New dtrections in cryptography. IEEE Trans Inform. Theory IT-22, 6 (Nov 1976), 644-654
|
 |
3
|
|
| |
4
|
WENSLEY, J H., ET ^L. SIFT: destgn and analysis of a fault-tolerant computer for aircraft control Proc. IEEE 66, 10 (Oct. 1978), 1240-1255.
|
CITED BY 253
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Joseph Y. Halpern , Yoram Moses , Orli Waalrts, A characterization of eventual Byzantine agreement, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.333-346, August 22-24, 1990, Quebec City, Quebec, Canada
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Baruch Awerbuch , Boaz Patt-Shamir , David Peleg , Mark Tuttle, Collaboration of untrusting peers with changing interests, Proceedings of the 5th ACM conference on Electronic commerce, May 17-20, 2004, New York, NY, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Dalia Malki , Ken Birman , Aleta Ricciardi , André Schiper, Uniform actions in asynchronous distributed systems, Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.274-283, August 14-17, 1994, Los Angeles, California, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Michael Ben-Or , Shafi Goldwasser , Avi Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computation, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.1-10, May 02-04, 1988, Chicago, Illinois, United States
|
|
|
|
|
|
|
|
|
C. Mohan , R. Strong , S. Finkelstein, Method for distributed transaction commit and recovery using Byzantine Agreement within clusters of processors, Proceedings of the second annual ACM symposium on Principles of distributed computing, p.89-103, August 17-19, 1983, Montreal, Quebec, Canada
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Joseph Y. Halpern , Ronald Fagin, A formal model of knowledge, action, and communication in distributed systems: preliminary report, Proceedings of the fourth annual ACM symposium on Principles of distributed computing, p.224-236, August 1985, Minaki, Ontario, Canada
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Richard A. DeMillo , Nancy A. Lynch , Michael J. Merritt, Cryptographic protocols, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.383-400, May 05-07, 1982, San Francisco, California, United States
|
|
|
|
|
|
|
|
|
|
|
|
M. J. Fischer , S. Moran , R. Rudich , G. Taubenfeld, The wakeup problem, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.106-116, May 13-17, 1990, Baltimore, Maryland, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Amotz Bar-Noy , Danny Dolev , Cynthia Dwork , H. Raymond Strong, Shifting gears: changing algorithms on the fly to expedite Byzantine agreement, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.42-51, August 10-12, 1987, Vancouver, British Columbia, Canada
|
|
|
C Dwork , D Peleg , N Pippenger , E Upfal, Fault tolerance in networks of bounded degree, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.370-379, May 28-30, 1986, Berkeley, California, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Roberto De Prisco , Dahlia Malkhi , Michael K. Reiter, On k-set consensus problems in asynchronous systems, Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, p.257-265, May 04-06, 1999, Atlanta, Georgia, United States
|
|
|
Rajeev Alur , Hagit Attiya , Gadi Taubenfeld, Time-adaptive algorithms for synchronization, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.800-809, May 23-25, 1994, Montreal, Quebec, Canada
|
|
|
|
|
|
Matthias Fitzi , Daniel Gottesman , Martin Hirt , Thomas Holenstein , Adam Smith, Detectable byzantine agreement secure against faulty majorities, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
U. Feige , D. Peleg , P. Raghavan , E. Upfal, Computing with unreliable information, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.128-137, May 13-17, 1990, Baltimore, Maryland, United States
|
|
|
|
|
|
|
|
|
|
|
|
Michael Ben-Or , Boaz Kelmer , Tal Rabin, Asynchronous secure computations with optimal resilience (extended abstract), Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.183-192, August 14-17, 1994, Los Angeles, California, United States
|
|
|
|
|
|
|
|
|
Hagit Attiya , Cynthia Dwork , Nancy Lynch , Larry Stockmeyer, Bounds on the time to reach agreement in the presence of timing uncertainty, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.359-369, May 05-08, 1991, New Orleans, Louisiana, United States
|
|
|
|
|
|
|
|
|
Nathan Goodman , Dale Skeen , Arvola Chan , Umeshwar Dayal , Stephen Fox , Daniel Ries, A recovery algorithm for a distributed database system, Proceedings of the 2nd ACM SIGACT-SIGMOD symposium on Principles of database systems, March 21-23, 1983, Atlanta, Georgia
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
S. Amitanand , I. Sanketh , K. Srinathant , V. Vinod , C. Pandu Rangan, Distributed consensus in the presence of sectional faults, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.202-210, July 13-16, 2003, Boston, Massachusetts
|
|
|
Atul Adya , William J. Bolosky , Miguel Castro , Gerald Cermak , Ronnie Chaiken , John R. Douceur , Jon Howell , Jacob R. Lorch , Marvin Theimer , Roger P. Wattenhofer, Farsite: federated, available, and reliable storage for an incompletely trusted environment, ACM SIGOPS Operating Systems Review, v.36 n.SI, Winter 2002
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Ran Canetti , Shai Halevi , Amir Herzberg, Maintaining authenticated communication in the presence of break-ins, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.15-24, August 21-24, 1997, Santa Barbara, California, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
D. Powell , J. Arlat , L. Beus-Dukic , A. Bondavalli , P. Coppola , A. Fantechi , E. Jenn , C. Rabéjac , A. Wellings, GUARDS: A Generic Upgradable Architecture for Real-Time Dependable Systems, IEEE Transactions on Parallel and Distributed Systems, v.10 n.6, p.580-599, June 1999
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Lakshminarayanan Subramanian , Randy H. Katz , Volker Roth , Scott Shenker , Ion Stoica, Reliable broadcast in unknown fixed-identity networks, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Atul Adya , William J. Bolosky , Miguel Castro , Gerald Cermak , Ronnie Chaiken , John R. Douceur , Jon Howell , Jacob R. Lorch , Marvin Theimer , Roger P. Wattenhofer, Farsite: federated, available, and reliable storage for an incompletely trusted environment, Proceedings of the 5th symposium on Operating systems design and implementation Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading, December 09-11, 2002, Boston, Massachusetts
|
|
|
|
|
|
|
|
|
|
|
|
Chiu-Yuen Koo , Vartika Bhandari , Jonathan Katz , Nitin H. Vaidya, Reliable broadcast in radio networks: the bounded collision case, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Christian Cachin , Klaus Kursawe , Anna Lysyanskaya , Reto Strobl, Asynchronous verifiable secret sharing and proactive cryptosystems, Proceedings of the 9th ACM conference on Computer and communications security, November 18-22, 2002, Washington, DC, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Senthilkumar G. Cheetancheri , John Mark Agosta , Denver H. Dash , Karl N. Levitt , Jeff Rowe , Eve M. Schooler, A distributed host-based worm detection system, Proceedings of the 2006 SIGCOMM workshop on Large-scale attack defense, p.107-113, September 11-15, 2006, Pisa, Italy
|
|
|
Dov S. Gordon , Hazay Carmit , Jonathan Katz , Yehuda Lindell, Complete fairness in secure two-party computation, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Martin Biely , Josef Widder , Bernadette Charron-Bost , Antoine Gaillard , Martin Hutle , André Schiper, Tolerating corrupted communication, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Hui-Ching Hsieh , Jenq-Shiou Leu , Yen-Chiu Chen , Wei-Kuan Shih, Improving fault-tolerant scheme for a time-sensitive autonomous local wireless sensor network, Proceedings of the International Conference on Mobile Technology, Applications, and Systems, September 10-12, 2008, Yilan, Taiwan
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Prasant Gopal Anumanchipalli , Anuj Gupta , Pranav K. Vasishta , Piyush Bansal , Kannan Srinathan, Brief announcement: global consistency can be easier than point-to-point communication, Proceedings of the 28th ACM symposium on Principles of distributed computing, August 10-12, 2009, Calgary, AB, Canada
|
|
|
|
|
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
C.1