Optimization of Propagation Strategies in P2P Communication Networks

Será defendida no dia 15 de abril de 2026, às 09:00 horas, por videoconferência, a Tese de Doutorado intitulada “Optimization of Propagation Strategies in P2P Communication Networks”, do candidato ao título de Doutor em Computação – Alfredo Lima Moura Silva.

Link para defesa: https://meet.google.com/hfo-wuuy-zpm

Resumo:

A difusão de informações (broadcast) é uma operação fundamental em redes de comunicação, especialmente em sistemas peer-to-peer (P2P), nos quais influencia diretamente a eficiência, a escalabilidade e a confiabilidade de aplicações distribuídas de grande escala. Esta tese investiga aspectos teóricos e algorítmicos da otimização de broadcast em modelos de redes baseados em grafos, com foco no problema do Minimum Broadcast Time (MBT) e em suas extensões relevantes. São estudados quatro problemas intimamente relacionados: o Minimum Broadcast Time (MBT), o Weighted Minimum Broadcast Time (WMBT), o Minimum Broadcast p-Center (MBpC) e o Weighted Minimum Broadcast $p$-Center (WMBpC). Sob uma perspectiva teórica, analisam-se propriedades de complexidade computacional, estabelecendo-se resultados de NP-dificuldade, identificando-se casos solúveis em tempo polinomial e derivando-se resultados de inaproximabilidade e de aproximação.

Além disso, esta tese propõe métodos de solução exatos, heurísticos e híbridos. Para o problema WMBT, é apresentada a primeira formulação de programação linear inteira (ILP) que considera simultaneamente atrasos de transmissão em vértices e arestas, bem como um novo limite inferior, regras de redução e fixação de variáveis e dois algoritmos genéticos de chaves aleatórias enviesadas (BRKGAs) com decodificadores específicos ao problema. Adicionalmente, é proposta uma metodologia para a geração de instâncias sintéticas de benchmark com soluções ótimas conhecidas. Para os problemas MBpC e WMBpC, são apresentadas uma formulação ILP unificada, um limite inferior comum, heurísticas gulosas, metaheurísticas baseadas em BRKGA com múltiplas estratégias de decodificação e uma abordagem matheurística.

Extensos experimentos computacionais mostram que os métodos propostos superam consistentemente as abordagens existentes em qualidade das soluções e eficiência computacional. De modo geral, esta tese avança o estado da arte na otimização de broadcast em redes P2P, fornecendo novos insights teóricos, modelos exatos eficazes e algoritmos heurísticos robustos, além de indicar direções promissoras para pesquisas futuras.

Abstract:

Broadcasting is a fundamental operation in communication networks. In the context of peer-to-peer (P2P) systems, it directly influences the efficiency, scalability, and reliability of large-scale distributed applications. This thesis investigates theoretical and algorithmic aspects of broadcast optimization on graph-based network models, with a focus on the Minimum Broadcast Time (MBT) problem and several of its relevant extensions. We study four closely related problems: the Minimum Broadcast Time (MBT), the Weighted Minimum Broadcast Time (WMBT), the Minimum Broadcast p-Center (MBpC), and the Weighted Minimum Broadcast p-Center (WMBpC). From a theoretical perspective, we analyze computational complexity properties, establishing \np-hardness results, identifying polynomially solvable cases, and deriving inapproximability and approximation results for selected variants.

In particular, we present new NP-hardness results and an approximation algorithm for the MBpC problem.

Moreover, this thesis proposes exact, heuristic, and hybrid solution methods. For the WMBT problem, we introduce the first integer linear programming (ILP) formulation that simultaneously accounts for vertex and edge transmission delays, a novel lower bound, reduction and variable-fixing rules, and two biased random-key genetic algorithms (BRKGAs) with problem-specific decoders. Additionally, we propose a methodology for generating synthetic benchmark instances with known optimal solutions. For the MBpC and WMBpC problems, we present a unified ILP formulation, a common lower bound, greedy heuristics, BRKGA-based metaheuristics with multiple decoding strategies, and a matheuristic approach.

Across all studied problems, extensive computational experiments demonstrate that the proposed methods consistently outperform existing approaches with respect to both solution quality and computational efficiency. Overall, the results of this thesis advance the state of the art in broadcast optimization for P2P networks by providing new theoretical insights, effective exact models, and robust heuristic algorithms, while also outlining promising directions for future research on multicast and constrained broadcast variants.

Banca  examinadora:

Prof. Luiz Satoru Ochi, UFF – Presidente

Prof. Fabio Protti, UFF

Prof. Igor Machado Coelho, UFF

Prof. Rian Gabriel Santos Pinheiro, UFAL

Prof. Marcone Jamilson Freitas Souza, UFOP

Prof. Bruno Costa e Silva Nogueira, UFAL