顺序一致但不可线性化的执行
顺序一致但不可线性化的执行
提问于 2016-12-09 19:59:23
我正在尝试理解可线性化和顺序一致性之间的区别。更具体地说，我希望有一个顺序一致但不可线性化的执行示例。我的教授给了我这样一个执行的例子：
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，这是一个一致的值，所以可能我没有正确地得到“线性化”的定义。
回答 1
Stack Overflow用户
发布于 2019-07-25 16:55:08
首先，你的教授给你的不是明确的历史/执行，而是历史在两个线程上的投影。
历史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切换的行的任何组合)，您不能按顺序重新排序(即，一起启动/完成的对)，而不更改每个线程在两者之间观察到的帐户余额。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/41060005
复制相关文章
相似问题
腾讯云开发者
