For PRAM consistency, we consider the actions with their program order but have no need to order all actions into a single total order as required for sequential consistency. Instead, each thread may have its own different view on the ordering of the actions, but also for these local views, we have to respect the write order of the other threads.
To be more precise, if you consider the definition of PRAM consistency on slide 79 of the related chapter, you see that we consider Rstr(<=P,A(p)∪A(write)) which means that we consider all actions A(p) of thread p, and all the write actions A(write) of the other threads, and we respect their program order <=P.
In the example, threads P and Q have the following actions:
p1: read(x,3)
p2: write(x,1)
p3: write(y,2)
q1: read(y,2)
q2: write(x,3)
q3: read(x,1)
For checking PRAM consistency, we need to add the write actions of the other thread(es) to the actions of each thread. For thread P, this is no problem:
q2: write(x,3)
p1: read(x,3)
p2: write(x,1)
p3: write(y,2)
For thread Q, we must add p3 in before q1 since otherwise, there is no reason why q1 may read value 2 from y. But then, p2 must even occur before p3 since we have to respect the ordering of the write actions of thread P. However, then, which is consistent with the value read by q1. But then, variable x will be initialized with 1, and this becomes a problem for q2:
p2: write(x,1)
p3: write(y,2)
q1: read(y,2)
q2: write(x,3)
q3: read(x,1)The above is the only possibility, and it is not consistent.
