Cargando…
Dynamic Averaging Load Balancing on Cycles
We consider the following dynamic load-balancing process: given an underlying graph G with n nodes, in each step [Formula: see text] , a random edge is chosen, one unit of load is created, and placed at one of the endpoints. In the same step, assuming that loads are arbitrarily divisible, the two no...
Autores principales: | , , |
---|---|
Formato: | Online Artículo Texto |
Lenguaje: | English |
Publicado: |
Springer US
2021
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8927032/ https://www.ncbi.nlm.nih.gov/pubmed/35330618 http://dx.doi.org/10.1007/s00453-021-00905-9 |
_version_ | 1784670360683151360 |
---|---|
author | Alistarh, Dan Nadiradze, Giorgi Sabour, Amirmojtaba |
author_facet | Alistarh, Dan Nadiradze, Giorgi Sabour, Amirmojtaba |
author_sort | Alistarh, Dan |
collection | PubMed |
description | We consider the following dynamic load-balancing process: given an underlying graph G with n nodes, in each step [Formula: see text] , a random edge is chosen, one unit of load is created, and placed at one of the endpoints. In the same step, assuming that loads are arbitrarily divisible, 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. Peres et al. (Random Struct Algorithms 47(4):760–775, 2015) studied the variant of this process, where the unit of load is placed in the least loaded endpoint of the chosen edge, and the averaging is not performed. In the case of dynamic load balancing on the cycle of length n the only known upper bound on the expected gap is of order [Formula: see text] , following from the majorization argument due to the same work. In this paper, we leverage the power of averaging and provide an improved upper bound of [Formula: see text] . 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 [Formula: see text] . 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 also show that our analysis can be extended to the specific instance of Harary graphs. On the other hand, we prove that the expected second moment of the gap is lower bounded by [Formula: see text] . Additionally, we provide experimental evidence that our upper bound on the gap is tight up to a logarithmic factor. |
format | Online Article Text |
id | pubmed-8927032 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2021 |
publisher | Springer US |
record_format | MEDLINE/PubMed |
spelling | pubmed-89270322022-03-22 Dynamic Averaging Load Balancing on Cycles Alistarh, Dan Nadiradze, Giorgi Sabour, Amirmojtaba Algorithmica Article We consider the following dynamic load-balancing process: given an underlying graph G with n nodes, in each step [Formula: see text] , a random edge is chosen, one unit of load is created, and placed at one of the endpoints. In the same step, assuming that loads are arbitrarily divisible, 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. Peres et al. (Random Struct Algorithms 47(4):760–775, 2015) studied the variant of this process, where the unit of load is placed in the least loaded endpoint of the chosen edge, and the averaging is not performed. In the case of dynamic load balancing on the cycle of length n the only known upper bound on the expected gap is of order [Formula: see text] , following from the majorization argument due to the same work. In this paper, we leverage the power of averaging and provide an improved upper bound of [Formula: see text] . 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 [Formula: see text] . 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 also show that our analysis can be extended to the specific instance of Harary graphs. On the other hand, we prove that the expected second moment of the gap is lower bounded by [Formula: see text] . Additionally, we provide experimental evidence that our upper bound on the gap is tight up to a logarithmic factor. Springer US 2021-12-24 2022 /pmc/articles/PMC8927032/ /pubmed/35330618 http://dx.doi.org/10.1007/s00453-021-00905-9 Text en © The Author(s) 2021 https://creativecommons.org/licenses/by/4.0/Open AccessThis article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/ (https://creativecommons.org/licenses/by/4.0/) . |
spellingShingle | Article Alistarh, Dan Nadiradze, Giorgi Sabour, Amirmojtaba Dynamic Averaging Load Balancing on Cycles |
title | Dynamic Averaging Load Balancing on Cycles |
title_full | Dynamic Averaging Load Balancing on Cycles |
title_fullStr | Dynamic Averaging Load Balancing on Cycles |
title_full_unstemmed | Dynamic Averaging Load Balancing on Cycles |
title_short | Dynamic Averaging Load Balancing on Cycles |
title_sort | dynamic averaging load balancing on cycles |
topic | Article |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8927032/ https://www.ncbi.nlm.nih.gov/pubmed/35330618 http://dx.doi.org/10.1007/s00453-021-00905-9 |
work_keys_str_mv | AT alistarhdan dynamicaveragingloadbalancingoncycles AT nadiradzegiorgi dynamicaveragingloadbalancingoncycles AT sabouramirmojtaba dynamicaveragingloadbalancingoncycles |