Distributed Computing Through Combinatorial Topology
Maurice Herlihy, Sergio Rajsbaum
Language: English
Pages: 336
ISBN: 0124045782
Format: PDF / Kindle (mobi) / ePub
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 book provides a self-contained explanation of the mathematics to readers with computer science backgrounds, as well as explaining computer science concepts to readers with backgrounds in applied mathematics. The first section presents mathematical notions and models, including message passing and shared-memory systems, failures, and timing models. The next section presents core concepts in two chapters each: first, proving a simple result that lends itself to examples and pictures that will build up readers' intuition; then generalizing the concept to prove a more sophisticated result. The overall result weaves together and develops the basic concepts of the field, presenting them in a gradual and intuitively appealing way. The book's final section discusses advanced topics typically found in a graduate-level course for those who wish to explore further.
- Named a 2013 Notable Computer Book for Computing Methodologies by Computing Reviews
- Gathers knowledge otherwise spread across research and conference papers using consistent notations and a standard approach to facilitate understanding
- Presents unique insights applicable to multiple computing fields, including multicore microprocessors, wireless networks, distributed systems, and Internet protocols
- Synthesizes and distills material into a simple, unified presentation with examples, illustrations, and exercises
GPU Pro: Advanced Rendering Techniques
Distributed Systems: Concepts and Design (5th Edition)
Countdown to Zero Day: Stuxnet and the Launch of the World's First Digital Weapon
Kernel Adaptive Filtering: A Comprehensive Introduction
Immediate snapshot of the entire memory. Initially, each process’s view is its input. For layers, writes its view to mem[i] and, in the very next step, takes a snapshot of the entire memory, which becomes its new view. Processes can write concurrently and take snapshots concurrently, but each snapshot happens immediately after its matching write. After the last layer, returns an output value by applying a task-specific decision map to its final view. Figure 14.5 Full-information immediate.
A task has a protocol in either of the snapshot models, then it has a protocol in the corresponding immediate snapshot model (see Exercise 14.3). For the other direction, it will require a nontrivial argument to show that the ability to take an immediate snapshot is not more computationally powerful than the ability to take a snapshot. Figure 14.7 shows the five shared-memory models. An arrow from one model to another indicates a reduction: If a protocol exists in the target model, then one.
Reductions are shown as dashed arrows. Each dashed arrow is labeled with the chapter section number where we prove that implication. 14.4 Layered snapshot from read-write For our first nontrivial reduction, we will show how to simulate any layered snapshot protocol by a read-write protocol. Since each layer of a layered snapshot protocol uses a disjoint region of memory, it is enough to show how to simulate a single layer’s snapshot. The simulation is shown in Figure 14.8. It consists of two.
Agreement task with the protocol also solves using the same decision map . Proof Recall that by Definition 4.2.5 the task can be composed with the protocol , since . The result of the composition is a new protocol , where . We check that is a correct decision map for the task. Pick an arbitrary . We have where the last inclusion is a corollary of the fact that the protocol solves the task . It follows that is a decision map for the composite protocol. We may now combine the previous results.
That cannot be solved if names are taken from a small name space also cannot be solved if names are taken from a larger name space. For algorithms, however, it may be possible to abuse the small name-space assumption to derive trivial protocols. If , then weak symmetry breaking can be solved with no communication at all: The process with name 0 decides 0 and all others decide 1. Lower bounds are discussed in Chapter 12. One way of comparing the difficulty of two tasks , as in classical.