Consensus and Synchronization of Multi-agent Systems over Finite Fields -- Graph Topologies

A new research paper from Kristian Hengster-Movrić and Šimon Lehký, funded by the EU's ROBOPROX project, tackles a fundamental challenge in distributed AI: designing communication networks for multi-agent systems where each agent has extremely limited memory. These agents operate over 'finite fields,' meaning they process only a finite set of symbols or states, unlike traditional systems with continuous or large state spaces. The core problem is constructing an 'admissible communication topology'—figuring out which agents should talk to whom to achieve consensus or synchronization. This combinatorial problem is notoriously NP-hard, making it computationally intractable for large systems using brute-force methods.

The researchers' key contribution is proposing two novel algorithms that efficiently explore subsets of possible connection matrices to generate viable network topologies. By moving from a search through all possibilities to a more targeted exploration, they provide a practical path forward. The paper considers both simple 'single-integrator' consensus problems and synchronization of more complex Linear Time-Invariant (LTI) systems. Simulations validate that their algorithmic approach works, demonstrating that systems built this way are 'remarkably resilient to communication noise,' a critical advantage for real-world deployment where packet loss or signal interference is common.