Un protocolo de chismes es un procedimiento o proceso de comunicación entre pares por computadora que se basa en la forma en que se propagan las epidemias . [1] Algunos sistemas distribuidos utilizan chismes de igual a igual 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 se los pase a sus vecinos.
El término protocolo epidémico se utiliza a veces como sinónimo de protocolo de chismes, ya que los chismes difunden información de manera similar a la propagación de un virus en una comunidad biológica.
Comunicación de chismes
El concepto de comunicación de chismes se puede ilustrar con la analogía de los trabajadores de oficina que difunden rumores. Digamos que cada hora los trabajadores de la oficina se congregan alrededor del enfriador de agua. Cada empleado se empareja con otro, elegido al azar, y comparte los últimos chismes. 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 próxima reunión, Bob le dice a Alice, mientras Dave le repite la idea a Eve. Después de cada encuentro con el enfriador de agua, el número de personas que han escuchado el rumor se duplica aproximadamente (aunque esto no tiene en cuenta el chisme dos veces con la misma persona; tal vez Dave intente contarle la historia a Frank, solo para descubrir que Frank ya lo escuchó. de Alice). Los sistemas informáticos suelen implementar este tipo de protocolo con una forma de "selección de pares" aleatoria: con una frecuencia determinada, cada máquina elige otra máquina al azar y comparte los rumores.
Muchas variantes y estilos
Probablemente hay cientos de variantes de protocolos específicos similares a Gossip porque 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 intercambiada durante estas interacciones es de tamaño limitado.
- Cuando los agentes interactúan, el estado de al menos un agente cambia para reflejar el estado del otro.
- No se asume una comunicación confiable.
- La frecuencia de las interacciones es baja en comparación con las latencias típicas de los mensajes, por lo que los costos del protocolo son insignificantes.
- Existe alguna forma 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 de la información entregada.
Tipos de protocolos de chismes
Es útil distinguir dos estilos predominantes de protocolo de chismes: [2]
- Protocolos de difusión (o protocolos de difusión de rumores). Estos usan chismes para difundir información; Básicamente funcionan mediante agentes de inundación en la red, pero de una manera que produce cargas limitadas en el peor de los casos:
- Los protocolos de difusión de eventos utilizan chismes para realizar multidifusiones . Informan eventos, pero los chismes ocurren periódicamente y los eventos en realidad no desencadenan el chisme. Una preocupación aquí es la latencia potencialmente alta desde que ocurre el evento hasta que se entrega.
- Los protocolos de difusión de datos de fondo cotillean continuamente sobre información asociada con los nodos participantes. Por lo general, la latencia de propagación no es una preocupación, tal vez porque la información en cuestión cambia lentamente o no hay una penalización significativa por actuar sobre datos un poco obsoletos.
- 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, 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 serie de rondas de intercambio de información logarítmico en el tamaño del sistema, momento en el que 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 otro tipo de problemas utilizando el chisme; por ejemplo, existen 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 usando intercambios de información al estilo de agregación. De manera similar, existen algoritmos de chismes que organizan los nodos en un árbol y calculan agregados como "suma" o "recuento" cotilleando en un patrón sesgado para coincidir con la estructura del árbol.
Muchos protocolos que son anteriores al uso más antiguo del término "chismes" 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. Se puede usar un sustrato de chismes para implementar una red enrutada estándar: los nodos "chismes" sobre los mensajes tradicionales de punto a punto, empujando efectivamente el tráfico a través de la capa de chismes. Si el ancho de banda lo permite, esto implica que un sistema de chismes puede admitir potencialmente cualquier protocolo clásico o implementar cualquier servicio distribuido clásico. Sin embargo, rara vez se pretende una interpretación tan amplia e inclusiva. Más típicamente, los protocolos de chismes 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 nodos es particularmente característico. Por lo tanto, si bien uno podría ejecutar un protocolo de compromiso de 2 fases sobre un sustrato de chismes, hacerlo estaría en desacuerdo con el espíritu, si no con la redacción, de la definición.
El término coherencia convergente se utiliza a veces para describir protocolos que logran una difusión de información exponencialmente rápida. Para este propósito, un protocolo debe propagar cualquier información nueva a todos los nodos que serán afectados por la información dentro del tiempo logarítmico en el tamaño del sistema (el "tiempo de mezcla" debe ser logarítmico en el tamaño del sistema).
Ejemplos de
Supongamos que queremos encontrar el objeto que más se aproxima 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 está ejecutando un pequeño programa de agente que implementa un protocolo de chismes.
- Para comenzar la búsqueda, un usuario le pediría al agente local que comenzara a cotillear 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 tienda compartida).
- 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 serán conocidas por B, y viceversa. En la próxima "ronda" de chismes, A y B elegirán pares aleatorios adicionales, tal vez C y D. Este fenómeno de duplicación ronda por ronda hace que el protocolo sea muy robusto, incluso si se pierden algunos mensajes o si algunos de los pares seleccionados se pierden el mismo o ya sabe acerca de la cadena de búsqueda.
- Al recibir una cadena de búsqueda por primera vez, cada agente verifica en su máquina local los documentos coincidentes.
- Los agentes también cotillean sobre la mejor pareja hasta la fecha. Por lo tanto, si A cotillea con B, después de la interacción, A conocerá las mejores coincidencias conocidas con B, y viceversa. Las mejores coincidencias se "difundirán" a través de la red.
Si los mensajes pueden aumentar de tamaño (por ejemplo, si hay muchas búsquedas activas al mismo tiempo), se debe introducir un límite de tamaño. Además, las búsquedas deberían "dejar de existir" en la red.
De ello se deduce que dentro del 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. Con un retraso adicional de la misma duración aproximada, cada agente sabrá dónde se puede encontrar la mejor combinación. 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 ocurrir hasta una vez cada décima de segundo sin imponer una carga indebida, por lo tanto, esta forma de búsqueda de red podría buscar un gran centro de datos en aproximadamente 3 segundos.
En este escenario, las búsquedas pueden desaparecer automáticamente de la red después de, digamos, 10 segundos. Para entonces, el iniciador ya conoce la respuesta y no tiene sentido seguir cotilleando sobre esa búsqueda.
Los protocolos de chismes también se han utilizado para lograr y mantener la consistencia de la base de datos distribuida o con otros tipos de datos en estados consistentes, contando el número de nodos en una red de tamaño desconocido, difundiendo noticias de manera robusta, organizando nodos de acuerdo con alguna política de estructuración, construyendo así. llamadas redes superpuestas , computación de agregados, clasificación de nodos en una red, elección de líderes, etc.
Algoritmos epidémicos
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 epidémico se emplea a veces cuando se describe un sistema de software en el que se emplea este tipo de propagación de información basada en chismes.
Ver también
- Los protocolos de chismes son solo una clase entre muchas clases de protocolos de red. Ver también sincronía virtual , máquinas de estado distribuidas , algoritmo de 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 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 por un esquema más determinista. Por ejemplo, en el algoritmo NeighbourCast , en lugar de hablar con nodos aleatorios, la información se difunde hablando solo con los nodos vecinos. Hay varios algoritmos que utilizan ideas similares. Un requisito clave al diseñar tales protocolos es que el conjunto vecino traza un gráfico de expansión .
- Enrutamiento
- Tribler , cliente de igual a igual de BitTorrent mediante el protocolo de chismes.
Referencias
- ^ Demers, Alan; Greene, Dan; Hauser, Carl; Irlandés, Wes; Larson, John; Shenker, Scott; Sturgis, Howard; Swinehart, Dan; Terry, Doug (1 de enero de 1987). Algoritmos epidémicos para el mantenimiento de bases de datos replicadas . Actas del Sexto Simposio Anual de ACM sobre Principios de Computación Distribuida . PODC '87. Nueva York, NY, EE.UU .: ACM. págs. 1-12. doi : 10.1145 / 41840.41841 . ISBN 978-0897912396. S2CID 1889203 .
- ^ Jelasity, Márk (1 de enero de 2011). "Chismes" (PDF) . En Serugendo, Giovanna Di Marzo; Gleizes, Marie-Pierre; Karageorgos, Anthony (eds.). Software autoorganizado . Serie de Computación Natural. Springer Berlín Heidelberg. págs. 139-162. doi : 10.1007 / 978-3-642-17348-6_7 . ISBN 9783642173479. S2CID 214970849 .
Aquí hay algunas referencias adicionales a trabajos recientes de la comunidad de chismes. La mayoría de los investigadores consideran que el artículo de Demers es el primero en reconocer realmente el poder de estos protocolos y en proponer un tratamiento formal de los chismes.
- Corrección de un protocolo de membresía basado en chismes. André Allavena, Alan Demers y John Hopcroft. Proc. 24º Simposio de ACM sobre Principios de Computación Distribuida (PODC 2005).
- Multidifusión bimodal. Kenneth P. Birman, Mark Hayden, Oznur Ozkasap, Zhen Xiao, Mihai Budiu y Yaron Minsky. Transacciones ACM sobre sistemas informáticos, vol. 17, No. 2, págs. 41–88, mayo de 1999.
- Transmisión probabilística ligera. Patrick Eugster, Rachid Guerraoui, SB Handurukande, Petr Kouznetsov, Anne-Marie Kermarrec. ACM Transactions on Computer Systems (TOCS) 21: 4, noviembre de 2003.
- Kelips: Construyendo un P2P DHT eficiente y estable a través del aumento de la memoria y la sobrecarga de fondo. Indranil Gupta, Ken Birman, Prakash Linga, Al Demers, Robbert van Renesse. Proc. 2do Taller Internacional sobre Sistemas Peer-to-Peer (IPTPS '03)
- 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.
- HyParView: un protocolo de membresía para una transmisión confiable basada en chismes. João Leitão, José Pereira, Luís Rodrigues. Proc. 37a Conferencia Internacional Anual IEEE / IFIP sobre redes y sistemas confiables (DSN'07)
- Protocolos de estilo epidémico eficientes y adaptables para una multidifusión confiable y escalable. Indranil Gupta, Ayalvadi J. Ganesh, Anne-Marie Kermarrec. Transacciones IEEE en sistemas paralelos y distribuidos, vol. 17, no. 7, págs. 593–605, julio de 2006.
- T-Man: construcción de topología de superposición rápida basada en chismes. Márk Jelasity, Alberto Montresor y Ozalp Babaoglu. Computer Networks, 53 (13): 2321–2339, 2009.
- Árboles de transmisión de epidemias. João Leitão, José Pereira, Luís Rodrigues. Proc. 26th IEEE International Symposium on Reliable Distributed Systems (SRDS'07).
- Agregación basada en chismes en grandes redes dinámicas. Márk Jelasity, Alberto Montresor y Ozalp Babaoglu. ACM Transactions on Computer Systems, 23 (3): 219–252, agosto de 2005.
- Corte ordenado de redes superpuestas muy grandes. Márk Jelasity y Anne-Marie Kermarrec. IEEE P2P, 2006.
- Topologías de superposición de super pares con reconocimiento de 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).
- Cálculo de información agregada basado en chismes. David Kempe, Alin Dobra, Johannes Gehrke. Proc. 44º Simposio Anual del IEEE sobre Fundamentos de las Ciencias de la Computación (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. Revista Elsevier de Sistemas y Software , 2007.
- Construya uno, obtenga uno gratis: Aprovechando 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 caminata aleatoria. Laurent Massoulié, Erwan Le Merrer, Anne-Marie Kermarrec, Ayalvadi Ganesh. Proc. 25 ° ACM PODC . Denver, 2006.
- Acorde a pedido. Alberto Montresor, Márk Jelasity y Ozalp Babaoglu. Proc. Quinta Conferencia sobre Informática Peer-to-Peer (P2P), Konstanz, Alemania, agosto de 2005.
- Introducción a los gráficos expansores. Michael Nielsen. https://pdfs.semanticscholar.org/4c8a/e0bc0dca940264b7ed21fa58f826937f7b12.pdf . Informe técnico, junio de 2005.
- Construcción de redes P2P de bajo diámetro. G. Pandurangan, P. Raghavan, Eli Upfal . En Actas del 42 ° Simposio sobre fundamentos de la informática (FOCS), 2001.
- Astrolabio: una tecnología robusta y escalable para el monitoreo, la administración y la minería de datos de sistemas distribuidos. Robbert van Renesse, Kenneth Birman y Werner Vogels. ACM Transactions on Computer Systems (TOCS) 21: 2, mayo de 2003.
- Explotación de la proximidad semántica en la búsqueda de contenido de igual a igual. S. Voulgaris, A.-M. Kermarrec, L. Massoulie, M. van Steen. Proc. Décimo Taller Internacional sobre Tendencias Futuras en Sistemas de Computación Distribuida (FTDCS 2004), Suzhou, China, mayo de 2004.
- Agregación de reputación en la red peer-to-peer utilizando algoritmo diferencial de chismes. R. Gupta, YN Singh. CoRR, vol. abs / 1210.4301, 2012.
Aunque este libro de texto es antiguo, muchos investigadores de chismes lo citan como una fuente autorizada de información sobre el modelado matemático de los protocolos de chismes y epidemias:
- La teoría matemática de las epidemias. NJT Bailey, 1957. Griffen Press.