Improved Analysis of Deterministic Load-Balancing Schemes - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2014

Improved Analysis of Deterministic Load-Balancing Schemes

Résumé

We consider the problem of deterministic load balancing of tokens in the discrete model. A set of $n$ processors is connected into a $d$-regular undirected network. In every time step, each processor exchanges some of its tokens with each of its neighbours in the network. The goal is to minimize the discrepancy between the number of tokens on the most-loaded and the least-loaded processor as quickly as possible. Rabani et al. (1998) present a general technique for the analysis of a wide class of discrete load balancing algorithms. Their approach is to characterize the deviation between the actual loads of a discrete balancing algorithm with the distribution generated by a related Markov chain. The Markov chain can also be regarded as the underlying model of a continuous diffusion algorithm. Rabani et al. showed that after time $T = O(\log (Kn)/\mu)$ any algorithm of their class achieves a discrepancy of $O(d\log n/\mu)$, where $\mu$ is the spectral gap of the transition matrix of the graph, and $K$ is the initial load discrepancy in the system. In this work we identify some natural additional conditions on deterministic balancing algorithms, resulting in a class of algorithms reaching a smaller discrepancy. Specifically, we introduce the notion of cumulatively fair load-balancing algorithms where the total number of tokens sent over any outgoing edge of a node is the same for every interval of consecutive time steps. We prove that algorithms, which are cumulatively fair and where every node retains a sufficient part its load in each step, achieve a discrepancy of $O(\min\{d\sqrt{\log n/\mu} ,d\sqrt{n}\})$ in time $O(T)$. We also show that in general neither of these assumptions may be omitted without increasing discrepancy. We then show that any cumulatively fair scheme satisfying some additional assumptions achieves a discrepancy of $O(d)$ almost as quickly as the continuous diffusion process.
Fichier principal
Vignette du fichier
arxiv.pdf (274.39 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-00979691 , version 1 (16-04-2014)
hal-00979691 , version 2 (14-05-2014)
hal-00979691 , version 3 (19-07-2014)
hal-00979691 , version 4 (22-02-2015)

Identifiants

Citer

Petra Berenbrink, Ralf Klasing, Adrian Kosowski, Frederik Mallmann-Trenn, Przemyslaw Uznanski. Improved Analysis of Deterministic Load-Balancing Schemes. 2014. ⟨hal-00979691v3⟩

Collections

UNIV-AMU
611 Consultations
339 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More