Polylog randomized wait-free consensus

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Polylog randomized wait-free consensus

Full text

Pdf (926 KB)

Source

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

Philadelphia, Pennsylvania, United States

Pages: 166 - 175

Year of Publication: 1996

ISBN:0-89791-800-2

Author

Tushar Deepak Chandra

H2-L10 I. B. M. Thomas J. Watson Research Center, 30 Saw Mill Road, Hawthorne, NY

Sponsors

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

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 25, Citation Count: 19

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/248052.248083 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.

	AB96	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
	Abr88	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]
	ABZ94	Yonatan Aumann, Micheal Bender, and L. H. Zhang. Asynchronous consensus with an oblivious adversary scheduler. Unpublished manuscript, November 1994.
	AGTV92	Yehuda Afek , Eli Gafni , John Tromp , Paul M. B. Vitányi, Wait-free Test-and-Set (Extended Abstract), Proceedings of the 6th International Workshop on Distributed Algorithms, p.85-94, November 02-04, 1992
	AH90	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]
	Asp93	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]
	AW92	James Aspnes and Orli Waarts. Randomized consensus in expected O(n log2 n) operations per processor. In Proceedings of the Thirty-Third Symposium on Foundations of Computer Science, pages 137- 146. IEEE Computer Society Press, October 1992.
	CD92	Tushar D. Chandra and Cynthia Dwork. Personal communication. In this, we give a randomized implementation of test&set from multi reader multi writer register for a strong adversary with O(log n) expected running time., October 1992.
	CHP71	P. J. Courtois , F. Heymans , D. L. Parnas, Concurrent control with “readers” and “writers”, Communications of the ACM, v.14 n.10, p.667-668, Oct. 1971 [doi>10.1145/362759.362813]
	CIL87	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]
	HW90	Maurice P. Herlihy , Jeannette M. Wing, Linearizability: a correctness condition for concurrent objects, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.3, p.463-492, July 1990 [doi>10.1145/78969.78972]
	LA87	M.C. Loui and Abu-Amara. Memory requirements for agreement among unreliable asynchronous processes. Advances in computing research, 4:163-183, 1987.
	Lam86	Leslie Lamport. On interprocess communication, parts i and ii. Distributed Computing, 1:77-101, 1986.

CITED BY 19

	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
	Marcos K. Aguilera, A pleasant stroll through the land of infinitely many creatures, ACM SIGACT News, v.35 n.2, June 2004
	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
	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 , 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
	Yonatan Aumann, Efficient asynchronous consensus with the weak adversary scheduler, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.209-218, August 21-24, 1997, Santa Barbara, California, United States
	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
	James Aspnes, Randomized protocols for asynchronous consensus, Distributed Computing, v.16 n.2-3, p.165-175, 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 , 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
	James Aspnes , Faith Ellen Fich , Eric Ruppert, Relationships between broadcast and shared memory in reliable anonymous distributed systems, Distributed Computing, v.18 n.3, p.209-219, February 2006
	Ling Cheung , Nancy Lynch , Roberto Segala , Frits Vaandrager, Switched PIOA: parallel composition via distributed scheduling, Theoretical Computer Science, v.365 n.1, p.83-108, 10 November 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
	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