How useful is old information (extended abstract)?

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

How useful is old information (extended abstract)?

Full text

Pdf (941 KB)

Source

Annual ACM Symposium on Principles of Distributed Computing archive
Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing table of contents

Santa Barbara, California, United States

Pages: 83 - 91

Year of Publication: 1997

ISBN:0-89791-952-1

Author

Michael Mitzenmacher

Digital Systems Research Center, 130 Lytton Ave., Palo Alto, CA

Sponsors

SIGOPS: ACM Special Interest Group on Operating Systems
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 12, Citation Count: 13

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/259380.259426 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. Alanyali , B. Hajek, On simple algorithms for dynamic load balancing, Proceedings of the Fourteenth Annual Joint Conference of the IEEE Computer and Communication Societies (Vol. 1)-Volume, p.230, April 02-06, 1995
	2	Baruch Awerbuch , Yossi Azar , Amos Fiat , Tom Leighton, Making commitments in the face of uncertainty: how to pick a winner almost every time (extended abstract), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.519-530, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.238000]
	3	Yossi Azar , Andrei Z. Broder , Anna R. Karlin , Eli Upfal, Balanced allocations (extended abstract), Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.593-602, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195412]
	4	D. R. Cox, W. L. Smith, Queues, Wiley, 1961.
	5	Derek L. Eager , Edward D. Lazowska , John Zahorjan, Adaptive load sharing in homogeneous distributed systems, IEEE Transactions on Software Engineering, v.12 n.5, p.662-675, May 1986
	6	S. N. Ethier and T. G. Kurtz, Markov Processes: Characterization and Convergence, 1986, John Wiley and Sons.
	7	Richard M. Karp , Michael Luby , Friedhelm Meyer auf der Heide, Efficient PRAM simulation on a distributed memory machine, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.318-326, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129743]
	8	T. G. Kurtz, Approximation of Population Proceases, SIAM, 1981.
	9	R. Mirchandaney , D. Towsley , J. A. Stankovic, Analysis of the Effects of Delays on Load Sharing, IEEE Transactions on Computers, v.38 n.11, p.1513-1525, November 1989 [doi>10.1109/12.42124]
	10	Ravi Mirchandaney , Don Towsley , John A. Stankovic, Adaptive load sharing in heterogeneous distributed systems, Journal of Parallel and Distributed Computing, v.9 n.4, p.331-346, Aug. 1990 [doi>10.1016/0743-7315(90)90118-9]
	11	Michael Mitzenmacher, Constant time per edge is optimal on rooted tree networks, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.162-169, June 24-26, 1996, Padua, Italy [doi>10.1145/237502.237524]
	12	M. Mitzenmacher, Load balancing and density dependent jump Markov processes, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.213, October 14-16, 1996
	13	Michael David Mitzenmacher , Alistair Sinclair, The power of two choices in randomized load balancing, 1996
	14	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 [doi>10.1145/258492.258521]
	15	A. Shwartz and A. Weiss, Large Deviations for Performance Analysis, 1995, Chapman & Hall.
	16	G. D. Stamoulis and J. N. Tsitsiklis, "The Efficiency of Greedy Routing in Hypercubes and Butterflies", IEEE Transactions on Communications, Vol. 42(11), 1994, pp. 3051-3061.
	17	D. Towsley and R. Mirchandaney, "The Effect of Communication Delays on the Performance of Load Balancing Policies in Distributed Systems", Proceedings of the Second International MCPR Workshop, 1988, pp. 213-226.
	18	R. Weber, "On the Optimal Assignment of Customers to Parallel Servers", J. of Appl. Prob., Vol 15, 1978, pp. 406-413.
	19	Ward Whitt, Deciding which queue to join: Some counterexamples, Operations Research, v.34 n.1, p.55-62, Jan./Feb. 1986 [doi>10.1287/opre.34.1.55]
	20	W. Winston, "Optimality of the Shortest Line Discipline", J. o! Appl. Prob., Vol 14, 1977, pp. 181-189.
	21	N. C. Wormald, "Differential Equations for Random Processes and Random Graphs", Annals of Appl. Prob., Vol 5, 1995, pp. 1217-1235.
	22	N.D. Vvedenskaya, R.L. Dobrushin, and F.I. Karpelerich. "Queueing System with Selection of the Shortest of Two Queues: an Asymptotic Approach", Problems of Information Transmission, Vol 32, 1996, pp. 15-27.

CITED BY 13

	Susanne Albers , Moses Charikar , Michael Mitzenmacher, Delayed information and action in on-line algorithms, Information and Computation, v.170 n.2, p.135-152, November 1, 2001
	Artur Czumaj, Recovery time of dynamic allocation processes, Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.202-211, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Henri Casanova , Graziano Obertelli , Francine Berman , Rich Wolski, The AppLeS parameter sweep template: user-level middleware for the grid, Proceedings of the 2000 ACM/IEEE conference on Supercomputing (CDROM), p.60-es, November 04-10, 2000, Dallas, Texas, United States
	Walfredo Cirne , Francine Berman, Using moldability to improve the performance of supercomputer jobs, Journal of Parallel and Distributed Computing, v.62 n.10, p.1571-1601, October 2002
	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 Dahlin, Interpreting Stale Load Information, IEEE Transactions on Parallel and Distributed Systems, v.11 n.10, p.1033-1047, October 2000
	Simon Fischer , Berthold Vöcking, Adaptive routing with stale information, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA
	Raffaella Grieco , Delfina Malandrino , Vittorio Scarano, SEcS: scalable edge-computing services, Proceedings of the 2005 ACM symposium on Applied computing, March 13-17, 2005, Santa Fe, New Mexico
	Henri Casanova , Graziano Obertelli , Francine Berman , Richard Wolski, The AppLeS Parameter Sweep Template: User-level middleware for the Grid\m{1}, Scientific Programming, v.8 n.3, p.111-126, August 2000
	Simon Fischer , Harald Räcke , Berthold Vöcking, Fast convergence to Wardrop equilibria by adaptive sampling methods, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Danny Dolev, Century papers at the first quarter-century milestone, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, p.3-4, July 23-26, 2006, Denver, Colorado, USA
	Simon Fischer , Berthold Vöcking, Adaptive routing with stale information, Theoretical Computer Science, v.410 n.36, p.3357-3371, August, 2009
	Robert Kleinberg , Georgios Piliouras , Éva Tardos, Load balancing without regret in the bulletin board model, Proceedings of the 28th ACM symposium on Principles of distributed computing, August 10-12, 2009, Calgary, AB, Canada