Distributed Computing Through Combinatorial Topology

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

Studies in Complexity and Cryptography: Miscellanea on the Interplay between Randomness and Computation (Lecture Notes in Computer Science / Theoretical Computer Science and General Issues)

Robot Motion and Control: Recent Developments (Lecture Notes in Control and Information Sciences)

Computational Intelligence: A Methodological Introduction (Texts in Computer Science)

Testing Computer Software (2nd Edition)

 

 

 

 

 

 

 

 

 

 

1958;67(1):172+. 128. Rajsbaum Sergio. Iterated shared memory models. In: López-Ortiz Alejandro, ed. LATIN 2010: theoretical informatics. Berlin, Heidelberg, Germany: Springer; 2010;407–416. Lecture notes in Computer Science vol. 6034. 129. Rajsbaum Sergio, Raynal Michel. A survey on some recent advances in shared memory models. In: Kosowski Adrian, Yamashita Masafumi, eds. Structural Information and Communication Complexity. Berlin, Heidelberg, Germany: Springer; 2011;17–28. Lecture notes in

dimension . As an example, for any vertex of a pure complex of dimension , we have Another example is taking the join of an -simplex with an -simplex, which yields an -simplex. There is also a purely topological definition of the join of two topological spaces. Here we simply mention that the simplicial and topological joins commute with the geometric realization, that is, for any two abstract simplicial complexes and , the spaces and are homeomorphic. 3.4 Carrier maps The concept of a

Since the map can be extended to all of , it is contractible, and so is the triangle loop . Contractible Implies Protocol. Let be the homeomorphism of Fact 5.6.10. The edge map induces a continuous map carried by : for , and for . The composition of followed by is a simple loop: also carried by . Because is contractible, Fact 5.6.5 implies that can be extended to also carried by . It is easy to check that the composition is also carried by . Theorem 5.2.7 implies that there is a -resilient

reachable protocol complex, that holds in each final configuration also holds in each initial configuration. We argue by contradiction. We assume that the property does not hold at the start, and we maneuver the protocol into a critical configuration where the property still does not hold, but where any further step by any process will make it hold henceforth (from that point on). We then do a case analysis of each of the process’s possible next steps and use a combination of model-specific

check that agrees with on but collapses one fewer simplex than , contradicting our assumption that collapses a minimum number of simplices. Figure 11.14 Eliminating collapse: Base case. For the induction step, assume the claim for complexes of dimension less than . Let be an -complex, and a continuous map that is simplicial and rigid on . Fact 11.5.5 implies there exists a subdivision such that and a simplicial map that agrees with on . Suppose, by way of contradiction, that for every such and

Download sample

Download