A near-tight lower bound on the time complexity of

ANEAR-TIGHTLOWERBOUNDONTHETIMECOMPLEXITYOFDISTRIBUTEDMINIMUM-WEIGHTSPANNINGTREECONSTRUCTION∗DAVIDPELEG†ANDVITALYRUBINOVICH‡SIAMJ.COMPUT.c2000SocietyforIndustrialandAppliedMathematicsVol.30,No.5,pp.1427–1442Abstract.ThispaperpresentsalowerboundofΩ(D+√n/logn)onthetimerequiredforthedistributedconstructionofaminimum-weightspanningtree(MST)inweightedn-vertexnetworksofdiameterD=Ω(logn),intheboundedmessagemodel.Thisestablishestheasymptoticnear-optimalityofexistingtime-efficientdistributedalgorithmsfortheproblem,whosecomplexityisO(D+√nlog∗n).Keywords.distributedalgorithm,minimumweightspanningtree,lowerboundAMSsubjectclassifications.05C85,68Q22,68Q25PII.S00975397003697401.Introduction.Thestudyofdistributedalgorithmsforminimum-weightspan-ningtree(MST)constructionwasinitiatedbythepioneeringworkofGallager,Humb-let,andSpira[GHS83],whichintroducedabasicdistributedtechniquefortheproblemandpresentedamessage-optimalalgorithmwithtimecomplexityO(nlogn)onann-vertexnetwork.Thisresultwaslaterimprovedtoamessage-optimalalgorithmwithtimecomplexityO(n)byAwerbuch[A87].However,formanynaturaldistributednetworkproblems,theparametercon-trollingthetimecomplexityisnotthenumberofverticesbutratherthenetwork’sdiameterD,namely,themaximumdistancebetweenanytwovertices(measuredinhops).Thisholds,forexample,forleaderelectionandrelatedproblems[P90].ItiseasytoverifythatΩ(D)timeisrequiredfordistributedMSTconstructionintheworstcase.Moreformally,foreverytwointegersn≥2and1≤D≤n/2thereexistweightedn-vertexnetworksofdiameterD(say,basedona2D-vertexringwithn−2Dverticesattachedtoitasleaves)onwhichanydistributedMSTalgorithmwillrequireatleastDtime.Hence,anaturalquestioniswhetherO(D)-timealgorithmsexistfordistributedMSTconstructionaswell.Moregenerally,theproblemofdevisingo(n)(thoughpossi-blynotmessage-optimal)distributedalgorithmsforMSTconstructionwasintroducedin[GKP98].Clearly,intheextrememodelallowingthetransmissionofanunbounded-sizemessageonalinkinasingletimeunit(cf.[L92]),theproblemcanbetriviallysolvedintimeO(D)bycollectingtheentiregraph’stopologyandalltheedgeweightsintoacentralvertex,computinganMSTlocallyandbroadcastingtheresultthroughoutthenetwork.Theproblemthusbecomesinterestinginthemorerealistic,andrather∗ReceivedbytheeditorsMarch27,2000;acceptedforpublication(inrevisedform)August1,2000;publishedelectronicallyNovember8,2000.AnextendedabstracthasappearedinAnear-tightlowerboundonthetimecomplexityofdistributedMSTconstruction,inProceedingsofthe40thIEEESymposiumonFoundationsofComoputerScience,IEEEComputerSocietyPress,LosAlamitos,CA,1999,pp.253–261.†DepartmentofComputerScienceandAppliedMathematics,TheWeizmannInstituteofScience,Rehovot,76100Israel([e-mail]).TheworkofthisauthorwassupportedinpartbyagrantfromtheIsraelMinistryofScienceandArt.‡DepartmentofMathematicsandComputerScience,BarIlanUniversity,RamatGan,Israel([e-mail]).14271428DAVIDPELEGANDVITALYRUBINOVICHcommon,B-bounded-messagemodel(henceforthreferredtosimplyastheBmodel),inwhichmessagesizeisboundedbysomevalueB(usuallytakentobeeitherconstantorO(logn)),andavertexmaysendatmostonemessageoneachedgeateachtimeunit.Thealgorithmpresentedin[GKP98]fordistributedMSTconstructioninthismodel(withB=O(logn)-bitmessages)hastimecomplexityO(D+n
log∗n)for=ln6/ln3≈0.613.ThiswaslaterimprovedtoO(D+√nlog∗n)in[KP98].Similarboundswererecentlyobtainedbyususingotheralgorithmicmethods,butnoneofthosemethodswereabletobreakthe√n-timebarrier,indicatingthatdistributedMSTmightbeharderthanotherdistributednetworkproblemssuchasleaderelectionorbreadth-firstsearch(BFS)treeconstruction.Itisimportanttomentionthatthealgorithmsof[GHS83,A87,GKP98,KP98]discussedabovewereanalyzedunderthe(natural)assumptionthattheweightofeachedgecanberepresentedasanintegersmallenoughtobeincludedinasinglemessage.Thisassumptionisadoptedinthecurrentpaper.Thecurrentpaperconcernsestablishingtheasymptoticnear-optimalityofthealgorithmof[KP98],byshowingthat˜Ω(√n)isalowerbound1aswell,evenonlowdiameternetworks.Specifically,foranyintegersK,m≥2,weconstructafamilyofO(m2K)-vertexnetworksofdiameterD=O(Km)forwhichΩ(mK/(BK))timeisrequiredforconstructingaminimumspanningtreeintheBmodel.Fixingsomeposi-tiveintegerm≥2,wegetthatforeveryintegern≥1thereexistsafamilyofn-vertexnetworksofdiameterΘ(logn)forwhichMSTconstructionrequiresΩ(√n/(Blogn))timeintheBmodel.WhileitisnotclearthattheΩ(logn)limitationonthediametersforwhichthelowerboundholdsisessential,somelimitationmustapparentlyexist.Thisfollowsfromtheobservationthatthen-vertexcompletegraph(D=1)admitsasimpleO(logn)timedistributedMSTconstructionalgorithm.TowardsprovingthelowerboundondistributedMSTconstruction,wefirstes-tablishalowerboundonthetimecomplexityofaproblemreferredtoasthemailingproblem,whichcanbeinformallystatedasfollows.GivenaparticulartypeofgraphnamedFKm,forintegersm,K≥2,andtwoverticessandrinit,itisrequiredtodeliveranmK-bitstringXgeneratedinstor.ThegraphFKmhasn=O(m2K)verticesanddiameterO(Km),yetweshowthatthetimerequiredformailingfromstoronFKmintheBmodelisc