ACM通信
给编辑的信
计算机科学系
图片来源:Getty Images
2022年1月主编的专栏“全球计算社区是否不可逆转地分裂了?”提出了一个重要的问题。从计算的角度来看，很难尝试一个完整的答案，更不用说解决方案，因为该专栏也与政治科学有关;更准确地说，是国际关系的子领域。
然而，在计算文献中有一个划分，这不是不可逆转的。并行计算和分布式计算的加速定律和模型仅仅被理论出版物忽略，而被工程出版物广泛依赖。例如，在一篇极具影响力的论文中，希尔和马蒂被1700多人引用1依靠Amdahl定律提出非对称(异构)芯片多处理器架构。阿姆达尔定律是在1969年提出的，它对无限多个处理器的加速施加恒定的上限。
从那时起，超过6800篇工程论文依赖或引用了阿姆达尔定律。在同一时期内，许多理论论文也证明了多项式数量处理器的多项式加速2但他们中没有一个人提到阿姆达尔定律，更不用说试图澄清这一矛盾了。这本杂志可以帮助克服这种巨大的分歧，特别是因为它促成了这种分歧。
首批戈登·贝尔奖得主的实验结果已经与安达尔定律相矛盾。然而，在1988年5月通信古斯塔夫森在《重新评价阿姆达尔定律》一文中不当地声称，阿姆达尔的模型假设问题规模固定，并提出了一个基于固定时间的新加速模型。因此，Amdahl的模型仍然被广泛接受为固定尺寸模型，而Gustafson的模型被接受为固定时间加速模型。
不幸的是，Amdahl和Gustafson的模型都是错误的。即使我们解决了问题的大小，加速也会随着处理器数量的增加而增加。2016年Gordon Bell奖得主报告的67%的高效强缩放结果与Amdahl定律相矛盾，即使是固定尺寸加速定律。古斯塔夫森定律与已有的理论结果相矛盾。
由于戈登·贝尔奖是ACM颁发的奖项，因此ACM内部也有一个部门。克服这种分歧的最好办法是澄清安达尔定律和戈登·贝尔奖之间的矛盾。
费伦茨Devai,伦敦,英国
作者的回应:
统计学家乔治·博克斯说:“基本上，所有的模型都是错误的，但有些是有用的。”阿姆达尔定律，我们的扩展，1和古斯塔夫森定律是复杂现实的模型。只有现实是正确的，但往往提供很少的洞察力。模型从来都不是完全正确的，应该根据其误差和洞察力的平衡来进行判断。把这些模型称为“定律”是不幸的——就像摩尔和牛顿那样——但很难改变。
Amdahl的“模型”和我们的扩展是错误的，因为计算不是完全串行的或线程级并行的(向量化在哪里?)，串行部分很少是固定的。然而，我们扩展了Amdahl关于串行计算如何以不同方式限制同质、异构和动态多核系统的总体性能的见解。许多人发现这一点很有价值。
马克·d·希尔，麦迪逊，威斯康星州，美国
保持冷静
在进程故障、网络不可靠和异步通信存在的情况下，分布式一致性是一个困难的问题(《保持冷静:当分布式一致性很容易》，2020年9月)。困难来自于以不可预测的方式协调多个独立过程。诸如FLP不可能结果和CAP定理等否定的结果帮助我们认识到在特定的系统中我们不能做什么。另一方面，CALM定理为构建不需要(或只需要极少的)协调就能实现一致性的系统铺平了道路。CALM定理是一个积极的结果，它潜在地使工程师在面对不可能的结果时不放弃，相反，试图找到一种方法(或制造一种方法)来构建一致的系统，而不需要承担全面协调的负担。有两个关于CALM文章的讨论可能会受益于澄清:quorum的作用和分区下可用性的可能性。
在两种情况下，文章指出协调需要所有机器参与行动。这给人一种印象，即只有在所有机器都知道彼此的当前状态时，才可能进行全面协调。然而，采用共识算法的容错系统表明，通常情况下，在分布式环境中，机器的法定人数足以达成任意协议。一个重要的问题是足够解决这个问题的法定人数的大小。某些优化还可以产生更小的quorum，从而减少协调成本。好奇的读者可能还会说，quorum的大小取决于系统中故障的类型。例如，如果机器不可靠，但网络基础设施能够进行原子广播等复杂的操作，那么在不要求所有机器参与过程的情况下，协调就会变得更便宜。
文章中的观察1指出“无协调性等同于分区下的可用性。”这一观察提出了以下问题:在分区下是否所有无协调的问题都可用，反之亦然?文章指出“一个无协调的程序根据定义在分区下是可用的。”如果手头的问题可以简化为一个更简单的问题，这是正确的。例如，考虑分布式死锁检测的问题。如果问题是机器是否观察到死锁，那么答案很简单，不需要协调。但是，如果问题是确定给定事务的死锁，那么问题就会变得困难得多。
CALM定理是一个有趣的结果，它通过提醒工程师，如果手头的问题允许，他们不必屈服于不可能的结果，从而发挥出工程师的最好能力。CALM还比单纯的优化更进一步，它向我们展示了如果我们能够灵活地处理问题，那么我们就可以享受构建一致的系统而不需要过程的全面协调，这是非常有价值的。我们希望这些讨论将阐明这一主题并使人们参与进来通信通过创造新的讨论来阅读读者。
莫森·沙里夫伊朗的德黑兰和Amirhossein Sayyadabdi,伊斯法罕,伊朗
作者的回应:
谢谢你提出这些有趣的问题。你提到了两个:quorum和CALM之间的潜在关系，以及文章中关于CALM定理中的无协调性和CAP定理中的可用性之间的等价性的担忧。
关于第一点，在许多分布式协议协议中确实使用了法定人数，但本文没有提及。注意，仲裁一致性只在全局意义上有帮助，如果它使非仲裁成员与仲裁决策保持一致。(一言以蔽之，如果少数人不遵守，“多数原则”是没有用的!)为了说明这一点，请考虑本文中的非单调示例—分布式垃圾收集—它在指针图中查找与根没有连接的对象。节点仲裁可能只包含所有对象的一个子集，并带有指向其他节点中的对象的传出指针。仲裁在原则上可以声明它们实际上没有存储的任何对象都是“垃圾”，但这样做会破坏垃圾收集器的典型语义，从而导致程序崩溃。
这说明了仲裁足以保证分布式协议，但协议本身并不能提供一致性——需要某种补偿动作使非仲裁节点与仲裁保持一致。分布式系统中有补偿(“反向”、“道歉”)的悠久传统，考虑如何在与CALM结果相关的情况下对它们进行正式建模是很有趣的。
关于您关于无协调性和可用性的第二点，讨论需要谨慎。实际上，您对本文中的死锁示例进行了两个更改:一个是局限于给定事务视角的问题的变体，另一个是使用“是否”存在死锁的措辞。在第一点上，您提出查询“如果事务T处于死锁则报告”(也就是说，节点T出现在等待图中的一个循环中)。这就像论文中最初的例子一样，是单调和无协调的:一旦确定了一个肯定的答案，额外的信息将不会改变结果。将透视图更改为单个事务并不会使程序变得非单调。关于第二点，你用“是否”这个词实际上使讨论复杂化了不信。”查询“如果事务T是”则报告不“死锁”(即没有循环通过T)确实是非单调的:一个肯定的答案可以被额外的信息反驳，因此需要协调以确保没有这样的信息出现。因此“whether or not”确实更难——“or not”方面是非单调的。回到更大的一点，单调程序(“whether”)可以在划分过程中得出结论，而非单调问题(“或否”)不能。
但是，在可用性的背景下，你的框架确实阐明了CALM定理的一个重要方面:Ameloot的形式主义区分了数据依赖(影响所有分布式程序)的可能摊位要求用于协调的档位(仅影响非单调程序)。回到CAP参照系，在分区期间，单调程序可以安全地对它所观察到的数据完成任何有用的工作，而非单调服务即使它能观测到的数据也必须停止，只是以防它无法观察到的数据会使其结论无效。
约瑟夫·m·赫勒斯坦，伯克利，加州，美国，和彼得•Alvaro圣克鲁斯，加利福尼亚州，美国
参考文献
1.希尔博士和马蒂博士，多核时代的阿姆达尔定律。电脑41， 7(2008)， 33-38。
2.Roughgarden, T.等人。shuffle和电路(现代并行计算的下界)。J. acm 65第41条(2018年11月)。
©2022 acm 0001-0782/22/3
允许为个人或课堂使用部分或全部作品制作数字或硬拷贝，但不得为盈利或商业利益而复制或分发，且副本在首页上附有本通知和完整的引用。除ACM外，本作品的其他组件的版权必须受到尊重。允许有信用的文摘。以其他方式复制、重新发布、在服务器上发布或重新分发到列表，都需要事先获得特定的许可和/或费用。请求发布的权限permissions@acm.org传真(212)869-0481。
数字图书馆是由计算机协会出版的。版权所有©2022 ACM, Inc.
没有找到条目