type
status
date
slug
summary
tags
category
icon
password
*uniform有均匀的意思
Concept
Basic concept
- A group of n processes, among which some (usually f) may crash（可能出错）
- 只需要正确结点要达成一致
- 每个结点都可以提议，但是最终会decide
Consensus
Termination - 终止：最终一定要决定结果
Validity - 有效性 一个v如果被决定，一定有进程提议过v
Integrity - 完整性 没有进程重复决定
Agreement - 同意 没有两个正确进程决定的不同
Uniform consensus
Uniform Agreement - 均匀同意：只要决定了就都是相同的
Consensus Algorithms using failure detectors
Algorithm I
每一轮中该轮对应的leader决定，有两个事件一定有一个发生
当目前round的leader为自己，且提议不为空，则广播
收到了message
p2收到propose后更新轮数，成为本次的leader，同时由于1比2小，更新自己的propose
算法保证正确结点一致
Uniform consensus
只要决定了的结点（无论是否正确）都统一
Algorithm II
算法2: 只能在N轮之后才能decide
在每轮中进程将提议发送给所有进程，提议更新算法：只要受到了一个提议而且比现在的提议更近就采纳
如果已经过了n轮则decide，否则下一轮
Total Order Broadcast全序广播
不是基于轮数的广播 → 连续共识 考察消息的顺序
causal order中仍然存在乱序（半序广播）
只考察了m1和m2的关系
在全序中可能不遵循因果序，但是各个节点提交的顺序一致
TOB5 - 全序性质
维护unordered集合，如果unordered集合不为空则开始排序
Paxos
如果没有quorum的话，会出现脑裂问题
同时如果有多个proposals，可能没有共识
使用Quorum和Eventually perfect Failure Detector来实现，通过选取一个主节点来达成共识，轮流成为主节点，直到达成共识
假设中为partial sync：delta最终满足，但是可能波动
菱形P是最终完美错误检测器，有强完整（节点出故障最终一定会被发现）和最终正确（最终不会有正确的进程被怀疑）
考虑到正确进程可能部分被怀疑，因此共识算法I和II的轮数检测是无法推进的
Algorithm III
轮数选择：模n算法
选出一个leader，只要leader没有被怀疑，就会带领节点共识
pi首先选择潜在的共识结果，然后选择一个值引入到大多数，如果没有被怀疑，就进入decide
*如果第一轮没有潜在的结果，就用自己的
step1先了解共识结果，step2再引入，没有怀疑就decide，这样是一个round
如果此时是我的轮，而且我手里没有潜在共识结果，那我read一下看
收到read消息后给人家返回一个潜在的结果，在states里面存储每一个结点的信息，当存储的信息量超过majority时（已经超过半数回复了gather）
此时leader要检查，如果有est和estrnd已经不是初始值，则选出estrnd最高的值作为这次的推荐值，然后广播一个impose消息（如果都是初始值，就广播本地的值
如果收到了impose就返还一个ACK，ACK超过半数的时候就达成共识，决定
如果是p的轮但它被怀疑，就广播一个NACK，如果有一个节点发送了NACK，所有节点最终都会收到，并且进入下一轮
消息模式：
*Agreement：使用round最高的作为新的共识
*复杂度：
两次通信 - read + impose，同时会有NACK（每个节点要发到N个节点，共f个节点）
FLP不可能定理：
一个异步的确定性共识，当n≥2时是不可能的（C3是最终同步的，不适用这个定理）
然而使用错误检测/同步，没有错误，使用随机机制等方式可以绕过FLP
共识3 → Synod → Paxos（完整的全序广播）
Paxos
在过程中使用Synod
- Author:faii
- URL:https://www.faii.top/article/37757e34-1e98-42e7-a916-162f7c2a56a3
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!
Relate Posts