Revisiting Finite-Time Distributed Algorithms via Successive Nulling of Eigenvalues

Abstract

In this letter, we characterize the finite-time behavior on arbitrary undirected graphs. In particular, we derive distributed iterations that are a function of a linear operator on the underlying graph and show that any arbitrary initial condition can be forced to lie on a particular subspace in a finite time. This subspace can be chosen to have the same dimension as the algebraic multiplicity of any (arbitrarily chosen) eigenvalue of the underlying linear operator and is spanned by the eigenvectors corresponding to the chosen eigenvalue. In other words, finite-time behavior is completely characterized by the algebraic multiplicity of the eigenvalues and the corresponding eigenvectors of the underlying linear operator. We show that finite-time average-consensus can be cast naturally in this setup for which we further develop the necessary and sufficient conditions.