On Diffusion and Selfish Load Balancing

27^th November 2012, 16:00 Ashton Lecture Theatre
Prof. Petra Berenbrink
School of Computing Science
Simon Fraser University
Canada

Abstract

We will discuss various models for network-based load balancing of
discrete tasks in two main settings: resource-driven and task-driven.
Generally speaking, the former class is based upon diffusion-type
algorithms, whereas the latter has a more balls-into-bins flavour.

In the main part of the talk we will consider the resource-driven
models, with particular focus on randomised diffusion, Propp-type
(rotor) algorithms and simulation of the generic continuous algorithm
for arbitrarily splittable tasks. We will then very briefly discuss
task-driven models.

In this talk we aim to present an overview of recent models and results,
and we will only rarely plunge into technical depths but instead only
hint at main ingredients and ideas of the proofs.