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 ff crashed processes is said to be ff-crash resilient.

Problem definition

We consider a system that contains a collection of nn processes, where each process can communicate reliably, whereby ff 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 nn processes, of which at most ff might crash, i.e., at least nfn-f processes are correct, and any process pip_{i} starts with an initial input value viVv_{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 vVv \in V, then any (not crashing) process in the decision state has chosen that value vv.

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 vv, then vv was proposed by some process, meaning that the decision value must be the input value of a process.

Get hands-on with 1200+ tech skills courses.