Tolerancia a fallos El método más usado en tolerancia a fallos es el empleo de redundancia La redundancia puede ser: de información: p.ej. añadiendo bits con código de Hamming que permita recuperar errores de tiempo: se realiza una acción, y en caso necesario, se repite en el tiempo. P.ej. la transacción atómica. La redundancia en el tiempo es muy útil en fallos intermitentes y transitorios física: se agregan equipos o procesadores adicionales. Se puede hacer de dos formas: réplica activa respaldo primario
Tolerancia a fallos Tolerancia a fallos mediante réplica activa: todos los procesadores se usan todo el tiempo como servidores, funcionando en paralelo, ocultando los fallos La réplica activa se utiliza en: biología: los mamíferos tenemos dos ojos, oídos, etc. aviación: los 747 tienen 4 motores pero pueden volar con 3 deporte: varios árbitros Se dice que un sistema es tolerante a k fallos si puede superar fallos en k componentes y seguir cumpliendo sus especificaciones
Tolerancia a fallos Si los componentes fallan de manera silenciosa, bastan k+1 de ellos para proporcionar la tolerancia a k fallos Si los componentes tienen fallos bizantinos, continuan su ejecución al fallar y dan respuestas aleatorias o erróneas, por lo que se necesitan al menos 2k+1 componentes para lograr la tolerancia a k fallos
Tolerancia a fallos Tolerancia a fallos mediante respaldo primario: en todo instante es un servidor primario el que realiza todo el trabajo. Si el primario falla, el de respaldo comienza a funcionar, todo ello de forma transparente a los programas de aplicación De este esquema también hay numerosos ejemplos en la vida real: gobierno: ej. vicepresidente aviación: ej. copilotos generadores diesel en los hospitales Ventaja con respecto a la réplica activa: la operación normal es más sencilla, funciona solo un servidor en vez de varios en paralelo Desventaja: trabaja mal en presencia de fallos bizantinos, en los que el primario afirma erróneamente que funciona de manera perfecta
Tolerancia a fallos Acuerdos en sistemas defectuosos: en ss.dd. es muy importante lograr acuerdos sobre algo (elección de coordinador, si completar una transacción o no). ¿cómo llegar a acuerdos cuando hay fallos? Supongamos que tenemos procesadores perfectos pero una línea de comunicación que puede fallar Ese caso podemos estudiarlo teóricamente con el problema de los dos ejércitos
Tolerancia a fallos Problema de los dos ejércitos: El ejército rojo tiene 5000 soldados, acampados en un valle Dos ejércitos azules, cada uno con 3000 efectivos, acampan en las colinas circundantes al valle Si los dos ejércitos azules logran llegar a un acuerdo de ataque simultáneo, derrotarán al ejército rojo Si solo lo intenta uno de los ejércitos azules, saldrá derrotado Supongamos que el comandante del ejército 1 envía un mensaje al comandante del ejército 2. El mensaje dice “Tengo un plan, ataquemos mañana al amanecer” El mensajero logra pasar, y el comandante del ejército 2 le devuelve una nota que dice “Espléndido, ataquemos pues mañana al amanecer” El mensajero regresa a salvo y el comandante 1 prepara entonces a sus tropas
Tolerancia a fallos Pero más tarde el comandante 1 se pone a pensar y se da cuenta de que el comandante 2 no sabe si el mensajeró regresó a salvo, y al dudar podría no atreverse a atacar Así que el comandante 1 vuelve a enviar un mensaje Ocurre lo mismo No importa el nº de reconocimientos enviados, el comandante 1 y el comandante 2 nunca llegarán a un acuerdo => Incluso si los procesadores no fallan (comandantes), el acuerdo entre dos procesos no es posible si existe una comunicación no confiable
Tolerancia a fallos Supongamos ahora que la comunicación es perfecta pero los procesadores no lo son Ese caso podemos estudiarlo teóricamente con el problema de los generales bizantinos El ejército rojo sigue acampando en el valle, pero n generales azules comandan ejércitos en las colinas cercanas La comunicación es perfecta (p.ej línea telefónica), pero m de los n generales son traidores (fallan). Dan información incorrecta o contradictoria Ahora supongamos que cada general conoce el nº de soldados de que dispone. Definiremos el acuerdo como sigue: los generales intercambian la información del nº de soldados que tienen. Al final del algoritmo cada general debe tener un vector de longitud n. Si el general i es leal, entonces el elemento i es su cantidad de efectivos; en caso contrario está indefinido
Tolerancia a fallos Lamport y colaboradores diseñaron un algoritmo recursivo que resuelve este problema bajo ciertas condiciones Veamos cómo funciona para n=4 y m=1 (tres generales leales y uno traidor). Con estos parámetros el algoritmo opera en 4 pasos En el paso uno, cada general envía un mensaje a los demás con la información de sus tropas Los generales leales dicen la verdad, mientras que el traidor puede decir a cada uno de los demás una mentira diferente. Sea el general 3 el traidor. Informan así: general 1: 1 Ksoldados general 2: 2 Ksoldados general 3: x,y,z Ksoldados general 4: 4 Ksoldados
Tolerancia a fallos En el paso 2, los resultados recibidos de los otros se reunen en forma de vectores:
1. (1,2,x,4) 2. (1,2,y,4) 3. (1,2,3,4) 4. (1,2,z,4)
En el paso 3, cada general pasa su vector a los demás En este paso el general 3 vuelve a mentir, ideando 12 nuevos valores a-l:
gral.1 gral.2 gral.4
(1,2,y,4) (1,2,x,4) (1,2,x,4) (a,b,c,d) (e,f,g,h) (1,2,y,4) (1,2,z,4) (1,2,z,4) (i,j,k,l)
Tolerancia a fallos Por último, en el paso 4 cada general examina su i-ésimo elemento de cada uno de los vectores que ha recibido Si cualquier valor tiene una mayoría, este valor se coloca en el vector resultado. Si ningún valor tiene mayoría, el elemento correspondiente del vector resultado se marca como INCOGNITA Vemos que en este caso obtenemos como vector resultado: (1,2,INCOGNITA,4) => El general 3 es un traidor!
Tolerancia a fallos Lamport y colaboradores demostraron que en un sistema con m procesadores que pueden fallar, el acuerdo solo se logra si se dispone de 2m+1 procesadores que funcionen de manera correcta Si por ejemplo hubiésemos tenido n=3 y m=1 (dos generales leales y un traidor) no hubiésemos podido llegar a un acuerdo
| Página siguiente |