Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms

Full text

Pdf (1.32 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the eighteenth annual ACM symposium on Theory of computing table of contents

Berkeley, California, United States

Pages: 206 - 219

Year of Publication: 1986

ISBN:0-89791-193-8

Authors

R Cole	New York University and Tel Aviv University
U Vishkin	New York University and Tel Aviv University

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 64, Citation Count: 36

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

	AHU-74	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	AS-83	B. Awerbuch and Y. Shiloach, "New connectivity and MSF algorithms for Ultracomputer and PRAM", Proc. 1983 International Conf. on Parallel Processing (1983), 175-179.
	Br-74	Richard P. Brent, The Parallel Evaluation of General Arithmetic Expressions, Journal of the ACM (JACM), v.21 n.2, p.201-206, April 1974 [doi>10.1145/321812.321815]
	CLC-81	F.Y. Chin, J. Lain and I. Chen, "Optimal parallel algorithms for the connected component problems," Proc. 1981 International Conf. on Parallel Processing (1981), 170-175.
	CLC-82	Francis Y. Chin , John Lam , I-Ngo Chen, Efficient parallel algorithms for some graph problems, Communications of the ACM, v.25 n.9, p.659-665, Sept 1982 [doi>10.1145/358628.358650]
	C-86	R. Cole, "An optimal parallel selection algorithm", in preparation.
	CS-85	R. Cole and A. Siegel, "On information flow and sorting: new upper and lower bounds for VLSI circuits", 26th Annual Syrup. on Foundations off computer Science, 208-221.
	CV-86	R. Cole and U. Vishkin, "Efficient parallel graph algorithms", in preparation.
	CY-85	R. Cole and C. Yap, "A parallel median algorithm", IPL 20, 137-139.
	FMRW-85	F E Fich , F Meyer auf der Heide , P Ragde , A Wigderson, One, two, three . . . infinity: lower bounds for parallel computation, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.48-58, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22151]
	FL-80	Richard E. Ladner , Michael J. Fischer, Parallel Prefix Computation, Journal of the ACM (JACM), v.27 n.4, p.831-838, Oct. 1980 [doi>10.1145/322217.322232]
	GLR-83	Allan Gottlieb , Boris D. Lubachevsky , Larry Rudolph, Basic Techniques for the Efficient Coordination of Very Large Numbers of Cooperating Sequential Processors, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.2, p.164-189, April 1983 [doi>10.1145/69624.357206]
	HCS-79	D. S. Hirschberg , A. K. Chandra , D. V. Sarwate, Computing connected components on parallel computers, Communications of the ACM, v.22 n.8, p.461-464, Aug. 1979 [doi>10.1145/359138.359141]
	HMS-83	P. Hochschild, E. Mayr and A. Siegel, "Techniques for solving graph algorithms in parallel environments", Proc 24th Annual Syrup. on Foundations of Computer Science, 351-359.
	IM-85	A. Israeli and S. Moran. private communication.
	KRS-85	C.P. Kruskal, L. Rudolph and M. Snir, "Efficient parallel algorithms for graph problems". Proc. 1985 International Conf. on Parallel Processing, 180-185.
	MW-85	F. Meyer auf der Heide and A. Wigderson. "The complexity of parallel sorting", Proc. 26th IEEE Annual Conf. on Foundations of Computer Science (1985), 532-540.
	SV-82	Y. Shiloach and U. Vishkin, " An O(logn) parallel connectivity algorithm, J. Algorithms 3.1, 57-67.
	TV-85	R.E. Tarjan and U. Vishkin, "An efficient parallel biconnectivity algorithm", SIAM J. of Comput., 14,4(1985), 862- 874.
	Va-75	L. Valiant, "Parallelism in comparison problems", SIAM J. Comput. 4(3), 348-355.
	Vi-83a	U. Vishkin, "Synchronous parallel computation - a survey", TR 71, Dept. of Computer science, Courant Institute, NYU. 1983.
	Vi-83b	U. Vishkin, "An optimal parallel algorithm for selection", manuscript, 1983.
	Vi-84a	U. Vishkin, "An optimal parallel connectivity algorithm", Discrete Applied Math. 9 (I984), 197-207.
	Vi-84b	Uzi Vishkin, Randomized speed-ups in parallel computation, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.230-239, December 1984 [doi>10.1145/800057.808686]
	Vi-85	U. Vishkin, "On efficient parallel strong orientation", lnfor- ,nation Processing Letters 20 (1985), 235-240.
	W-79	James C. Wyllie, The Complexity of Parallel Computations, Cornell University, Ithaca, NY, 1979

CITED BY 36

	Marco Zagha , Guy E. Blelloch, Radix sort for vector multiprocessors, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.712-721, November 18-22, 1991, Albuquerque, New Mexico, United States
	Márió Szegedy , Sundar Vishwanathan, Locality based graph coloring, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.201-207, May 16-18, 1993, San Diego, California, United States
	R. Lin , S. Olariu, Optimal parallel coloring algorithms for a family of tree-representable graphs, Proceedings of the 19th annual conference on Computer Science, p.29-38, April 1991, San Antonio, Texas, United States
	Alain Mayer , Yoram Ofek , Rafail Ostrovsky , Moti Yung, Self-stabilizing symmetry breaking in constant-space (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.667-678, May 04-06, 1992, Victoria, British Columbia, Canada
	William L. Hightower , Jan F. Prins , John H. Reif, Implementations of randomized sorting on large parallel machines, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.158-167, June 29-July 01, 1992, San Diego, California, United States
	Amotz Bar-Noy , Joseph Naor , Moni Naor, One bit algorithms, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.66-76, August 15-17, 1988, Toronto, Ontario, Canada
	Michael T. Goodrich, Constructing arrangements optimally in parallel (preliminary version), Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.169-179, July 21-24, 1991, Hilton Head, South Carolina, United States
	Dascal Vishkin , Uzi Vishkin, Experiments with list ranking for explicit multi-threaded (XMT) instruction parallelism, Journal of Experimental Algorithmics (JEA), 5, p.10-es, 2000
	Alessandro Panconesi , Aravind Srinivasan, Improved distributed algorithms for coloring and network decomposition problems, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.581-592, May 04-06, 1992, Victoria, British Columbia, Canada
	Nathan Linial , Michael Saks, Decomposing graphs into regions of small diameter, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.320-330, January 28-30, 1991, San Francisco, California, United States
	Torben Hagerup , H. Jung , E. Welzl, Efficient parallel computation of arrangements of hyperplanes in d dimensions, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.290-297, July 02-06, 1990, Island of Crete, Greece
	F. Fich , V. Ramachandran, Lower bounds for parallel computation on linked structures, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.109-116, July 02-06, 1990, Island of Crete, Greece
	Gianluca De Marco , Andrzej Pelc, Fast distributed graph coloring with O(&Dgr;) colors, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.630-635, January 07-09, 2001, Washington, D.C., United States
	Graham Cormode , S. Muthukrishnan, The string edit distance matching problem with moves, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.667-676, January 06-08, 2002, San Francisco, California
	Ramesh Subramonian, Designing synchronous algorithms for asynchronous processors, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.189-198, June 29-July 01, 1992, San Diego, California, United States
	Jop F. Sibeyn, Better trade-offs for parallel list ranking, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.221-230, June 23-25, 1997, Newport, Rhode Island, United States
	N. Dadoun , D. G. Kirkpatrick, Parallel processing for efficient subdivision search, Proceedings of the third annual symposium on Computational geometry, p.205-214, June 08-10, 1987, Waterloo, Ontario, Canada
	A. Goldberg , S. Plotkin , G. Shannon, Parallel symmetry-breaking in sparse graphs, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.315-324, January 1987, New York, New York, United States
	Sühleyman Cenk Sahinalp , Uzi Vishkin, Symmetry breaking for suffix tree construction, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.300-309, May 23-25, 1994, Montreal, Quebec, Canada
	U. Vishkin, Deterministic sampling—a new technique for fast pattern matching, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.170-180, May 13-17, 1990, Baltimore, Maryland, United States
	Margaret Reid-Miller, List ranking and list scan on the Cray C-90, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.104-113, June 27-29, 1994, Cape May, New Jersey, United States
	S. Muthukrishnan , Süleyman Cenk Sahinalp, Approximate nearest neighbors and sequence comparison with block operations, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.416-424, May 21-23, 2000, Portland, Oregon, United States
	Yehuda Afek , Gad M. Landau , Baruch Schieber , Moti Yung, The power of multimedia: combining point-to point and multi-access networks, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.90-104, August 15-17, 1988, Toronto, Ontario, Canada
	Alain Mayer , Rafail Ostrovsky , Moti Yung, Self-stabilizing algorithms for synchronous unidirectional rings, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.564-573, January 28-30, 1996, Atlanta, Georgia, United States
	Jop F. Sibeyn, List-ranking on interconnection networks, Information and Computation, v.181 n.2, p.75-87, March 15, 2003
	Guy E. Blelloch , Charles E. Leiserson , Bruce M. Maggs , C. Greg Plaxton , Stephen J. Smith , Marco Zagha, A comparison of sorting algorithms for the connection machine CM-2, Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.3-16, July 21-24, 1991, Hilton Head, South Carolina, United States
	Y. Han, An optimal linked list prefix algorithms on a local memory computer, Proceedings of the 17th conference on ACM Annual Computer Science Conference, p.278-286, February 21-23, 1989, Louisville, Kentucky
	Yijie Han, An Optimal Linked List Prefix Algorithm on a Local Memory Computer, IEEE Transactions on Computers, v.40 n.10, p.1149-1153, October 1991
	E. L. G. Saukas , S. W. Song, Efficient selection algorithms on distributed memory computers, Proceedings of the 1998 ACM/IEEE conference on Supercomputing (CDROM), p.1-26, November 07-13, 1998, San Jose, CA
	K. W. Ryu , J. JáJ', Efficient Algorithms for List Ranking and for Solving Graph Problems on the Hypercube, IEEE Transactions on Parallel and Distributed Systems, v.1 n.1, p.83-90, January 1990
	Graham Cormode , S. Muthukrishnan, Substring compression problems, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Tuğkan Batu , Funda Ergun , Cenk Sahinalp, Oblivious string embeddings and edit distance approximations, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.792-801, January 22-26, 2006, Miami, Florida
	Jeff Hightower , Marcia Talkmitt, 3D in the Pines and on the Plains, Proceedings of the 1998 ACM/IEEE conference on Supercomputing (CDROM), p.1-26, November 07-13, 1998, San Jose, CA
	S. Muthukrishnan, Data streams: algorithms and applications, Foundations and Trends® in Theoretical Computer Science, v.1 n.2, p.117-236, August 2005
	Anders Dessmark , Andrzej Pelc, Distributed Colouring and Communication in Rings with Local Knowledge, Combinatorics, Probability and Computing, v.13 n.2, p.123-136, March 2004
	Y. Han, Matching partition a linked list and its optimization, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.246-253, June 18-21, 1989, Santa Fe, New Mexico, United States