Synchronization of networks over finite fields

Abstract

In this paper, the synchronization problem for networks over finite fields is investigated, which is a generalization of consensus and provides a new perspective for networks of agents with limited capacities of memory and communication. It is assumed that the states and communication weights can only attain values from a finite alphabet equipped with a prime number of integers, termed finite fields, and operations are processed relying on modular arithmetic. For this synchronization problem, necessary and sufficient conditions are derived based on the transition graph of the studied network. The large number of nodes in the transition graph, dependent on the numbers of integers in finite fields and the agents, may lead to high computational cost and difficulties in verifying synchronization. To avoid this, an equivalent condition for synchronization of networks is provided by the characteristic polynomial of the studied network matrix. Furthermore, in a synchronized network over finite fields, the periodic behavior can be determined by the network matrix and the initial state.