En la actualidad hacemos uso de sistemas distribuidos todos los días, desde computadoras personales hasta la web. Dada su presencia, es importante desarrollar una teoría del cómputo distribuido que permita entender estos sistemas de mejor forma. Existen varios ejemplos en los que estudios formales de problemas que modelan situaciones de la vida real, impactan al cabo de un tiempo en el diseño e implementación de lo sistemas distribuidos reales. En este proyecto proponemos estudiar formlamente tres problemas que tienen implicaciones tanto teóricas como prácticas: (1) la relación entre las colas y la familia de operaciones Common2, (2) algoritmos de renombramiento y (3) algoritmos de ruteo en redes tolerantes a fallos. Estos problemas serán estudiados en modelos de computación que a lo largo del tiempo han demostrado su valía, no solo teórica, sino práctica también.

La intención del proyecto es contribuir al desarrollo de una teoría del cómputo distribuido sólida y profunda, que pueda servir de base para entender el comportamiento de los sistemas distribuidos reales. En este proyecto de investigación planeamos estudiar formalmente tres problemas que son importantes tanto por sus implicaciones teóricas como prácticas. 1) Determinar la relación entre las estructuras de datos de las colas y la familia Common2. Este problema lleva abierto más de 20 años, y la solución al problema daría información importante acerca de la naturaleza de estas estructuras de datos que se usan todos los días en los sistemas distribuidos reales. 2) Algoritmos de renombramiento. El problema del renombramiento ha sido ampliamente estudiado desde el momento de su definción a finales de los 80's, y es considerado hoy en día todo un paradigma para el estudio de la noción del rompimiento de simetrías que aparece constantement en el desarrollo e implementación de sistemas reales. Sin embargo, aún hay problemas importantes que resolver. Algoritmos nuevos y eficientes o resultados de imposibilidad tendrían un valor indudable desde un enfoque tanto teórico como práctico. 3) Algoritmos de ruteo tolerantes a fallos. Sin duda el ruteo de mensajes en redes de computadoras es un problema fundamental. El desarrollo de algoritmos de ruteo tolerantes a fallos tiene gran valor dado que actualmente se conocen soluciones tolerantes a fallos muy limitadas en lo que se refiere a la tolerancia a fallos; es decir, estas soluciones asumen que no ocurren, u ocurren muy pocos fallos en el sistema, algo que en la actualidad es irreal.