Introduction to Reliable Distributed Programming

by Guerraoui, Rachid; Rodrigues, Luis

• ISBN13: 9783540288459
• ISBN10: 3540288457
• Format: Hardcover
• Copyright: 2006-04-15
• Publisher: Springer-Verlag New York Inc

Summary

In modern computing, a program usually executes on several processes. The fundamental problem when devising algorithms for distributed computing is the need to achieve some form of cooperation of these processes on a common task.Guerraoui and Rodrigues present an introductory description of distributed programming abstractions and of the algorithms used to implement them in different distributed environments. They follow an incremental approach by first introducing basic elements of distributed computing, on top of which they then build more sophisticated abstractions. After the introduction, every chapter is devoted to one problem class, covering reliable delivery, shared memory, broadcast, commitment, and communication.This textbook comes with a companion set of running examples implemented in Java, which can be used by students to get a better understanding of many implementation details. All chapters together make up for a full course on distributed computing. In addition, the book can also be used as a complete reference of the basic building blocks for reliable distributed applications.

Table of Contents

1. Introduction	1	(24)
1.1 Motivation	1	(2)
1.2 Distributed Programming Abstractions	3	(4)
1.2.1 Inherent Distribution	4	(2)
1.2.2 Distribution as an Artifact	6	(1)
1.3 The End-to-End Argument	7	(1)
1.4 Software Components	8	(7)
1.4.1 Composition Model	8	(2)
1.4.2 Programming Interface	10	(1)
1.4.3 Modules	11	(2)
1.4.4 Classes of Algorithms	13	(2)
1.5 Hands-On	15	(10)
1.5.1 Print Module	16	(2)
1.5.2 BoundedPrint Module	18	(2)
1.5.3 Composing Modules	20	(5)
2. Basic Abstractions	25	(44)
2.1 Distributed Computation	26	(3)
2.1.1 Processes and Messages	26	(1)
2.1.2 Automata and Steps	26	(2)
2.1.3 Liveness and Safety	28	(1)
2.2 Abstracting Processes	29	(5)
2.2.1 Process Failures	29	(1)
2.2.2 Arbitrary Faults and Omissions	30	(1)
2.2.3 Crashes	30	(2)
2.2.4 Recoveries	32	(2)
2.3 Abstracting Communication	34	(9)
2.3.1 Link Failures	35	(1)
2.3.2 Fair-Loss Links	36	(1)
2.3.3 Stubborn Links	36	(2)
2.3.4 Perfect Links	38	(2)
2.3.5 Logged Perfect Links	40	(1)
2.3.6 On the Link Abstractions	41	(2)
2.4 Timing Assumptions	43	(4)
2.4.1 Asynchronous System	43	(2)
2.4.2 Synchronous System	45	(1)
2.4.3 Partial Synchrony	46	(1)
2.5 Abstracting Time	47	(11)
2.5.1 Failure Detection	47	(1)
2.5.2 Perfect Failure Detection	48	(2)
2.5.3 Leader Election	50	(1)
2.5.4 Eventually Perfect Failure Detection	51	(3)
2.5.5 Eventual Leader Election	54	(4)
2.6 Distributed System Models	58	(2)
2.6.1 Combining Abstractions	58	(1)
2.6.2 Measuring Performance	59	(1)
2.7 Hands-On	60	(4)
2.7.1 Sendable Event	60	(1)
2.7.2 Message and Extended Message	61	(1)
2.7.3 Fair-Loss Point-to-Point Links	62	(1)
2.7.4 Perfect Point-to-Point Links	62	(1)
2.7.5 Perfect Failure Detector	63	(1)
2.8 Exercises	64	(1)
2.9 Solutions	65	(2)
2.10 Historical Notes	67	(2)
3. Reliable Broadcast	69	(66)
3.1 Motivation	69	(2)
3.1.1 Client-Server Computing	69	(1)
3.1.2 Multi-participant Systems	70	(1)
3.2 Best-Effort Broadcast	71	(1)
3.2.1 Specification	71	(1)
3.2.2 Fail-Silent Algorithm: Basic Broadcast	71	(1)
3.3 Regular Reliable Broadcast	72	(4)
3.3.1 Specification	73	(1)
3.3.2 Fail-Stop Algorithm: Lazy Reliable Broadcast	73	(1)
3.3.3 Fail-Silent Algorithm: Eager Reliable Broadcast	74	(2)
3.4 Uniform Reliable Broadcast	76	(5)
3.4.1 Specification	77	(1)
3.4.2 Fail-Stop Algorithm: All-Ack Uniform Reliable Broadcast	78	(1)
3.4.3 Fail-Silent Algorithm: Majority-Ack Uniform Reliable Broadcast	79	(2)
3.5 Stubborn Broadcast	81	(2)
3.5.1 Overview	81	(1)
3.5.2 Specification	81	(1)
3.5.3 Fail-Recovery Algorithm: Basic Stubborn Broadcast	82	(1)
3.6 Logged Best-Effort Broadcast	83	(1)
3.6.1 Specification	83	(1)
3.6.2 Fail-Recovery Algorithm: Logged Basic Broadcast	83	(1)
3.7 Logged Uniform Reliable Broadcast	84	(2)
3.7.1 Specification	85	(1)
3.7.2 Fail-Recovery Algorithm: Logged Majority-Ack URB	86	(1)
3.8 Randomized Broadcast	86	(8)
3.8.1 The Scalability of Reliable Broadcast	87	(1)
3.8.2 Epidemic Dissemination	88	(1)
3.8.3 Specification	88	(1)
3.8.4 Randomized Algorithm: Eager Probabilistic Broadcast	89	(2)
3.8.5 Randomized Algorithm: Lazy Probabilistic Broadcast	91	(3)
3.9 Causal Broadcast	94	(7)
3.9.1 Overview	94	(1)
3.9.2 Specifications	94	(2)
3.9.3 Fail-Silent Algorithm: No-Waiting Causal Broadcast	96	(2)
3.9.4 Fail-Stop Extension: Garbage Collecting the Causal Past	98	(1)
3.9.5 Fail-Silent Algorithm: Waiting Causal Broadcast	98	(3)
3.10 Hands-On	101	(24)
3.10.1 Basic Broadcast	101	(2)
3.10.2 Lazy Reliable Broadcast	103	(3)
3.10.3 All-Ack Uniform Reliable Broadcast	106	(2)
3.10.4 Majority-Ack URB	108	(1)
3.10.5 Probabilistic Reliable Broadcast	109	(3)
3.10.6 No-Waiting Causal Broadcast	112	(4)
3.10.7 No-Waiting Causal Broadcast with Garbage Collection	116	(6)
3.10.8 Waiting Causal Broadcast	122	(3)
3.11 Exercises	125	(2)
3.12 Solutions	127	(6)
3.13 Historical Notes	133	(2)
4. Shared Memory	135	(54)
4.1 Introduction	135	(5)
4.1.1 Sharing Information in a Distributed System	135	(1)
4.1.2 Register Overview	136	(3)
4.1.3 Completeness and Precedence	139	(1)
4.2 (1, N) Regular Register	140	(6)
4.2.1 Specification	140	(1)
4.2.2 Fail-Stop Algorithm: Read-One Write-All Regular Register	140	(3)
4.2.3 Fail-Silent Algorithm: Majority Voting Regular Register	143	(3)
4.3 (1, N) Atomic Register	146	(11)
4.3.1 Specification	146	(3)
4.3.2 Transformation: From (1, N) Regular to (1, N) Atomic	149	(4)
4.3.3 Fail-Stop Algorithm: Read-Impose Write-All (1, N) Atomic Register	153	(2)
4.3.4 Fail-Silent Algorithm: Read-Impose Write-Majority (1, N) Atomic Register	155	(2)
4.4 (N, N) Atomic Register	157	(7)
4.4.1 Multiple Writers	157	(1)
4.4.2 Specification	158	(1)
4.4.3 Transformation: From (1, N) Atomic to (N, N) Atomic Registers	159	(3)
4.4.4 Fail-Stop Algorithm: Read-Impose Write-Consult (N, N) Atomic Register	162	(1)
4.4.5 Fail-Silent Algorithm: Read-Impose Write-Consult-Majority (N, N) Atomic Register	162	(2)
4.5 (1, N) Logged Regular Register	164	(7)
4.5.1 Precedence in the Fail-Recovery Model	165	(1)
4.5.2 Specification	166	(1)
4.5.3 Fail-Recovery Algorithm: Logged-Majority-Voting	167	(4)
4.6 Hands-On	171	(10)
4.6.1 (1, N) Regular Register	171	(3)
4.6.2 (1, N) Atomic Register	174	(4)
4.6.3 (N, N) Atomic Register	178	(3)
4.7 Exercises	181	(1)
4.8 Solutions	182	(5)
4.9 Historical Notes	187	(2)
5. Consensus	189	(44)
5.1 Regular Consensus	189	(6)
5.1.1 Specification	189	(1)
5.1.2 Fail-Stop Algorithm: Flooding Consensus	190	(3)
5.1.3 Fail-Stop Algorithm: Hierarchical Consensus	193	(2)
5.2 Uniform Consensus	195	(4)
5.2.1 Specification	195	(1)
5.2.2 Fail-Stop Algorithm: Flooding Uniform Consensus	196	(1)
5.2.3 Fail-Stop Algorithm: Hierarchical Uniform Consensus	197	(2)
5.3 Abortable Consensus	199	(7)
5.3.1 Overview	199	(1)
5.3.2 Specification	200	(1)
5.3.3 Fail-Silent Algorithm: RW Abortable Consensus	201	(3)
5.3.4 Fail-Noisy Algorithm: From Abortable Consensus to Consensus	204	(2)
5.4 Logged Abortable Consensus and Logged Consensus	206	(2)
5.4.1 Fail-Recovery Algorithm: Logged Abortable Consensus	206	(2)
5.5 Randomized Consensus	208	(4)
5.5.1 Specification	208	(1)
5.5.2 Randomized Algorithm: Probabilistic Consensus	209	(3)
5.6 Hands-On	212	(13)
5.6.1 Flooding Regular Consensus Protocol	212	(4)
5.6.2 Hierarchical Regular Consensus Protocol	216	(3)
5.6.3 Flooding Uniform Consensus	219	(3)
5.6.4 Hierarchical Uniform Consensus	222	(3)
5.7 Exercises	225	(1)
5.8 Solutions	226	(6)
5.9 Historical Notes	232	(1)
6. Consensus Variants	233	(54)
6.1 Total Order Broadcast	233	(6)
6.1.1 Overview	233	(1)
6.1.2 Specifications	234	(2)
6.1.3 Algorithm: Consensus-Based Total Order Broadcast	236	(3)
6.2 Terminating Reliable Broadcast	239	(3)
6.2.1 Overview	239	(1)
6.2.2 Specification	240	(1)
6.2.3 Algorithm: Consensus-Based TRB	240	(2)
6.3 Non-blocking Atomic Commit	242	(4)
6.3.1 Overview	242	(1)
6.3.2 Specification	243	(1)
6.3.3 Algorithm: Consensus-Based NBAC	244	(2)
6.4 Group Membership	246	(3)
6.4.1 Overview	246	(1)
6.4.2 Specification	247	(1)
6.4.3 Algorithm: Consensus-Based Group Membership	248	(1)
6.5 View Synchronous Communication	249	(9)
6.5.1 Overview	249	(1)
6.5.2 Specification	250	(1)
6.5.3 Algorithm: TRB-Based View Synchronous Broadcast	251	(4)
6.5.4 Algorithm: Consensus-Based Uniform View Synchronous Broadcast	255	(3)
6.6 Hands-On	258	(17)
6.6.1 Uniform Total Order Broadcast	258	(5)
6.6.2 Consensus-Based Non-blocking Atomic Commit	263	(3)
6.6.3 Consensus-Based Group Membership	266	(3)
6.6.4 TRB-Based View Synchrony	269	(6)
6.7 Exercises	275	(1)
6.8 Solutions	276	(9)
6.9 Historical Notes	285	(2)
7. Concluding Remarks	287	(9)
7.1 Further Implementations	287	(2)
7.2 Further Readings	289	(7)
Bibliography	296	(1)
Index	297