Estudio de protocolos distribuidos interactivos sobre clases de grafos hereditarios

Abstract

En el presente trabajo se estudian protocolos distribuidos para el reconocimiento de ciertas clases de grafos geométricos. En estos protocolos, existe un probador con poder ilimitado pero no confiable, llamado Merlín, que le entrega mensajes a los nodos de un grafo, buscando convencerlos de que el grafo cumple un cierto predicado. Posterior a que Merlín entrega los mensajes, los nodos pueden entrar de inmediato en la etapa de verificación, durante la cual intercambian los mensajes que poseen con sus vecinos y, cada uno, de forma local, decide con esta colección de mensajes si acepta o rechaza. Se debe cumplir que si el grafo satisface el predicado, entonces existe una asignación de mensajes de Merlín a los nodos que hace que todos acepten. Si no cumple el predicado, para cualquier colección de mensajes entregados por Merlín, al menos un nodo debe rechazar. Este modelo, donde inmediatamente después de recibir los mensajes dados por Merlín los nodos entran en la etapa de verificación, es el modelo llamado proof labeling schemes. Si se permite que haya más rondas de interacción entre los nodos y Merlín, al modelo lo llamamos protocolos interactivos distribuidos.

El primer capítulo se dedica a definir toda la teoría necesaria de Teoría de Grafos y algunos resultados de Teoría de Números, junto con protocolos distribuidos para resolver ciertos problemas particulares que son usados como subrutinas en los protocolos distribuidos aquí diseñados. También se introducen las clases de grafos geométricos de intersección que son estudiados en este trabajo: Grafos de permutación, trapezoidales, circulares, k-circulares-poligonales y cuadrado unitario.

En el segundo capítulo, se estudian los grafos de permutación y trapezoidales, donde se da una caracterización de ellos y un protocolo proof labeling scheme para reconocerlos.

En el tercer capítulo se introducen y resuelven de forma distribuida dos problemas independientes, llamados CORRESPONDING ORDER PROBLEM y LINEAR ASSIGNATION PROBLEM, que permiten compartir información verificable entre nodos que no son vecinos.

En el cuarto capítulo se estudian las clases de grafos circulares, $k$-circulares-poligonales y de cuadrado-unitario. Para estas tres clases se presentan algoritmos distribuidos interactivos que necesitan de 3 rondas de interacción alternada entre Merlín y los nodos para reconocerlas.

Finalmente, en el quinto capítulo se prueba que el largo de los mensajes que son necesarios para reconocer cualquiera de las clases estudiadas en este trabajo es de \Omega(log n).

Finalmente, en el quinto capítulo se prueba que el largo de los mensajes que son necesarios para reconocer cualquiera de las clases estudiadas en este trabajo es de \Omega(\og n). Esto implica que los algoritmos presentados en el Capítulo 2 son óptimos de acuerdo a información compartida, y los protocolos del Capítulo 4 son óptimos en cuanto a información compartida, y solo se podrían mejorar disminuyendo la cantidad de rondas de interacción.