CJO - Abstract - Studying Balanced Allocations with Differential Equations

Cambridge Journals Online

Cambridge Journals Online
Skip to content
Combinatorics, Probability and Computing (1999), 8 : 473-482 Cambridge University Press
doi:10.1017/S0963548399003946 (About doi)
 
Combinatorics, Probability and Computing (1999), 8:473-482 Cambridge University Press
Copyright © 1999 Cambridge University Press
Research Article

Studying Balanced Allocations with Differential Equations fn1

MICHAEL MITZENMACHER a1 fn2
a1 Digital Systems Research Center, 130 Lytton Avenue, Palo Alto, CA 94301, USA (e-mail: michaelm@pa.dec.com)

Abstract

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.

(Received November 4 1997)
(Revised June 25 1998)


fn1 A preliminary version of this work appeared in the Proceedings of the 37th Annual IEEE Symposium on the Foundations of Computer Science, October 1996.

fn2 Much of this work was done at U.C. Berkeley, supported by a fellowship from the Office of Naval Research and by NSF grant CCR-9505448.


back to top
Cambridge University Press