I think there are open possibilities in making leaderless single-round-trip consensus systems for log-oriented FSMs, which is what pretty much everyone WANTS.
This is based on her presentation and some dinner conversation at HPTS 2019, so I don't know if there's actually a paper I can point to. The gist of is that Paxos normally involves an arbitration phase where there are conflicting proposals, which adds a second pair of message delays. But if you relax the consensus problem to agreement on a set of proposals, rather than a single proposal, you don't need the arbitration phase. Instead of "who won", it becomes "everyone wins". Then you can impose an order on that set via, say, sorting, and iterate to get a replicated log.
I read over bits of Elle; the documentation in it is absolutely top-notch. You and Peter Alvaro knocked it out of the park!
Thank you! Could I... hang on, just let me grab reviewer #1 quickly, I'd like them to hear this. ;-)
> This is based on her presentation and some dinner conversation at HPTS 2019, so I don't know if there's actually a paper I can point to. The gist of is that Paxos normally involves an arbitration phase where there are conflicting proposals, which adds a second pair of message delays. But if you relax the consensus problem to agreement on a set of proposals, rather than a single proposal, you don't need the arbitration phase. Instead of "who won", it becomes "everyone wins". Then you can impose an order on that set via, say, sorting, and iterate to get a replicated log.
This sounds very similar to atomic broadcast (https://en.wikipedia.org/wiki/Atomic_broadcast) where each node sends a single message and the process ensures that all nodes agree on the same set of messages. Not sure how it would fit with a log-oriented FSM, but it certainly sounds interesting.
It’s really pretty trivial to implement RSM given an atomic broadcast protocol. But you can implement many other things, like totally ordered ephemeral messaging with arbitrary fanout, or a replicated durable log ala Kafka. Here’s my current favorite atomic broadcast protocol (from 2007 or so), which is leaderless, has write throughput saturating network bandwidth, and read throughput scaling linearly with cluster size:
This is based on her presentation and some dinner conversation at HPTS 2019, so I don't know if there's actually a paper I can point to. The gist of is that Paxos normally involves an arbitration phase where there are conflicting proposals, which adds a second pair of message delays. But if you relax the consensus problem to agreement on a set of proposals, rather than a single proposal, you don't need the arbitration phase. Instead of "who won", it becomes "everyone wins". Then you can impose an order on that set via, say, sorting, and iterate to get a replicated log.
I read over bits of Elle; the documentation in it is absolutely top-notch. You and Peter Alvaro knocked it out of the park!
Thank you! Could I... hang on, just let me grab reviewer #1 quickly, I'd like them to hear this. ;-)