Benefit of Random-Local Updates in Networks (Load Balancing)

Abstract

This thesis studies the discrete load balancing problem on graphs in both static and dynamic settings. In discrete load balancing, a graph G=(V,E) is given, and each node initially holds an integer number of load tasks (tokens). At each step, nodes apply the same balancing rule, and a task cannot be divided. In the static setting, no new tasks are added, whereas in the dynamic setting, a fixed number of tasks are generated and distributed uniformly at random to the nodes at the start of each round. The goal is to make the loads across all nodes approximately equal. We focus on two main models: the matching model, where each node interacts with at most one neighbour per round, and the diffusion model, where each node interacts with all its neighbours in each round.

We propose and analyse simple local balancing rules, which use randomisation. In the matching model, two matched nodes take the average of their loads. If the sum of their loads is odd, the node that receives the one excess token is selected at random. In the diffusion model, each node spreads its loads as evenly as possible among its neighbors and itself. Any extra tokens are distributed randomly and without replacement between itself and its neighbours.