Community-Based Gossip Algorithm for Distributed Averaging - Sirocchi, Christel; Bogliolo, Alessandro (Distributed Applications and Interoperable Systems, 2023)
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 directio