Rajsbaum Sergio - Distributed Computing Through Combinatorial Topology

This book is intended to serve as a textbook for an undergraduate or graduate course in theoretical distributed computing or as a reference for researchers who are, or want to become, active in this area. Previously, the material covered here was scattered across a collection of conference and journal publications, often terse and using different notations and terminology. Here we have assembled a self-contained explanation of the mathematics for computer science readers and of the computer science for mathematics readers.

Each of these chapters includes exercises. We think it is essential for readers to spend time solving these problems. Readers should have some familiarity with basic discrete mathematics, including induction, sets, graphs, and continuous maps. We have also included mathematical notes addressed to readers who want to explore the deeper mathematical structures behind this material.

The first three chapters cover the fundamentals of combinatorial topology and how it helps us understand distributed computing. Although the mathematical notions underlying our computational models are elementary, some notions of combinatorial topology, such as simplices, simplicial complexes, and levels of connectivity, may be unfamiliar to readers with a background in computer science. We explain these notions from first principles, starting in we describe the approach in more detail for the case of a system consisting of two processes only. Elementary graph theory, which is well-known to both computer scientists and mathematicians, is the only mathematics needed.

The graph theoretic notions of , where most of the topological notions used in the book are presented. Though similar material can be found in many topology texts, our treatment here is different. In most texts, the notions needed to model computation are typically intermingled with a substantial body of other material, and it can be difficult for beginners to extract relevant notions from the rest. Readers with a background in combinatorial topology may want to skim this chapter to review concepts and notations.

The next four chapters are intended to form the core of an advanced undergraduate course in distributed computing. The mathematical framework is self-contained in the sense that all concepts used in this section are defined in the first three chapters.

In this part of the book we concentrate on the so-called colorless tasks, a large class of coordination problems that have received a great deal of attention in the research literature. In

, we put these pieces together to give necessary and sufficient conditions for solving general tasks in various models of computation. Here notions from elementary point-set topology, such as open covers and compactness are used.

The final part of the book provides an opportunity to delve into more advanced topics of distributed computing by using further notions from topology. These chapters can be read in any order, mostly after having studied uses Schlegel diagrams to prove basic topological properties about our core models of computation.

Maurice Herlihy was supported by .

Sergio Rajsbaum by UNAM PAPIIT and PAPIME Grants.

Dmitry Kozlov was supported by the University of Bremen and the German Science Foundation.