Full book (PDF, 200+ pages).

This free online textbook is an introduction to the **theory of distributed algorithms**, with focus on distributed graph algorithms (network algorithms). The topics covered include:

**Models of computing:**precisely what is a distributed algorithm, and what do we mean when we say that a distributed algorithm solves a certain computational problem?**Algorithm design and analysis:**which computational problems can be solved with distributed algorithms, which problems can be solved*efficiently*, and how to do it?**Computability and computational complexity:**which computational problems*cannot*be solved at all with distributed algorithms, which problems cannot be solved*efficiently*, why is this the case, and how to prove it?

No prior knowledge of distributed systems is needed. A basic knowledge of discrete mathematics and graph theory is assumed, as well as familiarity with the basic concepts from undergraduate-level courses on models on computation, computational complexity, and algorithms and data structures.

This textbook was written to support the lecture course CS-E4510 Distributed Algorithms at Aalto University. The course is worth 5 ECTS credits. There are 12 weeks of lectures. Each week we will cover one chapter of this book, and our students are expected to solve the quiz and at least 3 of the exercises from the chapter.

The book is also available as individual chapters. For Chapters 1–11 we have prepared short introductory videos. The lecture slides that we have used are available here for download, but please note that they are not entirely self-contained—many of them serve mainly as a background on top of which we draw during the lectures.

- Source code on GitHub (LaTeX source code, original PowerPoint files, illustrations)
- YouTube playlist with all videos
- Chapter 1: Warm-Up
- Video 1a: Introduction (14 min)
- Video 1b: Coloring cycles fast (7 min)
- Slides

- Chapter 2: Graph-Theoretic Foundations
- Chapter 3: Port-Numbering Model
- Video 3a: Port-numbering model (7 min)
- Slides

- Chapter 4: LOCAL Model
- Video 4a: Fast graph coloring (7 min)
- Slides

- Chapter 5: CONGEST Model
- Chapter 6: Randomized Algorithms
- Video 6a: Randomized coloring (6 min)
- Slides

- Chapter 7: Covering Maps
- Video 7a: Covering maps (8 min)
- Slides

- Chapter 8: Local Neighborhoods
- Chapter 9: Round Elimination
- Video 9a: Round elimination (12 min)
- Slides

- Chapter 10: Sinkless Orientation
- Video 10a: Round elimination (7 min)
- Slides

- Chapter 11: Hardness of Coloring
- Chapter 12: Conclusions
- Exam for Chapters 1–6
- Exam for Chapters 7–12

The book and all other material on this web page was prepared by Juho Hirvonen and Jukka Suomela. The content is licensed under the Creative Commons Attribution 4.0 International (CC BY 4.0) license—you are free to share and adapt this material, as long as you give appropriate credit to the authors.