IDEAS home Printed from https://ideas.repec.org/a/gam/jftint/v13y2021i5p134-d557179.html
   My bibliography  Save this article

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

Author

Listed:
  • 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)

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.

Suggested Citation

  • Martin Kenyeres & Jozef Kenyeres, 2021. "Comparative Study of Distributed Consensus Gossip Algorithms for Network Size Estimation in Multi-Agent Systems," Future Internet, MDPI, vol. 13(5), pages 1-22, May.
  • Handle: RePEc:gam:jftint:v:13:y:2021:i:5:p:134-:d:557179
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/1999-5903/13/5/134/pdf
    Download Restriction: no

    File URL: https://www.mdpi.com/1999-5903/13/5/134/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Claudia Antal & Tudor Cioara & Ionut Anghel & Marcel Antal & Ioan Salomie, 2021. "Distributed Ledger Technology Review and Decentralized Applications Development Guidelines," Future Internet, MDPI, vol. 13(3), pages 1-32, February.
    2. Andrei Vladyko & Abdukodir Khakimov & Ammar Muthanna & Abdelhamied A. Ateya & Andrey Koucheryavy, 2019. "Distributed Edge Computing to Assist Ultra-Low-Latency VANET Applications," Future Internet, MDPI, vol. 11(6), pages 1-22, June.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Rao Muzamal Liaqat & Philip Branch & Jason But, 2023. "Design Considerations and Performance Evaluation of Gossip Routing in LoRa-Based Linear Networks," Future Internet, MDPI, vol. 15(11), pages 1-17, November.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Mahdi Ghaemi Asl & Oluwasegun B. Adekoya & Muhammad Mahdi Rashidi, 2023. "Quantiles dependence and dynamic connectedness between distributed ledger technology and sectoral stocks: enhancing the supply chain and investment decisions with digital platforms," Annals of Operations Research, Springer, vol. 327(1), pages 435-464, August.
    2. Alexandru-Ioan Florea & Ionut Anghel & Tudor Cioara, 2022. "A Review of Blockchain Technology Applications in Ambient Assisted Living," Future Internet, MDPI, vol. 14(5), pages 1-18, May.
    3. Yi-Hsiang Lu & Ching-Chiang Yeh & Yu-Mei Kuo, 2024. "Exploring the critical factors affecting the adoption of blockchain: Taiwan’s banking industry," Financial Innovation, Springer;Southwestern University of Finance and Economics, vol. 10(1), pages 1-25, December.
    4. Sławomir Bielecki & Tadeusz Skoczkowski & Lidia Sobczak & Marcin Wołowicz, 2022. "Electricity Usage Settlement System Based on a Cryptocurrency Instrument," Energies, MDPI, vol. 15(19), pages 1-35, September.
    5. Haoli Sun & Bingfeng Pi & Jun Sun & Takeshi Miyamae & Masanobu Morinaga, 2021. "SASLedger: A Secured, Accelerated Scalable Storage Solution for Distributed Ledger Systems," Future Internet, MDPI, vol. 13(12), pages 1-19, November.
    6. Anthony Jnr. Bokolo, 2022. "Exploring interoperability of distributed Ledger and Decentralized Technology adoption in virtual enterprises," Information Systems and e-Business Management, Springer, vol. 20(4), pages 685-718, December.
    7. Ahad ZareRavasan & Taha Mansouri & Michal Krčál & Saeed Rouhani, 2022. "Editorial for the Special Issue on Blockchain: Applications, Challenges, and Solutions," Future Internet, MDPI, vol. 14(5), pages 1-2, May.
    8. Gkogkos, Georgios & Patsonakis, Christos & Drosou, Anastasios & Tzovaras, Dimitrios, 2023. "A DLT-based framework for secure IoT infrastructure in smart communities," Technology in Society, Elsevier, vol. 74(C).

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:gam:jftint:v:13:y:2021:i:5:p:134-:d:557179. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.