Problema del consenso

El problema del consenso es uno de los desafíos fundamentales en los sistemas distribuidos. Consiste en lograr que un conjunto de procesos, que se ejecutan en nodos independientes y que solo pueden comunicarse mediante el intercambio de mensajes, acuerden un único valor. Alcanzar consenso es trivial en ausencia de fallos, pero se vuelve extremadamente complejo cuando existen factores como fallos de nodos, pérdida o retraso de mensajes, falta de sincronización temporal e incluso comportamientos maliciosos.

Para resolver este problema se diseñan algoritmos o protocolos de consenso, que establecen las reglas mediante las cuales los procesos correctos (no maliciosos) se comunican, proponen valores y toman decisiones de manera coordinada.

Importancia del consenso

Los sistemas distribuidos son inherentemente propensos a fallos, ya sea por caídas de nodos, comunicación no confiable o incluso fallos intencionados (fallos bizantinos). Para aumentar la confiabilidad de estos sistemas, se suele recurrir a la replicación de datos o estados, donde varias copias del mismo estado se mantienen en nodos distintos.

Sin embargo, mantener estas copias consistentes es un reto, especialmente en entornos donde pueden ocurrir fallos. Aquí es donde intervienen los algoritmos de consenso: permiten que las réplicas acuerden un orden común de operaciones, garantizando que todos los nodos correctos mantengan el mismo estado.

Por ejemplo, en una base de datos distribuida, todas las réplicas deben aplicar las mismas operaciones en el mismo orden para permanecer sincronizadas. Los protocolos de consenso implementan esta lógica mediante el paradigma de máquinas de estado replicadas (State Machine Replication).

Modelos de fallos y dificultad del consenso

El consenso se ve afectado por el tipo de fallos considerados. Entre los modelos más comunes se encuentran:

• Fallos por caída (crash failures): un proceso deja de responder.
• Fallos por omisión: se pierden mensajes.
• Fallos bizantinos: los procesos pueden enviar mensajes corruptos o comportarse de manera arbitraria o maliciosa.

La dificultad del consenso depende directamente de estos modelos. Un resultado clave en teoría de sistemas distribuidos es el teorema FLP (Fischer–Lynch–Paterson), que establece que:

En un sistema completamente asíncrono, incluso si solo un proceso puede fallar por caída, no existe un algoritmo determinista que garantice siempre el consenso.

Por ello, muchos protocolos utilizan temporizadores, rondas, suposiciones de sincronía parcial o mecanismos probabilísticos para sortear esta limitación.

Formalización del consenso

Supongamos un conjunto de procesos 𝑝𝑖, con 𝑖 = 1, 2, …, 𝑁, que se comunican mediante paso de mensajes. Cada proceso comienza en un estado inicial sin decisión y propone un valor 𝑣𝑖.

El protocolo de consenso define cómo los procesos intercambian información y, finalmente, establecen un valor en su variable de decisión 𝑑𝑖, el cual no podrá modificarse una vez fijado.

Un algoritmo de consenso correcto debe cumplir las siguientes propiedades:

• Finalización: Todo proceso correcto debe eventualmente decidir un valor.

• Acuerdo: Todos los procesos correctos deben decidir el mismo valor.

• Validez: El valor decidido debe ser uno de los valores propuestos inicialmente.

• Integridad: Si todos los procesos correctos proponen el mismo valor, este debe ser el valor decidido.

En protocolos tolerantes a fallos bizantinos, suelen añadirse propiedades adicionales o reforzarse las anteriores.

Tipos de protocolos de consenso

Debido a la diversidad de entornos y modelos de fallos, existen diversos tipos de protocolos, cada uno orientado a distintos escenarios.

1. Algoritmos de consenso clásico (fallos por caída) Usados en sistemas distribuidos tradicionales para mantener máquinas de estado replicadas.

• Paxos y Multi-Paxos
• Raft
• Viewstamped Replication (VR)
• Zookeeper Atomic Broadcast (ZAB)

2. Protocolos de commit distribuido (no garantizan consenso general) Coordinan transacciones distribuidas, pero no toleran ciertos fallos.

• Commit en dos fases (2PC)
• Commit en tres fases (3PC)

3. Consenso tolerante a fallos bizantinos (BFT) Diseñados para manejar comportamientos maliciosos.

• PBFT (Practical Byzantine Fault Tolerance)
• Protocolos federados como los usados en Ripple o Stellar
• Protocolos de consenso paralelo para sistemas fragmentados (sharding), como el protocolo Cerberus, que extienden BFT para permitir transacciones atómicas a través de múltiples fragmentos.^[1]

4. Mecanismos de consenso en blockchains públicas Basados en mecanismos probabilísticos y criptográficos.

• Prueba de trabajo (Proof of Work)
• Prueba de participación (Proof of Stake) y sus variantes
• Prueba de quemado (Proof of Burn)

Tolerancia a fallos

La capacidad de un sistema para seguir funcionando pese a fallos se expresa típicamente en función de la cantidad máxima de fallos permitidos:

• Para tolerar f fallos bizantinos, se requiere al menos 3f + 1 nodos.

• Para tolerar f fallos por caída, basta con que la mayoría de nodos permanezca activa (por ejemplo, 𝑁>2𝑓).

Estas relaciones permiten establecer los límites teóricos y prácticos de los protocolos.