[judofyr]

> 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.

[senderista]

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:

https://os.zhdk.cloud.switch.ch/tind-tmp-epfl/394a62dd-278f-...