TIME: 1:30-2:20 pm,  March 28, 2006

PLACE: CSE 403

TITLE: Distributed Selfish Load Balancing

SPEAKER:  Petra Berenbrink
          Simon Fraser University

ABSTRACT:
Suppose that a set of m tasks are to be shared as equally as
possible amongst a set of n resources. A game-theoretic mechanism to
find a suitable allocation is to associate each task with a ``selfish
agent'', and require each agent to select a resource, with the cost of a
resource being the number of agents to select it. Agents would then be
expected to migrate from overloaded to underloaded resources, until
the allocation becomes balanced.

Recent work has studied the question of how this can take place within
a distributed setting in which agents migrate selfishly without any
centralized control. In this talk we discuss a natural protocol for the
agents which combines the following desirable features: It can
be implemented in a strongly distributed setting, uses no central
control, and has good convergence properties.  We show using a martingale
technique that the process converges in expected polynamial time. We also
give a lower bound  for the  convergence time, as well as an exponential
lower bound (in n) for a variant of this  protocol that allows the agents
to migrate even if they do not strictly improve their situation.

Joint work with Tom Friedetzky, Leslie Ann Goldberg, Paul Goldberg,
Zengjian Hu and Russel Martin