Я вставил псевдокод для алгоритма paxos ниже, и мне было интересно, может ли кто-нибудь указать мне правильное направление. Я пытаюсь реализовать приведенный ниже алгоритм, но я не понимаю, что именно представляют собой «представления» ниже. Я знаю, что в комментарии говорится, что это «карта прошлых номеров просмотров со значениями», но если бы кто-нибудь мог объяснить мне, что именно представляют собой эти «значения» и что такое «номера просмотров».
state:
num_h: highest proposal # seen in a prepare
num_a, val_a: highest value and proposal # which node has accepted
my_num: the last proposal # the node has used in this round of Paxos
inst_h: highest view number we have accepted (round number)
views: map of past view numbers to values
done: leader says agreement was reached, we can start new view
on each view change, initialize state:
num_a = 0
num_h = 0
my_num = 0
val_a = () // empty list
Paxos Phase 1
a node (maybe more than one...) decides to be leader (need not be in current view):
my_num = max(num_h, my_num)+1, append node ID // unique proposal number
done = false
sends prepare(inst_h+1, my_num) to all nodes in {views[inst_h], initial contact node, itself}
if node receives prepare(vid, n):
if vid <= inst_h:
return OLD_VIEW(vid, views[vid]) // views[vid] is the winner for vid
else if n > num_h:
num_h = n
done = false
return PROMISE(num_a, val_a)
else:
return REJECT()
Paxos Phase 2
if leader gets OLD_VIEW(vid, v):
views[vid] = v
inst_h = vid
view change
restart paxos
else if leader gets REJECT():
delay and restart paxos
else if leader gets PROMISE from majority of nodes in views[inst_h]:
if any PROMISE(n_i, v_i) exists such that v_i is not empty:
v = non-empty value v_i corresponding to highest n_i received
else leader gets to choose a value:
v = set of pingable nodes (including self)
send ACCEPT(inst_h+1, my_num, v) to all responders
else:
delay and restart paxos
if node gets ACCEPT(vid, n, v):
if vid <= inst_h:
return OLD_VIEW(vid, views[vid])
else if n >= num_h:
num_a = n
val_a = v
return ACCEPTED()
else
return REJECT()
Paxos Phase 3
if leader gets OLD_VIEW(vid, v):
views[vid] = v
inst_h = vid
view change
restart paxos
else if leader gets ACCEPTED from a majority of nodes in views[inst_h]:
send DECIDE(inst_h+1, val_a) to all (including self)
else:
delay and restart paxos
if node gets decide(vid, v):
if vid <= inst_h:
return OLD_VIEW(vid, views[vid])
else:
done = true
primary is lowest-numbered node in v
views[vid] = v
inst_h = vid
view change
