Défaillances de processeur en informatique distribuée qui ne sont pas en panne ou byzantines

13

Il existe deux principaux types de pannes de processeur dans les modèles informatiques distribués:

(1) Échecs de plantage: un processeur s'arrête et ne redémarre plus. (2) Défaillances byzantines: les processeurs se comportent de manière adversaire, malveillante.

Ma question est:

Quels sont les autres types de pannes de processeur qui ont été étudiés, qui ne se réduisent pas aux pannes ou aux pannes byzantines?

Aussi, une question plus spécifique:

A-t-on étudié un modèle où, avec une certaine probabilité, un processus est activé à l'étape , et sinon désactivé? Donc, chaque processus clignote, pour ainsi dire. $t$

Je m'intéresse surtout à la façon dont ces échecs sont liés au consensus et à d'autres problèmes d'accord distribué.

Je vous remercie.

reference-request dc.distributed-comp Aaron Sterling
la source

@Aaron: J'ai suivi un cours sur les "systèmes distribués" et un autre sur les "systèmes tolérants aux pannes" il y a plusieurs années, mais je ne suis pas vraiment dans ces sujets. Pourtant, je pense que le mot-clé modèle de défaut dynamique peut vous aider.

MS Dousti

1

Je suppose que le modèle d'échec utilisé dans le domaine de l' auto-stabilisation ne se réduit pas aux échecs de crash ou aux échecs byzantins. Une façon de le relier aux échecs byzantins: vous pouvez avoir un comportement byzantin temporaire , mais si et quand un tel comportement s'arrête, un système auto-stabilisant doit atteindre un état correct.

Jukka Suomela

1

Concernant votre question plus spécifique: si un processeur est "allumé" avec la probabilité

, cela me ressemble beaucoup à un modèle asynchrone dans lequel les processeurs sont toujours allumés mais les messages prennent, disons,

tours dans l'espoir d'atteindre leur destination. Pourriez-vous peut-être préciser en quoi cela diffère du modèle que vous aviez en tête?

p

$p$

1 / p

$1/p$

Jukka Suomela

1

@Aaron: Je ne sais pas vraiment à quel point ce type de modèles a été étudié. Mais je suppose que si vous avez un algorithme synchrone déterministe

avec le temps d'exécution

, vous pouvez simplement utiliser le synchroniseur

pour simuler

dans le modèle asynchrone, et je suppose que le temps d'exécution prévu serait quelque chose comme

. (Le synchroniseur

garantit simplement que vos voisins n'ont jamais plus d'un pas d'avance ou de retard sur vous dans la simulation de

)

A

$A$

T

$T$

α

$\alpha$

A

$A$

T / p

$T/p$

α

$\alpha$

A

$A$

Jukka Suomela

2

@Aaron: J'ai pris la théorie de l'informatique distribuée avec Michel Raynal et il a décrit un troisième modèle, où les messages peuvent être déposés aléatoirement. Dans ce modèle, un message peut échouer en silence pour être remis, mais cela ne signifie pas nécessairement que le nœud a échoué. Il s'agit de défaillances de liens plutôt que de défaillances de nœuds "modèle de canal à pertes équitables", vous pouvez en savoir plus ici: Quiescent Uniform Reliable Broadcast as an Introductory Survey to Failure Detector Oracles - Michel Raynal ( ftp.irisa.fr/techreports/2000/ PI-1356.ps.gz )

M. Alaggan

12

Copié des commentaires sur la question selon la demande.

J'ai pris la théorie de l'informatique distribuée avec Michel Raynal et il a décrit un troisième modèle, où les messages peuvent être déposés aléatoirement. Dans ce modèle, un message peut échouer en silence pour être remis, mais cela ne signifie pas nécessairement que le nœud a échoué. Il s'agit de défaillances de liens plutôt que de défaillances de nœuds "modèle de canal à pertes équitables", vous pouvez en savoir plus à ce sujet ici: Diffusion uniforme uniforme au repos comme enquête d'introduction aux oracles du détecteur de défaillance - Michel Raynal (ftp.irisa.fr/techreports/2000/ PI-1356.ps.gz)

M. Alaggan
la source

10

En raison du coût élevé des ressources impliqué par la tolérance aux pannes byzantine, des modèles de défaillance avec des hypothèses de plus en plus fortes ont bien sûr été analysés, en particulier en ce qui concerne les besoins en ressources pour tolérer les défauts de type restreint. ( Azadmanesh et Kieckhafer, 2002 ) fournissent une très belle taxonomie (voir Fig 1.)

Le type de mode de défaillance dans l'intervalle comportement byzantin entièrement asymétrique (nécessitant nœuds) et les défauts de collision bénignes ( nœuds), que votre recherchent et qui a déjà été mentionné par d' autres ci - dessus, est la classe de défauts symétriques (omissifs) $3f+1$ $f+1$ $2f+1$ $f$ défauts . Le document ci-dessus résume également les besoins en ressources pour les scénarios mixtes.

Une autre façon de modéliser les hypothèses du mode de défaillance consiste à s'éloigner du point de vue centré sur le nœud, où la perte de messages est modélisée comme la faute de l'expéditeur, vers le modèle de la faute de liaison, qui n'est qu'une double vue, une fois les incohérences qu'elles peuvent provoquer dans le système est considéré. Ce modèle a été étudié par ( Schmid, Weiss et Rushby, 2002 ), contournant un résultat d'impossibilité de ( Gray, 1978 ) montrant une solution déterministe du problème d'attaque coordonnée sous des failles de liaison.

Martin Schwarz
la source

8

Je ne sais pas si @M. Alaggan parlait de ce type de défauts, mais ils se ressemblent certainement: des défauts transitoires.

Dans le modèle de DVFS , où l'on peut modifier la fréquence et la tension afin de réduire la consommation d'énergie, Zhu et Aydin dans cet article (pdf) ont utilisé un modèle de défaut pour DVFS. Ils considèrent les défaillances transitoires, qui sont des défauts causés par exemple par des erreurs logicielles. Ils invalident uniquement l'exécution de la tâche en cours et le processeur soumis à cette défaillance pourra récupérer et exécuter la tâche suivante qui lui est affectée (le cas échéant).

$\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)}.$

Sorry to post this so long after the original post, but I found this question as I was working on this subject :). When not studying DVFS, these faults still exist, the formulaes are probably still valid (or adaptable). You can find more information on transient failures without DVFS here.

Gopi
la source

4

En ce qui concerne les modèles de défaillance d'omission déjà mentionnés, regardez NeigerToueg , qui considère différents types de ceux-ci.

A-t-on étudié un modèle dans lequel, avec une certaine probabilité, un processus est activé au pas de temps t, et sinon désactivé? Donc, chaque processus clignote, pour ainsi dire.

Cela ressemble à un modèle de récupération après incident. Je ne connais aucun modèle où les processus sont probablement activés / désactivés. Il existe également des variantes où les processus sont byzantins pendant un certain temps, puis récupèrent, où au fil du temps, tous les processus peuvent être byzantins (cependant, la plupart du temps pour la synchronisation d'horloge).

Notez que si en étant désactivé, vous voulez simplement dire qu'un processus ne progresse pas (il ne perd pas son état et que les messages ne sont pas perdus en raison de la désactivation du récepteur), alors ce que vous regardez est appelé asynchrone système. Dans le contexte de la mémoire partagée, votre question pourrait alors être étroitement liée à cet article d' Aspnes .

Martin B.
la source

1

Il pourrait y avoir d'autres types d'échecs. Par exemple, certains des processeurs (par exemple sous les protocoles de diffusion ou de multidiffusion) peuvent devenir surchargés et ne pourraient pas traiter tous les messages entrants. Il en résulte que le processeur apparaît hors ligne pour certains processeurs du système distribué.

Mohammad Al-Turkistany
la source

Défaillances de processeur en informatique distribuée qui ne sont pas en panne ou byzantines

Réponses: