Title : Geometrical and Multi-dimensional Generalizations of 
the Power of Two Choices

In this talk I present some new load-balancing results under 
the paradigm of the ``Power of Two Choices''. In standard 
analysis, such as for hash-tables, load-balancing is modeled 
as a balls-and-bins problem: items (balls) are thrown into 
locations (bins) uniformly at random. The power of two 
choices paradigm allows each ball two (or more) choices of 
bins, each taken uniformly at random, which is known to 
greatly improve the balance of the load. In peer-to-peer and 
sensor networks, bins may correspond to spaces defined by 
the underlying geometry that may not be equal in size; 
locations therefore cannot be modelled as being chosen 
uniformly at random. We therefore consider geometrical 
generalizations of the power of two choices. For search 
engines, we are concerned with word frequencies; the goal is 
to keep the number of documents with a given word stored at 
each server balanced simultaneously for all (sufficiently 
frequent) words. In this case, balls correspond to 
documents, but now a ball is really a vector (or word list) 
instead of a single item. We therefore consider multi-
dimensional generalizations of the power of two choices.