Name
Abstract | ||
|---|---|---|
We present a new randomized diffusion-based algorithm for balancing indivisible tasks (tokens) on a network. Our aim is to minimize the discrepancy between the maximum and minimum load. The algorithm works as follows. Every vertex distributes its tokens as evenly as possible among its neighbors and itself. If this is not possible without splitting some tokens, the vertex redistributes its excess tokens among all its neighbors randomly (without replacement). In this paper we prove several upper bounds on the load discrepancy for general networks. These bounds depend on some expansion properties of the network, that is, the second largest eigenvalue, and a novel measure which we refer to as refined local divergence. We then apply these general bounds to obtain results for some specific networks. For constant-degree expanders and torus graphs, these yield exponential improvements on the discrepancy bounds. For hypercubes we obtain a polynomial improvement. Presentation of new algorithm for balancing discrete loads.Algorithm is very natural and avoids nodes having negative loads.Quality measure is the gap between maximum and minimum load, called discrepancy.Upper bounds on discrepancy after algorithm has run as long as its continuous counterpart. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1016/j.jcss.2014.04.027 | Journal of Computer and System Sciences |
Keywords | DocType | Volume |
diffusion,specific network,load discrepancy,indivisible load,randomized diffusion,minimum load,general network,vertex reallocates,negative load,additional dependency,excess token,random walk,distributed computing,randomized algorithms,new randomized diffusion-based algorithm,general bound,load balancing,compression,pattern matching,upper bound | Conference | 81 |
Issue | ISSN | ISBN |
Issue-in-Progress | 0022-0000 | 978-1-61197-251-1 |
Citations | PageRank | References |
8 | 0.54 | 17 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Petra Berenbrink | 1 | 472 | 46.41 |
| Colin Cooper | 2 | 287 | 30.73 |
| tom friedetzky | 3 | 249 | 24.47 |
| Tobias Friedrich | 4 | 211 | 13.48 |
| Thomas Sauerwald | 5 | 575 | 39.99 |