Defesa de Proposta de Tese de Doutorado de Alfredo Lima Moura Silva, em 30/08/2024, às 10:00 horas, por videoconferência
Link para defesa: meet.google.com/onh-imbk-umn
Optimization of Propagation Strategies in P2P Communication Networks
Resumo:
O Problema de Tempo Mínimo de Broadcast (MBT) busca minimizar o tempo necessário para que uma mensagem seja propagada a todos os nós de uma rede a partir de nós fontes. O Problema de Tempo Mínimo de Broadcast Ponderado (WMBT) é uma extensão do MBT, considerando pesos nas arestas do grafo para refletir diferentes custos na propagação das mensagens. Além disso, o Problema do Centro de Broadcast Mínimo (MBC) foca em identificar o conjunto ideal de nós fontes que minimiza o tempo total de propagação.
Este trabalho apresenta avanços importantes para o WMBT, incluindo o primeiro modelo de Programação Linear Inteira (ILP) desenvolvido para o problema e um algoritmo de redução que diminui o número de arestas no grafo. Esse algoritmo acelera o processo de decodificação e melhora a qualidade das soluções obtidas. Foi introduzido também duas novas metaheurísticas BRKGA, denominadas BRKGA-MSF e BRKGA-DJ, que demonstram superioridade em relação aos métodos anteriores tanto na qualidade das soluções quanto na eficiência computacional. Adicionalmente, foi proposto um novo limite inferior e uma técnica para a geração de instâncias sintéticas com ótimos conhecidos. Os resultados experimentais confirmam a eficácia das abordagens propostas: em 80 instâncias testadas, BRKGA-MSF encontrou as melhores soluções em 75 casos e BRKGA-DJ em 73 casos. Em um subconjunto de 40 instâncias com ótimos conhecidos, BRKGA-MSF alcançou 10 soluções ótimas e BRKGA-DJ encontrou 8.
Para o problema MBC, o trabalho oferece um ILP, uma metaheurística baseada em BRKGA e um novo limite inferior. A análise comparativa entre o BRKGA e o ILP em 111 instâncias indica que o BRKGA proporciona soluções comparáveis ao ILP, evidenciando sua eficácia como abordagem heurística.
Além dos problemas abordados, o trabalho propõe a exploração do Problema de Tempo Mínimo de Multicast (MinMT) e outras variantes do MBT como futuras linhas de pesquisa.
Abstract:
The Minimum Broadcast Time (MBT) problem aims to minimize the time required for a message to be propagated to all nodes in a network from source nodes. An extension of this problem is the Weighted Minimum Broadcast Time (WMBT) problem, which incorporates weights at the edges of the graph to account for varying costs in message propagation. Additionally, the Minimum Broadcast Center (MBC) problem focuses on identifying the optimal set of source nodes that minimizes the overall message propagation time.
This work introduces significant advancements for the WMBT problem by presenting the first Integer Linear Programming model (ILP) developed for it and a reduction algorithm that decreases the number of edges in the graph. This reduction algorithm accelerates the decoding process and enhances the quality of the solutions obtained. Two new BRKGA metaheuristics, BRKGA-MSF and BRKGA-DJ, are proposed, demonstrating superior performance compared to previous methods in both solution quality and computational efficiency. Additionally, a new lower bound and a technique for generating synthetic instances with known optima are proposed. Experimental results confirm the effectiveness of the proposed approaches: out of 80 tested instances, BRKGA-MSF achieved the best solutions in 75 cases, while BRKGA-DJ excelled in 73 cases. In a subset of 40 instances with known optima, BRKGA-MSF found 10 optimal solutions and BRKGA-DJ found 8.
For the MBC problem, the work contributes a ILP model, a BRKGA-based metaheuristic, and a new lower bound. Comparative analysis between BRKGA and ILP across 111 instances shows that BRKGA provides solutions comparable to ILP, highlighting its effectiveness as a heuristic approach.
The work also proposes future exploration of the Minimum Multicast Time (MinMT) problem and other related MBT variants.
Banca examinadora:
Prof. Luiz Satoru Ochi, UFF – Presidente
Profa. Simone de Lima Martins, UFF
Prof. Rian Gabriel Santos Pinheiro, UFAL
Prof. Bruno Costa e Silva Nogueira, UFAL