Fallos del procesador en la informática distribuida que no son bloqueados o bizantinos

13

Hay dos tipos principales de fallas del procesador en los modelos de computación distribuida:

(1) Fallos de bloqueo: un procesador se detiene y nunca más se inicia. (2) Fallos bizantinos: los procesadores se comportan de manera adversa, maliciosa.

Mi pregunta es:

¿Cuáles son algunos otros tipos de fallas del procesador que se han estudiado y que no se reducen a fallas de bloqueo o bizantinas?

Además, una pregunta más específica:

¿Se ha estudiado un modelo en el que, con cierta probabilidad, un proceso esté activado en el paso tiempo y de otra manera desactivado? Por lo tanto, cada proceso parpadea, por así decirlo. $t$

Estoy más interesado en cómo estas fallas se relacionan con el consenso y otros problemas de acuerdos distribuidos.

Gracias.

reference-request dc.distributed-comp Aaron Sterling
fuente

@ Aaron: Tuve un curso sobre "sistemas distribuidos" y otro sobre "sistemas tolerantes a fallas" hace varios años, pero no estoy realmente interesado en esos temas. Sin embargo, creo que la palabra clave modelo de falla dinámica puede ayudarlo.

MS Dousti

1

Supongo que el modelo de falla utilizado en el área de autoestabilización no se reduce a fallas de choque o fallas bizantinas. Una forma de relacionarlo con las fallas bizantinas: puede tener un comportamiento bizantino temporal , pero si tal comportamiento se detiene, un sistema autoestabilizador debe alcanzar un estado correcto.

Jukka Suomela

1

Con respecto a su pregunta más específica: si un procesador está "encendido" con probabilidad

, me parece un modelo asíncrono en el que los procesadores siempre están encendidos pero los mensajes toman, por ejemplo,

rondas con la expectativa de llegar a su destino. ¿Podría quizás aclarar cómo difiere esto del modelo que tenía en mente?

p

$p$

1 / p

$1/p$

Jukka Suomela

1

@ Aaron: Realmente no sé cuánto se ha estudiado este tipo de modelos. Pero supongo que si tienes algún algoritmo determinista sincrónico

con tiempo de ejecución

A

$A$

, simplemente podría usar elsincronizador

para simular

en el modelo asincrónico, y supongo que el tiempo de ejecución esperado sería algo así como

. (Elsincronizador

simplemente garantiza que sus vecinos nunca estén más de 1 paso adelante o detrás de usted en la simulación de

).

T

$T$

α

$\alpha$

A

$A$

T / p

$T/p$

α

$\alpha$

A

$A$

Jukka Suomela

2

@ Aaron: Tomé la teoría de la computación distribuida con Michel Raynal y él describió un tercer modelo, donde los mensajes se pueden descartar al azar. En ese modelo, un mensaje puede fallar silenciosamente para ser entregado, pero eso no significa necesariamente que el nodo haya fallado. Se trata de fallas de enlace en lugar de fallas de nodo "modelo de canal con pérdidas equitativas", puede leer más sobre esto aquí: Difusión confiable uniforme de reposo como una encuesta introductoria para detectores de fallas Oráculos - Michel Raynal ( ftp.irisa.fr/techreports/2000/ PI-1356.ps.gz )

M. Alaggan

12

Copiado de los comentarios sobre la pregunta por solicitud.

Tomé la teoría de la computación distribuida con Michel Raynal y él describió un tercer modelo, donde los mensajes se pueden descartar aleatoriamente. En ese modelo, un mensaje puede fallar silenciosamente para ser entregado, pero eso no significa necesariamente que el nodo haya fallado. Se trata de fallas de enlace en lugar de fallas de nodo "modelo de canal con pérdidas equitativas", puede leer más sobre esto aquí: Difusión confiable uniforme de reposo como una encuesta introductoria para el detector de fallas Oráculos - Michel Raynal (ftp.irisa.fr/techreports/2000/ PI-1356.ps.gz)

M. Alaggan
fuente

10

Debido al alto costo de los recursos involucrados con la tolerancia a fallas bizantina, por supuesto, se han analizado modelos de fallas con supuestos cada vez más fuertes, especialmente en relación con los requisitos de recursos para tolerar fallas de tipo restringido. ( Azadmanesh y Kieckhafer, 2002 ) proporcionan una taxonomía muy agradable (ver Fig. 1.)

El tipo de modo de falla en el comportamiento bizantino completamente asimétrico (que requiere $3f+1$ $f+1$ $2f+1$ $f$

Otra forma de modelar las suposiciones del modo de falla es alejarse del punto de vista centrado en los nodos, donde la pérdida de mensajes modelada como la falla del remitente, hacia el modelo de falla de enlace, que es solo una vista dual, una vez que las inconsistencias pueden causar Se consideran el sistema. Este modelo ha sido investigado por ( Schmid, Weiss y Rushby, 2002 ), eludiendo un resultado de imposibilidad de ( Gray, 1978 ) que muestra una solución determinista del problema de ataque coordinado bajo fallas de enlace.

Martin Schwarz
fuente

8

No sé si @M. Alaggan estaba hablando de este tipo de fallas, pero ciertamente se parecen: fallas transitorias.

En el modelo de DVFS , donde se puede modificar la frecuencia y el voltaje para reducir el consumo de energía, Zhu y Aydin en este documento (pdf) utilizaron un modelo de falla para DVFS. Consideran fallas transitorias, que son fallas causadas por errores de software, por ejemplo. Invalidan solo la ejecución de la tarea actual y el procesador sujeto a ese fallo podrá recuperar y ejecutar la tarea posterior que se le haya asignado (si corresponde).

$\lambda$

λ (f) = λ_{p} e^{d \frac{f_{m a x} - f}{f_{m a x} - f_{m i n}}},

$\begin{equation} \label{fault} \lambda(f)=\lambda_p \; e^{d\frac{f_{max}-f}{f_{max}-f_{min}}}, \end{equation}$

f_{m i n} \leq f \leq f_{m a x}

$f_{min}\leq f \leq f_{max}$

d \geq 0

$d\geq0$

λ_{p}

$\lambda_p$

f_{m a x}

$f_{max}$

p

$p$

T_{i}

$T_i$

p

$p$

f_{i}

$f_i$

R_{i} (f_{i}) = e^{- λ (f_{i}) \times E x e c u t i o n T i m e (T_{i}, f_{i})} .

$R_i(f_i)=e^{-\lambda(f_i)\times Execution~Time(T_i,f_i)}.$

Lamento publicar esto mucho después de la publicación original, pero encontré esta pregunta porque estaba trabajando en este tema :). Cuando no se estudia DVFS, estas fallas aún existen, las fórmulas probablemente aún sean válidas (o adaptables). Puede encontrar más información sobre fallas transitorias sin DVFS aquí .

Gopi
fuente

4

Con respecto a los modelos de falla por omisión ya mencionados, observe NeigerToueg , que considera diferentes tipos de ellos.

¿Se ha estudiado un modelo en el que, con cierta probabilidad, un proceso está activado en el paso t de tiempo y de otra manera desactivado? Por lo tanto, cada proceso parpadea, por así decirlo.

Esto suena como un modelo de recuperación de fallos. No conozco ningún modelo en el que los procesos estén probablemente activados / desactivados. También hay variantes en las que los procesos son bizantinos durante algún tiempo y luego se recuperan, donde con el tiempo todos los procesos pueden ser bizantinos (aunque en su mayoría se consideran para sincronización de reloj).

Tenga en cuenta que si al estar apagado solo quiere decir que un proceso no está progresando (no pierde su estado y no se pierden mensajes debido a que el receptor está "apagado"), entonces lo que está viendo se denomina asíncrono. sistema. En el contexto de memoria compartida, su pregunta podría estar estrechamente relacionada con este documento de Aspnes .

Martin B.
fuente

1

Podría haber otros tipos de fallas. Por ejemplo, algunos de los procesadores (por ejemplo, bajo protocolos de difusión o multidifusión) pueden sobrecargarse y no podrían procesar todos los mensajes entrantes. Esto hace que el procesador aparezca fuera de línea para algunos procesadores en el sistema distribuido.

Mohammad Al-Turkistany
fuente

Fallos del procesador en la informática distribuida que no son bloqueados o bizantinos

Respuestas: