Exercise 82

[f zh]

1.  Explain how removing Line28 would violate Lemma6.4.4

I just can not see it violate the Lemma. In line 1~7, the lemma followed as the start(A) and head[A].seq are that of the announcement before current one. After line 8 and before line 9, it is possible start(A) > head[A].seq as head[A] is not the max. While even line28 had not been removed, start(A) > head[A].seq is also possible for the same reason. After line 9, the Lemma must be followed as head.seq can not decrease.

2. Would the algorithm still work correctly?

I think it is still OK. If it is NOT OK, the way to prove may be:

start(A) > head[A].seq ==>  After n + 1 iterations, head[A].seq - start(A) >= n violated ==> | concur(A) | > n violated ==> announce[A] belongs to head[] failed. 

But I can not figure out an example to convince myself. How could it fail?

Not exclusive? The Consensus Object guaranteed it.

Not return correct result? The apply travels through the whole list till the announce[A], instead of head[A]. The apply() result does not relate to head[] directly.

Not wait-free, i.e. starvation? If announce[A] can not be appended when the algorithm is still lock-free, the only possible reason I can see is that when ((before.seq + 1) % N) = A and before.next had been occupied. While how can the fastest thread observed announce[A] and get next seq = A and appended another announce?

Please help me to understand it. Thank you.