Memory and communication efficient algorithm for decentralized counting of nodes in networks.

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 algor...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Arindam Saha, James A R Marshall, Andreagiovanni Reina
Formato:	article
Lenguaje:	EN
Publicado:	Public Library of Science (PLoS) 2021
Materias:	Medicine R Science Q
Acceso en línea:	https://doaj.org/article/b588b1166feb4d3498d9280a7ad77f70
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:b588b1166feb4d3498d9280a7ad77f70
record_format	dspace
spelling	oai:doaj.org-article:b588b1166feb4d3498d9280a7ad77f702021-12-02T20:16:19ZMemory and communication efficient algorithm for decentralized counting of nodes in networks.1932-620310.1371/journal.pone.0259736https://doaj.org/article/b588b1166feb4d3498d9280a7ad77f702021-01-01T00:00:00Zhttps://doi.org/10.1371/journal.pone.0259736https://doaj.org/toc/1932-6203Node 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.Arindam SahaJames A R MarshallAndreagiovanni ReinaPublic Library of Science (PLoS)articleMedicineRScienceQENPLoS ONE, Vol 16, Iss 11, p e0259736 (2021)
institution	DOAJ
collection	DOAJ
language	EN
topic	Medicine R Science Q
spellingShingle	Medicine R Science Q Arindam Saha James A R Marshall Andreagiovanni Reina Memory and communication efficient algorithm for decentralized counting of nodes in networks.
description	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.
format	article
author	Arindam Saha James A R Marshall Andreagiovanni Reina
author_facet	Arindam Saha James A R Marshall Andreagiovanni Reina
author_sort	Arindam Saha
title	Memory and communication efficient algorithm for decentralized counting of nodes in networks.
title_short	Memory and communication efficient algorithm for decentralized counting of nodes in networks.
title_full	Memory and communication efficient algorithm for decentralized counting of nodes in networks.
title_fullStr	Memory and communication efficient algorithm for decentralized counting of nodes in networks.
title_full_unstemmed	Memory and communication efficient algorithm for decentralized counting of nodes in networks.
title_sort	memory and communication efficient algorithm for decentralized counting of nodes in networks.
publisher	Public Library of Science (PLoS)
publishDate	2021
url	https://doaj.org/article/b588b1166feb4d3498d9280a7ad77f70
work_keys_str_mv	AT arindamsaha memoryandcommunicationefficientalgorithmfordecentralizedcountingofnodesinnetworks AT jamesarmarshall memoryandcommunicationefficientalgorithmfordecentralizedcountingofnodesinnetworks AT andreagiovannireina memoryandcommunicationefficientalgorithmfordecentralizedcountingofnodesinnetworks
_version_	1718374489478135808

Memory and communication efficient algorithm for decentralized counting of nodes in networks.

Ejemplares similares