Can I read Pooling or Sampling: Collective Dynamics for Electrical Flow Estimation on EtoBox?

Pooling or Sampling: Collective Dynamics for Electrical Flow Estimation by Becchetti, Luca; Bonifaci, Vincenzo; Natale, Emanuele is a scholarly article available to read on EtoBox.

What is Pooling or Sampling: Collective Dynamics for Electrical Flow Estimation about?

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.

Author

Becchetti, Luca; Bonifaci, Vincenzo; Natale, Emanuele

Published

2018

Language

EN