Table of Contents
Algorithm
Leetcode 659: https://leetcode.com/problems/split-array-into-consecutive-subsequences/
https://medium.com/@dreamume/leetcode-659-split-array-into-consecutive-subsequences-a2828703cd4b
Review
Consensus Protocols: Three-phase Commit
https://www.the-paper-trail.org/post/2008-11-29-consensus-protocols-three-phase-commit/
之前我们谈到的两阶段提交算法具有低延迟的优点，但它不能允许参与者发生故障。今天我们介绍三阶段提交算法能改善这点，但代价是更高的延迟。
两阶段提交的难点是一旦协调者做出的决定去提交，联系部分节点，这些节点则也会提交但不会检查其他所有节点是否都收到该消息。如果有节点提交期间崩溃，系统无法知道该节点提交的结果（因为只有协调者和该节点有消息通信）。因为交易可能已经在崩溃节点提交，协议无法取消，因为交易可能有附加影响不能被undo。同样，协议也不能强制提交，因为原始的投票可能已经被取消。
通过在两阶段提交协议上再追加一个阶段，可以解决以上问题。想法非常简单，我们把第二阶段的提交分成两个阶段。前一阶段叫准备提交阶段，协调者发送消息到所有之前投票赞成的节点，当收到该消息后，节点进入准备提交状态，并确保一些影响undo的行为不被执行，然后节点回复协调者告知准备提交的消息已收到。
这一阶段的目的就是通信每个节点的投票结果以便协议在节点崩溃的情形下也能够恢复。
后一阶段跟两阶段提交的最后阶段一致。如果协调者收到所有节点准备提交的消息回复，则继续提交交易将安全执行。否则，协调者不能保证协议状态能恢复（如果能够容忍f个节点故障，协调者在收到f + 1个消息确认后能正常继续）。这种情况下，协调者将取消该交易。
如果协调者崩溃，则一个恢复节点将负责该交易并查询其他节点的状态。如果一个故障节点已经提交交易，我们知道其他节点都已收到准备提交的消息（否则协调者不会进入提交阶段），因此恢复节点能确定交易能够被提交，并安全地指导协议继续完成。如果任何节点报道给恢复节点其未收到准备提交消息，恢复节点则知道交易尚未提交给任意节点，则可以取消或重新开始进行。
三阶段提交也不能解决所有情况，当网络分区时，设想分区之一的所有节点收到了准备提交消息，而另一分区则没有，所有分区的恢复节点将各自继续完成提交或取消交易，当网络分区恢复时系统将出现不一致状态。所以三阶段提交可能不安全。三阶段提交能够保证不被单节点故障阻塞，适合于高可用性比低延迟更重要的场景中。
Tips
- leetcode作为算法练习题，可以很好的考验对算法的理解度、具体细节上的优化实现、避免思路上陷入僵化的问题及锻炼解题速度。
Share
Algorithms for the Masses
https://www.cs.princeton.edu/~rs/talks/AlgsMasses.pdf
《算法》的作者Sedgewick在ANALCO’11上的演讲
里面提到了科学方法：
- 创建模型描述自然世界
- 使用模型提出假设
- 进行试验验证假设
- 提炼模型并重复以上步骤
提到了银河算法，因为太过复杂而无法在实际中使用
算法分析基于以下经典研究领域：
- 概率
- 组合
- 分析
- 信息理论
且正在发展新的模型、方法和应用
介绍了一本书：《组合分析》，是学习离散结构的现代基础。Sedgewick也是作者之一。
介绍了计算机科学，介绍了目前的情况：任何人可以学习以下的重要性：
- 现代计算模型
- 理解程序行为的科学方法
- 计算机科学的基本原则
- 各种行业领域应用程序的计算
- 从事终身的计算的准备
最后，强调了科学方法是编程的必要基础，学习计算机科学和算法课程将服务更多的学生拥抱、支持、发展科学。