Abstract | ||
---|---|---|
We consider the problem of scheduling a given flow on a synchronous distributed network. This problem arises using diffusion-based approaches to compute a balancing flow, which has to be scheduled afterwards. We show that every distributed scheduling strategy requires at least 3/2 times the minimum number of rounds. Furthermore we give a distributed algorithm for flows on tree networks, which requires at most two times the optimal number of rounds. |
Year | DOI | Venue |
---|---|---|
2002 | 10.1007/3-540-45687-2_41 | MFCS |
Keywords | Field | DocType |
tree network,balancing flow,scheduling flows,optimal number,diffusion-based approach,minimum number,distributed algorithm | Flow network,Fair-share scheduling,Control flow graph,Load balancing (computing),Computer science,Scheduling (computing),Distributed algorithm,Tree structure,Dynamic priority scheduling,Distributed computing | Conference |
Volume | ISSN | ISBN |
2420 | 0302-9743 | 3-540-44040-2 |
Citations | PageRank | References |
1 | 0.37 | 6 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Thomas Lücking | 1 | 353 | 28.79 |
Burkhard Monien | 2 | 2199 | 279.35 |
Manuel Rode | 3 | 192 | 13.92 |