Presentation at PODC: Randomised Parallel Allocation of Jobs to Servers

At the ACM Symposium on Principles of Distributed Computing (PODC) in Chicago we will present a theoretical paper on the distribution of jobs to servers. The talk will be given on 26/07/2016.

Title: Self-stabilizing Balls & Bins in Batches

Authors: Petra Berenbrink, Tom Friedetzky, Peter Kling, Frederik Mallmann-Trenn, Lars Nagel, Chris Wastell

Abstract: A fundamental problem in distributed computing is the distribution of requests to a set of uniform servers without a centralized controller. Classically, such problems are modelled as static balls into bins processes, where m balls (tasks) are to be distributed to n bins (servers). In a seminal work, Azar et al. proposed the sequential strategy Greedy[d] for n=m. When thrown, a ball queries the load of d random bins and is allocated to a least loaded of these. Azar et al. showed that d=2 yields an exponential improvement compared to d=1. Berenbrink et al. extended this to m >> n, showing that the maximal load difference is independent of m for d=2 (in contrast to d=1).

We propose a new variant of an infinite balls into bins process. In each round an expected number of c*n new balls arrive and are distributed (in parallel) to the bins and each non-empty bin deletes one of its balls. This setting models a set of servers processing incoming requests, where clients can query a server's current load but receive no information about parallel requests.
We study the Greedy[d] distribution scheme in this setting and show a strong self-stabilizing property: For any arrival rate c=c(n)<1, the system load is time-invariant. Moreover, for any (even super-exponential) round t, the maximum system load is (w.h.p.) O(1/(1-c) * log(n/(1-c))) for d=1 and O(log(n/(1-c)))$ for d=2. In particular, Greedy[2] has an exponentially smaller system load for high arrival rates.