Distributed algorithms
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 algorithm...
| Autor principal: | |
|---|---|
| Formato: | Libro electrónico |
| Idioma: | Inglés |
| Publicado: |
San Francisco :
Morgan Kaufmann Publishers
c1996.
|
| Edición: | 1st edition |
| Colección: | Morgan Kaufmann series in data management systems.
|
| Materias: | |
| Ver en Biblioteca Universitat Ramon Llull: | https://discovery.url.edu/permalink/34CSUC_URL/1im36ta/alma991009627592406719 |
Tabla de Contenidos:
- Front Cover; Distributed Algorithms; Copyright Page; Contents; Preface; Chapter 1. Introduction; 1.1 The Subject Matter; 1.2 Our Viewpoint; 1.3 Overview of Chapters 2-25; 1.4 Bibliographic Notes; 1.5 Notation; Part I: Synchronous Network Algorithms; Chapter 2. Modelling I: Synchronous Network Model; 2.1 Synchronous Network Systems; 2.2 Failures; 2.3 Inputs and Outputs; 2.4 Executions; 2.5 Proof Methods; 2.6 Complexity Measures; 2.7 Randomization; 2.8 Bibliographic Notes; Chapter 3. Leader Election in a Synchronous Ring; 3.1 The Problem; 3.2 Impossibility Result for Identical Processes
- 3.3 A Basic Algorithm3.4 An Algorithm with O (n log n) Communication Complexity; 3.5 Non-Comparison-Based Algorithms; 3.6 Lower Bound for Comparison-Based Algorithms; 3.7 Lower Bound for Non-Comparison-Based Algorithms; 3.8 Bibliographic Notes; 3.9 Exercises; Chapter 4. Algorithms in General Synchronous Networks; 4.1 Leader Election in a General Network; 4.2 Breadth-First Search; 4.3 Shortest Paths; 4.4 Minimum Spanning Tree; 4.5 Maximal Independent Set; 4.6 Bibliographic Notes; 4.7 Exercises; Chapter 5. Distributed Consensus with Link Failures
- 5.1 The Coordinated Attack Problem-Deterministic Version5.2 The Coordinated Attack Problem-Randomized Version; 5.3 Bibliographic Notes; 5.4 Exercises; Chapter 6. Distributed Consensus with Process Failures; 6.1 The Problem; 6.2 Algorithms for Stopping Failures; 6.3 Algorithms for Byzantine Failures; 6.4 Number of Processes for Byzantine Agreement; 6.5 Byzantine Agreement in General Graphs; 6.6 Weak Byzantine Agreement; 6.7 Number of Rounds with Stopping Failures; 6.8 Bibliographic Notes; 6.9 Exercises; Chapter 7. More Consensus Problems; 7.1 k-Agreement; 7.2 Approximate Agreement
- 7.3 The Commit Problem7.4 Bibliographic Notes; 7.5 Exercises; Part II: Asynchronous Algorithms; Chapter 8. Modelling II: Asynchronous System Model; 8.1 I/O Automata; 8.2 Operations on Automata; 8.3 Fairness; 8.4 Inputs and Outputs for Problems; 8.5 Properties and Proof Methods; 8.6 Complexity Measures; 8.7 Indistinguishable Executions; 8.8 Randomization; 8.9 Bibliographic Notes; 8.10 Exercises; Part IIA: Asynchronous Shared Memory Algorithms; Chapter 9. Modelling III: Asynchronous Shared Memory Model; 9.1 Shared Memory Systems; 9.2 Environment Model; 9.3 Indistinguishable States
- 9.4 Shared Variable Types9.5 Complexity Measures; 9.6 Failures; 9.7 Randomization; 9.8 Bibliographic Notes; 9.9 Exercises; Chapter 10. Mutual Exclusion; 10.1 Asynchronous Shared Memory Model; 10.2 The Problem; 10.3 Dijkstra's Mutual Exclusion Algorithm; 10.4 Stronger Conditions for Mutual Exclusion Algorithms; 10.5 Lockout-Free Mutual Exclusion Algorithms; 10.6 An Algorithm Using Single-Writer Shared Registers; 10.7 The Bakery Algorithm; 10.8 Lower Bound on the Number of Registers; 10.9 Mutual Exclusion Using Read-Modify-Write Shared Variables; 10.10 Bibliographic Notes; 10.11 Exercises
- Chapter 11. Resource Allocation
