The computation of electrical flows is a crucial primitive for many recently proposed optimization algorithms on weighted networks. While typically implemented as a centralized subroutine, the ability to perform this task in a fully decentralized way is implicit in a number of biological systems. Thus, a natural question is whether this task can provably be accomplished in an efficient way by a network of agents executing a simple protocol. We provide a positive answer, proposing two distributed approaches to electrical flow computation on a weighted network: a deterministic process mimicking Jacobi's iterative method for solving linear systems, and a randomized token diffusion process, based on revisiting a classical random walk process on a graph with an absorbing node. We show that both processes converge to a solution of Kirchhoff's node potential equations, derive bounds on their convergence rates in terms of the weights of the network, and analyze their time and message complexity.
2018, Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS, Pages 1576-1584 (volume: 3)
Pooling or sampling: Collective dynamics for electrical flow estimation (04b Atto di convegno in volume)
Becchetti Luca, Bonifaci Vincenzo, Natale Emanuele
Gruppo di ricerca: Algorithms and Data Science