Home » Publication » 13875

Dettaglio pubblicazione

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

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.
ISBN: 9781510868083
Gruppo di ricerca: Algorithms and Data Science
© Università degli Studi di Roma "La Sapienza" - Piazzale Aldo Moro 5, 00185 Roma