Fast perfection-information leader-election protocol with linear immunity

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Fast perfection-information leader-election protocol with linear immunity

Full text

Pdf (887 KB)

Source

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

San Diego, California, United States

Pages: 662 - 671

Year of Publication: 1993

ISBN:0-89791-591-7

Authors

Jason Cooper
Nathan Linial

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): 12, Citation Count: 7

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/167088.167258 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	M. Ajtai and N. Linial, The influence of large coalitions, Combinatorica, to appear. Also, IBM Research Report, RJ 7133 (67380) 11/14/89.
	2	N. Alon and M. Naor, Coin-flipping games immune against linear-sized coalitions, SIAM J. Computing, to appear. Also, Proc. 31st IEEE Syrup. on the Foundations of Computer Science (1990) 46 - 54.
	3	N. Alon and J. Spencer The Probabilistic Method Wiley, 1992.
	4	M. Ben-Or and N. Linial, Collective coin flipping, in Randomness and Computation, (S. Micali, ed.) Academic Press, 1989, 91 - 115.
	5	A. Cohen and A. Wigderson, Dispersers, deterministic amplification, and weak random sources, Proc. 30th IEEE Syrup. on the Foundations of Computer Science (1989) 14- 19.
	6	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]
	7	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]
	8	J. Kahn, G. Kalai and N. Linial, The influence of variables on boolean functions, 29th Symposium on the Foundations of Computer Science, White Planes, 1988, 68- 80.
	9	N. Linial, Games Computers Play- Game- Theoretic Aspects of Computer Science, in "Handbook of Game Theory with Economic Applications" (R. J. Aumann and S. Hart eds.) North Holland, to appear 1993. Also available as a Leibniz Center, Computer Science Dept. Hebrew University, Tech. Report 5- 92.
	10	A. Lubotzky, R. Phillips and P. Sarnak, Ramanujan Graphs, Combinatorica 8(1988), 261-277.
	11	I. S. Rombauer and M. Rombauer Becker, Joy of Cooking Hobbs-Merril, 1979, p. 154.
	12	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 7

	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
	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
	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
	Rafail Ostrovsky , Sridhar Rajagopalan , Umesh Vazirani, Simple and efficient leader election in the full information model, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.234-242, May 23-25, 1994, Montreal, Quebec, Canada
	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
	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
	Richard John Anthony, An autonomic election algorithm based on emergence in natural systems, Integrated Computer-Aided Engineering, v.13 n.1, p.3-22, January 2006