什么是"查看"在协商一致的Paxos算法?算法、QUOT、Paxos

2023-09-11 07:11:46 作者:微凉如梦、轻如烟

我已经贴伪code下面一个Paxos的算法,并想知道,如果有人可以点我在正确的方向。我想实现下面的算法,但我是一个困惑是什么下方正是意见重新presents。我知道评论说,这是一个过去的观点号码数值图,但如果有人可以给我解释一下,究竟这些价值是什么的看法号是。

 状态:
  num_h:最高提案#见过的prepare
  num_a,val_a:最​​高值,并建议#哪个节点已接受
  my_num:最后一个提案#节点在这一轮Paxos的使用
  inst_h:最高视图编号我们接受(回合数)
  观点:过去查看数字地图值
  做到:领导说达成了协议,我们就可以开始新的看法

在每个视图的变化,初始化状态:
  num_a = 0
  num_h = 0
  my_num = 0
  val_a =()//空单

Paxos的第1阶段
  一个节点(可能多于一个的...)决定是领导者(不必是当前视图):
    my_num = MAX(num_h,my_num)+1,追加节点ID //唯一的建议数量
    做= FALSE
    发送prepare(inst_h + 1,my_num)在所有节点{意见[inst_h],初次接触的节点,本身}

  如果节点收到prepare(VID,N):
    如果VID< = inst_h:
      返回OLD_VIEW(VID,观点[VID])//意见[VID]是赢家VID
    否则如果n> num_h:
      num_h = N
      做= FALSE
      返回PROMISE(num_a,val_a)
    其他:
      返回拒绝()

Paxos的第2阶段
  如果领导者得到OLD_VIEW(VID,V):
    意见[VID] = V
    inst_h = VID
    查看变化
    重启的Paxos

  否则,如果领导者得到抑制():
    延迟和重新启动的Paxos

  否则,如果领导者得到PROMISE的多数意见[inst_h]节点:
    如果有PROMISE(n_i,V-I)的存在,使得V_I不为空:
      对应最高n_i V =非空值V_I收到
    其他领导者就可以选择一个值:
      V =设置ping到节点(包括自身)
    发送ACCEPT(inst_h + 1,my_num,v)的所有反应

  其他:
    延迟和重新启动的Paxos

  如果节点获得ACCEPT(VID,N,V):
    如果VID< = inst_h:
      返回OLD_VIEW(VID,观点[VID])
    否则如果n> = num_h:
      num_a = N
      val_a = V
      返回接受()
    其他
      返回拒绝()

Paxos的第3阶段
  如果领导者得到OLD_VIEW(VID,V):
    意见[VID] = V
    inst_h = VID
    查看变化
    重启的Paxos
  否则,如果领导者被从多数节点的观点[inst_h】受理:
    发送DECIDE(inst_h + 1,val_a)所有(包括自身)
  其他:
    延迟和重新启动的Paxos
  如果节点获得决定(VID,V):
    如果VID< = inst_h:
      返回OLD_VIEW(VID,观点[VID])
    其他:
      做=真
      主要是编号最小的节点为V
      意见[VID] = V
      inst_h = VID
      查看变化
 

解决方案

的意见对应轮的算法。他们被称为意见,因为算法中的每个节点是异步的,因此全球系统状态的每个节点的理解可能会过时。该节点使用视图同步算法的执行。看评论,说的观点=发。

I have pasted pseudocode for a paxos algorithm below and was wondering if someone could point me in the right direction. I am trying to implement the algorithm below, but I'm a confused what exactly "views" represents below. I know the comment says it is a "map of past view numbers to values", but if someone could explain to me what exactly these "values" are and what "view numbers" are.

  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
分布式一致性算法 Paxos原理与推导过程

解决方案

The views correspond to rounds of the algorithm. They are called views because every node in the algorithm is asynchronous and thus every node's understanding of the global system state can be outdated. The nodes use views to synchronize the execution of the algorithm. Look at the comment that says views = rounds.