TY - GEN
T1 - On balls and bins with deletions
AU - Cole, Richard
AU - Frieze, Alan
AU - Maggs, Bruce M.
AU - Mitzenmacher, Michael
AU - Richa, Andréa W.
AU - Sitaraman, Ramesh
AU - Upfal, Eli
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1998.
PY - 1998
Y1 - 1998
N2 - We consider the problem of extending the analysis of balls and bins processes where a ball is placed in the least loaded of d randomly chosen bins to cover deletions. In particular, we are interested in the case where the system maintains a fixed load, and deletions are determined by an adversary before the process begins. We show that with high probability the load in any bin is O(log log n). In fact, this result follows from recent work by Cole et al. concerning a more difficult problem of routing in a butterfly network. The main contribution of this paper is to give a different proof of this bound, which follows the lines of the analysis of Azar, Broder, Karlin, and Upfal for the corresponding static load balancing problem. We also give a specialized (and hence simpler) version of the argument from the paper by Cole et al. for the balls and bins scenario. Finally, we provide an alternative analysis also based on the approach of Azar, Broder, Karlin, and Upfal for the special case where items are deleted according to their age. Although this analysis does not yield better bounds than our argument for the general case, it is interesting because it utilizes a two dimensional family of random variables in order to account for the age of the items. This technique may be of more general use.
AB - We consider the problem of extending the analysis of balls and bins processes where a ball is placed in the least loaded of d randomly chosen bins to cover deletions. In particular, we are interested in the case where the system maintains a fixed load, and deletions are determined by an adversary before the process begins. We show that with high probability the load in any bin is O(log log n). In fact, this result follows from recent work by Cole et al. concerning a more difficult problem of routing in a butterfly network. The main contribution of this paper is to give a different proof of this bound, which follows the lines of the analysis of Azar, Broder, Karlin, and Upfal for the corresponding static load balancing problem. We also give a specialized (and hence simpler) version of the argument from the paper by Cole et al. for the balls and bins scenario. Finally, we provide an alternative analysis also based on the approach of Azar, Broder, Karlin, and Upfal for the special case where items are deleted according to their age. Although this analysis does not yield better bounds than our argument for the general case, it is interesting because it utilizes a two dimensional family of random variables in order to account for the age of the items. This technique may be of more general use.
UR - http://www.scopus.com/inward/record.url?scp=84958656539&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84958656539&partnerID=8YFLogxK
U2 - 10.1007/3-540-49543-6_12
DO - 10.1007/3-540-49543-6_12
M3 - Conference contribution
AN - SCOPUS:84958656539
SN - 354065142X
SN - 9783540651420
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 145
EP - 158
BT - Randomization and Approximation Techniques in Computer Science - 2nd International Workshop, RANDOM 1998, Proceedings
A2 - Serna, Maria
A2 - Rolim, José D.P
A2 - Luby, Michael
PB - Springer Verlag
T2 - 2nd International Workshop on Randomization and Approximation Techniques in Computer Science, Random 1998
Y2 - 8 October 1998 through 10 October 1998
ER -