文件名称:
Design.And.Analysis.Of.Distributed.Algorithms
开发工具:
文件大小: 3mb
下载次数: 0
上传时间: 2008-02-19
详细说明： Design.And.Analysis.Of.Distributed.Algorithms
1. Distributed ComputingEnvironments............................... 1
1.1 Entities......................................................... 1
1.2 Communication................................................. 4
1.3 Axioms and Restrictions ......................................... 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 An Example:Broadcasting...................................... 10
1.6 States andEvents............................................... 14
1.6.1 Time and Events.......................................... 14
1.6.2 StatesandConfigurations.................................. 16
1.7 Problemsand Solutions ( )...................................... 17
1.8 Knowledge.................................................... 19
1.8.1 Levels ofKnowledge...................................... 19
1.8.2 Types ofKnowledge ...................................... 21
1.9 Technical Considerations........................................ 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,and Answers ............................... 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 Cost ofBroadcasting...................................... 30
2.1.3 Broadcastingin SpecialNetworks.......................... 32
vii
viii CONTENTS
2.2 Wake-Up...................................................... 36
2.2.1 GenericWake-Up......................................... 36
2.2.2 Wake-UpinSpecial Networks.............................. 37
2.3 Traversal...................................................... 41
2.3.1 Depth-FirstTraversal...................................... 42
2.3.2 Hacking( ) .............................................. 44
2.3.3 Traversal inSpecialNetworks.............................. 49
2.3.4 ConsiderationsonTraversal................................ 50
2.4 Practical Implications:Use aSubnet.............................. 51
2.5 Constructing a SpanningTree.................................... 52
2.5.1 SPT Construction with a SingleInitiator: Shout.............. 53
2.5.2 OtherSPTConstructions with Single Initiator................ 58
2.5.3 Considerationson the ConstructedTree..................... 60
2.5.4 Application:Better Traversal............................... 62
2.5.5 Spanning-TreeConstruction with
Multiple Initiators......................................... 62
2.5.6 ImpossibilityResult....................................... 63
2.5.7 SPT withInitialDistinctValues ............................ 65
2.6 ComputationsinTrees.......................................... 70
2.6.1 Saturation:ABasic Technique ............................. 71
2.6.2 MinimumFinding ........................................ 74
2.6.3 DistributedFunctionEvaluation............................ 76
2.6.4 FindingEccentricities..................................... 78
2.6.5 CenterFinding ........................................... 81
2.6.6 OtherComputations....................................... 84
2.6.7 Computing inRootedTrees................................ 85
2.7 Summary...................................................... 89
2.7.1 Summary ofProblems..................................... 89
2.7.2 Summary ofTechniques................................... 90
2.8 BibliographicalNotes........................................... 90
2.9 Exercises,Problems,and Answers ............................... 91
2.9.1 Exercises ................................................ 91
2.9.2 Problems................................................. 95
2.9.3 Answersto Exercises...................................... 95
3. Election.......................................................... 99
3.1 Introduction ................................................... 99
3.1.1 ImpossibilityResult....................................... 99
3.1.2 AdditionalRestrictions................................... 100
3.1.3 SolutionStrategies....................................... 101
3.2 ElectioninTrees.............................................. 102
3.3 ElectioninRings.............................................. 104
3.3.1 AlltheWay............................................. 105
CONTENTS ix
3.3.2 AsFarAsItCan......................................... 109
3.3.3 ControlledDistance...................................... 115
3.3.4 ElectoralStages ......................................... 122
3.3.5 StageswithFeedback.................................... 127
3.3.6 AlternatingSteps........................................ 130
3.3.7 UnidirectionalProtocols.................................. 134
3.3.8 Limits toImprovements ( )............................... 150
3.3.9 Summary andLessons ................................... 157
3.4 ElectioninMeshNetworks..................................... 158
3.4.1 Meshes................................................. 158
3.4.2 Tori.................................................... 161
3.5 ElectioninCubeNetworks..................................... 166
3.5.1 OrientedHypercubes..................................... 166
3.5.2 UnorientedHypercubes .................................. 174
3.6 ElectioninCompleteNetworks................................. 174
3.6.1 StagesandTerritory...................................... 174
3.6.2 SurprisingLimitation .................................... 177
3.6.3 HarvestingtheCommunication Power ..................... 180
3.7 ElectioninChordal Rings ( )................................... 183
3.7.1 Chordal Rings........................................... 183
3.7.2 Lower Bounds........................................... 184
3.8 UniversalElection Protocols ................................... 185
3.8.1 Mega-Merger ........................................... 185
3.8.2 AnalysisofMega-Merger................................. 193
3.8.3 YO-YO................................................. 199
3.8.4 Lower Bounds andEquivalences .......................... 209
3.9 BibliographicalNotes ......................................... 212
3.10 Exercises,Problems,and Answers.............................. 214
3.10.1 Exercises.............................................. 214
3.10.2 Problems .............................................. 220
3.10.3 AnswerstoExercises ................................... 222
4. MessageRoutingand Shortest Paths.............................. 225
4.1 Introduction.................................................. 225
4.2 ShortestPathRouting......................................... 226
4.2.1 GossipingtheNetwork Maps............................. 226
4.2.2 IterativeConstructionof Routing Tables................... 228
4.2.3 ConstructingShortest-Path SpanningTree................. 230
4.2.4 ConstructingAll-PairsShortest Paths ..................... 237
4.2.5 Min-HopRouting....................................... 240
4.2.6 Suboptimal Solutions: Routing Trees...................... 250
4.3 CopingwithChanges.......................................... 253
4.3.1 Adaptive Routing........................................ 253
x CONTENTS
4.3.2 Fault-TolerantTables..................................... 255
4.3.3 OnCorrectnessand Guarantees ........................... 259
4.4 Routing inStaticSystems: CompactTables...................... 261
4.4.1 TheSizeofRoutingTables............................... 261
4.4.2 IntervalRouting......................................... 262
4.5 BibliographicalNotes ......................................... 267
4.6 Exercises,Problems,and Answers.............................. 269
4.6.1 Exercises ............................................... 269
4.6.2 Problems ............................................... 274
4.6.3 Answersto Exercises..................................... 274
5. Distributed SetOperations....................................... 277
5.1 Introduction.................................................. 277
5.2 DistributedSelection .......................................... 279
5.2.1 Order Statistics.......................................... 279
5.2.2 Selection inaSmallData Set ............................. 280
5.2.3 Simple Case: SelectionAmongTwo Sites.................. 282
5.2.4 GeneralSelection Strategy:RankSelect.................... 287
5.2.5 Reducing the Worst Case:ReduceSelect.................... 292
5.3 SortingaDistributedSet....................................... 297
5.3.1 DistributedSorting....................................... 297
5.3.2 Special Case: Sortingona Ordered Line ................... 299
5.3.3 RemovingtheTopologicalConstraints:
CompleteGraph......................................... 303
5.3.4 BasicLimitations........................................ 306
5.3.5 EfficientSorting:SelectSort .............................. 309
5.3.6 UnrestrictedSorting...................................... 312
5.4 DistributedSetsOperations .................................... 315
5.4.1 OperationsonDistributed Sets............................ 315
5.4.2 Local Structure.......................................... 317
5.4.3 Local Evaluation( ) ..................................... 319
5.4.4 GlobalEvaluation ....................................... 322
5.4.5 OperationalCosts........................................ 323
5.5 BibliographicalNotes ......................................... 323
5.6 Exercises,Problems,and Answers.............................. 324
5.6.1 Exercises ............................................... 324
5.6.2 Problems ............................................... 329
5.6.3 Answersto Exercises..................................... 329
6. SynchronousComputations...................................... 333
6.1 SynchronousDistributedComputing............................ 333
6.1.1 FullySynchronousSystems............................... 333
CONTENTS xi
6.1.2 ClocksandUnitof Time.................................. 334
6.1.3 CommunicationDelaysandSize ofMessages .............. 336
6.1.4 OntheUnique Natureof SynchronousComputations........ 336
6.1.5 TheCostof Synchronous Protocols........................ 342
6.2 Communicators,Pipeline, and Transformers ..................... 343
6.2.1 Two-Party Communication ............................... 344
6.2.2 Pipeline................................................. 353
6.2.3 Transformers............................................ 357
6.3 Min-Findingand Election: Waiting and Guessing................. 360
6.3.1 Waiting................................................. 360
6.3.2 Guessing................................................ 370
6.3.3 Double Wait:Integrating WaitingandGuessing............. 378
6.4 SynchronizationProblems:Reset, Unison, and FiringSquad....... 385
6.4.1 Reset/Wake-up ......................................... 386
6.4.2 Unison ................................................. 387
6.4.3 FiringSquad............................................ 389
6.5 BibliographicalNotes ......................................... 391
6.6 Exercises,Problems,and Answers.............................. 392
6.6.1 Exercises ............................................... 392
6.6.2 Problems ............................................... 398
6.6.3 Answersto Exercises..................................... 400
7. Computing inPresence of Faults ................................. 408
7.1 Introduction.................................................. 408
7.1.1 FaultsandFailures....................................... 408
7.1.2 ModellingFaults ........................................ 410
7.1.3 TopologicalFactors...................................... 413
7.1.4 Fault Tolerance,Agreement, and Common Knowledge ...... 415
7.2 TheCrushing Impactof Failures................................ 417
7.2.1 Node Failures:Single-FaultDisaster....................... 417
7.2.2 Consequences ofthe SingleFaultDisaster.................. 424
7.3 LocalizedEntity Failures: Using Synchrony...................... 425
7.3.1 SynchronousConsensus withCrash Failures................ 426
7.3.2 SynchronousConsensuswith Byzantine Failures............ 430
7.3.3 LimittoNumberof ByzantineEntities for Agreement....... 435
7.3.4 FromBooleantoGeneralByzantine Agreement............. 438
7.3.5 Byzantine AgreementinArbitraryGraphs.................. 440
7.4 LocalizedEntity Failures:Using Randomization.................. 443
7.4.1 RandomActionsandCoin Flips........................... 443
7.4.2 RandomizedAsynchronousConsensus: Crash Failures ...... 444
7.4.3 ConcludingRemarks..................................... 449
xii CONTENTS
7.5 LocalizedEntity Failures: Using Fault Detection ................. 449
7.5.1 FailureDetectors and Their Properties ..................... 450
7.5.2 TheWeakestFailure Detector............................. 452
7.6 LocalizedEntity Failures: Pre-Execution Failures................. 454
7.6.1 PartialReliability........................................ 454
7.6.2 Example: ElectioninCompleteNetwork................... 455
7.7 LocalizedLink Failures........................................ 457
7.7.1 ATaleofTwoSynchronous Generals...................... 458
7.7.2 Computing WithFaulty Links............................. 461
7.7.3 ConcludingRemarks..................................... 466
7.7.4 Considerationson Localized Entity Failures................ 466
7.8 UbiquitousFaults ............................................. 467
7.8.1 CommunicationFaults and Agreement..................... 467
7.8.2 Limits toNumber of Ubiquitous Faults for Majority......... 468
7.8.3 UnanimityinSpite of UbiquitousFaults.................... 475
7.8.4 Tightness............................................... 485
7.9 BibliographicalNotes ......................................... 486
7.10 Exercises,Problems,and Answers.............................. 488
7.10.1 Exercises.............................................. 488
7.10.2 Problems.............................................. 492
7.10.3 AnswerstoExercises................................... 493
8. DetectingStableProperties....................................... 500
8.1 Introduction.................................................. 500
8.2 DeadlockDetection ........................................... 500
8.2.1 Deadlock............................................... 500
8.2.2 DetectingDeadlock: Wait-forGraph....................... 501
8.2.3 Single-RequestSystems.................................. 503
8.2.4 Multiple-Requests Systems............................... 505
8.2.5 DynamicWait-for Graphs................................ 512
8.2.6 OtherRequests Systems.................................. 516
8.3 GlobalTerminationDetection .................................. 518
8.3.1 ASimpleSolution: Repeated Termination Queries .......... 519
8.3.2 ImprovedProtocols: Shrink............................... 523
8.3.3 ConcludingRemarks..................................... 525
8.4 GlobalStablePropertyDetection ............................... 526
8.4.1 GeneralStrategy......................................... 526
8.4.2 Time Cuts and ConsistentSnapshots....................... 527
8.4.3 Computing A Consistent Snapshot......................... 530
8.4.4 Summary:PuttingAll Together ........................... 531
8.5 BibliographicalNotes ......................................... 532
CONTENTS xiii
8.6 Exercises,Problems,and Answers.............................. 534
8.6.1 Exercises ............................................... 534
8.6.2 Problems ............................................... 536
8.6.3 Answersto Exercises..................................... 538
9. ContinuousComputations ....................................... 541
9.1 Introduction.................................................. 541
9.2 Keeping VirtualTime.......................................... 542
9.2.1 VirtualTime andCausal Order............................ 542
9.2.2 CausalOrder:CounterClocks............................. 544
9.2.3 Complete CausalOrder:VectorClocks..................... 545
9.2.4 ConcludingRemarks..................................... 548
9.3 DistributedMutualExclusion................................... 549
9.3.1 TheProblem............................................ 549
9.3.2 ASimpleAndEfficientSolution .......................... 550
9.3.3 Traversingthe Network................................... 551
9.3.4 Managing aDistributed Queue............................ 554
9.3.5 DecentralizedPermissions................................ 559
9.3.6 MutualExclusioninCompleteGraphs: Quorum ............ 561
9.3.7 ConcludingRemarks..................................... 564
9.4 Deadlock: SystemDetection and Resolution ..................... 566
9.4.1 System Detection and Resolution.......................... 566
9.4.2 DetectionandResolution in Single-Request Systems........ 567
9.4.3 DetectionandResolution in Multiple-RequestsSystems..... 568
9.5 BibliographicalNotes ......................................... 569
9.6 Exercises,Problems,and Answers.............................. 570
9.6.1 Exercises ............................................... 570
9.6.2 Problems ............................................... 572
9.6.3 Answersto Exercises..................................... 573
Index ................................................................ 577 ...展开收缩
(系统自动生成,下载前可以参看下载内容)
下载文件列表
相关说明
- 本站资源为会员上传分享交流与学习,如有侵犯您的权益,请联系我们删除.
- 本站是交换下载平台，提供交流渠道，下载内容来自于网络，除下载问题外，其它问题请自行百度。
- 本站已设置防盗链，请勿用迅雷、QQ旋风等多线程下载软件下载资源，下载后用WinRAR最新版进行解压.
- 如果您发现内容无法下载，请稍后再次尝试；或者到消费记录里找到下载记录反馈给我们.
- 下载后发现下载的内容跟说明不相乎，请到消费记录里找到下载记录反馈给我们，经确认后退回积分.
- 如下载前有疑问，可以通过点击"提供者"的名字，查看对方的联系方式，联系对方咨询.
