Protocolo de chismes

Concepto en informática

Un protocolo de chismes o protocolo de epidemia 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 chismes entre pares para garantizar 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 confiar en que cada miembro los transmita a sus vecinos.

Comunicación

El concepto de comunicación a través de chismes se puede ilustrar con la analogía de los empleados de oficina que difunden rumores. Digamos que cada hora los empleados de oficina 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 comienza un nuevo rumor: le comenta a Bob que cree que Charlie se tiñe el bigote. En la siguiente reunión, Bob se lo dice a Alice, mientras que Dave repite la idea a Eve. Después de cada encuentro junto al dispensador de agua, el número de personas que han oído el rumor se duplica aproximadamente (aunque esto no explica el chisme que se le cuenta dos veces a la misma persona; tal vez Dave intenta contarle la historia a Frank, sólo para descubrir que Frank ya se la había oído a Alice). Los sistemas informáticos suelen implementar este tipo de protocolo con una forma de "selección aleatoria de pares": con una frecuencia determinada, cada máquina elige otra máquina al azar y comparte los rumores.

Variantes y estilos

Probablemente existan cientos de variantes de protocolos específicos de tipo chisme porque es probable que cada escenario de uso se personalice según 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 intercambiada durante estas interacciones es de 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 sentado que la comunicación sea fiable.
• La frecuencia de las interacciones es baja en comparación con las latencias de mensajes típicas, por lo que los costos del protocolo son insignificantes.
• Existe algún tipo de aleatoriedad en la selección de pares. Los pares pueden seleccionarse de todo el conjunto de nodos o de un conjunto más pequeño de vecinos .
• Debido a la replicación existe una redundancia implícita de la información entregada.

Tipos de protocolo

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

• Protocolos de difusión (o protocolos de propagación de rumores). Estos utilizan los chismes para difundir información; básicamente funcionan inundando la red de agentes, pero de una manera que produce cargas limitadas en el peor de los casos:
  1. Los protocolos de difusión de eventos utilizan el chisme para realizar multidifusiones . Informan de eventos, pero el chisme se produce periódicamente y los eventos en realidad no lo activan. Una preocupación aquí es la latencia potencialmente alta desde que se produce el evento hasta que se entrega.
  2. Los protocolos de difusión de datos de fondo intercambian constantemente información asociada a los nodos participantes. Normalmente, la latencia de propagación no es un problema, tal vez porque la información en cuestión cambia lentamente o no hay una penalización significativa por actuar sobre datos ligeramente obsoletos.
• Protocolos que calculan agregados . Estos calculan un agregado de toda la red mediante el muestreo de información en los nodos de la red y la combinación de 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 más pequeño, etc. El requisito clave es que el agregado debe ser computable mediante intercambios de información por pares de tamaño fijo; estos normalmente 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 mediante chismes; por ejemplo, hay protocolos de chismes que pueden organizar los nodos en una superposición de chismes en una lista ordenada por id de nodo (o algún otro atributo) en tiempo logarítmico utilizando intercambios de información de estilo agregación. De manera similar, hay algoritmos de chismes que organizan los nodos en un árbol y calculan agregados como "suma" o "conteo" mediante chismes en un patrón sesgado para coincidir con la estructura del árbol.

Muchos protocolos anteriores al uso más temprano del término "chisme" caen dentro de esta definición bastante inclusiva. Por ejemplo, los protocolos de enrutamiento de Internet a menudo utilizan intercambios de información similares a los chismes. Un sustrato de chisme se puede utilizar para implementar una red enrutada estándar: los nodos "cotillean" sobre mensajes punto a punto tradicionales, impulsando efectivamente el tráfico a través de la capa de chisme. Si el ancho de banda lo permite, esto implica que un sistema de chisme puede potencialmente soportar cualquier protocolo clásico o implementar cualquier servicio distribuido clásico. Sin embargo, rara vez se pretende una interpretación tan amplia e inclusiva. Los protocolos de chisme más típicos son aquellos que se ejecutan específicamente de manera 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 2 fases sobre un sustrato de chisme, hacerlo estaría en desacuerdo con el espíritu, si no con la redacción, de la definición.

El término convergentemente consistente 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 la información en un tiempo logarítmico en relación con el tamaño del sistema (el "tiempo de mezcla" debe ser logarítmico en relación con el tamaño del sistema).

Ejemplos

Supongamos que queremos encontrar el objeto que más se acerque a algún patrón de búsqueda, dentro de una red de tamaño desconocido, pero donde las computadoras están conectadas entre sí y donde cada máquina ejecuta un pequeño programa agente que implementa un protocolo de chismes.

• Para iniciar la búsqueda, un usuario le pediría al agente local que comience a intercambiar información sobre la cadena de búsqueda. (Suponemos que los agentes comienzan con una lista conocida de pares o recuperan esta información de algún tipo de almacenamiento compartido).
• Periódicamente, a cierta velocidad (digamos diez veces por segundo, para simplificar), cada agente elige a otro agente al azar y cotillea con él. Las cadenas de búsqueda conocidas por A ahora también las conocerá B, y viceversa. En la siguiente "ronda" de cotilleos, A y B elegirán pares aleatorios adicionales, tal vez C y D. Este fenómeno de duplicación ronda tras ronda hace que el protocolo sea muy robusto, incluso si se pierden algunos mensajes o si algunos de los pares seleccionados son los mismos o ya conocen la cadena de búsqueda.
• Al recibir una cadena de búsqueda por primera vez, cada agente verifica su máquina local en busca de documentos coincidentes.
• Los agentes también cotillean sobre las mejores coincidencias hasta la fecha. Así, si A cotillea con B, después de la interacción, A sabrá cuáles son las mejores coincidencias que conoce B, y viceversa. Las mejores coincidencias se "difundirán" a través de la red.

Si los mensajes pueden llegar a ser muy grandes (por ejemplo, si hay muchas búsquedas activas al mismo tiempo), se debería introducir un límite de tamaño. Además, las búsquedas deberían "caducar" en la red.

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

Por ejemplo, en una red con 25.000 máquinas, podemos encontrar la mejor coincidencia después de unas 30 rondas de chismes: 15 para difundir la cadena de búsqueda y 15 más para descubrir la mejor coincidencia. Un intercambio de chismes podría producirse con una frecuencia de hasta una vez cada décima de segundo sin imponer una carga indebida, por lo que esta forma de búsqueda en la red podría buscar en un gran centro de datos en unos tres segundos.

En este escenario, las búsquedas podrían desaparecer automáticamente de la red después de, digamos, 10 segundos. Para entonces, el iniciador ya sabe la respuesta y no tiene sentido seguir hablando de esa búsqueda.

Los protocolos de chismes 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 manera 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.

Algoritmos de epidemias

Los protocolos de chismes se pueden utilizar para propagar información de una manera bastante similar a la forma en que 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 de chismes. El término algoritmo de epidemia se emplea a veces para describir un sistema de software en el que se emplea este tipo de propagación de información basada en chismes.

Véase también

• Los protocolos Gossip son sólo una clase entre muchas clases de protocolos de red. Véase también sincronía 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 el nivel de las garantías ofrecidas 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 los nodos vecinos. Hay varios algoritmos que utilizan ideas similares. Un requisito clave al diseñar dichos protocolos es que el conjunto de vecinos trace un gráfico expansor .
• Enrutamiento
• Tribler , cliente peer-to-peer de BitTorrent que utiliza el protocolo Gossip.

Referencias

1. Demers, Alan; Greene, Dan; Hauser, Carl; Irish, Wes; Larson, John (1987). "Algoritmos epidémicos para el mantenimiento de bases de datos replicadas". Actas del sexto simposio anual de la ACM sobre principios de computación distribuida - PODC '87 . págs. 1–12. doi :10.1145/41840.41841. ISBN 978-0-89791-239-6. OCLC  8876960204. S2CID  1889203.
2. Jelasity, Márk (1 de enero de 2011). "Chismes" (PDF) . En Serugendo, Giovanna Di Marzo; Gleizes, Marie-Pierre; Karageorgos, Anthony (eds.). Software autoorganizado . Natural Computing Series. Springer Berlin Heidelberg. págs. 139–162. doi :10.1007/978-3-642-17348-6_7. ISBN. 978-3-642-17347-9. Número de identificación del sujeto  214970849.

Lectura adicional

• Allavena, André; Demers, Alan; Hopcroft, John E. (2005). "Corrección de un protocolo de membresía basado en chismes". Actas del vigésimo cuarto simposio anual ACM SIGACT-SIGOPS sobre Principios de computación distribuida - PODC '05 . p. 292. doi :10.1145/1073814.1073871. ISBN 978-1-58113-994-5. OCLC  8876665695. S2CID  9378092.
• Birman, Kenneth P.; Hayden, Mark; Ozkasap, Oznur; Xiao, Zhen; Budiu, Mihai; Minsky, Yaron (mayo de 1999). "Multidifusión bimodal". ACM Transactions on Computer Systems . 17 (2): 41–88. doi : 10.1145/312203.312207 . S2CID  207744063.
• Eugster, P. Th.; Guerraoui, R.; Handurukande, SB; Kouznetsov, P.; Kermarrec, A.-M. (noviembre de 2003). "Transmisión probabilística ligera" (PDF) . ACM Transactions on Computer Systems . 21 (4): 341–374. doi :10.1145/945506.945507. S2CID  6875620.
• Gupta, Indranil; Birman, Ken; Linga, Prakash; Demers, Al; Van Renesse, Robbert (2003). "Kelips: creación de un DHT P2P estable y eficiente mediante el aumento de la memoria y la sobrecarga de fondo". Sistemas punto a punto II . Notas de clase en informática. Vol. 2735. págs. 160–169. doi :10.1007/978-3-540-45172-3_15. ISBN 978-3-540-40724-9.
• Diseño sistemático de tecnologías P2P para sistemas distribuidos. Indranil Gupta, Global Data Management, eds: R. Baldoni, G. Cortese, F. Davide y A. Melpignano, 2006.
• Leitao, Joao; Pereira, Jose; Rodrigues, Luis (2007). "HyPar View : Un protocolo de membresía para una transmisión confiable basada en chismes". 37.ª Conferencia internacional anual IEEE/IFIP sobre sistemas y redes confiables (DSN'07) . págs. 419–429. doi :10.1109/DSN.2007.56. hdl :1822/38895. ISBN 978-0-7695-2855-7.S2CID 9060122  .
• Gupta, I.; Kermarrec, A.-M.; Ganesh, AJ (julio de 2006). "Protocolos de estilo epidémico eficientes y adaptables para una multidifusión confiable y escalable". IEEE Transactions on Parallel and Distributed Systems . 17 (7): 593–605. doi :10.1109/TPDS.2006.85. S2CID  1148979.
• Jelasity, Márk; Montresor, Alberto; Babaoglu, Ozalp (agosto de 2009). "T-Man: construcción rápida de topologías superpuestas basada en Gossip" (PDF) . Redes de computadoras . 53 (13): 2321–2339. doi :10.1016/j.comnet.2009.03.013.
• Leitao, Joao; Pereira, Jose; Rodrigues, Luis (2007). "Epidemic Broadcast Trees". 2007 26th IEEE International Symposium on Reliable Distributed Systems (SRDS 2007) . págs. 301–310. doi :10.1109/SRDS.2007.27. hdl :1822/38894. ISBN 978-0-7695-2995-0.S2CID 7210467  .
• Jelasity, Márk; Montresor, Alberto; Babaoglu, Ozalp (agosto de 2005). "Agregación basada en chismes en grandes redes dinámicas" (PDF) . ACM Transactions on Computer Systems . 23 (3): 219–252. doi :10.1145/1082469.1082470. S2CID  2608879.
• Corte ordenado de redes superpuestas muy grandes. Márk Jelasity y Anne-Marie Kermarrec. IEEE P2P, 2006.
• Topologías de superposición de superpares que tienen en cuenta la proximidad. Gian Paolo Jesi, Alberto Montresor y Ozalp Babaoglu. IEEE Transactions on Network and Service Management, 4(2):74–83, septiembre de 2007.
• X-BOT: un protocolo para la optimización resistente de superposiciones no estructuradas. João Leitão, João Marques, José Pereira, Luís Rodrigues. Proc. 28º Simposio internacional IEEE sobre sistemas distribuidos confiables (SRDS'09).
• Protocolos de localización de recursos y chismes espaciales. David Kempe, Jon Kleinberg, Alan Demers. Journal of the ACM (JACM) 51: 6 (noviembre de 2004).
• Computación basada en chismes de información agregada. David Kempe, Alin Dobra, Johannes Gehrke. Proc. 44.º Simposio anual IEEE sobre fundamentos de la ciencia informática (FOCS). 2003.
• Técnicas activas y pasivas para la estimación del tamaño de grupos en sistemas distribuidos dinámicos y de gran escala. Dionysios Kostoulas, Dimitrios Psaltoulis, Indranil Gupta, Ken Birman, Al Demers. Elsevier Journal of Systems and Software , 2007.
• Cree uno y obtenga otro gratis: aprovechamiento de la coexistencia de múltiples redes superpuestas P2P. Balasubramaneyam Maniymaran, Marin Bertier y Anne-Marie Kermarrec. Proc. ICDCS , junio de 2007.
• Recuento y muestreo de pares en redes superpuestas: métodos de recorrido aleatorio. Laurent Massoulié, Erwan Le Merrer, Anne-Marie Kermarrec, Ayalvadi Ganesh. Proc. 25th ACM PODC . Denver, 2006.
• Chord on Demand. Alberto Montresor, Márk Jelasity y Ozalp Babaoglu. Proc. 5.ª Conferencia sobre Computación entre pares (P2P), Constanza, Alemania, agosto de 2005.
• Nielsen, Michael A. (2005). "Introducción a los grafos expansores" (PDF) . Michael Nielsen . S2CID  3045708. Archivado desde el original (PDF) el 15 de julio de 2011.
• Construcción de redes P2P de diámetro reducido. G. Pandurangan, P. Raghavan, Eli Upfal . En Actas del 42.º Simposio sobre Fundamentos de la Ciencia de la Computación (FOCS), 2001.
• Van Renesse, Robbert; Birman, Kenneth P.; Vogels, Werner (mayo de 2003). "Astrolabio: una tecnología robusta y escalable para la monitorización, gestión y extracción de datos de sistemas distribuidos". ACM Transactions on Computer Systems . 21 (2): 164–206. doi :10.1145/762483.762485. S2CID  6204358.
• Voulgaris, S.; Kermarrec, A.-M.; Massoulie, L.; Van Steen, M. (2004). "Explotación de la proximidad semántica en la búsqueda de contenido entre pares". Actas. 10.º Taller internacional IEEE sobre tendencias futuras de sistemas informáticos distribuidos, 2004. FTDCS 2004. págs. 238–243. doi :10.1109/FTDCS.2004.1316622. hdl :1871/12832. ISBN. 0-7695-2118-5.S2CID 9464168  .
• Gupta, Ruchir; Singh, Yatindra Nath (2015). "Agregación de reputación en redes entre pares mediante algoritmo de chismes diferenciales". IEEE Transactions on Knowledge and Data Engineering . 27 (10): 2812–2823. arXiv : 1210.4301 . doi :10.1109/TKDE.2015.2427793. S2CID  650473.
• Bailey, Norman TJ (1957). La teoría matemática de las epidemias . Hafner. ISBN 978-0-85264-113-2.