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.

Para los sistemas de computaci�on actuales, la habilidad de utilizar din�amicamente los recursos que se alojan en la red se ha convertido en un factor clave de �exito. Conforme la red sigue creciendo se hace cada vez m�as dif�ÿcil encontrar soluciones a los problemas que los usuarios plantean al sistema computacional. Los usuarios saben habitualmente qu�e quieren hacer, pero no c�omo hacerlo. Si el usuario conoce el objetivo que desea alcanzar es m�as sencillo ayudarle mediante el uso de una aproximaci�on diferente. Nuestra propuesta se orienta en incrementar los niveles de abstracci�on proporcionados por el sistema operativo y sus servicios. Esto nos permitir�a ofrecer una capa de ejecuci�on del sistema operativo perfectamente integrada en la red y con mecanismos de seguridad y fiabilidad que no pueden estar disponibles en niveles m�as bajos de abstracci�on de los sistemas operativos actuales. Esta evoluci�on comienza por cambiar el paradigma utilizado en el dise �no del SO. Cambiar las abstracciones que el SO utiliza est�a �ÿntimamente relacionado con el paradigma utilizado, y al cambiar este paradigma necesitamos proponer un nuevo m�odulo de ejecuci�on para el SO que soporte dicho paradigma. Este m�odulo de ejecuci�on es presentado tambi�en en este trabajo. Para solventar estos problemas presentamos un nuevo paradigma de Computaci�on Distribuida basada en Objetivos. Para implementar el paradigma se ha dise �nado una arquitectura de sistema operativo orientado a objetivos. En este SO el usuario expresa sus objetivos y el SO se encarga de ayudar al usuario a alcanzar sus objetivos por medio de una aproximaci�on orientada a servicios. Adem�as se presenta un simulador que da soporte a este paradigma, siguiendo los requisitos planteados en este trabajo. Algunos de estos requisitos son par�ametros que comprenden c�omo definirlas propiedades de un objetivo o los que definen la bondad de un plan que cumple dichos objetivos. Algunos de los par�ametros que est�an implicado / Palanca Cámara, J. (2012). Computación distribuida basada en objetivos [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/17702

El objetivo general del presente trabajo es poder interpretar un subconjunto del lenguaje de programación AmbientTalk en un dispositivo móvil liviano que sea capaz de interactuar con otros programas desarrollados en AmbientTalk alojados en otros dispositivos que no sean necesariamente del mismo tipo de equipo. El dispositivo móvil liviano usado para esta memoria es un Sun SPOT. El intérprete oficial de AmbientTalk está desarrollado para Java ME CDC, mientras que los Sun SPOT poseen como plataforma de desarrollo Java ME CLDC. Una de las diferencias importantes entre ambos es que tanto reflexión como serialización no están presentes en CLDC, mientras que si lo están en CDC. Ambas son características muy usadas y muy imprescindibles para el intérprete oficial, por lo que se hace necesario replantear un nuevo intérprete para los Sun SPOT. Debido a las capacidades de cómputo limitadas de un Sun SPOT, se decidió separar la plataforma en dos aplicaciones que corren en máquinas distintas: un compilador que lea código fuente AmbientTalk y que genere un archivo binario, y un intérprete AmbientTalk que lea ese archivo binario e interprete el programa almacenado en él en un Sun SPOT. A cada una de las aplicaciones se le realizó un diseño de arquitectura lógica, separando los componentes en módulos semi desacoplados. Luego se realizó una validación al intérprete, realizando para tal efecto una aplicación ejemplo de programación distribuida consistente en un sistema controlador de luces remotas. Se realizó esta aplicación tanto para Java ME CLDC, como para AmbientTalk, mostrando que mientras la aplicación en Java ME CLDC es más eficiente, la aplicación en AmbientTalk fue más simple de desarrollar. Finalmente se concluye que esta plataforma es un paso para tener una implementación de AmbientTalk en toda la gama de dispositivos con Java y que AmbientTalk permite disminuir el tiempo de programación para aplicaciones distribuidas en un Sun SPOT.