首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >问答首页 >Paxos共识算法中的“视图”是什么?

Paxos共识算法中的“视图”是什么?
EN

Stack Overflow用户
提问于 2012-05-08 08:20:33
回答 2查看 938关注 0票数 1

我已经在下面粘贴了一个paxos算法的伪代码,不知道是否有人可以给我指出正确的方向。我正在尝试实现下面的算法,但我对下面的“视图”到底代表什么感到困惑。我知道评论说它是“从过去的视图数字到值的映射”,但如果有人能给我解释一下这些“值”到底是什么,什么是“视图数字”。

代码语言:javascript
运行
复制
  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
EN

回答 2

Stack Overflow用户

回答已采纳

发布于 2012-05-08 13:00:06

视图与算法的轮次相对应。它们被称为视图,因为算法中的每个节点都是异步的,因此每个节点对全局系统状态的理解可能会过时。节点使用视图来同步算法的执行。看一下注释,上面写着views = rounds。

票数 1
EN

Stack Overflow用户

发布于 2013-02-28 08:38:28

视图在论文Paxos Made Practical中定义。"view“是集群的一种特殊状态,即一组机器和指定的领导者。

我们关心视图的原因是,集群的状态可能会随着机器的来来去去而变化(例如,因为您想要重新配置集群,或者因为一个或多个机器发生了故障)。

每个视图还与一个view-number (也称为view-id)相关联,每次视图更改时,都会为新视图分配一个新的view-number。与特定view-number关联的值就是视图本身(集群中的机器列表)。所以“视图”可能看起来像这样:

代码语言:javascript
运行
复制
{ view-number = 1 : value = { machine-01, machine-02, machine-03 },
  view-number = 2 : value = { machine-02, machine-03, machine-04 },
  view-number = 3 : value = { machine-01, machine-02, machine-04 } }

你可以在论文中找到更多细节。

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/10490902

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档