Comparative Study of Distributed Consensus Gossip Algorithms for Network Size Estimation in Multi-Agent Systems

Martin Kenyeres and Jozef Kenyeres
Additional contact information
Martin Kenyeres: Institute of Informatics, Slovak Academy of Sciences, Dúbravská Cesta 9, 845 07 Bratislava, Slovakia
Jozef Kenyeres: EBCONT Proconsult GmbH, Millennium Tower, Handelskai 94-96, 1200 Vienna, Austria

Future Internet, 2021, vol. 13, issue 5, 1-22

Abstract: Determining the network size is a critical process in numerous areas (e.g., computer science, logistic, epidemiology, social networking services, mathematical modeling, demography, etc.). However, many modern real-world systems are so extensive that measuring their size poses a serious challenge. Therefore, the algorithms for determining/estimating this parameter in an effective manner have been gaining popularity over the past decades. In the paper, we analyze five frequently applied distributed consensus gossip-based algorithms for network size estimation in multi-agent systems (namely, the Randomized gossip algorithm, the Geographic gossip algorithm, the Broadcast gossip algorithm, the Push-Sum protocol, and the Push-Pull protocol). We examine the performance of the mentioned algorithms with bounded execution over random geometric graphs by applying two metrics: the number of sent messages required for consensus achievement and the estimation precision quantified as the median deviation from the real value of the network size. The experimental part consists of two scenarios—the consensus achievement is conditioned by either the values of the inner states or the network size estimates—and, in both scenarios, either the best-connected or the worst-connected agent is chosen as the leader. The goal of this paper is to identify whether all the examined algorithms are applicable to estimating the network size, which algorithm provides the best performance, how the leader selection can affect the performance of the algorithms, and how to most effectively configure the applied stopping criterion.

Keywords: consensus algorithms; count; data aggregation; distributed algorithms; distributed computing; gossip algorithms; information fusion; network size; network size estimation; sensor fusion (search for similar items in EconPapers)
JEL-codes: O3 (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://www.mdpi.com/1999-5903/13/5/134/pdf (application/pdf)
https://www.mdpi.com/1999-5903/13/5/134/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jftint:v:13:y:2021:i:5:p:134-:d:557179

Access Statistics for this article

Future Internet is currently edited by Ms. Grace You

More articles in Future Internet from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().