Hostname: page-component-74656f9884-rdgjk Total loading time: 0 Render date: 2026-11-07T10:51:43.112Z Has data issue: false hasContentIssue false

Studying Balanced Allocations with Differential Equations

Published online by Cambridge University Press:  01 September 1999

MICHAEL MITZENMACHER
Affiliation:
Digital Systems Research Center, 130 Lytton Avenue, Palo Alto, CA 94301, USA (e-mail: michaelm@pa.dec.com)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Using differential equations, we examine the GREEDY algorithm studied by Azar, Broder, Karlin and Upfal for distributed load balancing [1]. This approach yields accurate estimates of the actual load distribution, provides insight into the exponential improvement GREEDY offers over simple random selection, and allows one to prove tight concentration theorems about the loads in a straightforward manner.

Information

Type
Research Article
Copyright
1999 Cambridge University Press