Protocolo de población

Un protocolo de población es un modelo de computación distribuida formado por agentes móviles con recursos limitados que se encuentran de forma aleatoria según un grafo de interacción . Las funciones se calculan actualizando el estado de los agentes cada vez que se encuentran, basándose en 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.

Hay un conjunto${\displaystyle N=\{1,2,\ldots ,n\}}$de nodos. Cada nodo es un autómata finito con${\displaystyle s}$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 en${\displaystyle \{0,1\}}$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.

La versión en tiempo discreto del modelo es la siguiente: en cada punto${\displaystyle t=1,2,\ldots }$con el tiempo, algún nodo${\displaystyle i}$se selecciona uniformemente al azar. Luego el nodo se empareja con otro nodo.${\displaystyle j}$, que se elige uniformemente al azar del conjunto de vecinos del nodo${\displaystyle i}$. Posteriormente, nodos${\displaystyle i}$y${\displaystyle j}$intercambian contenidos de memoria y actualizan sus estados. Alternativamente, se puede considerar un modelo de tiempo continuo donde cada nodo${\displaystyle i}$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.

Los protocolos suelen diseñarse para minimizar el tiempo de convergencia o la cantidad de memoria requerida por nodo, o ambas cosas. ^{[ 1 ]}

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 ha sido analizado para grafos de interacción completos. ^{[ 2 ] [ 3 ]} Este protocolo funciona de la siguiente manera. Sea cada nodo${\displaystyle i}$inicializar su estado de memoria a su bit de creencia inicial${\displaystyle b_{i}\in \{0,1\}.}$En cada instante en que dos nodos se comunican, actualizan su estado según la siguiente tabla. Las etiquetas de las filas indican el estado del iniciador y las etiquetas de las columnas, el estado del respondedor.

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

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

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

El protocolo de tres estados resuelve el problema de la mayoría aproximada, en el que la respuesta correcta se alcanza solo con alta probabilidad y solo cuando el desequilibrio inicial es suficientemente grande. Una variante más difícil es la mayoría exacta, donde la población debe estabilizarse en el verdadero valor de la mayoría con probabilidad 1 independientemente de cuán pequeño sea el sesgo inicial. ^{[ 4 ]} En grafos de interacción completos, la mayoría exacta exhibe compensaciones espacio-temporales: cualquier protocolo de estado constante es comparativamente lento, mientras que los protocolos que usan estados Θ(log n) pueden estabilizarse en el tiempo asintóticamente óptimo Θ(n log n) . ^{[ 5 ]} Un protocolo simple de cuatro estados resuelve la mayoría exacta en cualquier grafo de interacción conectado, no solo en los completos. ^{[ 6 ]} Para grafos generales, la complejidad temporal y espacial de la mayoría exacta puede analizarse en términos del tiempo de relajación del paseo aleatorio inducido por el planificador y el desequilibrio de grado del grafo; en grafos expansores regulares esto produce protocolos que coinciden con el rendimiento de tiempo casi óptimo de los estados Θ(log n) conocido para grafos completos. ^{[ 7 ]}

Los protocolos de población fueron introducidos por Dana Angluin et al. ^{[ 8 ]} como uno de los primeros modelos de computación totalmente descentralizados que involucraban agentes con recursos muy limitados, por ejemplo, los que se encuentran en las redes de sensores . Desde entonces, este modelo de computación abstracto ha encontrado aplicaciones en robótica ^{[ 9 ]} y química ^{[ 10 ]} .

Inteligencia de enjambre