代码之家 › 专栏 › 技术社区 › Allen George

在这种情况下,paxos代理的正确行为是什么?

paxos consensus distributed algorithm

Allen George · 技术社区 · 14 年前

我正在研究paxos,在这个人为的例子中,我对算法的行为感到困惑。我希望下面的图表能够解释这种情况。

几点:

每个代理都充当提议者/接受者/学习者。
Prepare messages have form (instance,proposal_num) 。


    
     
      propose messages have form
      
       (instance,proposal_num,proposal_val)
       
        。
       
      
     
     
      
       
        server1和server2都决定同时启动建议流程
       
       
        在开始消息M1、M2和M3同时出现


   
    
     
      
       这里看起来,尽管协议是“正确的”,即只有一个值
       
        s2
       
       is selected,server1和server2相信它是因为不同的建议编号而被选择的。
      
      
      
      
       paxos算法是否仅在
       
        decide(…)
        
         message is sent out to the learners时终止?我一定是误会了,Paxos maked simple
         
          但是我认为是在提案人达到法定人数的那一刻做出了选择,因为他们的
          
           propose(…)
           
            messages.
           
          
         
        
       
      
      
       
        
         
          
           
           
          
         
        
       
      
      
       
        
         
          
           
            如果只有在
            
             decide(…)
             
              message is sent out to the agents之后才进行选择,那么server2是否应终止其sending of
              
               decide(1,5,s2)
               
                when it recovers because it saw a later
                
                 prepare(1,7)
                 
                  ?
                 
                
               
              
             
            
           
          
         
        
       
      
      
       
        
         
          
           
            
             
              
               
                
                 
                  
                 
                
               
              
             
            
           
          
         
        
       
      
      
      
      
       
        
         
          
           
            
             
              
               
                
                 
                  几点:
                 
                 
                  
                   每个代理都充当提议者/接受者/学习者。
                  
                  
                   准备邮件具有窗体
                   
                    (instance, proposal_num)
                   
                  
                  
                   建议消息有表单
                   
                    (instance, proposal_num, proposal_val)
                   
                  
                  
                   server1和server2都决定同时启动建议流程
                  
                  
                   在开始消息M1、M2和M3同时出现
                  
                 
                 
                  这里看起来,尽管协议是“正确的”,即只有一个值
                  
                   S2
                  
                  选择了,server1和server2认为选择它是因为提案编号不同。
                 
                 
                  paxos算法是否仅在
                  
                   Decide(...)
                  
                  信息发送给学习者?我一定是误会了
                  
                   Paxos变得简单
                  
                  但我认为选择是在提案人达到法定人数时做出的。
                  
                   Propose(...)
                  
                  信息。
                 
                 
                  如果只有在
                  
                   决定(…)
                  
                  如果服务器2终止其发送,则消息将发送给代理。
                  
                   Decide(1, 5, S2)
                  
                  当它恢复时,因为它看到了
                  
                   Prepare(1, 7)
                  
                  ?

2 回复 | 直到 14 年前

dougvk 14 年前

只需重新定义术语(我们也要去掉1,因为我们只研究一个paxos迭代):

1)propose(n)==propose(n),来自当前身份的提议者的消息n

2)acceptPrepare(n,v)==ack(n,v),发送给提议者的消息n.v为空,如果该节点尚未接受任何值,o.w.v等于它已接受的值。

3)createDelect(n,v)==接受!(x,v),要求节点接受具有标识x的提议者的该值。如果节点已收到准备(n)消息,则节点将拒绝该消息,其中n>x

一旦达到准备的法定人数(n)——也就是说,大多数人已经确认了消息——那么具有标识n的提议者发出一个接受命令!(n,v)。如果准备(n+x),x>0,是由一个身份为n+x的提议者发出的,并且被大多数人确认,在确认(n,v)消息和接受之间!(n,v),那么大多数人承诺不接受时间戳为<n+x,x>0(也就是节点将拒绝接受)的建议值!(n,v)

一旦大多数人接受,就做出选择!(n,v)他们没有承诺要忽略的信息。

因此,当server2重新联机并发送accept时!(5,s2),它将被忽略,因为5<7。

Dave Turner 8 年前

为了与公认的答案形成对比,算法本身并不真正需要终止在任何非常明确的意义上。更合理的做法是,单独讨论每个节点,终止它在算法中的参与,该算法是实现定义的。然后,也许您可以说,当所有参与的节点都退出时,算法本身已经终止,如果这是一个有用的事情需要知道的话。

该算法有效地 会聚的 一旦大多数承兑人发送 AcceptPropose 同一张选票的信息(在这种意义上,一旦发生,就没有选择最终决定什么价值),但这并不是一种可以在实践中观察到的情况:例如,如果网络在这组投票之前就开始删除信息, 接受提议 消息被发送,没有节点能够知道算法已经收敛,直到连接恢复。

然而,曾经一节点知道算法已经收敛(通过接收 接受提议 来自大多数人的信息)通过传统方式(例如通过发送 Decide 通过广播或流言传递消息,并让其他节点转发消息,直到每个节点都知道实现了收敛。

每个节点一旦知道算法收敛到的值,就可以终止它在算法中的参与,尽管根据您的实现约束,它可能更愿意继续参与更长的时间。

您必须稍微考虑一下故障容忍度,以说服自己在决定时终止可以保持活跃性:如果所有知道决定了什么值的节点在共享之前都会死亡,那么是否仍有可能取得进展?幸运的是,答案是肯定的:只要大多数节点仍然存在,如果其中任何一个节点知道确定的值,那么它就可以与其他节点共享该值,如果不知道,那么大多数参与节点只需要选择更高的投票号并运行另一轮。

在公认的答案中要注意的一点是:

一旦大多数人接受,就会做出选择!(N,V)他们没有承诺要忽略的信息。

首先,协议中没有关于 承诺忽视 接受提议 信息。与之相关的承诺 Propose 应忽略/拒绝消息。大多数 接受提议 消息可以总是用于学习所选的值,而不考虑选票号。

其次,一旦获得多数,就可以有效地做出选择。发送 接受提议 信息。您不能直接观察到这一点,因此您必须等待至少一个节点收到 接受提议 大多数人在知道做出选择之前发出的信息。一旦发生这种情况,您可以通过更多 接受提议 信息或通过广播/八卦 Decided 消息,取决于哪个更适合您的实现约束。