选举算法paxos

Ⅰ 几种nosql的浅谈

1、性能
都比较高，性能对我们来说应该都不是瓶颈。
总体来讲，TPS 方面 redis 和 memcache 差不多，要大于 mongodb。
2、操作的便利性
memcache 数据结构单一。（key-value）
redis 丰富一些，数据操作方面，redis 更好一些，较少的网络 IO 次数，同时还提供 list，set，
hash 等数据结构的存储。
mongodb 支持丰富的数据表达，索引，最类似关系型数据库，支持的查询语言非常丰富。
3、内存空间的大小和数据量的大小
redis 在 2.0 版本后增加了自己的 VM 特性，突破物理内存的限制；可以对 key value 设置过
期时间（类似 memcache）
memcache 可以修改最大可用内存,采用 LRU 算法。Memcached 代理软件 magent，比如建立
10 台 4G 的 Memcache 集群，就相当于有了 40G。 magent -s 10.1.2.1 -s 10.1.2.2:11211 -b
10.1.2.3:14000 mongoDB 适合大数据量的存储，依赖操作系统 VM 做内存管理，吃内存也比较厉害，服务
不要和别的服务在一起。
4、可用性（单点问题）
对于单点问题，
redis，依赖客户端来实现分布式读写；主从复制时，每次从节点重新连接主节点都要依赖整
个快照,无增量复制，因性能和效率问题，
所以单点问题比较复杂；不支持自动 sharding,需要依赖程序设定一致 hash 机制。
一种替代方案是，不用 redis 本身的复制机制，采用自己做主动复制（多份存储），或者改成
增量复制的方式（需要自己实现），一致性问题和性能的权衡
Memcache 本身没有数据冗余机制，也没必要；对于故障预防，采用依赖成熟的 hash 或者环
状的算法，解决单点故障引起的抖动问题。
mongoDB 支持 master-slave,replicaset（内部采用 paxos 选举算法，自动故障恢复）,auto sharding 机制，对客户端屏蔽了故障转移和切分机制。
5、可靠性（持久化）
对于数据持久化和数据恢复，
redis 支持（快照、AOF）：依赖快照进行持久化，aof 增强了可靠性的同时，对性能有所影
响
memcache 不支持，通常用在做缓存,提升性能；
MongoDB 从 1.8 版本开始采用 binlog 方式支持持久化的可靠性
6、数据一致性（事务支持）
Memcache 在并发场景下，用 cas 保证一致性redis 事务支持比较弱，只能保证事务中的每个操作连续执行
mongoDB 不支持事务
7、数据分析
mongoDB 内置了数据分析的功能(maprece),其他不支持
8、应用场景
redis：数据量较小的更性能操作和运算上
memcache：用于在动态系统中减少数据库负载，提升性能;做缓存，提高性能（适合读多写
少，对于数据量比较大，可以采用 sharding）
MongoDB:主要解决海量数据的访问效率问题。
表格比较：
memcache redis 类型 内存数据库 内存数据库
数据类型 在定义 value 时就要固定数据类型 不需要
有字符串，链表，集 合和有序集合
虚拟内存 不支持 支持
过期策略 支持 支持
分布式 magent master-slave，一主一从或一主多从
存储数据安全 不支持 使用 save 存储到 mp.rdb 中
灾难恢复 不支持 append only file(aof)用于数据恢复
性能
1、类型——memcache 和 redis 都是将数据存放在内存，所以是内存数据库。当然，memcache 也可用于缓存其他东西，例如图片等等。
2、 数据类型——Memcache 在添加数据时就要指定数据的字节长度,而 redis 不需要。
3、 虚拟内存——当物理内存用完时，可以将一些很久没用到的 value 交换到磁盘。
4、 过期策略——memcache 在 set 时就指定，例如 set key1 0 0 8,即永不过期。Redis 可以通
过例如 expire 设定，例如 expire name 10。
5、 分布式——设定 memcache 集群，利用 magent 做一主多从;redis 可以做一主多从。都可
以一主一从。
6、 存储数据安全——memcache 断电就断了，数据没了；redis 可以定期 save 到磁盘。
7、 灾难恢复——memcache 同上，redis 丢了后可以通过 aof 恢复。
Memecache 端口 11211
yum -y install memcached
yum -y install php-pecl-memcache
/etc/init.d/memcached start memcached -d -p 11211 -u memcached -m 64 -c 1024 -P /var/run/memcached/memcached.pid
-d 启动一个守护进程
-p 端口
-m 分配的内存是 M
-c 最大运行并发数-P memcache 的 pid
//0 压缩（是否 MEMCACHE_COMPRESSED） 30 秒失效时间
//delete 5 是 timeout

Ⅱ Paxos怎么读，麻烦给出英文音标

Paxos读作[ˈpæksoʊs]。

Paxos

发音：[ˈpæksoʊs]

含义：Paxos（帕克索斯）算法

用法：在句子中充当主语或宾语。

例句：

The High Replication Datastore increases the number of data centers that maintain replicas of your data by using the Paxos algorithm to synchronize that data across datacenters in real time.

High Replication Datastore使用Paxos算法来实时同步跨越多个数据中心的数据，进而增加了用于维护数据复制的数据中心数量。

(2)选举算法paxos扩展阅读：

Paxos 算法的背景：

Paxos 算法解决的问题是一个分布式系统如何就某个值（决议）达成一致。一个典型的场景是，在一个分布式数据库系统中，如果各节点的初始状态一致，每个节点执行相同的操作序列，那么他们最后能得到一个一致的状态。

为保证每个节点执行相同的命令序列，需要在每一条指令上执行一个“一致性算法”以保证每个节点看到的指令一致。一个通用的一致性算法可以应用在许多场景中，是分布式计算中的重要问题。因此从20世纪80年代起对于一致性算法的研究就没有停止过。

节点通信存在两种模型：共享内存（Shared memory）和消息传递（Messages passing）。Paxos 算法就是一种基于消息传递模型的一致性算法。

Ⅲ paxos算法是什么

Paxos算法是莱斯利·兰伯特（Leslie Lamport，就是LaTeX中的＂La"，此人现在在微软研究院）于1990年提出的一种基于消息传递的一致性算法。这个算法被认为是类似算法中最有效的。

兰伯特提出的Paxos算法包含2个部分：

一个是Basic Paxos算法，描述的是多节点之间如何就某个值（提案Value）达成共识；

另一个是Multi-Paxos思想，描述的是执行多个Basic Paxos实例，就一系列值达成共识

可因为兰伯特提到的Multi-Paxos思想，缺少代码实现的必要细节（比如怎么选举领导者），所以在理解上比较难。Basic Paxos是Multi-Paxos思想的核心。

(3)选举算法paxos扩展阅读

背景

Paxos算法解决的问题是一个分布式系统如何就某个值（决议）达成一致。一个典型的场景是，在一个分布式数据库系统中，如果各节点的初始状态一致，每个节点执行相同的操作序列，那么他们最后能得到一个一致的状态。

为保证每个节点执行相同的命令序列，需要在每一条指令上执行一个“一致性算法”以保证每个节点看到的指令一致。

一个通用的一致性算法可以应用在许多场景中，是分布式计算中的重要问题。因此从20世纪80年代起对于一致性算法的研究就没有停止过。节点通信存在两种模型：共享内存（Shared memory）和消息传递（Messages passing）。Paxos算法就是一种基于消息传递模型的一致性算法。

Ⅳ 号称史上最晦涩的算法paxos，如何变得平易近人

分布式一致性算法（Consensus Algorithm）是一个分布式计算领域的基础性问题，其最基本的功能是为了在多个进程之间对某个（某些）值达成一致（强一致）；进而解决分布式系统的可用性问题（高可用）。Paxos是最重要的分布式一致性算法，很多人都把它作为“分布式一致性协议”的代名词（Mike Burrows, inventor of the Chubby service at Google, says that“there is only one consensus protocol, and that’s Paxos”）。
关于Paxos的历史和原理，已经有很多经典的论文可以参考，也有厂内外的文章有详细的描述，本文就不再重复了。感兴趣的同学可以阅读下这些论文[1,2,3,4]。

Ⅳ Paxos 算法的几种算法

上面通过证明如果一个协议满足B1-B3 约束条件，那么就可以保证一致性。直接从这些约束得到preliminary protocol ，basic protocol 是preliminary protocol 的限制版，保证了一致性。complete Synod protocol 进一步限制了basic protocol ，满足一致性和过程需求（progress requirements）。下面将这三个算法的具体过程。 满足B1，牧师发起选举的编号必须满足偏序关系，有一个方法是每个发起牧师使用递增的数值作为选举编号，但这样牧师无法立即知道他们选的数值有没有被其他牧师选作选举编号已经被使用。还有一个方法是使用数字+牧师姓名作为选举编号，这样就避免了自己的选举编号被其他牧师使用。
满足B2，每次选举的法定人数必须是一个大部分集合（majority set）Q，这样任意两个选举都会有一个共同的牧师。这里大部分集合是一个灵活的选择，在原文中Lamport 使用体重打比方，体重的人更有可能呆在议会大厅，这样就可以使用体重超过一半的牧师集合作为大部分集合。至于实际情况中的大部分集合是什么要看具体情况了。
满足B3，要求每个牧师p 每次在发起选举前必须找到B_qrm 中每个牧师q 的MaxVote(b,q,B)。
根据以上要求，可以得到初始协议：
1. 牧师p 选择一个选举编号b ，并发送NextBallot(b)送给其他牧师
2. 其他牧师q 在收到NextBallot(b) 后，返回LastVote(b,v) 给牧师p，v=MaxVote(b,q,B)$是小于b 编号的q 投的最大的赞成票。为了保证B3，q 不能在b 和b_bal 之间的选举投赞成票。（如果q 在发送了LastVote(b,v)又对新的选举投票了那么v 也就不是q 投的最大赞成票）
3. 牧师p 从一个大部分集合Q 中每个牧师q 中都收到LastVote(b,v) 后，发起一个新的选举，编号为b，法定人数为Q，法律d满足B3。然后牧师p 将这个法律写在自己账目的背面，发送BeginBallot(b,d)给Q 中每个牧师。
4. 牧师q 收到BeginBallot(b,d) 后决定是否为这次选举投赞成票，如果赞同，则他将发送Vote(b,q) 给牧师p。
5. 如果牧师p 收到Q 中每个牧师q 发来的赞成票Vote(b,q)，则将法律d 写入他的账目中，并向所有q发送Success(d) 消息。
6. 收到Success(d) 消息后，牧师q 将法律d 写入到自己的账目中。
说明：第一步表示发起法律的牧师p 希望下一个选举的编号是b 。牧师q 用LastVote(b,v) 回应了牧师p 的请求，也就是向牧师p 通过法律时保证了v=MaxVote(b,q,B) 的被改变，具体来说就是不在b 和b_bal 之间的选举投赞成票。
第三步要求法律d 需要满足B3，这里我开始有点迷糊，实际系统中的值是客户端决定的，而不应该是B3 决定的。这里我们还是用上面的key-value 数据库的例子来理清下思路：当某个节点/牧师第一次发起更新前相当于B为空集，发起更新/选举的操作不断进行，直至所有法定人数（quorum）都对法律投了赞成票（即majority set 的节点都更新了该key-value 的值则认为更新成功），B3对应的就是之前的更新没有成功，那么新的选举值需要保持的情况。第四步允许牧师可以不发送Vote(b,q) 或者发送几次，对应的是发送的信息可能因为通信而失败而未发送或者被多次发送。一旦牧师投了赞成票则确认可以修改该值。
考虑到最后第六步法律d 才被牧师q 写入到账目，有可能出现的情况就是在第五步的时候牧师p 将法律写入到了自己账目中，接着发送Success(d) 给其他牧师，其中因为通信或者牧师离开议会大厅而没有被写入到自己的账目中，导致不一致。所以真正写入到账目时机应该是在第四步牧师q 在发送给牧师p 赞成票的同时就法律写入到了各自账目中。而不用考虑如何保证牧师q 第四步写入的法律会导致不一致，因为法律如果没有通过则还有更多的选举来保证一致性。后面也谈到了当法律第一次别写入到账目中算通过法律。 初始协议（Preliminary Protocol）要求每个牧师都保存 (i) 他发起的每个选举； (ii) 他投的每个赞成票； (iii) 他发送的每个$LastVote$。为了简化牧师需要保存的数据，我们对上面的协议做一个限制，得到基础（Basic Protocol）协议。首先介绍三个新的参数：
lastTried[p] 牧师p 发起的最后一个选举
prevVote[p] 牧师p 最近一次的投票
nextBal[p] 收到的选举编号的b 的最大值，即牧师p参加的最大选举编号
在初始协议中，每个牧师可以同时发起任意个选举，在基础协议中要求每个牧师只能发起一个选举lastTried[p]，一旦发起一个选举，那么之前发起选举的信息就都不重要了。在初始协议中要求每个牧师不能在b_bal 和b 之间投赞成票，在基础协议中则更严格地要求不能给小于b 的选举投赞成票。那么基础协议可以概述为下面几步：
1. 牧师p 选择一个大于lastTried[p] 的选举编号b ，发送NextBallot(b)给其他牧师
2. 牧师q 收到NextBallot(b) 且b>nextBal[q]后设置nextBal[q]=b ，接着发送LastVote(b,v) 给牧师p，其中v==prevBa[q] 。（如果b 小于或等于nextBal[q]，则不回复）
3. 从满足某个大部分集合Q 中每个牧师收到了LastVote(b,v) 信息，牧师p 发起一个编号为b ，法定人数为Q ，法律为d（满足B3 ）的选举，并将BeginBallot(b,d) 发送给Q 中每个牧师。（如果没有满足任意大部分集合Q 的牧师返回，则返回第一步）
4. 牧师q 收到BeginBallot(b,d) ，决定投赞成票，设置prevVote[p] 为这次投票，并发送Vote(b,q) 给牧师p。（如果在收到BeginBallot(b,d) 后发现b 不等于nextBal[q] 则忽略这条信息，说明这期间牧师q 还收到了其他的编号更大的选举）
5. 牧师p 从大部分集合Q 中每个牧师q 收到了Voted(b,d) ，且b==lastTried[p] ，则认为这次选举成功，将法律d 记录在账目中，并向Q 中每个牧师q 发功成功消息Success(d) 。
6. 每个牧师q 收到Success(d) 消息后将法律写入账目。
基础协议是初始协议的限制版，因为两者都对牧师没有行为要求，所以也不保证过程（QS）。下面介绍一个保证过程的协议— 完整议会协议（complete Synode protocol）。 基础协议保证了一致性却没有保证任何过程，因为它只阐述了牧师可能做什么，没有要求牧师应该做什么。为了达到之前谈到的过程需求（Qrogress Requirements），我们需要添加一些额外的要求使得牧师们尽快执行完2-6 步。
考虑一种情况如果牧师q 第二步收到的选举编号b 都比之前收到的要大，那么他就要放弃之前收到的所有选举。可是在选举编号为b 的选举在未确认前，可能又会收到更大编号的选举b’ ，这样就无法通过任何法律，过程也不能保证。所以为了达到过程需求则需要一个选举成功后再发起另一个选举。而首先应该知道服务员传递消息和牧师处理消息的时间，在网络中常常通过设置timeout 来实现，同样的如果超过了一定时间牧师没有收到服务员的回复，则认为该服务员或者对应的牧师离开了议会大厅。
假设牧师执行一个动作在7 分钟以内，服务员传递一个消息在4 分钟以内，那么一个牧师p 发送消息给牧师q ，希望其回复的时间应该是在22 分钟内（7+4+7+4 分钟）。
有了上面时间的假设，再考虑上面讨论过的情况，如果发起选举的牧师p 会在第二步和第四步期望22 分钟内收到其他牧师的回复，如果没有则可能是一些牧师或者服务员离开了议会大厅，或者还有一些牧师发起了编号更大的选举。遇到这两种情况都牧师p 应该终止本次选举，而重新开始发起一个新的选举，为了不至于新发起的选举编号还是太小而仍不能执行，需要从其他牧师哪里获取最新的选举编号，从而选取一个更大的编号发起选举。
进而假设牧师p 是唯一能够发起选举的牧师且议会大厅内有大部分集合的牧师，那么可以保证在99分钟内通过一条法律：22 分钟内发现了有更大编号的法律，22 分钟内获取最大编号并选择个更大的编号，55 分钟内完成1-6 步完成一次成功的选举（疑问：既然只有牧师p 能够发起选举，那么编号都是由其控制的，前两步发现并选择更大的编号似乎就没有必要了。答：并不是所有的选举都是president发起的，其他牧师发起选举，president向其他希望发起选举的牧师配发选举编号）。从上面的过程我们发现完整议会协议需要一个选举president的过程，president的选举算法不是文章重点，所以文章中仅用T 分钟代替了选举president的时间，这样T+99 分钟内可以通过一部法律。
文中选择president的方法是谁的姓在字母表中最后，并将自己的姓发送给议会大厅内所有牧师，如果在T-11 分钟内某个牧师没有收到比自己姓在字母表中更靠后的姓，则认为自己是president（我觉得广播体重也应该不错，不是说体重更重的呆在议会大厅会更久么？^_^）。还有一个细节：在选举president的时候每个牧师p 需要将自己的lastTried[p] 发送给其他牧师，以使得president能够在第一次选举时选择一个足够大的编号。
至此，通过选举president和设置超时，完整议会协议就可以保证过程了。
多法律国会协议
上节的议会协议（complete Synod protocol）中，president被选举出来后，每个希望发起选举的牧师通知他，president给牧师配发选举编号，每次仅通过一部法律。多法律国会协议（The Multi-Decree Parliment）选择一个president通过一系列法律，且只需要执行前两步一次即可。
具体方法是president第一步发送NextBallot(b,n) 代替NextBallot(b) ，表示希望通过n-b 之间的所有的法律，在president 的账目上，编号n 之前的法律都是连续记录了的，b>n 。其他牧师q 收到消息后将每部已经出现在其账目中编号大于$n$的法律都返回给president，不在账目上的返回正常的LastVote 信息。
下面谈到多法律国会协议有关性质，首先是法律的顺序，不同法律编号的选举同时进行，发起选举的每个牧师都认为自己是president（不知道president 是怎么选举出来的，也不知道法律通过的顺序）。在完整议会协议第三步中法律被提议，第一次写入到账目上时称法律被通过。当一个president需要提出新的法案时，他必须从大部分集合牧师中学习到那么法律他们都投了赞成票，每部法律都被大部分集合牧师中至少一个牧师投了票，所以president发起新的选举前总能学到所有之前通过了的法律。president不会在空缺的法律编号内填补重要的法律。，也不会乱序提议法律，所以协议满足“法律有序性”：如果法律A 和法律B 都是重要的法律，法律A 在法律B 提议之前通过，那么法律A 有比法律B 更低的法律编号。第二点属性是president在选举出后且没有人再进出议会大厅，法律是按照下面步骤不断通过的（对应完整议会协议的3-5步）：
3. president 向一个法定人数牧师中每个牧师发送BeginBallot ；
4.每个牧师向president 发送Voted 信息。
5.president向每个牧师发送Success 消息。这样通过每部法律只需要三次消息传递，通过合并BeginBallot 和Success 命令可以进一步减少消息传递。

Ⅵ Paxos 算法的背景

Paxos 算法解决的问题是一个分布式系统如何就某个值（决议）达成一致。一个典型的场景是，在一个分布式数据库系统中，如果各节点的初始状态一致，每个节点都执行相同的操作序列，那么他们最后能得到一个一致的状态。为保证每个节点执行相同的命令序列，需要在每一条指令上执行一个“一致性算法”以保证每个节点看到的指令一致。一个通用的一致性算法可以应用在许多场景中，是分布式计算中的重要问题。因此从20世纪80年代起对于一致性算法的研究就没有停止过。节点通信存在两种模型：共享内存（Shared memory）和消息传递（Messages passing）。Paxos 算法就是一种基于消息传递模型的一致性算法。
不仅只用在分布式系统，凡是多个过程需要达成某种一致性的都可以用到Paxos 算法。一致性方法可以通过共享内存（需要锁）或者消息传递实现，Paxos 算法采用的是后者。下面是Paxos 算法适用的几种情况：一台机器中多个进程/线程达成数据一致；分布式文件系统或者分布式数据库中多客户端并发读写数据；分布式存储中多个副本响应读写请求的一致性。
Lamport 最初Paxos 算法的论文The Part-Time Parliament 在理解起来比较有挑战性，个人认为部分原因是Lamport 通过故事的方式来表述、解释这个问题，所以在阅读文章的时候读者需要透过故事讲的本身看到作者想说明什么。比如文章中会有很多讲到Paxos 文明没有被发现和考证的，这些映射到实际系统中往往是简单、大家都心知肚明的基础，但如果读者苦于想知道这些内容是什么时，就上当了。下面章节安排如下：第二节对应原文的1.1-2.1。第三节对应原文2.2-3.2。

Ⅶ Paxos 算法的数学问题

既然Lamport 是通过故事的方式提出Paxos 问题 ，我们就有必要简述下这个问题：希腊岛屿Paxon 上的执法者（legislators，后面称为牧师priest）在议会大厅（chamber）中表决通过法律，并通过服务员传递纸条的方式交流信息，每个执法者会将通过的法律记录在自己的账目（ledger）上。问题在于执法者和服务员都不可靠，他们随时会因为各种事情离开议会大厅，并随时可能有新的执法者（或者是刚暂时离开的）回到议会大厅进行法律表决，使用何种方式能够使得这个表决过程正常进行，且通过的法律不发生矛盾。
说明：不难看出故事中的议会大厅就是我们的分布式系统，每个牧师就是对应的每个节点或者进程，服务员传递纸条的过程即通信的过程，法律即是我们需要保证一致性的值（value）。牧师和服务员的进出对应着节点/网络的失效和加入，牧师的账目对应节点持久化存储设备。上面表决过程正常进行可以进一步表述为过程需求（progress requirements）：当大部分牧师在议会大厅呆了足够长时间，且期间没有牧师进入或者退出，那么提出的法案应该被通过并被记录在每个牧师的账目上。 Paxon 中的法律通过投票（ballots，也有翻译成选举）完成，每次投票涉及到的一群牧师称为法定人数（quorum），当且仅当法定人数中的所有牧师都赞成这个法案时，投票成功并通过该法律。每次投票B 包含以下内容：
B_dec 正在进行的投票
B_qrm 法定人数牧师的集合（非空牧师集合）
B_vot 赞成的牧师集合
B_bal 投票编号
有了以上定义，我们看出投票B 通过的充要条件是：B_qrm 属于 B_vot。接着我们定义B 为一次投票的集合，并说明投票如果满足下面三个条件，那么一致性可以得到保证。实际中每一次投票都可以看做是一次读写请求，所有法定人数的牧师赞成才通过法律表示：所有涉及到这次请求的节点都同时响应请求（比如更新某个值）才能保证一致性。这里选举编号（B_bal）的大小代表选举发起的先后顺序。下面给出三个重要的定义：
B1(B) B 中每个选举都有一个独一无二的选举编号。
B2(B) B 中每两个选举至少有一个共同的牧师。
B3(B) B 中每一次选举B ，如果其法定人数中任意牧师在之前的一次选举中赞成，那么这次选举B 等于之前一次所有B 中牧师赞成的选举，。即新的法律等于所有参与选举牧师中投赞成票的法律。
说明：看到这里，读者八成已经很迷糊了，下面我们以一个版本更新的分布式key-value 数据库为例，每个key-value 有多个副本，如果客户端发起一个update(key,vaule) 的操作，则会产生由一个节点发起、相关节点进行响应的一次一致性操作，即选举B。对保存了该key-value 的副本进行更新。需要注意的是法定人数牧师（B_qrm）是例子中所有保存这个key-value 副本的节点的一个大部分子集，因为可能在某些时候某些保存这个key-value 副本的节点不可达。B 是关于某个key-value 的一系列更新操作，不同的法律实际上是一个key-value 的不同值。那么B1-B3就好明白了，B1指一次只进行一个更新操作；B2指每两次更新操作必须有共同的节点参与；B3指某次key-value 操作的key-value 值与所有参与节点中之前进行投赞成票的最新值一致。这是因为如果某个节点在之前已经投票，说明它已经确认可以修改该值，而其他法定人数的牧师/节点还没有确认该值。
下面说明为什么B1-B3 蕴含一致性！
引理1.1 如果B1(B)，B2(B)$ 和B3(B) 满足，那么对于在B中的任意B 和B’ ，有

证明略，有兴趣的可以参考原文
定理1.2 如果B1(B)，B2(B) 和B3(B) 满足，那么对于在B 中的任意B 和B’ ，有

证：如果$B’_bal=B_bal 那么由B1(B) 可知B’=B 。如果B’_bal 不等于 B_bal ，那么总有一个编号大、一个小，根据引理1.1 可得。
定理1.3 b>B_bal 且对于所有B 中的B 都有Q 和 B_qrm 交集不为空。有一个选举B’ 满足B’_bal=b、B’_qrm=B’_vot=Q，那么如果B1(B)、B2(B)、B3(B)满足，则B1(B并B’)、B1(B并B’)、B1(B并B’) 也满足。
证明略，见原文。
这个定理说的是在一个选举集合B 之后的每次成功选举，只要和之前集合中每次选举都有交集，那么这些成功的选举合并选举集合B 满足一致性。

Ⅷ 如何浅显易懂地解说 Paxos 的算法

Paxos算法解决的问题是在一个可能发生消息可能会延迟、丢失、重复的分布式系统中如何就某个值达成一致，保证不论发生以上任何异常，都不会破坏决议的一致性。

一个典型的场景是，在一个分布式数据库系统中，如果各节点的初始状态一致，每个节点都执行相同的操作序列，那么他们最后能得到一个一致的状态。为保证每个节点执行相同的命令序列，需要在每一条指令上执行一个“一致性算法”以保证每个节点看到的指令一致。

一个通用的一致性算法可以应用在许多场景中，是分布式计算中的重要问题。 节点通信存在两种模型：共享内存和消息传递。Paxos算法就是一种基于消息传递模型的一致性算法。

分析Paxos算法的目的

Paxos算法的目的是为了解决分布式环境下一致性的问题。多个节点并发操纵数据，如何保证在读写过程中数据的一致性，并且解决方案要能适应分布式环境下的不可靠性（系统如何就一个值达到统一）。

Paxos算法中，可分为4种角色：

• Proposer：提议发起者，处理客户端请求，将客户端的请求发送到集群中，以便决定这个值是否可以被批准。

• Acceptor：提议批准者，负责处理接收到的提议，他们的回复就是一次投票。会存储一些状态来决定是否接收一个值。

• Client：产生议题者，Proposer就像Client的使者，由Proposer使者拿着Client的议题去向Acceptor提议，让Acceptor来决策。

• Learner：最终决策学习者，最终学习的目标是Acceptor们最终接受了什么议题？

Paxos算法的原理

例如：公司商定年会举办的地点，每个人都可以提出建议。在现实环境中我们可以在一个会议室共同讨论或在微信群中讨论（基于内存共享方式）；但在基于消息传递的分布式环境中每个人只能通过手机短信与其它人通过。如何在这种会延迟、丢失的环境中确定一个年会举办地点。

Paxos算法是这样解决这个问题：

每个人都可以提出建议、同意建议、接受建议

少数服从多数。只要建议被多数人同意即可确定该建议。

于是确定以下讨论方式：

• 只有被提出来的建议才能被大家同意。

• 最终只能确定一个建议。

• 如果某个人认为大家同意了某 个建议，那么这个建议必须真的是被大家同意的。

Paxos算法图解



在实现环境中会通过一次提议，选择一个Leader。后续所有的提议都只能由Leader提出。

原来paxos算法里的角色都是这样的不靠谱，不过没关系，结果靠谱就可以了。该算法就是为了追求结果的一致性。

原文链接：什么是Paxos算法？Paxos算法是区块链核心算法之一

Ⅸ 如何浅显易懂地解说 Paxos 的算法

Paxos真的并不是很容易理解，而且最初版本的Paxos也不能实现，相对而言一些变种算法更加容易理解，而且在工程实现上也比较简单。

其实看论文确实是最有效的，但却不是最高效的。理解运作过程也好，推导过程也好，大家的回答都是为了帮助大家更高效的掌握这门算法。大家的回答已经很好， 我这里作为补充，也是算另一个角度，帮助大家去理解paxos的数学推导过程，写了这么一篇文章：Paxos理论介绍(1): 朴素Paxos算法理论推导与证明 - 分布式一致性与高可用实践 - 知乎专栏。希望能帮到大家。