Lower bounds for distributed coin-flipping and randomized consensus

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Lower bounds for distributed coin-flipping and randomized consensus

Full text

Pdf (1.13 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-ninth annual ACM symposium on Theory of computing table of contents

El Paso, Texas, United States

Pages: 559 - 568

Year of Publication: 1997

ISBN:0-89791-888-6

Author

James Aspnes

Yale University, Department of Computer Science, 51, Prospect Street/P.O. Box 208285, New Haven, CT

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 20, Citation Count: 6

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

	AAT94	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 [doi>10.1145/195058.195464]
	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]
	ADS89	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]
	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]
	AN90	Noga Alon and Moni Naor. Coin-flipping games immune against linear-Led coalitions. In Proceedings o! the 31st Annual Symposium on Foundations of Computer Science, pages 46-54. IEEE, 1990.
	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]
	AW96	James Aspnes , Orli Waarts, Randomized Consensus in Expected O(n log^ 2 n) Operations Per Processor, SIAM Journal on Computing, v.25 n.5, p.1024-1044, Oct. 1996 [doi>10.1137/S0097539792240881]
	BOL85	Michael Ben-Or and Nathan Linial. Collective coin flipping, robust voting schemes and minimization of banzhaf values. In Proceedings of the 26th Annual Symposium on Foundations of Computer Science, pages 408-416. IEEE, 1985.
	BOLS87	M. Ben-Or, N. Linial, and M. Saks. Collectire coin flipping and other models of iraperfect randomness. In Combinatorics, volume 52 of Colloquia Mathematic Societatis Jdnos Bolliai, pages 75-112, Eger (Hunguy), 1987.
	BR90	Gabi Bracha and Ophir Rachman. Approximated counters and randomized consensus. Technical Report 662, Technion, 1990.
	BR91	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
	CFG+85	Benny Chor, Joel Friedman, Oded Goldreich, Johan H/mtad, Steven Rudich, and Roman Smolensky. The bit extraction problem or t-resilient functions. In Proceedings o/the ,~th Annual Symposium on Foundations of Computer Science, pages 396-407. IEEE, 1985.
	Cha96	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]
	CI93	Richard Cleve and Russell Impagliazzo. Martingales with Boolean final value must make jumps of O(1/n1/2) with constant probability. Unpublished manuscript, 1993.
	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]
	CL93	Jason Cooper , Nathan Linial, Fast perfection-information leader-election protocol with linear immunity, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.662-671, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167258]
	DDS87	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]
	DHPW92	Cynthia Dwork , Serge A. Plotkin , Maurice Herlihy , Orli Waarts, Time-lapse snapshots, Symposium proceedings on Theory of computing and systems, p.154-170, June 1992, Haifa, Israel
	FHS93	Faith Fich , Maurice Herlihy , Nir Shavit, On the space complexity of randomized synchronization, Proceedings of the twelfth annual ACM symposium on Principles of distributed computing, p.241-249, August 15-18, 1993, Ithaca, New York, United States [doi>10.1145/164051.164078]
	FLP85	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]
	Fri92	Joel Friedman. On the bit extraction problem. In Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, pages 314-319. IEEE, 1992.
	Har66	L.H. Harper. Optimal numberings and isoperimetric problems on graphs. Journal o/Combinatorial Theory, 1:385-394, 1966.
	Her91	Maurice Herlihy, Wait-free synchronization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.1, p.124-149, Jan. 1991 [doi>10.1145/114005.102808]
	LAA87	Michael C. Loui and Hosame H. Abu- Amara. Memory requirements for agreement among unreliable asynchronous processes. In Franco P. Preparata, editor, Advances in Computing Research, volume 4. JAI Press, 1987.
	LLS89	D. Lichtenstein, N. Linial, and M. Saks. Some extremaJ problems arising from discrete control processes. 6'ombinatorica, 9, 1989.
	Sak89	Michael Saks, A robust noncrytographic protocol for collective coin flipping, SIAM Journal on Discrete Mathematics, v.2 n.2, p.240-244, May 1989 [doi>10.1137/0402020]
	SSW91	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
	Vaz85	U V Vazirani, Towards a strong communication complexity theory or generating quasi-random sequences from two communicating slightly-random sources, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.366-378, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22186]

CITED BY 6

	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
	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
	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
	Faith Fich , Maurice Herlihy , Nir Shavit, On the space complexity of randomized synchronization, Journal of the ACM (JACM), v.45 n.5, p.843-862, Sept. 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
	Prasad Jayanti, A time complexity lower bound for randomized implementations of some shared objects, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.201-210, June 28-July 02, 1998, Puerto Vallarta, Mexico