Self-Stabilizing Balls and Bins in Batches : The Power of Leaky Bins
- Submitting institution
-
King's College London
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 127986513
- Type
- D - Journal article
- DOI
-
10.1007/s00453-018-0411-z
- Title of journal
- ALGORITHMICA
- Article number
- -
- First page
- 3673
- Volume
- 80
- Issue
- 12
- ISSN
- 0178-4617
- Open access status
- Compliant
- Month of publication
- February
- Year of publication
- 2018
- URL
-
-
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
5
- Research group(s)
-
-
- Citation count
- 0
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- This paper analyses a fundamental problem in distributed computing: the distribution of requests to a set of uniform servers without a centralised controller. In the most common solution, the GREEDY process of [Azar et al. SODA 94], each request samples a few servers and moves to the server with the lowest load. This paper is the first to analyse the more realistic setting with parallel arrivals and job completions. The results found applications in mobile cloudlet computing (Shuang Lai et al. IEEE Access v.8, 2020) and blockchains (Ahmad et al. ICC19). Moreover, they translate into results for queuing-theory.
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -