concurrency - 顺序一致但不可线性执行

Question

我试图了解线性一致性和顺序一致性之间的区别。更具体地说，我想要一个顺序一致但不可线性化的执行示例。我的教授给了我以下这种执行的例子:

Alice and bob write checks to each other.
Alice’s Statement:
-10  Check Alice -> Bob
0  Check Bob -> Alice

Bob’s Statement
-10  Check Bob -> Alice
0  Check Alice -> Bob

Both overdraft.
It is sequential: each client sees a consistent order
It is not linearizable: no globally linear story 

但是我没看懂。线路

n Check A -> B

应该被解释为“A在操作后给B及其账户写了一张支票是n”。我不明白为什么该操作不应该是可线性化的:Alice 和 Bob 最终都以 0 结尾，这是一个一致的值，所以我可能没有正确理解“线性化”的定义。

Answer 1

首先，你的教授给你的不是明确的历史/执行，而是历史在它的两个线程上的投影。

历史 H 是可线性化的，如果通过离开挂起的调用和/或添加对挂起的调用的响应(你没有离开)你可以获得等同于不矛盾的顺序历史 S 的历史H 隐含的优先级。

换句话说，您的示例不可线性化的原因是操作(金融交易)无法分配到单个时间点。先扣除钱，然后再添加，线程/个人银行对账单会观察到这种行为。

如果银行对账单是

Alice’s Statement:
-10  Check Alice -> Bob
0  Check Bob -> Alice

Bob’s Statement
10  Check Alice -> Bob
0  Check Bob -> Alice

那么我们将有一个历史 S 如下:

Alice: Send Bob 10
Alice: Send completed
Bob:   Send Alice 10
Bob:   Send completed

但在您的示例中，历史可能是

Alice: Send Bob 10 (i.e. money is gone)
Bob:   Send Alice 10 (i.e. money is gone)
Bob:   Send completed (i.e. money arrived)
Alice: Send completed (i.e. money arrived)

(或第 1/2 行和第 3/4 行的任意组合)并且您不能按顺序重新排序(即成对的开始/完成一起)而不更改中间每个线程观察到的帐户余额。