SKR 5302: Advanced Distributed Computing

6.6. Consensus and related problems

The problem is for processes to agree on a value after one or more of the processes has proposed what that value should be. 
System model

• A collection of processes pi (i = 1, 2, …, N) communicating by message passing. 
• Important requirement: consensus to be reached even in the presence of faults. 
• Assume that communication is reliable but the processes may fail. 

Definition of the consensus problem

• To reach consensus, every process pi begins in the undecided state and proposes a single value v_i, drawn from a set D (i = 1, 2, …, N). 
• The processes communicate with one another, exchanging values. 
• Each process then sets the value of a decision variable di.
• In doing so, it enters the decided state, in which is may no longer change di (i = 1, 2, …, N). 
  
  

  Figure 6.16: Consensus for three processes
  
  
  

The requirements of a consensus algorithm:

• Termination: Eventually each correct process sets its decision variable. 
• Agreement: The decision value of all correct processes is the same

If p_i and p_j are correct and have entered the decided state, then d_i = d_j (i,j = 1, 2, …, N)

• Integrity: If the correct processes all proposed the same value, then any correct process in the decided state has chosen that value. 

Consider a system in which processes cannot fail. 

• Processes are collect into a group and have each process reliably multicast its proposed value to the members of the group. 
• Each process waits until it has collected all N values (including its own). 
• It then evaluates the function majority(v1, v2, …, vN), which returns the value that occurs the most often among its arguments. 

If processes can crash, this introduces the complication of detecting failures.

• It is not immediately clear that a run of the consensus algorithm can terminate.

If processes can fail in arbitrary (Byzantine) ways, then faulty processes can in principle communicate random values to the others. 

• Correct processes must compare what they have received with what other processes claim to have received. 
• The Byzantine generals problem

Differs from consensus in that a distinguished process supplies a value that the others are to agree upon, instead of each of them proposing a value. 

Requirements:

• Termination: Eventually each correct process sets its decision variable.
• Agreement: The decision value of all correct processes is the same

If p_i and p_j are correct and have entered the decided state, then d_i = d_j (i,j = 1, 2, …, N)

Integrity: If the commander is correct, then all correct processes decide on the value that the commander proposed. 

Interactive consistency

• Every process proposes a single value.
• The goal of the algorithm is for the correct processes to agree on a vector of values, one for each process. 
  • Example: the goal could be for each of a set of processes to obtain the same information about their respective states. 
• The requirements:
  • Termination: Eventually each correct process sets its decision variable.
  • Agreement: The decision vector of all correct processes is the same.
  • Integrity: If p_i is correct, then all correct processes decide on v_i as the i^th component of their vector.