拜占庭容错中的状态转换算法研究

2 0 1 3年第 1期文章编号： 1 0 0 6— 2 4 7 5 ( 2 0 1 3 ) 0 1 - 0 0 3 7 - 0 3

计算机与现代化 J I S U A N J I Y U X I A N D A I HU A

总第 2 0 9期

拜占庭容错中的状态转换算法研究 陈柳，周伟 ( 1 .武汉工程大学电气信息学院，湖北武汉 4 3 0 0 7 3; 2 .华中师范大学计算机学院，湖北武汉 4 3 0 0 7 9 ) 摘要：针对现有拜占庭容错中的状态转换算法不适用于主动复制品的这一问题，提出支持有状态复制品的状态转换算

法。在每个复制品中创建恢复队列，当一个复制品从错误中恢复或者其他原因导致其状态不是最新的，需要使用本算法 从其它复制品处获得最新的状态。实验分析结果显示了算法的有效性。 关键词：复制品；状态转换；检查点中图分类号： T P 3 0 1 . 6 文献标识码： A d o i: 1 0 . 3 9 6 9/ j . i s s n . 1 0 0 6 - 2 4 7 5 . 2 0 1 3 . 0 1 . O 1 1

Re s e a r c h o n St a t e Tr a n s f e r Al g o r i t h m i n By z an t i ne Fa u l t To l e r a nc e CHEN L i u ,ZHOU We i

( 1 .S c h o o l o f E l e c t i r c a l a n d I n f o r m a t i o n E n g i n e e i r n g, Wu h a n I n s t i t u t e o f T e c h n o l o g y, Wu h a n 4 3 0 0 7 3, C h i n a;

2 . S c h ol o f C o m p u t e r, C e n t r l a C h i n a N o r m l a U n i v e r s i t y, Wu h a n 4 3 0 0 7 9, C h i n a ) Ab s t r a c t:To s o l v e t he p r o b l e m t h a t e x i s t i n g s t a t e t r a ns f e r a l g o it r hm i s n o t a p p l i e d t O p r o a c t i v e r e p l i c a,f l s t a t e t r a ns f er lg a o it r h m

wh i c h s u p p o r t i n g r e p l

i c a w i t h s t a t e i s p r o p o s e d .T h e r e c o v e r y q u e u e i s c r e a t e d i n e v e r y r e p l i c a .W h e n t h e r e p l i c a wh o s e s t a t e i s n o t l a t e s t b e c a u s e o f r e c o v e in r g f r o m f a u l t s o r o t h e r r e a s o n s,t h e lg a o it r h m c a n b e u s e d t o f e t c h l a t e s t s t a t e f r o m o t h e r r e p l i c a s . The e x pe ime r n t a l r e s u l t s s h o w t h e e fe c t i v e o f t he lg a o it r h m.

Ke y wo r d s:r e p l i c a;s t a t e t r a n s f e r;c h e c k p o i n t

0 引言 随着 I n t e ac r t越来越普遍的使用，以及企业和政府对网络服务的越来越严重的依赖，拜占庭错误¨剖 对企业和政府的损害也越来越严重。互联网不断开

编号大于自己日志中消息编号的上限。 状态转换协议的关键是有效地从其他正确复制

品处获得最新的状态加 ,要达成此目标需减少从其 他复制品处获得的信息数量，减少对其他复制品的负 担。

放的同时为恶意攻击提供了广阔的实施环境，软件系 统不断复杂的同时伴随着不断增多的错误操作和软件错误。因此，建立一个能抵抗恶意攻击，能容拜占

1 算法描述 本文中最新的状态 l 1 1 - 1 3]是指最新的稳定检查点的状态，如果复制品不知道当前最新的检查点编号， 本协议也能够成功完成状态更新。假设需要更新状

庭错误的系统是高可用系统研究的一个新挑战。 现有的拜占庭容错协议 _ 1刮不支持具有状态的主动服务，因此本文设计新的状态转移算法，该算法能

态的复制品是 t i, S t a t e T r a n s f e r协议过程详述如下： S t e p l 复制品 t i向其他复制品广播发送消息 m t咖

够用于拜占庭容错中的复制品状态转移，且支持复制 品具有状态。

i=( G E T S T A T E, v, n, t i ),其中 n是要获取状态

在拜占庭容错协议中，复制品 t出现以下情

的检查点编号。如果 t i不知道最新检查点编号，设置 n=0。

况时，使用状态转换协议 _ 6 重建自己的状态。 ( 1 )从错误中恢复； ( 2 )获知有新的稳定的检查点[ 7 - 8],且检查点的

S t e p 2复制品 t j收到消息 m删 t i后判断 n的值。 如果 n=0, t 向t;发送最新的稳定检查点 n t j的摘要

收稿日期： 2 0 1 2 - 0 8 . 2 4 作者简介：陈柳 ( 1 9 7 9一 ),女，湖北丹江 E 1人，武汉工程大学电气信息学院讲师，华中师范大学计算机学院博士研究生，研究方向：服务容错；周伟 ( 1 9 8 0一 ),男，湖北襄阳人，讲师，博士，研究方向：网络安全。

第1页