网络异常情况下拜占庭容错算法探究.doc

网络异常情况下拜占庭容错算法探究 　　摘 要：随着电子商务网站等分布式应用的高速发展，系统的可用性已经受到了越来越多的重视。关键的服务不仅需要能够容忍良性错误，还需要能够容忍拜占庭错误。针对当前大部分的拜占庭容错算法主要针对算法正常执行的问题，提出了考虑出错情况下的拜占庭容错算法。该算法主要考虑实际过程中服务请求端和服务提供端的主复制品可能发生错误而没有响应，或者因网络拥塞而使响应没有及时送达等网络异常的情况。该算法解决了其他拜占庭容错算法在网络发生异常的情况下不能正常工作的问题，具有更强的适应性。 关键词：复制品；网络异常；拜占庭容错算法 中图分类号：TP393.08 容错算法，一直是分布式应用程序框架的组成部分。在分布式系统中，研究者们对高可用系统的研究。一般集中在良性错误，如服务器宕机、拒绝服务攻击、在网络上窃听消息或修改与破坏数据等，这些错误可能使服务器中断，破坏数据的完整性和必威体育官网网址性。但缺乏对更为严重的恶意攻击的研究，譬如软件错误、错误操作、密钥丢失、服务器被黑客控制等。这种由恶意攻击引起的错误，被称为拜占庭错误。如果任其发展，由于拜占庭故障造成的分布式应用偏离指定的行为，可能导致财产损失甚至人类生命丧失。 当前主流拜占庭容错算法主要针对算法正常执行的问题，提出了考虑出错情况下的拜占庭容错算法。该算法主要考虑实际过程中服务请求端和服务提供端的主复制品可能发生错误而没有响应，或者因网络拥塞而使响应没有及时送达的情况。 1 算法描述 1.1 基本概念 拜占庭容错中，为了容忍f个错误的复制品，复制品集合的大小 。一旦错误复制品的数量超过了错误容忍的门限值 ，该服务就不能再正常工作。一些符号说明如下： Fc是服务请求端中发生拜占庭错误上限值；每个replica用ci表示，主副制品用cp表示；服务响应端T由tn=3ft+1个replicas组成，ft是服务响应端中发生拜占庭错误replicas个数的上限值，每个replica用ti表示，主副制品用tp表示。 1.2 出错情况下的拜占庭容错算法 当前主流的拜占庭容忍算法针对的是服务请求端和服务提供端的主复制品都未发生错误且网络畅通的情况，这是一种理想状况。在实际过程中服务请求端和服务提供端的主复制品可能发生错误而没有响应，或者因网络拥塞而使响应没有及时送达。本节就服务请求端未能及时收到消息，引起计时器超，服务提供端发生错误的情形，对算法进行讨论。 引起服务请求端的复制品计时器超时的原因可能有：（1）服务响应端的主复制品 发生错误，未能将服务请求端发生来的请求转发给其他服务响应端的复制品。（2）服务响应端的主复制品 被黑客控制，故意不将服务响应端的复制品经过算法认可后的结果发送给服务请求端的复制品。（3）服务请求端的复制品计时器时间设置过短，不适用于当前的网络状况。 对于情况（3）应该使用使用神经网络等建模工具对计时器的时间进行建模，对计时器的时间进行动态调整，这不在本文讨论的范围内，本文主要考虑情况（1）和情况（2）。解决这一问题的算法描述如下： Step1：当服务请求端C需要调用外部服务响应端T服务时，C中的每一个复制品向T中的主服务复制品tp发送消息 。其中o是要ci请求的操作，x是该操作的序号， 是该请求o的时间戳。发送请求后，服务请求者ci启动计时器，等待来自T的应答，如图1所示。 Step2：C中的复制品ci发送请求后，等待应答的过程中，计时器超时，ci将请求 发送给T中的每一个复制品。 Step3：T中的复制品 收到 条匹配的DirectRequest消息后， 向T的主复制品 发送消息 ，并启动计时器。 Step4： 向T的主复制品 发送消息 后，在计时器时间收到了 发送的消息，则说明 未发生错误，T的复制品开始PRE-PREPARE、PREPARE和COMMIT三个阶段的通信过程；如果 在计时器时间内未收到 发送的消息， 开始怀疑 发生了错误，向其他复制品发送更改视图的消息 。 Step5：T中的复制品经过View-change算法后，选举了一个新的主复制品（如中的t2），开始拜占庭一致算法。 Step6： 收到其他复制品 发送的消息 ， 是当前T中复制品所在的视图，r是执行的结果，x是请求操作的序号。 比较这些结果，如果其中包含相同数量的 的消息数量2ft+1，则接受此结果，并将结果 发送给服务请求端中的每一个复制品。 Step7：C中的复制品 收到 发送来的结果 后，对结果进行验证，确定消息来自 后，发送应答消息 给服务请求端中的主复制品（简称 ），其中 是当前T中复制品所在的视图。 Step8： 收到各 发送的应答消息 后，验证 来自于 后查看