MST construction in O(log log n) communication rounds

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

MST construction in O(log log n) communication rounds

Full text

Pdf (167 KB)

Source

ACM Symposium on Parallel Algorithms and Architectures archive
Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures table of contents

San Diego, California, USA

SESSION: Algorithms 1 table of contents

Pages: 94 - 100

Year of Publication: 2003

ISBN:1-58113-661-7

Authors

Zvi Lotker	Tel Aviv University, Tel Aviv, Israel
Elan Pavlov	Hebrew University, Jerusalem, Israel
Boaz Patt-Shamir	Hewlett Packard, One Cambridge Center, Cambridge MA
David Peleg

Sponsors

ACM: Association for Computing Machinery
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

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

Additional Information:

abstract 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/777412.777428 What is a DOI?

ABSTRACT

We consider a simple model for overlay networks, where all n processes are connected to all other processes, and each message contains at most O(log n) bits. For this model, we present a distributed algorithm that constructs a minimum-weight spanning tree in O(log log n) communication rounds, where in each round any process can send a message to each other process. This result is the first to break the ω(log n) parallel time complexity barrier with small message sizes.

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	Micah Adler , Wolfgang Dittrich , Ben Juurlink , Mirosław Kutyłowski , Ingo Rieping, Communication-optimal parallel minimum spanning tree algorithms (extended abstract), Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.27-36, June 28-July 02, 1998, Puerto Vallarta, Mexico [doi>10.1145/277651.277662]
	2	Baruch Awerbuch, Complexity of network synchronization, Journal of the ACM (JACM), v.32 n.4, p.804-823, Oct. 1985 [doi>10.1145/4221.4227]
	3	B. Awerbuch, Optimal distributed algorithms for minimum weight spanning tree, counting, leader election, and related problems, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.230-240, January 1987, New York, New York, United States [doi>10.1145/28395.28421]
	4	B. Awerbuch , Y. Shiloach, New connectivity and MSF algorithms for shuffle-exchange network and PRAM, IEEE Transactions on Computers, v.36 n.10, p.1258-1263, Oct. 1987 [doi>10.1109/TC.1987.1676869]
	5	Richard Cole , Philip N. Klein , Robert E. Tarjan, Finding minimum spanning forests in logarithmic time and linear work using random sampling, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.243-250, June 24-26, 1996, Padua, Italy [doi>10.1145/237502.237563]
	6	R. G. Gallager , P. A. Humblet , P. M. Spira, A Distributed Algorithm for Minimum-Weight Spanning Trees, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.1, p.66-77, Jan. 1983 [doi>10.1145/357195.357200]
	7	Juan A. Garay , Shay Kutten , David Peleg, A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees, SIAM Journal on Computing, v.27 n.1, p.302-316, Feb. 1998 [doi>10.1137/S0097539794261118]
	8	J. Jannotti, D. Gifford, K. L. Johnson, M. F. Kaashoek, and J. J. W. O'Toole. Overcast: Reliable multicasting with an overlay network. In 4th USENIX OSDI, pages 197--212, October 2000.
	9	David R. Karger , Philip N. Klein , Robert E. Tarjan, A randomized linear-time algorithm to find minimum spanning trees, Journal of the ACM (JACM), v.42 n.2, p.321-328, March 1995 [doi>10.1145/201019.201022]
	10	Zvi Lotker , Boaz Patt-Shamir , David Peleg, Distributed MST for constant diameter graphs, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.63-71, August 2001, Newport, Rhode Island, United States [doi>10.1145/383962.383984]
	11	Nancy A. Lynch, Distributed Algorithms, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
	12	David Peleg , Vitaly Rubinovich, A Near-Tight Lower Bound on the Time Complexity of Distributed Minimum-Weight Spanning Tree Construction, SIAM Journal on Computing, v.30 n.5, p.1427-1442, 2000 [doi>10.1137/S0097539700369740]
	13	J. H. Saltzer , D. P. Reed , D. D. Clark, End-to-end arguments in system design, ACM Transactions on Computer Systems (TOCS), v.2 n.4, p.277-288, Nov. 1984 [doi>10.1145/357401.357402]
	14	Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.149-160, August 2001, San Diego, California, United States
	15	Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983