Stability of continuous-time distributed consensus

arXiv:math/0409010v1[math.OC]1Sep2004Stabilityofcontinuous-timedistributedconsensusalgorithmsLucMoreau∗†GhentUniversityBelgiumFebruary1,2008AbstractWestudythestabilitypropertiesoflineartime-varyingsystemsincon-tinuoustimewhosesystemmatrixisMetzlerwithzerorowsums.Thisclassofsystemsarisesnaturallyinthecontextofdistributeddecisionprob-lems,coordinationandrendezvoustasksandsynchronizationproblems.Theequilibriumsetcontainsallstateswithidenticalstatecomponents.Wepresentsufficientconditionsguaranteeinguniformexponentialstabil-ityofthisequilibriumset,implyingthatallstatecomponentsconvergetoacommonvalueastimegrowsunbounded.Furthermoreitisshownthatthisconvergenceresultisrobustwithrespecttoanarbitrarydelay,pro-videdthatthedelayaffectsonlytheoff-diagonaltermsinthedifferentialequation.Keywords:distributedalgorithms,coordination,synchronization,stabil-ity,communicationdelay1INTRODUCTIONWeconsideracoordinationproblemforanetworkofsystemsinteractingvialocalcoupling.Eachindividualsysteminthenetworkisassumedtohavesimpleintegratordynamics.Thenetworkcouplingisallowedtobetime-dependentandnon-bidirectional.Weshowthat,underverymildconditions,theindividual∗TheauthorwasaPostdoctoralFellowoftheFundforScientificResearch-Flanders(Bel-gium),associatedtotheSYsTeMSResearchGroup,Electricalenergy,SystemsandAutoma-tionDepartment,GhentUniversity,9052Ghent,Belgium.TheauthoriscurrentlyemployedatSidmar,Ghent,Belgium.ThispaperpresentsresearchresultsoftheBelgianProgrammeonInteruniversityAttractionPoles,initiatedbytheBelgianFederalSciencePolicyOffice.Thescientificresponsibilityrestswithitsauthor.†ResearchperformedwhilevisitingtheDepartmentofMechanicalEngineering,TechnicalUniversityofEindhoven,5600MBEindhoven,TheNetherlands.1statevariablesofthesystemsinthenetworkconvergetoacommonvalueastimegrowsunbounded.Eachsysteminthenetworkmaybeakinematicmodelofafullyactuatedvehicleandthecorrespondingstatevariablemayrepresentitspositioninone-dimensionalspace.Thecoordinationproblemthenaskstosteerallvehiclestoacommonrendezvousposition—whichisnotapriorigivenbutwilldependonthevehicles’initialpositions.Thestrategystudiedhereisofadistributednature.Noleaderorexternalcoordinatorisassumedtobepresent.Insteadthedesiredformationisformedasaconsequenceofthelocalinteractionbetweentheindividualvehicles.Othervehiclemodelsmaybeconceived.Eachsysteminthenetworkcould,forexample,modelaparticlemovingatconstantspeedintwo-dimensionalspace,itsdirectionofmotionbeingrepresentedbythesystem’sstatevariableasin[1,2].Moregeneralmodelsarepossible,wheretheindividualstatevariablesarenotnecessarilyscalarbutvector-valued,representingtheconfigurationofavehicleinthree-dimensionalspace.Suchhigherdimensionalextensions,however,willnotbeconsideredinthepresentpaper.Wereferto[3,4,5,6,7,8,9,10,11,12,13,14]forthestudyofmoregeneralswarmingmodelsandcollectivemotionpatterns.Inadifferentcontextofsynchronization[15]eachsysteminthenetworkcouldrepresentanoscillatorandtheindividualsystem’sstatevariablecoulddeterminetheoscillationphase.Inthiscasetheconsensusproblemcorrespondstoasynchronizationproblemfortheoscillators.Thepresentmodelmaythenbeinterpretedasalinearizedversionofthemorecomplexsynchronizationmodelsstudied,forexample,in[16,17,18].Finally,theindividualsystems’statevariablescouldrepresentanabstractdecisionvariable.Inthiscasethenetworkequationsrepresentadistributedconsensusalgorithmforthepurposeofdistributeddecisionmakingasin[19,20,21,22,23].Distributedagreementproblemshavealonghistory;see,forexample,thebook[24,section4.6]andthepaper[25].Thedistributedconsensusalgorithmthatweconsiderherehasreceivedcon-siderableattentionintherecentliterature[2,10,19,20,21,22,23,26,27].Comparedwiththesereferences,amaincontributionofthepresentpaperisthatwedonotimposerestrictiveassumptionsonthenetworkcouplingtopol-ogy(otherthanaverymildconnectivityassumption).Weallowforgeneralnon-bidirectionalandtime-dependentcommunicationpatterns.Unidirectionalcommunicationisimportantinpracticalapplicationsandcaneasilybeincorpo-rated,forexample,viabroadcasting.Also,sensedinformationflowwhichplaysacentralroleinschoolingandflockingistypicallynotbidirectional.Inaddition,wedonotexcludeloopsinthecouplingtopology.Thismeansthat,typically,weareconsideringleaderlesscoordinationratherthanaleader-followerapproach.(Leaderlesscoordinationisalsoconsidered,forexample,in[28,29,30,31,32]).Finally,weallowfortime-dependentcommunicationpatternswhichareimpor-tantifwewanttotakeintoaccountlinkfailureandlinkcreation,reconfigurablenetworksandnearestneighborcoupling.Thepresentworkmaybeseenasacontinuationoftheauthor’sprevi-ouswork[33,34].Weextendthediscrete-timeresultsofthosepapersto-2wardscontinuous-timedistributedalgorithms.Furthermore,weshowthatthecontinuous-timeresultspresentedherearerobustwithrespecttoanarbitrarycommunicationdelay,providedthatthedelayaffectsonlythosevariablesthatareactuallybeingcommunicatedbetweendistinctsystemsinthenetwork.Eventhoughwerestrictattentiontolinearsystemsinthepresentpaper,itisinstruc-tivetoobservethatourapproachisofaninherentlynonlinearnature,withanon-quad