MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Vöcking, Bertholddblp
Editor(s):
BibTeX cite key*:
Voecking2001c
Title, Booktitle
Title*:
Symmetric vs. Asymmetric Multiple-Choice Algorithms
Booktitle*:
Proceedings of the 2nd International Workshop on Approximation and Randomized Algorithms in Communication Networks (ARACNE)
Event, URLs
Conference URL::
Downloading URL:
Event Address*:
Aarhus
Language:
English
Event Date*
(no longer used):
August, 27, 2001
Organization:
Event Start Date:
27 August 2001
Event End Date:
27 August 2001
Publisher
Name*:
Carleton Scientific
URL:
Address*:
Waterloo, Ontario, Canada
Type:
Vol, No, Year, pp.
Series:
Volume:
Number:
Month:
Pages:
1-10
Year*:
2001
VG Wort Pages:
ISBN/ISSN:
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
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.
Download
Access Level:
Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Audience:
Expert
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{Voecking2001c,
AUTHOR = {V{\"o}cking, Berthold},
 TITLE = {Symmetric vs. Asymmetric Multiple-Choice Algorithms},
 BOOKTITLE = {Proceedings of the 2nd International Workshop on Approximation and Randomized Algorithms in Communication Networks (ARACNE)},
 PUBLISHER = {Carleton Scientific},
 YEAR = {2001},
 PAGES = {1--10},
 ADDRESS = {Aarhus},
}

Entry last modified by Uwe Brahm, 03/02/2010
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Berthold Voecking		Created
03/17/2002 05:52:10 PM
Revision
1.
0.


Editor
Uwe Brahm
Berthold Voecking


Edit Date
02/14/2005 09:44:33 PM
17/03/2002 17:52:10