Abstract

Sequential resource allocation problems arise naturally in computer science. For example, load balancing can be viewed as an instance of such problem. Therefore, there is general interest from the community in methods for distributing resources evenly, robustly and efficiently. This presentation introduces the balls into bins model as an abstract characterization of such problems. Different allocation strategies will be discussed and contrasted, with an emphasis on randomized allocations such as the one-choice and the d­choice processes. We shall show that the latter, being a simple generalization of the former, does possess the three properties we seek for allocation algorithms. Perhaps surprisingly, these theoretical results can be applied to drastically optimise the performance of hash tables.