Computer Communications and Networks Forfurthervolumes: www.springer.com/series/4198 TheComputerCommunicationsandNetworksseriesisarangeoftextbooks,monographs and handbooks. It sets out to provide students, researchers and non-specialists alike with a sure grounding in current knowledge, together with comprehensible access to the latest developmentsincomputercommunicationsandnetworking. Emphasisisplacedonclearandexplanatorystylesthatsupportatutorialapproach,sothat eventhemostcomplexoftopicsispresentedinalucidandintelligiblemanner. K. Erciyes Distributed Graph Algorithms for Computer Networks K.Erciyes ComputerEngineeringDepartment IzmirUniversity Uckuyular,Izmir,Turkey SeriesEditor A.J.Sammes CentreforForensicComputing CranfieldUniversity Shrivenhamcampus Swindon,UK ISSN1617-7975 ComputerCommunicationsandNetworks ISBN978-1-4471-5172-2 ISBN978-1-4471-5173-9(eBook) DOI10.1007/978-1-4471-5173-9 SpringerLondonHeidelbergNewYorkDordrecht LibraryofCongressControlNumber:2013938954 ©Springer-VerlagLondon2013 Thisworkissubjecttocopyright.AllrightsarereservedbythePublisher,whetherthewholeorpartof thematerialisconcerned,specificallytherightsoftranslation,reprinting,reuseofillustrations,recitation, broadcasting,reproductiononmicrofilmsorinanyotherphysicalway,andtransmissionorinformation storageandretrieval,electronicadaptation,computersoftware,orbysimilarordissimilarmethodology nowknownorhereafterdeveloped.Exemptedfromthislegalreservationarebriefexcerptsinconnection with reviews or scholarly analysis or material supplied specifically for the purpose of being entered and executed on a computer system, for exclusive use by the purchaser of the work. Duplication of this publication or parts thereof is permitted only under the provisions of the Copyright Law of the Publisher’slocation,initscurrentversion,andpermissionforusemustalwaysbeobtainedfromSpringer. PermissionsforusemaybeobtainedthroughRightsLinkattheCopyrightClearanceCenter.Violations areliabletoprosecutionundertherespectiveCopyrightLaw. Theuseofgeneraldescriptivenames,registerednames,trademarks,servicemarks,etc.inthispublication doesnotimply,evenintheabsenceofaspecificstatement,thatsuchnamesareexemptfromtherelevant protectivelawsandregulationsandthereforefreeforgeneraluse. Whiletheadviceandinformationinthisbookarebelievedtobetrueandaccurateatthedateofpub- lication,neithertheauthorsnortheeditorsnorthepublishercanacceptanylegalresponsibilityforany errorsoromissionsthatmaybemade.Thepublishermakesnowarranty,expressorimplied,withrespect tothematerialcontainedherein. Printedonacid-freepaper SpringerispartofSpringerScience+BusinessMedia(www.springer.com) To the memories of Necdet Dogˇanata and Selçuk Erciyes, and all who believe in educa- tion Preface Distributedsystemsconsistingofanumberofautonomouscomputingelementscon- nectedoveracommunicationnetworkthatcooperatetoachievecommongoalshave shown an unprecedented growth in the last few decades, especially in the form of theGrid,theCloud,mobileadhocnetworks,andwirelesssensornetworks.Design ofalgorithmsforthesesystems,namelythedistributedalgorithms,hasbecomean importantresearchareaofcomputerscience,engineering,appliedmathematics,and otherdisciplinesastheyposedifferentandusuallymoredifficultproblemsthanthe sequentialalgorithms.Agraphcanbeusedtoconvenientlymodeladistributedsys- tem,anddistributedgraphalgorithmsorgraph-theoreticaldistributedalgorithms,in thecontextofthisbook,areconsideredasdistributedalgorithmsthatmakeuseof somepropertyofthegraphthatmodelsthedistributedsystemtosolveaproblemin suchsystems. Thisbookisaboutdistributedgraphalgorithmsasappliedtocomputernetworks withfocusonimplementationandhopefullywithoutmuchsacrificeonthetheory.It grewoutoftheneedIhavewitnessedwhileteachingdistributedsystemsandalgo- rithmscoursesinthelasttwodecadesorso.Themainobservationwasthatalthough thereweremanybooksondistributedalgorithms,graphtheory,andadhocnetworks separately,theredidnotseemtobeanybookwithdetailedfocusontheintersection of these three major areas of research. The second observation was the difficulty thestudentsfacedwhenimplementingdistributedalgorithmcodealthoughthecon- ceptsandtheideaofanalgorithminanabstractmannerwereperceivedrelatively morecomfortably.Forexample,whenandhowtosynchronizealgorithmsrunning ondifferentcomputingnodeswasoneofthemaindifficulties.Inthissense,wehave attemptedtoprovidealgorithmsinready-to-be-codedformatinmostcases,showing minordetailsexplicitlytoaidthedistributedalgorithmdesignerandimplementor. Thebookisdividedintothreeparts.Afterreviewingthebackground,PartIpro- vides a review of the fundamental and better known distributed graph algorithms. Part II describes the core concepts of distributed graph algorithms that have wide rangeofapplicationsincomputernetworksinanabstractmanner,withoutconsider- ingtheapplicationenvironment.However,inPartIII,wefocusourselvesonadhoc wirelessnetworksandshowhowsomeofthealgorithmswehaveinvestigatedcan bemodifiedforthisenvironment. vii viii Preface Thelayoutofeachchapteriskeptquiteuniformforeaseofreading.Eachchapter starts with an introduction describing the problem shortly by showing its possible applicationsincomputernetworks.Theproblemisthenstatedformally,andexam- plesareprovidedinmostofthecases.Wethenprovidealistofalgorithmsusually startingbyasequentialonetoaidunderstandingtheproblembetter.Thedistributed algorithms shown may be well established if they exist and sometimes algorithms that have been recently published as articles are described with examples if they haveprofoundeffectonthesolutionoftheproblem. Analgorithmisfirstintroducedconceptually,andthen,itspseudocodeisgiven and described in detail. We provide similar simple graph templates to show the steps of the implementation of the algorithm and then provide analysis of its time andmessagecomplexity.Proofofcorrectnessisgivenonlywhenthisdoesnotseem obviousor,onthecontrary,areferenceisgivenfortheproofifthisrequireslengthy analysis.ThechapterconcludesbytheChapterNotessection,whichusuallyempha- sizesmainpoints,comparesthedescribedalgorithms,andalsoprovidesacontem- porarybibliographicreviewofthetopicwithopenresearchareaswhereapplicable. Thisstyleisrepeatedthroughoutthebookforallchapters.Exercisesattheendof chaptersareusuallyintheformofsmallprogrammingprojectsinlinewiththemain goalofthebook,whichistodescribehowtoimplementdistributedalgorithms. There are few aspects of the book worth mentioning. Firstly, many self- stabilizing algorithms are included, some being very recent, for most of the top- ics covered in Part II. There are few algorithms, again in Part II, that are new and have not been published elsewhere. Also, an updated survey of the topic covered is provided for all chapters. Finally, a simple simulator we have designed, imple- mented, and used while teaching distributed algorithm courses is included as the finalchapter,anditssourcecodeisgiveninAppendixB. The intended audience for this book are the graduate students and researchers of computer science and mathematics and engineering or any person with basic backgroundindiscretemathematics,algorithms,andcomputernetworks. IwouldliketothankgraduatestudentsatEgeUniversity,UniversityofCalifornia Davis,CaliforniaStateUniversitySanMarcosandseniorstudentsatIzmirUniver- sity who have taken the distributed algorithms courses, sometimes under slightly different names, for their valuable feedback when parts of the material covered in thebookwaspresentedduringlectures.IwouldliketothankAysegulAlaybeyoglu, Deniz Cokuslu, Orhan Dagdeviren, and Jukka Suomela for their review of some chaptersandvaluablecomments.IwouldalsoliketothankSpringereditorsWayne Wheeler and Simon Rees for their continuous support during the course of this projectandDonatasAkmanavicˇiusforthefinaleditingprocess. Izmir,Turkey K.Erciyes Contents 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 DistributedSystems . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 DistributedComputingPlatforms . . . . . . . . . . . . . . . . . . 2 1.2.1 TheGrid . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2.2 CloudComputing . . . . . . . . . . . . . . . . . . . . . . 3 1.2.3 MobileAdhocNetworks . . . . . . . . . . . . . . . . . . 3 1.2.4 WirelessSensorNetworks . . . . . . . . . . . . . . . . . . 3 1.3 Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.4 SoftwareArchitecture . . . . . . . . . . . . . . . . . . . . . . . . 4 1.5 DesignIssues . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.5.1 Synchronization . . . . . . . . . . . . . . . . . . . . . . . 5 1.5.2 LoadBalancing . . . . . . . . . . . . . . . . . . . . . . . 6 1.5.3 FaultTolerance . . . . . . . . . . . . . . . . . . . . . . . 6 1.6 DistributedGraphAlgorithms . . . . . . . . . . . . . . . . . . . . 6 1.7 OrganizationoftheBook . . . . . . . . . . . . . . . . . . . . . . 7 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 PartI FundamentalAlgorithms 2 Graphs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.1 DefinitionofGraphs . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.1.1 SpecialGraphs . . . . . . . . . . . . . . . . . . . . . . . . 13 2.1.2 GraphRepresentations . . . . . . . . . . . . . . . . . . . . 14 2.2 Walks,PathsandCycles . . . . . . . . . . . . . . . . . . . . . . . 14 2.2.1 Diameter,Radius,Circumference,andGirth . . . . . . . . 15 2.3 Subgraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.4 Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.4.1 CutpointsandBridges . . . . . . . . . . . . . . . . . . . . 18 2.5 Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.5.1 MinimumSpanningTrees . . . . . . . . . . . . . . . . . . 19 ix x Contents 2.6 ChapterNotes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.6.1 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3 TheComputationalModel . . . . . . . . . . . . . . . . . . . . . . . . 23 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.2 MessagePassing . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.3 Finite-StateMachines . . . . . . . . . . . . . . . . . . . . . . . . 26 3.3.1 MooreMachineExample:ParityChecker. . . . . . . . . . 27 3.3.2 MealyMachineExample:DataLinkProtocolDesign . . . 27 3.4 Synchronization . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.5 CommunicationPrimitives . . . . . . . . . . . . . . . . . . . . . 30 3.6 ApplicationLevelSynchronization . . . . . . . . . . . . . . . . . 32 3.7 PerformanceMetrics . . . . . . . . . . . . . . . . . . . . . . . . . 34 3.7.1 TimeComplexity . . . . . . . . . . . . . . . . . . . . . . 34 3.7.2 BitComplexity. . . . . . . . . . . . . . . . . . . . . . . . 34 3.7.3 SpaceComplexity . . . . . . . . . . . . . . . . . . . . . . 34 3.7.4 MessageComplexity . . . . . . . . . . . . . . . . . . . . 34 3.8 ChapterNotes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 3.8.1 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 4 SpanningTreeConstruction . . . . . . . . . . . . . . . . . . . . . . . 39 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 4.2 TheFloodingAlgorithm . . . . . . . . . . . . . . . . . . . . . . . 39 4.2.1 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 4.3 Flooding-BasedAsynchronousSpanningTreeConstruction . . . . 41 4.3.1 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 4.4 AnAsynchronousAlgorithmwithTerminationDetection . . . . . 43 4.4.1 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 4.5 Tarry’sTraversalAlgorithm . . . . . . . . . . . . . . . . . . . . . 46 4.5.1 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 4.6 ConvergecastandBroadcastoveraSpanningTree . . . . . . . . . 47 4.7 ChapterNotes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 4.7.1 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 5 GraphTraversals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 5.2 Breadth-First-SearchAlgorithms . . . . . . . . . . . . . . . . . . 54 5.2.1 SynchronousBFSConstruction . . . . . . . . . . . . . . . 54 5.2.2 AsynchronousBFSConstruction . . . . . . . . . . . . . . 58 5.2.3 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 5.3 Depth-First-SearchAlgorithms . . . . . . . . . . . . . . . . . . . 60 5.3.1 TheClassicalDFSAlgorithm . . . . . . . . . . . . . . . . 61 5.3.2 Awerbuch’sDFSAlgorithm . . . . . . . . . . . . . . . . . 63