2 for the second question
source | link

For your first question

Q: 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?

The short answer is that serializability is inherently a blocking property. Quoted from Section 3.3 of the paper: Herlihy@TOPLAS'90:

A: Serializability is inherently a blocking property: under certain circumstances, a transaction may be unable to complete a pending operation without violating serializability, even if the operation is total. Such a transaction must be rolled back and restarted, implying that additional mechanisms must be provided for that purpose. For example, consider the following history involving two register objects: $x$ and $y$, and two transactions: $A$ and $B$.

x Read( ) A
y Read( ) B
x Ok(O) A
Y Ok(O) B
x Write(l) B
y Write(l) A

Here, A and B respectively read x and y and then attempt to write new values to y and x. It is easy to see that both pending invocations cannot be completed without violating serializability. Although different concurrency control mechanisms would resolve this conflict in different ways, such deadlocks are not an artifact of any particular mechanism; they are inherent to the notion of serializability itself. By contrast, we have seen that linearizability never forces processes executing total operations to wait for one another.


For your second question

Q: Additionally, what does blocking mean in the context of a history? Does blocking remove an item from the history?

A: An operation is blocked in a history if its invocation event has no matching response event.

I am not able to answer the question "Additionally, what does blocking mean in the context of a history? Does blocking remove an item from the history?". My opinion is that it may or may not cause effects in the history. It is non-deterministic.

For your first question

Q: 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?

The short answer is that serializability is inherently a blocking property. Quoted from Section 3.3 of the paper: Herlihy@TOPLAS'90:

A: Serializability is inherently a blocking property: under certain circumstances, a transaction may be unable to complete a pending operation without violating serializability, even if the operation is total. Such a transaction must be rolled back and restarted, implying that additional mechanisms must be provided for that purpose. For example, consider the following history involving two register objects: $x$ and $y$, and two transactions: $A$ and $B$.

x Read( ) A
y Read( ) B
x Ok(O) A
Y Ok(O) B
x Write(l) B
y Write(l) A

Here, A and B respectively read x and y and then attempt to write new values to y and x. It is easy to see that both pending invocations cannot be completed without violating serializability. Although different concurrency control mechanisms would resolve this conflict in different ways, such deadlocks are not an artifact of any particular mechanism; they are inherent to the notion of serializability itself. By contrast, we have seen that linearizability never forces processes executing total operations to wait for one another.

For your first question

Q: 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?

The short answer is that serializability is inherently a blocking property. Quoted from Section 3.3 of the paper: Herlihy@TOPLAS'90:

A: Serializability is inherently a blocking property: under certain circumstances, a transaction may be unable to complete a pending operation without violating serializability, even if the operation is total. Such a transaction must be rolled back and restarted, implying that additional mechanisms must be provided for that purpose. For example, consider the following history involving two register objects: $x$ and $y$, and two transactions: $A$ and $B$.

x Read( ) A
y Read( ) B
x Ok(O) A
Y Ok(O) B
x Write(l) B
y Write(l) A

Here, A and B respectively read x and y and then attempt to write new values to y and x. It is easy to see that both pending invocations cannot be completed without violating serializability. Although different concurrency control mechanisms would resolve this conflict in different ways, such deadlocks are not an artifact of any particular mechanism; they are inherent to the notion of serializability itself. By contrast, we have seen that linearizability never forces processes executing total operations to wait for one another.


For your second question

Q: Additionally, what does blocking mean in the context of a history? Does blocking remove an item from the history?

A: An operation is blocked in a history if its invocation event has no matching response event.

I am not able to answer the question "Additionally, what does blocking mean in the context of a history? Does blocking remove an item from the history?". My opinion is that it may or may not cause effects in the history. It is non-deterministic.

1
source | link

For your first question

Q: 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?

The short answer is that serializability is inherently a blocking property. Quoted from Section 3.3 of the paper: Herlihy@TOPLAS'90:

A: Serializability is inherently a blocking property: under certain circumstances, a transaction may be unable to complete a pending operation without violating serializability, even if the operation is total. Such a transaction must be rolled back and restarted, implying that additional mechanisms must be provided for that purpose. For example, consider the following history involving two register objects: $x$ and $y$, and two transactions: $A$ and $B$.

x Read( ) A
y Read( ) B
x Ok(O) A
Y Ok(O) B
x Write(l) B
y Write(l) A

Here, A and B respectively read x and y and then attempt to write new values to y and x. It is easy to see that both pending invocations cannot be completed without violating serializability. Although different concurrency control mechanisms would resolve this conflict in different ways, such deadlocks are not an artifact of any particular mechanism; they are inherent to the notion of serializability itself. By contrast, we have seen that linearizability never forces processes executing total operations to wait for one another.