Tesis:
Agreement Abstractions in Anonymous and Homonymous Distributed Systems Prone to Failures.
- Autor: TANG, Jian
- Título: Agreement Abstractions in Anonymous and Homonymous Distributed Systems Prone to Failures.
- Fecha: 2015
- Materia: Sin materia definida
- Escuela: E.T.S DE INGENIEROS INFORMÁTICOS
- Departamentos: SISTEMAS INFORMATICOS
- Acceso electrónico: http://oa.upm.es/38766/
- Director/a 1º: JIMENEZ MERINO, José Ernesto
- Director/a 2º: AREVALO VIÑUALES, Sergio
- Resumen: Los modelos de computación distribuida normalmente asumen que todos los procesos en el sistema tienen un identificador distinto, lo que se denomina como sistema epónimo. En este tipo de sistemas distribuidos, el identificador único es útil para resolver los problemas de fuente y destino de la información al transmitir un mensaje (esto normalmente se hace incluyendo en el mensaje un campo con los identificadores origen y destino de los procesos). Un aspecto fundamental de los sistemas epónimos es que disponer de identificadores únicos en los procesos hace fácil romper la simetría del sistema (es decir, cómo distinguir los mensajes transmitidos entre procesos), lo cual es fundamental para resolver los problemas de coordinación. Sin embargo, esta identificación única también acarrea problemas de seguridad y de asignación. En el caso de la seguridad porque garantizar la privacidad no siempre es fácil en ciertos entornos, y en el caso de la asignación única no siempre es posible si el número de procesos es muy elevado y dinámico. Un ejemplo es el caso de redes de sensores con miles de motas con una capacidad muy limitada de proceso y batería. En recientes trabajos se ha demostrado que problemas tradicionales de coordinación tales como elección de líder y consenso pueden ser resueltos sin necesidad de que los procesos del sistema tengan identificadores únicos. Estos sistemas se llaman homónimos cuando varios procesos pueden tener un mismo valor como identificador, y anónimos cuando los procesos no tienen identificadores. Los sistemas homónimos aumentan la privacidad al permitir que más de un proceso utilice el mismo valor como identificador, y los sistemas anónimos directamente permiten trabajar sin la necesidad de identificadores, lo cual garantiza esa privacidad y elimina el problema de asignación de identificadores. En los sistemas distribuidos homónimos y anónimos, el problema de simetría es el principal obstáculo en el diseño de soluciones para solventar los problemas de coordinación. Esta tesis tiene como objetivo proponer diferentes métodos de ruptura de simetría para resolver problemas de coordinación (por ejemplo, la función aleatoria, la técnica de recuento, etc.). En esta tesis se centra principalmente en el diseño de soluciones de consenso, detectores de fallos, acuerdo en valores (set agreement) y distintos tipos de radiado en los sistemas distribuidos anónimos y homónimos. En primer lugar se presenta en la tesis el problema de radiado con tolerancia a fallos en sistemas anónimos con canales de comunicación fiables y con “pérdidas justas” (fair-lossy). Se proponen dos clases de detectores de fallos anónimos (AΘ y AP∗), y ,junto con el detector de fallos ψ ya previamente definido en la literatura, se implementan distintos tipos de radiado. Se estudia también en esta tesis el problema consenso y detectores de fallos en sistemas anónimos. Para ello se demuestra que la clase del detector de fallos AΩ′ es estrictamente más débil que AΩ. También se presenta el primer algoritmo de AΩ′, con lo cual se demuestra que es implementable (frente a AΩ que solo tiene un valor teórico porque está demostrado que no es implementable). Además se presenta un algoritmo de consenso en sistemas anónimos con AΩ′ cuando la mayoría de procesos son correctos. Por último, se resuelve el problema de acuerdo en valores (set agreement) en un sistema homónimo utilizando el detector de fallos más débil (L). Se incluye también un algoritmo para implementar L en dicho sistema homónimo, así como un estudio de las restricciones para su implementabilidad.