10
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Paxos / wikipedia, family of protocols $\endgroup$ – vzn Feb 11 '14 at 5:36
  • 1
    $\begingroup$ Can you be a bit more specific with your comment? $\endgroup$ – danyhow Feb 11 '14 at 7:31
  • 1
    $\begingroup$ 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). $\endgroup$ – Kaveh Feb 21 '16 at 19:02
10
$\begingroup$

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, 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). A similar conversion is not known for randomised algorithms (and I think it is unlikely to exist in the general case).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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