# 超越不可能

## Consensus

• 终止性（Liveness）：所有正确进程最后都能完成决定。
• 协定性（Safety）：所有正确进程决定相同的值。
• 完整性（Integrity）：如果正确的进程都提议同一个值，那么所有正确进程最终决定该值。

## FLP不可能性

• Initial Bivalency Lemma (Lemma 2): Any algorithm that solves the 1-crash consensus has an initial bivalent configuration
• Bivalency Preservation Lemma (Lemma 3): Given any bivalent config $$\gamma$$ and any event $$e$$ applicable, There exists a reachable config $$\delta$$ where $$e$$ is applicable, and $$e(\delta)$$ is bivalent ($$\delta=\gamma$$ possible)

FLP不可能性提出后，人们不再尝试寻找异步模型中共识问题完全正确的解法，而是对于提出的共识算法，分析其在异步模型中能够解决的部分。

## Failure Detectors

Completeness:

• Strong: Eventually every process that crashes is permanently suspected by every correct process.
• Weak: Eventually every process that crashes is permanently suspected by some correct process.

Accuracy:

• Strong: No process is suspected before it crashes.
• Weak: Some correct process is never suspected.
• Eventual strong: There is a time after which correct processes are not suspected by any correct process.
• Eventual weak: There is a time after which some correct process is never suspected by any correct process.

## 参考资料

[1] Fischer M J, Lynch N A, Paterson M S. Impossibility of distributed consensus with one faulty process[R]. Massachusetts Inst of Tech Cambridge lab for Computer Science, 1982.

[2] Guerraoui R, Schiper A. Consensus: the big misunderstanding [distributed fault tolerant systems][C]//Proceedings of the Sixth IEEE Computer Society Workshop on Future Trends of Distributed Computing Systems. IEEE, 1997: 183-188.

[3] Chandra T D, Toueg S. Unreliable failure detectors for reliable distributed systems[J]. Journal of the ACM (JACM), 1996, 43(2): 225-267.