开发学院WEB开发ASP 时间同步算法与Simple Ring-based election algor... 阅读

时间同步算法与Simple Ring-based election algorithm算法分析

 2010-01-15 10:44:38 来源:WEB开发网   
核心提示:时间同步算法的应用非常广泛,譬如在Unix系统里面,时间同步算法与Simple Ring-based election algorithm算法分析,Make命令,只是用来编译新修改过的代码文件,数学模型和统计表可以参考这篇论文: http://www.vs.inf.ethz.ch/publ/papers/MsgCplx
时间同步算法的应用非常广泛。

譬如在Unix系统里面,Make命令,只是用来编译新修改过的代码文件。Make命令使用运行的客户端的时钟来决定哪个文件是被修改过的。但是,如果把代码放到文件服务器上面,而运行make命令的主机与文件服务器的时间不同的时候,make命令就有可能工作不正常。

譬如玩dota的时候,几个客户端需要一个同步过的时钟来使每个人的画面保持一致。、再譬如PC电脑同步服务器上面的时间可以做到很高的同步精度。



时间同步算法



时间同步算法,有以下几个解决方案:



Cristian’s algorithm算法



Cristian's Algorithm算法的应用背景,主要是在一个进程P像一个服务器S请求时间:

1.    P发送一个请求包到S请求时间。

2.    S收到P的请求包以后,在包上面加上当前S的时间,然后回发过去。

3.    P收到数据包之后,把当前时间设置为T+RTT/2。



RTT表示一个Round Trip Time,即P从发送到接受到数据包的时间。该算法假设发送数据包和接受数据包在网络上所用的时间是一样的。而且也假设S在处理请求的时候时间可以忽略不计。基于以上假设,改算法可以改进如下:

从P发送多个请求包到S,然后取RTT最小的做为RTT除以二加在此包包含的时间上。

算法精度分析:假设min为从S到P的最短时间,T为包含在上述定义的RTT中的时间。那么,P设置时间的范围应该是[T+min,T+RTT-min]。这样时间的偏差范围就在RTT-2min以内。改进后的算法精度应该为RTT/2-min。

    

Berkeley algorithm算法



Berkeley算法的使用环境与Cristian算法有所不同。Cristian算法是用在一个客户端向一个服务器请求正确时间的时候。而Berkeley算法是几个客户端之间同步时钟的算法。具体算法如下:

1.    首先通过Change and Robert’s Algorithm来从一个环里面选择一个节点做为Master。

2.    一个Master使用Cristian算法来请求各个节点的时间。

3.    Master通过记录RTT的平均值,同时剔除偏差很大的RTT来评估出每个节点的时间偏差。

4.    Master发送每个节点的时间偏差到每个节点,让节点自行校正。



客户端接受到了时间以后,一般来说不会把当前的时间往回调整。因为这会导致一些程序莫名奇妙的错误。因为在很多算法中,时间不会往回调整是一个基本假设。譬如make命令。

解决的方案有一个:让时钟走慢点就可以了。花费一些时间来调整到正确时间。



另外,还需讨论一下Change and Robert’s Algorithm这个算法。这个算法和时间同步算法一样,是玩dota的时候需要用到的。在dota初始化的时候,需要同步各个玩家的时钟。在掉线了之后,就要通过特定的算法来找一个新的主机:



Change and Robert’s Algorithm



Change and Robert’s Algorithm算法假设每个PRocess都有一个UID,同时在一个Ring状网络中可以有个没有方向的通讯信道。算法如下:

1.    首先ring中的每个节点把自个标识为non-participant。

2.    当一个process发现主机掉线了的时候,它首先把自个标识成为participant,然后发送给邻居一个包含了自个UID的一个选主机的数据包。

3.    当数据包达到邻居的时候,首先和自己的UID比较下,如果自己的UID比这个UID大,就把自己标识成为participant,同时修改数据包里面的UID,并且也往顺时针方向发送这个数据。

4.    当一个process接到一个数据包的时候发现这个数据包里面的UID和自己的UID一样的时候,就开始这个算法的第二阶段:

5.    这个process把自己标识成为non-participant,同时发送已经选择好了主机的信息到邻居,并且包含UID信息。

6.    如此循环,当回到被选中成为主机的Process的时候,整个过程结束。



这是在分布式系统里面选择一个主机的算法。当然,在特定的环境下,可以把选择的条件变化一下,譬如选择网络速度最快的或者是CPU最快的作为主机。同时,这个算法还可以避免多个Process同时发现主机掉线,几个process同时寻求主机的情况。



这个算法的伪码可以描述如下:

Start : M:= i:

    Send <i> to neighbor;

Upon receiving message <j>;

    If M<j then M:=j;

            Send <j> to neighbor;

        Elseif M=j then leader;

        Endif;



该算法详细的复杂度分析,数学模型和统计表可以参考这篇论文:



http://www.vs.inf.ethz.ch/publ/papers/MsgCplxElecAlgo.pdf



本文仅分析了Centrilized System里面的几个时间同步算法,对于分布式系统里面的Network Time Protocal和Reference broadcast Synchronization算法并未做分析。以后有空研究研究NTP。

Tags:时间 同步 算法

编辑录入:爽爽 [复制链接] [打 印]
[]
  • 好
  • 好的评价 如果觉得好,就请您
      0%(0)
  • 差
  • 差的评价 如果觉得差,就请您
      0%(0)
赞助商链接