Convergence Rates of Distributed Consensus over Cluster Networks: A Two-Time-Scale Approach

We study the popular distributed consensus method over networks composed of a number of densely connected clusters with a sparse connection between them. In these cluster networks, the method often constitutes two-time-scale dynamics, where the internal nodes within each cluster reach consensus quickly relative to the aggregate nodes across clusters. Our main contribution is to provide the rate of convergence of the distributed consensus method in a way that characterizes explicitly the impacts of the internal and external graphs on its performance. Our main result shows that the consensus method converges exponentially and only scales with a few number of nodes, which is relatively small to the size of the network. The key technique in our analysis is to consider a Lyapunov function that captures the impact of different time-scale dynamics on the convergence of the method. Our approach avoids using model reduction, which is the typical way according to singular perturbation theory and relies on relatively simple definitions of the slow and fast variables. We illustrate our theoretical results by a number of numerical simulations over different cluster networks.