Studying Balanced Allocations with Differential Equations.pdfVIP

SRC Technical Note 1997 - 024 October 1, 1997 Studying Balanced Allocations with Differential Equations Michael Mitzenmacher d i g i t a l Systems Research Center 130 Lytton Avenue Palo Alto, California 94301 /SRC/ c Copyright Digital Equipment Corporation 1997. All rights reserved Studying Balanced Allocations with Differential Equations Michael Mitzenmacher y 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 distribu- tion, 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. 1 Introduction Suppose that n balls are placed into n bins, with each ball being placed into a bin chosen independently and uniformly at random. Let the load of a bin be the number of balls in that bin after all balls have been thrown. It is well known that with high probability, the maximum load upon completion will be approximately log n log log n [8]. (We use with high probability to mean with probability at least 1 − O 1n, where n is the number of balls. Also, log will always mean the natu