摘要
为消除Raft(Replicated And Fault Tolerant)算法在领导者选举阶段的强随机性,满足安全关键系统对强确定性分布式一致性算法的需求,提出改进算法BE-Raft(Bounded Election Raft),通过全局时基和延迟感知机制,以及具有硬时间和结果约束的选举流程,消除随机性。利用SMT(Satisfiability Modulo Theories)求解器对算法进行形式化验证,并在小规模分布式集群中评估BE-Raft重新选举所需轮数与时间开销。结果表明,BE-Raft能在单轮选举内,于硬时间约束内产生唯一可预测的领导者。其最差选举时间比经典Raft缩短至60.1%至83.8%,最差与平均时间开销增幅小于2%,较经典方法提升10倍以上;平均时间开销与经典方法接近。BE-Raft在选举阶段实现了严格的时间与结果确定性,提升了Raft算法在安全关键系统中的适用性。
To eliminate the strong randomness in the leader election phase of the Raft(Replicated And Fault Tolerant)algorithm and meet the requirements of safety-critical systems for strongly deterministic distributed consensus algorithms,an improved algorithm called BE-Raft(Bounded Election Raft)is proposed.It eliminates randomness through a global time base,a delay-aware mechanism,and an election process with hard time and result constraints.The SMT(Satisfiability Modulo Theories)solver is used for formal verification of the algorithm,and the number of rounds and time overhead required for BE-Raft re-election are evaluated in a small-scale distributed cluster.The results show that BE-Raft can generate a unique and predictable leader within a single election round and under hard time constraints.Its worst-case election time is reduced to 60.1%to 83.8%of that of the classic Raft,the increase in worst-case and average time overhead is less than 2%,which is more than 10 times better than the classic method;the average time overhead is close to that of the classic method.BE-Raft achieves strict time and result determinism in the election phase,improving the applicability of the Raft algorithm in safety-critical systems.
作者
郑伯阳
高艳华
郭晓坤
ZHENG Bo-yang;GAO Yan-hua;GUO Xiao-kun(Beijing Institute of Control and Electronic Technology,Beijing 100038,China)
出处
《计算机仿真》
2025年第11期326-330,396,共6页
Computer Simulation
关键词
分布式一致性
确定性
领导者选举
安全关键系统
Distributed consistency
Determinism
Leader election
Safety-critical systems
