BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Randomised Load Balancing For Networks - Thomas Sauerwald - Univer
 sity of Cambridge\, Computer Laboratory
DTSTART:20140129T140000Z
DTEND:20140129T150000Z
UID:TALK49751@talks.cam.ac.uk
CONTACT:David Greaves
DESCRIPTION:We consider the problem of balancing load items (tokens) on ne
 tworks. Starting with an arbitrary load distribution\, we allow in each ro
 und nodes to exchange tokens with their neighbours. The goal is to obtain 
 a load distribution where all nodes have the same number of tokens. For th
 e continuous case where tokens are arbitrarily divisible\, most load balan
 cing schemes correspond to Markov chains whose convergence is fairly well-
 understood.\n\nHowever\, in many applications load items cannot be divided
  arbitrarily often and we need to deal with the discrete case where load i
 s composed of indivisible tokens. In this talk we investigate a natural ra
 ndomised protocol and demonstrate that there is almost no difference betwe
 en the discrete and continuous case. Specifically we show that for any reg
 ular network all nodes have the same number of tokens up to an additive co
 nstant in the same number of rounds as in the continuous case.
LOCATION:Lecture Theatre 1\, Computer Laboratory
END:VEVENT
END:VCALENDAR