14
$\begingroup$

There are two main types of processor failures in distributed computing models:

(1) Crash failures: a processor stops, and never starts again. (2) Byzantine failures: processors behave adversarially, maliciously.

My question is:

What are some other types of processor failures that have been studied, that do not reduce to crash or Byzantine failures?

Also, a more specific question:

Has a model been studied where, with some probability, a process is on at time step $t$, and otherwise off? So each process is winking on and off, as it were.

I am most interested in how these failures relate to consensus and other distributed agreement problems.

Thank you.

Improve this question
$\endgroup$
8
  • $\begingroup$ @Aaron: I had a course on "distributed systems" and another one on "fault-tolerant systems" several years ago, but I'm not really into those topics. Yet I think the keyword dynamic fault model can help you. $\endgroup$
    – Sadeq Dousti
    Nov 11, 2010 at 14:24
  • 1
    $\begingroup$ I guess the failure model used in the area of self-stabilisation does not reduce to crash failures or Byzantine failures. One way to relate it to Byzantine failures: you can have temporary Byzantine behaviour, but if and when such behaviour stops, a self-stabilising system has to reach a correct state. $\endgroup$
    – Jukka Suomela
    Nov 11, 2010 at 14:29
  • 1
    $\begingroup$ Regarding your more specific question: If a processor if "on" with probability $p$, it sounds to me very much like an asynchronous model in which processors are always on but messages take, say, $1/p$ rounds in expectation to reach their destination. Could you perhaps clarify how this differs from the model that you had in mind? $\endgroup$
    – Jukka Suomela
    Nov 11, 2010 at 14:52
  • 1
    $\begingroup$ @Aaron: I don't really know how much this kind of models have been studied. But I guess if you have any deterministic synchronous algorithm $A$ with running time $T$, you could simply use the $\alpha$-synchroniser to simulate $A$ in the asynchronous model, and I guess the expected running time would be something like $T/p$. (The $\alpha$-synchroniser simply guarantees that your neighbours are never more than 1 time step ahead or behind you in the simulation of $A$.) $\endgroup$
    – Jukka Suomela
    Nov 11, 2010 at 15:40
  • 2
    $\begingroup$ @Aaron: I have taken theory of distributed computing with Michel Raynal and he described a third model, where messages can be dropped randomly. In that model a message can fail silently to be delivered, but that doesn't necessarily mean that the node has failed. It is about link failures rather than node failures "fair lossy channel model", you can read more about it here : Quiescent Uniform Reliable Broadcast as an Introductory Survey to Failure Detector Oracles - Michel Raynal (ftp.irisa.fr/techreports/2000/PI-1356.ps.gz) $\endgroup$
    – Mohammad Alaggan
    Nov 11, 2010 at 15:43

5 Answers 5

Reset to default
13
$\begingroup$

Copied from the comments on the question as per-request.

I have taken theory of distributed computing with Michel Raynal and he described a third model, where messages can be dropped randomly. In that model a message can fail silently to be delivered, but that doesn't necessarily mean that the node has failed. It is about link failures rather than node failures "fair lossy channel model", you can read more about it here : Quiescent Uniform Reliable Broadcast as an Introductory Survey to Failure Detector Oracles - Michel Raynal (ftp.irisa.fr/techreports/2000/PI-1356.ps.gz)

Improve this answer
$\endgroup$
10
$\begingroup$

Due to the high resource cost involved with Byzantine fault-tolerance, failure models with increasingly stronger assumptions have of course been analyzed, especially w.r.t. to resource requirements to tolerate faults of restricted type. (Azadmanesh and Kieckhafer, 2002) provide a very nice taxonomy (see Fig 1.)

The type of failure mode in-between fully asymmetric Byzantine behavior (requiring $3f+1$ nodes) and benign crash faults ($f+1$ nodes), that your are looking for and which has already been mentioned by others above, is the class of symmetric (omissive) faults, where messages are not received by some of the receivers, but no value-faulty (adversary) message is ever received by any node, which requires only $2f+1$ nodes to tolerate $f$ faults. The paper above also summarizes the resource requirements for mixed scenarios.

Another way to model failure mode assumptions is to move away from the node-centric point of view, where message loss modeled as the sender's fault, towards the link-fault model, which is just a dual view, once the inconsistencies they can cause in the system are considered. This model has been investigated by (Schmid, Weiss, and Rushby, 2002), circumventing an impossibility result of (Grey, 1978) showing a deterministic solution of the Coordinated Attack problem under link faults.

Improve this answer
$\endgroup$
0
8
$\begingroup$

I don't know if @M. Alaggan was talking about this kind of faults, but they certainly look alike: transient faults.

In the model of DVFS, where one can modify the frequency and voltage in order to reduce the energy consumption, Zhu and Aydin in this paper(pdf) used a fault model for DVFS. They consider transient failures, which are faults caused by software errors for example. They invalidate only the execution of the current task and the processor subject to that failure will be able to recover and execute the subsequent task assigned to it (if any).

For transient failures, Shatz and Wang introduced a reliability model in this paper (1989) which states that the radiation-induced transient faults follow a Poisson distribution. The parameter $\lambda$ of the Poisson distribution is then:

\begin{equation} \label{fault} \lambda(f)=\lambda_p \; e^{d\frac{f_{max}-f}{f_{max}-f_{min}}}, \end{equation} where $f_{min}\leq f \leq f_{max}$ is the processing speed, the exponent $d\geq0$ is a constant, indicating the sensitivity of fault rates to DVFS, and $\lambda_p$ is the average fault rate corresponding to $f_{max}$ on processor $p$. We see that reducing the speed for energy saving increases the fault rate exponentially. The reliability of a task $T_i$ executed on a processor $p$ at speed $f_i$ is: $$ 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.

Improve this answer
$\endgroup$
0
4
$\begingroup$

Regarding the already mentioned omission failure models have look at NeigerToueg, which considers different kinds of those.

Has a model been studied where, with some probability, a process is on at time step t, and otherwise off? So each process is winking on and off, as it were.

This sounds like a crash-recovery model. I'm not aware of any model where processes are probabilistically on/off. There's also variants where processes are Byzantine for some time and then recover, where over time all processes can be Byzantine (mostly considered for clock-sync, though).

Note that if by being off you just mean that a process is only not making progress (it does not loose its state, and not messages get lost due to the receiver being "off") then what you are looking at is referred to as asynchronous system. In the shared memory context your question could then be closely related to this Aspnes paper.

Improve this answer
$\endgroup$
1
$\begingroup$

There could other types of failures. For example, some of the processors (e.g. under broadcast or multicast protocols) may become overloaded and would not be able to process all incoming messages. This results in making the processor appear offline to some processors in the distributed system.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.