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
Another definitnion of linarizibilty using subhistories
H is linearizable if, and only if, for each object x, Hjx (projection of x in H) i.e. the subhistory of H with only all method calls concerning object x, is linearizable.
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.
What isthe idea of consensus?
Tipp: notion of how strong a certain synchronization primitive, such as TAS, is.
First off the consensus number of primitive is only used for proofs
Each class in the hierarchy has an associated consensus number, which is the maximum number of threads for which objects of the class can solve an elementary synchronization problem called consensus.
What is the consensus problem?
ou have N processes. Every thread gets to propose a value, then the threads should decide on one and the same of these proposed values.
What are valid outcomes of the consensus problem in following scenario:
Thread A suggests value A, Thread B suggests value B.
Then the valid outcomes are that either both threads decide A, or that both threads decide B.
There are different special objects or operations that are useful in solving consensus problems. What does the consensus number say about them?
The powerfulness of a special object is graded by their consensus number. This equals the maximum number of threads for which they can solve the consensus problem.
Remember consensus problem: all threads decide on the same value
Give example for:
Consensus number 1
Consensus number 2
Consensus number infinity
1: Normal read/write registers. (That is, plain variables.)
2: Test & set (a.k.a. compare & set), queue, stack et.c.
infinity: Compare & Swap
What consensus number do atomic registers have?
1 (They can solve the consensus problem only for one thread)
What is part of the consensus problem and what methods are used in it? How does the consensus problem play out?
A consensus object provides a single method decide(). Each thread calls the decide() method with its input v (v is a value every thread has a different one they want to agree on one) once. The objects decide() method (decision of every thread) will then return a value meeting the following conditions:
consistent: all threads decide the same value
valid: the common decision value is some thread’s input
I := Invoke R:= Response
Just 1 thread
H_S : I1 R1 I2 R2 I3 R3
What can we say about this history
Its a sequential history hence a sequence of events of which each Invoke is followed instantaneously by its ceorresponding Response.
There is no concurrency here there is just 1 thread
