Be Fair and Be Selfish! Characterizing Deterministic Diffusive Load-Balancing Schemes with Small Discrepancy

Abstract : We consider the problem of deterministic distributed load balancing of indivisible tasks in the discrete setting. A set of $n$ processors is connected into a $d$-regular symmetric network. In every time step, each processor exchanges some of the tasks allocated to it with each of their neighbours in the network. The goal is to minimize the discrepancy between the number of tasks on the most-loaded and the least-loaded processor as quickly as possible. In this model, the performance of load-balancing schemes obtained by rounding the continuous diffusion process up or down to the nearest integer was considered by Rabani et al. (1998), who showed that after $T = O(\log (Kn)/\mu)$ steps any such scheme achieves a discrepancy of $O(d\log n/\mu)$, where $\mu$ is the spectral gap of the transition matrix of the network graph, and $K$ is the initial load discrepancy in the system. In this work, we identify natural additional conditions on the form of the discrete deterministic balancing scheme, which result in smaller values of discrepancy between maximum and minimum load. Specifically, we introduce the notion of a \emph{cumulatively fair} load-balancing scheme, in which every node sends in total almost the same number of tasks along each of its outgoing edges during every interval of consecutive time steps, and not only at every single step. As our first main result, we prove that any scheme which is cumulatively fair and which has the selfish property that every node retains a sufficient part of its load for itself at each step, achieves a discrepancy of $O(\min\{d\sqrt{\log n/\mu} ,d\sqrt{n}\})$ in time $O(T)$, and that in general neither of these assumptions may be omitted without increasing discrepancy. We then show that any cumulatively fair scheme satisfying additional assumptions on fairness and selfishness achieves a discrepancy of $O(d)$ almost as quickly as the continuous diffusion process. In particular, we provide an example of a scheme belonging to this class, which is both deterministic and stateless, i.e.\ such that the number of tasks sent by a node to its neighbours is a function of only its current load. The $O(d)$ discrepancy achieved by this scheme is asymptotically the best possible in the class of stateless schemes and is reached after time $O(T + \log^2 n/\mu)$. We also provide time bounds for other schemes belonging to the characterized class, such as variants of the deterministic rotor-router process, and remark on possible generalizations of our results.
Document type :
Preprints, Working Papers, ...
Complete list of metadatas

https://hal.inria.fr/hal-00979691
Contributor : Adrian Kosowski <>
Submitted on : Wednesday, May 14, 2014 - 5:15:37 PM
Last modification on : Monday, March 4, 2019 - 2:04:14 PM
Long-term archiving on: Monday, April 10, 2017 - 10:58:16 PM

Files

RotorRouter.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00979691, version 2
  • ARXIV : 1404.4344

Citation

Petra Berenbrink, Ralf Klasing, Adrian Kosowski, Frederik Mallmann-Trenn, Przemyslaw Uznanski. Be Fair and Be Selfish! Characterizing Deterministic Diffusive Load-Balancing Schemes with Small Discrepancy. 2014. ⟨hal-00979691v2⟩

Share

Metrics

Record views

279

Files downloads

41