El consenso es el problema de lograr que varias máquinas se pongan de acuerdo en un valor, o en una secuencia de valores, incluso cuando algunas se caen y los mensajes se extravían. Está debajo de las bases de datos replicadas, los servicios de cerrojos y los almacenes de configuración: siempre que muchos nodos deben actuar como uno, algo ejecuta un protocolo de consenso.
Conceptos clave
- Seguridad y vivacidad: nunca se decide nada incorrecto, y con el tiempo se decide algo; los protocolos garantizan siempre lo primero y lo segundo solo en buenas condiciones.
- Imposibilidad FLP: en un sistema totalmente asíncrono, ningún protocolo determinista puede garantizar el acuerdo si basta con que un nodo pueda caerse.
- Elección de líder y términos: Paxos y Raft eligen un líder para un término numerado, y un término mayor reemplaza a un líder caduco.
- Registro replicado: los nodos acuerdan un registro ordenado de comandos y lo aplican en el mismo orden, formando una máquina de estados replicada.
- Modelos de fallo: los fallos por caída requieren una mayoría de nodos; los fallos bizantinos, donde los nodos mienten, requieren más de dos tercios honestos.
Vocabulario
- Quórum: una mayoría cuyo solapamiento garantiza que dos decisiones no pueden chocar.
- Término o ronda: un número que ordena a los líderes en el tiempo.
- Confirmación (commit): el punto a partir del cual una entrada ya no puede perderse.
- Máquina de estados replicada: copias idénticas de un programa determinista alimentadas con el mismo registro.
- Fallo bizantino: un nodo que se comporta de forma arbitraria, incluso maliciosa.
Qué estudiar, en orden
- Fundamentos de sistemas distribuidos: asincronía, fallos por caída, quórums.
- Lee el artículo de Raft, escrito para ser entendido, y sigue sus figuras con lápiz.
- Implementa la elección de líder, luego la replicación del registro, y prueba con un simulador que descarte y retrase mensajes.
- Lee sobre Paxos y compáralo con Raft: ¿en qué se diferencian y por qué?
- Aprende lo que cuesta la tolerancia a fallos bizantinos y cuándo compensa.
Etiquetas relacionadas
#distributed-systems #blockchain #formal-methods #concurrency