Re:WPaxos: a wide area network Paxos protocol
by ccleve on Wednesday December 27, 2017 @10:57AM
(#16015456)
Perhaps we should step away from the terms "linearizability" and "serializability" and speak of global total ordering. That's what some other systems provide and this one doesn't. It's a valuable feature because it makes it possible to know the state of the system as of a snapshot in time.
Re:WPaxos: a wide area network Paxos protocol
by matthelb on Wednesday December 27, 2017 @12:01PM
(#16016028)
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.
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...