5
$\begingroup$

According to this paper written by Lamport, `selecting a unique leader is equivalent to solving the consensus problem'.

Based on the above quote, my question is: What is the difference between consensus and leader election problems?

My answer: I think that there is no theoretical difference between them. They are two terms with the same meaning, but they are used in different context. When the context is related to data stores, replication, or related subjects, 'consensus' is used, otherwise, 'leader election' is used.


Note: In the above paragraph, 'theoretical' means the way of defining a true consensus and leader election algorithm. A true consensus and leader election algorithm should satisfy three properties-- termination, agreement, and integrity.

$\endgroup$

2 Answers 2

6
$\begingroup$

This is not a matter of terminology: they're related, but different concepts.

A consensus algorithm is one that allows all the participants in a distributed system to choose a value from a set in such a way that all the participants choose the same value. A solution to the consensus problem is a distributed algorithm that has the following properties:

  • At the beginning, each participant $i$ has an initial value $v^0_i$.
  • At the end, all the participants must have the same value: $\forall i, \forall j, v_i = v_j$.
  • The common final value must be the initial value of at least one of the participants: $\exists i, v_i = v^0_i$.

A leader election algorithm is a special case of consensus algorithm where the set is the set of participants. The leader election problem consists of requiring a leader election whenever there is no leader. If there are failures, this may require running more than one election, because a new election becomes necessary when the current leader fails.

In the absence of failures, if you can solve consensus then you can solve the leader election problem: apply consensus with every participant initially choosing themselves. Conversely, if you can elect a leader, then you can solve consensus by having everybody choose the leader's value. This is often how consensus is solved in practice: choose a leader (using a specialized consensus algorithm), then the leader broadcasts its choice of value each time a consensus is needed.

However, if there are failures, this equivalence no longer holds. There are failure models where it's possible to solve consensus, but not to elect a leader. See Laura S. Sabely and Keith Marzullo, Election Vs. Consensus in Asynchronous Systems, Cornell University technical report, 1995. The gap is that certain failure detectors are sufficient to run a consensus algorithm, so they are sufficient to run a leader election, but they are not sufficient to solve the leader election problem, because they aren't sufficient to detect when a new leader election is needed.

$\endgroup$
1
$\begingroup$

Consensus is broader. Leader election is about coming to agreement on the leader. Consensus is about coming to agreement on something -- might be on the leader, but might be something else that the participants want to agree on.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.