Consensus with Crash Failures in Synchronous Systems

We’ll consider the weakest case, namely fail-stop failures. In this case, a faulty process can stop somewhere in the middle of its execution.

We recall the Definition of crash-resilience:

Crash-resilience: A protocol that can tolerate up to $f$ crashed processes is said to be $f$-crash resilient.

Problem definition

We consider a system that contains a collection of $n$ processes, where each process can communicate reliably, whereby $f$ processes may fail only by crashing. Remember that in this case, any process might stop during a message sending step, resulting in only a subset of messages being sent, meaning a process may send a message to only a subset of all processes before crashing. In this case, we assume that the process remains halted and never reaches the decided state.

Conditions for the consensus problem in the fail-stop model

There are $n$ processes, of which at most $f$ might crash, i.e., at least $n-f$ processes are correct, and any process $p_{i}$ starts with an initial input value $v_{i} \in V$. The processes must decide for one of those values, satisfying the following properties (Nancy A. Lynch (1996)Nancy A. Lynch. Distributed Algorithms. The Morgan Kaufmann Series in Data Management Systems. San Francisco, California, 1996. Elsevier Science.):

1. Termination: Every correct (not crashing) process is eventually decided in finite time.
2. Agreement: All correct (not crashing) processes decide for the same value, i.e., no two processes decide differently.
3. Validity: If all processes started by proposing the same initial value $v \in V$, then any (not crashing) process in the decision state has chosen that value $v$.

Note: There are appropriate variations on the definition of validity in literature dependent on the application. An alternative and stronger validity condition for fail-stops are as follows.

A stronger validity condition

Validity: If a process decides a value $v$, then $v$ was proposed by some process, meaning that the decision value must be the input value of a process.