不可靠高流量分布式系统中分布式容错全局协调器选举算法(IJITCS-V7-N3-1)

1、I.J.InformationTechnologyandComputerScience,2015,03,1-11PublishedOnlineFebruary2015inMECS()DOI:10.5815/ijitcs.2015.03.01Copyright©2015MECSI.J.InformationTechnologyandComputerScience,2015,03,1-11ADistributedFaultToleranceGlobalCoordinatorElectionAlgorithminUnreliableHighTrafficDistributedSystemsDanialRahdariDepartmentofComputerEngineering,ScienceandResearchBranch,IslamicAzadUniversity,IranE-mail:d.rahdary@srbiau.ac.irAmirMasoudRahmani,NiushaAboutalebyDepartmentofComputerEngineering,ScienceandRes。

2、earchBranch,IslamicAzadUniversity,IranE-mail:rahmani@sr.iau.ac.ir;n.aboutaleby@gmail.comAliSheidaeiKarambastiNo15,GhafariAlley,MashahirSt.,GhaemMaghameFarahaniAve.,Tehran,IranE-mail:a.sheidaei@etadbir.comAbstract—Distributedsystemsconsistofseveralmanagementsiteswhichhavedifferentresourcesharinglevels.Resourcescanbesharedamonginnersiteandoutersiteprocessesatfirstandsecondlevelrespectively.Globalcoordinatorshouldexistinordertocoordinateaccesstomultisite’ssharedresources.Moreover;someothercoordinat。

3、orsshouldmanageaccesstoinnersite’ssharedresourcessothatexertingappropriatecoordinatorelectionalgorithmsineachleveliscrucialtoachievemostefficientsystem.Inthispaperahierarchicaldistributedelectionalgorithmisproposedwhicheliminatessinglepointoffailureofelectionlauncher.Meanwhiletrafficisappliedtonetworkatdifferenttimesandthenumberofelectionmessagesisextremelydecreasedaswellwhichappliesmoreefficiencyespeciallyinhightrafficnetworks.Astandbysystembetweencoordinatorsandtheirfirstalternativeisconsidere。

4、dtoinductlesswaittimetoprocesseswhichwanttocommunicatewithcoordinator.IndexTerms—DistributedAlgorithm,CoordinatorElection,FaultTolerance,CloudComputing,HotStandby,Unreliability,·GlobalCoordinatorI.INTRODUCTIONProcessesandsystemscollaborationaregrowingmoreandmorebyemergingnewtechnologiesandconceptsintheworldofdistributedsystemswhichgivecommunicationthemostcrucialroleofthesesystems.ItisclearthatProcessescommunicatewitheachotherthroughoperatingsystemandTransitionlayer[1].Thefunctionsofsomeprocesses。

5、duringexecutionprocedurearedependentontheothersstatebecauseofthesamesharedresources.Asanexampleifaprocesswantstoaccessanexclusivesharedresource,itshouldcheckovertoensuretobetheonlyonewhichusesthecriticalregiontofulfillmutualexclusionproperty.Therearelotsofchallenges,fewofwhicharelistedbelow,thatshouldbeconsideredduringthisprocess.Processesshouldaskalltheothersforpermissionbeforeaccessingthesharedresources.Thereforeasignificantnumberofmessagesshouldbepassed.Duringpermissionaskingprocess,theproc。

6、essesresponseisn’tguaranteed.Itusuallyhappensbecauseoftheirfailureor100%usageofsystem’sprocessor.Thereforetheycannotaccesstheresourcebecauseoflackofpermission.Theexistenceofcentralcontrollingprocessisnecessarytohandlethesesituations.Singlepointoffailureisclearlythesothatifitcrashes,newelectionshouldbelaunchedtosetnewprocessascoordinator.Leaderelectionalgorithmswhichareusedforelectingcoordinatoranditsalternativesareusefulinmanyvariousareas.Theyareusedindistributedsystemsforloadbalancingandkeeping。

7、resourcereplicasconsistency[2].Whenacoordinatorcrashes,somewaittimeisappliedtoprocessessupposedtocommunicatetocoordinator.Thistimeisaffectedbythepowerofanelectionalgorithmwhichgoesmorebyhigherspeedandlessbandwidthusage.Hence,morepowerfulalgorithmsapplylesswaittimeandappreciatesystemperformance.Meanwhile,thereshouldbeatrade-offbetweenthesafetyandpowerofanelectionalgorithminthesystem,becauseifweneedmorepowerfulalgorithms,wemustattendtosafetylesssinceitneedstoexchangemoreandmoremessagesbetweenproce。

8、ssorswhichcausetheweaknessofthealgorithm.Thisproblemisalsoknownaselectionproblem[3].Coordinatorsplayahugeroleinspreadareassuchasvideoconferencing,multiplayergames,recognizingprocessororcomputerfailurefordatatransferring,loadbalancing,andmanyotherswhichshowtheimportanceofthecoordinatorsoncemoreandconvincetheresearcherstogivemoreattentiontoit.2ADistributedFaultToleranceGlobalCoordinatorElectionAlgorithminUnreliableHighTrafficDistributedSystemsCopyright©2015MECSI.J.InformationTechnologyandComputerS。

9、cience,2015,03,1-11II.RELATEDWORKThisareawelcomedwiderangeofalgorithmswiththepassingoftime.Algorithmsdifferinspecificationssuchasnetworktopologies,thekindofcommunicationsbetweenprocesses,andalsosettingthenameoftheprocesses.Bully[4]andRing[5]aretwoclassiconesthatarereferredtoinmanypapers.Bullyalgorithmwhosenetworktopologyisusedinthispaperlauncheselectionwhenprocessesfindcoordinatorcrashed.Inthefirststepofelection,theseprocessessendElectionmessagestotheprocesseswithanupperprocessnumberthanthemselv。

10、es.ThenwhenprocessesreceiveElectionlabeledmessage,theywillrespondbyanOKmessage.However,ifnoprocessresponds,thesenderwouldintroduceitselfasthenewcoordinatortothesystembysendingaCoordinatormessagetothem.IfprocessP2repliesthesender,P2willsendanotherElectionmessageinthesystembyusingthepreviousprocedure.ThesestepscontinueuntilnootherprocesswithanuppernumberthanthesenderprocessexistsoranyotherOKmessagesfromtheuppernumberprocessesdidn’treceivetoinformer.Authorin[6]proposedaunif。