A hierarchy between distributed communication models combining broadcast, congest and local rounds

Abstract

En esta tesis, enmarcada en computación distribuida, se estudian diferentes modelos de comunicación distribuida construidos a partir de la combinación de rondas de modelos pre- existentes tales como broadcast, congest y local. Especfícamente, buscamos construir un lattice, ordenado por inclusión, de los distintos lenguajes de grafos que se pueden decidir a través de combinaciones de los modelos anteriores. Primero, se estudia si existen inclusiones entre los lenguajes que se pueden decidir en una ronda broadcast, una ronda local y una ronda congest. Segundo, se comparan los lenguajes que pueden ser decididos en todas las combinaciones de tamaño dos de los modelos anteriores. Tercero se estudian las combinaciones de tamaño tres de rondas broadcast y local. Cuarto, se estudian algunos modelos con un número constante de rondas broadcast y local. Finalmente, se prueba una cota inferior de un problema de comunicación que se usa para hacer reducciones en las demostraciones anteriores.