# Consensus and Agreement Protocols

Learn about different models of computation in this lesson.

## 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.

“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 (

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” (

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.

Despite this consideration,

### 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 (

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

Probabilistic algorithms offer many advantages. According to

### 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.

Get hands-on with 1200+ tech skills courses.