Algoritmos de consenso

1) Qué es el consenso y por qué es necesario

Consenso: acuerda el mismo valor/secuencia de valores entre varios nodos en caso de fallos y retrasos. Tradicionalmente se resuelve el problema de replicación de estado (State Machine Replication, SMR): hay una máquina de estados determinista y un orden de operaciones general.

• Consenso (SMR): orden total único de comandos → almacenamiento/registro lineable, metadatos de clúster, coordinadores transaccionales.
• Operaciones de quórum sin orden total (Dynamo-like, CRDT): permiten la divergencia y posterior fusión; no sustituyen al consenso donde se necesita la serialización global.

2) Modelo de tiempo y fallos

2. 1 Modelo de tiempo

Red asíncrona: los retrasos son ilimitados; el teorema FLP ⇒ es imposible garantizar tanto la seguridad como la vida sin suposiciones adicionales.
Parcialmente sincronizado (a menudo en la práctica): después de un T desconocido, el sistema «se comporta» de forma sincronizada - la mayoría de los algoritmos (Raft, Paxos) se basan precisamente en eso.
Sincronizado: límites de tiempo rígidos en los canales (raramente en venta, excepto redes especiales/PTP).

2. 2 Modelo de fallos

tolerante de grifo (CFT): los nodos pueden caer/colgarse, pero no se comportan maliciosamente.
Byzantine-fault tolerant (BFT): los nodos pueden mentir/falsificar mensajes. Se requieren 3f + 1 nudos para tolerancia a f bizantino.

3) Propiedades del consenso

Seguridad: consistencia (dos nodos correctos no resolverán valores diferentes).
Liveness (vitalidad): si la red es «saludable», se llega a una solución.
Linealizabilidad (linealidad): las operaciones se «ven» como atómicas en un solo orden.
Durabilidad: las decisiones tomadas no se retrotraen (protección por registro/quórum).

4) Quórums, mayoría y intersecciones

En el mundo CFT, un clásico: quórum> N/2. Los registros y la elección del líder utilizan la intersección de quórum, por lo que dos operaciones «válidas» no chocan.
En el mundo BFT: los quórums 2f + 1 de 3f + 1 proporcionan una intersección mínima en f + 1 nodos honestos.

Regla de intersección: cualquier dos quórum debe tener un nodo honesto (CFT) o ≥f+1 (BFT) ≥1 común.

5) Replicación de estado (registro + aplicación)

• Snapshots (corte del estado después del cual se pueden eliminar/comprimir las entradas tempranas).
• Un compacto de la revista y un trío de registros.
• Comprobaciones de determinismo (la misma versión de código/confites).

6) Esquemas de liderazgo y no liderazgo

Leader (Raft, Multi-Paxos, ZAB): un líder serializa las grabaciones → más fácil mental y operativamente, mejor latencia en un líder estable.
Sin plomo/multilider (EPaxos, César): más paralelismo y tolerancia hacia el líder, pero más difícil de implementar y conflicto-solución; las ganancias son visibles en pequeños conflictos de equipos.

7) Algoritmos CFT clásicos

7. 1 Paxos/Multi-Paxos (y prácticas)

Idea: dos fases (prepare/propose), promesas de aceptores, quórums mayoritarios. Multi-Paxos deja un «líder estable» y convierte las operaciones en una sola ronda (para nuevas grabaciones) después de «calentar».

• Modelo flexible pero complejo de implementar.
• Re-configuraciones a través de registros especiales (joint consensus).
• En la práctica, bibliotecas/motores (generación Chubby/Spanner).

7. 2 Raft

Descompuesto para la capacidad de aprendizaje: selección del líder, replicación de registros, re-configuración.

Election: temporizadores aleatorios, votación térmica; un líder a término.
AppendEntries: el líder en streaming del registro, supervisa la coincidencia del prefijo (índice/term), commite por fijación mayoritaria.
Read-path: lease-reads (con un líder fuerte) o read-index para lecturas lineales.
Reconfig: «configuración conjunta» (joint): los nodos votan en dos clústeres antes de la transición.

Pros: más fácil para el desarrollo/debag, invariantes fuertes del orden. Contras: el líder es el punto de presión.

7. 3 ZAB (ZooKeeper Atomic Broadcast) / Viewstamped Replication (VRR)

ZAB: el líder emite transacciones, fase de recuperación, zxid (era + índice).
VRR: «especies» (views) con replicante primario, similar a Multi-Paxos en espíritu.

8) CFT Nelider/Multilider

8. 1 EPaxos

No hay un líder permanente: cualquier nodo puede iniciar un comando.
Los comandos en conflicto reciben un orden parcial; sin conflicto - commite en 1-2 RTT localmente.
Ganancia en la distribución geográfica con baja conflictividad, pero códigos complejos de dependencias/grafos.

8. 2 Caesar, Mencius

Variaciones que optimizan la latencia/el equilibrio y el funcionamiento en la WAN.

9) algoritmos BFT y familia PoS

9. 1 PBFT (Practical BFT)

Tres fases (pre-prepare/prepare/commit), requiere 3f + 1 nodos.
Baja latencia en redes locales, carreteras por multi-paso y mensajes O (N ²).

9. 2 Tendermint (estilo BFT-PoS)

Rondas con proposal y dos votaciones (prevote/precommit).
Validador-sugerente determinista, tiempos de espera, sincronía parcial.
Bueno para redes permissioned/PoS con decenas/cientos de validadores.

9. 3 HotStuff (y derivados)

Se ha unificado el esquema trifásico en «paquetes» con certificados de quórum (QC).
La complejidad lineal de las comunicaciones, el soporte de empaquetado y la paiplinización paralela, son fáciles de implementar en blockchains (por ejemplo, el ecosistema Diem/Move).
Con las firmas de umbral (señales threshold), el tráfico disminuye.

9. 4 PoW/consenso acumulativo (breve)

No BFT en sentido estricto, sino convergencia probabilística (la cadena con más trabajo). Virtudes: simplicidad/apertura; desventajas: energía, ~ segundos-minutos hasta la final.

10) Lecturas: lineales, secuenciales y en caché

Lecturas lineales: líder con lease activo o vía read-index (Raft) → confirmación a través de quórum.
Consistente: se puede leer desde cualquier nodo, pero sin garantías de frescura.
Follower reads: admisibles cuando los requisitos son débiles; para caché - ok.

11) Re-configuración (cambio de composición del clúster)

Requiere dos configuraciones superpuestas (joint consensus): cualquier commita pasa los quórums de ambas configuraciones → sin «agujeros».
Agregue/elimine uno por uno, cumpla con el tamaño del quórum.
La transferencia de liderazgo (leadership transfer) reduce las pausas.

12) Rendimiento y afinación

12. 1 Retrasos

Algoritmos de liderazgo: 1 RTT por escritura (con un líder estable) + replicación.
Distribución geográfica: WAN RTT domina → utiliza regiones locales + replicación cruzada regional o enfoques EPaxos/HotStuff.

12. 2 Ancho de banda

Batching (agrupación de comandos), AppendEntries paralelos, caché de page de registro, aplicación paralela (cuando las operaciones se conmutan).
Discos: NVMe/Registro en un dispositivo separado, 'O _ DIRECT '/AIO, una gran' fsync '-intervención con restricciones SLA (compromiso durabilidad/latencia).

12. 3 Colas p99

Evite los nodos calientes (el líder está constantemente solo): rotación periódica o read-offload en los seguidores.
Controle las pausas GC (JVM/Go), los pines CPU, NUMA.

13) Geografía y topologías

1 región, 3 zonas: clúster clásico de CFT (N = 3/5).
2 regiones: evitar - no se obtiene un quórum confiable cuando se divide 1-1.
3 + regiones: líder en «medio» o algoritmos sin línea; los proxies regionales/frentes locales con registro asíncrono son posibles.

14) Cuestiones prácticas de explotación

14. 1 Snapshots y recuperación

Umbral por tamaño de registro/número de operaciones.
Transferencia de snapshot a nuevos nodos; comprobación de las cantidades de control.

14. 2 Monitoreo

Liderazgo: quién es el líder, cuántos plazos (term/epoch) han cambiado.
Лаги: `append_latency`, `commit_index - applied_index`.

Salud de quórum: «¿Están vivos la mayoría/2f + 1?»

Tamaño del registro/velocidad del compacto, cola de snapshots.
Para BFT: la proporción de votos, los firmantes, los retrasos del control de calidad.

14. 3 Seguridad/consistencia de código

Versionabilidad del protocolo en el cable, migración con compatibilidad de registro.
Fichas de fantasía en efectos externos (ver «Bloqueos distribuidos»): término de liderazgo (term) para transferir a CRON/jobs.

15) Anti-patrones

Poner el consenso «por el bien de la moda» donde se agarre un solo DBM o lecturas de quórum sin serializar.
Mezclar CP y AP sin límites claros (CAP) → UX impredecible.
Reevaluar PoW/PoS para tareas empresariales con docenas de nodos (difícil/caro).
Ignorar la re-configuración y los "quórums' de intersección cuando se cambia la composición.
Ninguna lectura-barrier (lease/read-index) → lecturas «sucias».
Ejecutar clústeres de 2 nodos (no hay mayoría).
Subestimación de discos y fsync: «todo vuela en la memoria» - hasta el primer reinicio.

16) Lista de verificación de selección

1. Modelo de fallas: ¿CFT (tintes) o BFT (malintencionados)?
2. Geografía: ¿una región/tres zonas o WAN? RTT decide.
3. La semántica de las lecturas: ¿se necesitan lecturas lineales? Lease/read-index/follower-rid.
4. Carga: espera por p50/p99, throughput; si se necesita multi-liderazgo.
5. Complejidad operativa: biblioteca/motor terminado (etcd/ZK/Consul/Raft-libes) vs implementación nativa.
6. Reconfiguración: ¿frecuente? Necesita un consensus de joint y herramientas de migración.
7. Integraciones: efectos secundarios externos - ¿hay fencing por epoch/term?
8. Seguridad: autenticación de nodos, cifrado de canales, control de versiones de protocolo.
9. Pruebas de reproducción: partition, GC-stop, líder kill, slow disk, clock skew.
10. Observabilidad: métricas de líder/lags/registro y alertas personalizadas.

17) Mini-guía: cuándo tomar

etcd/Raft-cluster para configuraciones/bloqueos/coordinación dentro de DC.
ZooKeeper/ZAB para servicios ya atados en ZK (pilas viejas, colas, liderazgo).
Multi-Paxos a través de un servicio/biblioteca listo en sistemas altamente especializados.
EPaxos en la distribución geográfica y bajo conflicto de comandos.
Tendermint/HotStuff para redes permissioned/PoS-leyer con decenas a cientos de validadores y requisitos de finalidad.
Dynamo-similar/CRDT cuando el consenso no es necesario, pero la disponibilidad/escala es importante con la fusión posterior.

18) Ejemplos de interfaces (pseudo)

18. 1 Commit de grabación (estilo Raft)

pseudo client -> leader: Propose(cmd)
leader. appendLog(cmd)
leader. replicateToQuorum()
if quorum_acked:
leader. commit(index)
leader. apply(index)
leader. reply(client, ok)

18. 2 Índice de lectura para lectura lineal (Raft)

pseudo client -> any: LinearizableRead node -> leader: ReadIndex?
leader -> quorum: Heartbeat (barrier)
leader -> node: ReadIndex=commit_index node. wait_until(applied_index >= ReadIndex)
node. reply(client, state_at(ReadIndex))

18. 3 Configuración conjunta

pseudo old_conf + new_conf # quorums must intersect commit (entries under joint)
switch_to(new_conf)

18. 4 BFT (HotStuff-aproximado)

pseudo propose(block)
collect votes -> QC lock on highest QC commit when have consecutive QCs across phases

19) FAQ

P: ¿Por qué no usar dos nodos y un tie breaker?
R: Dos nudos sin un tercer árbitro no dan quórum en la división. Necesita ≥3 (CFT) o 3f + 1 (BFT).

P: ¿Qué es Raft «más simple» que Paxos?
R: Descomposición clara, invariantes comprensibles del registro y la configuración; más fácil de implementar y acompañar.

P: ¿Cómo leer rápido sin cargar a un líder?
R: Follower-reads (secuenciales) para no críticos, o lease-reads/read-index para lineales; en caché.

P: ¿Qué mata p99?
R: WAN-RTT, disco fsync, pies GC, líder sobrecalentado, snapshots grandes en «hora punta».

P: ¿Necesita consenso para la caché/directorio?
R: Si la consistencia eventual es suficiente - no. Si se requieren invariantes transaccionales, sí.

20) Resultados

El consenso es un instrumento para una estricta coherencia y racionalización. Seleccione un algoritmo basado en el modelo de fallas y la geografía; proporcione intersecciones de quórum, una correcta re-configuración, lecturas lineales donde sea crítico y observabilidad. No olvides el fencing para efectos externos, snapshots y la disciplina de las revistas. Entonces la replicación del estado será predecible y los incidentes raros y comprensibles.