Replication with sequential and causal sequence
The shared variables x, y, and z are accessed by two processes. Each process accesses a different storage replica used to store these variables. Initially, x, y and z are 0.
Process 1:
x = 1; if (y == 0) z++;
And process 2:
y = 1; if (x == 0) z++;
After completing both statements, what are the possible values of z in a) sequential and b) random consistency model?
I know that in a sequential order, processes are executed in some sequential order as indicated by the program. I believe that in the example above, the result for z will be zero in the sequential consistency model, since the two processes are running concurrently in the order listed in the processes. Thus, none of the if conditions are met. But I'm not sure.
To be random, related records must be in the same order across all processes. Simultaneous recordings can be different. I can't figure out how this rule works in our example.
source to share
A sequential system guarantees you that its behavior will always look like some sequential execution of reads and writes, according to the relative order of reads and writes in the program, each of which the processor performs. It makes no guarantees as to what order will output the two operations performed by different processors.
It is of course possible that you end up with:
P1: store(x, 1)
P2: store(y, 1)
P1: load(y) // 1
P2: load(x) // 1
and none of the processors will increment z. However, it is also perfectly reasonable for the system to rely on:
P1: store(x, 1)
P1: load(y) // 0
P1: store(z, z+1)
P2: store(y, 1)
P2: load(x) // 1
With 'z' ending in 1. You will need to add a lock if you want a deterministic result. The sequential system guarantees that z is never 2: there is no way to change the write order so that both processes load the value 0 and increment z without breaking sequential consistency.
In contrast, a causal system does not guarantee that its behavior will always look the same as a single sequential read and write. It is quite normal for different processors to see other people write in different orders as long as those records are not causal. You may well end up:
// P1 local history
P1: store(x, 1)
P1: load(y) // 0
P1: store(z, z+1)
P2: store(y, 1)
// P2 local history
P2: store(y, 1)
P2: load(x) // 0
P2: store(z, z+1)
P1: store(x, 1)
And the final value is 2 for z. Which causal sequence ensures that you are doing the third process:
if (z == 2)
print(x, y)
will never print 0:
- If P3 loads / prints x and y, loads should occur after loading z
- If load z sees value 2, it should happen after P1 and P2 values match in local history P3
- The P1 store (x, 1) must appear before its increment z; similarly for P2 / y
By transitivity, any local history for P3 that includes a print statement MUST be seen for x and y.
source to share