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.

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).

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.

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.

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.

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)

Bitcoin y Ethereum tienen un consumo energético cercano al de países enteros como Suecia y Rumania respectivamente, lo que ha impulsado la transición de Ethereum hacia Proof of Stake (The Merge, septiembre de 2022).^[3]

Los algoritmos de consenso tienen aplicaciones que van más allá de las bases de datos distribuidas tradicionales:

• Internet de las Cosas Industrial (IIoT): En entornos como la conducción autónoma o la fabricación inteligente, los protocolos de consenso permiten tomar decisiones críticas en tiempo real incluso cuando los enlaces de comunicación individuales no son completamente fiables. Esto es fundamental para lograr comunicaciones ultra confiables y de baja latencia (URLLC) en sistemas distribuidos.^[4]

• Registro distribuido de aeronaves: NASA identificó tempranamente la necesidad de consenso tolerante a fallos bizantinos para sistemas de control de aeronaves, donde un componente fallido podría enviar información contradictoria a diferentes partes del sistema.^[5]

• Sistemas de pago y liquidación de activos: Bancos centrales y entidades financieras están desarrollando protocolos de consenso tolerantes a fallos bizantinos para entornos controlados (permissioned), como el protocolo FBFT (FROSTed Byzantine Fault Tolerance) desarrollado por el Banco de Italia, que combina PBFT con firmas Schnorr umbral para preservar la confidencialidad de los validadores.^[6]

• Fischer, M. J., Lynch, N. A., & Paterson, M. S. (1985). Impossibility of distributed consensus with one faulty process. Journal of the ACM, 32(2), 374–382. https://doi.org/10.1145/3149.214121
• Lynch, N. (1996). Distributed algorithms. Morgan Kaufmann.
• Attiya, H., & Welch, J. (2004). Distributed computing: Fundamentals, simulations, and advanced topics (2.ª ed.). Wiley.
• Lamport, L. (1998). The part-time parliament. ACM Transactions on Computer Systems, 16(2), 133–169. https://doi.org/10.1145/279227.279229
• Lamport, L. (2001). Paxos made simple. ACM SIGACT News, 32(4), 51–58. https://doi.org/10.1145/568425.568433
• Ongaro, D., & Ousterhout, J. (2014). In search of an understandable consensus algorithm (Raft). In Proceedings of the USENIX Annual Technical Conference (pp. 305–319).
• Oki, B. M., & Liskov, B. (1988). Viewstamped replication: A new primary copy method to support highly-available distributed systems. In Proceedings of the 7th Annual ACM Symposium on Principles of Distributed Computing (pp. 8–17). ACM. https://doi.org/10.1145/62546.62549
• Hunt, P., Konar, M., Junqueira, F. P., & Reed, B. (2010). ZooKeeper: Wait-free coordination for internet-scale systems. In Proceedings of the USENIX Annual Technical Conference (pp. 145–158).