Abstract
The effective resistance (ER) between nodes in a weighted undirected graph is a critical quantity in fields ranging from linear systems to Markov chains. This research develops an efficient, linearly convergent distributed algorithm for computing ER and demonstrates its utility in accelerating distributed optimization. By weighting communication probabilities based on ER, we show that classical consensus iterations can be accelerated by a factor depending on the network structure, particularly in graphs with significant bottlenecks.
The Bottleneck Problem in Distributed Consensus
In distributed systems, agents often need to compute the average of their local values, a task known as the consensus problem. The standard approach is randomized gossiping, where nodes communicate with random neighbors. However, this method suffers from "bottlenecks"—edges that connect dense clusters but are rarely selected under uniform probability distributions.
As seen in the barbell graph above, a uniform random choice will rarely select the bridge edge. Consequently, the two clusters reach internal consensus quickly but take a very long time to synchronize with each other. This research addresses this by treating the network like an electrical circuit and weighting edges by their Effective Resistance.
Effective Resistance as a Weighting Strategy
If every edge in a graph is viewed as a resistor, the ER between two nodes is the voltage drop induced when a unit current is injected at one and extracted at the other. The authors leverage Foster’s Theorem—which states the sum of all ER weights in a graph is $n-1$—to create a robust, normalized probability distribution for node activation.
Key methodological steps include:
- ER-Based Gossiping: Activating communication with a probability proportional to the ER of the connecting edge.
- Spectral Analysis: Analyzing the spectral gap of the iteration matrix to prove faster convergence.
- Distributed Computation: Utilizing a Distributed Randomized Kaczmarz (D-RK) algorithm to allow nodes to estimate ER weights locally without global knowledge.
Performance on Complex Topologies
The paper evaluates these theories using synthetic graph topologies that represent common network challenges, such as the $c$-barbell graph.
On a standard barbell graph with $n$ nodes, ER-based gossiping is $\Theta(n)$ times faster than uniform gossiping, reducing averaging time from $O(n^3 \log(1/\epsilon))$ to $O(n^2 \log(1/\epsilon))$. The authors prove that for such graphs, ER gossiping is the optimal choice among all symmetric gossip matrices.
Applications in Distributed Optimization
Beyond simple averaging, the ER-based framework accelerates complex distributed optimization algorithms. By improving the underlying consensus step, the researchers demonstrated significant reductions in communication rounds for decentralized machine learning tasks, specifically within the EXTRA and DPGA-W frameworks. This synergy suggests that ER weights are a powerful "building block" for any decentralized algorithm relying on neighbor-to-neighbor information exchange.
Conclusion
While ER weights provide the most significant gains in bottlenecked or community-structured graphs, the development of a decentralized algorithm to compute these weights makes the approach practical for real-world sensor networks and autonomous systems. Future work aims to extend these benefits to directed graphs and dynamic networks where topology may change over time.
Summary updated