Skip to main content

Research Repository

Advanced Search

Dynamic diffusion load balancing

Berenbrink, P.; Friedetzky, T.; Martin, R.; Caires, L.; Italiano, G.F.; Monteiro, L.; Palamidessi, C.; Yung, M.

Dynamic diffusion load balancing Thumbnail


Authors

P. Berenbrink

T. Friedetzky

R. Martin

L. Caires

G.F. Italiano

L. Monteiro

C. Palamidessi

M. Yung



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., Caires, L., Italiano, G., Monteiro, L., …Yung, M. (2005). Dynamic diffusion load balancing. In Automata, languages and programming : 32nd International Colloquium, ICALP 2005, 11-15 July 2005, Lisbon, Portugal ; proceedings (1386-1398). https://doi.org/10.1007/11523468_112

Conference Name 32nd International Colloquium on Automata, Languages and Programming : ICALP 2005
Conference Location Lisboa, Portugal
Start Date Jul 11, 2005
End Date Jul 15, 2005
Publication Date 2005-07
Deposit Date Nov 4, 2008
Publicly Available Date Nov 4, 2008
Pages 1386-1398
Series Title Lecture notes in computer science
Series Number 3580
Series ISSN 0302-9743,1611-3349
Book Title Automata, languages and programming : 32nd International Colloquium, ICALP 2005, 11-15 July 2005, Lisbon, Portugal ; proceedings
ISBN 9783540275800
DOI https://doi.org/10.1007/11523468_112
Keywords Network, Algorithm, Load generation model.
Publisher URL http://springerlink.metapress.com/link.asp?id=bn60fter0q68whlq
Additional Information July 11-15, 2005.

Files



Downloadable Citations