Show Paths Random Selection / Fanout Send Message Play Delete Restart
Nodes Fanout Apply

Is it a real implementation?

If you take a look at the code, you won't see a real implementation of a Gossip protocol. This is because there is no reason for it. The goal of this simulator is to help people understand how they work not how they're implemented. If we really wanted to do it, we would need to implement a transport layer to mimic tcp or udp. The best idea would be to use the messages as transport layer. In my github, you can see a real implementation in clojure here&here

Implementation

Doubts? This will help.

In the simulator, all the nodes seem to be synchronized as if there was one global cycle. This happens in the simulator because is easier for the visualization. However, this is NOT what happens in a real gossip protocol where each node has its own cycle and there is not synchronization at all.

How do the nodes know about each other? That's a good question!

There are several ways depending on the implementation. For example, in HyParView [6], when a node wishes to join the overlay, it must know another node that already belongs to the overlay. That node is called the contact node. In Gossip protocolsi, when two nodes exchange information, they also exchange the list of nodes thet have. In that way, the view that each node has is updated in every cycle.

Separated Cycles

Recommended readings and talks

References

[1] Ken Birman. The Promise, and Limitations, of Gossip Protocols. SIGOPS Oper. Syst. Rev., 41(5):8–13, October 2007

[2] A. Demers, D. Greene, C. Hauser, W. Irish, J. Larson, S. Shenker, H. Sturgis, D. Swinehart, and D. Terry. “Epidemic Algorithms for Replicated Database Maintenance.” In Proc. Sixth Symp. on Principles of Distributed Computing, pp. 1–12, Aug. 1987. ACM.

[3] JELASITY, M., GUERRAOUI, R., KERMARREC, A.-M., AND VAN STEEN, M. 2004. The peer sampling service: Experimental evaluation of unstructured gossip-based implementations. In Middleware 2004, H.-A. Jacobsen, Ed. Lecture Notes in Computer Science, vol. 3231. Springer-Verlag, 79–98.

[4] http://www.inf.u-szeged.hu/~jelasity/ddm/gossip.pdf

[5] S. Voulgaris, M. Jelasity, M. van Steen, A Robust and Scalable Peer-to-Peer Gossiping Protocol,Lecture Notes in Computer Science (LNCS), vol. 2872 (Springer, Berlin/Heidelberg, 2004), pp. 47–58. doi:10.1007/b104265

[6] J. Leita ̃o, J. Pereira, and L. Rodrigues. Hyparview: a membership protocol for reliable gossip-based broadcast. In Proceedings of the Internacional Conference on Dependable Systems and Networks (DSN), Edinburgh, UK, June 2007.