Back to Search
Start Over
Pooling or sampling: Collective dynamics for electrical flow estimation
- Source :
- Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, 3 (2018): 1576–1584., info:cnr-pdr/source/autori:Becchetti L.; Bonifaci V.; Natale E./titolo:Pooling or sampling: Collective dynamics for electrical flow estimation/doi:/rivista:Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems (Print)/anno:2018/pagina_da:1576/pagina_a:1584/intervallo_pagine:1576–1584/volume:3, Scopus-Elsevier, Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS '18), Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS '18), Jul 2018, Stockholm, Sweden. ⟨10.5555/3237383.3237935⟩
- Publication Year :
- 2018
- Publisher :
- ACM Press, New York, N.Y. , Stati Uniti d'America, 2018.
-
Abstract
- International audience; 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.
- Subjects :
- Kirchhoff's equation
FOS: Computer and information sciences
Kirchhoff's equations
Jacobi's method
token diffusion
electrical flow
Computer Science - Distributed, Parallel, and Cluster Computing
Artificial Intelligence
Control and Systems Engineering
Electrical flow
Laplacian system
Token diffusion
Software
Kirchhoff equations
Distributed, Parallel, and Cluster Computing (cs.DC)
[INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
Jacobi method
Subjects
Details
- Language :
- English
- Database :
- OpenAIRE
- Journal :
- Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, 3 (2018): 1576–1584., info:cnr-pdr/source/autori:Becchetti L.; Bonifaci V.; Natale E./titolo:Pooling or sampling: Collective dynamics for electrical flow estimation/doi:/rivista:Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems (Print)/anno:2018/pagina_da:1576/pagina_a:1584/intervallo_pagine:1576–1584/volume:3, Scopus-Elsevier, Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS '18), Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS '18), Jul 2018, Stockholm, Sweden. ⟨10.5555/3237383.3237935⟩
- Accession number :
- edsair.doi.dedup.....677c59cd120cbbebda822282cbf59121