Distributed two-time-scale methods over clustered networks

Abstract

In this paper, we consider consensus problems over a network of nodes, where the network is divided into a number of clusters. We are interested in the case where the communication topology within each cluster is dense as compared to the sparse communication across the clusters. Moreover, each cluster has one leader which can communicate with other leaders in different clusters. The goal of the nodes is to agree at some common value under the presence of communication delays across the clusters. Our main contribution is to propose a novel distributed two-time-scale consensus algorithm, which pertains to the separation in network topology of clustered networks. In particular, one scale is to model the dynamic of the agents in each cluster, which is much faster (due to the dense communication) than the scale describing the slowly aggregated evolution between the clusters (due to the sparse communication). We prove the convergence of the proposed method in the presence of uniform, but possibly arbitrarily large, communication delays between the leaders. In addition, we provided an explicit formula for the convergence rate of such algorithm, which characterizes the impact of delays and the network topology. Our results shows that after a transient time characterized by the topology of each cluster, the convergence of the two-time-scale consensus method only depends on the connectivity of the leaders. Finally, we validate our theoretical results by a number of numerical simulations on different clustered networks.

References in corpus (8)

• A Tutorial on Modeling and Analysis of Dynamic Social Networks. Part I
• Convergence rate of linear two-time-scale stochastic approximation
• Structural Controllability of Multi-Agent Networks: Robustness against Simultaneous Failures
• Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noise
• Finite-Time Performance Bounds and Adaptive Learning Rate Selection for Two Time-Scale Reinforcement Learning
• Distributed two-time-scale methods over clustered networks
• Distributed Stochastic Approximation for Solving Network Optimization Problems Under Random Quantization
• Finite-Time Performance of Distributed Two-Time-Scale Stochastic Approximation

Cited by in corpus (3)

• Distributed two-time-scale methods over clustered networks
• Finite-Time Convergence Rates of Nonlinear Two-Time-Scale Stochastic Approximation under Markovian Noise
• Convergence Rates of Decentralized Gradient Methods over Cluster Networks