Petra Berenbrink
Randomized Diffusion for Indivisible Loads
Berenbrink, Petra; Cooper, Colin; Friedetzky, Tom; Friedrich, Tobias; Sauerwald, Thomas
Authors
Colin Cooper
Dr Tom Friedetzky tom.friedetzky@durham.ac.uk
Associate Professor
Tobias Friedrich
Thomas Sauerwald
Contributors
Dana Randall
Editor
Abstract
We present a new randomized diffusion-based algorithm for balancing indivisible tasks (tokens) on a network. Our aim is to minimize the discrepancy between the maximum and minimum load. The algorithm works as follows. Every vertex distributes its tokens as evenly as possible among its neighbors and itself. If this is not possible without splitting some tokens, the vertex redistributes its excess tokens among all its neighbors randomly (without replacement). In this paper we prove several upper bounds on the load discrepancy for general networks. These bounds depend on some expansion properties of the network, that is, the second largest eigenvalue, and a novel measure which we refer to as refined local divergence. We then apply these general bounds to obtain results for some specific networks. For constant-degree expanders and torus graphs, these yield exponential improvements on the discrepancy bounds compared to the algorithm of Rabani, Sinclair, and Wanka [14]. For hypercubes we obtain a polynomial improvement. In contrast to previous papers, our algorithm is vertex-based and not edge-based. This means excess tokens are assigned to vertices instead to edges, and the vertex reallocates all of its excess tokens by itself. This approach avoids nodes having “negative loads” (like in [8, 10]), but causes additional dependencies for the analysis.
Citation
Berenbrink, P., Cooper, C., Friedetzky, T., Friedrich, T., & Sauerwald, T. (2011). Randomized Diffusion for Indivisible Loads. In . D. Randall (Ed.), Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011 (429-439)
Conference Name | Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms. |
---|---|
Conference Location | San Francisco |
Publication Date | Jan 1, 2011 |
Deposit Date | Nov 29, 2012 |
Publicly Available Date | Dec 13, 2013 |
Publisher | Society for Industrial and Applied Mathematics |
Pages | 429-439 |
Edition | n/a |
Book Title | Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011. |
Public URL | https://durham-repository.worktribe.com/output/1157536 |
Publisher URL | http://www.siam.org/proceedings/soda/2011/SODA11_034_berenbrinkp.pdf |
Files
Published Conference Proceeding
(924 Kb)
PDF
You might also like
Infinite Balanced Allocation via Finite Capacities
(2021)
Conference Proceeding
Randomized renaming in shared memory systems
(2021)
Journal Article
Time-space trade-offs in population protocols for the majority problem
(2020)
Journal Article
Tight & Simple Load Balancing
(2019)
Conference Proceeding
Self-Stabilizing Balls and Bins in Batches
(2018)
Journal Article
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search