Partial Resilient Leader-Follower Consensus in Time-Varying Graphs

1. Problema Investigado

O trabalho aborda o problema de consenso líder-seguidor resiliente em sistemas multiagente sujeitos a agentes adversários (maliciosos ou falhos) em redes com topologia variável no tempo.

• Contexto: Em cenários de consenso padrão, agentes normais tentam concordar com um valor comum ou rastrear um líder. No entanto, agentes adversários podem transmitir informações falsas para degradar o desempenho ou impedir o consenso.
• Limitação do Estado da Arte: A maioria dos algoritmos existentes (como os baseados em Mean Subsequence Reduced - MSR) exige que a rede inteira satisfaça condições topológicas rigorosas de robustez (ex: strong r-robustness) para garantir que todos os seguidores normais atinjam o consenso.
• A Lacuna: Em sistemas reais com restrições de energia ou comunicação, essas condições de robustez global nem sempre são atendidas. O comportamento do sistema quando essas condições falham é pouco explorado. Especificamente, não se sabe quais agentes conseguem convergir e quais falham quando a robustez global não é garantida.
• Objetivo: O artigo propõe estudar o comportamento do sistema sob condições de robustez insuficientes e introduz o conceito de consenso líder-seguidor parcial, onde apenas um subconjunto de seguidores normais consegue rastrear o líder com sucesso, enquanto o restante permanece seguro (dentro da envoltória convexa), mas não necessariamente converge.

2. Metodologia Proposta

Os autores propõem um novo algoritmo distribuído chamado BP-MSR (Bootstrap Percolation and Mean Subsequence Reduced). A abordagem combina dois conceitos principais:

A. Percolação de Bootstrap (BP)

• Os agentes executam um processo local de "ativação" baseado na conectividade da rede.
• Cada agente normal começa inativo, exceto os líderes.
• Em iterações locais, um agente torna-se "ativo" se tiver pelo menos $r$ vizinhos ativos.
• O limiar é definido como $r = 2F + 1$, onde $F$ é o número máximo de agentes adversários em qualquer vizinhança (modelo $F$-local).
• Se um agente permanece ativo após o processo de percolação, ele inferiu localmente que pertence a um subgrafo fortemente $(2F+1)$-robusto em relação aos líderes (e adversários).

B. Atualização de Estado Seletiva (MSR)

• Lógica de Participação: Apenas os agentes que foram marcados como "ativos" ($q_i[t]=1$) participam da atualização do estado de consenso no passo de tempo $t$.
• Filtragem MSR: Os agentes ativos aplicam o algoritmo W-MSR (Mean Subsequence Reduced ponderado), descartando os $F$ maiores e $F$ menores valores recebidos de seus vizinhos antes de calcular a média ponderada.
• Inatividade: Agentes que não atingem o estado "ativo" ($q_i[t]=0$) mantêm seu estado atual ($x_i[t+1] = x_i[t]$), evitando propagar valores potencialmente corrompidos ou não confiáveis.

3. Principais Contribuições

1. Conceito de Consenso Parcial: Formalização da ideia de que, mesmo sem robustez global, um subconjunto de seguidores pode alcançar o consenso resiliente. Isso permite quantificar a degradação de desempenho em vez de apenas falhar completamente.
2. Algoritmo BP-MSR: Desenvolvimento de um algoritmo distribuído onde cada agente decide autonomamente, baseado em sua conectividade local atual, se deve atualizar seu estado ou não.
3. Condições Suficientes Individuais: Diferente de trabalhos anteriores que exigem condições para a rede inteira, este trabalho estabelece condições suficientes para a convergência de agentes individuais.
   • Teorema 1: Estabelece que qualquer seguidor que pertença a um subgrafo fortemente $(2F+1)$-robusto infinitas vezes (ou seja, que se torne ativo infinitas vezes) garantirá o consenso líder-seguidor.
4. Caracterização do Conjunto Convergente:
   • Fornece limites inferiores e superiores para o conjunto de seguidores que convergem ($F_C$), dependendo do comportamento dos adversários (se eles transmitem estados de ativação falsos como 0 ou 1).
   • Demonstra que, mesmo para seguidores não convergentes, o algoritmo garante que seus estados permaneçam dentro da envoltória convexa dos estados dos agentes normais (segurança).

4. Resultados e Validação

Os resultados foram validados através de simulações numéricas utilizando grafos variáveis no tempo que falham em satisfazer as condições de robustez global necessárias para algoritmos tradicionais.

• Comparação com Algoritmos Existentes:
  • Foram comparados o algoritmo proposto (BP-MSR) com o W-MSR padrão e o SW-MSR (Switching W-MSR).
  • Em cenários onde a rede alternava entre topologias que não eram globalmente robustas, os algoritmos W-MSR e SW-MSR falharam em fazer os seguidores rastrear o líder.
  • O BP-MSR conseguiu garantir que um subconjunto específico de seguidores (aqueles que satisfaziam as condições locais de robustez) alcançasse o consenso, enquanto os demais permaneciam estáveis.
• Análise do Conjunto Convergente:
  • As simulações confirmaram as previsões teóricas sobre os limites do conjunto convergente.
  • Quando o agente adversário manipulava seus estados de ativação para "desativar" a rede (enviando 0), o conjunto convergente foi minimizado.
  • Quando o adversário enviava 1 (simulando ser um líder), o conjunto convergente foi maximizado.
  • Os resultados mostraram que o algoritmo é robusto a essas manipulações, garantindo a convergência do subconjunto possível em cada cenário.

5. Significado e Impacto

Este trabalho é significativo por mudar o paradigma de "tudo ou nada" no consenso resiliente:

• Tolerância a Falhas Realista: Reconhece que em redes dinâmicas e restritas, a robustez global é frequentemente impossível. Em vez de abandonar o objetivo, o sistema se adapta para garantir o máximo de consenso possível.
• Garantia de Segurança: Mesmo para os agentes que não conseguem rastrear o líder (não convergentes), o algoritmo impede que seus estados se desviem para valores extremos ou perigosos, mantendo-os dentro de limites seguros definidos pelos agentes normais.
• Aplicabilidade: A abordagem é particularmente útil para redes de sensores, enxames de drones ou sistemas de energia distribuída, onde a conectividade pode flutuar e a presença de nós comprometidos é uma ameaça constante.

Em resumo, o artigo fornece uma ferramenta teórica e prática para projetar sistemas multiagente que continuam operando de forma segura e parcialmente eficaz mesmo quando as condições ideais de rede para consenso total não são atendidas.