Information dissemination in networks via linear iterative strategies over finite fields

Abstract

Given an arbitrary network of interconnected nodes, each with an initial value from a discrete set, we consider the problem of distributively disseminating these initial values under the constraint that the nodes can only process and communicate values in that set. To solve this problem, we treat the initial values as elements in a finite field and employ a linear iterative strategy, whereby at each time-step, each node in the network transmits a value that is a linear combination of its own value and the most recent transmissions of its neighbors. Our approach is an important (and non-trivial) extension of previous work on linear iterative strategies with real-valued transmissions and operations, and can find applications in networks that have communication or computational constraints. We show that if the weights for the linear iteration are chosen randomly (uniformly and independently) from a finite field of sufficiently large size, then with some nonzero probability, any node will be able to obtain the initial value of any other node. Furthermore, this can be accomplished after running the linear iteration for a finite number of time-steps (upper bounded by the number of nodes in the network). In the process of deriving our results, we develop a theory of structured observability for linear systems over finite fields. ©2009 IEEE.