Partial Resilient Leader-Follower Consensus in Time-Varying Graphs

Resumen Técnico: Consenso Parcial Resiliente Líder-Seguidor

1. Planteamiento del Problema

El consenso en sistemas multiagente es fundamental para la coordinación, pero es vulnerable a agentes adversarios (o "maliciosos") que transmiten información falsa, lo que puede degradar el rendimiento o causar el fallo total del sistema.

• Contexto Actual: La mayoría de los algoritmos de consenso resiliente existentes (como los basados en Mean Subsequence Reduced o MSR) requieren que toda la red cumpla estrictamente con condiciones topológicas de robustez (ej. $r$-robustez fuerte o $(r, s)$-robustez) en todo momento para garantizar que todos los seguidores normales converjan al estado del líder.
• Brecha de Conocimiento: En sistemas prácticos con restricciones de energía o comunicación, garantizar que la red completa cumpla estas condiciones de robustez es difícil. Sin embargo, el comportamiento del sistema cuando estas condiciones no se cumplen (es decir, en entornos no ideales) ha sido poco explorado.
• Objetivo: El trabajo busca caracterizar el comportamiento del sistema cuando la robustez global falla. En lugar de exigir que todos los seguidores converjan, se introduce el concepto de consenso líder-seguidor parcial, donde un subconjunto de seguidores normales logra rastrear exitosamente al líder, mientras que el resto permanece acotado pero no necesariamente converge.

2. Metodología Propuesta: Algoritmo BP-MSR

Los autores proponen un nuevo algoritmo distribuido llamado Bootstrap Percolation and Mean Subsequence Reduced (BP-MSR). La idea central es permitir que los agentes decidan localmente cuándo participar en el protocolo de consenso basándose en su conectividad actual.

El algoritmo consta de dos fases principales en cada paso de tiempo $t$:

1. Fase de Percolación de Arranque (Bootstrap Percolation - BP):

   • Los agentes ejecutan un proceso de propagación de activación para determinar si pertenecen a un subgrafo suficientemente robusto.
   • Se define un umbral $r = 2F + 1$, donde $F$ es el número máximo de adversarios locales.
   • Los líderes inician como "activos". Un seguidor se vuelve activo ($q_i[t]=1$) si tiene al menos $r$ vecinos activos.
   • Este proceso se realiza localmente y de forma sincronizada. Si un agente no logra activarse, significa que no tiene suficientes conexiones seguras en ese instante.

2. Fase de Actualización de Estado (MSR):

   • Si el agente está activo ($q_i[t]=1$): Participa en el protocolo de consenso estándar (W-MSR). Descarta los $F$ valores más altos y los $F$ más bajos recibidos de sus vecinos y actualiza su estado como una combinación convexa de los restantes.
   • Si el agente no está activo ($q_i[t]=0$): No actualiza su estado ni transmite información en ese paso de tiempo. Se mantiene en su estado anterior.

Ventaja Clave: Al restringir la actualización solo a agentes que verifican localmente que pertenecen a un subgrafo fuertemente robusto, el algoritmo evita que valores adversarios se propaguen a través de la red en momentos de baja conectividad.

3. Contribuciones Principales

• Definición de Consenso Parcial Resiliente: Se formaliza la idea de que, incluso si la red completa no es robusta, un subconjunto de seguidores ($F_C$) puede lograr el consenso con el líder, mientras que el resto ($F'_C$) no converge pero permanece acotado dentro del casco convexo de los estados normales.
• Algoritmo BP-MSR: Desarrollo de un algoritmo distribuido que no requiere conocimiento global de la topología ni garantías de robustez de toda la red, sino que opera bajo condiciones locales dinámicas.
• Condiciones Suficientes Individuales: A diferencia de trabajos previos que requieren condiciones globales para la convergencia de todos, este trabajo establece condiciones suficientes para la convergencia de individuos. Se demuestra que un seguidor converge si pertenece infinitamente a menudo a un subgrafo fuertemente $(2F+1)$-robusto respecto a los líderes y adversarios.
• Caracterización del Conjunto Convergente: Se proporcionan cotas (subconjunto y superconjunto) para el conjunto de seguidores que convergen, dependiendo de cómo los adversarios manipulan sus estados de activación (enviando 0 o 1).

4. Resultados Teóricos y Simulaciones

• Teorema 1 (Convergencia Parcial): Se demuestra que si un seguidor normal se activa infinitamente a menudo (es decir, $q_i[t]=1$ para infinitos $t$), su estado convergerá al del líder. Además, se garantiza que todos los estados de los agentes normales permanecen dentro del casco convexo de sus valores iniciales y del líder, asegurando seguridad incluso para los no convergentes.
• Corolario 1 (Convergencia Total): Si la red completa satisface las condiciones de robustez en un sentido unionado a lo largo del tiempo, el algoritmo BP-MSR recupera el consenso resiliente completo (todos los seguidores convergen).
• Validación por Simulación:
  • Se comparó BP-MSR con algoritmos tradicionales (W-MSR y SW-MSR) en grafos de tiempo variable que no cumplen las condiciones de robustez global requeridas por los métodos existentes.
  • Resultado: Los algoritmos tradicionales fallaron completamente (los seguidores no rastrearon al líder). En contraste, BP-MSR logró que un subconjunto específico de seguidores ({6, 7, 8} en el ejemplo) alcanzara el consenso, mientras que los demás permanecieron acotados.
  • Se validó empíricamente que el tamaño del conjunto convergente varía según el comportamiento de los adversarios, alineándose con las cotas teóricas propuestas en la Proposición 1.

5. Significado e Impacto

Este trabajo es significativo porque cambia el paradigma de la tolerancia a fallos en redes dinámicas:

1. Realismo Práctico: Reconoce que en sistemas reales (drones, sensores IoT) la robustez global es difícil de mantener. En lugar de fallar catastróficamente, el sistema degrada su rendimiento de manera controlada, permitiendo que una parte funcional de la red siga operando correctamente.
2. Robustez Local: Permite que los agentes tomen decisiones autónomas basadas en su entorno inmediato, sin depender de una supervisión centralizada o de garantías de red global.
3. Seguridad: Garantiza que, incluso en el peor de los casos (donde ningún seguidor converge), los estados de los agentes no se desvían arbitrariamente, manteniéndose acotados.

En conclusión, el artículo ofrece una solución robusta para entornos de comunicación inestables y hostiles, demostrando que el consenso parcial es una meta alcanzable y valiosa cuando el consenso total es imposible.