¿Qué son los protocolos Gossip?
Cuando hablamos de protocolo Gossip o Epidemic nos referimos a una forma específica de comunicación peer-to-peer que tiene lugar entre diferentes dispositivos que participan en una red. La información es enviada de un nodo a otro hasta que eventualmente consigue distribuirse por toda la red.
Esta propuesta intenta resolver el problema de conseguir comunicar un mensaje a todos los miembros de una red. En el caso de este protocolo se consigue tomando como base la forma en que una enfermedad se expande, es decir, un nodo no envía un mensaje a todos los demás, sino solo a algunos y éstos a su vez a otros tantos, así sucesivamente hasta conseguir que la información sea recibida por todos.
En un primer momento, este protocolo fue utilizado como una forma de mantener la consistencia en las bases de datos que eran replicadas en diferentes lugares. Sin embargo, se vió que también podía ser utilizado para resolver otros problemas como la comunicación entre nodos de una red P2P.
¿Cómo funciona?
Un protocolo gossip es simple a nivel teórico y de programar. Como hemos dicho antes la idea que hay detrás de ellos es que un nodo quiere compartir información con otros nodos de la red. Por tanto, cada cierto tiempo elige aleatoriamente uno o varios nodos de un grupo y comparte la información con ellos. Los que la reciben hacen exactamente lo mismo. A cada una de esas rondas en las que se envía la información se la denomina ciclo. Y al número de nodos a los que se envía el mensaje se llama Fanout.
Por tanto, la forma en que esta propuesta trabaja suele ser la siguiente:
- Un nodo elige de forma aleatoria otros nodos a los que enviar la información
- El proceso de intercambio de información tiene lugar
- Los nodos procesan la información recibida
- Los pasos son repetidos hasta que la información se haya distribuido por toda la red.
Sabiendo lo anterior, vemos que en un punto determinado del proceso de expansión del mensaje nos podemos encontrar nodos con diferentes estados dentro de un protocolo gossip. En concreto con 3 de ellos: infectados, posibles y eliminados:
Infectados
Un nodo infectado es aquel que tiene la nueva información e intentará distribuirla seleccionando de forma aleatoria otros nodos para enviarla.
Posibles
Son aquellos que no tienen la información y que, por tanto, eventualmente se convertirán en infectados.
Eliminados
Son aquellos que saben sobre los nuevos datos, pero que no están intentando distribuirla. Un caso sería, por ejemplo, que todos los nodos a los que está conectado ya saben la información.
Veámos un ejemplo, digamos que en una red el nodo N1 recibe un nuevo dato. Éste elegirá aleatoriamente un nodo para enviarle la información. El nodo elegido y al que enviará la información lo llamamos N2. Ahora mismo tenemos N1 y N2 que tienen la nueva información y ambos elegirán, por separado e independientemente el uno del otro, aleatoriamente nuevos destinatarios. Digamos que N1 enviará el dato a N3 y N2 a N4. El proceso descrito continuará hasta que la información sea enviada a todos los nodos.
Los análisis de estos algoritmos se centran fundamentalmente en el diseño de las mejores estrategias a la hora de seleccionar nodos con los que compartir la información. Para ello, se han desarrollado modelos matemáticos para demostrar la eficiencia de las diferentes estrategias. Usualmente, en estos sistemas la información se consigue transmitir a todos los nodos en O(log(N)) ciclos, donde N es el número de nodos en la red
Ventajas
Escalables
Es un protocolo escalable, ya que, por lo general, le lleva O(log N) ciclos que una información llegue a todos los nodos. Además un nodo enviará un número limitado de mensajes independientemente del tamaño de la red y no espera confirmación de la recepción del mismo.
Tolerante a fallos
Tiene la habilidad de poder funcionar en redes irregulares y con posibles fallos de conexión. La razón de ello es que un nodo compartirá la misma información varias veces con diferentes participantes. Por tanto, si un punto no es accesible, la información se compartirá a través de otro nodo. En consecuencia, hay diferentes rutas para que la información llegue a destino.
Robusto
Ningún nodo de la red tiene un rol específico, por lo que si uno falla no evita que los otros continúen trabajando. Además, cada nodo puede unirse o dejar la red cuando quiera sin causar disrupciones en el sistema. Sin embargo, esto no quiere decir que sean infalibles, ya que no funcionan correctamente ante nodos malignos por ejemplo.
Descentralización
Ofrecen la posibilidad de compartir la información entre los nodos de una red descentralizada.
Sencillez
Los algoritmos que hay detrás de estos protocolos son sencillos y simples.
Desventajas
No muy eficientes
Puede ocurrir que un mismo mensaje pueda ser enviado varias veces a un mismo nodo. Por ejemplo, el nodo N1 en un primer ciclo elige aleatoriamente N2 para enviar la información. En un ciclo posterior puede ocurrir que vuelva elegirlo como destinatario de la información. Esto lleva a un alto consumo de ancho de banda por información redundante.
Dificultad para encontrar fallos
La aleatoriedad propia de estos protocolos puede dificultar el trabajo para reproducir ciertos errores y encontrar posibles bugs que surjan en tiempo de ejecución.
No son escalables en ciertas situaciones
Por ejemplo el aumento de ratio de eventos puede consumir toda la capacidad de transporte de información de los diferentes canales de transmisión. Esto llevaría a un funcionamiento erróneo del protocolo. El punto de saturación dependerá de diferentes factores tales como el ratio en el que los eventos entran en el sistema, el tamaño de los mismos, el fanout y el tamaño de los mensajes.
Aplicaciones prácticas de este grupo de protocolos existen muchas y varias, como ejemplo, tenemos Bitcoin donde es utilizado para la comunicación entre los mineros el valor del nonce. Otros ejemplos lo podemos encontrar en Hashgraph y Hyperledger.
Fuentes:
https://en.wikipedia.org/wiki/Gossip_protocol
https://managementfromscratch.wordpress.com/2016/04/01/introduction-to-gossip/
