The Influence of Memory in Multi-Agent Consensus

David Kohan Marzagão, Luciana Basualdo Bonatto, Tiago Madeira, Marcelo Matheus Gauy, Peter McBurneyAAAI 2021 · DOI

Introduction

In distributed systems and swarm robotics, achieving global consensus through local interactions is a fundamental challenge. Traditional models, such as the Voter Model, are typically "memoryless," meaning agents update their states based solely on the current observations of their neighbors. While elegant, these models often suffer from structural deadlocks and slow convergence rates on specific network topologies.

A recent study presented at AAAI-21, "The Influence of Memory in Multi-Agent Consensus," introduces a novel framework that incorporates memory into consensus protocols. By allowing agents to occasionally adopt the past states of their neighbors, the researchers demonstrate that systems can not only avoid infinite oscillations but also achieve consensus significantly faster.

The Problem: Deadlocks and Inefficiency

Memoryless consensus protocols face two primary hurdles:

  1. Topological Deadlocks: In certain structures, such as even-length cycles, the system can enter a state of permanent oscillation where consensus is never reached.
  2. Slow Convergence: On many common networks, the time required for a single opinion to dominate the entire group can be prohibitively long due to the "random walk" nature of state transitions.

Methodology: The m-Memory Graph

To address these issues, the authors proposed the $m$-memory consensus protocol. In this model, at each time step $t$, an agent selects a previous time step $k \in \{t-m, \dots, t\}$ with probability $p_k$ and adopts the state of a randomly chosen neighbor from that time.

To analyze this process, the researchers developed the $m$-Memory Graph construction. This theoretical tool transforms a process with memory into an equivalent memoryless process on a larger, layered graph. Each layer represents a different time step in the agents' memory, allowing the application of standard Markov chain analysis to determine convergence properties.

The m-Memory Graph construction transforms a complex memory-based process into a layered, memoryless graph for easier analysis.

The study evaluated this protocol across five synthetic graph benchmarks: cliques (fully connected), cycles, bicliques (complete bipartite graphs), grids (2D torus), and binary trees.

Key Insights

  • Guaranteed Convergence: The introduction of any amount of memory ($m > 0$) ensures that the system is "well-behaved," mathematically guaranteeing that consensus will eventually be reached, even on topologies where memoryless systems fail.
  • Breaking Oscillations: Memory is particularly effective on graphs that are "close to bipartite," such as bicliques and cycles. In these structures, opinions often oscillate between partitions; memory acts as a dampening mechanism that breaks these cycles.
  • Outcome Neutrality: For "early memory processes," the probability of a specific opinion winning remains unchanged compared to the memoryless version. Memory improves the efficiency of the process without biasing the final outcome.

Results: Massive Speedups and Scalability

The most striking result is the magnitude of speedup achieved on specific topologies. On biclique graphs, the 1-memory process reached consensus approximately 100 times faster than the memoryless baseline, corresponding to a speedup ratio $\tau \approx 0.01$.

The speedup ratio $\tau$ across different topologies as a function of the number of nodes $n$. Lower values indicate greater speedup from memory.

As shown in the experimental results, the benefits of memory are highly dependent on the network topology. While bicliques and cycles see dramatic improvements, more "compact" structures like cliques and binary trees show minimal gains. Furthermore, these performance benefits are robust and stabilize as the network size $n$ increases, typically reaching a steady state around 800 nodes.

Conclusion

The research demonstrates that memory is a powerful, decentralized tool for enhancing multi-agent consensus. By breaking structural oscillations, memory-based protocols offer a scalable solution for faster and more reliable agreement in complex networks. Future work will explore deeper memory buffers and the application of these principles to more complex decision rules like the Majority Rule.

For implementation details, the authors' code is available on GitHub.

Summary updated

BibTeX
@inproceedings{marzagao2021influence,
  author = {David Kohan Marzagão and Luciana Basualdo Bonatto and Tiago Madeira and Marcelo Matheus Gauy and Peter McBurney},
  title = {{The Influence of Memory in Multi-Agent Consensus}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i13.17342},
}
Figure