Nagel_Self-stabilizingBallsAndBinsInBatches.pdf (710.47 kB)
Self-stabilizing balls & bins in batches: The power of leaky bins [Extended Abstract]
conference contribution
posted on 2018-02-06, 13:44 authored by Petra Berenbrink, Tom Friedetzky, Peter Kling, Frederik Mallmann-Trenn, Lars NagelLars Nagel, Chris Wastell© 2016 ACM. 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. [4] 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. [7] 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 superexponential) 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.
Funding
Petra Berenbrink is supported by the Natural Sciences and Engineering Research Council of Canada (NSERC). Peter Kling is partly supported by the Natural Sciences and Engi- neering Research Council of Canada (NSERC) and the Pacific Institute for the Mathematical Sciences (PIMS). Lars Nagel is supported by the German Ministry of Education and Research under Grant 01IH13004. Christopher Wastell is supported by EPSRC.
History
School
- Science
Department
- Computer Science
Published in
Proceedings of the Annual ACM Symposium on Principles of Distributed ComputingVolume
25-28-July-2016Pages
83 - 92Citation
BERENBRINK, P. ...et al., 2016. Self-stabilizing balls & bins in batches: The power of leaky bins [Extended Abstract]. IN: Proceedings of the Annual ACM Symposium on Principles of Distributed Computing (PODC '16), New York, 25-28th July, pp. 83-92.Publisher
© the Authors. Published by ACMVersion
- AM (Accepted Manuscript)
Publisher statement
This work is made available according to the conditions of the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0) licence. Full details of this licence are available at: https://creativecommons.org/licenses/by-nc-nd/4.0/Publication date
2016Notes
{© the Authors. Published by ACM {2016}. This is the author's version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in https://doi.org/10.1145/2933057.2933092ISBN
9781450339643Publisher version
Language
- en