Protocolo de chismes

Un protocolo de chismes o protocolo epidémico es un procedimiento o proceso de comunicación entre pares de computadoras que se basa en la forma en que se propagan las epidemias . ^{[ 1 ]} Algunos sistemas distribuidos utilizan el chisme entre pares para asegurar que los datos se difundan a todos los miembros de un grupo. Algunas redes ad hoc no tienen un registro central y la única forma de difundir datos comunes es que cada miembro los transmita a sus vecinos.

El concepto de comunicación por chismes se puede ilustrar con la analogía de los oficinistas que difunden rumores. Digamos que cada hora se reúnen alrededor del dispensador de agua. Cada empleado se empareja con otro, elegido al azar, y comparte el último chisme. Al comienzo del día, Dave inicia un nuevo rumor: le comenta a Bob que cree que Charlie se tiñe el bigote. En la siguiente reunión, Bob se lo cuenta a Alice, mientras que Dave repite la idea a Eve. Después de cada encuentro en el dispensador de agua, el número de personas que han escuchado el rumor se duplica aproximadamente (aunque esto no tiene en cuenta el chismeo repetido a la misma persona; tal vez Dave intenta contarle la historia a Frank, solo para descubrir que Frank ya la escuchó de Alice). Los sistemas informáticos suelen implementar este tipo de protocolo con una forma de "selección aleatoria entre pares": con una frecuencia determinada, cada máquina elige otra máquina al azar y comparte los rumores.

Probablemente existan cientos de variantes de protocolos específicos similares a los chismes, ya que es probable que cada escenario de uso se adapte a las necesidades específicas de la organización.

Por ejemplo, un protocolo de chismes podría emplear algunas de estas ideas:

• El núcleo del protocolo implica interacciones periódicas, por pares, entre procesos.
• La información que se intercambia durante estas interacciones tiene un tamaño limitado.
• Cuando los agentes interactúan, el estado de al menos uno de ellos cambia para reflejar el estado del otro.
• No se da por sentada una comunicación fiable.
• La frecuencia de las interacciones es baja en comparación con las latencias típicas de los mensajes, por lo que los costes del protocolo son insignificantes.
• Existe cierto grado de aleatoriedad en la selección de pares. Los pares pueden seleccionarse del conjunto completo de nodos o de un conjunto más pequeño de vecinos .
• Debido a la replicación, existe una redundancia implícita en la información entregada.

Es útil distinguir dos estilos predominantes de protocolo de chismes: ^{[ 2 ]}

• Protocolos de difusión (o protocolos de propagación de rumores). Estos utilizan el chisme para difundir información; básicamente funcionan inundando la red con agentes, pero de una manera que produce cargas máximas limitadas:
  1. Los protocolos de difusión de eventos utilizan el sistema de comunicación por intercambio de mensajes (gossip) para realizar multidifusión . Estos protocolos informan sobre los eventos, pero el intercambio de mensajes se produce periódicamente y los eventos no lo activan directamente. Una preocupación es la posible alta latencia entre el momento en que ocurre el evento y su entrega.
  2. Los protocolos de difusión de datos en segundo plano intercambian información constantemente sobre los nodos participantes. Por lo general, la latencia de propagación no es un problema, quizás porque la información en cuestión cambia lentamente o porque no hay una penalización significativa por actuar sobre datos ligeramente desactualizados.
• Protocolos que calculan agregados . Estos calculan un agregado de toda la red muestreando información en los nodos de la red y combinando los valores para llegar a un valor de todo el sistema: el valor más grande para algunos nodos de medición que están haciendo. El requisito clave es que el agregado debe ser computable mediante intercambios de información por pares de tamaño fijo; estos generalmente terminan después de una cantidad de rondas de intercambio de información logarítmica en el tamaño del sistema, momento en el cual se habrá establecido un patrón de flujo de información de todos a todos. Como efecto secundario de la agregación, es posible resolver otros tipos de problemas usando gossip; por ejemplo, hay protocolos gossip que pueden organizar los nodos en una superposición gossip en una lista ordenada por nodo-id (u algún otro atributo) en tiempo logarítmico usando intercambios de información de estilo agregación. De manera similar, hay algoritmos gossip que organizan los nodos en un árbol y calculan agregados como "suma" o "conteo" mediante gossip en un patrón sesgado para coincidir con la estructura del árbol.

Muchos protocolos anteriores al primer uso del término "gossip" se ajustan a esta definición bastante amplia. Por ejemplo, los protocolos de enrutamiento de Internet suelen utilizar intercambios de información similares a los de gossip. Un sustrato gossip puede utilizarse para implementar una red enrutada estándar: los nodos "comparten" información sobre mensajes punto a punto tradicionales, dirigiendo el tráfico a través de la capa gossip. Si el ancho de banda lo permite, esto implica que un sistema gossip puede potencialmente admitir cualquier protocolo clásico o implementar cualquier servicio distribuido clásico. Sin embargo, rara vez se pretende una interpretación tan amplia. Lo más habitual es que los protocolos gossip se ejecuten de forma regular, periódica, relativamente perezosa, simétrica y descentralizada; el alto grado de simetría entre los nodos es particularmente característico. Por lo tanto, si bien se podría ejecutar un protocolo de confirmación de dos fases sobre un sustrato gossip, hacerlo iría en contra del espíritu, si no de la redacción, de la definición.

El término "consistente convergente" se utiliza a veces para describir protocolos que logran una propagación exponencialmente rápida de la información. Para ello, un protocolo debe propagar cualquier información nueva a todos los nodos que se verán afectados por ella en un tiempo logarítmico con respecto al tamaño del sistema (el "tiempo de mezcla" debe ser logarítmico con respecto al tamaño del sistema).

Supongamos que queremos encontrar el objeto que mejor se ajuste a un patrón de búsqueda, dentro de una red de tamaño desconocido, pero donde los ordenadores están interconectados y donde cada máquina ejecuta un pequeño programa agente que implementa un protocolo de comunicación por intercambio de información.

• Para iniciar la búsqueda, el usuario solicitaría al agente local que comenzara a intercambiar información sobre la cadena de búsqueda. (Suponemos que los agentes parten de una lista conocida de pares o que recuperan esta información de algún tipo de repositorio compartido).
• Periódicamente, a una frecuencia determinada (digamos diez veces por segundo, para simplificar), cada agente elige a otro agente al azar y se comunica con él. Las cadenas de búsqueda conocidas por A ahora también serán conocidas por B, y viceversa. En la siguiente ronda de comunicación, A y B elegirán a otros agentes al azar, por ejemplo, C y D. Este fenómeno de duplicación en cada ronda hace que el protocolo sea muy robusto, incluso si se pierden algunos mensajes o si algunos de los agentes seleccionados son los mismos o ya conocen la cadena de búsqueda.
• Al recibir una cadena de búsqueda por primera vez, cada agente comprueba en su máquina local si hay documentos coincidentes.
• Los agentes también comentan sobre la mejor pareja hasta la fecha. Por lo tanto, si A conversa con B, después de la interacción, A conocerá las mejores parejas que B conoce, y viceversa. Las mejores parejas se difundirán por la red.

Si los mensajes pueden llegar a ser muy grandes (por ejemplo, si hay muchas búsquedas activas simultáneamente), se debería establecer un límite de tamaño. Además, las búsquedas deberían desaparecer de la red con el tiempo.

De ello se deduce que, en un tiempo logarítmico respecto al tamaño de la red (el número de agentes), cualquier nueva cadena de búsqueda habrá llegado a todos los agentes. Tras un retraso adicional de duración similar, cada agente sabrá dónde encontrar la mejor coincidencia. En concreto, el agente que inició la búsqueda habrá encontrado dicha coincidencia.

Por ejemplo, en una red con 25 000 máquinas, podemos encontrar la mejor coincidencia después de aproximadamente 30 rondas de intercambio de información: 15 para difundir la cadena de búsqueda y 15 más para descubrir la mejor coincidencia. Un intercambio de información podría ocurrir hasta una vez cada décima de segundo sin generar una carga excesiva; por lo tanto, este método de búsqueda en red podría explorar un gran centro de datos en aproximadamente tres segundos.

En este caso, las búsquedas podrían desaparecer automáticamente de la red después de, digamos, 10 segundos. Para entonces, quien inició la búsqueda ya conoce la respuesta y no tiene sentido seguir hablando de ella.

Los protocolos Gossip también se han utilizado para lograr y mantener la consistencia de bases de datos distribuidas o con otros tipos de datos en estados consistentes, contar el número de nodos en una red de tamaño desconocido, difundir noticias de forma robusta, organizar nodos de acuerdo con alguna política de estructuración, construir las llamadas redes superpuestas , calcular agregados, ordenar los nodos en una red, elegir líderes, etc.

Los protocolos de chismes pueden utilizarse para propagar información de forma similar a como se propaga una infección viral en una población biológica. De hecho, las matemáticas de las epidemias se utilizan a menudo para modelar las matemáticas de la comunicación por chismes. El término algoritmo epidémico se emplea a veces para describir un sistema de software que utiliza este tipo de propagación de información basada en chismes.

• Los protocolos Gossip son solo una clase entre muchas clases de protocolos de red. Véase también sincronización virtual , máquinas de estados distribuidas , algoritmo Paxos , transacciones de bases de datos . Cada clase contiene decenas o incluso cientos de protocolos, que difieren en sus detalles y propiedades de rendimiento, pero son similares en cuanto a las garantías que ofrecen a los usuarios.
• Algunos protocolos de chismes reemplazan el mecanismo de selección aleatoria de pares con un esquema más determinista. Por ejemplo, en el algoritmo NeighbourCast , en lugar de comunicarse con nodos aleatorios, la información se difunde comunicándose únicamente con nodos vecinos. Existen varios algoritmos que utilizan ideas similares. Un requisito clave al diseñar dichos protocolos es que el conjunto de vecinos trace un grafo expansor .
• Enrutamiento
• Tribler , cliente peer-to-peer de BitTorrent que utiliza el protocolo gossip.