What is the consensus algorithm that requires an odd number of nodes?

Question

Last week I stood up and gave a talk on the Raft Consensus Algorithm.

The first question I got was:

Doesn't it need an odd number of nodes?

I answered "During leader election, the first node to become a candidate, all the other nodes have to vote for. (Provided for that node the lack of heartbeat, timeout conditions have been triggered, and for the client nodes the candidate has an update to date term log). If two candidates arise at the same time, and neither gets a majority, each will fall back to a different random timeout, and the first to become a candidate (provided all the other criterion are met) will win. So you don't need an odd number of nodes to reach a majority, you just need to be the first candidate. Split votes are handled."

Immediately after this answer - I got the same question from a different person all over again.

So how does it reach consensus if it doesn't have an odd number of nodes?

My question is: What is the consensus algorithm that requires an odd number of nodes?

EDIT:

Here is an online publication that claims distributed systems need an odd number of nodes. (Spurious claim).

Partition tolerant consensus algorithms use an odd number of nodes (e.g. 3, 5 or 7). With just two nodes, it is not possible to have a clear majority after a failure. For example, if the number of nodes is three, then the system is resilient to one node failure; with five nodes the system is resilient to two node failures.

Answer 1

To my knowledge there is no quorum-based consensus algorithm that requires an odd number of nodes (processes). That's because such algorithms don't require a majority in the sense that a higher number of processes accept a value. A majority in these algorithms means that at least $N / 2 + 1$ processes accept a value, where $N$ is the total number of processes.

The reason for this is that a quorum-based algorithm requires that every decision made is known by at least one member of each one of the possible quorums in the system. One simple way (but not the only one) to achieve this is to require that every quorum is composed by $N/2 + 1$ processes and that the vote is unanimous inside a quorum.

For example, in a system with two processes two votes are required and the system is not fault tolerant. For three processes two votes are required. For four, three votes. For five, three votes.

Answer 2

"Always have an odd number of replica set members" is a common simplification of the MongoDB replica set election process and best practices for deployment, but certainly not a strict requirement.

The main requirement to elect (and sustain) a primary in a MongoDB replica set is a healthy majority of configured voting members able to communicate with each other. As at MongoDB 3.6, there is a maximum of 7 voting members per replica set with up to 50 members in total. All members are voting by default; non-voting members can be configured but are not eligible to be candidates for the role of primary.

An even number of voting replica set members does not improve fault tolerance over a similar replica set with one less voting member. The majority of a replica set (n/2 + 1) with 4 voting members is 3 while the majority with 3 voting members is 2. Both of these configurations can only tolerate unavailability of a single voting member in order to elect (and sustain) a primary.

An odd number of voting members can reduce the chance of tied elections where half the members vote for a different (but equally eligible) candidate to become primary, or where a network split creates several partitions without a majority of voting members. The maximum of 7 voting members puts a reasonable limit on the number of potential participants in a distributed election.

Elections will still be successful given an even number of voting members, but may require more voting rounds to confirm a majority win in some circumstances. With MongoDB's original v0 replica set protocol, election rounds were consecutive so failed elections could add notable delay. MongoDB 3.2 introduced a new v1 replica set protocol inspired by Raft, which allows concurrent elections and significantly reduces election time. MongoDB's v1 protocol extends Raft with some practical deployment considerations such as member priority, replication chaining, and primary catch-up (to avoid unnecessary rollback of committed data). For more background details, see: Replication Election and Consensus Algorithm Refinements for MongoDB 3.2 and Raft Consensus in MongoDB.

Answer 3

This clicked for me this week in a MongoDB Product Forum. Mongo requires an odd number of nodes to establish a majority.