Constant time per edge is optimal on rooted tree networks

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Constant time per edge is optimal on rooted tree networks

Full text

Pdf (876 KB)

Source

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

Padua, Italy

Pages: 162 - 169

Year of Publication: 1996

ISBN:0-89791-809-6

Author

Michael Mitzenmacher

Computer Science Division, U.C. Berkeley, Berkeley, CA

Sponsors

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): 2, Downloads (12 Months): 11, 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/237502.237524 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	Allan Borodin , Jon Kleinberg , Prabhakar Raghavan , Madhu Sudan , David P. Williamson, Adversarial queueing theory, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.376-385, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237984]
	2	H. D. Friedman. Reduction methods for tandem queuing systems. Operations Research, 13:121-131, 1965.
	3	Mor Harchol-Balter , David Wolfe, Bounding delays in packet-routing networks, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.248-257, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225133]
	4	Nabil Kahale , Tom Leighton, Greedy dynamic routing on arrays, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.558-566, January 22-24, 1995, San Francisco, California, United States
	5	F.P. Kelly. Reversibility and Stochastic Networks. John Wiley and Sons, 1979.
	6	L. Kleinrock. Queueing Systems, Volume iI: Computer Applications. John Wiley and Sons, 1976.
	7	F. T. Leighton, Average case analysis of greedy routing algorithms on arrays, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.2-10, July 02-06, 1990, Island of Crete, Greece [doi>10.1145/97444.97448]
	8	M.A. Mars#n. On some discrete time queueing systems. Alta Frequenza, 49:285-292, 1980.
	9	Michael Mitzenmacher, Bounds on the greedy routing algorithm for array networks, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.346-353, June 27-29, 1994, Cape May, New Jersey, United States [doi>10.1145/181014.181446]
	10	S.C. Niu. On the comparison of waiting times in tandem queues. Journal of Applied Probability, 18:707-714, 1981.
	11	R. Righter. and J. Shanthikumar. Extremal properties of the fifo discipline in queueing networks. Journal of Applied Probability, 29:967-978, November 1992.
	12	T. Rolski and D. Stoyan. On the comparison of waiting times in gi/g/1 queues. Operations Research, 24:197- 200, 1976.
	13	S.M. Ross. Average delay in queues with non-stationary poisson arrivals. Journal of Applied Probabdzty, 15:602- 609, 1978.
	14	S.M. Ross. Stochastic Models. John Wiley and Sons, 1983.
	15	I. Rubin. Communication networks: Message path delays. IEEE Transactions of the Professional Group on In}ormation Theory, 20:738-745, 1974.
	16	M. Shaked and J. Shantikumar. Stochastic Orders and Their Applications. Academic Press, Inc., 1994.
	17	George D. Stamoulis , John N. Tsitsiklis, The efficiency of greedy routing in hypercubes and butterflies, Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.248-259, July 21-24, 1991, Hilton Head, South Carolina, United States [doi>10.1145/113379.113402]
	18	D. Stoyan. Compamson Method.for Queues and Other Stochastic Models. John Wiley and Sons, 1983.
	19	R. Szekli. Stochastic Ordering and Dependence in Applied Probability : Lecture Notes in Statistics 97. Springer-Verlag, 1995.

CITED BY 7

	Michael Mitzenmacher, Analyses of load stealing models based on differential equations, Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.212-221, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Stephen Alstrup , Jacob Holm , Kristian de Lichtenberg , Mikkel Thorup, Direct routing on trees, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.342-349, January 25-27, 1998, San Francisco, California, United States
	Uriel Feige, Nonmonotonic phenomena in packet routing, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.583-591, May 01-04, 1999, Atlanta, Georgia, United States
	Michael Mitzenmacher, On the analysis of randomized load balancing schemes, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.292-301, June 23-25, 1997, Newport, Rhode Island, United States
	Michael Mitzenmacher, How useful is old information (extended abstract)?, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.83-91, August 21-24, 1997, Santa Barbara, California, United States
	Michael Mitzenmacher, How Useful Is Old Information?, IEEE Transactions on Parallel and Distributed Systems, v.11 n.1, p.6-20, January 2000
	Costas Busch , Malik Magdon-Ismail , Marios Mavronicolas, Efficient bufferless packet switching on trees and leveled networks, Journal of Parallel and Distributed Computing, v.67 n.11, p.1168-1186, November, 2007