Ingeniero Civil Matemático / La computación distribuida, rama de las ciencias de la computación, se focaliza en estu-
diar sistemas distribuidos, tales como internet, redes sociales o protocolos de mensajería. La
información se encuentra distribuida entre las distintas entidades que conforman el sistema
y el objetivo último es resolver algún problema global. Para ello las distintas entidades se
comunican mediante los canales de la red hasta que encuentran la solución.
Esta memoria comienza estudiando el problema de la degenerancia de un grafo en los
modelos de computación distribuida UCAST y BCAST, donde la degenerancia de un grafo G
se define como el máximo grado mínimo de un subgrafo F de G. Los modelos distribuidos
UCAST y BCAST corresponden a redes completas de n individuos, los cuales se comunican
de manera síncrona por los canales de la red en rondas. En el primer caso, cada individuo
por ronda puede enviar diferentes mensajes por cada uno de sus canales. En el segundo caso,
cada individuo por ronda envía a través de sus canales el mismo mensaje. En general, se suele
decir que BCAST es una restricción de UCAST.
Primero, se construye un protocolo aleatorio en el modelo UCAST que calcula una (1 + ε)-
aproximación de la degenerancia en O(log n) rondas con mensajes de largo O(log n). En
el modelo BCAST se demuestra que el problema de calcular la degenerancia es difícil en 1
ronda. Más específicamente, se demuestra que todo protocolo aleatorio de 1 ronda que calcule
exactamente la degenerancia debe enviar un mensaje de largo Ω(n). En el mismo modelo, se
construye un protocolo aleatorio de 2 rondas con mensajes de largo O(log 2 n) que calcula una
(1 + ε)-aproximación de la degenerancia para grafos α-densos. Finalmente, se construye un
protocolo determinista que calcula una (2 + ε)-aproximación de la degenerancia en O(log n)
rondas con mensajes de largo O(log n).
Como segunda parte de este trabajo, y motivado por el protocolo en BCAST que calcula
una (2 + ε)-aproximación de la degenerancia, se estudia la siguiente dinámica sobre grafos:
Durante cada iteración, eliminar todos los vértices que tengan grado a lo más el grado prome-
dio del grafo +1. Se conjetura que para todo grafo G de n vértices la dinámica toma O(log n)
iteraciones en vaciar el grafo. Se aborda el problema estudiando clases de grafos tales como:
bosques, grafos planares, grafos con degenerancia acotada y grafos unión disjunta de cliques.
Finalmente, se estudian diversos problemas en el modelo BCAST. Se comienza estudiando
el problema de calcular el conjunto independiente maximal con un vértice fijo. Se prueba que
el problema es difícil en 1 ronda y luego se contruye un protocolo que en O(log n) rondas,
usando mensaje de largo O(log n), calcula el conjunto independiente. Se estudia también el
problema de calcular el número cromático de un grafo. Se prueba que el problema resulta
difícil en 1 ronda. Concluyendo el capítulo, se estudian los problemas de encontrar conjuntos
dominantes de tamaño k y conjuntos -dominantes de tamaño k, en ambos casos se demuestra
que los problemas son difíciles en 1 ronda. / Este trabajo ha sido parcialmente financiado por Proyecto Fondecyt 1130061
| Identifer | oai:union.ndltd.org:UCHILE/oai:repositorio.uchile.cl:2250/142770 |
| Date | January 2016 |
| Creators | Pérez Salazar, Sebastián Walter |
| Contributors | Rapaport Zimermann, Iván, Matamala Vásquez, Martín, Han, Hiep |
| Publisher | Universidad de Chile |
| Source Sets | Universidad de Chile |
| Language | Spanish |
| Detected Language | Spanish |
| Type | Tesis |
| Rights | Attribution-NonCommercial-NoDerivs 3.0 Chile, http://creativecommons.org/licenses/by-nc-nd/3.0/cl/ |
Page generated in 0.0017 seconds