Introduction to Reliable and Secure Distributed Programming

ISBN-13: 9783642152597 / Angielski / Twarda / 2011 / 367 str.

Christian Cachin

Opis

The scope of this second edition of the introduction to fundamental distributed programming abstractions has been extended to cover 'Byzantine fault tolerance'. It includes algorithms to implement these abstractions in vulnerable distributed systems.

Spis treści

1. Introduction. - 1.1 Motivation. -1.2 Distributed Programming Abstractions. 1.3 The End-to-End Argument. 1.4 Software Components. - 1.5 Classes of Algorithms. -1.6 Chapter Notes. 2. Basic Abstractions. - 2.1 Distributed Computation. - 2.2 Abstracting Processes. - 2.3 Cryptographic Abstractions. - 2.4 Abstracting Communication. - 2.5 Timing Assumptions. - 2.6 Abstracting Time. - 2.7 Distributed-System Models. - 2.8 Exercises. - 2.9 Solutions. - 2.10 Chapter Notes . - . - 3. Reliable Broadcast. - 3.1 Motivation. - 3.2 Best-Effort Broadcast. - 3.3 Regular Reliable Broadcast. - 3.4 Uniform Reliable Broadcast. - 3.5 Stubborn Broadcast. - 3.6 Logged Best-Effort Broadcast. - 3.7 Logged Uniform Reliable Broadcast. - 3.8 Probabilistic Broadcast. - 3.9 FIFO and Causal Broadcast. - 3.10 Byzantine Consistent Broadcast. - 3.11 Byzantine Reliable Broadcast. - 3.12 Byzantine Broadcast Channels. - 3.13 Exercises. - 3.14 Solutions. - 3.15 Chapter Notes . - . - 4. Shared Memory. - 4.1 Introduction. - 4.2 (1, N) Regular Register. - 4.3 (1, N) Atomic Register. - 4.4 (N, N) Atomic Register. - 4.5 (1, N) Logged Regular Register. - 4.6 (1,N) Byzantine Safe Register. - 4.7 (1, N) Byzantine Regular Register. - 4.8 (1,N) Byzantine Atomic Register. - 4.9 Exercises. - 4.10 Solutions. - 4.11 Chapter Notes . - . - 5. Consensus. - 5.1 Regular Consensus. - 5.2 Uniform Consensus. - 5.3 Uniform Consensus in the Fail-Noisy Model. - 5.4 Logged Consensus. - 5.5 Randomized Consensus. - 5.6 Byzantine Consensus. - 5.7 Byzantine Randomized Consensus. - 5.8 Exercises. - 5.9 Solutions. - 5.10 Chapter Notes . - . - 6. Consensus Variants. - 6.1 Total-Order Broadcast. - 6.2 Byzantine Total-Order Broadcast. - 6.3 Terminating Reliable Broadcast. - 6.4 Fast Consensus. - 6.5 Fast Byzantine Consensus. - 6.6 Non-blocking Atomic Commit. - 6.7 Group Membership. - 6.8 View-Synchronous Communication. - 6.9 Exercises. - 6.10 Solutions. - 6.11 Chapter Notes . - . - 7. Concluding Remarks. - 7.1 Implementation in Appia. - 7.2 Further Implementations. - 7.3 Further Reading

O autorze

Rachid Guerraoui is Professor in the School of Computer and Communication Sciences (LPD), at EPFL in Lausanne, Switzerland. Luís E. T. Rodrigues is Professor (Professor Catedrático) at the Departamento de Engenharia Informática, Instituto Superior Técnico (IST), at the Universidade Técnica de Lisboa in Portugal. Christian Cachin works at IBM Research in Zurich, Switzerland.

Blurb

In modern computing a program is usually distributed among several processes. The fundamental challenge when developing reliable and secure distributed programs is to support the cooperation of processes required to execute a common task, even when some of these processes fail. Failures may range from crashes to adversarial attacks by malicious processes.

Cachin, Guerraoui, and Rodrigues present an introductory description of fundamental distributed programming abstractions together with algorithms to implement them in distributed systems, where processes are subject to crashes and malicious attacks. The authors follow an incremental approach by first introducing basic abstractions in simple distributed environments, before moving to more sophisticated abstractions and more challenging environments. Each core chapter is devoted to one topic, covering reliable broadcast, shared memory, consensus, and extensions of consensus. For every topic, many exercises and their solutions enhance the understanding

This book represents the second edition of "Introduction to Reliable Distributed Programming". Its scope has been extended to include security against malicious actions by non-cooperating processes. This important domain has become widely known under the name "Byzantine fault-tolerance".