非表示:
キーワード:
-
要旨:
Multiple-choice allocation algorithms have been studied intensively
over the last decade. These algorithms have several applications
in the areas of load balancing, routing, resource allocation and
hashing. The underlying idea is simple and can be explained best
in the balls-and-bins model: Instead of assigning balls
(jobs, requests, or keys) simply at random to bins (machines, servers,
or positions in a hash table), choose first a small set of bins at
random, inspect these bins, and place the ball into one of the bins
containing the smallest number of balls among them.
The simple idea of first selecting a small set of alternatives at
random and then making the final choice after careful inspection of
these alternatives leads to great improvements against algorithms
that place their decisions simply at random. We illustrate the power
of this principle in terms of simple balls-and-bins processes.
In particular, we study recently presented algorithms that
treat bins asymmetrically in order to obtain a better load balancing.
We compare the behavior of these asymmetric schemes with symmetric
schemes and prove that the asymmetric schemes achieve a better load
balancing than their symmetric counterparts.
