Discrete load balancing on complete bipartite graphs

We study the process of balancing m indivisible tokens among n nodes connected by a complete bipartite graph. The load of a node at time t is the number of tokens the node stores at that time. Initialized with an arbitrary load distribution of the tokens, in each time step, an edge of the graph is randomly selected, and the two endpoint nodes exchange tokens such that their loads are balanced as evenly as possible. A balance is the state where all nodes have nearly the same number of tokens. We prove that, with high probability, this process reaches an almost perfect balance after O(n log Delta + n(1)n(2) log n) steps, where n(1) and n(2) are the vertex number of the two independent sets in the bipartite graph, and Delta is the maximum initial load difference between two nodes. (C) 2021 Elsevier B.V. All rights reserved.

Automated summary

The study explores balancing indivisible tokens among nodes connected by a complete bipartite graph. Through a series of steps, the tokens between nodes are balanced. It is proven that the process can reach an almost perfect balance within a certain number of steps.