Agreement in a Failure-Free System

Reaching consensus in a failure-free system

It’s obvious that reaching an agreement or consensus in a failure-free system is possible in a straightforward manner by applying a flooding algorithm (Nancy A. Lynch. (1996)Nancy A. Lynch. Distributed Algorithms. The Morgan Kaufmann Series in Data Management Systems. San Francisco, California, 1996. Elsevier Science.), broadcasting each value of any process to all other ones, and using the decision rule in the end. Algorithm 5 (given below) shows a simple deterministic protocol for a synchronous system using the minimum function. We can assume that communication takes place in synchronous communication rounds.

Algorithm 5

A simple deterministic consensus protocol for failure-free systems does the following:

1. Broadcasts its own value to all other processes.
2. Receives values from all other processes.
3. Decides on the minimum value.

In this case, the correctness conditions of termination and validity ( of this definition :Correctness_conditions_for_the_agreement hold. For the agreement condition, let’s consider the example below:

Example: reaching consensus in a failure-free system with five processes

Assume there’s a synchronous system with $5$ processes $p_{i}, i \in\{0,1,2,3,4\}$, where each process has its initial value $v_{i}=i \in V$ as shown in Figure 1

(a) and $V$ is the set of possible initial values. Let’s further assume that the communication takes place in synchronous communication rounds.

By applying Algorithm 5, each process $p_{i}$ broadcasts its own value to all other processes in one round. After broadcasting, each process calculates its decision value $d_{i}=\min \left(v_{0}, \ldots, v_{4}\right)$. Since every process receives the minimum value $v_{0}=0$, every process decides with $d_{i}=v_{0}=0$ (see Figure 1 (b)), hence a consensus is reached.

Figure 1