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

Kristian Hengster-Movrić, Šimon Lehký, Farnaz Adib Yaghmaie · 2026

Read Consensus and Synchronization of Multi-agent Systems over Finite Fields - Graph Topologies by Kristian Hengster-Movrić, Šimon Lehký, Farnaz Adib Yaghmaie (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-14205.txt.

Introduction

Hengster-Movrić, Lehký, and Yaghmaie design cooperative protocols for multi-agent systems whose agents hold only finite states. Both scalar single-integrator consensus and general linear time-invariant synchronization come under study. Finite-state agents, with tiny memory reading a finite alphabet, resist communication noise well, but building an admissible communication topology is NP-hard. The authors explore subsets of admissible graph matrices and offer two new algorithms to build them, with simulations backing the approach.

Catalog record

CREATORKristian Hengster-Movrić, Šimon Lehký, Farnaz Adib Yaghmaie
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE42817
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.14205

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Consensus and Synchronization of Multi-agent Systems over Finite Fields - Graph Topologies Kristian Hengster-Movrić, Šimon Lehký, Farnaz Adib Yaghmaie Abstract This paper brings cooperative protocols for multi-agent systems with agents having a finite state-space. Both scalar single-integrator consensus and general LTI systems synchronization are considered. Systems having a finite state-space describe agents with minimal memory capacity processing only a finite alphabet. Such systems are remarkably resilient to communication noise. The crucial problem, however, is to construct the admissible communication topology, which is NP-hard. We address this by efficiently exploring the subsets of admissible matrices and propose two new algorithms to generate the topologies. Simulations validate the proposed approach. I Introduction and Notation Multi-agent systems consisting of agents with minimal memory capacity, processing only values from a finite alphabet, are becoming increasingly interesting due to the emerging IoT coding requirements for secure communication over digital networks, [ 5 ] , capacity and memory constrained sensor networks and for describing discretized orientations of rigid bodies, [ 13 ] , to name just a few compelling applications. Consensus of real scalar single-integrator agents over nonnegative real edge-weight graphs has been long studied from multiple perspectives. Fundamental results on the graph topology necessary for consensus of single-integrators were extended to synchronization of general linear time-invariant (LTI) agents over the same underlying graphs. Spanning tree subgraph is found to be the minimal necessary requirement for cooperative synchronization of dynamical systems evolving in continuous-time and discrete-time, on finite-dimensional vector spaces over continuum fields of real or complex numbers. Extensions of consensus and synchronization protocols to signed real edge-weight graphs, [ 2 , 16 ] and complex edge-weight graphs, [ 11 , 6 ] , both for single-integrator and general LTI agents followed thereafter, [ 15 , 1 ] . Modular systems and finite-state automata, also referred to as sequential machines [ 4 ] , are likewise studied for a long time, [ 7 , 8 , 9 ] . Theory exists for LTI sequential modular systems evolving in discrete-time steps on finite-dimensional vector spaces over finite ( Galois ) fields, Hamming spaces ; frequency domain Z -transformation transfer function analysis, formally the same as for conventional discrete-time systems over fields of real and complex numbers, is useful there as well [ 8 , 9 , 4 ] , as are the polynomial-based approaches, [ 8 , 9 ] . Nevertheless, cooperative synchronization of such systems over graphs with finite-field edge-weights has not been hitherto systematically investigated in a satisfactorily unified framework, although [ 13 ] makes crucial first steps in that direction, while [ 14 , 12 ] propose extensions to more general single-agents and [ 10 ] even addresses time-delays. This paper develops an analysis and design methodology for consensus of identical LTI sequential modular systems, following the spirit of the conventional synchronizing region approach. For an LTI system that is finite-field stabilizable, we show that the unique stabilizing controller gain is obtained directly and transparently from either the controllable canonical form or the Kalman decomposition of the single-agent dynamics. Thus, the essential challenge is not the controller design itself, but rather the identification of admissible communication structures, (graph topologies and edge weights), that render a cooperatively stabilizing control feasible. The finite-field admissible graph topology problem is identified in [ 13 ] as NP-hard. In this work, we demonstrate that the design of admissible communication structures for synchronization is completely independent of the single-agent characteristics. This decoupling allows one to address graph design separately from single-agent controller synthesis. The contributions of this paper are twofold. First, we develop a unified analysis and design framework for state consensus and synchronization of modular multi-agent systems. In contrast to [ 13 ] , which considers only single-integrator dynamics, we address general identical LTI agents. This also generalizes the results of [ 12 ] , which considers single-agent dynamics of a special form. Moreover, in contrast to [ 14 ] , we do not restrict graphs to be directed acyclic (DAG), nor do we require the equality of all in-degrees, but allow for all finite-field admissible graph topologies. Second, we propose efficient algorithms for generating admissible graph topologies that guarantee modular consensus, and we analyze their computational complexity. To the best of our knowledge, these results have not been previously reported. The paper is organized as follows: Section I brings the introduction and preliminaries on finite fields, graphs and notation. Section II introduces the scalar single-integrator consensus, while Section III considers general finite-field LTI agents. Section IV elucidates the structures to be explored, Section V brings the efficient search algorithms, Section VI gives a numerical example, Section VII concludes the paper. I-A Finite Field \mathbb{F}_{p} A finite field \mathbb{F}_{p} consists of the set of elements \{0,\>1,...,p-1\} with addition and multiplication operations defined. In particular, we denote the finite field of integers modulo p by \mathbb{Z}_{p} . Throughout, we assume that p is a prime number so that \mathbb{Z}_{p} forms a field and contains no zero divisors. All algebraic operations in this paper are performed modulo p . For a matrix T\in\mathbb{F}_{p}^{m\times n} , the entry in the i -th row and j -th column is written as [T]_{ij}\in\mathbb{F}_{p} . The i -th row ( j -th column) of a matrix T is denoted by [T]_{i,:} ( [T]_{:,j} ). The transpose of matrix T is denoted by T^{\top} . Let T\in\mathbb{F}_{p}^{s\times s} be an s\times s matrix. The trace of T is defined as \operatorname{Tr}(T)=\sum\nolimits_{i=1}^{s}[T]_{ii}\in\mathbb{F}_{p}, and the determinant of T is denoted by \det(T) where all additions and multiplications are performed modulo p . Equivalently, T is invertible over \mathbb{F}_{p} if and only if \det(T)\neq 0 in \mathbb{F}_{p} . For an invertible matrix T and any matrix A , the matrix T^{-1}AT is similar to A , T^{-1}AT\sim A . I_{N} denotes an N\times N identity matrix with ones on the diagonal. A vector of ones with appropriate dimension is denoted by \mathbf{1}=(1,1,\dots,1)^{\top} , or \mathbf{1}_{N} when the dimension is of concern. Similarly, \mathbf{0}=(0,0,\dots,0)^{\top} or \mathbf{0}_{N} denote a vector of zeros. Let e_{i} denote the i -th basis vector of \mathbb{F}_{p}^{n} whose entries are all zero except for the i -th entry, which is equal to one. I-B Graphs with Finite-field Edge-weights For a graph \mathcal{G}(\mathcal{V},\mathcal{E},E) , having |\mathcal{V}|=N and |\mathcal{E}|=M , with finite-field edge-weights, the adjacency matrix E\in\mathbb{F}_{p}^{N\times N} , with elements e_{ij} , is an N\times N matrix with finite-field entries; e_{ij}\in\mathbb{F}_{p},e_{ij}\neq 0 if (i,j)\in\mathcal{E} and e_{ij}=0 if (i,j)\notin\mathcal{E} . Conversely, any N\times N matrix with finite-field entries induces a graph \mathcal{G}(\mathcal{V},\mathcal{E},E) with finite-field edge-weights. If there exists a node emanating directed paths to all other nodes in the graph, the graph contains a spanning tree subgraph, and each such globally influential node is a possible root of a spanning tree. II Scalar Single-Integrator Modular Consensus Consider a multi-agent system comprised of N agents with state dynamics x_{i}(k+1)=\sum\nolimits_{j}e_{ij}x_{j}(k),\quad x_{i}\in\mathbb{F}_{p},\qquad i=1,\dots,N, (1) where possibly e_{ii}\neq 0 . In global form, ( 1 ) reads x(k+1)=Ex(k)\in\mathbb{F}_{p}^{N},\quad E\in\mathbb{F}_{p}^{N\times N}. (2) Theorem 1 Let E be nilpotent with the characteristic polynomial P_{E}(\lambda)=\lambda^{N} , or let E be row-stochastic, E\mathbf{1}_{N}=\mathbf{1}_{N} , with the characteristic polynomial P_{E}(\lambda)=(\lambda-1)\lambda^{N-1} and left eigenvector p^{\top}\in\mathbb{F}_{p}^{N},p^{\top}E=p^{\top} , pertaining to the simple eigenvalue 1 , satisfying p^{\top}\mathbf{1}_{N}\neq 0 . Then

Read the complete text