Raft Consensus with a Minority of Nodes
padhye.org
padhye.org
(Heidi's work is both deeper and more practical; this post is just a really cute observation that there's something mathematically deeper underlying the idea of intersecting quora.)
There is another side to this, it must not be possible for two »majorities« to coexist, otherwise they could independently move on in case of a split cluster. This also rules out allowing consensus by majority in addition to majority by a bloc. In the seven node example, there could be a { 1, 2, 3 } and { 4, 5, 6, 7 } split, the first partition being a bloc and the second one being a majority but not containing a bloc.
What you need are rules that define a safe behavior in face of arbitrary communication breakdowns. You need a default behavior that guarantees that you are still doing the right thing no matter which other nodes you can no longer talk to. And safe behavior means two things. First, you need continuity, you must not lose any commits, so at least one node in the current round must have participated in the latest round. Second, you have to ensure that no two groups of nodes independently decide that they should continue to make commits, otherwise the state would diverge.
And from this comes the tensions, you want many nodes in the quorum to make continuity easy, you want few nodes in the quorum to tolerate many failures, you kind of want many nodes in the quorum to prevent multiple quorums.
This article flipped my understanding of split-brain or network partitions on its head: You don't actually have to have a majority to ensure progress, you just have to design your quorum selection criteria in such a way that no other partition believes they are authoritative, and these finite projection planes are an interesting way of proving that (with caveats).
As danbruc mentions below we also would really like our networks to only ever split into sets such that there is at most one set which could include a leader; otherwise we might have a more durable consensus split.
That said, algebraic structures are a tool for working with consensus problems, but there’s also process. Together we get consensus protocols. So, for example, you could have a healing process step that privileges the larger group and forces a merge even if at some moment you had two candidates that believed they were a valid leader for their own split network view.
And for the merging, if you can do that, then why bother with consensus to begin with? The problem is that things that got committed are usually not just sitting in a database, they get read and acted upon. Webservice calls made, credit card transaction processed, parcel shipped, ... You can merge and undo commits in one database easily, controlling the ripple effects of those changes in other systems and the real world becomes impossible quickly.
That seems like horrible tradeoff
The sentence you quote is inevitably going to be true for any type of Raft quorum that can reach consensus with a minority of nodes. You don't even need to get into the specifics of the math.
Suppose you have a quorum Q. Then its complement Q' must not also be able to form a quorum; if it did, a network partition between Q and Q' would create a split-brain. So if Q is a minority subset, then Q' is a majority that cannot reach consensus on its own.
> The key correctness insight is this: any two majorities of nodes must overlap in at least one node. So between any two consecutive global state changes — whether two commits, two leader elections, or one of each — at least one node participated in both.
intuitively makes sense, but would be nice to see this result explicitly derived or illustrated the same way the fano planes were.
The idea of non-MDS erasure codes isn't quite the same, but they're related in the way that MDS codes are the easiest to think about, and non-MDS codes come with interesting complexities while opening up some cool new options for system design and recovery.
Using "majority" as the criterion has been around for a long time (e.g. Gifford in '79 https://pages.cs.wisc.edu/~remzi/Classes/739/Fall2015/Papers..., and Thomas also in '79 https://dl.acm.org/doi/10.1145/320071.320076). Also related is the idea of weighted voting (e.g. Peleg and Wool in '95 https://www.sciencedirect.com/science/article/pii/S089054018...).