What is the advantage of designing deterministic distributed algorithms? 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.
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).