Resumen

  • El resultado conjunto de Fischer, Lynch y Paterson es existencial: para cualquier protocolo determinista de consenso parcialmente correcto hay una ejecución admisible que no decide bajo su modelo asíncrono con una caída posible.
  • Una configuración bivalente conserva accesibles los valores 0 y 1. La conmutación de eventos independientes permite aplazar el paso crítico sin sacrificar la entrega final de mensajes ni la equidad del planificador.
  • Los relojes parciales, los detectores de fallos y el azar añaden supuestos. Un temporizador puede ordenar una reacción, pero no certifica que el nodo remoto haya muerto.

En un centro de operaciones, treinta segundos de silencio parecen una medida objetiva. En el modelo de FLP no lo son: no existe un límite contra el cual comparar esos segundos. El nodo silencioso puede haberse detenido, avanzar despacio o esperar un mensaje retrasado. Desde fuera, esas historias aún son indistinguibles.

Michael J. Fischer, Nancy A. Lynch y Michael S. Paterson convirtieron esa indistinguibilidad en una prueba de 1985. Su teorema no declara que un clúster nunca pueda acordar un valor. Dice que ningún algoritmo determinista, seguro en el modelo elegido, puede prometer terminación en todas las ejecuciones admisibles si se tolera una sola caída.

Fiabilidad sin calendario

Los procesos dan pasos deterministas y se comunican por mensajes. No hay velocidad mínima para un proceso, demora máxima para la red ni reloj sincronizado. Los mensajes pueden reordenarse o tardar arbitrariamente, pero deben entregarse correctamente y una sola vez. Si el destinatario no falla y sigue recibiendo, su mensaje acaba llegando.

Una ejecución admisible permite como máximo un proceso defectuoso y exige entrega a los no defectuosos. Estos últimos dan infinitos pasos. Por eso la ejecución adversa de la prueba no depende de ocultar para siempre un paquete. Puede recorrer los procesos y atender la cola con equidad, dejando a la vez la decisión siempre para después.

El requisito de progreso que se derrota es incluso débil: bastaría con que algún proceso decidiera en cada ejecución admisible. La imposibilidad de garantizar eso arrastra cualquier condición de terminación más fuerte.

Dos futuros dentro de una configuración

Una configuración combina los estados locales y los mensajes pendientes. Si todas sus continuaciones decisivas producen 0, es 0-valente; si producen 1, es 1-valente; si ambos resultados siguen al alcance, es bivalente.

La primera parte de la prueba encuentra una configuración inicial bivalente. Si todas fueran univalentes, al cambiar las entradas una por una aparecerían dos configuraciones vecinas con resultados opuestos. Solo diferirían en un proceso. Si ese proceso cae antes de actuar, los demás no pueden distinguirlas, aunque la especificación les exige decisiones distintas.

La segunda parte se concentra en un evento aplicable, por ejemplo la recepción de un mensaje. Supongamos que aplazarlo y ejecutarlo después siempre fuerza una valencia. En algún punto habría una frontera crítica. Pero los pasos de procesos distintos conmutan: A seguido de B alcanza el mismo estado que B seguido de A. El cuadrado resultante obligaría a un mismo estado a heredar valencias incompatibles.

Así, el planificador siempre puede avanzar durante un tramo finito, aplicar finalmente el evento y seguir en una configuración bivalente. Repite el procedimiento, rota por procesos y mensajes, y obtiene una ejecución infinita que cumple las reglas sin decidir.

Una frontera, no una explicación universal

La existencia de esa ejecución no convierte todas las ejecuciones en ella. Los sistemas reales progresan cuando la red se comporta mejor que el peor caso o cuando el diseño incorpora información ausente del modelo. FLP elimina la garantía incondicional; no elimina el funcionamiento observado.

Tampoco convierte un incidente en demostración matemática. Una elección puede atascarse por pérdida real de paquetes, saturación, un error de membresía o un defecto de implementación. Usar “FLP” como diagnóstico sin identificar la seguridad que limita los pasos y la indistinguibilidad entre demora y caída añade prestigio, no causalidad.

Cómo cambia el contrato

La sincronía parcial de Dwork, Lynch y Stockmeyer admite que existan límites desconocidos o que límites conocidos solo valgan después de un momento de estabilización desconocido. El protocolo puede progresar cuando esa época llega.

Los detectores de fallos de Chandra y Toueg ofrecen propiedades declaradas de completitud y precisión. No observan la muerte directamente: añaden una fuente de sospecha con garantías. Los protocolos aleatorios, como el de Ben-Or, cambian el determinismo por decisiones probabilísticas y formulan de otro modo la promesa de terminación.

Cada familia paga por su progreso con un supuesto visible. Esa contabilidad, no el pesimismo, es el legado operativo de FLP.

La autoría y la lección de Lynch

Lynch recuerda que ella y Fischer comenzaron a trabajar en el problema en 1982 y que Paterson se incorporó al camino que llevó a la prueba. Mantener la triple autoría importa: el argumento es una obra compartida, aunque la trayectoria posterior de Lynch convirtiera el modelado formal de sistemas distribuidos en un programa de investigación duradero.

Un protocolo serio debe publicar qué fallos tolera, qué significa su reloj, qué promete su detector y cuándo preservará seguridad aunque pierda disponibilidad. FLP no exige abandonar el consenso. Exige nombrar el mundo en el que se promete.

Fuentes