We study a general framework for broadcast gossip algorithms which use companion variables to solve the average consensus problem. Each node maintains an initial state and a companion variable. Iterative updates are performed asynchronously whereby one random node broadcasts its current state and companion variable and all other nodes receiving the broadcast update their state and companion variable. We provide conditions under which this scheme is guaranteed to converge to a consensus solution, where all nodes have the same limiting values, on any strongly connected directed graph. Under stronger conditions, which are reasonable when the underlying communication graph is undirected, we guarantee that the consensus value is equal to the average, both in expectation and in the mean-squared sense. Our analysis uses tools from non-negative matrix theory and perturbation theory. The perturbation results rely on a parameter being sufficiently small. We characterize the allowable upper bound as well as the optimal setting for the perturbation parameter as a function of the network topology, and this allows us to characterize the worst-case rate of convergence. Simulations illustrate that, in comparison to existing broadcast gossip algorithms, the approaches proposed in this paper have the advantage that they simultaneously can be guaranteed to converge to the average consensus and they converge in a small number of broadcasts.
Recent work of Cai and Ishii @cite_11 @cite_19 analyzes related distributed averaging algorithms on directed graphs that use companion variables. The two types of algorithms analyzed in @cite_11 @cite_19 involve asynchronous pairwise updates and synchronous updates. They make use of tools from matrix perturbation theory, and the work in the present article can be seen as generalizing the results in @cite_11 @cite_19 for broadcast gossip updates.
@cite_19 @cite_11
2084044206 2069512951
We study the average consensus problem of multi-agent systems for general network topologies with unidirectional information flow. We propose two linear distributed algorithms, deterministic and gossip, respectively for the cases where the inter-agent communication is synchronous and asynchronous. In both cases, the developed algorithms guarantee state averaging on arbitrary strongly connected digraphs; in particular, this graphical condition does not require that the network be balanced or symmetric, thereby extending previous results in the literature. The key novelty of our approach is to augment an additional variable for each agent, called "surplus", whose function is to locally record individual state updates. For convergence analysis, we employ graph-theoretic and nonnegative matrix tools, plus the eigenvalue perturbation theory playing a crucial role. We study the average consensus problem of multiagent systems for general network topologies with unidirectional information flow. We propose a linear distributed algorithm which guarantees state averaging on arbitrary strongly connected digraphs. In particular, this graphical condition does not require that the network be balanced or symmetric, thereby extending the previous results in the literature. The novelty of our approach is the augmentation of an additional variable for each agent, called “surplus”, whose function is to locally record individual state updates. For convergence analysis, we employ graph-theoretic and nonnegative matrix tools, with the eigenvalue perturbation theory playing a crucial role.