Professor Alistair Sinclair Chair Professor Christos Papadimitriou Professor David Aldous 1996

Abstract:  The Power of Two Choices in Randomized Load Balancing by Michael David Mitzenmacher Doctor of Philosophy in Computer Science University of California at Berkeley Professor Alistair Sinclair, Chair Suppose that n balls are placed into n bins, each ball being placed into a bin chosen independently and uniformly at random. Then, with high probability, the maximum load in any bin is approximately log n log log n . Suppose instead that each ball is placed sequentially into the least full of d bins chosen independently and uniformly at random. It has recently been shown that the maximum load is then only log log n log d +O(1) with high probability. Thus giving each ball two choices instead of just one leads to an exponential improvement in the maximum load. This result demonstrates the power of two choices, and it has several applications to load balancing in distributed systems. In this thesis, we expand upon this result by examining related models and by developing techniques for stu...