Self-stabilizing Balls & Bins in Batches: The Power of Leaky Bins

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

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.; JoC'99] 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.; JoC'99] showed that d=2 yields an exponential improvement compared to d=1. [Berenbrink et al.; JoC'06] 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 λ 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 over 1-λ•logn over 1-λ) for d=1 and O(log n over 1-λ) for d=2. In particular, Greedy[2] has an exponentially smaller system load for high arrival rates.

Citation

Berenbrink, P., Friedetzky, T., Kling, P., Mallmann-Trenn, F., Nagel, L., & Wastell, C. (2016, December). Self-stabilizing Balls & Bins in Batches: The Power of Leaky Bins. Presented at ACM Symposium on Principles of Distributed Computing - PODC '16, Chicago, Illinois, USA

• Presentation Conference Type: Conference Paper (published)
• Conference Name: ACM Symposium on Principles of Distributed Computing - PODC '16
• Acceptance Date: Apr 24, 2016
• Online Publication Date: Jul 25, 2016
• Publication Date: Jan 1, 2016
• Deposit Date: Oct 17, 2016
• Publicly Available Date: Oct 21, 2016
• Publisher: Association for Computing Machinery (ACM)
• Pages: 83-92
• Series Title: ACM Symposium on Principles of Distributed Computing
• Series Number: 10.1145/2933057.2933092
• Book Title: Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing.
• DOI: https://doi.org/10.1145/2933057.2933092
• Public URL: https://durham-repository.worktribe.com/output/1151038
• Related Public URLs: https://arxiv.org/abs/1603.02188
• Additional Information: Conference date: July 25-29, 2016