1

I have pasted pseudocode for a paxos algorithm here:

What is a "view" in the Paxos consensus algorithm?

and was wondering if someone could point me in the right direction.

The algorithm says that each node has a "state" which contains a bunch of information the node should keep track of.

Suppose we have two nodes: Node #1 and Node #2. In the simplest case Node #2 joins Node #1 and they both play paxos. What exactly happens to the states of Node #1 and Node #2 after 2 joins 1? When does the "views" data structure change and what does it contain? If someone can explain to me this simple case of two nodes playing paxos, then I think I can figure out multiple node case.

My current understanding (which I'm pretty sure is not correct) is as follows:

  1. Node #2 sends a message to join Node #1.
  2. Node #1 receives message from Node #2 asking to join.
  3. Node #1 assumes leadership and kicks into phase 1, computes my_num = max(0,0) + 1 = 1
  4. Node #1 sends all nodes in views[0] (which is empty) prepare(1,1)
  5. Node #1 sends initial contact node (Node #2) prepare(1,1)
  6. Node #1 sends Node #1 (itself) prepare(1,1)
  7. Node #2 receives prepare(1,1). It sets its num_h=1 and returns to leader PROMISE(0,{empty list})
  8. Node #1 receives prepare(1,1) and sets its num_h=1 and returns itself PROMISE(0,{empty list}).

now we get to phase 2

This is where I am quite confused.

Node #1 is the leader and it receives two PROMISE(0,{empty list}) messages. According to the algorithm, if the leader gets a majority of promises in views[0] then it can set a value for "v" and send the ACCEPT message to all responders.

What I am confused about is currently the views[0] for the leader is empty so how can you compute the majority of an empty list?

Also, let's assume the leader has received a majority of promises and proceeds to set v = set of pingable nodes (including self). What exactly are pingable nodes? Is it just Node #1 and Node #2?

Would appreciate all / any help and will definitely award points to those that help.

4

1 回答 1

0

伪代码不是专门针对特定问题的。事实上，教授说如果我们不想使用伪代码，我们不需要使用伪代码，并表示我们可以查看其他 Paxos 论文（即 paxos made simple、paxos made live 等）以获得有关实现此算法的指导. 也许你是对的，我应该看看维基百科来实现这个算法。因此，views[..] 只是一个哈希映射，节点可以选择它想要的任何值。如果我理解正确，您说多数声明只是检查它是否收到“足够”的 PROMISE 消息。但是知道我们是否有足够的唯一方法是节点是否跟踪它的组成员是谁。这意味着我需要一个不同的数据结构。

另外，因为你发表了评论，我不能给你积分。如果您发布答案，那么我可以给您积分。

于 2012-05-12T14:07:48.283 回答