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
On rough consensus
- Humming as ’temp checks’ for people to voice disagreement but default assumption is optimistic trust
- “While counting heads might give a good guess as to what the rough consensus will be, doing so can allow important minority views to get lost in the noise. One of the strengths of a consensus model is that minority views are addressed, and using a rough consensus model should not take away from that.”
- “We can’t know who the “members” of any given working group would be at any one time, and we certainly can’t know who all of the “members” of the IETF would be: That’s why we refer to “participants” in the IETF; the IETF doesn’t really have “members”. Indeed, we often recruit additional implementers and other experts into working groups in order to ensure that broader views are brought into the discussion. So, voting is simply not practical.”
# Algorithmic Consensus
There are four requirements to such an algorithm:
- 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.
- Uniform agreement. All nodes must select the same value.
- Integrity. A node can select only a single value. That is, a node cannot announce one outcome and later change its mind.
- 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.
- Common consensus algorithms (all assume partially synchronous, crash-recovery system model)
- Paxos: single-value consensus
- Multi-Paxos: generalization to total order broadcast
- Raft, Viewstamped Replication, Zab: total order broadcast by default
- Blockchain consensus models assume partially synchronous Byzantine system model
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
- Consistency: all notes agree on the same history
- 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.