---
res:
bibo_abstract:
- "We consider the following dynamic load-balancing process: given an underlying
graph G with n nodes, in each step t≥ 0, one unit of load is created, and placed
at a randomly chosen graph node. In the same step, the chosen node picks a random
neighbor, and the two nodes balance their loads by averaging them. We are interested
in the expected gap between the minimum and maximum loads at nodes as the process
progresses, and its dependence on n and on the graph structure. Variants of the
above graphical balanced allocation process have been studied previously by Peres,
Talwar, and Wieder [Peres et al., 2015], and by Sauerwald and Sun [Sauerwald and
Sun, 2015]. These authors left as open the question of characterizing the gap
in the case of cycle graphs in the dynamic case, where weights are created during
the algorithm’s execution. For this case, the only known upper bound is of \U0001D4AA(n
log n), following from a majorization argument due to [Peres et al., 2015], which
analyzes a related graphical allocation process. In this paper, we provide an
upper bound of \U0001D4AA (√n log n) on the expected gap of the above process
for cycles of length n. We introduce a new potential analysis technique, which
enables us to bound the difference in load between k-hop neighbors on the cycle,
for any k ≤ n/2. We complement this with a \"gap covering\" argument, which bounds
the maximum value of the gap by bounding its value across all possible subsets
of a certain structure, and recursively bounding the gaps within each subset.
We provide analytical and experimental evidence that our upper bound on the gap
is tight up to a logarithmic factor. @eng"
bibo_authorlist:
- foaf_Person:
foaf_givenName: Dan-Adrian
foaf_name: Alistarh, Dan-Adrian
foaf_surname: Alistarh
foaf_workInfoHomepage: http://www.librecat.org/personId=4A899BFC-F248-11E8-B48F-1D18A9856A87
- foaf_Person:
foaf_givenName: Giorgi
foaf_name: Nadiradze, Giorgi
foaf_surname: Nadiradze
foaf_workInfoHomepage: http://www.librecat.org/personId=3279A00C-F248-11E8-B48F-1D18A9856A87
- foaf_Person:
foaf_givenName: Amirmojtaba
foaf_name: Sabour, Amirmojtaba
foaf_surname: Sabour
foaf_workInfoHomepage: http://www.librecat.org/personId=bcc145fd-e77f-11ea-ae8b-80d661dbff67
bibo_doi: 10.4230/LIPIcs.ICALP.2020.7
bibo_volume: 168
dct_date: 2020^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/18688969
- http://id.crossref.org/issn/9783959771382
dct_language: eng
dct_publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik@
dct_title: Dynamic averaging load balancing on cycles@
...