Exclusión Mutua Distribuida y Elección de Líder
La exclusión mutua y la elección de líder son problemas clásicos de coordinación: asegurar que como máximo un proceso acceda a un recurso crítico y seleccionar un único coordinador distinguido entre pares.
Definition
La exclusión mutua distribuida garantiza que como máximo un proceso a la vez posea un recurso compartido, asegurando al mismo tiempo el acceso eventual para todos los solicitantes; la elección de líder selecciona determinísticamente exactamente un proceso como coordinador, con todos los procesos acordando el resultado.
Scope
Este tema abarca algoritmos de exclusión mutua basados en permisos (algoritmo de marcas de tiempo de Lamport, Ricart-Agrawala, el enfoque de quórum de Maekawa) y algoritmos basados en tokens, junto con su complejidad de mensajes y propiedades de equidad; y algoritmos de elección de líder para anillos (Chang-Roberts) y redes generales (el algoritmo del matón), incluyendo sus suposiciones sobre identificadores y sincronía. Estas primitivas se repiten en los servicios de coordinación y sistemas replicados.
Core questions
- ¿Cómo pueden los procesos serializar el acceso a un recurso compartido utilizando solo mensajes?
- ¿Cuáles son las compensaciones en complejidad de mensajes y equidad entre los esquemas basados en permisos y los basados en tokens?
- ¿Cómo se elige un líder único y cómo se vuelve a activar la elección después de que el líder falla?
Key theories
- Exclusión mutua basada en permisos
- Algoritmos como Ricart-Agrawala ordenan las solicitudes por marcas de tiempo lógicas y otorgan la entrada una vez que un solicitante ha recibido permiso de todos (o un quórum de) los pares, logrando equidad con un costo de mensaje acotado por entrada a la sección crítica.
- Exclusión mutua basada en tokens
- Un token único circula o se solicita bajo demanda, y solo su poseedor puede entrar en la sección crítica, reduciendo el tráfico de mensajes pero requiriendo mecanismos para regenerar un token perdido después de fallos.
- Elección de líder
- Los algoritmos de elección como Chang-Roberts para anillos y el algoritmo del matón para redes generales utilizan identificadores de proceso para converger en un único coordinador de mayor prioridad que todos los procesos correctos reconocen.
Clinical relevance
La elección de líder se invoca siempre que un sistema replicado debe elegir un primario o coordinador, y el bloqueo distribuido generaliza la exclusión mutua; ambos se exponen como servicios centrales por los sistemas de coordinación utilizados en toda la infraestructura de la nube.
History
El artículo de Lamport de 1978 sobre relojes lógicos introdujo un algoritmo de exclusión mutua basado en marcas de tiempo; Ricart y Agrawala lo optimizaron en 1981, Maekawa introdujo los quórums poco después, y el algoritmo del matón de Garcia-Molina de 1982 formalizó la elección de líder, dando al campo sus algoritmos de coordinación canónicos.
Key figures
- Leslie Lamport
- Glenn Ricart
- Ashok Agrawala
- Hector Garcia-Molina
Related topics
Seminal works
- ricart1981
- garcia-molina1982
- lynch1996
Frequently asked questions
- ¿En qué se diferencia la exclusión mutua distribuida de un bloqueo en una sola máquina?
- No hay memoria compartida o un gestor de bloqueo central en el que confiar, por lo que los procesos deben coordinarse puramente mediante el intercambio de mensajes y deben manejar explícitamente el retraso de los mensajes y los fallos, algo que un bloqueo de una sola máquina puede dar por sentado.