Muutke küpsiste eelistusi

E-raamat: Distributed Algorithms

Teised raamatud teemal:
  • Formaat - PDF+DRM
  • Hind: 111,15 €*
  • * 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.
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. 

This introduction to the field of distributed algorithms presents a collection of the most significant algorithms and impossibility results in a simple automata-theoretic setting. Problems covered include resource allocation, communication, consensus among distributed processes, data consistency, deadlock detection, leader election, and global snapshots. Material is organized by the system model first by the timing model and then by the interprocess communication mechanism. Annotation c. by Book News, Inc., Portland, Or.

In Distributed Algorithms, Nancy Lynch provides a blueprint for designing, implementing, and analyzing distributed algorithms. She directs her book at a wide audience, including students, programmers, system designers, and researchers.



Distributed Algorithms contains the most significant algorithms and impossibility results in the area, all in a simple automata-theoretic setting. The algorithms are proved correct, and their complexity is analyzed according to precisely defined complexity measures. The problems covered include resource allocation, communication, consensus among distributed processes, data consistency, deadlock detection, leader election, global snapshots, and many others.



The material is organized according to the system model—first by the timing model and then by the interprocess communication mechanism. The material on system models is isolated in separate chapters for easy reference.



The presentation is completely rigorous, yet is intuitive enough for immediate comprehension. This book familiarizes readers with important problems, algorithms, and impossibility results in the area: readers can then recognize the problems when they arise in practice, apply the algorithms to solve them, and use the impossibility results to determine whether problems are unsolvable. The book also provides readers with the basic mathematical tools for designing new algorithms and proving new impossibility results. In addition, it teaches readers how to reason carefully about distributed algorithms—to model them formally, devise precise specifications for their required behavior, prove their correctness, and evaluate their performance with realistic measures.

Preface xix
1 Introduction
1(14)
1.1 The Subject Matter
1(3)
1.2 Our Viewpoint
4(2)
1.3 Overview of
Chapters 2-25
6(7)
1.4 Bibliographic Notes
13(1)
1.5 Notation
14(1)
Part I Synchronous Network Algorithms 15(182)
2 Modelling I: Synchronous Network Model
17(8)
2.1 Synchronous Network Systems
17(2)
2.2 Failures
19(1)
2.3 Inputs and Outputs
20(1)
2.4 Executions
20(1)
2.5 Proof Methods
21(1)
2.6 Complexity Measures
21(1)
2.7 Randomization
22(1)
2.8 Bibliographic Notes
23(2)
3 Leader Election in a Synchronous Ring
25(26)
3.1 The Problem
25(2)
3.2 Impossibility Result for Identical Processes
27(1)
3.3 A Basic Algorithm
27(4)
3.4 An Algorithm with O (n log n) Communication Complexity
31(4)
3.5 Non-Comparison-Based Algorithms
35(3)
3.5.1 The TimeSlice Algorithm
35(1)
3.5.2 The VariableSpeeds Algorithm
36(2)
3.6 Lower Bound for Comparison-Based Algorithms
38(6)
3.7 Lower Bound for Non-Comparison-Based Algorithms(*)
44(1)
3.8 Bibliographic Notes
46(1)
3.9 Exercises
47(4)
4 Algorithms in General Synchronous Networks
51(30)
4.1 Leader Election in a General Network
52(5)
4.1.1 The Problem
52(1)
4.1.2 A Simple Flooding Algorithm
52(2)
4.1.3 Reducing the Communication Complexity
54(3)
4.2 Breadth-First Search
57(4)
4.2.1 The Problem
57(1)
4.2.2 A Basic Breadth-First Search Algorithm
58(2)
4.2.3 Applications
60(1)
4.3 Shortest Paths
61(2)
4.4 Minimum Spanning Tree
63(8)
4.4.1 The Problem
63(1)
4.4.2 Basic Theory
64(2)
4.4.3 The Algorithm
66(5)
4.5 Maximal Independent Set
71(5)
4.5.1 The Problem
71(1)
4.5.2 A Randomized Algorithm
71(3)
4.5.3 Analysis(*)
74(2)
4.6 Bibliographic Notes
76(1)
4.7 Exercises
77(4)
5 Distributed Consensus with Link Failures
81(18)
5.1 The Coordinated Attack Problem--Deterministic Version
82(4)
5.2 The Coordinated Attack Problem--Randomized Version
86(9)
5.2.1 Formal Modelling
87(1)
5.2.2 An Algorithm
88(5)
5.2.3 A Lower Bound on Disagreement
93(2)
5.3 Bibliographic Notes
95(1)
5.4 Exercises
95(4)
6 Distributed Consensus with Process Failures
99(62)
6.1 The Problem
100(2)
6.2 Algorithms for Stopping Failures
102(14)
6.2.1 A Basic Algorithm
103(2)
6.2.2 Reducing the Communication
105(3)
6.2.3 Exponential Information Gathering Algorithms
108(7)
6.2.4 Byzantine Agreement with Authentication
115(1)
6.3 Algorithms for Byzantine Failures
116(13)
6.3.1 An Example
117(2)
6.3.2 EIG Algorithm for Byzantine Agreement
119(4)
6.3.3 General Byzantine Agreement Using Binary Byzantine Agreement
123(2)
6.3.4 Reducing the Communication Cost
125(4)
6.4 Number of Processes for Byzantine Agreement
129(6)
6.5 Byzantine Agreement in General Graphs
135(4)
6.6 Weak Byzantine Agreement
139(3)
6.7 Number of Rounds with Stopping Failures
142(10)
6.8 Bibliographic Notes
152(1)
6.9 Exercises
153(8)
7 More Consensus Problems
161(36)
7.1 k-Agreement
161(16)
7.1.1 The Problem
162(1)
7.1.2 An Algorithm
162(2)
7.1.3 Lower Bound(*)
164(3)
7.2 Approximate Agreement
177(5)
7.3 The Commit Problem
182(10)
7.3.1 The Problem
182(2)
7.3.2 Two-Phase Commit
184(1)
7.3.3 Three-Phase Commit
185(4)
7.3.4 Lower Bound on the Number of Messages
189(3)
7.4 Bibliographic Notes
192(1)
7.5 Exercises
192(5)
Part II Asynchronous Algorithms 197(38)
8 Modelling II: Asynchronous System Model
199(36)
8.1 I/O Automata
200(6)
8.2 Operations on Automata
206(6)
8.2.1 Composition
207(5)
8.2.2 Hiding
212(1)
8.3 Fairness
212(3)
8.4 Inputs and Outputs for Problems
215(1)
8.5 Properties and Proof Methods
216(12)
8.5.1 Invariant Assertions
216(1)
8.5.2 Trace Properties
216(2)
8.5.3 Safety and Liveness Properties
218(3)
8.5.4 Compositional Reasoning
221(3)
8.5.5 Hierarchical Proofs
224(4)
8.6 Complexity Measures
228(1)
8.7 Indistinguishable Executions
229(1)
8.8 Randomization
229(1)
8.9 Bibliographic Notes
230(1)
8.10 Exercises
231(4)
Part IIA Asynchronous Shared Memory Algorithms 235(220)
9 Modelling III: Asynchronous Shared Memory Model
237(18)
9.1 Shared Memory Systems
237(4)
9.2 Environment Model
241(3)
9.3 Indistinguishable States
244(1)
9.4 Shared Variable Types
244(6)
9.5 Complexity Measures
250(1)
9.6 Failures
251(1)
9.7 Randomization
251(1)
9.8 Bibliographic Notes
251(1)
9.9 Exercises
252(3)
10 Mutual Exclusion
255(80)
10.1 Asynchronous Shared Memory Model
256(3)
10.2 The Problem
259(6)
10.3 Dijkstra's Mutual Exclusion Algorithm
265(11)
10.3.1 The Algorithm
265(4)
10.3.2 A Correctness Argument
269(3)
10.3.3 An Assertional Proof of the Mutual Exclusion Condition
272(2)
10.3.4 Running Time
274(2)
10.4 Stronger Conditions for Mutual Exclusion Algorithms
276(2)
10.5 Lockout-Free Mutual Exclusion Algorithms
278(16)
10.5.1 A Two-Process Algorithm
278(5)
10.5.2 An n-Process Algorithm
283(6)
10.5.3 Tournament Algorithm
289(5)
10.6 An Algorithm Using Single-Writer Shared Registers
294(2)
10.7 The Bakery Algorithm
296(4)
10.8 Lower Bound on the Number of Registers
300(9)
10.8.1 Basic Facts
301(1)
10.8.2 Single-Writer Shared Variables
302(1)
10.8.3 Multi-Writer Shared Variables
302(7)
10.9 Mutual Exclusion Using Read-Modify-Write Shared Variables
309(17)
10.9.1 The Basic Problem
310(1)
10.9.2 Bounded Bypass
311(8)
10.9.3 Lockout-Freedom
319(3)
10.9.4 A Simulation Proof
322(4)
10.10 Bibliographic Notes
326(1)
10.11 Exercises
327(8)
11 Resource Allocation
335(36)
11.1 The Problem
336(5)
11.1.1 Explicit Resource Specifications and Exclusion Specifications
336(1)
11.1.2 Resource-Allocation Problem
337(2)
11.1.3 Dining Philosophers Problem
339(2)
11.1.4 Restricted Form of Solutions
341(1)
11.2 Nonexistence of Symmetric Dining Philosophers Algorithms
341(3)
11.3 Right-Left Dining Philosophers Algorithms
344(10)
11.3.1 Waiting Chains
344(2)
11.3.2 The Basic Algorithm
346(3)
11.3.3 A Generalization
349(5)
11.4 Randomized Dining Philosophers Algorithm(*)
354(13)
11.4.1 The Algorithm(*)
354(3)
11.4.2 Correctness(*)
357(10)
11.5 Bibliographic Notes
367(1)
11.6 Exercises
367(4)
12 Consensus
371(26)
12.1 The Problem
372(4)
12.2 Agreement Using Read/Write Shared Memory
376(11)
12.2.1 Restrictions
376(1)
12.2.2 Terminology
376(1)
12.2.3 Bivalent Initializations
377(1)
12.2.4 Impossibility for Wait-Free Termination
378(5)
12.2.5 Impossibility for Single-Failure Termination
383(4)
12.3 Agreement Using Read-Modify-Write Shared Memory
387(1)
12.4 Other Types of Shared Memory
388(1)
12.5 Computability in Asynchronous Shared Memory Systems(*)
389(2)
12.6 Bibliographic Notes
391(1)
12.7 Exercises
392(5)
13 Atomic Objects
397(58)
13.1 Definitions and Basic Results
398(22)
13.1.1 Atomic Object Definition
398(10)
13.1.2 A Canonical Wait-Free Atomic Object Automation
408(3)
13.1.3 Composition of Atomic Objects
411(1)
13.1.4 Atomic Objects versus Shared Variables
411(8)
13.1.5 A Sufficient Condition for Showing Atomicity
419(1)
13.2 Implementing Read-Modify-Write Atomic Objects in Terms of Read/Write Variables
420(1)
13.3 Atomic Snapshots of Shared Memory
421(13)
13.3.1 The Problem
422(1)
13.3.2 An Algorithm with Unbounded Variables
423(5)
13.3.3 An Algorithm with Bounded Variables(*)
428(6)
13.4 Read/Write Atomic Objects
434(15)
13.4.1 The Problem
434(1)
13.4.2 Another Lemma for Showing Atomicity
434(2)
13.4.3 An Algorithm with Unbounded Variables
436(4)
13.4.4 A Bounded Algorithm for Two Writers
440(7)
13.4.5 An Algorithm Using Snapshots
447(2)
13.5 Bibliographic Notes
449(1)
13.6 Exercises
450(5)
Part IIB Asynchronous Network Algorithms 455(278)
14 Modelling IV: Asynchronous Network Model
457(18)
14.1 Send/Receive Systems
457(9)
14.1.1 Processes
458(1)
14.1.2 Send/Receive Channels
458(6)
14.1.3 Asynchronous Send/Receive Systems
464(1)
14.1.4 Properties of Send/Receive Systems with Reliable FIFO Channels
464(2)
14.1.5 Complexity Measures
466(1)
14.2 Broadcast Systems
466(3)
14.2.1 Processes
466(1)
14.2.2 Broadcast Channel
467(1)
14.2.3 Asynchronous Broadcast Systems
468(1)
14.2.4 Properties of Broadcast Systems with Reliable Broadcast Channels
468(1)
14.2.5 Complexity Measures
469(1)
14.3 Multicast Systems
469(2)
14.3.1 Processes
469(1)
14.3.2 Multicast Channel
470(1)
14.3.3 Asynchronous Multicast Systems
471(1)
14.4 Bibliographic Notes
471(1)
14.5 Exercises
471(4)
15 Basic Asynchronous Network Algorithms
475(56)
15.1 Leader Election in a Ring
475(20)
15.1.1 The LCR Algorithm
476(6)
15.1.2 The HS Algorithm
482(1)
15.1.3 The Peterson Leader-Election Algorithm
482(4)
15.1.4 A Lower Bound on Communication Complexity
486(9)
15.2 Leader Election in an Arbitrary Network
495(1)
15.3 Spanning Tree Construction, Broadcast and Convergecast
496(5)
15.4 Breadth-First Search and Shortest' Paths
501(8)
15.5 Minimum Spanning Tree
509(14)
15.5.1 Problem Statement
509(1)
15.5.2 The Synchronous Algorithm: Review
510(1)
15.5.3 The GHS Algorithm: Outline
511(2)
15.5.4 In More Detail
513(4)
15.5.5 Specific Messages
517(2)
15.5.6 Complexity Analysis
519(2)
15.5.7 Proving Correctness for the GHS Algorithm
521(1)
15.5.8 A Simpler "Synchronous" Strategy
522(1)
15.5.9 Application to Leader Election
523(1)
15.6 Bibliographic Notes
523(1)
15.7 Exercises
524(7)
16 Synchronizers
531(34)
16.1 The Problem
532(3)
16.2 The Local Synchronizer
535(6)
16.3 The Safe Synchronizer
541(5)
16.3.1 Front-End Automata
542(2)
16.3.2 Channel Automata
544(1)
16.3.3 The Safe Synchronizer
544(1)
16.3.4 Correctness
545(1)
16.4 Safe Synchronizer Implementations
546(7)
16.4.1 Synchronizer Alpha
546(1)
16.4.2 Synchronizer Beta
547(1)
16.4.3 Synchronizer Gamma
548(5)
16.5 Applications
553(2)
16.5.1 Leader Election
553(1)
16.5.2 Breadth-First Search
554(1)
16.5.3 Shortest Paths
554(1)
16.5.4 Broadcast and Acknowledgment
555(1)
16.5.5 Maximal Independent Set
555(1)
16.6 Lower Bound on Time
555(5)
16.7 Bibliographic Notes
560(1)
16.8 Exercises
560(5)
17 Shared Memory versus Networks
565(26)
17.1 Transformations from the Shared Memory Model to the Network Model
566(16)
17.1.1 The Problem
566(1)
17.1.2 Strategies Assuming No Failures
567(8)
17.1.3 An Algorithm Tolerating Process Failures
575(5)
17.1.4 An Impossibility Result for n/2 Failures
580(2)
17.2 Transformations from the Network Model to the Shared Memory Model
582(4)
17.2.1 Send/Receive Systems
583(2)
17.2.2 Broadcast Systems
585(1)
17.2.3 Impossibility of Agreement in Asynchronous Networks
586(1)
17.3 Bibliographic Notes
586(1)
17.4 Exercises
587(4)
18 Logical Time
591(26)
18.1 Logical Time for Asynchronous Networks
591(5)
18.1.1 Send/Receive Systems
592(2)
18.1.2 Broadcast Systems
594(2)
18.2 Adding Logical Time to Asynchronous Algorithms
596(4)
18.2.1 Advancing the Clock
597(1)
18.2.2 Delaying Future Events
598(2)
18.3 Applications
600(10)
18.3.1 Banking System
600(4)
18.3.2 Global Snapshots
604(2)
18.3.3 Simulating a Single State Machine
606(4)
18.4 Transforming Real-Time Algorithms to Logical-Time Algorithms(*)
610(2)
18.5 Bibliographic Notes
612(1)
18.6 Exercises
612(5)
19 Global Snapshots and Stable Properties
617(58)
19.1 Termination-Detection for Diffusing Algorithms
618(7)
19.1.1 The Problem
618(1)
19.1.2 The DijkstraScholten Algorithm
619(6)
19.2 Consistent Global Snapshots
625(11)
19.2.1 The Problem
625(2)
19.2.2 The Chandy-Lamport Algorithm
627(5)
19.2.3 Applications
632(4)
19.3 Bibliographic Notes
636(1)
19.4 Exercises
637(4)
20 Network Resource Allocation
641(28)
20.1 Mutual Exclusion
641(12)
20.1.1 The Problem
641(2)
20.1.2 Simulating Shared Memory
643(1)
20.1.3 Circulating Token Algorithm
643(3)
20.1.4 An Algorithm Based on LogicalTimeME Algorithm
646(3)
20.1.5 Improvements to the LogicalTimeME Algorithm
649(4)
20.2 General Resource Allocation
653(11)
20.2.1 The Problem
653(1)
20.2.2 Coloring Algorithm
654(1)
20.2.3 Algorithms Based on Logical Time
655(1)
20.2.4 Acyclic Digraph Algorithm
656(2)
20.2.5 Drinking Philosophers(*)
658(6)
20.3 Bibliographic Notes
664(1)
20.4 Exercises
664(5)
21 Asynchronous Networks with Process Failures
669(22)
21.1 The Network Model
670(1)
21.2 Impossibility of Agreement in the Presence of Faults
671(1)
21.3 A Randomized Algorithm
672(5)
21.4 Failure Detectors
677(4)
21.5 k-Agreement
681(1)
21.6 Approximate Agreement
682(2)
21.7 Computability in Asynchronous Networks(*)
684(1)
21.8 Bibliographic Notes
685(1)
21.9 Exercises
686(5)
22 Data Link Protocols
691(42)
22.1 The Problem
692(1)
22.2 Stenning's Protocol
693(4)
22.3 Alternating Bit Protocol
697(6)
22.4 Bounded Tag Protocols Tolerating Reordering
703(12)
22.4.1 Impossibility Result for Reordering and Duplication
704(2)
22.4.2 A Bounded Tag Protocol Tolerating Loss and Reordering
706(6)
22.4.3 Nonexistence of Efficient Protocols Tolerating Loss and Reordering
712(3)
22.5 Tolerating Crashes
715(13)
22.5.1 A Simple Impossibility Result
716(2)
22.5.2 A Harder Impossibility Result
718(3)
22.5.3 A Practical Protocol
721(7)
22.6 Bibliographic Notes
728(1)
22.7 Exercises
729(4)
Part III Partially Synchronous Algorithms 733(96)
23 Partially Synchronous System Models
735(38)
23.1 MMT Timed Automata
736(8)
23.1.1 Basic Definitions
736(5)
23.1.2 Operations
741(3)
23.2 General Timed Automata
744(12)
23.2.1 Basic Definitions
745(6)
23.2.2 Transforming MMT Automata into General Timed Automata
751(3)
23.2.3 Operations
754(2)
23.3 Properties and Proof Methods
756(12)
23.3.1 Invariant Assertions
757(2)
23.3.2 Timed Trace Properties
759(1)
23.3.3 Simulations
760(8)
23.4 Modelling Shared Memory and Network Systems
768(1)
23.4.1 Shared Memory Systems
768(1)
23.4.2 Networks
768(1)
23.5 Bibliographic Notes
769(1)
23.6 Exercises
770(3)
24 Mutual Exclusion with Partial Synchrony
773(22)
24.1 The Problem
773(1)
24.2 A Single-Register Algorithm
774(10)
24.3 Resilience to Timing Failures
784(4)
24.4 Impossibility Results
788(1)
24.4.1 A Lower Bound on the Time
788(1)
24.4.2 Impossibility Result for Eventual Time Bounds(*)
789(1)
24.5 Bibliographic Notes
790(1)
24.6 Exercises
791(4)
25 Consensus with Partial Synchrony
795(34)
25.1 The Problem
795(1)
25.2 A Failure Detector
796(2)
25.3 Basic Results
798(5)
25.3.1 Upper Bound
798(3)
25.3.2 Lower Bound
801(2)
25.4 An Efficient Algorithm
803(7)
25.4.1 The Algorithm
803(2)
25.4.2 Safety Properties
805(1)
25.4.3 Liveness and Complexity
806(4)
25.5 A Lower Bound Involving the Timing Uncertainty(*)
810(8)
25.6 Other Results(*)
818(5)
25.6.1 Synchronous Processes, Asynchronous Channels(*)
818(1)
25.6.2 Asynchronous Processes, Synchronous Channels(*)
819(1)
25.6.3 Eventual Time Bounds(*)
819(4)
25.7 Postscript
823(1)
25.8 Bibliographic Notes
823(1)
25.9 Exercises
824(5)
Bibliography 829(28)
Index 857


About the author:Nancy A. Lynch is a professor of electrical engineering and computer science at MIT and heads MIT's Theory of Distributed Systems research group. She is the author of numerous research articles about distributed algorithms and impossibility results, and about formal modeling and verification of distributed systems.
Lisainfo e-raamatute kohta Lisainfo e-raamatute kohta
Püsilink: https://www.kriso.ee/db/97800805047042e.html
Märksõnad: