Title:  New Directions in Balls and Bins Problems

Abstract:

Balls and bins models, often used in the study of hashing and

load balancing schemes, have enjoyed a great deal of attention in

recent years.  Here we provide a mini-survey of some new directions

for these models.

Balls and Bins with Memory:  A well-studied model from recent years is

that there are n balls and n bins;  balls are placed sequentially by

choosing 2 bins independently and uniformly at random, and placing the

ball in the least loaded of the two.  Using 2 choices per ball instead

of 1 choice reduces the maximum number of balls per bin from       

O(log n / log log n) to O(log log n).  Consider the following alternative:

each ball gets 1 fresh random choice, but it also remembers the best

choice left over from the last ball.  Each ball (except the first) gets

two choices: one random, and one from memory.  How does memory compare

with additional random choices?

Balls and Bins with Feedback:  Suppose that instead of balls being placed

in the least loaded of 2 or more choices,  balls are attracted

to bins according to a function of the number of balls in the bin. 

Such systems model the effect of "positive feedback" studied in economics.

What does the evolution of such systems look like?