Efficient asynchronous consensus with the weak adversary scheduler

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Efficient asynchronous consensus with the weak adversary scheduler

Full text

Pdf (852 KB)

Source

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

Santa Barbara, California, United States

Pages: 209 - 218

Year of Publication: 1997

ISBN:0-89791-952-1

Author

Yonatan Aumann

Department of Mathematics and Computer Science, Barllan University, Ramat-Gan, 92500, Israel

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): 1, Downloads (12 Months): 19, Citation Count: 17

Additional Information:

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/259380.259441 What is a DOI?

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	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 [doi>10.1145/62546.62594]
	2	M. Ajtai, J. Aspnes, C. Dwork, and O. Waarts. A theory of competitive analysis for distributed algorithms. In Proceedings of the ~Sth IEEE Sympo. slum on Foundations of Computer Science, pages 401-411, 1994.
	3	James Aspnes, Time-and space-efficient randomized consensus, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.325-331, August 22-24, 1990, Quebec City, Quebec, Canada [doi>10.1145/93385.93433]
	4	James Aspnes, Time- and space-efficient randomized consensus, Journal of Algorithms, v.14 n.3, p.414-431, May 1993 [doi>10.1006/jagm.1993.1022]
	5	James Aspnes, Lower bounds for distributed coin-flipping and randomized consensus, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.559-568, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258649]
	6	James Aspnes , M. Herlihy, Fast randomized consensus using shared memory, Journal of Algorithms, v.11 n.3, p.441-461, Sep. 1990 [doi>10.1016/0196-6774(90)90021-6]
	7	James Aspnes , William Hurwood, Spreading rumors rapidly despite an adversary, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.143-151, May 23-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/248052.248077]
	8	J. Aspnes and O. Waarts. Randomized consensus in expected O(n log2 n) operations per processor. In Proceedings of the 33rd Annual Symposium on the Foundalions of Computer Science, pages 137- 146, 1992.
	9	James Aspnes , Orli Waarts, Modular competitiveness for distributed algorithms, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.237-246, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237869]
	10	H. Attiya , D. Dolev , N. Shavit, Bounded polynomial randomized consensus, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.281-293, June 1989, Edmonton, Alberta, Canada [doi>10.1145/72981.73001]
	11	Yonatan Aumann , Michael A. Bender, Efficient Asynchronous Consensus with the Value-Oblivious Adversary Scheduler, Proceedings of the 23rd International Colloquium on Automata, Languages and Programming, p.622-633, July 08-12, 1996
	12	Gabriel Bracha , Ophir Rachman, Randomized Consensus in Expected O(n²log n) Operations, Proceedings of the 5th International Workshop on Distributed Algorithms, p.143-150, October 07-09, 1991
	13	Tushar Deepak Chandra, Polylog randomized wait-free consensus, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.166-175, May 23-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/248052.248083]
	14	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 [doi>10.1145/41840.41848]
	15	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]
	16	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]
	17	O. Goldreich , E. Petrank, The best of both worlds: guaranteeing termination in fast randomized Byzantine agreement protocols, Information Processing Letters, v.36 n.1, p.45-49, Oct. 1990 [doi>10.1016/0020-0190(90)90185-Z]
	18	H. Lout, M. Abu-Amara. Memory requirements for agreement among unreliable asynchr(mous processes. Advances in Computing Research, 4:163- 183, 1987.
	19	Michael Saks , Nir Shavit , Heather Woll, Optimal time randomized consensus—making resilient algorithms fast in practice, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.351-362, January 28-30, 1991, San Francisco, California, United States

CITED BY 17

	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
	James Aspnes, Lower bounds for distributed coin-flipping and randomized consensus, Journal of the ACM (JACM), v.45 n.3, p.415-450, May 1998
	Yonatan Aumann , Avivit Kapah-Levy, Cooperative sharing and asynchronous consensus using single-reader single-writer registers, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.61-70, January 17-19, 1999, Baltimore, Maryland, United States
	James Aspnes, Fast deterministic consensus in a noisy environment, Journal of Algorithms, v.45 n.1, p.16-39, October 2002
	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
	James Aspnes, Randomized protocols for asynchronous consensus, Distributed Computing, v.16 n.2-3, p.165-175, September 2003
	Faith Fich , Eric Ruppert, Hundreds of impossibility results for distributed computing, Distributed Computing, v.16 n.2-3, p.121-163, September 2003
	Anna Pogosyants , Roberto Segala , Nancy Lynch, Verification of the randomized consensus algorithm of Aspnes and Herlihy: a case study, Distributed Computing, v.13 n.3, p.155-186, July 2000
	James Aspnes , Orli Waarts, Compositional competitiveness for distributed algorithms, Journal of Algorithms, v.54 n.2, p.127-151, February 2005
	James Aspnes , Gauri Shah , Jatin Shah, Wait-free consensus with infinite arrivals, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	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
	Harry Buhrman , Alessandro Panconesi , Riccardo Silvestri , Paul Vitanyi, On the importance of having an identity or, is consensus really universal?, Distributed Computing, v.18 n.3, p.167-176, February 2006
	Hagit Attiya , Keren Censor, Tight bounds for asynchronous randomized consensus, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 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
	Hagit Attiya , Keren Censor, Lower bounds for randomized consensus under a weak adversary, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada
	Hagit Attiya , Keren Censor, Tight bounds for asynchronous randomized consensus, Journal of the ACM (JACM), v.55 n.5, p.1-26, October 2008
	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