Saltar a contenido

Failure Detector Formal Properties

El paper SWIM construye sobre cuatro propiedades formales de failure detectors definidas por Chandra-Toueg (1996): Strong Completeness, Speed, Accuracy y Network Load. FLP (Fischer-Lynch-Paterson 1985) prueba que en redes asíncronas no se puede tener Strong Completeness Y Accuracy perfecta — todos los failure detectors prácticos eligen completeness y minimizan false positives. Esto explica por qué SWIM (y por extensión Camunda) siempre declara muertos los nodos lentos en lugar de arriesgarse a ignorar uno realmente muerto.

Las cuatro propiedades de Chandra-Toueg

Definidas en "Unreliable failure detectors for reliable distributed systems" (Journal of the ACM, 1996). Citadas verbatim por el paper SWIM:

1. Strong Completeness

"Crash-failure of any group member is detected by all non-faulty members."

Implicación: si un nodo se cae, eventualmente TODOS los nodos sanos lo detectan. No es aceptable que un nodo "se pierda" un evento de muerte.

2. Speed of failure detection

"The time interval between a member failure and its detection by some non-faulty group member."

Métrica de latencia: cuánto tarda algún nodo en darse cuenta. Distinto de la latencia de propagación al resto del cluster.

3. Accuracy

"The rate of false positives of failure detection."

Métrica de precisión: con qué frecuencia se declara muerto a un nodo que en realidad está vivo (slow processes, GC pauses, network blips).

4. Network Message Load

"In bytes per second generated by the protocol."

Métrica de costo: bytes/seg consumidos por el detector, idealmente independiente del tamaño del cluster.

El resultado de imposibilidad FLP

Fischer-Lynch-Paterson (1985) probaron:

"The impossibility of building a failure detector over an asynchronous network that is both accurate (no false detections) and strongly complete."

Razonamiento intuitivo: en una red asíncrona, no hay forma de distinguir entre: - Un nodo que se cayó (no responderá nunca) - Un nodo que es muy lento o tiene packet loss alto (responderá eventualmente)

Si insistes en accuracy perfecta (no false positives), tienes que esperar infinitamente antes de declarar a alguien muerto — y entonces nunca completas.

La elección de SWIM (y de Camunda)

"Most failure detectors, including heartbeating-based solutions, guarantee this property [Strong Completeness] while attempting to maintain a low rate of false positives. SWIM takes the same approach."

Decisión universal en sistemas distribuidos prácticos:

  1. Garantizar Strong Completeness (no perder muertes).
  2. Minimizar — no eliminar — false positives mediante mecanismos como Suspicion (ver incarnation-numbers).
  3. Tolerar el costo de false positives (un nodo "rejuvenece" después de un blip).

Camunda hereda esta filosofía vía el fork de Atomix. Los defaults failureTimeout = 10 sec + suspectProbes = 3 son la materialización concreta del trade-off "esperar suficiente para distinguir slow de dead, sin esperar demasiado".

Lower bound de network load (Gupta-Chandra-Goldszmidt 2001)

El paper SWIM cita [12] (precursor del propio grupo de Cornell):

"[12] calculates this load as (N · log(1/PM(F)) · log(qF)) / log(qS), where qF is the prob. of a packet drop within the underlying network."

Donde: - N = tamaño del grupo - PM(F) = probability of false detection (fija por el usuario) - qF = packet drop probability - qS = packet success probability (= 1 - qF)

Insight: este es el mínimo teórico que cualquier failure detector debe gastar. Define la baseline contra la cual comparar protocolos.

"All-to-all heartbeat protocols ... have a sub-optimality factor that varies linearly with group size."

Es decir: heartbeating gasta N× el mínimo. SWIM logra constante por nodo, alcanzando el lower bound asintóticamente.

Aplicación al MVP

Si el MVP single-node arranca con una sola partición, no necesita failure detector formal. Pero apenas se vaya a multi-node:

Decisión 1: ¿Strong Completeness o Eventual Completeness?

  • Strong Completeness: todo nodo sano detecta toda muerte (lo que hace SWIM y Camunda).
  • Eventual Completeness (más débil): basta con que alguno detecte y propague.

Para un MVP centrado en Postgres, una alternativa es delegar a Postgres mismo (vía pg_stat_replication y connection state) y aceptar Eventual Completeness con TTL conservador (~30s). Trade-off: latencia mayor a cambio de no implementar SWIM custom.

Decisión 2: ¿Cuánto tolerar false positives?

Política Aceptable cuándo
Aggressive (5s timeout) Workloads idempotentes; aceptar duplicados
Conservative (30s timeout) State con side effects no idempotentes
SWIM-style (10s con suspicion) Multi-region donde GC pauses son comunes

Decisión 3: ¿Network load es bottleneck?

Para clusters de < 10 nodos, heartbeats simples (load O(N²) = 100) son irrelevantes. SWIM brilla a partir de 50+ nodos donde el ahorro O(N) → O(1) per-node es real.

Cross-refs