Consenso y Coordinación
El consenso y la coordinación abordan cómo los procesos independientes que se comunican solo por mensajes pueden acordar un valor o una acción común a pesar de los retrasos y las fallas.
Definition
El consenso es el problema de tener un conjunto de procesos, cada uno proponiendo un valor, que todos decidan sobre un único valor común de tal manera que la decisión sea válida, todos los procesos correctos estén de acuerdo, y cada proceso correcto finalmente decida, incluso cuando algunos procesos fallen.
Scope
Esta área cubre el problema del consenso y sus variantes (acuerdo, difusión atómica, validez, terminación), el resultado fundamental de imposibilidad FLP para el consenso asíncrono determinista, protocolos de consenso prácticos como Paxos y Raft, acuerdo tolerante a fallas bizantinas, y los problemas clásicos de coordinación de exclusión mutua y elección de líder. Es el núcleo teórico y práctico de la computación distribuida tolerante a fallas.
Sub-topics
Core questions
- ¿Bajo qué modelos de tiempo y falla es resoluble el consenso, y cuándo es demostrablemente imposible?
- ¿Cómo eluden los protocolos prácticos la imposibilidad FLP mientras preservan la seguridad?
- ¿Cuánta replicación se requiere para tolerar fallas por caída (crash) versus fallas bizantinas?
- ¿Cómo pueden los procesos coordinar el acceso a recursos compartidos o elegir un líder de manera confiable?
Key theories
- Imposibilidad FLP
- En un sistema completamente asíncrono, ningún protocolo determinista puede garantizar el consenso si incluso un solo proceso puede fallar, porque un proceso lento no se puede distinguir de uno fallido; este resultado motiva la sincronicidad parcial, la aleatorización y los detectores de fallas.
- Consenso basado en quórum
- Protocolos como Paxos logran el acuerdo al requerir que mayorías superpuestas (quórums) acepten propuestas, asegurando que dos decisiones cualesquiera se intersequen en un proceso correcto y, por lo tanto, permanezcan consistentes a través de rondas y cambios de líder.
- Límites del acuerdo bizantino
- Para llegar a un acuerdo cuando hasta f procesos pueden comportarse arbitrariamente, se requieren al menos 3f+1 procesos en el entorno síncrono clásico, un límite estricto que da forma al diseño de todos los sistemas tolerantes a fallas bizantinas.
Clinical relevance
El consenso es la columna vertebral de la infraestructura confiable: los servicios de coordinación, las bases de datos replicadas, los bloqueos distribuidos y las cadenas de bloques (blockchains) ejecutan un protocolo de consenso para mantener la coherencia de las réplicas, lo que hace que esta área sea directamente responsable de las garantías de durabilidad y disponibilidad de los sistemas de nube modernos.
History
El artículo de 1982 sobre los generales bizantinos y el resultado de imposibilidad FLP de 1985 enmarcaron los límites del acuerdo; el Paxos de Lamport (circulado en 1989, publicado en 1998) proporcionó un protocolo práctico asíncrono seguro, y el trabajo posterior sobre la tolerancia a fallas bizantinas y Raft hizo que el consenso fuera robusto contra fallas maliciosas y accesible para los implementadores.
Debates
- ¿La imposibilidad FLP hace que el consenso sea inalcanzable en la práctica?
- FLP descarta un protocolo determinista que sea siempre seguro y vivo en un modelo completamente asíncrono, pero los sistemas prácticos lo eluden asumiendo una sincronicidad eventual o usando aleatorización, manteniendo la seguridad incondicional y logrando la vivacidad siempre que la red se comporte.
Key figures
- Leslie Lamport
- Nancy Lynch
- Michael Fischer
- Michael Paterson
- Barbara Liskov
Related topics
Seminal works
- fischer1985
- lamport1998
- lamport1982byz
Frequently asked questions
- ¿Por qué el consenso se considera el problema más difícil en los sistemas distribuidos?
- Porque muchas otras tareas de coordinación —difusión atómica, máquinas de estado replicadas, bloqueo distribuido— se reducen al consenso, y el consenso en sí mismo es demostrablemente imposible de resolver de forma determinista en el modelo asíncrono de falla por caída (crash-failure), por lo que cualquier solución debe hacer suposiciones cuidadosas de tiempo o aleatoriedad.
- ¿Cómo se relaciona el consenso con las bases de datos replicadas?
- Una base de datos replicada mantiene la coherencia de sus réplicas al acordar el orden de las operaciones, lo cual es exactamente una secuencia de decisiones de consenso; por eso, sistemas como los almacenes de clave-valor distribuidos incrustan un protocolo de consenso en su núcleo.