Summary
This paper tackles the problem of how multiple agents can work together to allocate resources efficiently while communicating very little information. The authors propose a method where each agent only sends one bit of information per connection at each step, specifically the direction (sign) of their cost gradient. This approach guarantees that the total demand is always met and converges steadily towards a good solution without needing complex tuning. They show that their method greatly cuts communication costs in tasks like power distribution and server scheduling, trading off a small, controllable loss in optimality.
What this means in practice
- •For energy grid operators: Coordinate power generation from many plants while minimizing communication bandwidth to balance supply and demand efficiently.
- •For data center managers: Schedule computing jobs across hundreds of servers with minimal control communication, reducing overhead while keeping workload balanced.
Tested on simulated data.
Abstract
This paper proposes a distributed resource allocation algorithm in which each agent communicates only the sign of its local cost gradient, a single bit per directed link per iteration. The algorithm is based on Laplacian-gradient dynamics and preserves the equality (demand) constraint at every iterate, guaranteeing anytime feasibility irrespective of termination time. First, we provide a complete Lyapunov-based convergence analysis for the fixed-step-size regime: the iterates are shown to enter, in at most O(1/\varepsilon^2) iterations, a neighborhood of the optimizer whose radius scales as O(τ) in the decision variable and O(τ^2) in the cost residual, where $τ$ is the step-size. Crucially, the step-size bound is a time-invariant network constant (depending only on the graph Laplacian spectrum and the cost curvature bounds), so no adaptive tuning is required. Second, we characterize the invariant set under B-connected, weight-balanced digraphs, strictly weaker than the all-time connectivity and doubly-stochastic weights assumed in most prior work, and show that any odd, sign-preserving nonlinearity yields the same invariant-set and descent structure, with the single-bit protocol being the extreme communication-minimizing instance of a broader nonlinear class. Third, we address local box constraints via smooth penalty relaxation and quantify explicitly how the penalty weight interacts with the step-size bound and the optimality gap. Simulations on economic dispatch (1000 generators) and CPU scheduling (500 servers) demonstrate that the single-bit protocol achieves 5-60 times reduction in total communication cost relative to multi-bit baselines, at the price of a tunable and explicitly bounded optimality gap. A diminishing step-size schedule is shown empirically to eliminate this gap; its formal convergence analysis is identified as an open problem.