9/15/07

Counting Fish in Water



A great simple gossiping algorithm for counting the number of nodes in a large (unreliable) network.

currentEstimate =
my_water / my_fish;
Periodically:
my_fish /= my_degree+1;
my_water /= my_degree+1;
sendToAllNeighbours (my_fish, my_water);
Receive (fish , water):
my_fish += fish;
my_water += water;


From "Brief Announcement: Practical Summation via Gossip."