|
|
xiii | |
|
|
xxi | |
Acknowledgments |
|
xxiii | |
Preface |
|
xxv | |
References |
|
xxviii | |
|
1 Introduction to Dependable Distributed Computing |
|
|
1 | (14) |
|
1.1 Basic Concepts and Terminologies |
|
|
2 | (7) |
|
|
2 | (1) |
|
|
3 | (4) |
|
1.1.3 Dependability Attributes and Evaluation Metrics |
|
|
7 | (2) |
|
1.2 Means to Achieve Dependability |
|
|
9 | (6) |
|
|
9 | (1) |
|
1.2.2 Fault Detection and Diagnosis |
|
|
10 | (1) |
|
|
10 | (1) |
|
|
11 | (2) |
|
|
13 | (2) |
|
2 Logging and Checkpointing |
|
|
15 | (42) |
|
|
16 | (5) |
|
|
17 | (1) |
|
2.1.2 Process State and Global State |
|
|
17 | (3) |
|
2.1.3 Piecewise Deterministic Assumption |
|
|
20 | (1) |
|
|
20 | (1) |
|
|
21 | (1) |
|
2.2 Checkpoint-Based Protocols |
|
|
21 | (13) |
|
2.2.1 Uncoordinated Checkpointing |
|
|
21 | (2) |
|
2.2.2 Tamir and Sequin Global Checkpointing Protocol |
|
|
23 | (6) |
|
2.2.3 Chandy and Lamport Distributed Snapshot Protocol |
|
|
29 | (3) |
|
|
32 | (2) |
|
|
34 | (23) |
|
2.3.1 Pessimistic Logging |
|
|
36 | (9) |
|
2.3.2 Sender-Based Message Logging |
|
|
45 | (9) |
|
|
54 | (3) |
|
3 Recovery-Oriented Computing |
|
|
57 | (40) |
|
|
59 | (3) |
|
3.2 Fault Detection and Localization |
|
|
62 | (21) |
|
3.2.1 Component Interactions Modeling and Anomaly Detection |
|
|
66 | (4) |
|
3.2.2 Path Shapes Modeling and Root Cause Analysis |
|
|
70 | (4) |
|
3.2.3 Inference-Based Fault Diagnosis |
|
|
74 | (9) |
|
|
83 | (4) |
|
3.3.1 Microrebootable System Design Guideline |
|
|
84 | (1) |
|
3.3.2 Automatic Recovery with Microreboot |
|
|
85 | (1) |
|
3.3.3 Implications of the Microrebooting Technique |
|
|
86 | (1) |
|
3.4 Overcoming Operator Errors |
|
|
87 | (10) |
|
3.4.1 The Operator Undo Model |
|
|
88 | (1) |
|
3.4.2 The Operator Undo Framework |
|
|
89 | (4) |
|
|
93 | (4) |
|
4 Data and Service Replication |
|
|
97 | (44) |
|
|
99 | (6) |
|
|
101 | (2) |
|
4.1.2 Implementation of Service Replication |
|
|
103 | (2) |
|
|
105 | (6) |
|
4.3 Optimistic Replication |
|
|
111 | (20) |
|
|
112 | (2) |
|
4.3.2 Establish Ordering among Operations |
|
|
114 | (3) |
|
4.3.3 State Transfer Systems |
|
|
117 | (4) |
|
4.3.4 Operation Transfer System |
|
|
121 | (5) |
|
|
126 | (5) |
|
|
131 | (10) |
|
|
134 | (1) |
|
4.4.2 Implications of Enabling Partition Tolerance |
|
|
135 | (3) |
|
|
138 | (3) |
|
5 Group Communication Systems |
|
|
141 | (52) |
|
|
143 | (3) |
|
5.2 Sequencer Based Group Communication System |
|
|
146 | (14) |
|
|
147 | (4) |
|
|
151 | (8) |
|
5.2.3 Proof of Correctness |
|
|
159 | (1) |
|
5.3 Sender Based Group Communication System |
|
|
160 | (26) |
|
5.3.1 Total Ordering Protocol |
|
|
161 | (7) |
|
5.3.2 Membership Change Protocol |
|
|
168 | (9) |
|
|
177 | (7) |
|
5.3.4 The Flow Control Mechanism |
|
|
184 | (2) |
|
5.4 Vector Clock Based Group Communication System |
|
|
186 | (7) |
|
|
191 | (2) |
|
6 Consensus and the Paxos Algorithms |
|
|
193 | (46) |
|
6.1 The Consensus Problem |
|
|
194 | (2) |
|
|
196 | (10) |
|
6.2.1 Algorithm for Choosing a Value |
|
|
196 | (2) |
|
6.2.2 Algorithm for Learning a Value |
|
|
198 | (1) |
|
6.2.3 Proof of Correctness |
|
|
198 | (2) |
|
6.2.4 Reasoning of the Paxos Algorithm |
|
|
200 | (6) |
|
|
206 | (4) |
|
6.3.1 Checkpointing and Garbage Collection |
|
|
207 | (1) |
|
6.3.2 Leader Election and View Change |
|
|
208 | (2) |
|
|
210 | (11) |
|
|
211 | (3) |
|
|
214 | (7) |
|
|
221 | (8) |
|
|
222 | (1) |
|
6.5.2 Collision Recovery, Quorum Requirement, and Value Selection Rule |
|
|
223 | (6) |
|
6.6 Implementations of the Paxos Family Algorithms |
|
|
229 | (10) |
|
6.6.1 Hard Drive Failures |
|
|
230 | (1) |
|
6.6.2 Multiple Coordinators |
|
|
230 | (1) |
|
|
231 | (4) |
|
6.6.4 Limited Disk Space for Logging |
|
|
235 | (1) |
|
|
236 | (3) |
|
7 Byzantine Fault Tolerance |
|
|
239 | (50) |
|
7.1 The Byzantine Generals Problem |
|
|
240 | (15) |
|
|
241 | (3) |
|
7.1.2 The Oral Message Algorithms |
|
|
244 | (10) |
|
7.1.3 Proof of Correctness for the Oral Message Algorithms |
|
|
254 | (1) |
|
7.2 Practical Byzantine Fault Tolerance |
|
|
255 | (16) |
|
|
256 | (1) |
|
7.2.2 Overview of the PBFT Algorithm |
|
|
257 | (2) |
|
7.2.3 Normal Operation of PBFT |
|
|
259 | (2) |
|
|
261 | (1) |
|
|
262 | (3) |
|
7.2.6 Proof of Correctness |
|
|
265 | (1) |
|
|
266 | (5) |
|
7.3 Fast Byzantine Agreement |
|
|
271 | (1) |
|
7.4 Speculative Byzantine Fault Tolerance |
|
|
271 | (18) |
|
7.4.1 The Agreement Protocol |
|
|
273 | (4) |
|
7.4.2 The View Change Protocol |
|
|
277 | (5) |
|
7.4.3 The Checkpointing Protocol |
|
|
282 | (1) |
|
7.4.4 Proof of Correctness |
|
|
282 | (2) |
|
|
284 | (5) |
|
8 Application-Aware Byzantine Fault Tolerance |
|
|
289 | (44) |
|
8.1 High Throughput BFT Systems: Networked File Systems |
|
|
293 | (3) |
|
8.2 Exploiting Deep Application Semantics: Web Services Coordination |
|
|
296 | (20) |
|
8.2.1 The Web Services Atomic Transactions Standard |
|
|
297 | (3) |
|
8.2.2 The Web Services Business Activity Standard |
|
|
300 | (3) |
|
8.2.3 Customized BFT Solutions for WS-AT and WS-BA Coordination |
|
|
303 | (13) |
|
8.3 Application Nondeterminism Control |
|
|
316 | (17) |
|
8.3.1 Classification of Application Nondeterminism |
|
|
317 | (7) |
|
8.3.2 Controlling VPRE Type of Nondeterminism |
|
|
324 | (1) |
|
8.3.3 Controlling NPRE Type of Nondeterminism |
|
|
325 | (1) |
|
8.3.4 Controlling VPOST Type of Nondeterminism |
|
|
326 | (2) |
|
8.3.5 Controlling NPOST Type of Nondeterminism |
|
|
328 | (2) |
|
|
330 | (3) |
Index |
|
333 | |