Consensus in Distributed System

Consensus is a classic problem in distributed networks, where nodes/processes need to agree on the next state of the system, given identical input states.

Consensus

It’s a classic problem in distributed networks, where nodes/processes need to agree on the next state of the system, given identical input states. Typical applications of consensus include:

  • Agreeing on whether to commit or abort a transaction in a distributed database
  • Leader election
  • UAV (unmanned aerial vehicle) control
  • Clock synchronization
  • Pagerank
  • Load balancing
  • Blockchain

Problem description

The consensus problem deals with agreement among nodes/processors in a distributed network, with fault tolerance against failures in either the processors or the communication network. Consensus is a classic problem that always shows up in distributed systems with many participants. The natural approach is that all processors must agree on a value accepted by the majority, at least more than half (50%+1). However, this approach always runs into trouble when faulty processors can keep blocking consensus, or prevent it from ever being reached. So the consensus problem always puts a limit on the maximum number of faulty processors.

There are 3 conditions always set in the consensus problem:

Termination (the condition for ending the consensus process) correct processors eventually come up with a decision value.

Integrity (the integrity / consistency of the consensus process) if all correct processors propose value v, then any correct processor must agree that v is the decision.

Agreement (the invariant of the consensus process) every correct processor must agree on the same single value.

The integrity condition has many variants depending on the algorithm and the purpose of the consensus. For example, a weaker integrity is that the decision value can be chosen by a group of correct processors instead of all of them.

A bit of history

The consensus problem was first mentioned in 1978 by Robert Shostak with his publication on the “Interactive consistency problem”, while he was working on the SIFT (Software Implemented Fault Tolerance) project at the Computer Science lab at SRI International (funded by NASA). At the time, Shostak proved that at least 3n+1 processors are needed in the network for consensus to work with n=1 faulty processor. Later, Leslie Lamport restated the problem more generally and proved it for the case n>1.

Consensus in synchronous networks

In a synchronous network, consensus runs in rounds, and one round has to finish before the next begins.

Consensus shows up in many distributed applications. For example: processes need to agree on whether to commit or abort a transaction in a distributed database. The typical, fundamental consensus problem is called the “coordinated attack problem” - which puts us in a situation where messages can be lost.

Describing the coordinated attack problem:

Several generals (processes) decide to plan a coordinated attack on a piece of land. They understand the attack can only succeed if all of them take part. The problem is that they are stationed at different locations, and their only means of communication is word of mouth. They need to agree on the time to attack together. Generals who are near each other can communicate through messengers.

If all messengers are reliable, all generals can send messages to each other. So after a few rounds of messaging, they can agree on the attack time. However, message delivery can always fail => the problem becomes harder.

This problem is proven to be solvable only up to a certain probability of failure (meaning there can be cases where it can’t be solved). And this failure probability is unavoidable.

Version 1: Deterministic version

Modeling the problem: n generals numbered 1,…n. The initial decision state of each general is 0 (don’t attack) or 1 (attack). The problem accounts for message delivery that can fail. The problem to solve is for the generals to reach a final conclusion.

Agreement: No 2 generals decide on 2 different values.

Validity:

  • If all generals decide not to attack (0), then 0 must be the final result.
  • If all generals decide to attack (1), and all messages get through, then 1 is the final decision.

Termination: All generals must have a final decision.

The Agreement and Termination conditions are quite strict. The Validity condition can have many variants. In fact, the Validity condition above is the weak kind. Some other variants, for example 1: if one general starts with 1, the algorithm eventually chooses 1. Example 2: if all generals start with 1, and just 1 message gets lost, the algorithm is allowed to stop with a final decision of 0.

Treat the network between the generals as an undirected graph, where the messengers’ paths are the graph’s edges. It can be proven mathematically that the problem can’t be solved on any graph with 2 or more vertices. That means there is always a case with no solution.

Version 2: Randomized version

In the version above we assumed the n generals have their initial decisions set (although random), and their positions and messengers are arranged (the graph is fixed). In this version, we add some assumptions to increase randomness:

  • The agreement condition is still acceptable with a fraction e of generals reaching different conclusions.

=> we need to estimate the bounds min_e <= e <= max_e against the number of communication rounds (r) needed for the problem to finish.

=> The math shows that this ratio e is not small compared to r.

Final result: 1/(r+1) <= e <= 1/r.

Consensus with process failures (process failure)

Describing the agreement problem

Consider the case where communication is perfectly reliable but the processes themselves can fail. There are 2 kinds of failure: 1) stopping failure - going offline 2) byzantine failure - being attacked or impersonated.

Modeling the problem: n processes connected in a graph. Every process can connect to all the others. Assume at most f processes can fail, and the graph edges work without failures.

Validity: If all processes are initialized with the same value v, then v is the final and only consensus value. Agreement: The system is allowed to keep running even though up to f processes produce results different from the majority of the other processes.

The stopping failure case:

Agreement: No 2 processes decide 2 different values. Validity: as above. Termination: All non-stopped processes eventually make a decision.

The byzantine failure case:

The strict assumption is that a byzantine process can only cause harm in 2 ways: 1) sending wrong information 2) switching its own state incorrectly. A byzantine process can’t affect the results or messages of other processes.

Agreement: No 2 non-faulty processes decide 2 different values. Validity: As above, for all non-faulty processes. Termination: All non-byzantine processes eventually make a decision.

The difference between stopping failure and byzantine failure Stopping processes have to accept the result of the crowd, while byzantine processes can’t be controlled.

Algorithms for stopping failures:

  • FloodSet
  • EIGStop (Exponential Information Gathering)

Algorithms for byzantine failures: It is proven mathematically that the byzantine problem is only solvable when the number of processes (n) is greater than 3 times the number of faulty processes: n >= 3f + 1

  • EIGByz

For the case where processes only need to decide 0 or 1:

  • TurpinCoan
  • ConsistentBroadcast
  • PolyByz

Some notable conclusions:

  • The condition n >= 3f + 1 is mandatory for every algorithm that solves the consensus problem with fault tolenrance.
  • The minimum number of rounds needed to reach consensus is f + 1.
  • The conclusions above apply to both cases: stopping failure and byzantine failure.