泉州推广优化公司厦门seo新站策划

第一题

Q：在server1、server2和server3中选一个Master。

已知：

• Proposer1的编号为2；
• Proposer2的编号为1；
• Proposer3的编号为3.

Proposer向Acceptor提交决议的顺序为Proposer1、Proposer3、Proposer2.

试分析：最终选取出的Master是哪台服务器？写出分析过程。

已知：proposer2向acceptor2和acceptor3发送编号为1的消息，
proposer1向acceptor1和accepto2发送编号为2的消息，
proposer3向acceptor2和acceptor3发送编号为3的消息。

一、第一轮

（1）proposer1发送的消息到达acceptor1和acceptor2，它们都没有接收过请求，所以接收该请求并返回{pok，null，null}给proposer1，同时acceptor1和acceptor2承诺不再接受编号小于2的请求。

（2）proposer3的消息到达acceptor2和acceptor3，acceptor2已经接受proposer1的请求并承诺不再接收编号小于2的请求，但编号3的消息大于acceptor2已接受的2，所以acceptor2接收该请求并返回{pok，null，null}给proposer3，acceptor3没有接收过请求，所以接收该请求并返回{pok，null，null}给proposer3，同时acceptor2和acceptor3承诺不再接受编号小于3的请求。

（3）proposer2的消息到达acceptor2和acceptor3，它们都接受过请求并且承诺不再接收编号小于3的消息，所以acceptor2和acceptor3都拒绝proposer2的请求。

二、第二轮

各个proposer开始统计收到的结果，proposer可能开始进入accept阶段或者重新提交。

（1）proposer1收到两个回复，超过半数，并且返回的value值是null，所以proposer1提交{2，serv1}的提案，acceptor1和acceptor2接收到proposer1的提案{2，serv1}的提案，acceptor1承诺不再接收编号小于2的请求，所以acceptor1通过该提案，并返回{pok，2，serv1}给proposer1，acceptor2承诺不再接收编号小于3的请求，所以acceptor2拒绝该提案。

（2）proposer3收到两个回复，超过半数，并且返回的value值是null，所以proposer3提交{3，serv3}的提案，acceptor2和acceptor3接收到proposer3的提案{3，serv3}的提案，acceptor2和acceptor3都承诺不再接收编号小于3的请求，所以acceptor2和acceptor3通过该提案，并返回{pok，3，serv3}给proposer3。

（3）proposer2没有收到回复，尝试生成更大的编号4，并转回准备阶段执行。proposer2向acceptor2和acceptor3发送编号为4的消息，acceptor2和acceptor3都承诺不再接收编号小于3的请求，所以acceptor2和acceptor3接收该请求并返回{pok，3，serv3}给proposer2，acceptor2和acceptor3承诺不再接受编号小于4的请求。

三、第三轮

（1）proposer1收到一个回复，未超过半数，尝试生成更大的编号5，并转回准备阶段执行.propose1向acceptor1和acceptor2发送编号为5的消息，acceptor2承诺不再接收编号小于2的请求，所以acceptor接收该请求并返回{pok，2，serv1}给proposer1；acceptor3承诺不再接收编号小于3请求，所以acceptor接收该请求并返回{pok，3，serv3}给proposer1。此时proposer1收到两个回复，超过半数，并且返回的value值是不null，所以proposer1进行广播通知已经commit的value。此时可以从广播中得知acceptor们通过serv3的已经超过半数，所以选出Master，Master为serv3，结束。

最终选取出的Master是server3。

第二题

Q：从Server1、Server2、Server3和Server4中选一个Master。

已知：

• Proposer1的提案是Server1，初始编号为2；
• Proposer2的提案是Server2，初始编号为3；
• Proposer3的提案是Server3，初始编号为1；
• Proposer4的提案是Server4，初始编号为4；

.

• Proposer1的提案提交给多数派Acceptor1、Acceptor2和Acceptor3；
• Proposer2的提案提交给多数派Acceptor1、Acceptor2和Acceptor4；
• Proposer3的提案提交给多数派Acceptor1、Acceptor3和Acceptor4；
• Proposer4的提案提交给多数派Acceptor2、Acceptor3和Acceptor4.

Proposer向Acceptor提交决议的顺序为Proposer1、Proposer2、Proposer3、Proposer4.

试分析：最终能否选举出Master？如果能，选举出的Master是哪台服务器？写出分析过程。

已知：proposer1向acceptor1、acceptor2和acceptor3发送编号为2的消息，
proposer2向acceptor1、acceptor2和acceptor4发送编号为3的消息，
proposer3向acceptor1、acceptor3和acceptor4发送编号为1的消息，
proposer4向acceptor2、acceptor3和acceptor4发送编号为4的消息，
proposer向acceptor提交决议的顺序为proposer1、proposer2、proposer3、proposer4。

一、第一轮

（1）proposer1发送的消息到达acceptor1、acceptor2和acceptor3。它们都没有接收过请求，所以接收请求并返回{pok，null，null}给proposer1，同时acceptor1、acceptor2和acceptor3都承诺不再接受编号小于2的请求。

（2）proposer2发送的消息到达acceptor1和acceptor2和acceptor4。acceptor1已经接收过proposer1的请求并承诺不再接收编号小于2的请求，但编号3的消息大于acceptor1已经接受的2，所以acceptor1接收该请求并返回{pok，null，null}给proposer2，并承诺不再接收编号小于3的请求；acceptor2已经接收过proposer1的请求并承诺不再接收编号小于2的请求，但编号3的消息大于acceptor2已经接受的2，所以acceptor2接收该请求并返回{pok，null，null}给proposer2，并承诺不再接收编号小于3的请求；acceptor4没有接收过请求，所以接收请求并返回{pok，null，null}给proposer2，并承诺不再接收编号小于3的请求。

（3）proposer3发送的消息到达acceptor1和acceptor3和acceptor4。acceptor1和acceptor4已经接收过proposer2的请求并承诺不再接收编号小于3的请求，所以acceptor1和acceptor4拒绝接收proposer3发送的编号为1的请求；acceptor2已经接收过proposer1的请求并承诺不再接收编号小于2的请求，所以acceptor2拒绝接收proposer3发送的编号为1的请求.

（4）proposer4发送的消息到达acceptor2和acceptor3和acceptor4。acceptor2和acceptor4已经接收过proposer2的请求并承诺不再接收编号小于3的请求，但编号4的消息大于acceptor2和acceptor4已经接受的3，所以acceptor2和acceptor4接收该请求并返回{pok，null，null}给proposer4，并承诺不再接收编号小于4的请求；acceptor3已经接收过proposer1的请求并承诺不再接收编号小于2的请求，但编号4的消息大于acceptor3已经接受的2，所以acceptor3接收该请求并返回{pok，null，null}给proposer4，并承诺不再接收编号小于4的请求.

二、第二轮

各个proposer开始统计收到的结果，proposer可能开始进入accept阶段或者重新提交。

（1）proposer1收到3个回复，超过半数，并且返回的value值是null，所以proposer1提交{2，serv1}的提案，acceptor1、acceptor2和acceptor3接收到proposer1提交的{2，serv1}提案。acceptor1承诺不再接受编号小于3的请求，所以acceptor1拒绝该提案；acceptor2和acceptor3承诺不再接受编号小于4的请求，所以acceptor2和acceptor3拒绝该提案.

（2）proposer2收到3个回复，超过半数，并且返回的value值是null，所以proposer2提交{3，serv2}的提案，acceptor1、acceptor2和acceptor4接收到proposer2提交的{2，serv2}提案。acceptor1承诺不再接受编号小于3的请求，所以acceptor1通过该提案，并返回{pok，3，serv2}给proposer2；acceptor2和acceptor4承诺不再接受编号小于4的请求，所以acceptor2和acceptor4拒绝该提案.

（3）proposer3没有收到回复，尝试生成更大的编号5，并转回准备阶段执行。proposer3向acceptor1、acceptor3和acceptor4发送编号为5的消息；acceptor1承诺不再接收编号小于3的请求，所以acceptor1接收proposer3发送的编号为5的请求并返回{pok，3，serv2}给proposer3；acceptor3和acceptor4承诺不再接收编号小于4的请求，所以acceptor3和acceptor4接收该请求并返回{pok，4，null}给proposer3，并承诺不再接受编号小于5的请求.

（4）proposer4收到收到3个回复，超过半数，并且返回的value值是null，所以proposer4提交{4，serv4}的提案。acceptor2、acceptor3和acceptor4接收到proposer4提交的{4，serv4}提案。acceptor2承诺不再接受编号小于4的请求，所以通过该提案，并返回{pok，4，serv4}给proposer4；acceptor3和acceptor4承诺不再接受编号小于5的请求，所以acceptor3和acceptor4拒绝该提案。

三、第三轮

各个proposer开始统计收到的结果，proposer可能开始进入accept阶段或者重新提交。

（1）proposer1没有收到回复，尝试生成更大的编号6，并转回准备阶段执行。proposer1向acceptor1、acceptor2和acceptor3发送编号为6的消息，acceptor1和acceptor3承诺不再接受编号小于5的请求，所以acceptor1接受该请求并返回{pok，6，serv2}，acceptor3接受该请求并返回{pok，6，null}，同时acceptor1和acceptor3承诺不再接受编号小于6的请求；acceptor2承诺不再接受编号小于4的请求，所以acceptor2接受该请求并返回{pok，6，serv4}，并承诺不再接受编号小于6的请求。

（2）proposer2收到1条回复，没有超过半数，所以proposer2尝试生成更大的编号7，并转回准备阶段执行。proposer2向acceptor1、acceptor2和acceptor4发送编号为7的消息，acceptor1已经接收过proposer1的请求并承诺不再接收编号小于6的请求，但编号7的消息大于acceptor1已经接受的6，所以acceptor1接收该请求并返回{pok，6，serv2}给proposer2，并承诺不再接收编号小于7的请求；acceptor2已经接收过proposer1的请求并承诺不再接收编号小于6的请求，但编号7的消息大于acceptor2已经接受的6，所以acceptor2接收该请求并返回{pok，6，serv4}给proposer2，并承诺不再接收编号小于7的请求；acceptor4已经接收过proposer3的请求并承诺不再接收编号小于5的请求，但编号7的消息大于acceptor4已经接受的5，所以acceptor4接收该请求并返回{pok，5，nul}给proposer2，并承诺不再接收编号小于7的请求。

（3）proposer3收到收到3个回复，超过半数，并且有的返回的value值不是null，所以proposer3将收到的编号最大的value作为自己的提案，为提案serv2。proposer3向acceptor1、acceptor3和acceptor4提交{3，serv2}的提案，但是acceptor1和acceptor4已经承诺不再接受编号小于7的提案，acceptor3已经承诺不再接受编号小于6的提案，所以acceptor1、acceptor3和acceptor4都拒绝proposer3的提案。

（4）proposer4收到1条回复，没有超过半数，所以proposer4尝试生成更大的编号8，并转回准备阶段执行。proposer4向acceptor2、acceptor3和acceptor4发送编号为8的消息，acceptor2和acceptor4已经接收过proposer2的请求并承诺不再接收编号小于7的请求，但编号8的消息大于acceptor2和acceptor已经接受的7，所以acceptor2接收该请求并返回{pok，7，serv4}给proposer4，acceptor4接收该请求并返回{pok，7，null}给proposer4，并且acceptor2和acceptor4承诺不再接收编号小于8的请求；acceptor3已经接收过proposer1的请求并承诺不再接收编号小于6的请求，但编号8的消息大于acceptor3已经接受的6，所以acceptor3接收该请求并返回{pok，6，nul}给proposer4，并承诺不再接收编号小于8的请求。

至此，发现第三轮接收到proposer请求的情况和第一轮完全一样，所以接下来第四轮的情况也会第二轮完全一样，因此，第2n-1轮的请求都会一样，并且acceptor1的编号会是4n-1，acceptor2、acceptor3和acceptor4的编号都会是4n；第2n轮的请求也都会一样，并且acceptor2的编号是4n，acceptor1、acceptor3和acceptor4的编号都会是4n+1；从第二轮开始，acceptor1的值永远是serv2，acceptor2的值永远是serv4，acceptor3和acceptor4的值永远是null。paxos算法陷入了以两轮为一个循环节的死循环，最终无法选举出master。