对于每篇论文，你的作业有两部分。在讨论论文的课开始之前：
将你的答案放在 a.txt 中，问题放在 q.txt 中。 通过 Gradescope 提交这两个文件。
GFS 论文是一篇"经典"论文，描述了最早面向数据中心应用（如大规模 MapReduce 作业）的分布式文件系统之一。它涉及 6.5840 的许多主题：并行 性能、容错、复制和一致性。它是一篇优秀的系统论文，涵盖了从应用到网络 的各个层面的细节。
GFS 已被一个名为 Colossus 的系统所取代，总体目标相同，但在主节点性能和容错方面有所改进。此外，Google 内部的许多应用已经 转向更类似数据库的存储系统，如 BigTable 和 Spanner。然而，GFS 的大部分设计在 HDFS（Hadoop 开源 MapReduce 的存储系统）中得以延续。
问题： 描述一个事件序列，使得客户端从 Google 文件系统 中读取到过时的数据。
VM FT 如何处理网络分区？也就是说，如果主节点和备份节点分别处于不同的网络分区中，备份节点是否也会成为主节点，导致系统同时运行两个主节点？
考虑以下来自"不正确同步"示例的代码：
var a string
var done bool
func setup() {
a = "hello, world"
done = true
}
func main() {
go setup()
for !done {
}
print(a)
}
使用你选择的同步机制，修复这段代码，使其根据 Go 语言规范保证具有预期行为。用 happens-before 关系解释你的修改为何有效。
Paxos Made Simple 假设接受者是 A、B 和 C。A 和 B 同时也是提议者。 Paxos 如何确保以下事件序列不会发生？ 实际会发生什么，最终选择哪个值？
Raft 论文描述了一种共识算法，包括构建复制状态机应用所需的许多细节。该论文也是 6.5840 多个实验的主题。重要章节为 2、5、7 和 8。
该论文将自己定位为更好的 Paxos，但另一种看待 Raft 的方式是它解决了比 Paxos 更大的问题。要构建真实世界的复制服务，副本需要就无限序列的值（客户端命令）达成一致，并且需要高效的方式在服务器崩溃重启或丢失消息时进行恢复。人们已经以 Paxos 为起点构建了这样的系统（例如，Google 的 Chubby 和 Paxos Made Live 论文，以及 ZooKeeper/ZAB）。还有一个名为 Viewstamped Replication 的协议；它是一个很好的设计，与 Raft 类似，但相关论文难以理解。
这些真实世界的协议很复杂，而且在 Raft 之前没有一篇好的入门论文描述它们的工作原理。相比之下，Raft 论文相对容易阅读且相当详细。
问题： 假设我们有 Raft 论文图 7 所示的场景：一个包含七台服务器的集群，日志内容如图所示。第一台服务器（图中顶部的服务器）崩溃，无法联系。随后进行领导者选举。对于标记为 (a)、(d) 和 (f) 的服务器，它们能否被选为领导者？如果能，哪些服务器会给它投票？如果不能，哪些具体的 Raft 机制会阻止它被选中？
今天的课程涵盖了调试 6.5840 实验的有效方法。 提交一个关于你实验 1 方案的测试和调试过程的问题：例如，你遇到的困难、你不确定的地方，或者你好奇的内容。
接收到的 InstallSnapshot RPC 是否会导致状态机回退到过去的时间点？也就是说，图 13 中的步骤 8 是否会导致状态机被重置，使其反映的已执行操作更少？如果是，解释这是如何发生的。如果不是，解释为什么不会发生。
请阅读论文的附录。在 Spinnaker 中，领导者在领导者和一个跟随者将请求的日志记录写入持久存储后就响应客户端请求。为什么这足以保证即使在领导者或该跟随者故障后仍具有强一致性？
（本论文依赖于 Zookeeper，我们将在后面阅读。）
今天的课程是关于实验 3A/3B 的问答环节。 提交一个关于该实验的问题：例如，你在做实验时疑惑的事情、你不理解的地方、一个令人印象深刻的 bug，或者任何内容。
在一个可线性化的键值存储系统中，两个客户端同时对同一个键发出 get() 请求，能否收到不同的值？解释为什么不能，或者说明这是如何发生的。
Zookeeper 的一个用途是作为容错的锁服务（参见第 6 页"Simple locks"部分）。为什么两个客户端不可能获取同一把锁？特别是，Zookeeper 如何判断一个客户端已经故障，从而可以将该客户端的锁分配给其他客户端？
第 2.3 节的第 4 项指出，如果客户端读请求到达时最新版本是脏的，节点应该向尾部节点请求最新的已提交版本。假设节点改为用其最近的干净版本进行响应（忽略任何脏版本，不向尾部节点发送版本查询）。这种改变将使读取反映节点所知的最近已提交写入。解释这如何导致违反可线性化性——或违反论文强一致性的目标。
假设链式复制在下一个链服务器确认收到转发的更新后立即从头节点响应更新请求，而不是从尾部节点响应。解释这如何导致链式复制产生不可线性化的结果。
第 4.1 节第二段说"数据库维护的运行时状态使我们能够使用单段读取而非仲裁读取……"数据库需要维护什么运行时状态才能避免需要从仲裁中读取？
Russ Cox 是 Go 项目的负责人之一。你最喜欢 Go 的什么？为什么？你想改变这门语言中的什么？如果是，改什么，为什么？
6.033 教材。 只阅读第 9 章的以下部分：9.1.5、9.1.6、9.5.2、9.5.3、9.6.3。最后两节（关于两阶段锁和分布式两阶段提交）最为重要。 问题：描述一个两阶段锁比简单锁产生更高性能的情况。
Spanner 假设 Spanner 服务器的 TT.now() 返回正确的信息，但不确定性很大。例如，假设绝对时间是 10:15:30，TT.now() 返回区间 [10:15:20,10:15:40]。该区间是正确的，因为它包含了绝对时间，但误差范围是 10 秒。参见第 3 节了解 TT.now() 的解释。大的误差范围会对 Spanner 的运行产生什么不良影响？给出一个具体的例子。
在第 6.2 节末尾，Chardonnay 论文说快照读事务可以通过等待 epoch 前进一个来使其可线性化。论文所说的"可线性化"是指事务能观察到在它开始之前完成的所有事务的结果。为什么等待能使事务可线性化？
No compromises: distributed transactions with consistency, availability, and performance：假设有两个 FaRM 事务都对同一个对象执行递增操作。它们同时启动并看到相同的对象初始值。一个事务完全完成了提交（参见第 4 节和图 4）。然后第二个事务开始提交。没有故障发生。FaRM 会使用什么证据来意识到它必须中止第二个事务？在第 4 节/图 4 协议的哪个阶段 FaRM 会意识到必须中止？
Amazon DynamoDB: A scalable, predictably performant, and fully managed NoSQL Database service 为了避免干扰，如果客户的读写操作超过其容量，DynamoDB 可能会限制客户应用的流量，这可能导致应用不可用。DynamoDB 如何避免数据库表的单个热点分区导致应用不可用？
Distributed Transactions at Scale in Amazon DynamoDB。 第 3.3 节第三个要点说："事务的时间戳大于项目的时间戳，表明其最后一次写入的时间。"这个检查有助于排除什么样的错误结果的例子？
MDCC 今年的问题稍后公布。
Ownership: A Distributed Futures System for Fine-Grained Tasks。 如果图 6(a) 中的 C() 如下所示：
def C(x):
z = D(X)
return Get(z) # return value of future z
假设运行 D 的节点在完成之前故障，哪个节点会发起 D() 的重新执行？
Resilient Distributed Datasets: A Fault-Tolerant Abstraction for In-Memory Cluster Computing Spark 能很好地支持哪些 MapReduce/Hadoop 无法支持的应用？
Naiad: A Timely Dataflow System：
考虑图 3 中的数据流图，假设顶点按如下方式实例化：
现在假设我们在 In 顶点引入两条记录，在 epoch e = 1 时：(a, 2) 和 (b, 6)；在 e = 2 时：(a, 5)。
写出记录在流经图时经历的时间戳变化，例如 (a, 2): at A, t = (1, []); at B, t = ...。你可以省略不修改时间戳的顶点。
非正式地解释 E.OnNotify((1, [])) 何时会被调用。你不需要逐步说明 pointstamp 协议的细节。
Parameter Server： 参数服务器模型是为运行稀疏逻辑回归等机器学习算法而开发的（§ 5.1）。
你预计 workers 和 servers 的瓶颈（即负载最重的）资源（如 CPU、内存、网络）分别是什么？
如果在 §5.1 的实验中使用 Spark 的逻辑回归（参见 Spark 论文 §3.2.1）而不是参数服务器，你可能会观察到什么样的资源利用率？
Frangipani: A Scalable Distributed File System：假设一台服务器修改了一个 i 节点，将修改追加到其日志中，然后另一台服务器修改了同一个 i 节点，接着第一台服务器崩溃。恢复系统将在崩溃服务器的日志中看到 i 节点的修改，但不应将该日志条目应用到 i 节点，因为那样会撤销第二台服务器的更改。Frangipani 如何避免或应对这种情况？
Memcache at Facebook。 第 3.3 节暗示，写入数据的客户端不会从 Gutter 服务器中删除相应的键，即使客户端确实尝试从普通 Memcached 服务器中删除该键（图 1）。解释为什么写入客户端从 Gutter 服务器删除键是一个坏主意。
COPS。第 4.3 节最后一句话说，客户端在 put 之后清除其上下文，用该 put 替换上下文。文中指出"这个 put 依赖于之前所有的键-版本对，因此比它们更近。"为什么清除上下文并仅用该 put 替换是合理的？你可能认为客户端后续的 put 需要携带之前 get 的依赖信息。什么实体最终使用上下文信息，为什么它不需要最后一次 put 之前的 get 信息？
解释为什么所有查看 Certificate Transparency 日志的人看到相同的内容很重要。如果一个恶意日志服务器能够使部分读者看到一组记录序列，而其他读者看到另一组记录，那么可能进行什么攻击？什么机制确保所有查看者看到相同的日志内容？
为什么 Blockstack 的名称需要唯一、可读且去中心化？为什么同时提供这三个属性很困难？
Managing Update Conflicts in Bayou 假设我们使用 Bayou 构建一个分布式文件系统，该系统有一个复制操作。初始时，文件 A 包含 "foo"，文件 B 包含 "bar"。在一个节点上，用户将文件 A 复制到文件 B，覆盖了 B 的旧内容。在另一个节点上，用户将文件 B 复制到文件 A。在两个操作都提交后，我们希望两个文件都包含 "foo" 或者都包含 "bar"。为复制操作设计一个依赖检查和合并过程来实现这一点。Bayou 如何确保所有节点就 A 和 B 包含 "foo" 还是 "bar" 达成一致？
对于 Chord: a scalable peer-to-peer lookup service for Internet applications 中描述的设计，如果两个 Chord 节点 x 和 y 在互联网上彼此靠近（例如，它们都在同一个数据中心），当 x 查找存储在节点 y 上的键时，Chord 跳数是否很少（比如 1 或 2 而不是 log N）？
Dynamo 假设 Dynamo 服务器 S1 完全健康且网络连接正常。由于疏忽，管理员指示服务器 S2 使用 4.8.1 和 4.9 节中描述的机制移除 S1。成员变更从 S2 传播到系统其余部分（包括 S1）需要一段时间，因此在一段时间内，一些客户端和服务器会认为 S1 仍然是系统的一部分。Dynamo 在这种情况下能否正常运行？为什么？
Zanzibar 论文在第 4 节第四段中说，Zanzibar 总共服务大约每秒 1000 万个客户端请求。第 4.4 节说 aclservers 每秒执行大约 2 亿次内存查找。数量级差异的原因可能是什么？
论文在第 5.1 节提到解密增加了获取数据块的延迟。为什么首先要使用收敛加密来加密数据块？
Boki 确保函数看起来只执行一次，即使由于机器故障函数可能被重新执行。一个挑战是，如果函数更新了外部数据库（例如，更新 DynamoDB 中的一行），这个更新必须只发生一次。Boki 在图 6(a) 中如何实现这一目标？
Secure Untrusted Data Repository (SUNDR)。你只需要读到 3.3.2 节末尾。在简单的草率方案中，fetch 和 modify 操作都被放入日志并签名。假设一种替代设计只对 modify 操作进行签名和记录。这是否允许恶意服务器破坏 fetch-modify 一致性或 fork 一致性？为什么？
假设我们从 Practical BFT 协议中消除了 pre-prepare 阶段。相反，主节点向副本多播 PREPARE,v,n,m 消息，副本多播 COMMIT 消息并像之前一样回复客户端。这个协议可能出什么问题？给出一个简短的例子，例如"主节点发送 foo，副本 1 和 2 回复 bar……"
Bitcoin 尝试用 Bitcoin 买东西。与一些 6.5840 的同学合作可能会有帮助，提前几天开始也会有帮助。如果你决定放弃，那也没关系。简要描述你的经历。
Ethereum Whitepaper。 使用一个以太坊去中心化应用（dapp）并向智能合约发送一笔交易。
如果你决定放弃，那也没关系。简要描述你的经历。
IronFleet：考虑一个 Raft 实现（用 Dafny 编写），它没有实现论文的选举限制（即跟随者在投票时不检查候选者的日志是否是最新的）。在将 IronFleet 方法论应用于此实现时，开发者可能在图 3 的哪个位置卡住？
Experiences with a Distributed, Scalable, Methodological File System: AnalogicFS。在许多方面，这篇经验论文提出的问题比回答的更多。请回答以下问题之一，并考虑 AnalogicFS 的丰富历史和论文写作的精神：
a) 图 1 所示的 A* 搜索分析声称是 AnalogicFS 方法论的内省可视化；然而，并非所有决策都在图中描绘。特别是，如果 I <= P，应该探索的下一个节点是什么，使得第 2 节中的所有假设仍然成立？展示你的推导过程。
b) 尽管作者在引言中声称 AnalogicFS 是为了研究 SCSI 磁盘（及其与 lambda 演算的交互）而开发的，但第 4.1 节中详述的实验设置涉及的是退役的 Gameboy，它们使用基于卡带的类 Flash 存储器。如果作者在实验中使用了实际的 SCSI 磁盘，他们的结果在数量上会如何变化？
c) AnalogicFS 显示了相当不稳定的多播算法流行度（图 5），特别是与我们在 6.5840 中阅读的一些先前系统相比。给出另一个系统的例子，它会有更稳定的流行度页面测量，特别是在 0.1-0.4 分贝带宽范围内。
d) 作为他的 6.5840 项目，Ben Bitdiddle 选择构建实验 5 的一个变体，忠实模拟 LISP 机器上的恒定预期寻道时间，就像 AnalogicFS 那样。然而在实现时，他立即遇到了需要将值大小限制为 400 nm 而不是 676 nm 的问题。解释为 AnalogicFS 实现所做的哪些假设对实验 5 不成立，以及为什么这会改变最大值大小。
如有关于 6.5840 的问题或意见，请发送邮件至 6824-staff@lists.csail.mit.edu。