Consenso Distribuido

El consenso distribuido es el problema de lograr que un conjunto de procesos se ponga de acuerdo sobre un único valor a pesar de los retrasos en los mensajes y los fallos de los procesos, y es la abstracción central de la computación tolerante a fallos.

Definition

El consenso requiere que cada proceso no defectuoso, partiendo de una entrada propuesta, decida finalmente un valor de salida tal que todos los procesos no defectuosos decidan el mismo valor (acuerdo), el valor haya sido propuesto por algún proceso (validez), y cada proceso no defectuoso decida finalmente (terminación).

Scope

Este tema cubre la especificación formal del consenso (acuerdo, validez, integridad y terminación), el teorema de imposibilidad FLP y las formas en que se elude —sincronía parcial, detectores de fallos no fiables y aleatorización—, y la equivalencia del consenso con la difusión atómica y las máquinas de estado replicadas. Trata el escenario de fallos por caída; el escenario bizantino se trata en un tema relacionado.

Core questions

• ¿Qué debe garantizar exactamente un protocolo para ser un algoritmo de consenso correcto?
• ¿Por qué el consenso asíncrono determinista es imposible con incluso una sola caída?
• ¿Qué suposiciones adicionales —sincronía, detectores de fallos, aleatoriedad— restauran la resolubilidad?

Key theories

Imposibilidad FLP

Ningún protocolo determinista resuelve el consenso en un sistema asíncrono de paso de mensajes si incluso un proceso puede fallar, porque cada protocolo tiene una ejecución que puede ser dirigida para ejecutarse indefinidamente sin decidir.

Enfoque del detector de fallos

Aumentar un sistema asíncrono con un detector de fallos no fiable que sea finalmente preciso restaura la resolubilidad del consenso, y el detector más débil que es suficiente ha sido caracterizado con precisión.

Consenso aleatorio

Permitir que los procesos lancen monedas permite que el consenso termine con probabilidad uno incluso en un sistema completamente asíncrono, intercambiando la terminación determinista por la terminación probabilística para escapar de la barrera FLP.

Clinical relevance

Todo sistema distribuido fuertemente consistente —registros replicados, servicios de coordinación, almacenes de configuración— resuelve el consenso internamente, por lo que las garantías y límites establecidos aquí limitan directamente lo que dichos sistemas pueden prometer sobre la consistencia y la disponibilidad.

History

El teorema FLP de 1985 estableció la imposibilidad fundamental; el protocolo aleatorio de Ben-Or de 1983 y el marco de detectores de fallos de Chandra y Toueg de 1996 mostraron dos formas complementarias de hacer que el consenso fuera resoluble, definiendo la agenda de investigación para las décadas siguientes.

Key figures

• Michael Fischer
• Nancy Lynch
• Michael Paterson
• Tushar Chandra
• Sam Toueg
• Michael Ben-Or

Seminal works

• fischer1985
• chandra1996
• ben-or1983

Frequently asked questions

¿Si el consenso es imposible, cómo lo logran los sistemas reales?

La imposibilidad se aplica solo a un protocolo determinista que debe terminar siempre en un modelo completamente asíncrono. Los sistemas reales mantienen la seguridad incondicional y dependen de la sincronía eventual o la aleatoriedad para la terminación, por lo que nunca violan el acuerdo y progresan siempre que la red se comporta correctamente.