<p>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. (<a href="http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=888039&amp;tag=1">Azadmanesh and Kieckhafer, 2002</a>) provide a very nice taxonomy (see Fig 1.)</p>

<p>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 <strong>symmetric (omissive) faults</strong>, 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.</p>

<p>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 (<a href="http://www.computer.org/portal/web/csdl/doi/10.1109/ICDCS.2002.1022311">Schmid, Weiss, and Rushby, 2002</a>), circumventing an impossibility result of (<a href="http://www.springerlink.com/content/p24u11v1432k4t27/">Grey, 1978</a>) showing a deterministic solution of the Coordinated Attack problem under link faults.</p>

CC BY-SA 2.5
2010-11-12T14:08:14.007Z
2010-11-12T15:46:32.587Z
2010-11-12T15:46:32.587Z
Martin Schwarz
<p>I don't know if @M. Alaggan was talking about this kind of faults, but they certainly look alike: transient faults.</p>

<p>In the model of <a href="http://en.wikipedia.org/wiki/Dynamic_frequency_scaling">DVFS</a>, where one can modify the frequency and voltage in order to reduce the energy consumption, Zhu and Aydin in this <a href="http://www.google.fr/url?sa=t&amp;source=web&amp;cd=3&amp;ved=0CEMQFjAC&amp;url=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.130.7067&amp;ei=Bg6HTqKwAe6X0QXW7KT-Dw&amp;usg=AFQjCNG9vUUFAk-lZXsPKmmm2ajAS9mMpA&amp;sig2=hP0XSEzqbYEdv9GHitufkA">paper</a>(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). </p>

<p>For transient failures, Shatz and Wang introduced a reliability model in this <a href="http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=24570">paper</a> (1989) which states that the radiation-induced transient faults follow a Poisson
distribution.  The parameter $\lambda$ of the Poisson distribution is
then:</p>

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

<p>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 <a href="http://graal.ens-lyon.fr/~yrobert/onlinepapers/RRLIP2010-01.pdf">here</a>.</p>

CC BY-SA 3.0
2011-10-01T13:16:28.030Z
2011-10-01T13:16:28.030Z
Gopi
<p>Regarding the already mentioned omission failure models have look at <a href="http://citeseerx.ist.psu.edu/viewdoc/summary;jsessionid=3BDAA5BE3F21C71336605B7F4A943165?doi=10.1.1.119.685&amp;rank=1" rel="nofollow">NeigerToueg</a>, which considers different kinds of those.</p>

<blockquote>
  <p>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.</p>
</blockquote>

<p>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).</p>

<p>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 <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.22.7460" rel="nofollow">Aspnes</a> paper.</p>

CC BY-SA 2.5
2011-03-31T22:53:03.420Z
2011-03-31T22:53:03.420Z
Martin B.
<p>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.</p>

CC BY-SA 2.5
2010-11-11T16:55:17.430Z
2010-11-11T17:11:53.947Z
2010-11-11T17:11:53.947Z
Mohammad Al-Turkistany
<p>Copied from the comments on the question as per-request.</p>

<p>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) </p>

CC BY-SA 2.5
2010-11-11T16:40:52.253Z
2010-11-11T16:40:52.253Z
Mohammad Alaggan
<p>There are two main types of processor failures in distributed computing models:</p>

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

<p>My question is:</p>

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

<p>Also, a more specific question:</p>

<blockquote>
  <p>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.</p>
</blockquote>

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

<p>Thank you.</p>

CC BY-SA 2.5
2010-11-11T14:24:40.287Z
@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.
Sadeq Dousti
CC BY-SA 2.5
2010-11-11T14:29:58.827Z
I guess the failure model used in the area of [self-stabilisation](https://secure.wikimedia.org/wikipedia/en/wiki/Self-stabilization) 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.
Jukka Suomela
CC BY-SA 2.5
2010-11-11T14:52:54.553Z
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?
Jukka Suomela
CC BY-SA 2.5
2010-11-11T15:30:13.180Z
@Jukka: It sounds as though they might be the same thing. I'm not familiar with the mixing of deterministic asynchrony and probabilistic models, though I am sure it has been done. Is a fair amount known about the model you described?
Aaron Sterling
CC BY-SA 2.5
2010-11-11T15:40:58.603Z
@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$.)
Jukka Suomela
CC BY-SA 2.5
2010-11-11T15:43:44.543Z
@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://ftp.irisa.fr/techreports/2000/PI-1356.ps.gz)
Mohammad Alaggan
CC BY-SA 2.5
2010-11-11T16:30:02.307Z
@M. Alaggan: Your answer seems very helpful.  I moved from your suggestion to "probabilistic lossy channel systems," which seems very close to what I want.  Please consider posting your comment as an answer so I can give you some rep.
Aaron Sterling
CC BY-SA 2.5
2010-11-11T17:44:58.087Z
Also... @Jukka, thanks to you too!  I want to pump up the rep of the new guy, though. :-)
Aaron Sterling
<reference-request><dc.distributed-comp>
Processor failures in distributed computing that are not crash or Byzantine
Aaron Sterling
# Processor failures in distributed computing that are not crash or Byzantine

(Asked by: username_0 on 2010-11-11)

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.

**Tags:** reference-request, dc.distributed-comp
> **Comments:**
> **username_1**: @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.  
> **username_2**: I guess the failure model used in the area of [self-stabilisation](https://secure.wikimedia.org/wikipedia/en/wiki/Self-stabilization) 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.  
> **username_2**: 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?  
> **username_0**: @Jukka: It sounds as though they might be the same thing. I'm not familiar with the mixing of deterministic asynchrony and probabilistic models, though I am sure it has been done. Is a fair amount known about the model you described?  
> **username_2**: @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$.)  
> **username_3**: @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://ftp.irisa.fr/techreports/2000/PI-1356.ps.gz)  
> **username_0**: @M. Alaggan: Your answer seems very helpful.  I moved from your suggestion to "probabilistic lossy channel systems," which seems very close to what I want.  Please consider posting your comment as an answer so I can give you some rep.  
> **username_0**: Also... @Jukka, thanks to you too!  I want to pump up the rep of the new guy, though. :-)  

---

## 5 answers

### Answer by username_3 on 2010-11-11. Score: 13 | Accepted answer

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)


---

### Answer by username_4 on 2010-11-12. Score: 10

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](http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=888039&tag=1)) 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](http://www.computer.org/portal/web/csdl/doi/10.1109/ICDCS.2002.1022311)), circumventing an impossibility result of ([Grey, 1978](http://www.springerlink.com/content/p24u11v1432k4t27/)) showing a deterministic solution of the Coordinated Attack problem under link faults.


---

### Answer by username_5 on 2011-10-01. Score: 8

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](http://en.wikipedia.org/wiki/Dynamic_frequency_scaling), where one can modify the frequency and voltage in order to reduce the energy consumption, Zhu and Aydin in this [paper](http://www.google.fr/url?sa=t&source=web&cd=3&ved=0CEMQFjAC&url=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.130.7067&ei=Bg6HTqKwAe6X0QXW7KT-Dw&usg=AFQjCNG9vUUFAk-lZXsPKmmm2ajAS9mMpA&sig2=hP0XSEzqbYEdv9GHitufkA)(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](http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=24570) (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](http://graal.ens-lyon.fr/~yrobert/onlinepapers/RRLIP2010-01.pdf).


---

### Answer by username_6 on 2011-03-31. Score: 4

Regarding the already mentioned omission failure models have look at [NeigerToueg](http://citeseerx.ist.psu.edu/viewdoc/summary;jsessionid=3BDAA5BE3F21C71336605B7F4A943165?doi=10.1.1.119.685&rank=1), 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](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.22.7460) paper.


---

### Answer by username_7 on 2010-11-11. Score: 1

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.


---

