Consensus

Pre-requisites

In a group of failure-tolerant processes, each process that is not failing executes the same commands and in the same order as any other process that is also not failing.

Reformulation

Non-failing members of the group need to reach a consensus about which command to execute next.

Flooding

System model

Consider a group of processes P = {P1, ..., Pn}

Failure semantics Fail-stop, meaning, with detection of reliable failures.

A client contacts Pi asking to execute a command.

Each Pi holds a list of proposed commands.

Algorithm (round based)

In round r, Pi multicasts its set of Cmdr_i to everybody else.

At the end of r, each Pi merges every received command in a new Cmdr+1_i.

The next Cmd_i command is selected by a globally shared deterministic function.

Example

P2 receives all the proposed commands by all the other processes -> makes a decision.

P3 can detect that P1 crashed, but cannot know if P2 has received anything, i.e, P3 has no way of knowing if it has the same information as P2 -> cannot make a decision (same happens with P4).