This is a very good analysis.<p>I think it makes a slightly stronger argument about MultiPaxos than it needs to. There are other correct ways to use single-decree Paxos, as long as you recognize it's limitations. The true limitation is "use every register once", and a log is the gold standard way to do that. Another correct pattern could be a set-only K/V store, or a store for monotonic finite state machine states (at the cost of O(N) rounds for every contender). One real-world example is 2PC coordination, where the state machine is very simple, and can be modeled as an ordered pair of three registers.