Sistemas distribuidos: coordinación y acuerdo (II)
Segundo artículo de la serie de cinco publicaciones breves relacionadas con los sistemas distribuidos.
Coordinación y acuerdo
En los sistemas distribuidos es fundamental, dado un conjunto de procesos, coordinar sus acciones y ponerse de acuerdo en uno o más valores. Para ello se presentan una serie de algoritmos con objetivos variados.
Exclusión mutua distribuida
Los procesos distribuidos necesitan frecuentemente coordinar sus actividades. Si un conjunto de procesos comparte un recurso, o un conjunto de recursos, se requiere con frecuencia la exclusión mutua para prevenir interferencias y asegurar la consistencia cuando se accede a los recursos.
Dicho problema es conocido como el problema de la sección crítica en el dominio de los SO. En los sistemas distribuidos se requiere una solución que esté basada exclusivamente en el paso de mensajes.
Algoritmos para la exclusión mutua
Lo requisitos esenciales para la exclusión mutua son:
- EM1 (seguridad): a lo sumo un proceso puede estar ejecutándose un vez el la sección crítica.
- EM2 (superveniencia): las peticiones para entrar y salir de la sección crítica al final deben ser concedidas. Esto implica la inexistencia de deadlocks e inanición.
- EM3 (ordenación): si una petición parar entrar en la SC ocurrió antes que otra, entonces la entrada en la SC se garantiza en ese orden.
- Algoritmo del servidor central
Es la forma más simple de conseguir exclusión mutua, se logra empleando un servidor que da los permisos para entrar en la sección crítica.
El algoritmo no satisface EM3 y el servidor puede convertirse en un cuello de botella para el rendimiento del sistema.
- Algoritmo basado en un anillo
Es una de las maneras más simples de conseguir exclusión mutua entre procesos. La idea se basa en conseguir la exclusión obteniendo un testigo mediante un mensaje que se pasa de un proceso a otro en un a única dirección alrededor del anillo. Si un proceso no requiere entrar en la SC cuando recibe el testigo se lo pasa a su vecino. Si lo requiere espera a recibirlo y acto seguido lo retiene, liberándolo cuando el proceso salga de la SC.
El algoritmo satisface EM1 y EM2 y cabe destacar que consume continuamente ancho de banda.
- Algoritmo que usa multidifusión y relojes lógicos (Ricart y Agrawala)
La idea básica es que los procesos que necesitan entrar en una sección crítica envíen un mensaje de petición mediante radiodifusión y puedan entrar en ella solamente cuando el resto de procesos hayan respondido al mensaje.
El algoritmo satisface EM1 y e EM3. Su principal ventaja es que el retraso de sincronización es de solamente el tiempo de transmisión de un mensaje, mientras que en el resto de algoritmos se incurría en un retraso de sincronización por mensajes de ida y vuelta.
- Algoritmos de votación de Maekawa
Mamoru Maekawa observó que para que un proceso entrase en la sección crítica no era necesario que todos los procesos de una categoría pareja a la suya le permitiesen acceso. Los procesos solo necesitan obtener permiso de parte de un subconjunto de sus pares, siempre que los subconjuntos utilizados por cualquier par de procesos se solapen.
Podemos pensar en los procesos votando para que otro pueda entrar en la SC. Un proceso candidato debe recoger suficientes votos para poder entrar.
El algoritmo satisface EM1 y EM3. La espera para el cliente es igual que en multidifusión pero la espera en la sincronización es peor.
Tolerancia a fallos
Al evaluar los algoritmos anteriores con respecto a su tolerancia a fallos, las principales consideraciones a tener en cuenta son:
- ¿Qué ocurre cuando se pierden mensajes?
- ¿Qué ocurre cuando un proceso se cae?
Ninguno de los algoritmos toleraría la pérdida de mensajes.
El algoritmo basado en anillo no puede tolerar un fallo por caída de ningún proceso individual.
El algoritmo de Maekawa puede tolerar que algunos procesos se caigan siempre y cuando estos no estén en un conjunto de votantes requeridos.
El algoritmo del servidor central puede soportar la caída de un proceso cliente sin riesgo.
El algoritmo de multicast puede adaptase para tolerar la rotura de un proceso haciendo que, de forma implícita, conceda todas las peticiones.
Elecciones
Un algoritmo de elección es aquel que se utiliza para escoger un proceso único que juegue un papel específico. Se dirá que un proceso pide una elección si lleva a cabo una acción que inicia una ejecución específica del algoritmo de elección.
Los requisitos durante una ejecución de un algoritmo de elección son:
- E1 (seguridad): un proceso participante tiene un elegido donde este es el proceso con el identificador mayor que no se ha caído el final de la ejecución.
- E2 (superveniencia): todos los procesos participan y al final fijan el elegido o bien se han caído.
Existen varios algoritmos para la elección de un proceso:
- Algoritmo de elección basado en anillo
El objetivo de este algoritmo es la elección de un proceso individual llamado coordinador que es el proceso con identificador más grande.
En un principio todos los procesos se etiquetan como no participantes y cuando comienza una elección se marca como participante y envía un mensaje de elección. El algoritmo cumple E1 y E2. Es un algoritmo que sirve para comprender las características de los algoritmos de elección pero no tiene valor práctico dado que no tolera fallos.
- Algoritmo abusón (bully)
El algoritmo del abusón permite la caída de procesos durante una elección. A diferencia del algoritmo basado en anillo este supone que el sistema es síncrono, esto es, que utiliza timeouts para detectar un fallo en un proceso. El algoritmo del abusón supone que cada proceso conoce qué procesos tienen identificadores mayores y que puede comunicarse con todos esos procesos. El algoritmo cumple E1 y E2.
Coordinación y acuerdo en comunicaciones en grupo
La comunicación en grupo, o multidifusión (multicast), requiere la presencia de coordinación y acuerdo. Su objetivo es que cada uno de los procesos de un grupo reciba los mensajes enviados al grupo con garantías de que han sido entregados. Estas garantías incluyen el acuerdo sobre el grupo de mensajes que todo proceso del grupo debería recibir, y sobre el orden de entrega dentro de los miembros del grupo.
Modelo del sistema
El sistema contiene una colección de procesos que pueden comunicarse entre ellos de forma fiable a través de canales uno-a-uno. Dichos procesos son miembros de grupos, los cuales son los destinatarios de los mensajes enviados en una operación multicast.
Se dice que un grupo está cerrado si solo los miembros del grupo pueden hacer muticast dentro de el, incluida la entrada al mismo. Un grupo se dice abierto si los procesos que no están en el grupo le pueden enviar mensajes.
- Multicast básico (B-multicast)
Es un multicast que encapsula dentro de una primitiva el envío básico fiable uno-a-uno.
- Multicast fiable (F-multicast)
Un proceso de multicast es fiable si satisface las siguientes propiedades:
- Integridad: un proceso correcto entrega un mensaje a lo sumo una vez.
- Validez: si un proceso correcto multidifunde un mensaje, este al final será entregado.
- Acuerdo: si un proceso correcto entrega un mensaje entonces el resto de procesos correctos del grupo deben, al final, entregar el mensaje.
El multicast fiable está relacionado con la atomicidad del proceso de entrega de mensajes a un grupo.
- Multicas fiable sobre multicast IP
Una alternativa para realizar F-multicast es combinar la multidifusión IP, acuses de recibo adheridos y acuses de recibo negativos. Este protocolo se basa en la observación de que la comunicación mediante IP multicast casi siempre tiene éxito.
- Multicast ordenado
El algoritmo de multicast fiable entrega los mensajes en un orden arbitrario y esto puede no ser admisible en muchas aplicaciones. Los requisitos de ordenación más frecuentes son la ordenación total, causal y la ordenación FIFO además de ordenaciones híbridas total-causal y total-FIFO.
- Ordenación FIFO: establece que si un proceso difunde un mensaje m1 antes que un mensaje m2, entonces ningún proceso correcto entrega m2 si no ha entregado previamente m1.
- Ordenación causal: establece que si la difusión de un mensaje m1 ocurre antes que la difusión de un mensaje m2, entonces ningún proceso correcto entrega m2 si no ha entregado previamente m1.
- Ordenación total: si dos procesos correctos Pi y Pj entregan dos mensajes m1 y m2, entonces Pi entrega m1 antes que m2 sí y solo sí Pj entrega m1 antes que m2.
Dicho de otro modo la ordenación FIFO permite asegurar, desde la perspectiva del emisor, que el primer mensaje enviado ha sido el primero entregado. Por otra parte la ordenación causal lo que asegura es la relación de causa entre mensajes, mientras que la ordenación total asegura que si un mensaje llegó antes con un proceso esto se repite en los demás. La ordenación total multicast requiere de un reloj global.
Consenso
El consenso persigue la resolución de problemas en los procesos que deben ponerse de acuerdo en un valor después de que uno o más de dichos procesos hayan propuesto cuál debería ser ese valor.
En el caso de la exclusión mutua los procesos acuerdan cuales pueden entrar en la sección crítica. En el caso de una elección los proceso acuerdan cual es el proceso elegido.
Los requisitos para un algoritmo de consenso son que han de cumplirse las siguientes condiciones cada vez que se ejecute:
- Terminación: finalmente cada proceso correcto ha de fijar su variable de decisión.
- Acuerdo: el valor de decisión de todos los procesos es el mismo.
- Integridad: si todos los procesos correctos ha propuesto el mismo valor, entonces cualquier proceso correcto en el estado decidido ha elegido dicho valor.
El problema de los generales bizantinos
Se distingue del problema de consenso en que un proceso destacado proporciona un valor en que el que los otros han de ponerse de acuerdo, en vez de que cada uno proponga un valor.
Consistencia interactiva
Este problema es otra variante del consenso en el cual todo proceso propone un solo valor. El objetivo del algoritmo es que todos los procesos se pongan de acuerdo en un vector de valores, uno para cada proceso. A este vector se llamará vector de decisión.
Fuentes
- Distributed Systems: Concepts and Design, Fifth Edition
- Notas personales
