El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia

HOME

En la lección anterior dijimos con naturalidad que un sistema CP "rechaza las escrituras que no alcanzan quórum" y que "el lado de la partición con mayoría sigue funcionando". Detrás de esas frases hay un problema que la informática distribuida tardó décadas en resolver: cómo un grupo de nodos, cada uno con su propio reloj, con mensajes que se pierden o llegan tarde y con compañeros que pueden morir en cualquier momento, se pone de acuerdo en un valor, de forma que ninguno decida algo distinto y que, si las cosas van razonablemente bien, alguno decida de verdad. Ese problema se llama consenso, y es la pieza que convierte la etiqueta "CP" en un mecanismo.

Esta lección lo aborda en tres niveles. Primero, el problema en sí: qué propiedades exige, por qué el resultado FLP de 01-02 dice que no tiene solución garantizada en un sistema asíncrono y por qué, aun así, se resuelve en la práctica a diario. Segundo, los dos algoritmos que dominan la industria: Paxos, el original de Lamport, con sus roles y sus dos fases, y Raft, diseñado para ser comprensible, con sus términos, su elección de líder y su log replicado; ambos con simulaciones en Python que muestran a varios proposers en conflicto y a un líder que cae. Tercero, una visión general del consenso bizantino (PBFT) y de cuándo hace falta. Cerraremos con los sistemas que empaquetan estos algoritmos (etcd, ZooKeeper, Consul) y con su primer uso real en Kilómetro Cero: garantizar que solo una instancia del relay outbox de 02-05 publica en cada momento, usando etcd con un lease. La replicación de datos en general (líder-seguidor, multilíder, quórums de lectura y escritura) es la lección siguiente; aquí el consenso sirve para elegir líderes y acordar valores pequeños.

Contenido

El problema del consenso
Por qué es difícil: FLP y la salida práctica
Para qué se usa el consenso
Paxos: roles, fases y números de propuesta
Simulación: Paxos con dos proposers en conflicto
Raft: términos, elección de líder y log replicado
Simulación: elección de líder en Raft y caída del líder
Consenso bizantino: PBFT en una página
Tabla comparativa: Paxos, Raft y PBFT
Sistemas que lo implementan y su uso en Kilómetro Cero: etcd y el relay outbox
Errores comunes y consejos
Ejercicios
Conclusión

El problema del consenso

Un conjunto de N procesos, cada uno con un valor inicial propuesto, debe decidir un único valor. Un algoritmo de consenso es correcto si cumple tres propiedades:

Propiedad	Enunciado	Tipo
Acuerdo (agreement)	Dos procesos correctos nunca deciden valores distintos	Seguridad (safety): nunca pasa nada malo
Validez (validity)	El valor decidido fue propuesto por algún proceso (no vale decidir un valor por defecto que nadie propuso)	Seguridad
Terminación (termination)	Todo proceso correcto acaba decidiendo	Vivacidad (liveness): algo bueno acaba pasando

Las dos primeras son propiedades de seguridad: se pueden violar en un instante concreto y ya no hay vuelta atrás (si inv-bcn decide que el líder es relay-1 e inv-vlc que es relay-2, el daño está hecho). La tercera es de vivacidad: se viola solo si el sistema se queda atascado para siempre. Esta distinción es central porque, como veremos, los algoritmos prácticos nunca sacrifican seguridad y aceptan sacrificar vivacidad temporalmente.

En Kilómetro Cero, el "valor" a decidir será cosas como "quién es el líder del relay outbox en el término 7", "la configuración vigente es la versión 12" o, en el caso general de la replicación por consenso, "la entrada número 4.312 del log es reservar queso-curado para P-2026-000123".

Por qué es difícil: FLP y la salida práctica

En 01-02 presentamos el resultado de Fischer, Lynch y Paterson (1985): en un sistema asíncrono (sin cotas en la latencia de los mensajes ni en la velocidad de los procesos), ningún algoritmo determinista de consenso garantiza terminación si un solo proceso puede fallar por parada. La intuición: si un proceso no responde, los demás no pueden distinguir si ha muerto o si su mensaje está tardando; si esperan, pueden esperar para siempre; si deciden sin él, puede resultar que estaba vivo y a punto de decidir otra cosa. Siempre existe un adversario (una planificación de retrasos) que mantiene al algoritmo indeciso.

FLP no dice que el consenso sea imposible en la práctica; dice que no se puede garantizar en el peor caso asíncrono. Las salidas prácticas son las que anticipamos en 01-02:

Sincronía parcial: asumir que la red se comporta bien "la mayor parte del tiempo" y usar timeouts. Paxos y Raft garantizan seguridad siempre, en cualquier red, y terminación solo cuando la red está en un periodo estable. Es exactamente la división seguridad/vivacidad del apartado 1.
Aleatoriedad: los timeouts aleatorios de Raft y algunos protocolos probabilistas rompen la simetría que el adversario de FLP necesita.
Detectores de fallos: sospechar de un nodo tras un timeout, aceptando equivocarse (un nodo lento tratado como muerto sigue siendo seguro, solo cuesta progreso).

Y una regla que conviene grabarse: el consenso necesita mayoría. Con N nodos, se toleran f fallos de parada si N ≥ 2f + 1: tres nodos toleran uno, cinco toleran dos. La razón es que dos mayorías cualesquiera de N se intersecan en al menos un nodo, y ese nodo común es el que impide que dos grupos decidan valores distintos. Es también por qué un sistema CP con dos nodos, como el de la simulación de 03-02, no puede tolerar ninguna partición.

Para qué se usa el consenso

El consenso puro (acordar un valor) rara vez se usa directamente. Se usa como primitiva para construir:

Uso	Qué se decide	Ejemplo en Kilómetro Cero
Elección de líder	Quién manda durante un periodo	Una sola instancia del relay outbox de `pedidos` publica en `pedidos.eventos`; un único planificador asigna repartidores
Máquina de estados replicada (log replicado)	El orden de todas las operaciones	Base de un almacén CP: todas las réplicas aplican el mismo log en el mismo orden y por tanto tienen el mismo estado (así funcionan etcd, CockroachDB, Kafka con KRaft)
Configuración distribuida	La versión vigente de la configuración	Umbral de stock para pasar a modo CP (03-02), lista de mercados activos, feature flags de la "Semana del Queso Artesano"
Locks distribuidos y membresía	Quién tiene el lock; qué nodos están en el grupo	Evitar que dos procesos de `analitica` reconstruyan el mismo informe; saber qué réplicas de `inventario` están vivas
Commit atómico	Si una transacción se confirma o aborta	Variante de consenso con requisitos distintos, en 03-05

La idea de la máquina de estados replicada (Lamport, 1978; Schneider, 1990) merece una frase más: si varios nodos parten del mismo estado y aplican las mismas operaciones deterministas en el mismo orden, acaban en el mismo estado. El consenso se usa para acordar el orden (entrada 1, entrada 2, entrada 3...), y a partir de ahí la replicación es trivial. Es el patrón detrás de Multi-Paxos y de Raft, y la razón por la que ambos hablan de "log".

Paxos: roles, fases y números de propuesta

Leslie Lamport publicó Paxos en 1998 (tras un rechazo inicial del artículo, escrito como una parábola sobre un parlamento griego, en 1989). Resuelve el consenso de un solo valor (single-decree Paxos) con tres roles, que en la práctica suelen coexistir en cada nodo:

Proposer: propone un valor. Puede haber varios a la vez, y ahí está la dificultad.
Acceptor: vota. Recuerda dos cosas en almacenamiento estable: el número de propuesta más alto que ha prometido no ignorar, y la última propuesta que ha aceptado (número y valor). Un valor queda elegido cuando una mayoría de acceptors lo ha aceptado con el mismo número de propuesta.
Learner: se entera del valor elegido (preguntando a los acceptors o recibiendo notificaciones).

Cada propuesta lleva un número de propuesta único y totalmente ordenado; el truco habitual es n = ronda * 10 + id_proposer, de modo que dos proposers nunca generan el mismo número. El protocolo tiene dos fases:

sequenceDiagram
    participant P as Proposer (relay-1)
    participant A1 as Acceptor a1
    participant A2 as Acceptor a2
    participant A3 as Acceptor a3
    Note over P,A3: Fase 1: prepare / promise
    P->>A1: prepare(n=1)
    P->>A2: prepare(n=1)
    P->>A3: prepare(n=1)
    A1-->>P: promise(1, sin aceptado)
    A2-->>P: promise(1, sin aceptado)
    A3-->>P: promise(1, sin aceptado)
    Note over P: Mayoría de promesas y nadie había aceptado nada: propongo mi valor
    Note over P,A3: Fase 2: accept / accepted
    P->>A1: accept(n=1, "relay-1")
    P->>A2: accept(n=1, "relay-1")
    P->>A3: accept(n=1, "relay-1")
    A1-->>P: accepted(1)
    A2-->>P: accepted(1)
    A3-->>P: accepted(1)
    Note over P,A3: Mayoría de accepted con n=1: el valor "relay-1" queda ELEGIDO

Fase 1 (prepare/promise). El proposer elige un número n y envía prepare(n) a los acceptors. Un acceptor que recibe prepare(n) con n mayor que cualquier número que haya prometido responde promise(n, aceptado), comprometiéndose a no aceptar ninguna propuesta con número menor que n, e incluyendo la propuesta que hubiera aceptado antes, si la hay. Si n es menor o igual que su promesa, ignora o rechaza.

Fase 2 (accept/accepted). Si el proposer recibe promesas de una mayoría, elige el valor a proponer con esta regla, que es el corazón de Paxos: si alguna promesa incluía una propuesta ya aceptada, debe proponer el valor de la aceptada con número más alto; solo si ninguna incluía nada, puede proponer su propio valor. Envía accept(n, valor); cada acceptor lo acepta si no ha prometido un número mayor entretanto, y responde accepted. Con una mayoría de accepted, el valor está elegido.

Por qué funciona. Supón que el valor v ha sido elegido con número n (una mayoría lo aceptó). Cualquier propuesta posterior con número m > n tiene que obtener promesas de una mayoría, que necesariamente se interseca con la mayoría que aceptó v; al menos un acceptor de esa intersección informará de (n, v) en su promesa, y la regla de la fase 2 obligará al nuevo proposer a proponer v de nuevo. Por inducción, una vez elegido un valor, todas las propuestas futuras llevan ese mismo valor: acuerdo garantizado, con cualquier número de proposers y cualquier orden de mensajes. La validez es inmediata (solo se proponen valores propuestos) y la terminación... no está garantizada (FLP): dos proposers pueden turnarse en fase 1 con números crecientes, invalidando mutuamente sus promesas para siempre (livelock). La solución práctica es elegir un proposer distinguido con timeouts, es decir, un líder.

Por qué es difícil de implementar. Paxos de un solo valor es elegante, pero un sistema real necesita decidir una secuencia de valores (el log de la máquina de estados). Multi-Paxos hace eso: ejecuta una instancia de Paxos por entrada del log, y optimiza eligiendo un líder estable que hace la fase 1 una sola vez para todas las entradas futuras y luego solo ejecuta la fase 2 por entrada. Pero el artículo de Lamport no especifica cómo elegir el líder, cómo gestionar cambios de membresía, cómo compactar el log ni cómo recuperar acceptors que se han quedado atrás. Cada implementación (Chubby de Google, Spanner, Cassandra para sus transacciones ligeras) rellena esos huecos a su manera, y los autores de Chubby escribieron que "hay huecos significativos entre la descripción del algoritmo y las necesidades de un sistema real". Esa frustración es el origen de Raft.

Simulación: Paxos con dos proposers en conflicto

Vamos a implementar Paxos de un solo valor con tres acceptors y dos proposers, relay-1 y relay-2, cada uno de los cuales quiere ser elegido líder del relay outbox. La red permite descartar mensajes concretos para reproducir el caso interesante: relay-1 consigue que un acceptor acepte su valor, pierde el resto de mensajes, y relay-2 llega después con un número mayor.

# km0/simulaciones/paxos_un_valor.py
from dataclasses import dataclass, field


@dataclass
class Acceptor:
    nombre: str
    prometido: int | None = None                 # número más alto prometido
    aceptado: tuple[int, str] | None = None      # (número, valor) de la última propuesta aceptada

    def prepare(self, n: int) -> tuple[str, object]:
        if self.prometido is None or n > self.prometido:
            self.prometido = n
            return ("promise", self.aceptado)       # incluye lo que ya hubiera aceptado
        return ("nack", self.prometido)

    def accept(self, n: int, valor: str) -> tuple[str, object]:
        if self.prometido is None or n >= self.prometido:
            self.prometido = n
            self.aceptado = (n, valor)
            return ("accepted", n)
        return ("nack", self.prometido)


class Red:
    """Descarta los mensajes listados en `perdidos`: (proposer, acceptor, fase)."""
    def __init__(self) -> None:
        self.perdidos: set[tuple[str, str, str]] = set()

    def entrega(self, proposer: str, acceptor: str, fase: str) -> bool:
        return (proposer, acceptor, fase) not in self.perdidos


@dataclass
class Proposer:
    nombre: str
    id: int
    acceptors: list[Acceptor]
    red: Red
    ronda: int = 0
    traza: list[str] = field(default_factory=list)

    def _log(self, msg: str) -> None:
        print(f"  [{self.nombre}] {msg}")

    def proponer(self, valor: str) -> str | None:
        self.ronda += 1
        n = self.ronda * 10 + self.id                        # número único y creciente
        mayoria = len(self.acceptors) // 2 + 1
        self._log(f"fase 1: prepare(n={n}) queriendo proponer '{valor}'")

        promesas: list[tuple[int, str] | None] = []
        for a in self.acceptors:
            if not self.red.entrega(self.nombre, a.nombre, "prepare"):
                self._log(f"    prepare a {a.nombre} PERDIDO"); continue
            tipo, dato = a.prepare(n)
            self._log(f"    {a.nombre} -> {tipo} {dato if dato else ''}")
            if tipo == "promise":
                promesas.append(dato)
        if len(promesas) < mayoria:
            self._log(f"fase 1 fallida: {len(promesas)} promesas < mayoría {mayoria}")
            return None

        # Regla clave: si alguien ya aceptó algo, adoptar el valor del número más alto
        ya_aceptadas = [p for p in promesas if p is not None]
        if ya_aceptadas:
            n_prev, valor_prev = max(ya_aceptadas)
            if valor_prev != valor:
                self._log(f"fase 2: un acceptor ya aceptó ({n_prev}, '{valor_prev}'): ADOPTO '{valor_prev}' y abandono '{valor}'")
            valor = valor_prev
        self._log(f"fase 2: accept(n={n}, '{valor}')")

        aceptados = 0
        for a in self.acceptors:
            if not self.red.entrega(self.nombre, a.nombre, "accept"):
                self._log(f"    accept a {a.nombre} PERDIDO"); continue
            tipo, dato = a.accept(n, valor)
            self._log(f"    {a.nombre} -> {tipo} {dato}")
            aceptados += tipo == "accepted"
        if aceptados >= mayoria:
            self._log(f"ELEGIDO '{valor}' con n={n} ({aceptados} de {len(self.acceptors)})")
            return valor
        self._log(f"fase 2 fallida: {aceptados} aceptados < mayoría {mayoria}")
        return None


if __name__ == "__main__":
    red = Red()
    acceptors = [Acceptor("a1"), Acceptor("a2"), Acceptor("a3")]
    relay1 = Proposer("relay-1", id=1, acceptors=acceptors, red=red)
    relay2 = Proposer("relay-2", id=2, acceptors=acceptors, red=red)

    print("Ronda A: relay-1 propone, pero sus accept a a2 y a3 se pierden")
    red.perdidos = {("relay-1", "a2", "accept"), ("relay-1", "a3", "accept")}
    print("  resultado:", relay1.proponer("relay-1"))

    print("\nRonda B: relay-2 propone con número mayor; la red ya funciona")
    red.perdidos = set()
    print("  resultado:", relay2.proponer("relay-2"))

    print("\nRonda C: relay-1 reintenta con número aún mayor")
    print("  resultado:", relay1.proponer("relay-1"))

    print("\nEstado final de los acceptors:")
    for a in acceptors:
        print(f"  {a.nombre}: prometido={a.prometido}, aceptado={a.aceptado}")

Salida:

Ronda A: relay-1 propone, pero sus accept a a2 y a3 se pierden
  [relay-1] fase 1: prepare(n=11) queriendo proponer 'relay-1'
  [relay-1]    a1 -> promise
  [relay-1]    a2 -> promise
  [relay-1]    a3 -> promise
  [relay-1] fase 2: accept(n=11, 'relay-1')
  [relay-1]    a1 -> accepted 11
  [relay-1]    accept a a2 PERDIDO
  [relay-1]    accept a a3 PERDIDO
  [relay-1] fase 2 fallida: 1 aceptados < mayoría 2
  resultado: None

Ronda B: relay-2 propone con número mayor; la red ya funciona
  [relay-2] fase 1: prepare(n=12) queriendo proponer 'relay-2'
  [relay-2]    a1 -> promise (11, 'relay-1')
  [relay-2]    a2 -> promise
  [relay-2]    a3 -> promise
  [relay-2] fase 2: un acceptor ya aceptó (11, 'relay-1'): ADOPTO 'relay-1' y abandono 'relay-2'
  [relay-2] fase 2: accept(n=12, 'relay-1')
  [relay-2]    a1 -> accepted 12
  [relay-2]    a2 -> accepted 12
  [relay-2]    a3 -> accepted 12
  [relay-2] ELEGIDO 'relay-1' con n=12 (3 de 3)
  resultado: relay-1

Ronda C: relay-1 reintenta con número aún mayor
  [relay-1] fase 1: prepare(n=21) queriendo proponer 'relay-1'
  [relay-1]    a1 -> promise (12, 'relay-1')
  [relay-1]    a2 -> promise (12, 'relay-1')
  [relay-1]    a3 -> promise (12, 'relay-1')
  [relay-1] fase 2: accept(n=21, 'relay-1')
  [relay-1]    a1 -> accepted 21
  [relay-1]    a2 -> accepted 21
  [relay-1]    a3 -> accepted 21
  [relay-1] ELEGIDO 'relay-1' con n=21 (3 de 3)
  resultado: relay-1

Estado final de los acceptors:
  a1: prometido=21, aceptado=(21, 'relay-1')
  a2: prometido=21, aceptado=(21, 'relay-1')
  a3: prometido=21, aceptado=(21, 'relay-1')

Lo que enseña la ejecución:

En la ronda A, relay-1 obtiene las tres promesas pero solo a1 acepta: el valor no ha sido elegido (no hay mayoría). Sin embargo, a1 recuerda (11, 'relay-1').
En la ronda B, relay-2 quiere proponerse a sí mismo, pero la promesa de a1 le informa de que ya hay una propuesta aceptada. La regla de la fase 2 le obliga a abandonar su valor y adoptar relay-1, aunque relay-1 nunca llegó a ser elegido. Es un comportamiento conservador: Paxos no puede saber si (11, 'relay-1') fue aceptado por una mayoría de la que solo ve a un miembro, así que asume que pudo serlo. El resultado es que relay-2 hace elegir a relay-1.
En la ronda C, relay-1 reintenta y, naturalmente, confirma el mismo valor. Acuerdo preservado en las tres rondas, con mensajes perdidos y proposers compitiendo. Observa que los números de propuesta (11, 12, 21) nunca colisionan gracias a ronda * 10 + id.

Prueba a hacer que la ronda A pierda también el accept a a1: entonces ninguna promesa de la ronda B incluirá nada, y relay-2 será elegido. Y prueba a alternar perdidos para que cada proposer invalide las promesas del otro en fase 1: verás el livelock que motiva tener un líder.

Raft: términos, elección de líder y log replicado

Diego Ongaro y John Ousterhout publicaron Raft en 2014 con un objetivo declarado: ser comprensible, con la misma tolerancia a fallos y rendimiento que Multi-Paxos. Su estrategia fue descomponer el problema en tres subproblemas (elección de líder, replicación del log y seguridad) y reducir el número de estados posibles. Hoy es el algoritmo de etcd, Consul, CockroachDB, TiKV, Kafka (KRaft) y RabbitMQ (quorum queues), entre otros.

Términos y estados

El tiempo se divide en términos (terms), numerados de forma creciente. Cada término empieza con una elección; si la elección tiene éxito, un único líder gobierna el resto del término. Los términos actúan como reloj lógico (01-05): cada mensaje lleva el término del emisor, y un nodo que ve un término mayor que el suyo lo adopta inmediatamente y pasa a seguidor. Cada nodo está en uno de tres estados:

stateDiagram-v2
    [*] --> Seguidor
    Seguidor --> Candidato: timeout de elección sin latidos del líder
    Candidato --> Lider: votos de la mayoría
    Candidato --> Seguidor: descubre un líder o un término mayor
    Candidato --> Candidato: timeout sin mayoría (nuevo término)
    Lider --> Seguidor: descubre un término mayor

Elección de líder

Todo nodo empieza como seguidor y espera latidos (heartbeats) del líder. Cada seguidor tiene un timeout de elección aleatorio (típicamente entre 150 y 300 ms).
Si el timeout expira sin haber recibido latidos, el seguidor se convierte en candidato: incrementa su término, se vota a sí mismo y envía RequestVote a los demás.
Cada nodo concede un solo voto por término, al primer candidato que se lo pide y que cumpla la condición de seguridad de abajo. Si el candidato recibe votos de la mayoría, es líder y empieza a enviar latidos inmediatamente, lo que hace que los demás candidatos se rindan.
Si dos candidatos dividen los votos (ninguno con mayoría), ambos esperan un nuevo timeout aleatorio y lo intentan en un término nuevo. La aleatoriedad hace muy improbable que empaten repetidamente: en la práctica, uno de ellos expira antes y gana.

Es la aleatoriedad la que resuelve el livelock de Paxos y esquiva a FLP: seguridad siempre, terminación con probabilidad 1 cuando la red se estabiliza.

Replicación del log

Los clientes hablan solo con el líder. Cada operación se añade al log del líder como una entrada (índice, término, comando) y se envía a los seguidores con AppendEntries (el mismo mensaje que sirve de latido cuando va vacío). Cuando el líder sabe que la entrada está en una mayoría de logs, la marca como confirmada (committed), la aplica a su máquina de estados, responde al cliente e informa a los seguidores para que la apliquen también. Un seguidor con el log desalineado (por haber estado caído) es corregido por el líder, que le hace retroceder hasta el último punto en común y le reenvía el resto: el log del líder es siempre la verdad.

Seguridad

La propiedad que Raft demuestra es que una entrada confirmada nunca se pierde ni se sobreescribe, aunque cambie el líder. Dos reglas la garantizan:

Restricción de elección: un nodo solo vota por un candidato cuyo log esté al menos tan actualizado como el suyo (comparando el término de la última entrada y, a igualdad, el índice). Como una entrada confirmada está en una mayoría, y el candidato necesita votos de una mayoría, al menos un votante tiene la entrada y no votará por un candidato que no la tenga. El líder elegido tiene por tanto todas las entradas confirmadas, sin necesidad de la transferencia de estado de Paxos.
Commit solo de entradas del término actual: un líder solo cuenta réplicas para confirmar entradas de su propio término; las de términos anteriores se confirman indirectamente al confirmar una posterior. Evita un caso sutil en el que una entrada antigua replicada tardíamente pudiera confirmarse y después ser sobreescrita.

Raft especifica además los cambios de configuración (añadir o quitar nodos con configuración conjunta) y la compactación del log mediante snapshots, precisamente los huecos que Paxos dejaba abiertos.

Simulación: elección de líder en Raft y caída del líder

La siguiente simulación implementa la elección de líder de Raft con asyncio: tres nodos con timeouts aleatorios, términos, votos con restricción de log y latidos. No replica el log (los nodos tienen un log fijo para poder mostrar la restricción de elección), pero permite ver una elección real, la caída del líder y la reelección, y qué ocurre cuando un nodo con el log atrasado intenta ser líder.

# km0/simulaciones/raft_eleccion.py
import asyncio
import random

T0 = None


def ahora() -> float:
    return asyncio.get_running_loop().time() - T0


class Red:
    """Entrega mensajes con latencia aleatoria; no entrega a nodos caídos."""
    def __init__(self, nodos: dict, rng: random.Random):
        self.nodos, self.rng = nodos, rng

    async def llamar(self, destino: str, metodo: str, *args):
        await asyncio.sleep(self.rng.uniform(0.002, 0.010))     # latencia de red
        nodo = self.nodos[destino]
        if not nodo.vivo:
            await asyncio.sleep(0.05)                          # timeout de RPC
            return None
        return getattr(nodo, metodo)(*args)


class NodoRaft:
    def __init__(self, id: str, ultimo_indice: int, ultimo_termino: int, rng: random.Random,
                 primer_plazo: float | None = None):
        self.id, self.rng = id, rng
        self.primer_plazo = primer_plazo                 # para forzar quién expira primero en la demo
        self.estado = "seguidor"
        self.termino = 0
        self.votado_por: str | None = None
        self.ultimo_indice, self.ultimo_termino = ultimo_indice, ultimo_termino   # log fijo
        self.vivo = True
        self.plazo = 0.0
        self.red: Red | None = None

    # --- RPCs que reciben los otros nodos ------------------------------------
    def solicitar_voto(self, termino: int, candidato: str, ult_idx: int, ult_term: int):
        if termino > self.termino:
            self.termino, self.estado, self.votado_por = termino, "seguidor", None
        log_al_dia = (ult_term, ult_idx) >= (self.ultimo_termino, self.ultimo_indice)
        conceder = (termino == self.termino and self.votado_por in (None, candidato) and log_al_dia)
        if conceder:
            self.votado_por = candidato
            self._reiniciar_plazo()
        elif termino == self.termino and not log_al_dia:
            print(f"{ahora():6.3f}s  {self.id}: DENIEGO voto a {candidato} (su log ({ult_term},{ult_idx}) "
                  f"va por detrás del mío ({self.ultimo_termino},{self.ultimo_indice}))")
        return (self.termino, conceder)

    def recibir_latido(self, termino: int, lider: str):
        if termino >= self.termino:
            if self.estado != "seguidor" or termino > self.termino:
                print(f"{ahora():6.3f}s  {self.id}: reconozco a {lider} como líder del término {termino}")
            self.termino, self.estado, self.votado_por = termino, "seguidor", None
            self._reiniciar_plazo()
        return self.termino

    # --- bucle principal ------------------------------------------------------
    def _reiniciar_plazo(self) -> None:
        self.plazo = ahora() + self.rng.uniform(0.150, 0.300)

    async def ejecutar(self, pares: list[str]) -> None:
        self._reiniciar_plazo()
        if self.primer_plazo is not None:
            self.plazo = ahora() + self.primer_plazo
        while True:
            await asyncio.sleep(0.010)
            if not self.vivo:
                continue
            if self.estado == "lider":
                await asyncio.gather(*(self.red.llamar(p, "recibir_latido", self.termino, self.id) for p in pares))
                await asyncio.sleep(0.040)                      # latidos cada ~50 ms
            elif ahora() > self.plazo:
                await self._eleccion(pares)

    async def _eleccion(self, pares: list[str]) -> None:
        self.termino += 1
        self.estado, self.votado_por = "candidato", self.id
        self._reiniciar_plazo()
        print(f"{ahora():6.3f}s  {self.id}: timeout, me presento en el término {self.termino}")
        respuestas = await asyncio.gather(*(self.red.llamar(p, "solicitar_voto", self.termino, self.id,
                                                            self.ultimo_indice, self.ultimo_termino) for p in pares))
        if self.estado != "candidato":            # alguien más ganó mientras esperaba
            return
        votos = 1 + sum(1 for r in respuestas if r and r[1] and r[0] == self.termino)
        for r in respuestas:
            if r and r[0] > self.termino:
                self.termino, self.estado = r[0], "seguidor"; return
        if votos > (len(pares) + 1) // 2:
            self.estado = "lider"
            print(f"{ahora():6.3f}s  {self.id}: LÍDER del término {self.termino} con {votos} votos")


async def main() -> None:
    global T0
    T0 = asyncio.get_running_loop().time()
    rng = random.Random(3)
    # nodo-3 tiene el log atrasado (índice 3 frente a 5) y es el primero en expirar (0,12 s):
    # NO debe poder ser líder por mucho que se presente el primero
    nodos = {"nodo-1": NodoRaft("nodo-1", 5, 1, rng), "nodo-2": NodoRaft("nodo-2", 5, 1, rng),
             "nodo-3": NodoRaft("nodo-3", 3, 1, rng, primer_plazo=0.120)}
    red = Red(nodos, rng)
    for n in nodos.values():
        n.red = red
    tareas = [asyncio.create_task(n.ejecutar([p for p in nodos if p != n.id])) for n in nodos.values()]

    await asyncio.sleep(1.0)
    lider = next(n for n in nodos.values() if n.estado == "lider")
    print(f"{ahora():6.3f}s  --- {lider.id} CAE ---")
    lider.vivo = False
    await asyncio.sleep(1.0)
    print(f"{ahora():6.3f}s  --- {lider.id} VUELVE (cree seguir en el término {lider.termino}) ---")
    lider.vivo = True
    await asyncio.sleep(0.5)
    print("estado final:", {n.id: (n.estado, n.termino) for n in nodos.values()})
    for t in tareas:
        t.cancel()


if __name__ == "__main__":
    asyncio.run(main())

Salida (los tiempos pueden variar en unos milisegundos porque dependen del planificador de asyncio, pero la secuencia de hechos es la misma en cada ejecución gracias a la semilla y al primer_plazo de nodo-3):

 0.122s  nodo-3: timeout, me presento en el término 1
 0.125s  nodo-2: DENIEGO voto a nodo-3 (su log (1,3) va por detrás del mío (1,5))
 0.129s  nodo-1: DENIEGO voto a nodo-3 (su log (1,3) va por detrás del mío (1,5))
 0.194s  nodo-1: timeout, me presento en el término 2
 0.203s  nodo-1: LÍDER del término 2 con 3 votos
 1.001s  --- nodo-1 CAE ---
 1.153s  nodo-3: timeout, me presento en el término 3
 1.163s  nodo-2: DENIEGO voto a nodo-3 (su log (1,3) va por detrás del mío (1,5))
 1.281s  nodo-2: timeout, me presento en el término 4
 1.336s  nodo-2: LÍDER del término 4 con 2 votos
 2.001s  --- nodo-1 VUELVE (cree seguir en el término 2) ---
 2.003s  nodo-1: reconozco a nodo-2 como líder del término 4
estado final: {'nodo-1': ('seguidor', 4), 'nodo-2': ('lider', 4), 'nodo-3': ('seguidor', 4)}

Qué observar:

Restricción de elección en acción. nodo-3, con el log atrasado, es el primero en agotar su timeout y se presenta en el término 1, pero los otros dos le deniegan el voto porque su última entrada (1, 3) es anterior a la de ellos (1, 5). Nunca podrá ser líder mientras esté atrasado, lo que protege las entradas confirmadas que él no tiene. Su petición ha tenido un efecto, sin embargo: los demás han adoptado el término 1, y cuando nodo-1 expira poco después se presenta en el término 2 y gana con los tres votos (nodo-3 también le vota: su log está más al día que el suyo).
Caída y reelección. Al caer nodo-1, los latidos cesan. nodo-3 vuelve a ser el primero en expirar (término 3) y vuelve a ser denegado por nodo-2; nodo-1 no responde porque está caído. Unos 130 ms después expira nodo-2, se presenta en el término 4 y gana con dos votos (el suyo y el de nodo-3): mayoría de 3. El sistema ha estado sin líder unos 335 ms. Ese es el coste de disponibilidad de un sistema CP durante un fallo: acotado y pequeño, no indefinido. Observa que el término ha saltado de 2 a 4: los términos consumidos por elecciones fallidas no se reutilizan.
El líder antiguo vuelve. nodo-1 revive creyéndose líder del término 2, pero el primer latido de nodo-2 con término 4 le hace retroceder a seguidor. Los términos como reloj lógico evitan que haya dos líderes actuando: un mensaje con término antiguo es ignorado por todos. (En un sistema real, nodo-1 podría haber intentado enviar un AppendEntries de término 2 antes de recibir el latido; los seguidores lo rechazarían por término obsoleto.)

Si quitas el primer_plazo de nodo-3, el orden en que expiran los nodos depende de los timeouts aleatorios y la traza cambia en cada ejecución; en muchas de ellas nodo-3 ni siquiera llega a presentarse. Es lo que pasa en producción: la restricción de elección solo se manifiesta cuando el nodo atrasado expira antes que los demás.

Consenso bizantino: PBFT en una página

Todo lo anterior asume el modelo de fallo crash de 01-02: un nodo que falla, se calla. Si un nodo puede mentir (fallo bizantino: un bug que envía mensajes incoherentes, un disco que corrompe el log, un participante malicioso), Paxos y Raft no sirven: un acceptor que promete a dos proposers a la vez o un líder que envía logs distintos a cada seguidor rompen el acuerdo.

El consenso bizantino resuelve este caso con un coste mayor. El resultado clásico (Lamport, Shostak y Pease, 1982) es que se necesitan N ≥ 3f + 1 nodos para tolerar f bizantinos: 4 nodos para tolerar 1, 7 para tolerar 2. La intuición: con f mentirosos, una mayoría honesta de las respuestas que un nodo recibe (N - f, porque los mentirosos pueden callar) debe seguir siendo mayoría aunque f de esas respuestas sean falsas, lo que exige N - 2f > f. PBFT (Castro y Liskov, 1999) fue el primer algoritmo bizantino práctico: un líder (primary) propone el orden, y las réplicas intercambian tres rondas de mensajes firmados (pre-prepare, prepare, commit) de forma que cada una recoge 2f + 1 confirmaciones de las otras antes de ejecutar; si el líder se comporta mal, las réplicas lo cambian por votación (view change). El coste es O(N²) mensajes por decisión y firmas criptográficas en cada uno, frente a O(N) de Raft.

¿Cuándo hace falta? Cuando los nodos pertenecen a partes que no confían entre sí: cadenas de bloques con permisos (Hyperledger Fabric, Tendermint/Cosmos usan variantes de PBFT), sistemas de control aeroespacial con redundancia frente a hardware defectuoso, o consorcios. En Kilómetro Cero todos los nodos son de la misma organización y se protegen contra bugs con pruebas y contra intrusos con la seguridad del Módulo 6; un fallo bizantino interno se trata como un incidente, no con consenso bizantino. Raft basta y sobra.

Tabla comparativa: Paxos, Raft y PBFT

Aspecto	Paxos (Multi-Paxos)	Raft	PBFT
Modelo de fallo	Crash (parada / recuperación)	Crash	Bizantino
Nodos para tolerar f fallos	2f + 1	2f + 1	3f + 1
Líder	Opcional en teoría; distinguido en Multi-Paxos	Obligatorio; elección integrada con timeouts aleatorios	Primary con cambio de vista
Mensajes por decisión (régimen estable)	O(N): solo fase 2 con líder estable	O(N): un `AppendEntries`	O(N²), firmados
Comprensibilidad	Baja; huecos de especificación	Alta; especificación completa (membresía, snapshots)	Media-baja
Quién puede ser líder	Cualquiera (recibe el estado en fase 1)	Solo quien tiene el log al día	Rotación determinista
Seguridad garantizada	Siempre	Siempre	Siempre (con f < N/3)
Terminación	Con sincronía parcial y líder estable	Con sincronía parcial (aleatoriedad)	Con sincronía parcial
Usado en	Chubby, Spanner, Cassandra (LWT), Neo4j	etcd, Consul, CockroachDB, TiKV, Kafka KRaft, RabbitMQ quorum queues	Hyperledger Fabric, Tendermint, sistemas críticos

Sistemas que lo implementan y su uso en Kilómetro Cero: `etcd` y el relay outbox

Casi nadie implementa Raft o Paxos para su aplicación: se usa un sistema de coordinación que lo encapsula y expone primitivas sencillas sobre un almacén clave-valor linealizable:

Sistema	Algoritmo	Primitivas	Dónde se ve
etcd	Raft	Clave-valor con revisiones, leases (TTL), watch, transacciones compare-and-swap	Kubernetes guarda ahí todo su estado
ZooKeeper	ZAB (similar a Raft, anterior)	Znodes jerárquicos, nodos efímeros y secuenciales, watches	Kafka (hasta KRaft), HBase, Hadoop
Consul	Raft	Clave-valor, sesiones, descubrimiento de servicios, health checks	Service mesh HashiCorp

Los tres son PC/EC en la tabla de 03-02: cada escritura pasa por consenso y el lado minoritario de una partición rechaza escrituras (y, por defecto, lecturas linealizables). Se despliegan en clústeres de 3 o 5 nodos y se usan para datos pequeños y críticos: quién es líder, qué configuración está vigente, qué nodos están vivos. Nunca para datos de aplicación (el stock, los pedidos): son lentos por diseño y su capacidad es de megabytes, no de terabytes.

El problema de Kilómetro Cero

En 02-05 escribimos el relay del patrón Outbox: un proceso que lee de la tabla outbox de km0_pedidos con FOR UPDATE SKIP LOCKED y publica en pedidos.eventos. Con una instancia funciona. Pero pedidos se despliega con tres réplicas en Kubernetes (01-06), y si las tres ejecutan el relay, aunque SKIP LOCKED evite que dos cojan la misma fila a la vez, el orden de publicación por pedido deja de estar garantizado (dos relays publican filas del mismo pedido en paralelo) y el relay que muere tras publicar y antes de marcar duplica eventos con más frecuencia. Queremos una sola instancia activa y que, si muere, otra tome el relevo en segundos. Es una elección de líder, y la haremos con etcd.

Añadimos etcd al docker-compose.yml:

  etcd:
    image: quay.io/coreos/etcd:v3.5.15
    command: >
      etcd --name etcd0
           --listen-client-urls http://0.0.0.0:2379
           --advertise-client-urls http://etcd:2379
    ports:
      - "2379:2379"

(Un solo nodo para desarrollo; en producción serían 3 o 5, porque un etcd de un nodo es un punto único de fallo que no tolera nada.) El mecanismo se apoya en dos primitivas de etcd:

Lease: un contrato con TTL. Las claves asociadas a un lease desaparecen automáticamente si el cliente deja de renovarlo (keep-alive). Si el relay líder muere, su clave se borra sola al expirar el TTL.
Transacción compare-and-swap: "si la clave no existe, créala con mi identidad y este lease". Como etcd es linealizable, solo una de varias instancias concurrentes verá "no existe" y ganará.

# km0/servicios/pedidos/relay_lider.py
import os
import socket
import time

import etcd3                                   # pip install etcd3
from etcd3.events import DeleteEvent

CLAVE = "/km0/lider/relay-outbox"
TTL_SEGUNDOS = 10
YO = f"{socket.gethostname()}-{os.getpid()}"

cliente = etcd3.client(host=os.environ.get("ETCD_HOST", "etcd"), port=2379)


def intentar_ser_lider(lease) -> bool:
    """Crea la clave solo si no existe (compare-and-swap linealizable)."""
    exito, _ = cliente.transaction(
        compare=[cliente.transactions.version(CLAVE) == 0],        # version 0 = la clave no existe
        success=[cliente.transactions.put(CLAVE, YO, lease=lease)],
        failure=[],
    )
    return exito


def esperar_a_que_quede_libre() -> None:
    valor, _ = cliente.get(CLAVE)
    print(f"[{YO}] líder actual: {valor.decode() if valor else '(ninguno)'}; espero")
    eventos, cancelar = cliente.watch(CLAVE)
    for evento in eventos:
        if isinstance(evento, DeleteEvent):       # el lease del líder expiró o lo revocó
            break
    cancelar()


def publicar_pendientes() -> int:
    """El relay de 02-05: lee outbox FOR UPDATE SKIP LOCKED, publica en Kafka, marca publicado_en."""
    ...
    return 0


def bucle() -> None:
    while True:
        lease = cliente.lease(TTL_SEGUNDOS)
        if not intentar_ser_lider(lease):
            lease.revoke()
            esperar_a_que_quede_libre()
            continue
        print(f"[{YO}] SOY LÍDER del relay outbox")
        try:
            while True:
                publicar_pendientes()
                respuesta = lease.refresh()             # keep-alive: si falla, hemos perdido el liderazgo
                if not respuesta or respuesta[0].TTL <= 0:
                    raise RuntimeError("no he podido renovar el lease")
                time.sleep(1)
        except Exception as e:
            print(f"[{YO}] dejo de ser líder: {e}")
        finally:
            try:
                lease.revoke()                          # liberar cuanto antes para que otro tome el relevo
            except Exception:
                pass


if __name__ == "__main__":
    bucle()

Cómo se comporta con tres réplicas de pedidos:

Las tres arrancan y ejecutan intentar_ser_lider. etcd, vía Raft, procesa las tres transacciones en un orden total; la primera ve version == 0 y crea la clave; las otras dos ven que ya existe y pasan a esperar_a_que_quede_libre, bloqueadas en un watch (sin sondeo).
La líder publica cada segundo y renueva el lease. Si es desplegada de nuevo o muere limpiamente, revoke borra la clave al instante; si muere de golpe (kill -9, nodo caído), la clave desaparece cuando el lease expira, como máximo 10 segundos después.
El watch de las otras dos recibe el DeleteEvent, y ambas vuelven a intentar intentar_ser_lider; exactamente una gana. El relay ha estado parado entre 0 y 10 segundos: los eventos se acumulan en outbox (nada se pierde) y se publican en orden al reanudar.

Hay una sutileza que conviene entender bien. Si la líder queda aislada de etcd (partición) pero sigue viva y conectada a PostgreSQL y Kafka, su lease expirará sin que pueda renovarlo, otra instancia tomará el liderazgo, y durante unos segundos podría haber dos relays publicando: la nueva y la antigua, que aún no sabe que ha perdido. El refresh que falla y detiene el bucle acota esa ventana, pero no la elimina (entre el último refresh con éxito y la expiración hay hasta 10 segundos). Este es el problema clásico de los locks distribuidos y tiene dos remedios: aceptar la ventana porque los consumidores son idempotentes (nuestro caso: 02-05 ya nos protege de duplicados) o usar un token de cercado (fencing token): la mod_revision que etcd asigna a la clave del líder, monótonamente creciente, se incluye en cada UPDATE outbox ... WHERE publicado_en IS NULL AND lider_revision <= %s, de modo que la base de datos rechace las escrituras de un líder antiguo. Los locks distribuidos y el fencing reaparecerán en 07-03 al hablar de failover.

Errores Comunes y Consejos

Implementar el consenso a mano. Paxos y Raft parecen cortos en papel y son traicioneros en código (los propios autores de Raft mantienen una lista de errores comunes en implementaciones publicadas). Usa etcd, ZooKeeper o Consul, o una biblioteca madura, y dedica el esfuerzo a la aplicación.
Clúster de coordinación con número par de nodos. Cuatro nodos toleran un fallo, igual que tres, pero con más coste y más probabilidad de que un fallo ocurra. Usa 3 o 5.
Usar el almacén de coordinación como base de datos. etcd tiene un límite práctico de unos pocos GB y cada escritura pasa por Raft y por fsync en la mayoría. Guardar ahí posiciones de furgonetas lo colapsaría en minutos.
Un lock distribuido sin token de cercado en operaciones no idempotentes. Si el efecto protegido por el lock no tolera un ejecutor antiguo, la expiración del lease no basta; hay que cercar en el recurso (la base de datos, el almacén) con la revisión del lease.
Timeouts de elección demasiado cortos. Si el timeout de elección es del orden de la latencia de red, cualquier congestión provoca elecciones continuas (el líder no llega a enviar latidos a tiempo). Raft recomienda que el tiempo de latido sea un orden de magnitud menor que el timeout de elección, y este un orden de magnitud menor que el tiempo medio entre fallos.
Confundir "mayoría de los configurados" con "mayoría de los vivos". La mayoría es siempre sobre el número total de nodos del clúster, no sobre los que responden. Un clúster de 5 con 3 caídos no puede elegir líder con "2 de 2 vivos": no hay mayoría, y eso es correcto (podría haber otros 3 vivos al otro lado de una partición eligiendo lo contrario).
Consejo: al depurar un sistema basado en Raft, mira los términos. Un término que crece rápidamente significa elecciones continuas: red inestable, timeouts mal ajustados o un nodo con reloj de CPU sobrecargado.
Consejo: documenta qué decisiones de Kilómetro Cero pasan por consenso (liderazgo de relays y planificadores, configuración) y cuáles no (todo el dato de negocio), y por qué. Es la lista que un nuevo miembro del equipo necesita antes de tocar etcd.

Ejercicios

Ejercicio 1: Paxos con mensajes perdidos en fase 1

Con la simulación del apartado 5, configura la red para que en la ronda A se pierdan los accept de relay-1 a a1 y a3 (solo a2 acepta), y en la ronda B se pierda el prepare de relay-2 precisamente a a2. ¿Qué valor propone relay-2 en la fase 2 y qué valor acaba elegido? ¿Se viola el acuerdo? Ejecuta la ronda C y explica el estado final.

Ejercicio 2: Dividir votos en Raft

Modifica la simulación del apartado 7 para que los tres nodos tengan el mismo log (índice 5) y para que el rango de timeouts sea muy estrecho, uniform(0.150, 0.151). Ejecuta varias veces y describe qué ocurre en los primeros términos. ¿Se viola alguna vez la seguridad (dos líderes en el mismo término)? ¿Qué se viola? Vuelve al rango original y compara.

Ejercicio 3: Diseñar el uso de etcd

Kilómetro Cero necesita que el servicio reparto ejecute un único planificador que asigne pedidos a repartidores cada 30 segundos, y que además todos los nodos de reparto conozcan la lista de mercados activos (Girona, Lleida, Tarragona, Valencia) que un administrador puede cambiar. Diseña las claves de etcd, indica qué primitivas usarías para cada necesidad (lease, transacción, watch) y explica qué ocurre paso a paso si el nodo planificador queda aislado de etcd durante 25 segundos con un lease de 10. ¿Necesitas token de cercado? Justifícalo.

Soluciones

Solución 1:

Ronda A: relay-1 obtiene tres promesas (n=11), pero solo a2 acepta (11, 'relay-1'): no hay mayoría, no hay valor elegido. Ronda B: relay-2 envía prepare(12) a a1 y a3 únicamente (el de a2 se pierde); ambos responden promise sin propuesta aceptada, lo que es mayoría (2 de 3). Como ninguna promesa incluye nada, relay-2 propone su propio valor 'relay-2'. En la fase 2 lo aceptan los tres: a2 también, porque nunca prometió nada mayor que 11 y un accept(12) supera esa promesa (un acceptor no necesita haber recibido el prepare para aceptar; solo necesita no haber prometido un número mayor). 'relay-2' queda elegido y la antigua (11, 'relay-1') de a2 queda sobreescrita: nunca formó parte de una mayoría, así que no importaba. Ronda C: relay-1 hace prepare(21) a los tres, los tres informan de (12, 'relay-2'), y relay-1 adopta 'relay-2' y lo confirma con n=21. Estado final: todos con (21, 'relay-2'). El acuerdo se conserva: el valor elegido en B es el que se confirma en C. Es el caso simétrico del apartado 5: allí la propuesta parcial de relay-1 "sobrevivió" porque el único acceptor que la tenía estaba en la mayoría de promesas de relay-2; aquí no lo estaba y se descartó. Ambos desenlaces son correctos, porque en ninguno de los dos casos el valor parcial había sido elegido.

Solución 2:

Con timeouts casi iguales, los tres nodos agotan el plazo prácticamente a la vez y se presentan en el mismo término; cada uno se vota a sí mismo y, como solo hay un voto por término, ninguno alcanza dos votos: votos divididos. Todos reinician el plazo (de nuevo casi igual) y repiten en el término siguiente, y así varias veces; los términos crecen rápidamente sin líder. En algún momento las pequeñas diferencias de latencia (el uniform(0.002, 0.010) de la red) hacen que un candidato pida el voto antes de que otro se haya presentado, y gana. Nunca hay dos líderes en el mismo término (la seguridad se mantiene: un voto por término y mayoría), pero se viola temporalmente la vivacidad: el sistema tarda mucho en decidir. Con el rango original (150-300 ms), la probabilidad de que dos nodos expiren en la misma ventana de latencia es pequeña y la elección suele resolverse en el primer o segundo término. Es la demostración empírica de por qué Raft usa timeouts aleatorios y de cómo la aleatoriedad esquiva a FLP en la práctica.

Solución 3:

Claves: /km0/lider/planificador-reparto (valor: identidad de la instancia, con lease de 10 s) y /km0/config/mercados-activos (valor JSON ["girona","lleida","tarragona","valencia"], sin lease: es configuración persistente).

Primitivas: para el planificador, el mismo esquema del apartado 10: lease + transacción version == 0 + watch del borrado; el líder ejecuta la asignación cada 30 s y renueva el lease cada 3 s. Para los mercados, cada nodo de reparto hace un get al arrancar y un watch permanente sobre la clave; el administrador escribe con un put normal (o con una transacción condicionada a mod_revision para evitar pisar cambios concurrentes); el watch entrega el nuevo valor a todos los nodos en milisegundos, sin sondeo.

Aislamiento de 25 s: t=0, última renovación con éxito. t≈3, el refresh falla; el bucle del líder debe detener la planificación inmediatamente (no seguir "por si acaso"). t=10, el lease expira en etcd, la clave se borra, las otras instancias reciben el DeleteEvent y una gana. t=25, el antiguo líder recupera la conexión, intenta renovar un lease que ya no existe, pasa a esperar_a_que_quede_libre y se queda como seguidor. Ventana peligrosa: entre t=0 y t≈3 el antiguo líder aún se cree líder legítimamente, pero como no hay nuevo líder hasta t=10, no hay dos planificadores a la vez siempre que el antiguo se detenga al fallar el refresh. Si el antiguo no comprobase el refresh (o si una asignación ya en curso tarda más que el TTL restante), sí podría solaparse con el nuevo.

Token de cercado: la asignación de un pedido a un repartidor no es idempotente por naturaleza (dos planificadores podrían asignar el mismo pedido a furgoneta-3 y a otra furgoneta). Es prudente incluir la mod_revision de la clave del líder en la escritura de la asignación (UPDATE pedidos_reparto SET repartidor = %s, lider_revision = %s WHERE id = %s AND (lider_revision IS NULL OR lider_revision <= %s)), de modo que una asignación de un líder antiguo sea rechazada por la base de datos. Alternativamente, hacer la asignación idempotente por pedido (una sola fila de asignación por pedido con INSERT ... ON CONFLICT DO NOTHING, como en 02-05) elimina la necesidad del token para este caso concreto, aunque no evitaría que dos planificadores compitieran por asignar al mismo repartidor más de sus 8 pedidos.

Conclusión

El consenso es el problema de que varios nodos decidan un único valor cumpliendo acuerdo, validez y terminación, y esta lección lo ha resuelto en los tres niveles anunciados. FLP nos recordó que en un sistema asíncrono no se puede garantizar la terminación, y vimos que la respuesta de la industria es separar seguridad (siempre) de vivacidad (cuando la red se comporta): con mayorías de 2f + 1 nodos, timeouts y aleatoriedad. Paxos resuelve el consenso de un valor con proposers, acceptors y learners en dos fases, y su regla central (adoptar el valor ya aceptado con número más alto) es lo que hizo que relay-2, en la simulación, acabara eligiendo a relay-1; Multi-Paxos lo extiende a un log, dejando huecos que cada implementación rellena. Raft cubre esos huecos con términos, elección por timeouts aleatorios, replicación de log con commit por mayoría y la restricción de que solo puede ser líder quien tiene el log al día, y la simulación con asyncio mostró a nodo-3 denegado dos veces por su log atrasado, al líder nodo-1 caer y a nodo-2 tomar el relevo en unos 335 ms, con el término saltando de 2 a 4. El consenso bizantino, con 3f + 1 nodos y PBFT, queda para cuando los participantes no confían entre sí, que no es el caso de Kilómetro Cero. Y el primer uso práctico ha sido concreto: etcd con un lease y una transacción compare-and-swap garantiza que solo una instancia del relay outbox publica, con el matiz del token de cercado para la ventana en la que un líder aislado aún no sabe que ha dejado de serlo.

Sabemos ya nombrar las garantías (03-01), elegir qué sacrificar ante una partición (03-02) y hacer que un grupo de nodos se ponga de acuerdo (03-03). Lo que aún no hemos hecho es mover los datos de verdad: cómo llega una fila insertada en el primario de km0_pedidos a su réplica, qué se pierde si el primario muere antes de que llegue, qué pasa cuando dos regiones aceptan escrituras a la vez, y cómo funcionan los quórums de lectura y escritura con los que Cassandra y DynamoDB ofrecen consistencia ajustable sin un líder. Es el tema de la siguiente lección, Replicación de Datos, donde además montaremos una réplica PostgreSQL real en el docker-compose.yml de Kilómetro Cero y la veremos llegar tarde.

Algoritmos de Consenso

Contenido

El problema del consenso

Por qué es difícil: FLP y la salida práctica

Para qué se usa el consenso

Paxos: roles, fases y números de propuesta

Simulación: Paxos con dos proposers en conflicto

Raft: términos, elección de líder y log replicado

Términos y estados

Elección de líder

Replicación del log

Seguridad

Simulación: elección de líder en Raft y caída del líder

Consenso bizantino: PBFT en una página

Tabla comparativa: Paxos, Raft y PBFT

Sistemas que lo implementan y su uso en Kilómetro Cero: `etcd` y el relay outbox

El problema de Kilómetro Cero

Errores Comunes y Consejos

Ejercicios

Ejercicio 1: Paxos con mensajes perdidos en fase 1

Ejercicio 2: Dividir votos en Raft

Ejercicio 3: Diseñar el uso de etcd

Soluciones

Conclusión

Curso de Arquitecturas Distribuidas

Módulo 1: Introducción a los Sistemas Distribuidos

Módulo 2: Comunicación en Sistemas Distribuidos

Módulo 3: Consistencia y Replicación

Módulo 4: Almacenamiento Distribuido

Módulo 5: Computación Distribuida

Módulo 6: Seguridad en Sistemas Distribuidos

Módulo 7: Monitoreo y Mantenimiento

Módulo 8: Casos de Estudio y Aplicaciones

Algoritmos de Consenso

Contenido

El problema del consenso

Por qué es difícil: FLP y la salida práctica

Para qué se usa el consenso

Paxos: roles, fases y números de propuesta

Simulación: Paxos con dos proposers en conflicto

Raft: términos, elección de líder y log replicado

Términos y estados

Elección de líder

Replicación del log

Seguridad

Simulación: elección de líder en Raft y caída del líder

Consenso bizantino: PBFT en una página

Tabla comparativa: Paxos, Raft y PBFT

Sistemas que lo implementan y su uso en Kilómetro Cero: etcd y el relay outbox

El problema de Kilómetro Cero

Errores Comunes y Consejos

Ejercicios

Ejercicio 1: Paxos con mensajes perdidos en fase 1

Ejercicio 2: Dividir votos en Raft

Ejercicio 3: Diseñar el uso de etcd

Soluciones

Conclusión

Curso de Arquitecturas Distribuidas

Módulo 1: Introducción a los Sistemas Distribuidos

Módulo 2: Comunicación en Sistemas Distribuidos

Módulo 3: Consistencia y Replicación

Módulo 4: Almacenamiento Distribuido

Módulo 5: Computación Distribuida

Módulo 6: Seguridad en Sistemas Distribuidos

Módulo 7: Monitoreo y Mantenimiento

Módulo 8: Casos de Estudio y Aplicaciones

Sistemas que lo implementan y su uso en Kilómetro Cero: `etcd` y el relay outbox