Consensus in the presence of partial synchrony

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Consensus in the presence of partial synchrony

Full text

Pdf (3.19 MB)

Source

Journal of the ACM (JACM) archive
Volume 35 , Issue 2 (April 1988) table of contents

Pages: 288 - 323

Year of Publication: 1988

ISSN:0004-5411

Authors

Cynthia Dwork	IBM Almaden Research Center, San Jose, CA; and Massachusetts Institute of Technology, Cambridge
Nancy Lynch	Massachusetts Institute of Technology, Cambridge
Larry Stockmeyer	IBM Almaden Research Center, San Jose, CA; and Massachusetts Institute of Technology, Cambridge

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 43, Downloads (12 Months): 237, Citation Count: 125

Additional Information:

abstract references cited by index terms review collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/42282.42283 What is a DOI?

Warning: The download time has expired please click on the item to try again.

ABSTRACT

The concept of partial synchrony in a distributed system is introduced. Partial synchrony lies between the cases of a synchronous system and an asynchronous system. In a synchronous system, there is a known fixed upper bound &Dgr; on the time required for a message to be sent from one processor to another and a known fixed upper bound &PHgr; on the relative speeds of different processors. In an asynchronous system no fixed upper bounds &Dgr; and &PHgr; exist. In one version of partial synchrony, fixed bounds &Dgr; and &PHgr; exist, but they are not known a priori. The problem is to design protocols that work correctly in the partially synchronous system regardless of the actual values of the bounds &Dgr; and &PHgr;. In another version of partial synchrony, the bounds are known, but are only guaranteed to hold starting at some unknown time T, and protocols must be designed to work correctly regardless of when time T occurs. Fault-tolerant consensus protocols are given for various cases of partial synchrony and various fault models. Lower bounds that show in most cases that our protocols are optimal with respect to the number of faults tolerated are also given. Our consensus protocols for partially synchronous processors use new protocols for fault-tolerant “distributed clocks” that allow partially synchronous processors to reach some approximately common notion of time.

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	Chagit Attiya , Danny Dolev , Joseph Gil, Asynchronous Byzantine consensus, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.119-133, August 27-29, 1984, Vancouver, British Columbia, Canada [doi>10.1145/800222.806740]
	2	Gabriel Bracha , Sam Toueg, Asynchronous consensus and broadcast protocols, Journal of the ACM (JACM), v.32 n.4, p.824-840, Oct. 1985 [doi>10.1145/4221.214134]
	3	DOLEV, D., AND STRONG, H. R. Authenticated algorithms for Byzantine agreement. SIAM J. Comput. 12 (1983), 656-666.
	4	Danny Dolev , Cynthia Dwork , Larry Stockmeyer, On the minimal synchronism needed for distributed consensus, Journal of the ACM (JACM), v.34 n.1, p.77-97, Jan. 1987 [doi>10.1145/7531.7533]
	5	DOLEV, D., FISCHER, i. J., FOWLER, R., LYNCH, N. A., AND STRONG, H.R. Efficient Byzantine agreement without authentication. Inf. Control 52 (1982), 257-274.
	6	Danny Dolev , Nancy A. Lynch , Shlomit S. Pinter , Eugene W. Stark , William E. Weihl, Reaching approximate agreement in the presence of faults, Journal of the ACM (JACM), v.33 n.3, p.499-516, July 1986 [doi>10.1145/5925.5931]
	7	C Dwork , Y Moses, Knowledge and common knowledge in a Byzantine environment I: crash failures, Proceedings of the 1986 Conference on Theoretical aspects of reasoning about knowledge, p.149-169, March 1986, Monterey, California, United States
	8	FISCHER, M.J. The consensus problem in unreliable distributed systems (a brief survey). Rep. YALEU/DSC/RR-273. Dept. of Computer Science, Yale Univ., New Haven, Conn., June 1983.
	9	FISCHER, M. J., AND LAMPORT, L. Byzantine generals and transaction commit protocols. Tech. Rep. Op. 62, SRI International, Menlo Park, Calif., 1982.
	10	Michael J. Fischer , Nancy A. Lynch , Michael S. Paterson, Impossibility of distributed consensus with one faulty process, Journal of the ACM (JACM), v.32 n.2, p.374-382, April 1985 [doi>10.1145/3149.214121]
	11	Hector Garcia-Molina , Frank Pittelli , Susan Davidson, Is byzantine agreement useful in a distributed database?, Proceedings of the 3rd ACM SIGACT-SIGMOD symposium on Principles of database systems, April 02-04, 1984, Waterloo, Ontario, Canada [doi>10.1145/588011.588022]
	12	Jim Gray, Notes on Data Base Operating Systems, Operating Systems, An Advanced Course, p.393-481, January 1978
	13	Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
	14	L. Lamport, The Weak Byzantine Generals Problem, Journal of the ACM (JACM), v.30 n.3, p.668-676, July 1983 [doi>10.1145/2402.322398]
	15	Leslie Lamport , Robert Shostak , Marshall Pease, The Byzantine Generals Problem, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.3, p.382-401, July 1982 [doi>10.1145/357172.357176]
	16	Shlomit Sarah Pinter, Distributed computation systems: modelling, verification, and algorithms, 1984
	17	Rüdiger Reischuk, A new solution for the byzantine generals problem, Information and Control, v.64 n.1-3, p.23-42, Jan./Feb./March 1985 [doi>10.1016/S0019-9958(85)80042-5]
	18	Fred B. Schneider, Byzantine generals in action: implementing fail-stop processors, ACM Transactions on Computer Systems (TOCS), v.2 n.2, p.145-154, May 1984 [doi>10.1145/190.357399]
	19	Dale Skeen, A Quorum-Based Commit Protocol, Cornell University, Ithaca, NY, 1982
	20	SRIKANTH, T. K., AND TOUEG, S. Simulating authenticated broadcasts to derive simple faulttolerant algorithms. Rep. 84-623, Computer Science Dept., Cornell Univ., Ithaca, N.Y., 1984.

CITED BY 125

	P. D. V. Van Der Stok , A. H. T. Janssen-Raemaekers, Real-Time Atomic Multicast Algorithms Implemented on a Shared Memory Multiprocessor, Real-Time Systems, v.24 n.1, p.55-91, January 2003
	Felix C. Gärtner, Fundamentals of fault-tolerant distributed computing in asynchronous environments, ACM Computing Surveys (CSUR), v.31 n.1, p.1-26, March 1999
	Michel Raynal , Mukesh Singhal, Mastering Agreement Problems in Distributed Systems, IEEE Software, v.18 n.4, p.40-47, July 2001
	Gil Neiger , Sam Toueg, Automatically increasing the fault-tolerance of distributed systems, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.248-262, August 15-17, 1988, Toronto, Ontario, Canada
	Hagit Attiya , Cynthia Dwork , Nancy Lynch , Larry Stockmeyer, Bounds on the time to reach agreement in the presence of timing uncertainty, Journal of the ACM (JACM), v.41 n.1, p.122-152, Jan. 1994
	Maurice Herlihy, A methodology for implementing highly concurrent data objects, ACM Transactions on Programming Languages and Systems (TOPLAS), v.15 n.5, p.745-770, Nov. 1993
	N. Lynch, A hundred impossibility proofs for distributed computing, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.1-28, June 1989, Edmonton, Alberta, Canada
	Jean-François Hermant , Gérard Le Lann, Fast Asynchronous Uniform Consensus in Real-Time Distributed Systems, IEEE Transactions on Computers, v.51 n.8, p.931-944, August 2002
	Tushar Deepak Chandra , Sam Toueg, Unreliable failure detectors for reliable distributed systems, Journal of the ACM (JACM), v.43 n.2, p.225-267, March 1996
	R. L. Graham , A. C. Yao, On the improbability of reaching Byzantine agreements, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.467-478, May 14-17, 1989, Seattle, Washington, United States
	Tushar Deepak Chandra , Sam Toueg, Unreliable failure detectors for asynchronous systems (preliminary version), Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.325-340, August 19-21, 1991, Montreal, Quebec, Canada
	Ajei S. Gopal , Kenneth J. Perry, Unifying self-stabilization and fault-tolerance, Proceedings of the twelfth annual ACM symposium on Principles of distributed computing, p.195-206, August 15-18, 1993, Ithaca, New York, United States
	Tushar Deepak Chandra , Vassos Hadzilacos , Sam Toueg, The weakest failure detector for solving consensus, Journal of the ACM (JACM), v.43 n.4, p.685-722, July 1996
	Gregory Chockler , Dahlia Malkhi, Active disk paxos with infinitely many processes, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California
	Aleta M. Ricciardi , Kenneth P. Birman, Using process groups to implement failure detection in asynchronous environments, Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.341-353, August 19-21, 1991, Montreal, Quebec, Canada
	Yehuda Afek , Gideon Stupp, Delimiting the power of bounded size synchronization objects (extended abstract), Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.42-51, August 14-17, 1994, Los Angeles, California, United States
	Paulo E. Veríssimo, Travelling through wormholes: a new look at distributed systems models, ACM SIGACT News, v.37 n.1, March 2006
	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
	Christof Fetzer , Flaviu Cristian, Fail-awareness in timed asynchronous systems, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.314-321, May 23-26, 1996, Philadelphia, Pennsylvania, United States
	Gregory V. Chockler , Idid Keidar , Roman Vitenberg, Group communication specifications: a comprehensive study, ACM Computing Surveys (CSUR), v.33 n.4, p.427-469, December 2001
	M. Herlihy, A methodology for implementing highly concurrent data structures, ACM SIGPLAN Notices, v.25 n.3, p.197-206, Mar. 1990
	Leslie Lamport, The part-time parliament, ACM Transactions on Computer Systems (TOCS), v.16 n.2, p.133-169, May 1998
	James Aspnes, Fast deterministic consensus in a noisy environment, Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.299-308, July 16-19, 2000, Portland, Oregon, United States
	Louise E. Moser , P. M. Melliar-Smith , Vivek Agrawala, Necessary and sufficient conditions for broadcast consensus protocols, Distributed Computing, v.7 n.2, p.75-85, December 1993
	M. Herlihy , Mark R. Tuttle, Lower bounds for wait-free computation in message-passing systems, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.347-362, August 22-24, 1990, Quebec City, Quebec, Canada
	Michael Barborak , Anton Dahbura , Minoslaw Malek, The consensus problem in fault-tolerant computing, ACM Computing Surveys (CSUR), v.25 n.2, p.171-220, June 1993
	Stephen Ponzio, Consensus in the presence of timing uncertainty: omission and Byzantine failures (extended abstract), Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.125-138, August 19-21, 1991, Montreal, Quebec, Canada
	Rachid Guerraoui, Indulgent algorithms (preliminary version), Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.289-297, July 16-19, 2000, Portland, Oregon, 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
	Tushar Deepak Chandra , Vassos Hadzilacos , Sam Toueg, The weakest failure detector for solving consensus, Proceedings of the eleventh annual ACM symposium on Principles of distributed computing, p.147-158, August 10-12, 1992, Vancouver, British Columbia, Canada
	Achour Mostefaoui , Sergio Rajsbaum , Michel Raynal, The combined power of conditions and failure detectors to solve asynchronous set agreement, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA
	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
	Rajeev Alur , Thomas A. Henzinger, Finitary fairness, ACM Transactions on Programming Languages and Systems (TOPLAS), v.20 n.6, p.1171-1194, Nov. 1998
	Karl Abrahamson, On achieving consensus using a shared memory, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.291-302, August 15-17, 1988, Toronto, Ontario, Canada
	Dimitris Michailidis, Fast set agreement in the presence of timing uncertainty, Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, p.249-256, May 04-06, 1999, Atlanta, Georgia, United States
	Romain Boichat , Partha Dutta , Svend Frølund , Rachid Guerraoui, Deconstructing paxos, ACM SIGACT News, v.34 n.1, March 2003
	Paul Attie, Wait-free Byzantine consensus, Information Processing Letters, v.83 n.4, p.221-227, 31 August 2002
	James Aspnes, Fast deterministic consensus in a noisy environment, Journal of Algorithms, v.45 n.1, p.16-39, October 2002
	Idit Keidar , Sergio Rajsbaum, On the cost of fault-tolerant consensus when there are no faults: preliminary version, ACM SIGACT News, v.32 n.2, June 2001
	Marcos K. Aguilera , Carole Delporte-Gallet , Hugues Fauconnier , Sam Toueg, On implementing omega with weak reliability and synchrony assumptions, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.306-314, July 13-16, 2003, Boston, Massachusetts
	Roberto de Prisco , Dahlia Malkhi , Michael Reiter, On k-Set Consensus Problems in Asynchronous Systems, IEEE Transactions on Parallel and Distributed Systems, v.12 n.1, p.7-21, January 2001
	Achour Mostefaoui , Sergio Rajsbaum , Michel Raynal, Conditions on input vectors for consensus solvability in asynchronous distributed systems, Journal of the ACM (JACM), v.50 n.6, p.922-954, November 2003
	Flaviu Cristian , Christof Fetzer, The Timed Asynchronous Distributed System Model, IEEE Transactions on Parallel and Distributed Systems, v.10 n.6, p.642-657, June 1999
	Dariusz R. Kowalski , Alex A. Shvartsman, Performing work with asynchronous processors: message-delay-sensitive bounds, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.265-274, July 13-16, 2003, Boston, Massachusetts
	Faith Fich , Eric Ruppert, Hundreds of impossibility results for distributed computing, Distributed Computing, v.16 n.2-3, p.121-163, September 2003
	Bernadette Charron-Bost , André Schiper, Uniform consensus is harder than consensus, Journal of Algorithms, v.51 n.1, p.15-37, 1 April 2004
	Michael J. Fischer , Michael Merritt, Appraising two decades of distributed computing theory research, Distributed Computing, v.16 n.2-3, p.239-247, September 2003
	James Aspnes, Randomized protocols for asynchronous consensus, Distributed Computing, v.16 n.2-3, p.165-175, September 2003
	On the Implementation of Unreliable Failure Detectors in Partially Synchronous Systems, IEEE Transactions on Computers, v.53 n.7, p.815-828, July 2004
	Marcos K. Aguilera , Carole Delporte-Gallet , Hugues Fauconnier , Sam Toueg, Communication-efficient leader election and consensus with limited link synchrony, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada
	Achour Mostefaoui , Sergio Rajsbaum , Michel Raynal , Matthieu Roy, A hierarchy of conditions for consensus solvability, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.151-160, August 2001, Newport, Rhode Island, United States
	Paulo Veríssimo , António Casimiro, The Timely Computing Base Model and Architecture, IEEE Transactions on Computers, v.51 n.8, p.916-930, August 2002
	Cynthia Dwork , Maurice Herlihy , Orli Waarts, Contention in shared memory algorithms, Journal of the ACM (JACM), v.44 n.6, p.779-805, Nov. 1997
	Cynthia Dwork , Maurice Herlihy , Orli Waarts, Contention in shared memory algorithms, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.174-183, May 16-18, 1993, San Diego, California, United States
	Maurice Herlihy, Randomized wait-free concurrent objects (extended abstract), Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.11-21, August 19-21, 1991, Montreal, Quebec, Canada
	Hagit Attiya , Amotz Bar-Noy , Danny Dolev , David Peleg , Rüdiger Reischuk, Renaming in an asynchronous environment, Journal of the ACM (JACM), v.37 n.3, p.524-548, July 1990
	Partha Dutta , Rachid Guerraoui, The inherent price of indulgence, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California
	P. Ramanathan , Dilip D. Kandlur , Kang G. Shin, Hardware-Assisted Software Clock Synchronization for Homogeneous Distributed Systems, IEEE Transactions on Computers, v.39 n.4, p.514-524, April 1990
	Rachid Guerraoui , Michel Raynal, The Information Structure of Indulgent Consensus, IEEE Transactions on Computers, v.53 n.4, p.453-466, April 2004
	Ittai Abraham , Gregory V. Chockler , Idit Keidar , Dahlia Malkhi, Byzantine disk paxos: optimal resilience with byzantine shared memory, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada
	Marcos Kawazoe Aguilera , Wei Chen , Sam Toueg, Failure detection and consensus in the crash-recovery model, Distributed Computing, v.13 n.2, p.99-125, April 2000
	André Schiper, Early consensus in an asynchronous system with a weak failure detector, Distributed Computing, v.10 n.3, p.149-157, April 1997
	Xavier Défago , André Schiper , Péter Urbán, Total order broadcast and multicast algorithms: Taxonomy and survey, ACM Computing Surveys (CSUR), v.36 n.4, p.372-421, December 2004
	E. Anceaume , A. Fernández , A. Mostefaoui , G. Neiger , M. Raynal, A necessary and sufficient condition for transforming limited accuracy failure detectors, Journal of Computer and System Sciences, v.68 n.1, p.123-133, February 2004
	Deborah Shands , Chung-Kuo Chang, Characterizing distributed systems using knowledge-based models: preliminary version, Proceedings of the 4th conference on Theoretical aspects of reasoning about knowledge, p.29-42, March 22-25, 1992, Monterey, California
	Alex Brodsky , Faith Ellen Fich, Efficient synchronous snapshots, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada
	M. Hurfin , A. Mostéfaoui , M. Raynal, A Versatile Family of Consensus Protocols Based on Chandra-Toueg's Unreliable Failure Detectors, IEEE Transactions on Computers, v.51 n.4, p.395-408, April 2002
	Massimo Franceschetti , Jehoshua Bruck, A Group Membership Algorithm with a Practical Specification, IEEE Transactions on Parallel and Distributed Systems, v.12 n.11, p.1190-1200, November 2001
	Achour Mostéfaoui , Sergio Rajsbaum , Michel Raynal , Matthieu Roy, Condition-based consensus solvability: a hierarchy of conditions and efficient protocols, Distributed Computing, v.17 n.1, p.1-20, February 2004
	Gregory Chockler , Murat Demirbas , Seth Gilbert , Calvin Newport , Tina Nolte, Consensus and collision detectors in wireless Ad Hoc networks, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA
	Idit Keidar , Jeremy Sussman , Keith Marzullo , Danny Dolev, Moshe: A group membership service for WANs, ACM Transactions on Computer Systems (TOCS), v.20 n.3, p.191-238, August 2002
	Mikel Larrea , Antonio Fernández , Sergio Arévalo, Eventually consistent failure detectors, Journal of Parallel and Distributed Computing, v.65 n.3, p.361-373, March 2005
	Michael Backes , Dennis Hofheinz , Jörn Müller-Quade , Dominique Unruh, On fairness in simulatability-based cryptographic systems, Proceedings of the 2005 ACM workshop on Formal methods in security engineering, November 11-11, 2005, Fairfax, VA, USA
	Michel Hurfin , Michel Raynal, A simple and fast asynchronous consensus protocol based on a weak failure detector, Distributed Computing, v.12 n.4, p.209-223, September 1999
	Dariusz R. Kowalski , Alex A. Shvartsman, Performing work with asynchronous processors: message-delay-sensitive bounds, Information and Computation, v.203 n.2, p.181-210, December 15, 2005
	Idit Keidar , Alexander Shraer, Timeliness, failure-detectors, and consensus performance, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA
	Felix C. Freiling , Hagen Völzer, Illustrating the impossibility of crash-tolerant consensus in asynchronous systems, ACM SIGOPS Operating Systems Review, v.40 n.2, p.105-109, April 2006
	Gregory Chockler , Dahlia Malkhi, Active disk Paxos with infinitely many processes, Distributed Computing, v.18 n.1, p.73-84, July 2005
	Partha Dutta , Rachid Guerraoui, The inherent price of indulgence, Distributed Computing, v.18 n.1, p.85-98, July 2005
	Guojing Cong , David A. Bader, Designing irregular parallel algorithms with mutual exclusion and lock-free protocols, Journal of Parallel and Distributed Computing, v.66 n.6, p.854-866, June 2006
	Miguel Correia , Nuno Ferreira Neves , Lau Cheuk Lung , Paulo Veríssimo, Low complexity Byzantine-resilient consensus, Distributed Computing, v.17 n.3, p.237-249, March 2005
	Rachid Guerraoui , Marko VukoliĆ, Refined quorum systems, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA
	Weigang Wu , Jiannong Cao , Jin Yang , Michel Raynal, Using asynchrony and zero degradation to speed up indulgent consensus protocols, Journal of Parallel and Distributed Computing, v.68 n.7, p.984-996, July, 2008
	Alysson Neves Bessani , Joni da Silva Fraga , Lau Cheuk Lung, BTS: a Byzantine fault-tolerant tuple space, Proceedings of the 2006 ACM symposium on Applied computing, April 23-27, 2006, Dijon, France
	Miguel Correia , Nuno Ferreira Neves , Lau Cheuk Lung , Paulo Veríssimo, Worm-IT - A wormhole-based intrusion-tolerant group communication system, Journal of Systems and Software, v.80 n.2, p.178-197, February, 2007
	Gregory Chockler , Dahlia Malkhi, Light-weight leases for storage-centric coordination, International Journal of Parallel Programming, v.34 n.2, p.143-170, April 2006
	Hana Chockler , Eitan Farchi , Ziv Glazberg , Benny Godlin , Yarden Nir-Buchbinder , Ishai Rabinovitz, Formal verification of concurrent software: two case studies, Proceeding of the 2006 workshop on Parallel and distributed systems: testing and debugging, July 17-17, 2006, Portland, Maine, USA
	Jim Gray , Leslie Lamport, Consensus on transaction commit, ACM Transactions on Database Systems (TODS), v.31 n.1, p.133-160, March 2006
	Jin Yang , Jiannong Cao , Weigang Wu , Corentin Travers, The notification based approach to implementing failure detectors in distributed systems, Proceedings of the 1st international conference on Scalable information systems, p.14-es, May 30-June 01, 2006, Hong Kong
	Taisuke Izumi , Akinori Saitoh , Toshimitsu Masuzawa, Adaptive timeliness of consensus in presence of crash and timing faults, Journal of Parallel and Distributed Computing, v.67 n.6, p.648-658, June, 2007
	Bernadette Charron-Bost , André Schiper, Harmful dogmas in fault tolerant distributed computing, ACM SIGACT News, v.38 n.1, March 2007
	Xianbing Wang , Yong Meng Teo , Jiannong Cao, Message and time efficient consensus protocols for synchronous distributed systems, Journal of Parallel and Distributed Computing, v.68 n.5, p.641-654, May, 2008
	Ramakrishna Kotla , Lorenzo Alvisi , Mike Dahlin , Allen Clement , Edmund Wong, Zyzzyva: speculative byzantine fault tolerance, ACM SIGOPS Operating Systems Review, v.41 n.6, December 2007
	Özalp Babaoğlu , Renzo Davoli , Alberto Montresor, Group membership and view synchrony in partitionable asynchronous distributed systems: specifications, ACM SIGOPS Operating Systems Review, v.31 n.2, p.11-22, April 1997
	Achour Mostefaoui , Sergio Rajsbaum , Michel Raynal, Conditions on input vectors for consensus solvability in asynchronous distributed systems, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.153-162, July 2001, Hersonissos, Greece
	Achour Mostefaoui , Michel Raynal , Corentin Travers, Time-Free and Timer-Based Assumptions Can Be Combined to Obtain Eventual Leadership, IEEE Transactions on Parallel and Distributed Systems, v.17 n.7, p.656-666, July 2006
	Carlo Marchetti , Roberto Baldoni , Sara Tucci-Piergiovanni , Antonino Virgillito, Fully Distributed Three-Tier Active Software Replication, IEEE Transactions on Parallel and Distributed Systems, v.17 n.7, p.633-645, July 2006
	Nuno F. Neves , Miguel Correia , Paulo Verissimo, Solving Vector Consensus with a Wormhole, IEEE Transactions on Parallel and Distributed Systems, v.16 n.12, p.1120-1131, December 2005
	Achour Mostefaoui , Gilles Trédan, Towards the minimal synchrony for byzantine consensus, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA
	Roy Friedman , Anne-Marie Kermarrec , Michel Raynal, Modularity: a first class concept to address distributed systems, ACM SIGACT News, v.39 n.2, June 2008
	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
	Alysson Neves Bessani , Eduardo Pelison Alchieri , Miguel Correia , Joni Silva Fraga, DepSpace: a byzantine fault-tolerant coordination service, ACM SIGOPS Operating Systems Review, v.42 n.4, May 2008
	Neeraj Mittal , Felix C. Freiling , S. Venkatesan , Lucia Draque Penso, On termination detection in crash-prone distributed systems with failure detectors, Journal of Parallel and Distributed Computing, v.68 n.6, p.855-875, June, 2008
	Chryssis Georgiou , Seth Gilbert , Rachid Guerraoui , Dariusz R. Kowalski, On the complexity of asynchronous gossip, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada
	Ramakrishna Kotla , Allen Clement , Edmund Wong , Lorenzo Alvisi , Mike Dahlin, Zyzzyva: speculative Byzantine fault tolerance, Communications of the ACM, v.51 n.11, November 2008
	Fernando Castor Filho , Augusta Marques , Raphael Y. de Camargo , Fabio Kon, A group membership service for large-scale grids, Proceedings of the 6th international workshop on Middleware for grid computing, p.1-6, December 01-05, 2008, Leuven, Belgium
	Marcos K. Aguilera , Sam Toueg, Timeliness-based wait-freedom: a gracefully degrading progress condition, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada
	Roy Friedman , Achour Mostefaoui , Michel Raynal, On the Respective Power of ◊P and ◊S to Solve One-Shot Agreement Problems, IEEE Transactions on Parallel and Distributed Systems, v.18 n.5, p.589-597, May 2007
	Roy Friedman , Achour Mostefaoui , Sergio Rajsbaum , Michel Raynal, Asynchronous Agreement and Its Relation with Error-Correcting Codes, IEEE Transactions on Computers, v.56 n.7, p.865-875, July 2007
	Prasad Jayanti , Sam Toueg, Every problem has a weakest failure detector, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada
	Sergio Gorender , Raimundo Jose de Araujo Macedo , Michel Raynal, An Adaptive Programming Model for Fault-Tolerant Distributed Computing, IEEE Transactions on Dependable and Secure Computing, v.4 n.1, p.18-31, January 2007
	Miguel Correia , Alysson Neves Bessani , Paulo Veríssimo, Research note: On Byzantine generals with alternative plans, Journal of Parallel and Distributed Computing, v.68 n.9, p.1291-1296, September, 2008
	R. Guerraoui , N. Lynch, A general characterization of indulgence, ACM Transactions on Autonomous and Adaptive Systems (TAAS), v.3 n.4, p.1-19, November 2008
	Martin Biely , Josef Widder, Optimal message-driven implementations of omega with mute processes, ACM Transactions on Autonomous and Adaptive Systems (TAAS), v.4 n.1, p.1-22, January 2009
	Rachid Guerraoui , Maurice Herlihy , Bastian Pochon, A topological treatment of early-deciding set-agreement, Theoretical Computer Science, v.410 n.6-7, p.570-580, February, 2009
	Cristian Martín , Mikel Larrea , Ernesto Jiménez, Implementing the Omega failure detector in the crash-recovery failure model, Journal of Computer and System Sciences, v.75 n.3, p.178-189, May, 2009
	Samia Souissi , Xavier Défago , Masafumi Yamashita, Using eventually consistent compasses to gather memory-less mobile robots with limited visibility, ACM Transactions on Autonomous and Adaptive Systems (TAAS), v.4 n.1, p.1-27, January 2009
	Atul Singh , Pedro Fonseca , Petr Kuznetsov , Rodrigo Rodrigues , Petros Maniatis, Defining weakly consistent Byzantine fault-tolerant services, Proceedings of the 2nd Workshop on Large-Scale Distributed Systems and Middleware, September 15-17, 2008, Yorktown Heights, New York
	Benjamin Wester , James Cowling , Edmund B. Nightingale , Peter M. Chen , Jason Flinn , Barbara Liskov, Tolerating latency in replicated state machines through client speculation, Proceedings of the 6th USENIX symposium on Networked systems design and implementation, p.245-260, April 22-24, 2009, Boston, Massachusetts
	Andre Schiper , Sam Toueg, From Set Membership to Group Membership: A Separation of Concerns, IEEE Transactions on Dependable and Secure Computing, v.3 n.1, p.2, January 2006
	Erez Petrank , Madanlal Musuvathi , Bjarne Steesngaard, Progress guarantee for parallel programs via bounded lock-freedom, ACM SIGPLAN Notices, v.44 n.6, June 2009
	Naohiro Hayashibara , Makoto Takizawa, Design of the notification system for failure detectors, International Journal of High Performance Computing and Networking, v.6 n.1, p.25-34, June 2009
	Jawwad Shamsi , Monica Brockmeyer , Chunbo Chu, PSON: predictable service overlay networks, The Fourth International Conference on Heterogeneous Networking for Quality, Reliability, Security and Robustness & Workshops, August 14-17, 2007, Vancouver, Canada
	Marcos K. Aguilera , Carole Delporte-Gallet , Hugues Fauconnier , Sam Toueg, Partial synchrony based on set timeliness, Proceedings of the 28th ACM symposium on Principles of distributed computing, August 10-12, 2009, Calgary, AB, Canada
	Srikanth Sastry , Scott M. Pike , Jennifer L. Welch, The weakest failure detector for wait-free dining under eventual weak exclusion, Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures, August 11-13, 2009, Calgary, AB, Canada

INDEX TERMS

Primary Classification:
C. Computer Systems Organization
C.2 COMPUTER-COMMUNICATION NETWORKS

Additional Classification:
C. Computer Systems Organization
C.4 PERFORMANCE OF SYSTEMS
Subjects: Reliability, availability, and serviceability

D. Software
D.4 OPERATING SYSTEMS
D.4.7 Organization and Design
Subjects: Distributed systems

General Terms:
Algorithms, Reliability, Theory

REVIEW

"Jason Gait : Reviewer"

A distributed set of processors reaches consensus on a value when the correctly performing processors decide on the same value. This outcome is subject to the conditions that if those correct processors begin with the same value, then they must more...

Collaborative Colleagues:

Cynthia Dwork: colleagues

Nancy Lynch: colleagues

Larry Stockmeyer: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player