DESIGN AND ANALYSIS OF DISTRIBUTED ALGORITHMS Nicola Santoro CarletonUniversity,Ottawa,Canada WILEY-INTERSCIENCE A JOHN WILEY & SONS, INC., PUBLICATION DESIGN AND ANALYSIS OF DISTRIBUTED ALGORITHMS DESIGN AND ANALYSIS OF DISTRIBUTED ALGORITHMS Nicola Santoro CarletonUniversity,Ottawa,Canada WILEY-INTERSCIENCE A JOHN WILEY & SONS, INC., PUBLICATION Copyright©2007byJohnWiley&Sons,Inc.Allrightsreserved PublishedbyJohnWiley&Sons,Inc.,Hoboken,NewJersey PublishedsimultaneouslyinCanada Nopartofthispublicationmaybereproduced,storedinaretrievalsystem,ortransmittedinanyformor byanymeans,electronic,mechanical,photocopying,recording,scanning,orotherwise,exceptas permittedunderSection107or108ofthe1976UnitedStatesCopyrightAct,withouteithertheprior writtenpermissionofthePublisher,orauthorizationthroughpaymentoftheappropriateper-copyfeeto theCopyrightClearanceCenter,Inc.,222RosewoodDrive,Danvers,MA01923,(978)750-8400,fax (978)750-4470,oronthewebatwww.copyright.com.RequeststothePublisherforpermissionshould beaddressedtothePermissionsDepartment,JohnWiley&Sons,Inc.,111RiverStreet,Hoboken,NJ 07030,(201)748-6011,fax(201)748-6008,oronlineathttp://www.wiley.com/go/permission. LimitofLiability/DisclaimerofWarranty:Whilethepublisherandauthorhaveusedtheirbesteffortsin preparingthisbook,theymakenorepresentationsorwarrantieswithrespecttotheaccuracyor completenessofthecontentsofthisbookandspecificallydisclaimanyimpliedwarrantiesof merchantabilityorfitnessforaparticularpurpose.Nowarrantymaybecreatedorextendedbysales representativesorwrittensalesmaterials.Theadviceandstrategiescontainedhereinmaynotbesuitable foryoursituation.Youshouldconsultwithaprofessionalwhereappropriate.Neitherthepublishernor authorshallbeliableforanylossofprofitoranyothercommercialdamages,includingbutnotlimitedto special,incidental,consequential,orotherdamages. Forgeneralinformationonourotherproductsandservicesorfortechnicalsupport,pleasecontactour CustomerCareDepartmentwithintheUnitedStatesat(800)762-2974,outsidetheUnitedStatesat(317) 572-3993orfax(317)572-4002. Wileyalsopublishesitsbooksinavarietyofelectronicformats.Somecontentthatappearsinprintmay notbeavailableinelectronicformats.FormoreinformationaboutWileyproducts,visitourwebsiteat www.wiley.com. LibraryofCongressCataloging-in-PublicationData: Santoro,N.(Nicola),1951- Designandanalysisofdistributedalgorithms/byNicolaSantoro. p.cm.–(Wileyseriesonparallelanddistributedcomputing) Includesindex. ISBN-13:978-0-471-71997-7(cloth) ISBN-10:0-471-71997-8(cloth) 1. Electronicdataprocessing–Distributedprocessing. 2. Computeralgorithms. I. Title. II. Series. QA76.9.D5.S262007 005.1–dc22 2006011214 PrintedintheUnitedStatesofAmerica 10987654321 Tomyfavoritedistributedenvironment:Mychildren Monica,Noel,Melissa,Maya,Michela,Alvin. CONTENTS Preface .............................................................. xiv 1. DistributedComputingEnvironments............................... 1 1.1 Entities......................................................... 1 1.2 Communication................................................. 4 1.3 AxiomsandRestrictions......................................... 4 1.3.1 Axioms................................................... 5 1.3.2 Restrictions............................................... 6 1.4 CostandComplexity............................................ 9 1.4.1 AmountofCommunicationActivities........................ 9 1.4.2 Time.................................................... 10 1.5 AnExample:Broadcasting...................................... 10 1.6 StatesandEvents............................................... 14 1.6.1 TimeandEvents.......................................... 14 1.6.2 StatesandConfigurations.................................. 16 1.7 ProblemsandSolutions((cid:1))...................................... 17 1.8 Knowledge.................................................... 19 1.8.1 LevelsofKnowledge...................................... 19 1.8.2 TypesofKnowledge...................................... 21 1.9 TechnicalConsiderations........................................ 22 1.9.1 Messages................................................ 22 1.9.2 Protocol................................................. 23 1.9.3 CommunicationMechanism............................... 24 1.10 SummaryofDefinitions......................................... 25 1.11 BibliographicalNotes........................................... 25 1.12 Exercises,Problems,andAnswers............................... 26 1.12.1 ExercisesandProblems.................................. 26 1.12.2 AnswerstoExercises..................................... 27 2. BasicProblemsAndProtocols..................................... 29 2.1 Broadcast..................................................... 29 2.1.1 TheProblem............................................. 29 2.1.2 CostofBroadcasting...................................... 30 2.1.3 BroadcastinginSpecialNetworks.......................... 32 vii