Hacker News new | past | comments | ask | show | jobs | submit login
Linearizability versus Serializability (bailis.org)
52 points by r4um on Sept 30, 2014 | hide | past | favorite | 6 comments



How does linearizability provide "real-time" guarantees? It does not unless some uncommon version of "real-time" is being used here.


Let's assume for a second that the effects of general relativity are negligible, and that as external observers of the system, we can see the global ordering of operations on an object as issued by all participating machines.

"Real-time" in this context means all participants observe operations on an object in the order in which they were issued. Not only do all participants see the same total ordering of operations, but that total ordering is the same as the ordering that we would see as global external observers.

Contrast this to serializability, which only guarantees that all participants observe the same total ordering of operations. The order does not need to be consistent with the ordering we would see. For example, if we see that write W1 was issued before write W2, serializability means that the participants must either all agree that W1 occurred before W2, or all agree that W2 occurred before W1. Linearizability means that they must agree that W1 happened before W2, since W1 temporally precedes W2.


Sure, but this is not a "real-time guarantee".


"Real-time guarantee" in the context of consistency models (i.e. this article) means something completely different from "real-time guarantee" in the context of operating systems.


My suspicion is that the author was trying to distinguish total order of events vs. partial order of events. I feel like the reason vector clocks and the like were created was to deal with the fact that real-time is problematic in distributed system. There is some response from the author though on this question: http://www.bailis.org/blog/linearizability-versus-serializab...


Looks like it (confusion between 'real-time' precedence and real-time guarantee), thanks.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: