分布式系统：通常由异步网络连接的多个节点构成，每个节点有独立的计算和存储，节点之间通过网络通信进行协作
共识 Consensus
分布式系统中多个节点之间，彼此对某个状态达成一致结果的过程
虽然共识 （Consensus） 和一致性 （Consistency） 在很多应用场景中被认为是近似等价的， 但二者涵义存在着细微的差别：
- 一致性描述结果：侧重于节点共识过程最终达成的稳定状态
- 共识描述过程：侧重于达成一致性的方法与过程
由于翻译的关系，很多中文资料把 Consensus 翻译为一致性，导致概念混淆。所以，分布式一致性算法的说法是错误的，正确的名称应该是分布式共识算法。
共识达成条件
诚实节点是符合我们期望的节点行为的节点，与之相反的是恶意节点
- 可终止性（Termination）：诚实节点必须在有限时间内能达成共识
- 约同性（Agreement）：所有诚实节点最终完成决策的结果是相同的
- 合法性（Validity）：决策的结果必须是某个诚实节点提出的提案
一致性 Consistency
一致性要求的是一致，并不是正确，如果所有节点一致给出一个”错误“的答案，那也叫一致性
Strong consistency
– ensures that only consistent state can be seen.
* All replicas return the same value when queried for the attribute of an object * All replicas return the same value when queried for the attribute of an object. This may be achieved at a cost – high latency.
Weak consistency
– for when the “fast access” requirement dominates.
* update some replica, e.g. the closest or some designated replica
* the updated replica sends up date messages to all other replicas.
* different replicas can return different values for the queried attribute of the object the value should be returned, or “not known”, with a timestamp
* in the long term all updates must propagate to all replicas …….
--- Consistency in Distributed Systems- 强一致性：某个数据被成功更新后，后续任何对该数据的读取操作都将得到更新后的值。需要在响应延时上妥协。
- 弱一致性：某个数据被更新后，后续对该数据的读取操作可能是更改前的值。但经过一段时间后，后续对该数据的读取都是更新后的值。
- 从强到弱：线性一致性 > 顺序一致性 > 因果一致性 > 最终一致性
线性一致性
对于任何一个数据对象来说，系统表现得就像它只有一个副本一样
- 任何一次读都能读取到某个数据最近的一次写的数据。
- 所有进程看到的操作顺序都跟全局时钟下的顺序一致。
- 所有进程都按照全局时钟的时间戳来区分事件的先后，那么必然所有进程看到的数据读写操作顺序一定是一样的。
顺序一致性
所有的进程以相同的顺序看到所有的修改。读操作未必能获取到最新的值，但是每个进程读到的该数据的不同值的顺序是一致的。
- 任何一次读写操作都是按照某种特定的顺序。
- 所有进程看到的读写操作顺序都保持一致。
- 所有进程读写操作执行顺序不一定一致。
因果一致性
有因果关系的操作顺序是一致的，没有因果关系的操作顺序是随机的。
- 所有进程必须以相同的顺序看到具有因果关系的读写操作。
- 不同进程可以以不同的顺序看到并发的读写操作。
最终一致性
- 所有进程最终读取到的结果是一致的
- 最终必须在有限时间内发生
FLP 不可能定理
在异步系统中，设计一个始终能够达成一致的共识算法是不可能的！
在网络可靠并且存在节点失效（即便只有一个）的异步模型系统中，不存在一种完美的共识算法可以正确地终止（使所有节点达成一致）
In this paper, we show the surprising result that no completely asynchronous consensus protocol can tolerate even a single unannounced process death. We do not consider Byzantine failures, and we assume that the message system is reliable it delivers all messages correctly and exactly once.
论文 -> Impossibility of Distributed Consensuswith One Faulty Process假设理想环境：
- 系统中不存在拜占庭错误，即没有恶意节点
- 消息传递可靠，能正确且只需一次的传递任何消息
- 消息传递延迟未知，但最终都会成功
如果在理想环境下都无法保证共识算法的终止性，那现实中更不可能保证。
因此，如果不对通信模型做进一步的假设，或者对容错类型做更大的限制，那么该问题就不存在一个完美的解决方案。
