I am confused about a statement in The Art of Multiprocessor Programming:
Theorem 3.6.2: Let
inv(m)be an invocation of a total method. If
<x inv P>is a pending invocation in a linearizable history
H, then there exists a response
<x res P>such that
H · <x res P>is linearizable.
This theorem implies that linearizability by itself never forces a thread with a pending invocation of a total method to block.
(The Art of Multiprocessor Programming, Herlihy & Shavit, 2008 Edition, page 58)
I understand that partial methods might need to block for correctness reasons. For example, it is reasonable to block a dequeue operation until there are elements to remove.
However, I don't see why any correctness condition (e.g. linearizability or quiescent consistency) would force an invocation of a total method to block. Is there such a case, or am I misreading the implication of the theorem?
Additionally, what does blocking mean in the context of a history? Does blocking remove an item from the history?