Algoritmos distribuidos en clases de grafos y un nuevo modelo dinámico de verificación distribuida

Abstract

Esta tesis consta de dos partes. En la primera se estudia el problema del cálculo del diámetro en diferentes modelos de computación distribuida. Se inicia por describir un Proof Labeling Scheme (PLS) para resolver el problema en grafos de intervalos. Luego en el modelo Congest se revisa el mismo problema en grafos split y se resuelve para ciertas configuraciones especiales. Por último, en el modelo Congest, a partir de la estructura especial de los grafos split, se rescatan resultados del modelo Congested Clique como la reconstrucción de grafos de familias hereditarias. En segundo lugar, se presenta un nuevo modelo de computación distribuida, el MID que se caracteriza por variar su estructura en el tiempo. En este modelo, se resuelven algunos problemas directos para mostrar una idea de su poder. Luego, se estudia su comportamiento para detectar subgrafos de cuatro nodos y además se encuentra una cota inferior en el problema de la detección del clique máximo. Finalmente se compara este modelo con otros modelos similares, como el modelo OLOCAL y cómo se enfrenta a problemas que se pueden resolver en esos modelos.