Simple and efficient leader election in the full information model

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Simple and efficient leader election in the full information model

Full text

Pdf (740 KB)

Source

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

Montreal, Quebec, Canada

Pages: 234 - 242

Year of Publication: 1994

ISBN:0-89791-663-8

Authors

Rafail Ostrovsky	Computer Science Division, University of California at Berkeley, and International Computer Science Institute, Berkeley, CA
Sridhar Rajagopalan	Computer Science Division, University of California at Berkeley, CA
Umesh Vazirani	Computer Science Division, University of California at Berkeley, CA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 22, Citation Count: 6

Additional Information:

references cited by index terms collaborative colleagues peer to peer

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

	AL-89	M. AJTAI, N. LINIAL The influence of large coalitions. IBM Research Report 7133 (67380), Nov. 1989.
	AN-90	Noga Alon , Moni Naor, Coin-flipping games immune against linear-sized coalitions, SIAM Journal on Computing, v.22 n.2, p.403-417, April 1993 [doi>10.1137/0222030]
	AR-89	N. ALON, M. RABIN Biased coins and randomized algorithms. Advances in Computing Research, JAI Press (Silvio Micali, ed.) 5:499-507,1989.
	BGW-88	Michael Ben-Or , Shafi Goldwasser , Avi Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computation, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.1-10, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62213]
	BL-85	M. BEN-OR, N. LINIAL Collective coin flipping, robust voting schemes and minima of Banzhaf values. FO CS- 85 pp. 408-416.
	BL-89	M. BEN-OR, IN. LINIAL Collective coin flipping. Advances in Computing Research, JAI Press (Silvio Micali, ed.) 5:91-116,1989.
	BLS-87	M. BEN-OR, N. LINIAL, M. SAKS Collective coin flipping and other models of imperfect randomness. Colloq. Math. Soc. Jan6s Bolyai No., 52 Combinatorics Eger pp. 75-112, 1987. North-Holland Publ.
	BN1-93	Ravi B. Boppana , Babu O. Narayanan, The biased coin problem, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.252-257, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167164]
	BN2-93	R. BOPPANA, B. NARAYANAN. Collective Coin Flipping and Leader Election with Optimal Immunity., manuscript.
	B-85	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 [doi>10.1145/22145.22180]
	CCD-88	David Chaum , Claude Crépeau , Ivan Damgard, Multiparty unconditionally secure protocols, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.11-19, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62214]
	CD-89	B. CHOR, C. DWORK Randomization in Byzantine agreement. Advances in Computing Research, JA I Press (Silvio Micali, ed.) Vol. 5, 1989.
	CL-93	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]
	FM-88	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 [doi>10.1145/62212.62225]
	GG-79	O. GABBER, Z. GALIL Explicit construction of linear sized superconcentrators. FOCS-20 pp. 364,370. Also see the journal version, JCSS22 (1981), pp. 407-420.
	G-93	D. GILLMAN A Chernoff bound for random walks on expanders. FOCS- 93.
	GGL-91	Oded Goldreich , Shafi Goldwasser , Nathan Linial, Fault-tolerant computation in the full information model (extended abstract), Proceedings of the 32nd annual symposium on Foundations of computer science, p.447-457, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185405]
	IZ-89	R. IMPAGLIAZZO, D. ZUCKERMAN How to recycle random bits. FOCS 89 pp. 248-253.
	KKL-88	J. KAHN, G. KALAI, N. LINIAL The influence of variables on boolean functions. FOCS 88, pp. 68-80.
	K-94	N. KAHALE. Private Communication, February 1994.
	GMW-87	O. Goldreich , S. Micali , A. Wigderson, How to play ANY mental game, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.218-229, January 1987, New York, New York, United States [doi>10.1145/28395.28420]
	L-92	N. LINIAL Games Computers Play: Game-Theoretic AsDect# of Computing C.S. Tech. Report 92-5, The Hebrew University of Jerusalem, February 1992.
	S-89	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]

CITED BY 6

	Spyridon Antonakopoulos, Fast leader-election protocols with bounded cheaters' edge, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Valerie King , Jared Saia , Vishal Sanwalani , Erik Vee, Scalable leader election, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.990-999, January 22-26, 2006, Miami, Florida
	Nabil Kahale, Large Deviation Bounds for Markov Chains, Combinatorics, Probability and Computing, v.6 n.4, p.465-474, December 1997
	Saurabh Sanghvi , Salil Vadhan, The round complexity of two-party random selection, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	David Zuckerman, Randomness-optimal sampling, extractors, and constructive leader election, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.286-295, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	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