Consensus and Agreement Protocols

Types of algorithms

As there are different models of computation one can choose from, there are also different kinds of algorithms. There are mainly three different types of consensus protocols/algorithms, namely deterministic, nondeterministic, and probabilistic.

Delfs et al. (2007)Hans Delfs and Helmut Knebl. Introduction to Cryptography: Principles and Applications. Information Security and Cryptography. Berlin, Heidelberg, 2007. SpringerVerlag. describe a deterministic algorithm as follows:

“The output $y$ of a deterministic algorithm $A$ is completely determined by its input $x.$ In a deterministic way, $y$ is computed from $x$ by a sequence of steps decided in advance by the programmer. A behaves like a mathematical mapping: applying $A$ to the same input $x$ several times always yields the same output $y$. Therefore, we may use the mathematical notation of a mapping, $A: X \longrightarrow Y$, for a deterministic algorithm $A$, with inputs from $X$ and outputs in $Y$.”

This means the output of a deterministic algorithm is uniquely defined as a function of its input.

Deterministic algorithms

A deterministic algorithm is an algorithm where “the outcome of every operation is uniquely defined,” thus deterministic algorithms always return the same result any time they are called with a specific set of input variables (Adnan Yazici (2017)Adnan Yazici. The theory of NP-completeness. http://user.ceng.metu.edu.tr/ el25043/algonotes/algo8.pdf. Accessed: 2017-11-23.).

Opposite to a deterministic algorithm, a non-deterministic algorithm is an algorithm whose outcome is not unique for every operation, meaning that even for the same input, the output can exhibit different behaviors on different runs.

Non-deterministic algorithms

A non-deterministic algorithm is an algorithm where “the outcome of each operation is not uniquely defined, but restricted to a specific set of possibilities” (Adnan Yazici (2017)Adnan Yazici. The theory of NP-completeness. http://user.ceng.metu.edu.tr/ el25043/algonotes/algo8.pdf. Accessed: 2017-11-23.)

This means that a non-deterministic algorithm can exhibit different behaviors even for the same input. However, there’s often a common confusion about non-deterministic and probabilistic algorithms. Floyd (1967)Robert W. Floyd. Nondeterministic algorithms. J. ACM, 14(4) : 636 - 4 , October 1967. rectifies the terms as follows: “Because the word ‘non-deterministic’ has a double meaning, it is perhaps desirable to make clear that non-deterministic algorithms are not probabilistic, random or Monte Carlo algorithms. Rather, they are convenient representations of systematic search procedures.”

Despite this consideration, Hromkovič (2013)Juraj Hromkovič. Algorithmics for Hard Problems: Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics. Texts in Theoretical Computer Science. An EATCS Series. Berlin Heidelberg, 2013. Springer. argues that a “randomized algorithm can be viewed as a nondeterministic algorithm that has a probability distribution for every nondeterministic choice.” This means that probabilistic algorithms are based on non-deterministic protocols, whilst each non-deterministic step can be viewed as a random decision.

Probabilistic algorithm

A probabilistic algorithm $A$ is an algorithm whose behavior is partly controlled by random events. The computation of the output $y$ on input $x$ depends on the outcome of a finite number of random experiments. In particular, applying $A$ to the same input $x$ twice may yield two different outputs (Hans Delfs et al. (2007)Hans Delfs and Helmut Knebl. Introduction to Cryptography: Principles and Applications. Information Security and Cryptography. Berlin, Heidelberg, 2007. SpringerVerlag.).

Note: Probabilistic algorithms are often referred to as randomized algorithms.

Probabilistic algorithms offer many advantages. According to Hromkovič (2013)Juraj Hromkovič. Algorithmics for Hard Problems: Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics. Texts in Theoretical Computer Science. An EATCS Series. Berlin Heidelberg, 2013. Springer., probabilistic algorithms “may be more efficient (faster, more space-efficient, etc.) and simpler to handle (implement) than their best-known deterministic counterparts.” Tempo and Ishii (2008)Hideaki Ishii and Roberto Tempo. Las Vegas randomized algorithms in distributed consensus problems. At the 2008 American Control Conference. IEEE, Jun 2008. divide randomized algorithms into two classes, namely Las Vegas and Monte Carlo randomized protocols.

Las Vegas algorithms

Las Vegas randomized algorithms are randomized algorithms that always give the correct answer. The only difference from one run to another is the running time.

Monte Carlo algorithms

A Monte Carlo randomized algorithm is a randomized algorithm that may produce an incorrect result, but the probability of such an incorrect result is bounded.

In the following sections, we’ll see that the choice of the type of consensus protocol is of vital importance, since not every type of protocol can solve every consensus problem in specific environments.