Ingeniero Civil Matemático / La presente memoria se enmarca en el contexto de la computación distribuida. Esta es un área de las ciencias de la computación relativamente reciente, que surge ante la necesidad de un nuevo paradigma de computación, capaz de trabajar con cantidades masivas de datos, como son, por ejemplo, las redes sociales. En particular, se estudia la complejidad del problema CONEXIDAD de un grafo $G=(V,E)$ en el modelo computacional number-in-hand. Este problema consiste en decidir si un grafo $G$ es o no conexo. Por otro lado, a grandes rasgos, la complejidad que se considera aquí mide el largo de los mensajes (en bits) que los nodos deben comunicar para decidir CONEXIDAD. En primer lugar, se demuestra que la complejidad, en el caso en que el grafo $G$ es arbitrario, es al menos $f(n)$, donde $f(n) = \log n - (\log \log n +1+ \log n /n)$. Sin embargo, esta fórmula no aporta información alguna cuando el grafo $G$ posee $n<27$ nodos, pues $f(n) \leq 1$ para tales valores. Es decir, indica que la cantidad de bits que se tienen que comunicar es al menos $\leq 1$, lo que es evidente. Por esta razón, se profundiza el estudio analizando grafos pequeños, y se demuestra que 1 bit no es suficiente para decidir el problema en tal caso. Por otro lado, la cota expuesta se obtiene a partir de una reducción que construye un grafo de grado no acotado. Por lo tanto, $f(n)$ puede ser poco ajustada para la familia de grafos de grado acotado. Así pues, se complementa el trabajo restringiéndose a esta clase de grafos, con el fin de saber si en tal caso existe una mejor cota para la complejidad de CONEXIDAD en el modelo number-in-hand. Usando técnicas de complejidad comunicacional se encuentra una cota inferior de $\Omega(\log n)$. Más aún, se demuestra que esta cota es ajustada para esta clase de grafos.

Ingeniera Civil Matemático / La presente memoria tiene como objetivo el estudio del problema de reconstrucción de redes en sistemas distribuidos que utilizan mensajes pequeños. Esto resulta de gran interés en la actualidad debido a la existencia de redes de gran tamaño, tales como la World Wide Web y las redes sociales, que no necesariamente se encuentran almacenadas en su totalidad en un solo lugar. Debido a esto surge el interés de estudiar aspectos particulares de la topología de las redes de este tipo, coloquialmente denominadas Small World Networks. En primer lugar se elabora un protocolo donde todos los nodos o procesadores, utili- zando su información local, colaboran para reconstruir el grafo completo intercambiando información en rounds. Este protocolo es capaz de reconstruir cualquier grafo en 2 rounds. En particular, funcionará utilizando una cantidad pequeña de información local para cla- ses de grafos que exhiben una topología especial, que se denominará Popularidad Local (se dice que un grafo es k-Localmente-Popular si para todo nodo en la red, éste tiene a lo más k vecinos con grado mayor o igual a él). Posteriormente, se expone el modelo desarrollado por Barabási y Albert, quienes mo- tivados por simular de mejor forma la topología de redes que surgen en la actualidad, proponen un modelo que evoluciona en etapas discretas. Partiendo con un grafo pequeño, en cada etapa se agrega un nuevo nodo que se conecta con m nodos existentes en el grafo utilizando la regla Preferential Attachment, en la cual la probabilidad de conectarse con un nodo depende de su grado. Luego se introduce la noción de Popularidad-Local-Débil para grafos aleatorios. Se analiza la topología de los árboles del tipo Small World utilizando el modelo de Bara-bási y Albert con parámetro m = 1 y se demuestra que esta clase de grafos es 9-Débil- 4 Localmente-Popular. Por lo tanto, estos grafos se pueden reconstruir en 2 rounds utilizando información local de tamaño logarítmico. Finalmente se estudia experimentalmente la topología de los grafos generales de Ba- rabási y Albert y se conjetura que estos grafos son k-Débil-Localmente-Populares donde k sólo depende de m y no depende del tamaño del grafo. Ésto podría constituir un gran avance dado que permitiría reconstruir eficientemente las grandes redes de la actualidad.