matthelb

I think that's a fair takeaway specifically because you are careful to limit the scope of your comparison to Calvin and Spanner. If you were to replace "Spanner-like" with "partitioned", I'd push back that it's not as clear Calvin is better than non-Spanner partitioned systems, even when you have mostly multi-entity transactions.

EDIT: To be clear, when I say better I mean higher throughput and lower latency.

I appreciate the distinction that Daniel is trying to make between what he calls "partitioned consensus" databases and "unified consensus" databases, but I don't know if the points that he makes about partitioned consensus truly generalize to all such systems.

In the context of this blog post, he specifically calls out partitioned consensus databases for requiring two wide-area round trips in order to run 2PC. However, we've seen multiple examples of partitioned databases (i.e. MDCC, TAPIR, Janus, and others) since the Spanner paper that can commit multi-partition transactions in a single wide-area round trip . Just as in the "unified consensus" approach, failures or concurrency may cause these systems to infrequently take multiple wide-area round trips to commit.

The blog post does a great job explaining the differences between "Calvin-like" systems and "Spanner-like" systems, but it falls short in convincing me that the "Calvin-like" architecture is fundamentally better, or makes better tradeoffs, than any partitioned architecture.

I'm not sure the distinction that you're making between "distributed" and "decentralized" is commonly accepted in the research community (or broader technology community). In this context, the authors appear to be using "decentralized" to contrast with the "centralized" nature of leader-based state machine replication protocols.

Though it might not be explicitly stated in the paper, EPaxos has the same liveness guarantee as all other consensus protocols: commands will eventually commit if a long enough period of synchrony occurs. As the author of this post notes, this is a fundamental limitation of the specification of the consensus problem - no protocol can get around the limitation while solving consensus by definition.

You bring up a good point, although I'm not sure if I agree with (or understand) the premises. I can't imagine a world where hardware and the protocols running on top will be immune to physical sources of faults, such as natural disasters, human intervention, or cosmic radiation(!). As a result, dealing with failures will always be a consideration in building distributed software systems, and Paxos or protocols that solve the same problem as Paxos will always be relevant.

I do think you make a good point that we don't always need Paxos-like protocols. Paxos is a very strong tool, so it solves a difficult problem, but is heavy-handed in many scenarios. There is a lot of space to explore lighter-weight alternatives to Paxos while still providing similarly strong properties.

This is exactly what I was addressing in your initial comment! This system provides a global total ordering of operations. It's the whole point of a replicated state machine.

The ensuing conversation explored how/why the system provides a global total ordering.

I'm not thinking of strict serializability - I do actually mean linearizability.

My previous comments were referring to the basic algorithm presented as the main contribution of this paper in section 3. In this algorithm, "Every command accesses only one object o." With each operation applying to a single object and each object satisfying linearizability, the system as a whole will be linearizable.

The distinction between linearizability and strict serializability is somewhat subtle. I highly recommend this blog post [1] by Irene Zhang and this blog post [2] by Peter Bailis for some really great discussion on the subtleties involved.

[1] https://irenezhang.net/blog/2015/02/01/consistency.html

[2] http://www.bailis.org/blog/linearizability-versus-serializab...

Sorry, I was trying to give the GP more context for my initial comment.

As I said in my initial comment, the authors state that WPaxos provides per-object linearizability, which implies that it provides (to use your term, "global"-)linearizability.

Maurice Herlihy and Jeanette Wing introduced linearizability back in 1990 [1]. It stipulates that the result of a concurrent execution of the system is equivalent to a result from a sequential execution where the order of the sequential execution respects the real-time order of operations in the concurrent execution.

In this context, you could probably use "linear" and "orderable" to mean the same thing. The idea is that, for any linearizable execution, there exists an equivalent total order of the operations. Because there exists a total order, if a client C1 sees A2 before B2 then a client C2 cannot see B2 before A2.

[1] https://cs.brown.edu/~mph/HerlihyW90/p463-herlihy.pdf

I also haven't read through the technical report in detail, but in skimming through parts of it, it looks like WPaxos is supposed to provide linearizability. More specifically, the authors state that:

> WPaxos maintains separate logs for every object and provides per-object linearizability.

Linearizability is a composable correctness condition, so per-object linearizability implies that the composition of all the objects is linearizable. Thus, WPaxos does in fact provide a single total ordering of all operations. Nearly all of the replicated state machines via consensus protocols (Paxos, EPaxos, Mencius, Generalized Paxos, etc.) provide this same consistency level.