Gossip-based counting in dynamic networks

Gossip-based counting in dynamic networks

Van de Bovenkamp, R.
Kuipers, F.
Van Mieghem, P.

Electrical Engineering, Mathematics and Computer Science

Network Architectures and Services Group (NAS)

2012-03-25

We propose Gossipico, a gossip algorithm to average, sum or find minima and maxima over node values in a large, distributed, and dynamic network. Unlike previous work, Gossipico provides a continuous estimate of, for example, the number of nodes, even when the network becomes disconnected. Gossipico converges quickly due to the introduction of a beacon mechanism that directs messages to an autonomously selected beacon node. The information spread through the network shows a percolation-like phase-transition and allows information to propagate along near-shortest paths. Simulations in various different network topologies (ranging in size up to one million nodes) illustrate Gossipico’s robustness against network changes and display a near-optimal count time. Moreover, in a comparison with other related gossip algorithms, Gossipico displays an improved and more stable performance over various classes of networks.

gossip-algorithms
network dynamics
node counting

http://resolver.tudelft.nl/uuid:f14313e2-4ded-4e8d-aac4-b305d4bd050f

https://doi.org/10.1007/978-3-642-30054-7_32

Springer

978-3-642-30054-7

Proceedings 11th International IFIP TC 6 Networking Conference, Networking 2012, Part II, Praag, 21–25 Mei 2012

Institutional Repository

conference paper

(c) 2012 Van de Bovenkamp, R.
Kuipers, F.
Van Mieghem, P.