Really enjoyed this, and learning a little bit of combinatorics at the same time.
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.
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 [...] at least one node participated in both. This single overlapping node carries forward the knowledge of what was previously committed, preventing conflicts and ensuring consistency.
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.
I really enjoy when it when someone injects a dose of "wacky" into something that is taken more or less for granted (Raft) to challenge the standard way of thinking about it.
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).
> 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.
Really enjoyed this, and learning a little bit of combinatorics at the same time.
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.
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 [...] at least one node participated in both. This single overlapping node carries forward the knowledge of what was previously committed, preventing conflicts and ensuring consistency.
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.
I really enjoy when it when someone injects a dose of "wacky" into something that is taken more or less for granted (Raft) to challenge the standard way of thinking about it.
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).
excellent article.
> 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.