<p>I will answer this from the perspective of <strong>distributed graph algorithms</strong> (distributed algorithms that solve a graph problem related to the structure of the communication network).</p>

<p>Here are some non-obvious reasons for designing deterministic distributed algorithms in this setting:</p>

<ul>
<li><p><strong>Subroutines in randomised algorithms</strong>. On p. 12–13 of <a href="http://adga2013.hiit.fi/elkin.pdf">these slides</a>, Elkin outlines an algorithm design technique in which you can use a fast <em>deterministic</em> distributed algorithms as a subroutine in order to construct a fast <em>randomised</em> distributed algorithm. Interestingly, it is <em>not</em> possible to use a typical randomised algorithm as a subroutine in the same context (the error probability would be too high).</p></li>
<li><p><strong>Fault tolerance</strong>. There is a mechanical translation that allows you to convert a fast <em>deterministic</em> distributed algorithm into a fast <em>self-stabilising</em> distributed algorithm (see e.g. Section 2.4 of <a href="http://users.ics.aalto.fi/suomela/doc/local-self-stab.pdf">this survey</a>). A similar conversion is not known for randomised algorithms (and I think it is unlikely to exist in the general case).</p></li>
</ul>

CC BY-SA 3.0
2014-02-08T21:35:44.753Z
2014-02-08T21:35:44.753Z
Jukka Suomela
<p>Distributed algorithms that are resilient to failures can either be deterministic or probabilistic. Take for example the consensus problem.</p>

<ul>
<li><p>Paxos is deterministic in the sense that given the assumption it makes, it <em>always</em> works.</p></li>
<li><p>In constrast, randomized consensus works with a given probability.</p></li>
</ul>

<p>What is the advantage of designing and using a deterministic algorithm?</p>

<p>The assumptions upon which deterministic algorithms rely have also a probability of holding in the reality (what is called their <em>assumption coverage</em>). Hence, there is always a probability that a deterministic algorithm does not work in the reality.</p>

CC BY-SA 3.0
2014-02-11T05:36:13.393Z
[Paxos](http://en.wikipedia.org/wiki/Paxos_(computer_science)) /  wikipedia, family of protocols
vzn
CC BY-SA 3.0
2014-02-11T07:31:08.130Z
Can you be a bit more specific with your comment?
danyhow
CC BY-SA 3.0
2016-02-21T19:02:51.343Z
It is good to note that randomization is used typically for liveness properties not safety properties. Safety properties always hold, however there is a chance that the algorithm does not terminate (which typically decreases as time passes).
Kaveh
<randomized-algorithms><dc.distributed-comp><fault-tolerance>
What is the advantage of designing deterministic distributed algorithms?
danyhow
# What is the advantage of designing deterministic distributed algorithms?

(Asked by: username_0 on 2014-02-08)

Distributed algorithms that are resilient to failures can either be deterministic or probabilistic. Take for example the consensus problem.

* Paxos is deterministic in the sense that given the assumption it makes, it *always* works.
* In constrast, randomized consensus works with a given probability.

What is the advantage of designing and using a deterministic algorithm?

The assumptions upon which deterministic algorithms rely have also a probability of holding in the reality (what is called their *assumption coverage*). Hence, there is always a probability that a deterministic algorithm does not work in the reality.

**Tags:** randomized-algorithms, dc.distributed-comp, fault-tolerance
> **Comments:**
> **username_1**: [Paxos](http://en.wikipedia.org/wiki/Paxos_(computer_science)) /  wikipedia, family of protocols  
> **username_0**: Can you be a bit more specific with your comment?  
> **username_2**: It is good to note that randomization is used typically for liveness properties not safety properties. Safety properties always hold, however there is a chance that the algorithm does not terminate (which typically decreases as time passes).  

---

## 1 answers

### Answer by username_3 on 2014-02-08. Score: 10

I will answer this from the perspective of **distributed graph algorithms** (distributed algorithms that solve a graph problem related to the structure of the communication network).

Here are some non-obvious reasons for designing deterministic distributed algorithms in this setting:

* **Subroutines in randomised algorithms**. On p. 12–13 of [these slides](http://adga2013.hiit.fi/elkin.pdf), Elkin outlines an algorithm design technique in which you can use a fast *deterministic* distributed algorithms as a subroutine in order to construct a fast *randomised* distributed algorithm. Interestingly, it is *not* possible to use a typical randomised algorithm as a subroutine in the same context (the error probability would be too high).
* **Fault tolerance**. There is a mechanical translation that allows you to convert a fast *deterministic* distributed algorithm into a fast *self-stabilising* distributed algorithm (see e.g. Section 2.4 of [this survey](http://users.ics.aalto.fi/suomela/doc/local-self-stab.pdf)). A similar conversion is not known for randomised algorithms (and I think it is unlikely to exist in the general case).


---

