Preface

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 Chapter 1, where we provide an intuitive introduction to the new approach developed in the book. In Chapter 2 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 Chapter 2 are essentially one-dimensional simplicial complexes, and they provide a smooth introduction to Chapter 3, 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 Chapter 4, we describe our basic operational and combinatorial models of computation. We define tasks and asynchronous, fault-tolerant, wait-free shared-memory protocols. This chapter explains how the mathematical language of combinatorial topology (such as simplicial complexes and maps) can be used to describe concurrent computation and to identify the colorless tasks that can be solved by these protocols. In Chapter 5, we apply these mathematical tools to study colorless task solvability by more powerful protocols. We first consider computational models in which processes fail by crashing (unexpectedly halting). We give necessary and sufficient conditions for solving colorless tasks in a range of different computational models, encompassing different crash-failure models and different forms of communication. In Chapter 6, we show how the same mathematical notions can be extended to deal with Byzantine failures, where faulty processes, instead of crashing, can display arbitrary behavior. In Chapter 7, we show how to use reductions to transform results about one model of computation to results about others.

Chapters 8–11 are intended to form the core of a graduate course. Here, too, the mathematical framework is self-contained, although we expect a slightly higher level of mathematical sophistication. In this part, we turn our attention to general tasks, a broader class of problems than the colorless tasks covered earlier. In Chapter 8, we describe how the mathematical framework previously used to model colorless tasks can be generalized, and in Chapter 9 we consider manifold tasks, a subclass of tasks with a particularly nice geometric structure. We state and prove Sperner’s lemma for manifolds and use this to derive a separation result showing that some problems are inherently ‘‘harder’’ than others. In Chapter 10, we focus on how computation affects connectivity, informally described as the question of whether the combinatorial structures that model computations have ‘‘holes.’’ We treat connectivity in an axiomatic way, avoiding the need to make explicit mention of homology or homotopy groups. In Chapter 10, 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 Chapter 8. Chapter 12 examines the renaming task, and uses combinatorial theorems such as the Index Lemma to derive lower bounds on this task. Chapter 13 uses the notion of shellability to show that a number of models of computation that appear to be quite distinct can be analyzed with the same formal tools. Chapter 14 examines simulations and reductions for general tasks, showing that the shared-memory models used interchangeably in this book really are equivalent. Chapter 15 draws a connection between a certain class of tasks and the Word Problem for finitely-presented groups, giving a hint of the richness of the universe of tasks that are studied in distributed computing. Finally, Chapter 16 uses Schlegel diagrams to prove basic topological properties about our core models of computation.

Maurice Herlihy was supported by NSF grant 000830491.

Sergio Rajsbaum by UNAM PAPIIT and PAPIME Grants.

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