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:
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:
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:
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.
2. Protocolos de commit distribuido (no garantizan consenso general) Coordinan transacciones distribuidas, pero no toleran ciertos fallos.
3. Consenso tolerante a fallos bizantinos (BFT) Diseñados para manejar comportamientos maliciosos.
4. Mecanismos de consenso en blockchains públicas Basados en mecanismos probabilísticos y criptográficos.
La siguiente tabla resume las características principales de los algoritmos de consenso más relevantes:
| Algoritmo | Tolerancia a fallos | Tipo de fallo | Complejidad de comunicación | Escalabilidad | Uso principal |
|---|---|---|---|---|---|
| Paxos | Mayoría (N > 2f) | Por caída | O(N²) | Media | Bases de datos distribuidas |
| Raft | Mayoría (N > 2f) | Por caída | O(N²) | Media | Sistemas de coordinación (etcd, Consul) |
| PBFT | N ≥ 3f+1 | Bizantino | O(N²) | Baja (≤ 20 nodos) | Blockchains permissioned |
| PoW | Probabilístico | Bizantino | N/A (competitivo) | Alta (miles de nodos) | Bitcoin, blockchains públicas |
| PoS | Probabilístico / N ≥ 3f+1 | Bizantino | Variable | Alta | Ethereum, blockchains modernas |
| PoA | N ≥ 2f+1 | Bizantino (limitado) | O(N²) | Media | Redes de prueba, consorcios |
Notas:
| Característica | Proof of Work (PoW) | Proof of Stake (PoS) | Proof of Authority (PoA) |
|---|---|---|---|
| Consumo energético | Muy alto (equivalente a países enteros) | Bajo | Muy bajo |
| Finalidad de bloques | Probabilística (~6 bloques en Bitcoin) | Rápida (muchas redes tienen finalidad en 1-2 bloques) | Inmediata |
| Riesgo de centralización | Alto (minería con ASICs) | Medio (participación por stake) | Alto (autoridades predefinidas) |
| Tolerancia a atacantes | < 51% del poder de hash | < 33% (o 51% según variante) del stake | < 50% de autoridades |
| Ejemplos | Bitcoin, Litecoin, Dogecoin | Ethereum, Cardano, Solana | Binance Smart Chain, xDai, Rinkeby (testnet) |
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).
Los algoritmos de consenso tienen aplicaciones que van más allá de las bases de datos distribuidas tradicionales: