Skip to main content

Research Repository

Advanced Search

On the Stability of Dynamic Diffusion Load Balancing

Berenbrink, P.; Friedetzky, T.; Martin, R.

On the Stability of Dynamic Diffusion Load Balancing Thumbnail


Authors

P. Berenbrink

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