Protocolo de población

Modelo de computación distribuida

Un protocolo de población es un modelo de computación distribuida formado por agentes móviles con recursos limitados que se reúnen de manera aleatoria según un gráfico de interacción. Las funciones se calculan actualizando el estado de los agentes cada vez que se encuentran en función de su estado anterior, y el resultado del cálculo se puede leer en los estados de los agentes una vez que el cálculo ha convergido .

Modelo

Hay un conjunto de nodos. Cada nodo es un autómata finito con estados. Una clase importante de protocolos de población son los algoritmos de mayoría, donde el objetivo es calcular el bit de mayoría: cada nodo comienza con un bit de creencia y el objetivo es diseñar un protocolo al final del cual el bit de creencia de cada nodo sea el bit de mayoría inicial correcto. ${\displaystyle N=\{1,2,\ldots ,n\}}$ ${\displaystyle s}$ ${\displaystyle \{0,1\}}$

La versión de tiempo discreto del modelo es la siguiente: en cada punto del tiempo, se selecciona un nodo de manera uniforme y aleatoria. Luego, el nodo se empareja con otro nodo , que se elige de manera uniforme y aleatoria del conjunto de vecinos del nodo . Después, los nodos y intercambian contenidos de memoria y actualizan sus estados. Alternativamente, se puede considerar un modelo de tiempo continuo donde cada nodo tiene un reloj de Poisson que suena a una frecuencia unitaria. Cuando suena el reloj de un nodo, ese nodo se comunica con un vecino aleatorio. ${\displaystyle t=1,2,\ldots }$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle i}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle i}$

Los protocolos a menudo se diseñan para minimizar el tiempo de convergencia o la cantidad de memoria requerida por nodo o ambos. ^[1]

Protocolo de los tres estados

Para el problema de calcular la mayoría (consenso), existe un protocolo bien conocido que requiere solo tres estados de memoria por nodo y que se ha analizado para obtener gráficos de interacción completos. ^{[2] [3]} Este protocolo funciona de la siguiente manera. Deje que cada nodo inicialice su estado de memoria en su bit de creencia inicial. En cada punto del tiempo, cuando dos nodos se comunican, actualizan su estado de acuerdo con la siguiente tabla. Las etiquetas de fila dan el estado del iniciador y las etiquetas de columna el estado del respondedor. ${\displaystyle i}$ ${\displaystyle b_{i}\in \{0,1\}.}$

En otras palabras, si un nodo con creencia se empareja con un nodo con creencia , entonces ambos nodos mantienen su creencia; la actualización es similar si ambas creencias son o ambas son . Sin embargo, si la creencia del iniciador es y la creencia del respondedor es , entonces el respondedor actualiza su creencia a . Si, por otro lado, el iniciador tiene creencia y el respondedor tiene creencia , entonces el respondedor cambia su creencia a . Tenga en cuenta que este protocolo es unidireccional: cada interacción cambia como máximo el estado del respondedor; por lo tanto, se puede implementar con comunicación unidireccional. ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle ?}$ ${\displaystyle 0}$ ${\displaystyle ?}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle ?}$

Angluin, Aspnes y Eisenstat ^[2] demostraron que, a partir de cualquier configuración inicial que no consista en todos los " ", el protocolo de mayoría aproximada de tres estados converge hacia todos los nodos que tienen creencia o hacia todos los nodos que tienen creencia dentro de interacciones con alta probabilidad. Además, el valor elegido será el valor inicial mayoritario no " ", siempre que supere a la minoría por un margen suficiente. ${\displaystyle ?}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle O(n\cdot \log n)}$ ${\displaystyle ?}$

La siguiente imagen muestra la evolución del protocolo de tres estados en un conjunto de nodos, donde un tercio de los nodos tienen un bit de creencia inicial , mientras que los dos tercios restantes tienen un bit de creencia inicial . La fracción de nodos " " (en naranja) comienza en cero, aumenta durante un tiempo y luego vuelve a cero. ${\displaystyle n=500}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle ?}$

Historia

Los protocolos de población fueron introducidos por Dana Angluin et al. ^[4] como uno de los primeros modelos de computación en ser completamente descentralizados y en involucrar agentes con recursos altamente limitados, por ejemplo, aquellos que se encuentran en redes de sensores . Desde entonces, este modelo de computación abstracto encontró aplicaciones en robótica ^[5] y química ^[6] .

Véase también

Inteligencia de enjambre

Referencias

1. Alistarh, Dan; Aspnes, James; Eisenstat, David; Gelashvili, Rati; Rivest, Ronald L. (16 de enero de 2017). "Compensaciones espacio-temporales en protocolos de población". Soda '17. Sociedad de Matemáticas Industriales y Aplicadas: 2560–2579. arXiv : 1602.08032 . Código Bibliográfico :2016arXiv160208032A. {{cite journal}}: Requiere citar revista |journal=( ayuda )
2. Angluin, Dana; Aspnes, James; Eisenstat, David (2007), "Un protocolo de población simple para una mayoría aproximada rápida y robusta", Distributed Computing , Lecture Notes in Computer Science, vol. 4731, Springer Berlin Heidelberg, págs. 20–32, CiteSeerX 10.1.1.80.828 , doi :10.1007/978-3-540-75142-7_5, ISBN  9783540751410
3. Perron, E.; Vasudevan, D.; Vojnovic, M. (abril de 2009). "Uso de tres estados para el consenso binario en gráficos completos". IEEE Infocom 2009. IEEE. págs. 2527–2535. doi :10.1109/infcom.2009.5062181. ISBN. 9781424435128. Número de identificación del sujeto  12683772.
4. Dana Angluin , James Aspnes, Zoë Diamadi, Michael J. Fischer , René Peralta. Computación en redes de sensores de estado finito pasivamente móviles . Computación distribuida , 2006. [1]
5. Gregory Dudek, Michael Jenkin. Principios computacionales de la robótica móvil , Capítulo 10.
6. Ho-Lin Chen, David Doty, David Soloveichik. Cálculo de funciones deterministas con redes de reacciones químicas . Natural Computing , 2014. [2]