异步网络模型下的共识协议研究

doi:10.11896/jsjkx.240600132

摘要/Abstract

摘要： 随着分布式系统的发展,共识问题受到了计算机领域的广泛关注。然而,FLP不可能结论指出:“在存在故障节点的异步系统中,没有确定的共识协议能够使分布式系统达成一致”。该结论成为阻碍设计异步共识协议的鸿沟。目前,研究者就如何规避FLP结论,已在异步共识领域进行了大量研究。首先,通过对分布式共识问题的相关定义与理论进行分析,总结出异步共识协议的定义;然后,根据规避FLP结论策略的不同,分别阐述了异步共识协议的发展脉络、实现方法与相关指标,分析总结了通过随机化、部分同步模型、故障检测器、条件限制与混合共识的方法规避FLP结论的优劣,指出了异步共识协议大多仍停留在理论阶段,难以真正应用;最后,简单探讨了共识中的等价性问题,期望拓展共识协议的实现途径,推动异步共识协议的创新和发展。

关键词: 异步共识, FLP结论, 随机化, 部分同步, 故障检测器, 拜占庭故障

Abstract: As the development of distributed systems progresses,the consensus problem has garnered widespread attention in the field of computer science.The inevitable asynchrony in distributed systems greatly impacts the design of consensus protocols.However,the FLP impossibility result indicates that in asynchronous systems,there is no definitive consensus protocol capable of enabling a distributed system to reach agreement.Researchers have conducted extensive studies on how to circumvent the FLP conclusion in the field of asynchronous consensus.This paper first analyzes the relevant definitions and theories of the distributed consensus problem,summarizing and concluding the definition of asynchronous consensus protocols.Then elaborates on the development trajectory,implementation methods,and performance metrics of asynchronous consensus protocols from the perspective of different strategies to circumvent the FLP conclusion.The paper analyzes and summarizes the advantages and disadvantages of avoiding the FLP conclusion through methods such as randomization,partial synchronous models,failure detectors,conditional restrictions,and hybrid consensus approaches.It points out that the design of asynchronous consensus protocols mostly remains at the theoretical stage and is difficult to put into practical use.Finally,briefly discusses the issue of equivalence in consensus,hoping to expand the implementation pathways of consensus protocols and promote the innovation and development of asynchronous consensus protocols.

Key words: Asynchronous consensus, FLP impossibility, Randomization, Partial synchrony, Failure detectors, Byzantine fault

中图分类号:

TP311

王迪, 雷航, 曹广平. 异步网络模型下的共识协议研究[J]. 计算机科学, 2025, 52(4): 310-326. https://doi.org/10.11896/jsjkx.240600132

WANG Di, LEI Hang, CAO Guangping. Research on Consensus Protocols in Asynchronous Network Model[J]. Computer Science, 2025, 52(4): 310-326. https://doi.org/10.11896/jsjkx.240600132

参考文献

[1]EISENBERG E,GALE D.Consensus ofSubjective Probabilities:the Pari-Mutuel Method[J].The Annals of Mathematical Statistics,1959,30(1):165-168.
[2]AKKOYUNLU E A,EKANADHAM K,HUBER R V.SomeConstraints and Tradeoffs in the Design of Network Communications[C]//Proceedings of the 5th ACM Symposium on Operating Systems Principles.Austin,Texas,USA:ACM Press,1975:67-74.
[3]PEASE M,SHOSTAK R,LAMPORT L.Reaching Agreementin the Presence of Faults[J].Journal of the ACM,1980,27(2):228-234.
[4]DOLEV D,DWORK C,STOCKMEYER L.On theMinimal Synchronism Needed for Distributed Consensus[J].Journal of the ACM,1987,34(1):77-97.
[5]XIA Q,DOU W S,GUO K W,et al.A Survey on Blockchain Consensus Protocols[J].Journal of Software,2021,32(2):277-299.
[6]JIN S X,ZHANG X D,GE J G,et al.A Research Review on Blockchain Consensus Algorithms[J].Journal of Information Security,2021,6(2):85-100.
[7]LIU Y Z,LIU J W,ZHANG Z Y,et al.A Research Review onBlockchain Consensus Mechanisms[J].Cryptography Journal,2019,6(4):395-432.
[8]DENG X H,WANG Z Q,LI J,et al.Comparative Research on Mainstream Blockchain Consensus Algorithms[J].Application Research of Computers,2022,39(1):1-8.
[9]WANG Q,LI F J,NI X L,et al.Survey on Blockchain Consensus Algorithms and Application[J].Journal of Frontiers of Computer Science and Technology,2022,16(6):1214-1239.
[10]TAN P L,WANG R S,ZENG W H,et al.Overview of Blockchain Consensus Algorithms[J/OL].https://www.jsjkx.com/CN/article/openArticlePDF.jsp?id=21672.
[11]BALDONI R,HELARY J M.Strengthening Distributed Protocols to Handle Tougher Failures[R].France:Univ.de Rennes 1,2002.
[12]VORAPANYA A.Large-Scale Distributed Services[D].Florida:University of Florida,2000.
[13]FISCHER M J,LYNCH N A,PATERSON M S.Impossibility ofDistributed Consensus with one Faulty Process[J].Journal of the ACM,1985,32(2):374-382.
[14]WATTENHOFER R.The Science of the Blockchain[M].USA:CreateSpace Independent Publishing Platform,2016.
[15]LAMPORT L,SHOSTAK R,PEASE M.The Byzantine generals problem[J].ACM Transactions onProgramming Languages and Systems,1982,4(3):382-401.
[16]DOLEV D,LYNCH N A,PINTER S S,et al.ReachingApproximate Agreement in the Presence of Faults[J].Journal of the ACM,1986,33(3):499-516.
[17]CASTRO M,LISKOV B.Practical ByzantineFault Toleranceand Proactive Recovery[J].ACM Transactions on Computer Systems,1999,17(4):173-186.
[18]BARBORAK M,MALEK M,DAHBURA A.The ConsensusProblem in Fault-Tolerance Computing[J].ACM Computing Surveys,1998,6(25):171-220.
[19]FISHER M J.TheConsensus Problem in Unreliable Distributed Systems(A Brief Survey)[M].Berlin:Springer-Verlag Press,1983:127-140.
[20]LAMPORT L.How toMake a Multiprocessor Computer ThatCorrectly Executes Multiprocess Programs[J].IEEE Transactions on Computers,1979,28(9):690-691.
[21]KRISHNA S,EMMI M,ENEA C,et al.Verifying Visibility-Based Weak Consistency[C]//Proceedings of the 29th European Symposium on Programming.Dublin:Springer Press,2020:280-307.
[22]LOUT M C,ABU-AMARA H H.MemoryRequirements for Agreement Among Unreliable Asynchronous Processes[J].Advances in Computing Research,1987,4:163-183.
[23]RABIN M O.Probabilistic algorithms[M].New York:Academic Press,1976:21-39.
[24]RABIN M O.Randomized Byzantine Generals[C]//Proceedings of the 24th Annual Symposium on Foundations of Computer Science.Tucson,AZ,USA:IEEE Press,1983:403-409.
[25]BEN-OR M.Another advantage of free choice(Extended Abstract):Completely asynchronous agreement protocols[C]//Proceedings of the ACM Symposium on Principles of Distributed Computing.New York:ACM Press,1983:27-30.
[26]DOLEV D,STRONG R.Polynomial Algorithms for ByzantineAgreement[C]//Proceedings of the 14th ACM Symposium on Theory of Computing.New York:ACM Press,1982:401-407.
[27]FISCHER M,LYNCH N.A Lower Bound for the Time toAssure InteractiveConsistency[J].Information Processing Letters,1982,14(4):182-186.
[28]TOUEG S.Randomized Byzantine Agreements [C]//Procee-dings of the third ACM Symposium on Principles of Distributed Computing.Vancouver,British,Columbia,Canada:ACM Press,1984:183-178.
[29]SHAMIR A.How to share a secret[J].Communications of the ACM,1979,22(11):612-613.
[30]BRACHA G,TOUEG S.Asynchronous consensus and broad-cast protocols[J].Journal of the ACM,1985,32(4):824-840.
[31]BRACHA G.An Asynchronous (n－1)/3-Resilient ConsensusProtocol[C]//Proceedings of the third ACM Symposium on Principles of Distributed Computing.Vancouver,British,Columbia,Canada:ACM Press,1984:154-162.
[32]CACHIN C,KURSAWE K,SHOUP V.RandomOracles in Constantinople:Practical Asynchronous Byzantine Agreement Using Cryptography[J].Journal of Cryptology,2005,18(3):219-246.
[33]CACHIN C,KURSAWE K,PETZOLD F,et al.Secure and Efficient Asynchronous Broadcast Protocols[C]//Annual International Cryptology Conference.Berlin,Heidelberg:Springer Press,2001:524-541.
[34]CHANDRA T D,TOUEG S.Unreliable Failure Detectors forReliable Distributed Systems[J].Journal of the ACM,1996,43(2):225-267.
[35]MOUSTAFA H,MOSTEFAOUI A,RAYNAL M.Signature-free asynchronous Byzantine consensus with t<n/3 and O(n²) messages[C]//Proceedings of the 2014 ACM Symposium on Principles of Distributed Computing.New York:ACM,2014:2-9.
[36]BRACHA G.Asynchronous Byzantine agreement protocols[J].Information & Computation,1987,75(2):130-143.
[37]SRIKANTH T.K,TOUEG S.Simulating authenticated broadcasts to derive simple fault-tolerant algorithms[J].Distributed Computing,1987,2:80-94.
[38]BEN-OR M,KELMER B,RABIN T.Asynchronous secure computations with optimal resilience[C]//Proceedings of the 13th Annual ACM Symposium on Principles of Distributed Computing.New York:ACM Press,1994:183-192.
[39]MILLER A,XIA Y,CROMAN K,et al.The honey badger of BFT protocols[C]//Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security.New York:ACM Press,2016:31-42.
[40]CACHIN C,TESSARO S.Asynchronous verifiable information dispersal[C]//Proceedings of the International Conference on Distributed Computing.Orlando,FL,USA:IEEE Press,2005:191-201.
[41]GUO B Y,LI X Y.A High-Efficiency Multi-Value Byzantine Consensus Scheme [J].Cryptography Journal,2018,5(5):516-528.
[42]GUO B,LU Z,TANG Q,et al.Dumbo:Faster AsynchronousBFT Protocols[C]//CCS '20:2020 ACM SIGSAC Conference on Computer and Communications Security.New York:ACM,2020:803-818.
[43]WANG Y Q,LIU Y,LI X Y,et al.Efficient asynchronous Byzantine fault tolerance algorithm for blockchain[J].Application Research of Computers,2023,40(9):2590-2599.
[44]BAIRD L.The Swirlds hashgraph consensus algorithm:Fair,fast,Byzantine fault tolerance:Technical Report:SWIRLDS-TR-2016[R].2016.
[45]DEMERS A,GREENE D,HAUSER C,et al.Epidemic algo-rithms for replicated database maintenance[J].ACM SIGOPS Operating Systems Review,1988,22(1):8-32.
[46]EZHILCHELVAN P,MOSTEFAOUI A,RAYNAL M.Ran-domized multivalued consensus[C]//Proceedings of the 4th International Symposium on Object-oriented Real-time Distributed Computing.Newport Beach,CA,USA:IEEE Press,2001:195-201.
[47]HURFIN M,MOSTEFAOUI A,RAYNAL M.A versatile family of consensus protocols based on Chandra-Toueg’s unreliable failure detectors[J].IEEE Transactions on Computers,2002,51(4):395-408.
[48]DOLEV D,DWORK C,STOCKMEYER L.On the minimal synchronism needed for distributed consensus[J].Journal of the ACM,1987,34(1):77-97.
[49]DWORK C,LYNCH N,STOCKMEYER L.Consensus in the presence of partial synchrony[J].Journal of the ACM,1988,35(2):288-323.
[50]OKI B M,LISKOV B H.Viewstamped replication:a new primary copy method to support highly-available distributed systems[C]//Proceedings of the 7th Annual ACM Symposium on Principles of Distributed Computing.Toronto,Ontario,Canada:ACM Press,1988:8-17.
[51]ABRAHAM I,MALKHI D,SPIEGELMAN A.ValidatedAsynchronous Byzantine Agreement with Optimal Resilience and Asymptotically Optimal Time and Word Communication[EB/OL].(2018-11-04) [2024-04-28].https://arxiv.org/abs/1811.01332.
[52]ABRAHAM I,MALKHI D,SPIEGELMAN A.Asymptotically optimal validated asynchronous byzantine agreement[C]//Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing.Toronto,ON,Canada:ACM Press,2019:337-346.
[53]YIN M F,MALKHI D,REITER M K,et al.HotStuff:BFT consensus in thelens of blockchain[J].arXiv.1803.05069,2018.
[54]VERONESE G S,CORREIA M,BESSANI A N,et al.Efficient Byzantine fault-tolerance[J].IEEE Transactions on Computers,2013,62(1):16-30.
[55]BIRAN O,MORAN S,ZAKS S.A combinatorial characteri-zation of the distributed tasks that are solvable in the presence of one faulty processor[C]//Proceedings of the Seventh ACM Symposium on Principles of Distributed Computing.Toronto,Ontario:ACM Press,1988:263-275.
[56]TEL G.Introduction to Distributed Algorithms[M].Cam-bridge:Cambridge University Press,2003:505-509.
[57]AGUILERA M K,TOUEG S,DEIANOV B.Revisiting theweakest failure detector for uniform reliable broadcast[C]//Proceedings of the 13th International Symposium on Distributed Computing.Heidelberg:Distributed Computing,1999:19-33.
[58]LIU J X,WU Z B,DONG J,et al.Summarization on failure detector in distributed system[J].Intelligent Computer and Applications,2019,9(2):215-220.
[59]FAGG G E,DONGARRA J J.Building and using a Fault Tole-rant MPI implementation[J].International Journal of High Performance Applications and Supercomputing,2004,18(3):353-361.
[60]BATCHU R,DANDASS Y,SKJELLUM A,et al.A Model-Based Approach to Low-Overhead Fault Tolerant Message-Passing Middleware[J].Cluster Computing,2004,7(4):303-315.
[61]FOSTER I,KESSELMAN C,TUECKE S.The anatomy of the grid[J].International Journal of High Performance Computing Applications,2001,15(3):200-222.
[62]STELLING P,FOSTER I,KESSELMAN C,et al.A fault detection service for wide area distributed computations[C]//Proceedings of the 7th IEEE Symposium on High Performance Distributed Computing.Chicago:IEEE Press,1998:268-278.
[63]BURNS M W,GEORGE A D,WALLACE B A.Simulative Performance Analysis of Gossip Failure Detection for Scalable Distributed Systems[J].Cluster Computing,1999,2(3):207-217.
[64]WANG G.Research on Consensus Protocols of AsynchronousSystems Based on Fault Detectors [D].Changsha:Hunan University,2006.
[65]AGUILERA M K,CHEN W,TOUEG S.On the Weakest Fai-lure Detector for Quiescent Reliable Communication[R].New York:Cornell University,1997:2-15.
[66]LAMPORT L.The part-time parliament[J].ACM Transactions on Computer Systems,1998,16(2):133-169.
[67]MARTIN J P,ALVIZI L.Fast Byzantine consensus[J].IEEETransactions on Dependable and Secure Computing,2006,3(3):202-215.
[68]PRISCO R D,LAMPSON B,LYNCH N.Revisiting the PAXOS algorithm[J].Theoretical Computer Science,2000,243(1/2):35-91.
[69]CHANDRA T D,HADZILACOS V,TOUEG S.The weakestfailure detector for solving consensus[J].Journal of the ACM,1996,43(4):685-722.
[70]KIHLSTROM K P,MOSER L E,MELLIAR-SMITH P M.Byzantine fault detectors for solving consensus[J].The Computer Journal,2003,46(1):16-35.
[71]KIHLSTROM K P,MOSER L E,MELLIAR-SMITH P M.Solving Consensus in a Byzantine Environment Using an Unreliable Fault Detector[C]//International Conference on Principles of Distributed Systems.1997:61-75.
[72]DOUDOU A,GARBINATO B,GUERRAOUI R,et al.Mute-ness failure detectors:Specification and implementation[C]//European Dependable Computing Conference.Berlin:Springer Press,1999:71-87.
[73]MOSTEFAOUI A,RAYNAL M.Solving consensus usingChandra-Toueg’s unreliable failure detectors:a general quorum-based approach[C]//Proceedings of the 13th InternationalSymposium on Distributed Computing.Bratislava:Springer Press,1999:49-63.
[74]DUTTA P,GUERRAOUI R.Fast indulgent consensus with zero degradation[C]//Proceedings of the 4th European Dependable Computing Conference.Berlin:Springer Press,2002:191-208.
[75]MALKHI D,REITER M.Unreliable intrusion detection in distributed computations[C]//Proceedings of the 10th Computer Security Foundations Workshop.Los Alamitos:IEEE Press,1997:116-124.
[76]SCHIPER A.Early consensus in an asynchronous system with a weak failure detector[J].Distributed Computing,1997,10(3):149-157.
[77]FRIEDMAN R,MOSTEFAOUI A,RAYNAL M.Simple andefficient oracle-based consensus protocols for asynchronous Byzantine systems[J].IEEE Transactions on Dependable and Secure Computing,2005,2(1):46-56.
[78]BALDONI R,HÉLARY J M,RAYNAL M,et al.Consensus in Byzantine asynchronous systems[J].Journal of Discrete Algorithms,2003,1(2):185-210.
[79]MOSTEFAOUI A,RAJSBAUM S,RAYNAL M.Conditions on input vectors for consensus solvability in asynchronous distributed systems[J].Journal of the ACM,2003,50(6):922-954.
[80]MOSTÉFAOUI A,RAJSBAUM S,Raynal M,et al.Condition-based consensus solvability:a hierarchy of conditions and efficient protocols[J].Distributed Computing,2004,17(1):1-20.
[81]FRIEDMAN R,MOSTÉFAOUI A,RAJSBAUM S,et al.Dis-tributed agreement and its relation with error-correcting codes[C]//Proceedings of the International Symposium on Distributed Computing.Berlin:Springer Press,2002:63-87.
[82]FRIEDMAN R,MOSTÉFAOUI A,RAJSBAUM S,et al.Dis-tributed agreement problems and their connection with error-correcting codes[J].IEEE Transactions on Computers,2007,56(7):865-875.
[83]FETZER C,CRISTIAN F.On the possibility of consensus in asynchronous systems[C]//Proceedings of the Pacific Rim International Symposium on Fault-Tolerant Systems.California:IEEE Press,1995:86-91.
[84]AGUILERA M K,TOUEG S.Failure detection and randomization:a hybrid approach to solve consensus[J].SIAM Journal of Computing,1998,28(3):890-903.
[85]MOSTEFAOUI A,RAYNAL M,TRONEL F.The best of both worlds:a hybrid approach to solve consensus[C]//Proceedings of the International Conference on Dependable Systems and Networks.New York:IEEE Press,2000:513-522.
[86]GUERRAOUI R,RAYNAL M.The Information Structure of Indulgent Consensus[J].IEEE Transactions on Computers,2004,53(4):453-466.
[87]CANETTI R,RABIN T.Fast asynchronous Byzantine agreement with optimalresilience[C]//Proceedings of the 25th Annual ACM Symposium on Theory of Computing.San Diego,California:ACM Press 1993:42-51.
[88]SCHMID U,FETZER C.Randomized Asynchronous Consensus with Imperfect Communications[C]//22nd Symposium on Relia-ble Distributed Systems.Florence,Italy:IEEE Press,2003:362-370.
[89]CHOR B,DWORK C.Randomization in Byzantine agreement[J].Advances in Computer Research.Greenwich,1989,5:443-497.
[90]FRIEDMAN R,MOSTÉFAOUI A,RAYNAL M.Pmute-based consensus for asynchronous Byzantinesystems[J].Parallel Processing Letters,2005,15(1/2):162-182.
[91]AGUILERA M K,CHEN W,TOUEG S.Failure detection and consensus in the crash-recovery model[J].Distributed Computing,2000,13(2):99-125.
[92]HADZILACOS V,TOUEG S.Fault-tolerant broadcasts and related problems[C]//Distributed Systems(2nd Ed.).1993:97-145.
[93]CORREIA M,VERONESE G S,NEVES N F,et al.Byzantine consensus in asynchronous message-passing systems:a survey[J].International Journal of Critical Computer-Based Systems,2011,2(2):141-161.
[94]CORREIA M,NEVES N F,VERISSIMO P.From consensus to atomic broadcast:time-free Byzantine-resistant protocols without signatures[J].The Computer Journal,2006,49(1):82-96.
[95]NAKAMOTO S.Bitcoin:a peer-to-peer electronic cash system[EB/OL].(2008-06-10)[2024-05-13].https://bitcoin.org/bitcoin.pdf.
[96]MA Z F.Blockchain Technology Development Guide [M].Beijing:Tsinghua University Press,2021.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed