导　　师： 何克晶

授予学位： 硕士

作　　者： (）;

机构地区： 华南理工大学

摘　　要： Raft是以可理解性为设计初衷的分布式共识算法,通过简化状态空间和将共识过程分而治之,Raft优于其他诸如Paxos等共识算法。但是,Raft只能解决非拜占庭容错环境下的共识问题。在此驱动下,论文设计并提出了拜占庭容错的分布式共识算法BRaft(Byzantine Raft)。BRaft继承了Raft的状态空间,同时针对拜占庭容错从日志篡改、Leader选举和Committed确认三方面设计了强化机制,在具备同Raft一致的可理解性的基础上,保证了算法的安全性和活性。BRaft在诸多方面采用同Raft一致的设计思想,但是在以下三方面,BRaft针对拜占庭容错设计了其特有的机制。(1)日志篡改。在进行日志复制时,拜占庭节点具备篡改日志的能力。BRaft利用数字签名检测日志篡改行为,针对不同状态的节点设计了相应的响应机制,确保被篡改的日志项无法在非拜占庭节点间达成共识。(2)Leader选举。在Leader选举阶段,拜占庭节点可通过伪造投票消息获得其他节点的投票。BRaft通过Committed证明机制,确保当选Leader必定拥有全部已经达成共识的日志项。(3)Committed确认。一个日志项Committed意味着该日志项已在非拜占庭节点间达成共识。BRaft通过Committed确认机制,确保在拜占庭节点发送错误消息的情况下日志项依然能够被正确的Committed。BRaft算法通过Golang语言编程实现。实验从算法性能和拜占庭容错两方面对BRaft核心机制进行论证。相比于Raft,BRaft损失了一定的性能,从而具备了拜占庭容错特性;相比于其他支持拜占庭容错的分布式共识算法,BRaft在不失性能的前提下具备同Raft一致的可理解性。

关 键 词： 拜占庭容错 共识算法 日志复制

领　　域： []