Saha, Arindam;
Marshall, James AR;
Reina, Andreagiovanni;
(2021)
Memory and communication efficient algorithm for decentralized counting of nodes in networks.
PLoS ONE
, 16
(11)
, Article e0259736. 10.1371/journal.pone.0259736.
Preview |
Text
Memory and communication efficient algorithm for decentralized counting of nodes in networks.pdf - Other Download (1MB) | Preview |
Abstract
Node counting on a graph is subject to some fundamental theoretical limitations, yet a solution to such problems is necessary in many applications of graph theory to real-world systems, such as collective robotics and distributed sensor networks. Thus several stochastic and naïve deterministic algorithms for distributed graph size estimation or calculation have been provided. Here we present a deterministic and distributed algorithm that allows every node of a connected graph to determine the graph size in finite time, if an upper bound on the graph size is provided. The algorithm consists in the iterative aggregation of information in local hubs which then broadcast it throughout the whole graph. The proposed node-counting algorithm is on average more efficient in terms of node memory and communication cost than its previous deterministic counterpart for node counting, and appears comparable or more efficient in terms of average-case time complexity. As well as node counting, the algorithm is more broadly applicable to problems such as summation over graphs, quorum sensing, and spontaneous hierarchy creation.
| Type: | Article |
|---|---|
| Title: | Memory and communication efficient algorithm for decentralized counting of nodes in networks |
| Location: | United States |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1371/journal.pone.0259736 |
| Publisher version: | http://dx.doi.org/10.1371/journal.pone.0259736 |
| Language: | English |
| Additional information: | Copyright © 2021 Saha et al. This is an open access article distributed under the terms of the Creative Commons Attribution License, https://creativecommons.org/licenses/by/4.0/, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited. |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences > Dept of Statistical Science |
| URI: | https://discovery-pp.ucl.ac.uk/id/eprint/10186581 |
Archive Staff Only
 |
View Item |
