jzhao.xyz

Search IconIcon to open search
     * _ 
*_#  \/
  \._/#
  //        

Consensus

Last updated July 3, 2022

Consensus in human systems is actually usually pretty easy because of the social layer of society. This fault tolerance against 51% attacks is due to the fact that convincing the community that any engineered ’truth’ is the real on requires subverting every trusted member in the community, most notably media and news sources (also why systems of authoritarian power are so scary).

A difficult problem for governance within communities

# Consensus and Humming in the IETF

Source: IETF

On rough consensus

# Algorithmic Consensus

There are four requirements to such an algorithm:

  1. Validity. The result must be a value that was submitted by at least one of the processes. The consensus algorithm cannot just make up a value.
  2. Uniform agreement. All nodes must select the same value.
  3. Integrity. A node can select only a single value. That is, a node cannot announce one outcome and later change its mind.
  4. Termination. Also known as progress, every node must eventually reach a decision.

See also: 33% Impossibility Result

# Total order broadcast

Consensus is traditionally formulated as several nodes needing to come to an agreement about a single value. Consensus in the context of total order broadcast is on what the next message to deliver is

One way to do it is using a single leader, but what happens if the leader crashes/becomes unavailable? Manual failover: human operator chooses a new leader and reconfigures each node to use new leader, but this is non-ideal.

FLP Result states that these consensus algorithms cannot assume an asynchronous system model without giving up either safety or liveness.

# State Machine Replication

A subset of the algorithmic consensus problem about agreeing on the same state

  1. Consistency: all notes agree on the same history
  2. Liveness: every transaction submitted eventually added to all node’s histories

SMR can be reduced to BB

# Byzantine Agreement

Differs from Byzantine Broadcast

Every node has a private input, there is no distinguished sender.

All non-Byzantine nodes need to agree on a single common value.


Interactive Graph