We all broadly understand “consensus” as the notion of different parties agreeing with each other. In distributed computing, Consensus is one of the core functionalities. In this post, we define the consensus problem and discuss some variants and their differences.
In modern parliaments, the passing of decrees is hindered by disagreement among legislators – Leslie Lamport, Part-Time Parliament
Let us begin with the simplest consensus problem: agreement.
The Agreement Problem
In this problem, we assume a set of $n$ parties where each party $i$ has some input $v_i$ from some known set of input values $v_i \in V$. A protocol that solves Agreement must have the following properties:
Agreement: no two honest parties decide on different values.
Validity: if all honest parties have the same input value $v$, then $v$ must be the decision value.
Termination: all honest parties must eventually decide on a value in $V$ and terminate.
Obviously, Agreement is easily solvable if all parties are honest and the system is synchronous. To make the problem non-trivial we need to fix the communication model synchrony, asynchrony, or partial synchrony and then fix the threshold of the adversary and other details about the power of the adversary.
In the binary agreement problem, we assume the set of possible inputs $V$ contains just two values: 0 and 1.
For lower bounds it’s often beneficial to define an even easier problem of agreement with weak validity where we replace validity with:
Weak Validity: if all parties are honest and all have the same input value $v$, then $v$ must be the decision value.
More validity options and the notion of external validity is discussed in this post.
Uniform vs. non-uniform agreement
When the adversary is omission or crash, then the agreement property above is called non-uniform agreement. We can also have a stronger uniform agreement property where no two (even faulty) parties decide on different values. This is called uniform agreement and assumes an omission or a crash adversary (this definition is meaningless with malicious corruptions).
For example, the difference will be relevant in a state machine replication setting with omission faults. For another example, see this later post.
The Broadcast Problem
Here we assume a designated party, often called the leader (or dealer) that has some input $v$. A protocol that solves Broadcast must have the following properties:
Agreement: no two honest parties decide on different values.
Validity: if the leader is honest then $v$ must be the decision value and all honest will terminate.
For synchrony: Termination: all honest parties must eventually decide on a value in $V$ and terminate.
For asynchrony: Totality: if an honest party terminates then all honest parties must eventually decide on a value in $V$ and terminate.
Broadcast and Agreement are deeply connected in synchrony. A nice exercise is to solve Broadcast given Agreement. Another good exercise is to solve Agreement given Broadcast. You can find this solution in this post.
Please leave comments on Twitter.