3 ms·
I'm not thinking of strict serializability - I do actually mean linearizability. My previous comments were referring to the basic algorithm presented as the ma
by matthelb 9y ago
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 https://irenezhang.net/blog/2015/02/01/consistency.html
[2] http://www.bailis.org/blog/linearizability-versus-serializability/ http://www.bailis.org/blog/linearizability-versus-serializab...
- ccleve 9y agoPerhaps 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.
- matthelb 9y agoThis 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.