2015 | OriginalPaper | Buchkapitel
Locally Optimal Load Balancing
verfasst von : Laurent Feuilloley, Juho Hirvonen, Jukka Suomela
Erschienen in: Distributed Computing
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
This work studies distributed algorithms for
locally optimal load-balancing
: We are given a graph of maximum degree
$\varDelta$
, and each node has up to
L
units of load. The task is to distribute the load more evenly so that the loads of adjacent nodes differ by at most 1. If the graph is a path (
$\varDelta = 2$
), it is easy to solve the
fractional
version of the problem in
O
(
L
) communication rounds, independently of the number of nodes. We show that this is tight, and we show that it is possible to solve also the
discrete
version of the problem in
O
(
L
) rounds in paths. For the general case (
$\varDelta > 2$
), we show that fractional load balancing can be solved in
${\rm poly}(L,\varDelta)$
rounds and discrete load balancing in
$f(L,\varDelta)$
rounds for some function
f
, independently of the number of nodes.