Preliminary
系统包括:
Acceptor
Proposer
Learner
Proposer
生成一项提议,发送给Acceptor
,Acceptor
如果接受该提议,那么系统所有成员达成共识(即:该提议生效),通过Learner
获取共识的内容。
可能存在的问题:
- 如果有多个
Acceptor
,会出现多个Acceptor
同时接受多个不同的提议的情况; - 如果只有一个
Acceptor
,一旦Acceptor
出现故障,那么系统将无法运作;
PS: 下文中的接收是指收到一个请求,接受是指 accept 一项提议。
算法流程:
第一阶段:
-
Proposer
生成一个系统下唯一的ID:; -
Proposer
向大多数Acceptor
发送prepare
请求(附带 ),目的是需要得到Acceptor
的如下承诺:-
Acceptor
需要忽略掉 ID 小于 的请求
-
-
Acceptor
如果接收到上述请求,如果Acceptor
接收过其他Proposer
发送的prepare
请求且对应的ID如果大于 ,那么忽略该请求(不给出承诺),否则回复上述请求。回复的内容包括:- 该
Acceptor
接受过的 ID 小于 且最接近 的 某一项提议(抽象为一个值 ) - 如果没有,则返回空
- 该
第二阶段:
-
Proposer
如果接收到大多数Acceptor
的回复,Proposer
向大多数Acceptor
发起accept
请求。请求的内容包括:- 这些回复的提议中 ID 最大的那项提议的值,如果没有则自拟一项提议
-
prepare
请求中发送的
- 当
Acceptor
接收到accept
请求时,假设对应的提议ID为。如果该Acceptor
做过不接受ID小于的提议的承诺,那么就忽略掉该请求,否则则接受这项提议。
第三阶段:Learner
收集所有 Acceptor
接受的提议,完成共识算法。
分析
-
一旦系统达成共识,那么该共识就不会改变,比如:
-
Proposer 1
发送一项提议给大多数的Acceptor
,Proposer 1
获得大多数Acceptor
的回复后,拟定一项提议Proposal 1
发送给Acceptor
达成共识; -
Proposer 2
如果要发送另外一项提议给大多数Acceptor
,这些Acceptor
中的部分已经接受了Proposal 1
,根据上述算法,Proposer 2
只能提出提议Proposal 1
给Acceptor
;
-
-
存在不同的
Acceptor
接受不同的Proposal
,比如:-
Proposer 1
发送一项提议Proposal 1
给大多数的Acceptor
,在一部分Acceptor
未接受这项提议时,另外一个Proposer 2
发起了另一项提议Proposal 2
给这些Acceptor
; - 因为
Proposal 2
的ID要比Proposal 1
的ID要大,因此这部分既收到了Proposer 1
发送的prepare
请求又收到了Proposer 2
发送的prepare
请求的Acceptor
肯定只会接受Proposal 2
; - 这种情况只有在
Proposer 2
发送prepare
请求的Acceptor
都没有接受Proposal 1
时才成立 ;
-
少数
Acceptor
出现故障,不会影响系统的正常运行;存在一个
Acceptor
接受多个提议的情况,此时这多个提议的值是一样的;