Tutte Colloquium - Abbas Mehrabian

Friday, May 20, 2016 3:30 pm - 4:30 pm EDT (GMT -04:00)

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.