Procesos de consenso con nodos tramposos

cartas trampas ases poker

Hace unas semanas tuvo lugar el XIII  Congreso de Física Estadística: uno de los congresos a los que asisto regularmente desde que empecé el Master en Física de Sistemas Complejos. Esta vez fue en Sevilla y presenté un par de trabajos: de uno de ellos ya os he adelantado cosas porque es la parte más técnica del análisis de sentimientos en Twitter que conté en Comunica2, así que no me voy a repetir. Pero el otro trabajo es algo nuevo de este verano: detectar nodos que no siguen el proceso de consenso.

Los procesos de consenso en redes consisten en tratar que un conjunto de nodos de una red, como usuarios en Twitter o Facebook, una red de sensores (por ejemplo, los termómetros en una ciudad o los contadores eléctricos), o cualquier grupo organizado en forma de red, es capaz de realizar cálculos de forma distribuida sin que haya ningún nodo central que los coordine.

Por ejemplo, para calcular la temperatura de una ciudad, podemos tener muchos termómetros repartidos por ella y todos ellos mandan sus medidas de temperatura a un ordenador central que hace la media y nos dice que temperatura hace.

Pues bien, los procesos de consenso permitirían a cada termómetro calcular de forma autónoma ese valor medio de temperatura sin más que intercambiando su propia medida con los vecinos directos y actualizando su valor según esta fórmula:

x_i(t+1) = x_i(t) + \epsilon \sum_{j \in N_i}[x_j(t) - x_i(t)]

Pero para que funcione, se asume que todos los termómetros tienen que hacer lo mismo. Pero ¿qué ocurre si alguno falla? ¿o si alguien, de forma malintencionada, quiere alterar el cálculo?. Un resultado conocido es que, si uno de los nodos de la red no cambia su valor (por ejemplo, pasa a sus vecinos siempre 22º C), el valor medio final es el valor de ese nodo (todos pensarían que la temperatura media es de 22º C).

El trabajo que presenté en el Fises es parte de mi tesis y en él demuestro que

  1. se puede detectar cuando algún nodo de la red no sigue correctamente el proceso de consenso
  2. se puede corregir el valor defectuoso de forma que se calcule el valor correcto
  3. en determinadas condiciones, incluso se puede detectar qué nodo es el que está funcionando mal

Estoy terminando un artículo con los detalles. Mientras, te dejo el póster que envié al congreso (pincha en la imagen para verla más grande).

consensus cheating fises poster