[Solved]: How can an extended linearizable history G be equivalent to sequential history S?

Problem Detail: 

I am undertaking a module in Concurrent Programming where some of the new content this year covers linearizability, the Java Memory Model, and sequential consistency. Our class slides are companion slides to The Art Of Multiprocessor Programming.

I have been doing OK with linearizability but have become confused at this point below:

I understand that removing pending invocations gives a complete subhistory, however I cannot understand from this example how a subset G can be equivalent to set S which is larger than it - how is G obtained from S here?

As far as I am aware there is not enough information to determine if there are pending invocations from the diagram on the right and I am not sure why a --> b is removed in the subset that is G - at first I thought it's because they are overlapping but A and B both have linearization points for viewing them 'as sequential objects'.

I may be over looking something simple and have just misunderstood the slides.

Asked By : Vixxd

Answered By : Yuval Filmus

The idea of linearizability is that the parallel events behave as if each of them happened at a single point in time, during the duration of the actual execution of the event. Given a sequence of events, if the end point of event $A$ precedes the starting point of event $B$ then in any linearization, the time point of $A$ must precede the time point of $B$. These are the constraints $\rightarrow_G$, which we can think of as a partial order. The events are linearizable if the constraints are extendable to a linear order $\rightarrow_S$ such that the semantics match — the outcome of the events is the same as if they were applied in the order underlying $\rightarrow_S$. Perhaps this is what was meant by equivalence, though as you mention, it is clearly applied to the wrong objects. What is equivalent here is the actual turn of events and the turn of events given the order $\rightarrow_S$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/19901