2016/03/07 by Petra Berenbrink, Berenbrink, Petra, Tom Friedetzky +9 · 1 citation
Computer Science · #Cryptography and Data Security #Distributed #Distributed systems and fault tolerance #FOS: Computer and information sciences #Optimization and Search Problems #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1603.02188
openalex publication_date 2016/03/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 modeled 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 \greedyd 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. Each round an expected number of λn new balls arrive and are distributed (in parallel) to the bins. 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 \greedyd 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, \greedy2 has an exponentially smaller system load for high arrival rates.