Title: Tight Load Balancing via Randomized Local Search
Speaker: | Abbas Mehrabian |
Affiliation: | University of British Columbia |
Room: | MC 5501 |
Abstract:
Consider
n
identical
resources
and
m
identical
users.
Initially
each
user
is
assigned
to
some
resource.
We
analyze
a
distributed
randomized
local
search
protocol
introduced
in
2004
by
Goldberg,
whose
goal
is
to
re-allocate
users
to
resources
such
that
the
load
is
perfectly
balanced.
In
this
protocol,
users
are
activated
by
independent
exponential
clocks
of
rate
1.
On
activation,
a
user
samples
a
random
resource
and
compares
that
resource's
load
with
its
current
load.
If
the
new
load
is
lower,
the
user
switches.
It was known that the expected balancing time is O(ln^2 n + ln(n) x n^2/m). We improve this to O(ln(n) + n^2/m), which is tight. We also generalize this result to the setting where the resources may have different speeds. This is joint work with Petra Berebrink, Peter Kling, and Chris Liaw.