A leaderless consensus algorithm.
N nodes.
One of them gets a message A. Immediately assumes it.
Replicates it to other nodes: "I assume message A for round 1."
Once 51% of other nodes responded that they have assumed A, it can start processing A in the state machine.
Nodes gossip about the current state of consensus, who assumes what, etc. They also request information from specific nodes when they are interested in it.
When other nodes get wind that 51% of nodes assume a message for a round, they can also start processing it.
Another one gets a message B. Immediately assumes it.
Replicates it to other nodes: "I assume message B for round 2."
Once 51% of other nodes responded that they have assumed B, it can start processing B in the state machine.
It may also gossip to other nodes. "I assigned message B to round 2." If other nodes get wind of an assignment, they can just run with it as well.
If a node notices that no message will reach 51% assumption in a round, it's a bust: "I assign nothing to round 3."
When that happens, it may do some more research i.e. query other nodes about what their assumption was.
It moves on to the round 4. Its starting assumption for round 4 is the message that was assumed by most nodes (that it knows of) in the previous round.
With growing numbers of bust rounds, the likelihood of doing more and more research should increase and at some point reach 100% research. I.e. a node will only make a decision about an assumption on the next round if it knows what all (reachable) nodes in the previous round assumed.
When all nodes know all assumptions of all other nodes in a previous round, the next round is guaranteed to succeed.
If two messages tie in assumptions, there should be a consistent bias towards one of them e.g. the one with the lower message id.
Driftwood is about finding consensus about ordering a list of incoming messages.
The messages are ordered by assigning them to rounds.
Each round is assigned 1 or 0 messages.
Rounds are just numbered ascendingly.
A node assumes a message for a round when it has no prior knowledge and gets a new message.
When there were previous rounds from which information could be derived, it may assume different messages.
A node assigns a message to a round when it knows that all other nodes will also assign that message to that round.
It will only know that if:
A node may also assign nothing/bust to a round when it knows that all other nodes will also assign nothing/bust to that round.
It will only know that if:
Doesn't actually mean 51%, it just means >50%.
As in "gossip protocols".
I made this up when I learned about Raft and found the fact that there has to be a leader and multiple phases a bit inelegant.
I have not implemented this, let alone done benchmarks or tests.
I assume Raft is faster, better and stronger in a lot of cases.
But I like the elegance of driftwood. And I think it works.