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 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.
(Another solution that would solve for long-term unreachable nodes is to use not the majority but a deterministic node's assumption, e.g. round number modulo number of nodes. This would only apply when research reaches 100%, e.g. after 10 bust rounds.)
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.
type StateMachine interface {
Process(msg []byte) error
Snapshot() (snapshot []byte) error
Restore(snapshot []byte) error
}
var ErrFuture = errors.New("round is in the future")
var ErrPast = errors.New("round is too far in the past, information already dropped")
type Driftwood interface {
Assumption(round uint64) (msgId string, err error)
Assignment(round uint64) (bust bool, msgId string, err error)
Msg(msgId) (msg []byte, err error)
}
type PingStats struct {
Err error
Roundtrip time.Duration
}
type Comm interface {
// AllNodes returns ids of all nodes that are configured to be part of this Driftwood network.
// AllNodes()[0] is always self.
AllNodes() []string
// TellMsg notifies a node (nodeId) about the contents (msg) of a message (msgId).
TellMsg(nodeId string, msgId string, msg []byte) error
// TellAssumption notifies a node (nodeId) about the assumption (msgId) of another node (assumerId).
TellAssumption(nodeId string, uint64 round, msgId string, assumerId string) error
// TellAssignment notifies a node (nodeId) about the assignment for a round.
TellAssignment(nodeId string, uint64 round, msgId string) error
// TellBust notifies a node (nodeId) about a bust assignment.
TellBust(nodeId string, uint64 round) error
// AskMsg asks a node (nodeId) about the contents of a message.
AskMsg(nodeId string, msgId string) (msg []byte, err error)
// AskAssumption asks a node about the assumption of another node.
AskAssumption(nodeId string, uint64 round, assumerId) (msgId string, err error)
// AskAssignment asks a node about the assignment of a round.
AskAssignment(nodeId string, uint64 round) (bust bool, msgId string, err error)
Ping(nodeId string) PingStats
}
// Assumptions represents a single round's assumptions.
// It contains msgIds for each node's assumption.
// An empty string means the respective node's assumption is not known.
// len(Assumptions) is the number of total nodes.
// Note that Assumptions[0] does not immediately become the self assumption.
// It will only be set to the self assumption when 51% of the network know about the self assumption.
type Assumptions []string
// Consensus returns whether there is consensus for a round.
// consensus is returned as false if not enough information is available.
// If consensus is returned as true,
// bust is returned as true if the round is a bust.
// If consensus is returned as true and bust is returned as false,
// msgId identifies the msg for which consensus was reached.
func (a Assumptions) Consensus() (consensus bool, bust bool, msgId string)
// Assume marks msgId as the msg assumed by nodeIdx.
func (a *Assumption) Assume(nodeIdx int, msgId string)