Linearizability and Sequential Consistency Flashcards
What does a method call consist of? Histories
A method call consists of a method invocation and response
What is an invocation without matching response called?
pending
What is a history?
a finite sequence of method invocations and responses
what is a subhistory?
a subsequence of the events of a history
What does complete(H) consist of?
the subsequence of a history H consisting of all matching invocation and response events in H.
When is a history sequential?
if every invocation is immediately followed by a matching response, i.e. when no method calls overlap
Name the parts of invocation and response in a history.
Match the invocations and responses. Are there any pending invocations?
What are object nad thread projections of the image?
When are histories equivalent?
When the per thread projections are equal. see image
When does one method call precede another?
When the response event precedes the invocation event.
What 2 requirements mus a program fullfill to be sequentialy consistent?
1) Method calls schould appear to happen in a one-at-a-time, sequential order. Every method call returns before the next one starts.
2) Method calls should appear to take effect in program order. This means that we can order all method calls such that they
a) are consistent with respect to the program order, i.e. they adhere to the ordering imposed
by the thread subhistories
b) meet the object’s sequential specication
Check whether the history is sequentially consistent.
first requirement: method calls happen in a one-at-a-time, sequential order (every subhistory is a sequential history)
How do we check this? Check if in HjA (projection H to thread A) and HjB (projection H to thread B) each method call finishes before the next one starts.
Second requirement: find a method call ordering such that they are consistent with programm order.
How do we check this?
One such order is given by
s.push(1) –> s.push(2) –> s.pop() =2 –> s.pop()-=1
not the only possibility another order is:
s.push(2) –> s.push(1) –> s.pop()=1 –>s.pop()=2
It just need to be correct with the push and pops
Whats the rule to linearizability? informal by word
Tipp: Idea is that the concurrent history is equivalent to some sequential history.
if one method call precedes another, then the earlier call must have taken effect before the later call. By contrast, if two method calls overlap, then their order is ambigous, and we are free to order them in any convenient way.
Definition of linearizability
Start with a history H is linearizable if….
A history H is linearizible if it has a extension H’ such taht H’ is complete and there is a legal sequential history S such that
1) complete(H’) is equivalent to S, and
2) if method call 0 in H precedes method call 1, then method call 0 in S precedes method call 1
What does the picture say about linearibility?
The first SELECT statement reads the value of 50, while the second SELECT reads the value of 10 since in between the two read operations a write operation was executed.
Linearizability means that modifications happen instantaneously, and once a registry value is written, any subsequent read operation will find the very same value as long as the registry will not undergo any modification.
