Randomized Gossiping With Effective Resistance Weights: Performance Guarantees and Applications

• Published in: IEEE transactions on control of network systems 2022-06, Vol.9 (2), p.524-536
• Main Authors: Can, Bugra, Soori, Saeed, Aybat, Necdet Serhat, Dehnavi, Maryam Mehri, Gurbuzbalaban, Mert
• Format: Article
• Language: English
• Subjects: Approximation algorithms; Control systems; Distributed algorithms; Distributed algorithms/control; Gossip; Graphs; Linear systems; Markov chains; Network systems; networks of autonomous agents; Optimization; randomized gossiping algorithms; Resistance; Topology; Upper bound; Upper bounds
• ISSN: 2325-5870; 2325-5870; 2372-2533
• DOI: 10.1109/TCNS.2022.3161201

The effective resistance (ER) between a pair of nodes in a weighted undirected graph is defined as the potential difference induced when a unit current is injected at one node and extracted from the other, treating edge weights as the conductance values of edges. The ER is a key quantity of interest in many applications, e.g., solving linear systems, Markov chains, and continuous-time averaging networks. In this article, we consider ERs in the context of designing randomized gossiping methods for the consensus problem, where the aim is to compute the average of node values in a distributed manner through iteratively computing weighted averages among randomly chosen neighbors. For barbell graphs, we prove that choosing wake-up and communication probabilities proportional to ER weights improves the averaging time corresponding to the traditional choice of uniform weights. For c-barbell graphs, we show that ER weights admit lower and upper bounds on the averaging time that improves upon the lower and upper bounds available for uniform weights. Furthermore, for graphs with a small diameter, we can show that ER weights can improve upon the existing bounds for Metropolis weights by a constant factor under some assumptions. We illustrate these results through numerical experiments, where we showcase the efficiency of our approach on several graph topologies, including barbell and small-world graphs. We also present an application of ER gossiping to distributed optimization: we numerically verify that using ER gossiping within EXTRA and DPGA-W methods improves their practical performance in terms of communication efficiency.