Graph-based ball allocation rules have inherent load imbalance limits
Local decisions, diffusive influence, and lower bounds for graphical balanced allocation
Data Structures and Algorithms
Summary
This paper studies a way to distribute balls into buckets connected by a network, where each ball can only choose between two linked buckets. The authors prove there are fundamental limits on how evenly the balls can be spread when decisions depend only on local information at each link. They show that on simple networks like cycles, the difference between the fullest and emptiest bucket cannot be made very small using these local rules. This contrasts with strategies that use global knowledge, which can achieve much better balance.
What this means in practice
- •For network schedulers: Recognize that local decision rules for task assignment on network links inherently produce significant load imbalances, informing scheduling design choices.
- •For distributed systems engineers: Understand limits of local allocation schemes to avoid overly optimistic load balancing expectations in distributed systems relying on neighbor information.
A theory result. No direct application yet.
Authors
Obinna Okechukwu
Abstract
In graphical two-choice allocation, each arriving ball is assigned to one endpoint of a random edge. We study rules whose decision is a monotone function of the two endpoint loads, allowing edge-dependent thresholds and fresh randomization. Such a rule has an exact unit-discrepancy coupling: adding one ball to the initial state produces one tagged discrepancy at every later time. We represent the tag by conditional-expectation projections on the marked edge space and obtain diffusive displacement bounds. A transport-volume inequality then converts slow propagation of influence into lower bounds for the load gap. On the cycle with $n$ vertices, from every initial distribution and at every physical time $t\ge 1/n$, the expected gap is at least a constant times $\min\{\sqrt n,t^{1/4}\}$, and the gap exceeds this scale with probability at least $1/8$. After exactly $k\ge1$ allocations, the corresponding scale is $\min\{\sqrt n,(k/n)^{1/4}\}$. No stationarity, symmetry, recurrence, or moment assumption is used. The general inequality also yields a lower bound of order $\sqrt{L/K+\log K}$ on the $L\times K$ discrete torus $C_L\square C_K$. These results separate endpoint-local rules from global-information strategies that achieve polylogarithmic gaps on cycles.