Self-Stabilizing Balls and Bins in Batches: The Power of Leaky Bins

• Published in: Algorithmica 2018-12, Vol.80 (12), p.3673-3703
• Main Authors: Berenbrink, Petra, Friedetzky, Tom, Kling, Peter, Mallmann-Trenn, Frederik, Nagel, Lars, Wastell, Chris
• Format: Article
• Language: English
• Subjects: Algorithm Analysis and Problem Complexity; Algorithms; Computer Science; Computer Systems Organization and Communication Networks; Data Structures and Information Theory; Mathematics of Computing; Theory of Computation
• ISSN: 0178-4617; 1432-0541
• DOI: 10.1007/s00453-018-0411-z

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 among n bins (servers). In a seminal work, Azar et al. (SIAM J Comput 29(1):180–200, 1999 . https://doi.org/10.1137/S0097539795288490 ) proposed the sequential strategy G R E E D Y [ 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. ( 1999 ) showed that d = 2 yields an exponential improvement compared to d = 1 . Berenbrink et al. (SIAM J Comput 35(6):1350–1385, 2006 . https://doi.org/10.1137/S009753970444435X ) 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. Subsequently, 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 G R E E D Y [ 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.) for d = 1 and for d = 2 . In particular, G R E E D Y [ 2 ] has an exponentially smaller system load for high arrival rates.