Community-Based Gossip Algorithm for Distributed Averaging
Sirocchi C, Bogliolo A (2023)
Publication Type: Conference contribution
Publication year: 2023
Journal
Publisher: Springer
Series: Lecture Notes in Computer Science
City/Town: Cham
Pages Range: 37-53
Conference Proceedings Title: Distributed Applications and Interoperable Systems
Event location: Lissabon
ISBN: 9783031352591
DOI: 10.1007/978-3-031-35260-7_3
Abstract
Most real-world networks tend to organise according to an underlying modular structure, where nodes are relatively more connected with nodes belonging to the same community than others. Modularity can impact the performance of distributed data aggregation and computation in networked systems due to limited communication between communities. This paper examines the effects of modularity in the context of distributed averaging, a fundamental cooperative control problem and a central task in various applications ranging from clock synchronisation to formation control. Numerical experiments on synthetic networks demonstrate that modularity negatively affects the convergence rate of randomised gossip algorithms for distributed averaging. Further analysis suggests that nodes bridging communities (here termed boundary nodes) hold a crucial role in controlling the information flow across the network and that a modularity metric dependent on boundary nodes is a good linear predictor of performance while computable in a distributed manner. The averaging gossip protocol is then integrated with a distributed community detection algorithm, giving rise to a novel gossip scheme that leverages local community structure to improve performance by balancing the information flow at boundary nodes. The proposed community-based gossip algorithm is evaluated on synthetic modular structures, and its improved performance is confirmed by simulations run on real-world peer-to-peer networks. These findings emphasise the importance of community structure in distributed computation and might inspire further investigation in this direction.
Authors with CRIS profile
Involved external institutions
Italy (IT)How to cite
APA:
Sirocchi, C., & Bogliolo, A. (2023). Community-Based Gossip Algorithm for Distributed Averaging. In Distributed Applications and Interoperable Systems (pp. 37-53). Lissabon, PT: Cham: Springer.
MLA:
Sirocchi, Christel, and Alessandro Bogliolo. "Community-Based Gossip Algorithm for Distributed Averaging." Proceedings of the 23rd IFIP WG 6.1 International Conference, DAIS 2023, Held as Part of the 18th International Federated Conference on Distributed Computing Techniques, DisCoTec 2023, Lissabon Cham: Springer, 2023. 37-53.
BibTeX: Download