| Description |
1 online resource (1 volume) : illustrations |
| Bibliography |
Includes bibliographical references and index. |
| Contents |
Half Title; Title Page; Copyright; Dedication; Contents; Acknowledgments; Preface; 1 Introduction; 1.1 Concurrency Everywhere; 1.1.1 Distributed computing and topology; 1.1.2 Our approach; 1.1.3 Two ways of thinking about concurrency; 1.2 Distributed Computing; 1.2.1 Processes and protocols; 1.2.2 Communication; 1.2.3 Failures; 1.2.4 Timing; 1.2.5 Tasks; 1.3 Two Classic Distributed Computing Problems; 1.3.1 The muddy children problem; 1.3.2 The coordinated attack problem; 1.4 Chapter Notes; 1.5 Exercises; 2 Two-Process Systems; 2.1 Elementary Graph Theory. |
|
2.1.1 Graphs, vertices, edges, and colorings2.1.2 Simplicial maps and connectivity; 2.1.3 Carrier maps; 2.1.4 Composition of maps; 2.2 Tasks; 2.2.1 Example: coordinated attack; 2.2.2 Example: consensus; 2.2.3 Example: approximate agreement; 2.3 Models of Computation; 2.3.1 The protocol graph; 2.3.2 The alternating message-passing model; 2.3.3 The layered message-passing model; 2.3.4 The layered read-write model; 2.4 Approximate Agreement; 2.5 Two-Process Task Solvability; 2.6 Chapter Notes; 2.7 Exercises; 3 Elements of Combinatorial Topology; 3.1 Basic Concepts; 3.2 Simplicial Complexes. |
|
3.2.1 Abstract Simplicial Complexes and Simplicial Maps3.2.2 The Geometric View; 3.2.3 The topological view; 3.3 Standard Constructions; 3.3.1 Star; 3.3.2 Link; 3.3.3 Join; 3.4 Carrier Maps; 3.4.1 Chromatic complexes; 3.5 Connectivity; 3.5.1 Path connectivity; 3.5.2 Simply connected spaces; 3.5.3 Higher-dimensional connectivity; 3.6 Subdivisions; 3.6.1 Stellar subdivision; 3.6.2 Barycentric subdivision; 3.6.3 Standard chromatic subdivision; 3.6.4 Subdivision operators; 3.6.5 Mesh-shrinking subdivision operators; 3.7 Simplicial and Continuous Approximations; 3.8 Chapter Notes; 3.9 Exercises. |
|
4 Colorless Wait-Free Computation4.1 Operational Model; 4.1.1 Overview; 4.1.2 Processes; 4.1.3 Configurations and executions; 4.1.4 Colorless tasks; 4.1.5 Protocols for colorless tasks; 4.2 Combinatorial Model; 4.2.1 Colorless tasks revisited; 4.2.2 Examples of colorless tasks; 4.2.3 Protocols revisited; 4.2.4 Protocol composition; 4.2.5 Single-layer colorless protocol complexes; 4.2.6 Multilayer protocol complexes; 4.3 The Computational Power of Wait-Free Colorless Immediate Snapshots; 4.3.1 Colorless task solvability; 4.3.2 Applications; 4.4 Chapter Notes; 4.5 Exercises. |
|
5 Solvability of Colorless Tasks in Different Models5.1 Overview of Models; 5.2 t-Resilient Layered Snapshot Protocols; 5.3 Layered Snapshots with k-Set Agreement; 5.4 Adversaries; 5.5 Message-Passing Protocols; 5.5.1 Set agreement; 5.5.2 Barycentric agreement; 5.5.3 Solvability condition; 5.6 Decidability; 5.6.1 Paths and loops; 5.6.2 Loop agreement; 5.6.3 Examples of loop agreement tasks; 5.6.4 Decidability for layered snapshot protocols; 5.6.5 Decidability with k-set agreement; 5.7 Chapter Notes; 5.8 Exercises; 6 Byzantine-Resilient Colorless Computation; 6.1 Byzantine Failures. |
| Summary |
Distributed Computing Through Combinatorial Topology describes techniques for analyzing distributed algorithms based on award winning combinatorial topology research. The authors present a solid theoretical foundation relevant to many real systems reliant on parallelism with unpredictable delays, such as multicore microprocessors, wireless networks, distributed systems, and Internet protocols. Today, a new student or researcher must assemble a collection of scattered conference publications, which are typically terse and commonly use different notations and terminologies. This. |
| Subject |
Electronic data processing -- Distributed processing -- Mathematics.
|
|
Combinatorial topology.
|
|
Traitement réparti -- Mathématiques. |
|
Topologie combinatoire. |
|
Combinatorial topology |
| Added Author |
Kozlov, D. N. (Dmitriĭ Nikolaevich)
|
|
Rajsbaum, Sergio.
|
| Other Form: |
Print version: Herlihy, Maurice. Distributed computing through combinatorial topology. Amsterdam : Elsevier, [2014] 9780124045781 (DLC) 2013038781 (OCoLC)851417481 |
| ISBN |
9780124047280 |
|
0124047289 |
|
0124045782 |
|
9780124045781 |
|
More Resources