Paxos made simplesuperhusternavylq@163.com第1 节引言大 家 都 觉 得 分 布 式 容 错 算 法Paxos 很 难 理 解 ， 可 能 是 因 为 最 初 的 描 述 太 古 怪 了 。 实 际 上 ， 它 是 最 简单 、 最 显 而 易 见 的 分 布 式 算 法 （囧）， 核心是 一个 synod 算 法 。 下面一节将说明这个一致性算 法 满足我们希望满足的 一致性属性。 最 后一节介绍完整的Paxos 算 法 ， 通过一个简 单 应用的 状态机方法 构建一个分 布 式 系统， 这种方法 应该大 家 都 知道， 因 为 这可 能 是 分 布 式 理 论中引用最 多的 方向。第2 节一致性算法2.1问题假设一系列过程（processes）会发起一些值。 一致性算 法 保证每次都 只从提交的 值中选中一个值。 如果没有提交任何值， 则不选中任何值。 如果选中了 一个值， 那么这些过程既可 获悉到这些值， 一致性的安全需求有：• 只被提交的 值才能 被选中• 只选中一个值， 且• 任何过程都 获悉不到这个值， 直到这个值被选中我们并不需要指定精确的 活性要求。 因 为 目的 是 某个被提出的 值最 终被选中， 并且如果选中了 一个值， 那么过程应该最 终能 够获悉这个值。一致性算 法 中有三个角色：发起者， 接收者和学习者。 在实 际 的 应用中， 一个过程可 能 扮演超过一个角色， 但角色到过程的 映射我们并不用关注。假设角色之间可 以通过传递消息来通信。 我们使用常用的 异步、 无拜占庭问题方式 ， 其中：• 角色以任意速度执行， 可 能 失效， 也可 能 会重启。 因 为 所有的 角色在一个值被选中后全部挂掉然后又重启， 因 此过程应该能 够持久化地存储值才能 避免这种情况。• 通信的 消息可 能 花费任意长时间传递， 可 能 被复制， 也可 能 丢掉了 ， 但不会被破坏（如果被破坏了就是 拜占庭问题了 ）。12 .2选 中 一 个值选取一个值最简单的方法就是只有一个接收者角色。发起者向接收者发送请求，接收者选中收到的第一个请求的值。这个方法虽然很简单，但因为存在单点故障而不满足需求。所以当有多个接收者时，我们想想有没有其他选中一个值的方法。一个发起者发送值给一些接收者，接收者可能会接受这个值，当只有足够大集合的接收者都接受了这个值，可以认为这个值被选中。但这个集合为多大才合适呢？...
