Tolerancia a fallas benignas y bizantinas

Un punto importante a considerar son los posibles fallos que pueden presentarse en el sistema, estos pueden ocurrir en los procesos. En este caso se pueden presenciar dos:

• Fallas benignas: Es la imposibilidad de garantizar en un sistema asíncrono que una colección de procesos puedan ponerse de acuerdo en un valor compartido. También se puede decir que son los procesos que sufren un fallo por caída, es decir, no muestra fallos en ningun momento de la ejecución. Para tratar estos fallos existen el siguientes algoritmo:
  • Detector de fallo: Permite saber a los demás procesos mediante un servicio si un proceso ha fallado. Frecuentemente, se usa un detector de fallo local que se encuentra en cada proceso, este no es exacto(puede ser fiable o no) pero se encarga de evidenciar si el proceso pudo haber fallado o no. Más detalladamente el algoritmo es: Cada proceso p manda un mensaje al resto de procesos y lo hace cada  T  segundos.  El detector de fallos utiliza una estimación del máximo tiempo de transmisión de una mensaje de D segundos. Si el detector de fallos local en un proceso q no recibe un mensaje de p dentro de los T + D segundos desde el último, entonces informa a q que p quizá tenga un fallo. Sin embargo, si después recibe un mensaje de p, entonces informa a q de que p no tiene un fallo.

• Fallas bizantinas: Los procesos tienen problemas para ponerse de acuerdo en un valor después de que uno o más de dichos procesos haya propuesto cuál debería ser el valor. En el caso de la exclusión mutua, los procesos acuerdan cuáles pueden entrar en la sección crítica. En el caso de una elección, los procesos acuerdan cuál es el proceso elegido. Los algoritmos para solucionar este tipo de acuerdo son:
  • Algoritmo del consenso: Cada proceso pi comienza en el estado no decidido y propone un solo valor vi de un conjunto de posibles valores D(i = 1, 2, …, N). Los procesos se comunican entre sí, intercambiando valores. Entonces, cada proceso fija el valor de una variable de decisión di. Al hacer esto pasa al estado decidido, en el cual ya no puede cambiar el valor de di(i = 1, 2, …, N). Los requisitos para un algoritmo de consenso son:
    • Terminación: cada proceso correcto fija su variable de decisión.
    • Acuerdo: el valor de decisión  de todos los procesos correctos es el mismo: si pi y pj son correctos y están en el estado decidido, entonces di=dj(i, j = 1, 2, …, N)
    • Integridad: si todos los procesos correctos han propuesto el mismo valor, entonces cualquier proceso correcto en el estado decidido ha elegido dicho valor.
  • Algoritmo de los generales bizantinos: Informalmente, tres o más generales han de ponerse de acuerdo en si atacar o retirarse. Uno de ellos, el comandante, cursa la orden. Los otros, los tenientes del comandante, deben decidir si atacar o retirarse. Pero uno o más de los generales puede ser un traidor o fallar. Si el comandante es el traidor, manda atacar a un general y retirarse a otro. Si el traidor es un teniente, informa a uno de sus iguales que el comandante le mandó atacar mientras que a otro le dice que le ordenó retirarse. Este se distingue del de consenso en que un proceso destacado proporciona un valor en el que los otros han de ponerse de acuerdo, en vez de que cada uno proponga un valor. Los requisitos son:
    • Terminación: cada proceso correcto fija su variable de decisión.
    • Acuerdo: el valor de decisión  de todos los procesos correctos es el mismo: si pi y pj son correctos y están en el estado decidido, entonces di=dj(i, j = 1, 2, …, N)
    • Integridad: si el comandante es un proceso correcto, entonces todos los procesos correctos han de decidir el valor propuesto por el comandante.
  • Algoritmo de consistencia interactiva: Es una variante del consenso, en el cual todo proceso propone un solo valor. El objetivo del algoritmo es que los procesos correctos se pongan de acuerdo en un vector de valores, uno para cada procesos. A este se le llamara el vector de decisión. Los requisitos son:
    • Terminación: cada proceso correcto fija su variable de decisión.
    • Acuerdo el vector de decisión de todos los procesos correcto es el mismo.
    • Integridad: si pi es correcto, entonces todos los procesos correctos deciden que vi es la i-ésima componente de su vector.