Menu
I have found people answering differences between linearizability and searializability, but nowhere have I found people either saying that serializability is same as sequential consistency or it is different from that.
Also I have been pounded with different definitions of the above terms in different articles, books and web pages and I have confused it all. Could someone please explain the difference between serializability and sequential consistency is it exists.
I would appreciate formal definitions of the above terms additionally if possible (both in plain English and in terms of the program or execution histories).
863
Sequential consistency is a strong safety property for concurrent systems. Informally, sequential consistency implies that operations appear to take place in some total order, and that that order is consistent with the order of operations on each individual process.
Informally, serializability means that transactions appear to have occurred in some total order. Serializability is a transactional model: operations (usually termed “transactions”) can involve several primitive sub-operations performed in order.
In sequential consistency events are only related by program order, i.e., two events that happen in different threads are not related. In linearizability we also require that each method call takes effect at some point between the methods invocation and its response.
a) Sequential Consistency → Causal Consistency In sequential consistency, all writes must be seen in the same order by all processes. In causal consistency, causally related writes must be seen in the same order.
Serializability is more strict than Sequential consistency.
The definition of Sequential consistency in wiki: The result of any execution is the same as if the operations of all the processors were executed in some sequential order, and the operations of each individual processor appear in this sequence in the order specified by its program.
And, the definition of Serializability in wiki: A transaction schedule is serializable if its outcome (e.g., the resulting database state) is equal to the outcome of its transactions executed serially, i.e. without overlapping in time.
So, the granularity of Sequential consistency is a single operation (e.g., read or write), while that of Serializability is a transaction (i.e., a sequence of operations).
In other words, if a program satisfies serializablity, it also satisfies sequential consistency, and not vice versa.
130
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
