Muutke küpsiste eelistusi

E-raamat: Design and Analysis of Distributed Algorithms

4.00/5 (12 hinnangut Goodreads-ist)
(Carleton University, Ottawa, Canada)
Teised raamatud teemal:
  • Formaat - PDF+DRM
  • Hind: 202,48 €*
  • * hind on lõplik, st. muud allahindlused enam ei rakendu
  • Lisa ostukorvi
  • Lisa soovinimekirja
  • See e-raamat on mõeldud ainult isiklikuks kasutamiseks. E-raamatuid ei saa tagastada.
  • Raamatukogudele
Design and Analysis of Distributed AlgorithmsSuurem pilt
Teised raamatud teemal:

DRM piirangud

  • Kopeerimine (copy/paste):

    ei ole lubatud

  • Printimine:

    ei ole lubatud

  • Kasutamine:

    Digitaalõiguste kaitse (DRM)
    Kirjastus on väljastanud selle e-raamatu krüpteeritud kujul, mis tähendab, et selle lugemiseks peate installeerima spetsiaalse tarkvara. Samuti peate looma endale  Adobe ID Rohkem infot siin. E-raamatut saab lugeda 1 kasutaja ning alla laadida kuni 6'de seadmesse (kõik autoriseeritud sama Adobe ID-ga).

    Vajalik tarkvara
    Mobiilsetes seadmetes (telefon või tahvelarvuti) lugemiseks peate installeerima selle tasuta rakenduse: PocketBook Reader (iOS / Android)

    PC või Mac seadmes lugemiseks peate installima Adobe Digital Editionsi (Seeon tasuta rakendus spetsiaalselt e-raamatute lugemiseks. Seda ei tohi segamini ajada Adober Reader'iga, mis tõenäoliselt on juba teie arvutisse installeeritud )

    Seda e-raamatut ei saa lugeda Amazon Kindle's. 

Santoro (computer science, Carleton U., Canada) describes the general principles and techniques for creating algorithms in a distributed (networked) computing environment that are intended to ensure both correctness and efficiency. Requiring standard undergraduate knowledge of operating systems and algorithms, his text contains nine chapters covering distribute computing environments, basic problems and protocols, election protocols, message routing and shortest paths, distributed set operations, synchronous computations, computing in the presence of faults, detecting stable properties, and continuous computations. Annotation ©2006 Book News, Inc., Portland, OR (booknews.com)

This text is based on a simple and fully reactive computational model that allows for intuitive comprehension and logical designs. The principles and techniques presented can be applied to any distributed computing environment (e.g., distributed systems, communication networks, data networks, grid networks, internet, etc.). The text provides a wealth of unique material for learning how to design algorithms and protocols perform tasks efficiently in a distributed computing environment.
Preface xiv
1. Distributed Computing Environments 1(28)
1.1 Entities
1(3)
1.2 Communication
4(1)
1.3 Axioms and Restrictions
4(5)
1.3.1 Axioms
5(1)
1.3.2 Restrictions
6(3)
1.4 Cost and Complexity
9(1)
1.4.1 Amount of Communication Activities
9(1)
1.4.2 Time
10(1)
1.5 An Example: Broadcasting
10(4)
1.6 States and Events
14(3)
1.6.1 Time and Events
14(2)
1.6.2 States and Configurations
16(1)
1.7 Problems and Solutions (*)
17(2)
1.8 Knowledge
19(3)
1.8.1 Levels of Knowledge
19(2)
1.8.2 Types of Knowledge
21(1)
1.9 Technical Considerations
22(3)
1.9.1 Messages
22(1)
1.9.2 Protocol
23(1)
1.9.3 Communication Mechanism
24(1)
1.10 Summary of Definitions
25(1)
1.11 Bibliographical Notes
25(1)
1.12 Exercises, Problems, and Answers
26(3)
1.12.1 Exercises and Problems
26(1)
1.12.2 Answers to Exercises
27(2)
2. Basic Problems And Protocols 29(70)
2.1 Broadcast
29(7)
2.1.1 The Problem
29(1)
2.1.2 Cost of Broadcasting
30(2)
2.1.3 Broadcasting in Special Networks
32(4)
2.2 Wake-Up
36(5)
2.2.1 Generic Wake-Up
36(1)
2.2.2 Wake-Up in Special Networks
37(4)
2.3 Traversal
41(10)
2.3.1 Depth-First Traversal
42(2)
2.3.2 Hacking (*)
44(5)
2.3.3 Traversal in Special Networks
49(1)
2.3.4 Considerations on Traversal
50(1)
2.4 Practical Implications: Use a Subnet
51(1)
2.5 Constructing a Spanning Tree
52(18)
2.5.1 SPT Construction with a Single Initiator: Shout
53(5)
2.5.2 Other SPT Constructions with Single Initiator
58(2)
2.5.3 Considerations on the Constructed Tree
60(2)
2.5.4 Application: Better Traversal
62(1)
2.5.5 Spanning-Tree Construction with Multiple Initiators
62(1)
2.5.6 Impossibility Result
63(2)
2.5.7 SPT with Initial Distinct Values
65(5)
2.6 Computations in Trees
70(19)
2.6.1 Saturation: A Basic Technique
71(3)
2.6.2 Minimum Finding
74(2)
2.6.3 Distributed Function Evaluation
76(2)
2.6.4 Finding Eccentricities
78(3)
2.6.5 Center Finding
81(3)
2.6.6 Other Computations
84(1)
2.6.7 Computing in Rooted Trees
85(4)
2.7 Summary
89(1)
2.7.1 Summary of Problems
89(1)
2.7.2 Summary of Techniques
90(1)
2.8 Bibliographical Notes
90(1)
2.9 Exercises, Problems, and Answers
91(8)
2.9.1 Exercises
91(4)
2.9.2 Problems
95(1)
2.9.3 Answers to Exercises
95(4)
3. Election 99(126)
3.1 Introduction
99(3)
3.1.1 Impossibility Result
99(1)
3.1.2 Additional Restrictions
100(1)
3.1.3 Solution Strategies
101(1)
3.2 Election in Trees
102(2)
3.3 Election in Rings
104(54)
3.3.1 All the Way
105(4)
3.3.2 As Far As It Can
109(6)
3.3.3 Controlled Distance
115(7)
3.3.4 Electoral Stages
122(5)
3.3.5 Stages with Feedback
127(3)
3.3.6 Alternating Steps
130(4)
3.3.7 Unidirectional Protocols
134(16)
3.3.8 Limits to Improvements (*)
150(7)
3.3.9 Summary and Lessons
157(1)
3.4 Election in Mesh Networks
158(8)
3.4.1 Meshes
158(3)
3.4.2 Tori
161(5)
3.5 Election in Cube Networks
166(8)
3.5.1 Oriented Hypercubes
166(8)
3.5.2 Unoriented Hypercubes
174(1)
3.6 Election in Complete Networks
174(9)
3.6.1 Stages and Territory
174(3)
3.6.2 Surprising Limitation
177(3)
3.6.3 Harvesting the Communication Power
180(3)
3.7 Election in Chordal Rings (*)
183(2)
3.7.1 Chordal Rings
183(1)
3.7.2 Lower Bounds
184(1)
3.8 Universal Election Protocols
185(27)
3.8.1 Mega-Merger
185(8)
3.8.2 Analysis of Mega-Merger
193(6)
3.8.3 YO-YO
199(10)
3.8.4 Lower Bounds and Equivalences
209(3)
3.9 Bibliographical Notes
212(2)
3.10 Exercises, Problems, and Answers
214(11)
3.10.1 Exercises
214(6)
3.10.2 Problems
220(2)
3.10.3 Answers to Exercises
222(3)
4. Message Routing and Shortest Paths 225(52)
4.1 Introduction
225(1)
4.2 Shortest Path Routing
226(27)
4.2.1 Gossiping the Network Maps
226(2)
4.2.2 Iterative Construction of Routing Tables
228(2)
4.2.3 Constructing Shortest-Path Spanning Tree
230(7)
4.2.4 Constructing All-Pairs Shortest Paths
237(3)
4.2.5 Min-Hop Routing
240(10)
4.2.6 Suboptimal Solutions: Routing Trees
250(3)
4.3 Coping with Changes
253(8)
4.3.1 Adaptive Routing
253(2)
4.3.2 Fault-Tolerant Tables
255(4)
4.3.3 On Correctness and Guarantees
259(2)
4.4 Routing in Static Systems: Compact Tables
261(6)
4.4.1 The Size of Routing Tables
261(1)
4.4.2 Interval Routing
262(5)
4.5 Bibliographical Notes
267(2)
4.6 Exercises, Problems, and Answers
269(8)
4.6.1 Exercises
269(5)
4.6.2 Problems
274(1)
4.6.3 Answers to Exercises
274(3)
5. Distributed Set Operations 277(56)
5.1 Introduction
277(2)
5.2 Distributed Selection
279(18)
5.2.1 Order Statistics
279(1)
5.2.2 Selection in a Small Data Set
280(2)
5.2.3 Simple Case: Selection Among Two Sites
282(5)
5.2.4 General Selection Strategy: RankSelect
287(5)
5.2.5 Reducing the Worst Case: ReduceSelect
292(5)
5.3 Sorting a Distributed Set
297(18)
5.3.1 Distributed Sorting
297(2)
5.3.2 Special Case: Sorting on a Ordered Line
299(4)
5.3.3 Removing the Topological Constraints: Complete Graph
303(3)
5.3.4 Basic Limitations
306(3)
5.3.5 Efficient Sorting: SelectSort
309(3)
5.3.6 Unrestricted Sorting
312(3)
5.4 Distributed Sets Operations
315(8)
5.4.1 Operations on Distributed Sets
315(2)
5.4.2 Local Structure
317(2)
5.4.3 Local Evaluation (*)
319(3)
5.4.4 Global Evaluation
322(1)
5.4.5 Operational Costs
323(1)
5.5 Bibliographical Notes
323(1)
5.6 Exercises, Problems, and Answers
324(9)
5.6.1 Exercises
324(5)
5.6.2 Problems
329(1)
5.6.3 Answers to Exercises
329(4)
6. Synchronous Computations 333(75)
6.1 Synchronous Distributed Computing
333(10)
6.1.1 Fully Synchronous Systems
333(1)
6.1.2 Clocks and Unit of Time
334(2)
6.1.3 Communication Delays and Size of Messages
336(1)
6.1.4 On the Unique Nature of Synchronous Computations
336(6)
6.1.5 The Cost of Synchronous Protocols
342(1)
6.2 Communicators, Pipeline, and Transformers
343(17)
6.2.1 Two-Party Communication
344(9)
6.2.2 Pipeline
353(4)
6.2.3 Transformers
357(3)
6.3 Min-Finding and Election: Waiting and Guessing
360(25)
6.3.1 Waiting
360(10)
6.3.2 Guessing
370(8)
6.3.3 Double Wait: Integrating Waiting and Guessing
378(7)
6.4 Synchronization Problems: Reset, Unison, and Firing Squad
385(6)
6.4.1 Reset/Wake-up
386(1)
6.4.2 Unison
387(2)
6.4.3 Firing Squad
389(2)
6.5 Bibliographical Notes
391(1)
6.6 Exercises, Problems, and Answers
392(16)
6.6.1 Exercises
392(6)
6.6.2 Problems
398(2)
6.6.3 Answers to Exercises
400(8)
7. Computing in Presence of Faults 408(92)
7.1 Introduction
408(9)
7.1.1 Faults and Failures
408(2)
7.1.2 Modeling Faults
410(3)
7.1.3 Topological Factors
413(2)
7.1.4 Fault Tolerance, Agreement, and Common Knowledge
415(2)
7.2 The Crushing Impact of Failures
417(8)
7.2.1 Node Failures: Single-Fault Disaster
417(7)
7.2.2 Consequences of the Single-Fault Disaster
424(1)
7.3 Localized Entity Failures: Using Synchrony
425(18)
7.3.1 Synchronous Consensus with Crash Failures
426(4)
7.3.2 Synchronous Consensus with Byzantine Failures
430(5)
7.3.3 Limit to Number of Byzantine Entities for Agreement
435(3)
7.3.4 From Boolean to General Byzantine Agreement
438(2)
7.3.5 Byzantine Agreement in Arbitrary Graphs
440(3)
7.4 Localized Entity Failures: Using Randomization
443(6)
7.4.1 Random Actions and Coin Flips
443(1)
7.4.2 Randomized Asynchronous Consensus: Crash Failures
444(5)
7.4.3 Concluding Remarks
449(1)
7.5 Localized Entity Failures: Using Fault Detection
449(5)
7.5.1 Failure Detectors and Their Properties
450(2)
7.5.2 The Weakest Failure Detector
452(2)
7.6 Localized Entity Failures: Preexecution Failures
454(3)
7.6.1 Partial Reliability
454(1)
7.6.2 Example: Election in Complete Network
455(2)
7.7 Localized Link Failures
457(10)
7.7.1 A Tale of Two Synchronous Generals
458(3)
7.7.2 Computing With Faulty Links
461(5)
7.7.3 Concluding Remarks
466(1)
7.7.4 Considerations on Localized Entity Failures
466(1)
7.8 Ubiquitous Faults
467(19)
7.8.1 Communication Faults and Agreement
467(1)
7.8.2 Limits to Number of Ubiquitous Faults for Majority
468(7)
7.8.3 Unanimity in Spite of Ubiquitous Faults
475(10)
7.8.4 Tightness
485(1)
7.9 Bibliographical Notes
486(2)
7.10 Exercises, Problems, and Answers
488(12)
7.10.1 Exercises
488(4)
7.10.2 Problems
492(1)
7.10.3 Answers to Exercises
493(7)
8. Detecting Stable Properties 500(41)
8.1 Introduction
500(1)
8.2 Deadlock Detection
500(18)
8.2.1 Deadlock
500(1)
8.2.2 Detecting Deadlock: Wait-for Graph
501(2)
8.2.3 Single-Request Systems
503(2)
8.2.4 Multiple-Requests Systems
505(7)
8.2.5 Dynamic Wait-for Graphs
512(4)
8.2.6 Other Requests Systems
516(2)
8.3 Global Termination Detection
518(8)
8.3.1 A Simple Solution: Repeated Termination Queries
519(4)
8.3.2 Improved Protocols: Shrink
523(2)
8.3.3 Concluding Remarks
525(1)
8.4 Global Stable Property Detection
526(6)
8.4.1 General Strategy
526(1)
8.4.2 Time Cuts and Consistent Snapshots
527(3)
8.4.3 Computing A Consistent Snapshot
530(1)
8.4.4 Summary: Putting All Together
531(1)
8.5 Bibliographical Notes
532(2)
8.6 Exercises, Problems, and Answers
534(7)
8.6.1 Exercises
534(2)
8.6.2 Problems
536(2)
8.6.3 Answers to Exercises
538(3)
9. Continuous Computations 541(36)
9.1 Introduction
541(1)
9.2 Keeping Virtual Time
542(7)
9.2.1 Virtual Time and Causal Order
542(2)
9.2.2 Causal Order: Counter Clocks
544(1)
9.2.3 Complete Causal Order: Vector Clocks
545(3)
9.2.4 Concluding Remarks
548(1)
9.3 Distributed Mutual Exclusion
549(17)
9.3.1 The Problem
549(1)
9.3.2 A Simple and Efficient Solution
550(1)
9.3.3 Traversing the Network
551(3)
9.3.4 Managing a Distributed Queue
554(5)
9.3.5 Decentralized Permissions
559(2)
9.3.6 Mutual Exclusion in Complete Graphs: Quorum
561(3)
9.3.7 Concluding Remarks
564(2)
9.4 Deadlock: System Detection and Resolution
566(3)
9.4.1 System Detection and Resolution
566(1)
9.4.2 Detection and Resolution in Single-Request Systems
567(1)
9.4.3 Detection and Resolution in Multiple-Requests Systems
568(1)
9.5 Bibliographical Notes
569(1)
9.6 Exercises, Problems, and Answers
570(7)
9.6.1 Exercises
570(2)
9.6.2 Problems
572(1)
9.6.3 Answers to Exercises
573(4)
Index 577


NICOLA SANTORO, PhD, is Professor of Computer Science at Carleton University. Dr. Santoro has been involved in distributed computing from the beginning of the field. He has contributed extensively on the algorithmic aspects, authoring many seminal papers. He is a founder of the main theoretical conferences in the field (PODC, DISC, SIROCCO). His current research is on distributed algorithms for mobile agents, autonomous mobile robots, and mobile sensor networks.
Lisainfo e-raamatute kohta Lisainfo e-raamatute kohta
Püsilink: https://www.kriso.ee/db/97804700726392e.html
Märksõnad: