P. Berenbrink
On the Stability of Dynamic Diffusion Load Balancing
Berenbrink, P.; Friedetzky, T.; Martin, R.
Authors
T. Friedetzky
R. Martin
Abstract
We consider the problem of dynamic load balancing in arbitrary (connected) networks on n nodes. Our load generation model is such that during each round, n tasks are generated on arbitrary nodes, and then (possibly after some balancing) one task is deleted from every non-empty node. Notice that this model fully saturates the resources of the network in the sense that we generate just as many new tasks per round as the network is able to delete. We show that even in this situation the system is stable, in that the total load remains bounded (as a function of n alone) over time. Our proof only requires that the underlying “communication” graph be connected. (It of course also works if we generate less than n new tasks per round, but the major contribution of this paper is the fully saturated case.) We further show that the upper bound we obtain is asymptotically tight (up to a moderate multiplicative constant) by demonstrating a corresponding lower bound on the system load for the particular example of a linear array (or path). We also show some simple negative results (i.e., instability) for work-stealing based diffusion-type algorithms in this setting.
Citation
Berenbrink, P., Friedetzky, T., & Martin, R. (2008). On the Stability of Dynamic Diffusion Load Balancing. Algorithmica, 50(3), 329-350. https://doi.org/10.1007/s00453-007-9081-y
Journal Article Type | Article |
---|---|
Online Publication Date | Nov 1, 2007 |
Publication Date | Feb 1, 2008 |
Deposit Date | Oct 24, 2008 |
Publicly Available Date | Mar 28, 2024 |
Journal | Algorithmica |
Print ISSN | 0178-4617 |
Electronic ISSN | 1432-0541 |
Publisher | Springer |
Peer Reviewed | Peer Reviewed |
Volume | 50 |
Issue | 3 |
Pages | 329-350 |
DOI | https://doi.org/10.1007/s00453-007-9081-y |
Files
Accepted Journal Article
(227 Kb)
PDF
Copyright Statement
The original publication is available at www.springerlink.com
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