Gossip protocols: full view or partial view

I’ve been preparing my talk for Velocity Conf and Codemesh for a long time. One of the things I realized is that there is no day in which I don’t think that there is something I had as a certainty that starts crumbling after reading a new paper.  That’s exactly what happens with the peer sampling service in gossip protocols.

So first of all, what’s the peer sampling service?.
The fundamental property of gossip is that every node exchanges information with some of its peers and it selects them randomly. So, It’s clear that  random partner selection seems to be an essential aspect of gossip protocols [2].

 

peer.png
From “Gossiping in Distributed Systems” [5]

 

It doesn’t matter if it’s a function or separate service, when our gossip algorithm needs a peer, that service/function provides it.

So, we can think of a Gossip protocol using the Peer sampling service as Meta-Gossip protocol, that is, a Gossip protocol that relies on a Gossip protocol :). In more technical words, this is exactly what a membership protocol does, provide a view of all the nodes that are alive in the cluster and it’s one of the typical application of gossip protocols.

Most gossip protocols assume that this selection of peers follows a uniform random sample of all nodes in the system, and this assumption made it possible to establish many desirable features of gossip-based protocols like scalability, reliability, and efficiency.  In other words, if the node selection is not random all these properties can be seriously affected [1], [2], [3].
In other words, when processes select partners in an unregulated way, we lose our ability to guarantee traditional properties like logarithmic time and resilience to failures.

In most of the solutions or papers out there every peer knows all other peers, basically, every node keeps a table with all other nodes in the system.

Now, If you read papers [1],[2], [3] and [4] you probably are going to think that in order for a Gossip protocol to be scalable you need to have a partial view of the nodes.

“So, whereas the application and its underlying gossip-based protocol are supposed to be scalable, it is wrong to assume that this is also the case for the underlying peer sampling service” [1]

“As described above, the protocol requires each node to know the entire system membership, in order to select the target nodes for each gossip round. Clearly, this solution is not scalable, not only due to the large number of nodes that may constitute the view but also due to the cost of maintaining the complete membership up-to-date.” [3]

But, if that’s the case how come are there Gossip protocols such as SERF that are so successful? Serf is been deployed in a cluster of 10k nodes (https://groups.google.com/forum/#!topic/serfdom/GlTqAshmK_w).

I’ve been wondering the same thing, that’s why I create a thread in twitter about this. The reality as always is that it depends, it depends on the tradeoffs you want to assume. There implementations where each node has a full view and others where is a partial view. When to use each of them depends on several aspects, the size of the cluster, the frequency, and size of the messages. A membership protocol with a full view requires a simple implementation but it has the problem that as the system grows (number of nodes), the memory required by each node grows too. So this can be a problem.  A partial view solves this but it’s more complex to implement.

A good example of a protocol with a full view is SWIM [6] and its implementation SERF. An example of a partial view is [3]

So for me, the major learning from all this is as @old_sound and @ifesdjeen is that academia tends to force words, solutions, propositions to support their claims, but reality has more colors and nuances. So, when reading a paper take everything with a grain of salt.

[1] 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.
[2] Lorenzo Alvisi, Jeroen Doumen, Rachid Guerraoui, Boris Koldehofe, Harry Li, Robbert van Renesse, and Gilles Tredan. 2007. How robust are gossip-based communication protocols?. SIGOPS Oper. Syst. Rev. 41, 5 (October 2007), 14-18. DOI: https://doi.org/10.1145/1317379.1317383
[3] HyParView: a Membership Protocol for Reliable Gossip-based Broadcast. João Leitão, José Pereira, Luís Rodrigues. Proc. 37th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN’07)
[4] P. Th. Eugster, R. Guerraoui, S. B. Handurukande, P. Kouznetsov, and A.-M. Kermarrec. 2003. Lightweight probabilistic broadcast. ACM Trans. Comput. Syst. 21, 4 (November 2003), 341-374. DOI=http://dx.doi.org/10.1145/945506.945507
[5] Anne-Marie Kermarrec and Maarten van Steen. 2007. Gossiping in distributed systems. SIGOPS Oper. Syst. Rev. 41, 5 (October 2007), 2-7. DOI: https://doi.org/10.1145/1317379.1317381
[6] Abhinandan Das, Indranil Gupta, and Ashish Motivala. 2002. SWIM: Scalable Weakly-consistent Infection-style Process Group Membership Protocol. In Proceedings of the 2002 International Conference on Dependable Systems and Networks (DSN ’02). IEEE Computer Society, Washington, DC, USA, 303-312.

Anuncios

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google photo

Estás comentando usando tu cuenta de Google. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s