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:

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.

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:

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

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:

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.

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.

Comparativa de algoritmos

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:

  • f representa el número máximo de nodos fallidos que el sistema puede tolerar.
  • N es el número total de nodos en la red.
  • La complejidad O(N²) indica que cada nodo debe comunicarse con todos los demás, lo que limita la escalabilidad.
  • Los mecanismos probabilísticos (PoW, PoS) no garantizan consenso absoluto, sino que la probabilidad de bifurcación disminuye con el tiempo.

Comparación de mecanismos en blockchains públicas

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

Aplicaciones prácticas

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