tldr; I don't see world-changing novelty here, theoretically. There are dozens of other consensus algorithms in the world, some randomized, some not quorum based, etc. This is interesting if you're in Paxos land, trying to tune your Paxos for different fault-tolerance requirements. It's no way comparable to a computational model.
This is not true. It generalizes quite many more than that. It happens to use PaxOS as examples.
This is not a property of all consensus algorithms. Consensus algorithms don't need to behave this way. Paxos and derivatives behave this way, but I'm not sure Raft, etc. slide in as neatly (that would require a substantial analysis).
In particular, this generalization does not capture any nondeterministic algorithm, any algorithm tolerating Byzantine faults (or various other consensus problems), any non-quorum based algorithm, Nakamoto style (which is a byzantine consensus algorithm), Ben-Orr, etc. etc.
So, my question for you: what other algorithms do you think this paper generalizes, that are useful outside of the narrow scope of optimizing Paxos?
Don't forget that people often just want to use an algorithm and are not necessarily that interested in the underlying mathematical structure, only in whether it works reliably and does a better job than the existing solution.
Can we take a second to appreciate that this result will rapidly become the first thing taught in every single distributed systems class? And if this holds as a generalization of trustful distributed consensus as a field, then she has defined its Turing Machine equivalent. And it is even remarkably easy to understand! That is wild!!
Props to the authors. Personally, this is going on the top of my “to memorize” list.