Distributed Algorithms

by Lynch

• ISBN13: 9781558603486
• ISBN10: 1558603484
• eBook ISBN(s): 9780080504704
• Format: Hardcover
• Copyright: 1996-03-01
• Publisher: Elsevier Science
• More Book Details
• Purchase Benefits

Summary

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.

Table of Contents

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