2020/10/06 by Yefim Dinitz, Dinitz, Yefim, Shlomi Dolev +3
Computer Science · #Age of Information Optimization #Cloud Computing and Resource Management #Distributed #Distributed systems and fault tolerance #FOS: Computer and information sciences #Optimization and Search Problems #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2010.02486
openalex publication_date 2020/10/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In computer networks, participants may cooperate in processing tasks, so that\nloads are balanced among them. We present local distributed algorithms that\n(repeatedly) use local imbalance criteria to transfer loads concurrently across\nthe participants of the system, iterating until all loads are balanced. Our\nalgorithms are based on a short local deal-agreement communication of\nproposal/deal, based on the neighborhood loads. They converge monotonically,\nalways providing a better state as the execution progresses. Besides, our\nalgorithms avoid making loads temporarily negative. Thus, they may be\nconsidered anytime ones, in the sense that they can be stopped at any time\nduring the execution. We show that our synchronous load balancing algorithms\nachieve \ε-Balanced state for the continuous setting and 1-Balanced\nstate for the discrete setting in all graphs, within O(n D \log(n\nK/\ε)) and O(n D \log(n K/D) + n D2) time, respectively, where n is\nthe number of nodes, K is the initial discrepancy, D is the graph diameter,\nand \ε is the final discrepancy. Our other monotonic synchronous and\nasynchronous algorithms for the discrete setting are generalizations of the\nfirst presented algorithms, where load balancing is performed concurrently with\nmore than one neighbor. These algorithms arrive at a 1-Balanced state in time\nO(n K2) in general graphs, but have a potential to be faster as the loads\nare balanced among all neighbors, rather than with only one; we describe a\nscenario that demonstrates the potential for a fast (O(1)) convergence. Our\nasynchronous algorithm avoids the need to wait for the slowest participants'\nactivity prior to making the next load balancing steps as synchronous settings\nrestrict. We also introduce a self-stabilizing version of our asynchronous\nalgorithm.\n