What do you think?
Rate this book
Distributed Computing Through Combinatorial Topology
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 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.
336 pages, Paperback
First published November 29, 2013
6 people are currently reading
58 people want to read
Ratings & Reviews
Friends & Following
Create a free account to discover what your friends think of this book!
Community Reviews
Displaying 1 - 3 of 3 reviews
June 6, 2015
This book is a sweeping survey at least some of the mathematics used to describe distributed computing. Most of the book is dedicated to describing compute tasks/problem solving through the lens of simplicial complexes and associated mappings, topologies, etc.
Distributed Computing Through Combinatorial Topology walks the reader through basic concepts such as 2-node agreement via message passing problems and how to describe them on to more complex concepts such as wait-free colorless snapshots, adversarial systems, and so on eventually culminating in a variety of interesting results about simulations and reductions related to the variety of models covered in the book such as read-write, layered snapshot, etc.
Many expository texts claim to be self-contained in the material and many fall short of exactly that. I believe they fall prey to the, "pencil tapping problem" (See Simple: Conquering the Crisis of Complexity for more). This book isn't perfect in that right but it does a much better job than other introductions I have read before. The reader is advised that there is a need for mathematical maturity and computer science to truly reap value from this book. It helps to have exposure to discrete mathematics/combinatorics and topology. Linear algebra, abstract algebra, and programming concepts will greatly enhance your understanding as well. For example, Sperner's Lemma makes a showing.
This book isn't without it warts. Although I confess it might be misplaced expectations on my part as well. When I read the introduction and early chapters, I was under the impression that this was an applied mathematics book. As a practitioner, I expected a variety of examples, preferably real world, to round out the lessons. While there was a dash of pseudo-code throughout the book, most of the book was deeply focused on just the mathematics of distributed computing. One area I specifically wondered about was all the applications possible around barycentric subdivisions.
My preference for improving the text for a later edition would be more examples. As a reader, I could see possibilities where some of the mathematics could apply to multi-core systems with non-uniform memory access (NUMA) but I began to struggle with seeing other possibilities. This book's value would be greatly enhanced if they could shed light to the reader in this manner.
Overall, the book is an embarrassment of riches. The math contained is clear and easy to understand. New concepts are introduced in a progressive manner that builds upon previous chapters. If the discussion changes, the book pivots in a way that the reader isn't lost. Some of the examples of the authors' attention to detail is as follows - each chapter opens up with a high level summary of the content, introductory material is presented with explanation and reference, proofs & lemmas are presented, final results are discussed, and the chapter closes with a fascinating narrative of the research conducted in that area with lots of references for further reading. This book, for the appropriately interested person, could be the perfect launching point into the field.
For a lay person like myself, I finished this book with a deeper understanding of the mathematics of distributed computing, what models are appropriate for solving different kinds of problems such as symmetry breaking vs. consensus, and a deeper appreciation how simplicial complexes can be deployed to solve real world problems.
Distributed Computing Through Combinatorial Topology walks the reader through basic concepts such as 2-node agreement via message passing problems and how to describe them on to more complex concepts such as wait-free colorless snapshots, adversarial systems, and so on eventually culminating in a variety of interesting results about simulations and reductions related to the variety of models covered in the book such as read-write, layered snapshot, etc.
Many expository texts claim to be self-contained in the material and many fall short of exactly that. I believe they fall prey to the, "pencil tapping problem" (See Simple: Conquering the Crisis of Complexity for more). This book isn't perfect in that right but it does a much better job than other introductions I have read before. The reader is advised that there is a need for mathematical maturity and computer science to truly reap value from this book. It helps to have exposure to discrete mathematics/combinatorics and topology. Linear algebra, abstract algebra, and programming concepts will greatly enhance your understanding as well. For example, Sperner's Lemma makes a showing.
This book isn't without it warts. Although I confess it might be misplaced expectations on my part as well. When I read the introduction and early chapters, I was under the impression that this was an applied mathematics book. As a practitioner, I expected a variety of examples, preferably real world, to round out the lessons. While there was a dash of pseudo-code throughout the book, most of the book was deeply focused on just the mathematics of distributed computing. One area I specifically wondered about was all the applications possible around barycentric subdivisions.
My preference for improving the text for a later edition would be more examples. As a reader, I could see possibilities where some of the mathematics could apply to multi-core systems with non-uniform memory access (NUMA) but I began to struggle with seeing other possibilities. This book's value would be greatly enhanced if they could shed light to the reader in this manner.
Overall, the book is an embarrassment of riches. The math contained is clear and easy to understand. New concepts are introduced in a progressive manner that builds upon previous chapters. If the discussion changes, the book pivots in a way that the reader isn't lost. Some of the examples of the authors' attention to detail is as follows - each chapter opens up with a high level summary of the content, introductory material is presented with explanation and reference, proofs & lemmas are presented, final results are discussed, and the chapter closes with a fascinating narrative of the research conducted in that area with lots of references for further reading. This book, for the appropriately interested person, could be the perfect launching point into the field.
For a lay person like myself, I finished this book with a deeper understanding of the mathematics of distributed computing, what models are appropriate for solving different kinds of problems such as symmetry breaking vs. consensus, and a deeper appreciation how simplicial complexes can be deployed to solve real world problems.
April 19, 2023
I skimmed this a few years ago because the premise seemed fascinating, but finally committed to reading it cover to cover more recently. Lynch's Distributed Algorithms has one of these topological proofs in it, but this book goes fairly deep into the approach. Be warned that there's not much in terms of practical applications to be found, but the big idea is a nice one. There's stuff that uses the fundamental group of a simplicial complex that's really interesting, but only comes in at the very end. I found the notation used to be more confusing than seemed necessary, for example a large number of different symbols with the same pronunciation (\epsilon and \varepsilon for example), and the heavy overloading of vertical bars in the same section. And there are a fair few typographical errors which doesn't give one super high confidence, plus the intro has a link which it promises will contain updates among other things, but said website actually just has a product blurb.
April 11, 2022
The elements, in this book, are odd. Combinatorics and Topology in connection with the notion of the communication protocol, reminds me of some odd conversation I had at one point (indicating I did not understand distributed computing, and thus was reading Nancy Lynch- this was many decades ago). The book indicates, the author's have a good understanding of DC, however this contribution, has little substance.
Displaying 1 - 3 of 3 reviews