Análise de otimização em caso médio para algoritmos de consenso distribuído em grafos regulares

O problema de consenso em computação distribuída envolve uma rede de agentes que visa calcular a média de seus vetores iniciais por meio de comunicação local, representada por um grafo não direcionado. Este artigo foca no estudo desse problema utilizando uma abordagem de análise em caso médio, particularmente sobre grafos regulares. Algoritmos tradicionais para resolver o problema de consenso frequentemente se baseiam em cenários de avaliação de desempenho no pior caso, que podem não refletir o desempenho típico em aplicações do mundo real. Em vez disso, aplicamos análise em caso médio, focando na distribuição espectral esperada dos autovalores para obter uma visão mais realista do desempenho. As principais contribuições incluem a derivação do método ótimo para consenso em grafos regulares, mostrando sua relação com o método da Bola Pesada, analisando sua taxa de convergência assintótica e comparando-o com vários métodos de primeira ordem através de experimentos numéricos.