%0 DATA
%A Petra, Berenbrink
%A Tom, Friedetzky
%A Peter, Kling
%A Frederik, Mallmann-Trenn
%A Lars, Nagel
%A Chris, Wastell
%D 2018
%T Self-stabilizing balls and bins in batches: The power of leaky bins
%U https://repository.lboro.ac.uk/articles/Self-stabilizing_balls_and_bins_in_batches_The_power_of_leaky_bins/9403178
%2 https://repository.lboro.ac.uk/ndownloader/files/17019761
%K Balls-into-bins
%K Self-stabilizing
%K 2-choice
%K Positive recurrent
%K Maximum load
%X 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 among n bins (servers). In a seminal work, Azar et al. [4] proposed the sequential strategy Greedy[d] for n = m. Each ball queries the load of d random bins and is allocated to a least loaded of them. Azar et al. showed that d = 2 yields an exponential improvement compared to d = 1. Berenbrink et al. [7] extended this to m n, showing that for d = 2 the maximal load difference is independent of m (in contrast to the d = 1 case). We propose a new variant of an infinite balls-into-bins process. In each round an expected number of λ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 λ = λ(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−λ· log n 1−λ for d = 1 and O log n 1−λ for d = 2. In particular, Greedy[2] has an exponentially smaller system load for high arrival rates.