Abstract
We consider a multi-agent system where each agent has its own estimate of a given quantity and the goal is to reach consensus on the average. To this purpose, we propose a distributed consensus algorithm that guarantees convergence to the average in a finite number of iterations. The algorithm is tailored to ring networks with bidirectional pairwise communications. If the number of agents $m$ is even, say $m=2n$, then, the number of iterations needed is equal to $n$, which in this case is the diameter of the network, whereas the number of iterations grows to $3n$ if the number of agents is odd and equal to $m=2n+1$.
Introduction: The Distributed Averaging Problem
In multi-agent systems—such as sensor networks or robotic swarms—agents often need to reach an agreement on a specific value, typically the average of their individual measurements. This is known as the distributed averaging problem.
Traditional solutions, such as standard gossip algorithms or linear iterations, are generally asymptotic. While agents approach the true average over time, they never reach it exactly in a finite number of steps. Existing finite-time algorithms often suffer from high memory requirements or necessitate global knowledge of the network topology. This paper addresses these challenges specifically for ring networks, where each agent is connected to exactly two neighbors, under a gossip constraint (one-to-one communication).
Methodology
The proposed approach diverges based on the parity of the number of agents ($m$).
The Even Case ($m = 2n$)
For networks with an even number of agents, the authors introduce an algorithm utilizing time-varying weights ($\alpha_k$). Instead of a static mixing weight, the weights evolve at each iteration $k$: $$\alpha_k = \frac{k}{k+1}$$ Agents alternate communication between their clockwise and counter-clockwise neighbors. This structured scheduling allows information to propagate and merge perfectly across the ring. The algorithm terminates in exactly $n$ steps, matching the network's diameter.
The Odd Case ($m = 2n + 1$)
Odd-numbered rings present a challenge due to their lack of bipartite symmetry. To overcome this, the authors employ a "virtual" transformation. Each physical agent is treated as two "subagents" connected by a virtual link.
This transformation effectively doubles the agent count to $2m$ (an even number), allowing the application of the even-case logic. While "virtual" communication is a local computation, "actual" communication occurs over the physical links. This method ensures convergence in $3n$ iterations.
Key Insights and Results
- Optimal Convergence: For even rings, the algorithm reaches consensus in $n$ iterations. As $n$ is the network diameter, this represents the absolute physical lower bound for information propagation.
- Memory Efficiency: Unlike other finite-time methods that require storing multiple previous states, this algorithm only requires agents to store their current estimate. The memory footprint remains constant regardless of network size.
- Exact Consensus: By employing time-varying weights, the algorithm avoids the residual errors common in asymptotic methods, achieving the exact global average.
Conclusion and Future Work
The algorithm provides a highly efficient, finite-time solution for distributed averaging in ring networks. While currently optimized for rings, any connected graph can theoretically be reduced to a ring via a spanning cycle, though this may impact convergence speed. Future research will focus on extending these principles to asynchronous systems and more complex, non-ring topologies.
Summary updated