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.

Becchetti, L., Bonifaci, V., & Natale, E. (2018). Pooling or Sampling: Collective Dynamics for Electrical Flow Estimation. In Proc. of the 17th Int. Conf. on Autonomous Agents and MultiAgent Systems (pp.1576-1584). New York, NY : ASSOC COMPUTING MACHINERY.

Pooling or Sampling: Collective Dynamics for Electrical Flow Estimation

Bonifaci, V;
2018

Abstract

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.
978-1-4503-5649-7
Becchetti, L., Bonifaci, V., & Natale, E. (2018). Pooling or Sampling: Collective Dynamics for Electrical Flow Estimation. In Proc. of the 17th Int. Conf. on Autonomous Agents and MultiAgent Systems (pp.1576-1584). New York, NY : ASSOC COMPUTING MACHINERY.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11590/381922
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 3
social impact