UCAM-CL-TR-857.pdf

《UCAM-CL-TR-857.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、TechnicalReportUCAM-CL-TR-857ISSN1476-2986Number857ComputerLaboratoryARC:AnalysisofRaftConsensusHeidiHowardJuly201415JJThomsonAvenueCambridgeCB30FDUnitedKingdomphone+441223763500http://www.cl.cam.ac.uk/c2014HeidiHowardThistechnicalreportisbasedonadissertationsubmittedMay2014

2、bytheauthorforthedegreeofBachelorofArts(ComputerScienceTripos)totheUniversityofCambridge,PembrokeCollege.TechnicalreportspublishedbytheUniversityofCambridgeComputerLaboratoryarefreelyavailableviatheInternet:http://www.cl.cam.ac.uk/techreports/ISSN1476-2986AbstractThePaxosalg

3、orithm,despitebeingsynonymouswithdistributedconsensusforadecade,isfamouslydifficulttoreasonaboutandimplementduetoitsnon-intuitiveapproachandunderspecification.Inresponse,thisprojectimplementedandevalu-atedaframeworkforconstructingfault-tolerantapplications,utilisingtherecently

4、proposedRaftalgorithmfordistributedconsensus.Constructingasimulationframe-workforourimplementationenabledustoevaluatetheprotocoloneverythingfromunderstandabilityandefficiencytocorrectnessandperformanceindiversenetworkenvironments.Weproposearangeofoptimisationstotheprotocoland

5、releasedtothecommunityatestbedfordevelopingfurtheroptimisationsandinvestigatingoptimalprotocolparametersforreal-worlddeployments.3AcknowledgementsIhavethoroughlyenjoyedworkingonthisprojectandmyfinalyearatCambridge,itwouldn’thavebeenpossiblewithoutthehelpandsupportofthefollowi

6、ngwonderfulpeople:AnilMadhavapeddy,notonlyhaveyoubeenanexcellentsupervisorbutyouhavebeenmymentoroverthelasttwoyearsandDiegoOngaro,authorofRaft,whohastakenhistimetosupportmeinreproducinghisresultsandsharinghisideas.IwouldalsoliketothankMalteSchwarzkopfandChrisHadleyforprovidi

7、ngexcellentfeedbackonmydissertation,whichformsthebasisofthistechnicalreport.4Contents1Introduction91.1Motivation....................................91.2RelatedWork..................................101.2.1DefinitionofConsensus........................101.2.2CAPtheorem:Conjectur

8、e,Correctness&Controversy......111.2.3FLPImpossibilityResult...............