El algoritmo de consenso Chandra-Toueg , publicado por Tushar Deepak Chandra y Sam Toueg en 1996, es un algoritmo para resolver el consenso en una red de procesos poco confiables equipados con un detector de fallas eventualmente potente . El detector de fallas es una versión abstracta de tiempos de espera ; señala a cada proceso cuando otros procesos pueden haber fallado. Un detector de fallas eventualmente fuerte es aquel que nunca identifica algún proceso específico no defectuoso como fallado después de un período inicial de confusión y, al mismo tiempo, eventualmente identifica todosProcesos defectuosos como fallados (donde un proceso defectuoso es un proceso que eventualmente falla o se bloquea y un proceso que no falla nunca falla). El algoritmo de consenso de Chandra-Toueg asume que el número de procesos defectuosos, denotado por f , es menor que n / 2 (es decir, la minoría), es decir, asume f < n / 2, donde n es el número total de procesos.
El algoritmo
El algoritmo procede en rondas y utiliza un coordinador rotatorio: en cada ronda r , se elige como coordinador el proceso cuya identidad está dada por r mod n . Cada proceso realiza un seguimiento de su valor de decisión preferido actual (inicialmente igual a la entrada del proceso) y la última ronda en la que cambió su valor de decisión (la marca de tiempo del valor ). Las acciones que se realizan en cada ronda son:
- Todos los procesos envían (r, preferencia, marca de tiempo) al coordinador.
- El coordinador espera recibir mensajes de al menos la mitad de los procesos (incluido él mismo).
- Luego elige como su preferencia un valor con la marca de tiempo más reciente entre los enviados.
- El coordinador envía (r, preferencia) a todos los procesos.
- Cada proceso espera (1) para recibir (r, preferencia) del coordinador, o (2) para que su detector de fallas identifique al coordinador como fallado.
- En el primer caso, establece su propia preferencia a la preferencia del coordinador y responde con ack (r).
- En el segundo caso, envía nack (r) al coordinador.
- El coordinador espera recibir ack (r) o nack (r) de la mayoría de los procesos.
- Si recibe un ack (r) de una mayoría, envía decide (preferencia) a todos los procesos.
- Cualquier proceso que recibe decide (preferencia) por primera vez, los relés decide (preferencia) para todos los procesos, luego decide la preferencia y termina.
Tenga en cuenta que este algoritmo se utiliza para decidir solo sobre un valor.
Exactitud
Definición del problema
Un algoritmo que "resuelve" el problema de consenso debe asegurar las siguientes propiedades:
- terminación: todos los procesos deciden sobre un valor;
- acuerdo: todos los procesos deciden sobre el mismo valor; y
- validez: todos los procesos deciden sobre un valor que era el valor de entrada de algún proceso;
Supuestos
Antes de argumentar que el algoritmo de consenso de Chandra-Toueg satisface las tres propiedades anteriores, recuerde que este algoritmo requiere n = 2 * f + 1 procesos, donde como máximo f son defectuosos.
Además, tenga en cuenta que este algoritmo asume la existencia de un detector de fallas eventualmente fuerte (que son accesibles y pueden usarse para detectar el bloqueo de un nodo). Un detector de fallas eventualmente fuerte es aquel que nunca identifica algún proceso específico no defectuoso (o correcto) como fallado, después de un período inicial de confusión y, al mismo tiempo, eventualmente identifica todos los procesos defectuosos como fallados.
Prueba de corrección
La terminación se mantiene porque eventualmente el detector de fallas deja de sospechar algún proceso no defectuoso py eventualmente p se convierte en el coordinador. Si el algoritmo no ha terminado antes de que esto ocurra en alguna ronda r, entonces cada proceso no defectuoso en la ronda r espera recibir la preferencia de p y responde con ack (r). Esto permite que p recopile suficientes acuses de recibo para enviar decide (preferencia), lo que hace que todos los procesos terminen. Alternativamente, puede ser que algunos envíos de coordinadores defectuosos se decidan solo a unos pocos procesos; pero si alguno de estos procesos no tiene fallas, transmiten la decisión a todos los procesos restantes, provocando que decidan y terminen.
La validez se deriva del hecho de que cada preferencia comienza como la entrada de algún proceso; no hay nada en el protocolo que genere nuevas preferencias.
El acuerdo es potencialmente el más difícil de lograr. Es posible que un coordinador, en una ronda r, envíe un mensaje de decisión desde algún valor v que se propague solo a unos pocos procesos antes de que otro coordinador, en una ronda posterior r ', envíe un mensaje de decisión para algún otro valor v '. Para demostrar que esto no ocurre, observe que antes de que el primer coordinador pueda enviar decidir (v), debe haber recibido un ack (r) de la mayoría de los procesos; pero, luego, cuando cualquier coordinador posterior encuesta la mayoría de los procesos, la mayoría posterior se superpondrá al anterior y v será el valor más reciente. Por lo tanto, dos coordinadores que envían un mensaje de decisión envían el mismo valor.