Exercise 33

[Unmesh Joshi]

Please find the flaw in following explanation:                 
33. Prove that sequential consistency is nonblocking!

I think otherwise. Counter-example is following:

A: ------enq(x)------------------deq(x)---------------->

B:--------enq(y)-------------------deq(y)-------------->

Possible sequential consistent reordering is

    OP1     ->      OP2      ->     OP3       ->      OP4
[enq(x), A] -> [<enq(y), B>] -> [<deq(x), B>] -> [<deq(y), A>]

Now if thread B is delayed in either of the operations OP2 or OP3,
then thread A would not make any progress. (thread A is blocked)

Therefore this sequentially consisteny schedule is NOT non-blocking.
Hence, sequential consistency is  NOT non-blocking.

[Unmesh Joshi]

[Edit]
Changed the execution

On Sunday, October 13, 2013 12:58:21 AM UTC+2, Unmesh Joshi wrote:

Please find the flaw in following explanation:                 
33. Prove that sequential consistency is nonblocking!

I think otherwise. Counter-example is following:

A: ------enq(x)------------------deq(y)---------------->

B:--------enq(y)-------------------deq(x)-------------->

Possible sequential consistent reordering is

    OP1     ->      OP2      ->     OP3       ->      OP4
[enq(x), A] -> [<enq(y), B>] -> [<deq(x), B>] -> [<deq(y), A>]

Now if thread B is delayed in OP2

[SHEKHAR BHANDAKKAR]

Hello,

Method calls by different threads are unrelated by program order.

So, we can reorder the method calls by different threads. 

This explains the non-blocking property of SC.

In your question we can reorder as:

A: -----------enq(x)------------------deq(x)-------------->

B: ---------------------enq(y)------------------deq(y)---->