⚡ electrical engineering

Accelerated consensus in multi-agent networks via memory of local averages

This paper proposes a modified multi-agent consensus model that applies the DeGroot update to both current and previous states before combining them, demonstrating that this approach enables convergence in periodic networks and achieves faster convergence rates than classical DeGroot and prior accelerated averaging models.

Original authors: Aditya Bhaskar, Shriya Rangarajan, Vikram Shree, Mark Campbell, Francesca Parise

Published 2026-07-22

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Aditya Bhaskar, Shriya Rangarajan, Vikram Shree, Mark Campbell, Francesca Parise

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a group of friends trying to decide where to eat dinner. They are all in different rooms, but they can only talk to the people standing right next to them. If everyone just listens to their immediate neighbors and averages out their suggestions, they might eventually agree, but it could take a very long time. Worse, if the friends are arranged in a perfect circle where everyone only talks to the person on their left, they might get stuck in an endless loop of changing their minds back and forth, never actually agreeing. This is the world of "multi-agent networks," a field of science that studies how groups of independent units—whether they are robots, sensors, or people—share information to reach a common decision. The classic way to model this is the "DeGroot model," where everyone simply takes a weighted average of what their neighbors say right now. While this works for many situations, it has a frustrating flaw: in certain network shapes, like that perfect circle, the group can get stuck in a permanent dance of disagreement, oscillating forever without ever settling on a final answer.

This paper introduces a clever twist to that old recipe to fix the dancing problem and speed up the decision-making process. The authors, Aditya Bhaskar and colleagues, propose a new method called the "Memory of Local Averages" (MLA) model. Instead of just listening to what neighbors say right now, the agents in the network also remember what they calculated last time. Think of it like a group of friends who, before making a new suggestion, don't just look at their neighbor's current idea, but also recall what their neighbor suggested in the previous round. By mixing these two pieces of information—the fresh news and the old news—in a specific way, the group can break out of those endless loops and reach an agreement much faster. The paper proves mathematically that this simple memory trick allows the network to reach a consensus even in those tricky, circular arrangements where the old methods fail, and it shows through simulations that for many networks, this new approach gets everyone on the same page significantly quicker than before.

The Problem: The Endless Dance

In the world of networked agents, the goal is often "consensus," where everyone ends up with the same value, usually the average of their starting points. The standard way to do this is the DeGroot model. Imagine a line of people passing a note. Each person looks at the notes they received from their neighbors, averages them, and writes a new note. If the network is a simple, messy web, this works fine. But if the network is a perfect ring (like a circle of friends where everyone only talks to the person on their left), the DeGroot model hits a snag. The values can start oscillating: Person A says "Yes," Person B says "No," Person A says "No," Person B says "Yes," and they never stop. It's like a pendulum that never settles.

A previous attempt to fix this, called "accelerated averaging," tried to help by having agents mix their current average with their previous state. It was like telling the friends, "Take your neighbor's current idea, average it, and then mix that result with your own vote from last time." This helped speed things up in some cases, but the authors found that in those stubborn, circular networks, this method still failed to stop the oscillation. The group would still get stuck in the dance.

The Solution: Remembering the Average

The authors propose a different strategy. In their new MLA model, the agents don't just mix their current state with their past state. Instead, they first calculate the "local average" (what they would have said using the old DeGroot rule) for both the current moment and the previous moment. Then, they mix those two averages together.

To use an analogy: Imagine a committee trying to decide on a color.

DeGroot Model: Everyone looks at their neighbors' current votes, averages them, and writes down a new vote.
Old Accelerated Model: Everyone looks at their neighbors' current votes, averages them, and then mixes that result with their own vote from last time.
MLA Model (The New Idea): Everyone looks at their neighbors' current votes and averages them. Then, they look at what they calculated last time (the average of their neighbors' votes from last time) and average those two numbers together.

This subtle shift in what is being remembered and mixed turns out to be a game-changer.

The Findings: Breaking the Loop and Speeding Up

The paper uses rigorous math to show two main things. First, for networks that are "periodic" (like that perfect ring where the DeGroot and old accelerated models get stuck in an infinite loop), the MLA model actually works. It proves that by choosing the right mixing parameter (called $\gamma$ ), the oscillations die down, and the group reaches a steady agreement. The authors show that as long as the mixing parameter is between 0 and 2 (and satisfies a specific condition related to the network's structure), the system will converge. This is a big deal because it means the network can agree even in shapes that were previously considered impossible for these linear methods.

Second, the paper investigates how fast the group reaches agreement. They compare the MLA model against the DeGroot model and the old accelerated model. Using a concept called the "essential spectral radius" (which is basically a measure of how fast the errors shrink), they show that for many networks, the MLA model shrinks those errors much faster. In their simulations, they tested a ring network with four nodes. When they started with 1,000 different random starting points, the DeGroot and old accelerated models kept oscillating forever. The MLA model, however, settled down to a single, stable answer.

Furthermore, the authors found a "sweet spot" for the mixing parameter $\gamma$ . If you tune this number just right, the MLA model can converge significantly faster than both the classic DeGroot model and the previous accelerated model. They demonstrated this with a specific example: a ring network where a few tiny "self-loops" (connections to oneself) were added. In this setup, the MLA model reached consensus much more quickly than the others.

The Bottom Line

This paper doesn't just suggest a tweak; it provides a mathematical proof that this new "Memory of Local Averages" approach works where others fail. It shows that by changing how agents use their memory—specifically by averaging the averages rather than just mixing states with memories—we can solve the problem of endless oscillation in circular networks. While the math is complex, the core idea is simple: sometimes, to move forward faster, you need to look at where you've been, not just where you are. The authors suggest that this method could be a powerful tool for designing better communication systems for robots, sensors, and other distributed networks, especially in situations where the network structure is rigid or prone to getting stuck.

Technical Summary: Accelerated Consensus in Multi-Agent Networks via Memory of Local Averages

Problem Statement
In multi-agent networks, distributed averaging algorithms are essential for reaching global consensus through local computations. The classical DeGroot model updates an agent's state as a weighted average of its neighbors' current states. While effective for many networks, the DeGroot model suffers from slow convergence rates and, critically, fails to converge in periodic networks (where agents oscillate indefinitely). Previous work by Muthukrishnan et al. proposed an "accelerated averaging" model that incorporates memory by performing a DeGroot update on the current state and then linearly combining it with the previous state. However, this prior model also fails to converge in periodic networks. This paper addresses the limitations of both models by proposing a modification that leverages memory of local averages to achieve convergence in periodic networks and accelerate convergence rates in aperiodic ones.

Methodology
The authors propose the Memory of Local Averages (MLA) model. Unlike the prior accelerated model which updates the current state via DeGroot and then mixes it with the past state, the MLA model applies the DeGroot update to both the current state $x(k)$ and the previous state $x(k-1)$ to generate intermediate states $z(k)$ and $z(k-1)$ . The final state $x(k+1)$ is then a linear combination of these two intermediate states:
$x(k+1) = \gamma A x(k) + (1-\gamma) A x(k-1)$
where $A$ is the row-stochastic weighted adjacency matrix and $\gamma$ is a weighting parameter.

To analyze convergence, the authors formulate an augmented system with state $\hat{x}(k) = [x(k); x(k-1)]^T$ and an augmented iteration matrix $\hat{A}$ . They perform a spectral analysis of $\hat{A}$ , deriving the relationship between the eigenvalues of the original matrix $A$ ( $\lambda$ ) and the augmented matrix $\hat{A}$ ( $\hat{\lambda}$ ). The convergence properties are determined by the spectral radius of $\hat{A}$ , specifically ensuring that all eigenvalues except the dominant one (equal to 1) lie strictly within the unit disk.

Key Contributions and Results

Convergence in Periodic Networks:
The paper establishes that the MLA model can achieve consensus in undirected, connected, and periodic networks, a scenario where both the DeGroot model and the Muthukrishnan et al. accelerated model fail (resulting in persistent oscillations).
- Theorem 3 provides necessary and sufficient conditions for semi-convergence: $\gamma \in (0, 2)$ and $2\gamma\lambda_n - \lambda_n + 1 > 0$ , where $\lambda_n$ is the smallest eigenvalue of $A$ .
- For periodic networks, $\lambda_n = -1$ . The MLA model converges if $\gamma \in (0, 1)$ , whereas the prior accelerated model is proven (Lemma 5) to diverge for any initial condition aligned with the eigenvector of $\lambda_n = -1$ .
Accelerated Convergence in Aperiodic Networks:
For networks where all three models converge (primitive, symmetric, row-stochastic matrices), the authors identify conditions under which MLA offers faster convergence.
- Comparison with DeGroot: Lemma 7 shows that if $\lambda_2 + \lambda_n \neq 0$ , there exists a $\gamma$ such that the essential spectral radius of the MLA model is strictly smaller than that of the DeGroot model, implying faster convergence.
- Comparison with Accelerated Averaging: Theorem 8 derives an optimal parameter $\gamma^*$ that minimizes the essential spectral radius of the MLA model. Under the condition $\lambda_2 \le |\lambda_n|/3$ and $\lambda_n < 0$ , the MLA model achieves a convergence rate of $\rho_{ess}(\hat{A}) = \sqrt{1+\rho_{ess}(A)} - 1$ . This rate is proven to be strictly faster than both the DeGroot model and the optimally tuned accelerated averaging model.
Consensus Value:
Lemma 6 demonstrates that when convergence criteria are met, the MLA model converges to the same consensus value as the DeGroot model (the weighted average of initial states defined by the left dominant eigenvector of $A$ ), provided the initial conditions are consistent ( $x(0) = x(-1)$ ).

Significance
The paper claims that the MLA model represents a simple yet powerful modification to existing linear consensus schemes. Its primary significance lies in two areas:

Robustness: It extends the applicability of linear averaging algorithms to periodic networks without requiring non-linear updates or finite-time consensus schemes, which often carry higher computational burdens.
Efficiency: It provides a mechanism to accelerate convergence in standard networks by optimizing the memory parameter $\gamma$ , outperforming both the classical DeGroot approach and the previously proposed accelerated averaging method.

The authors note that their work retains the linearity of the update equations, allowing for analysis via linear algebra and Markov chains, distinguishing it from non-linear finite-time consensus approaches. The results are validated through spectral analysis and numerical simulations on ring networks, including perturbed periodic networks where the MLA model demonstrates superior performance. Future work is suggested to extend these results to asymmetric matrices.

The Problem: The Endless Dance

The Solution: Remembering the Average

The Findings: Breaking the Loop and Speeding Up

The Bottom Line

Technical Summary: Accelerated Consensus in Multi-Agent Networks via Memory of Local Averages

More like this