Another advantage of free choice (Extended Abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Another advantage of free choice (Extended Abstract): Completely asynchronous agreement protocols

Full text

Pdf (248 KB)

Source

Annual ACM Symposium on Principles of Distributed Computing archive
Proceedings of the second annual ACM symposium on Principles of distributed computing table of contents

Montreal, Quebec, Canada

Pages: 27 - 30

Year of Publication: 1983

ISBN:0-89791-110-5

Author

Michael Ben-Or

Sponsors

SIGOPS: ACM Special Interest Group on Operating Systems
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 14, Downloads (12 Months): 102, Citation Count: 95

Additional Information:

abstract references cited by index terms 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/800221.806707 What is a DOI?

ABSTRACT

Recently, Fischer, Lynch and Paterson [3] proved that no completely asynchronous consensus protocol can tolerate even a single unannounced process death. We exhibit here a probabilistic solution for this problem, which guarantees that as long as a majority of the processes continues to operate, a decision will be made (Theorem 1). Our solution is completely asynchronous and is rather strong: As in [4], it is guaranteed to work with probability 1 even against an adversary scheduler who knows all about the system.

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	Danny Dolev , H. Raymond Strong, Polynomial algorithms for multiple processor agreement, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.401-407, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802215]
	2	Fischer, M. and Lynch, N. A Lower Bound for the Time to Assure Interactive Consistency. Information Processing Letters 14, 4 (1982), 182-186.
	3	M. J. Fischer , N. A. Lynch , M. S. Paterson, IMPOSSIBILITY OF DISTRIBUTED CONSENSUS WITH ONE FAULTY PROCESS, Massachusetts Institute of Technology, Cambridge, MA, 1982
	4	Lehman, D. and Rabin, M. On the Advantages of Free Choice: A Symmetric and Fully Distributed Solution to the Dining Philosophers Problem. to appear.

CITED BY 95

	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
	Sam Toueg, Randomized Byzantine Agreements, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.163-178, August 27-29, 1984, Vancouver, British Columbia, Canada
	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
	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
	Eyal Kushilevitz , Yishay Mansour , Michael O. Rabin , David Zuckerman, Lower bounds for randomized mutual exclusion, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.154-163, May 16-18, 1993, San Diego, California, United States
	Z. M. Kedem , K. V. Palem , M. O. Rabin , A. Raghunathan, Efficient program transformations for resilient parallel computation via randomization (preliminary version), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.306-317, May 04-06, 1992, Victoria, British Columbia, Canada
	Donald Beaver, Correlated pseudorandomness and the complexity of private computations, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.479-488, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	Benny Chor , Michael Merritt , David B. Shmoys, Simple constant-time consensus protocols in realistic failure models, Journal of the ACM (JACM), v.36 n.3, p.591-614, July 1989
	Gabriel Bracha , Sam Toueg, Resilient consensus protocols, Proceedings of the second annual ACM symposium on Principles of distributed computing, p.12-26, August 17-19, 1983, Montreal, Quebec, Canada
	Brian Coan , Jennifer Lundelius, Transaction commit in a realistic fault model, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.40-51, August 11-13, 1986, Calgary, Alberta, Canada
	Paul Feldman , Silvio Micali, Optimal algorithms for Byzantine agreement, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.148-161, May 02-04, 1988, Chicago, Illinois, United States
	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
	Marcos K. Aguilera, A pleasant stroll through the land of infinitely many creatures, ACM SIGACT News, v.35 n.2, June 2004
	Hagit Attiya , Amotz Bar-Noy , Danny Dolev, Sharing memory robustly in message-passing systems, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.363-375, August 22-24, 1990, Quebec City, Quebec, Canada
	Soma Chaudhuri, Agreement is harder than consensus: set consensus problems in totally asynchronous systems, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.311-324, 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
	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
	G Bracha, An O(lg n) expected rounds randomized Byzantine generals protocol, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.316-326, May 06-08, 1985, Providence, Rhode Island, United States
	Roberto Segala, Verification of randomized distributed algorithms, Lectures on formal methods and performance analysis: first EEF/Euro summer school on trends in computer science, Springer-Verlag New York, Inc., New York, NY, 2002
	Nancy Lynch , Isaac Saias , Roberto Segala, Proving time bounds for randomized distributed algorithms, Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.314-323, August 14-17, 1994, Los Angeles, California, United States
	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
	B. A. Coan , J. L. Welch, Modular construction of nearly optimal Byzantine agreement protocols, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.295-305, June 1989, Edmonton, Alberta, Canada
	Gabriel Bracha, An asynchronous [(n - 1)/3]-resilient consensus protocol, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.154-162, August 27-29, 1984, Vancouver, British Columbia, Canada
	Alan Demers , Dan Greene , Carl Hauser , Wes Irish , John Larson , Scott Shenker , Howard Sturgis , Dan Swinehart , Doug Terry, Epidemic algorithms for replicated database maintenance, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.1-12, August 10-12, 1987, Vancouver, British Columbia, Canada
	Achour Mostefaoui , Michel Raynal, Randomized k-set agreement, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.291-297, July 2001, Crete Island, Greece
	Gabriel Bracha , Sam Toueg, Asynchronous consensus and broadcast protocols, Journal of the ACM (JACM), v.32 n.4, p.824-840, Oct. 1985
	Brian A Coan, A communication-efficient canonical form for fault-tolerant distributed protocols, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.63-72, August 11-13, 1986, Calgary, Alberta, Canada
	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
	Rajiv Gupta , Scott A. Smolka , Shaji Bhaskar, On randomization in sequential and distributed algorithms, ACM Computing Surveys (CSUR), v.26 n.1, p.7-86, March 1994
	George Varghese , Nancy A. Lynch, A tradeoff between safety and liveness for randomized coordinated attack protocols, Proceedings of the eleventh annual ACM symposium on Principles of distributed computing, p.241-250, August 10-12, 1992, Vancouver, British Columbia, Canada
	Roberto Segala , Nancy Lynch, Probabilistic simulations for probabilistic processes, Nordic Journal of Computing, v.2 n.2, p.250-273, Summer 1995
	Andrei Z. Broder, A provably secure polynomial approximation scheme for the distributed lottery problem (extended abstract), Proceedings of the fourth annual ACM symposium on Principles of distributed computing, p.136-148, August 1985, Minaki, Ontario, Canada
	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
	Ziv Bar-Joseph , Michael Ben-Or, A tight lower bound for randomized synchronous consensus, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.193-199, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Christian Cachin , Klaus Kursawe , Victor Shoup, Random oracles in constantipole: practical asynchronous Byzantine agreement using cryptography (extended abstract), Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.123-132, July 16-19, 2000, Portland, Oregon, United States
	Gabriel Bracha, An O(log n) expected rounds randomized byzantine generals protocol, Journal of the ACM (JACM), v.34 n.4, p.910-920, Oct. 1987
	Tushar Deepak Chandra , Vassos Hadzilacos , Sam Toueg , Bernadette Charron-Bost, On the impossibility of group membership, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.322-330, May 23-26, 1996, Philadelphia, Pennsylvania, United States
	Anna Pogosyants , Roberto Segala, Formal verification of timed properties of randomized distributed algorithms, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.174-183, August 20-23, 1995, Ottowa, Ontario, Canada
	Arkady Zamsky, An randomized Byzantine agreement protocol with constant expected time and guaranteed termination in optimal (deterministic) time, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.201-208, May 23-26, 1996, Philadelphia, Pennsylvania, United States
	Hagit Attiya , Amotz Bar-Noy , Danny Dolev, Sharing memory robustly in message-passing systems, Journal of the ACM (JACM), v.42 n.1, p.124-142, Jan. 1995
	Louise E. Moser , P. M. Melliar-Smith , Vivek Agrawala, Total ordering algorithms, Proceedings of the 19th annual conference on Computer Science, p.375-380, April 1991, San Antonio, Texas, United States
	Achour Mostefaoui , Eric Mourgaya , Michel Raynal, An introduction to oracles for asynchronous distributed systems, Future Generation Computer Systems, v.18 n.6, p.757-767, May 2002
	Benny Chor , Michael Merritt , David B. Shmoys, Simple constant-time consensus protocols in realistic failure models (extended abstract), Proceedings of the fourth annual ACM symposium on Principles of distributed computing, p.152-162, August 1985, Minaki, Ontario, Canada
	Josyula R. Rao, Reasoning about probabilistic parallel programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.3, p.798-842, May 1994
	Michael Ben-Or , Avinatan Hassidim, Fast quantum byzantine agreement, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Paulo E. Veríssimo, Travelling through wormholes: a new look at distributed systems models, ACM SIGACT News, v.37 n.1, March 2006
	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
	Roy Friedman , Achour Mostefaoui , Michel Raynal, A weakest failure detector-based asynchronous consensus protocol for f < n, Information Processing Letters, v.90 n.1, p.39-46, 15 April 2004
	James Aspnes, Randomized protocols for asynchronous consensus, Distributed Computing, v.16 n.2-3, p.165-175, September 2003
	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
	Benny Chor , Amos Israeli , Ming Li, On processor coordination using asynchronous hardware, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.86-97, August 10-12, 1987, Vancouver, British Columbia, Canada
	Yehuda Lindell , Anna Lysyanskaya , Tal Rabin, Sequential composition of protocols without simultaneous termination, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California
	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
	Bogdan S. Chlebus , Dariusz R. Kowalski, Gossiping to reach consensus, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada
	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
	Michel Reynal, A short introduction to failure detectors for asynchronous distributed systems, ACM SIGACT News, v.36 n.1, March 2005
	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
	Vasken Bohossian , Chenggong C. Fan , Paul S. LeMahieu , Marc D. Riedel , Jehoshua Bruck , Lihao Xu, Computing in the RAIN: A Reliable Array of Independent Nodes, IEEE Transactions on Parallel and Distributed Systems, v.12 n.2, p.99-114, February 2001
	Rachid Guerraoui , Michel Raynal, The Information Structure of Indulgent Consensus, IEEE Transactions on Computers, v.53 n.4, p.453-466, April 2004
	Hagen Völzer, A constructive proof for FLP, Information Processing Letters, v.92 n.2, p.83-87, 31 October 2004
	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
	Roy Friedman , Achour Mostefaoui , Michel Raynal, Simple and Efficient Oracle-Based Consensus Protocols for Asynchronous Byzantine Systems, IEEE Transactions on Dependable and Secure Computing, v.2 n.1, p.46-56, January 2005
	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
	Hasan M. Sayeed , Marwan Abu-Amara , Hosame Abu-Amara, Optimal asynchronous agreement and leader election algorithm for complete networks with Byzantine faulty links, Distributed Computing, v.9 n.3, p.147-156, December 1995
	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
	Yonatan Aumann , Michael A. Bender, Efficient low-contention asynchronous consensus with the value-oblivious adversary scheduler, Distributed Computing, v.17 n.3, p.191-207, March 2005
	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
	Roberto Baldoni , Jean-Michel Hélary , Sara Tucci Piergiovanni, A methodology to design arbitrary failure detectors for distributed protocols, Journal of Systems Architecture: the EUROMICRO Journal, v.54 n.7, p.619-637, July, 2008
	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
	Michael Ben-Or , Elan Pavlov , Vinod Vaikuntanathan, Byzantine agreement in the full-information model in O(log n) rounds, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Danny Dolev, Century papers at the first quarter-century milestone, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, p.3-4, July 23-26, 2006, Denver, Colorado, USA
	François Bonnet , Paul Ezhilchelvan , Einar Vollset, Quiescent consensus in mobile ad-hoc networks using eventually storage-free broadcasts, Proceedings of the 2006 ACM symposium on Applied computing, April 23-27, 2006, Dijon, France
	Bernadette Charron-Bost , André Schiper, Harmful dogmas in fault tolerant distributed computing, ACM SIGACT News, v.38 n.1, March 2007
	Sayan Mitra , Nancy Lynch, Proving Approximate Implementations for Probabilistic I/O Automata, Electronic Notes in Theoretical Computer Science (ENTCS), v.174 n.8, p.71-93, June, 2007
	Alessandro Tiberi, Probabilistic Configuration Theories, Electronic Notes in Theoretical Computer Science (ENTCS), v.174 n.8, p.95-108, June, 2007
	Michel Raynal , Gadi Taubenfeld, The notion of a timed register and its application to indulgent synchronization, Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, June 09-11, 2007, San Diego, California, USA
	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
	Alan Demers , Dan Greene , Carl Houser , Wes Irish , John Larson , Scott Shenker , Howard Sturgis , Dan Swinehart , Doug Terry, Epidemic algorithms for replicated database maintenance, ACM SIGOPS Operating Systems Review, v.22 n.1, p.8-32, Jan., 1988
	Bruce Kapron , David Kempe , Valerie King , Jared Saia , Vishal Sanwalani, Fast asynchronous byzantine agreement and leader election with full information, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.1038-1047, January 20-22, 2008, San Francisco, California
	Patrick Eugster , Pascal Felber , Fabrice Le Fessant, The "art" of programming gossip-based systems, ACM SIGOPS Operating Systems Review, v.41 n.5, October 2007
	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
	Ittai Abraham , Danny Dolev , Joseph Y. Halpern, An almost-surely terminating polynomial protocol forasynchronous byzantine agreement with optimal resilience, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada
	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
	Michael Ben-Or , Danny Dolev , Ezra N. Hoch, Fast self-stabilizing byzantine tolerant digital clock synchronization, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada
	Mohssen Abboud , Carole Delporte-Gallet , Hugues Fauconnier, Agreement and consistency without knowing the number of processes, Proceedings of the 8th international conference on New technologies in distributed systems, June 23-27, 2008, Lyon, France
	Jonathan Katz , Chiu-Yuen Koo, On expected constant-round protocols for Byzantine agreement, Journal of Computer and System Sciences, v.75 n.2, p.91-112, February, 2009
	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
	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
	Jialin Zhang , Wei Chen, Bounded cost algorithms for multivalued consensus using binary consensus instances, Information Processing Letters, v.109 n.17, p.1005-1009, August, 2009
	Bogdan S. Chlebus , Dariusz R. Kowalski , Michal Strojnowski, Fast scalable deterministic consensus for crash failures, Proceedings of the 28th ACM symposium on Principles of distributed computing, August 10-12, 2009, Calgary, AB, Canada
	Bogdan S. Chlebus , Dariusz R. Kowalski, Locally scalable randomized consensus for synchronous crash failures, Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures, August 11-13, 2009, Calgary, AB, Canada
	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