The Library
Dynamic diffusion load balancing
Tools
Berenbrink, Petra, Friedetzky, Thomas and Martin, R. (2005) Dynamic diffusion load balancing. In: Caires, L. and Italiano, G. E. and Monteiro, L. and Palamidessi, C. and Yung, M., (eds.) Automata, Languages and Programming. Lecture Notes in Computer Science, Volume 3580 . Springer Berlin Heidelberg, pp. 1386-1398. ISBN 9783540275800
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1007/11523468_112
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.
Item Type: | Book Item | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Series Name: | Lecture Notes in Computer Science | ||||
Publisher: | Springer Berlin Heidelberg | ||||
ISBN: | 9783540275800 | ||||
ISSN: | 0302-9743 | ||||
Book Title: | Automata, Languages and Programming | ||||
Editor: | Caires, L. and Italiano, G. E. and Monteiro, L. and Palamidessi, C. and Yung, M. | ||||
Official Date: | 2005 | ||||
Dates: |
|
||||
Volume: | Volume 3580 | ||||
Number of Pages: | 13 | ||||
Page Range: | pp. 1386-1398 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Conference Paper Type: | Paper | ||||
Title of Event: | 32nd International Colloquium on Automata, Languages and Programming (ICALP 2005) | ||||
Type of Event: | Other | ||||
Location of Event: | Lisbon, Portugal | ||||
Date(s) of Event: | 11-15 Jul 2005 |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |