Download

Full book · PDF, 200+ pages, last updated on 2024-11-03

Source code on GitHub

About the book

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.

Individual chapters and videos

The book is also available as individual chapters. For Chapters 1–11 we have prepared short introductory videos.

• Chapter 1: Warm-Up · updated on 2021-09-16
  • Video 1a: Introduction · 14 min
  • Video 1b: Coloring cycles fast · 7 min
• Chapter 2: Graph-Theoretic Foundations
  • Video 2a: Graph-theoretic foundations · 18 min
• Chapter 3: Port-Numbering Model · updated on 2023-09-20
  • Video 3a: Port-numbering model · 7 min
• Chapter 4: LOCAL Model · updated on 2024-11-03
  • Video 4a: Fast graph coloring · 7 min
• Chapter 5: CONGEST Model · updated on 2023-10-01
  • Video 5a: All-pairs shortest paths · 8 min
• Chapter 6: Randomized Algorithms · updated on 2021-12-11
  • Video 6a: Randomized coloring · 6 min
• Chapter 7: Covering Maps
  • Video 7a: Covering maps · 8 min
• Chapter 8: Local Neighborhoods · updated on 2023-10-29
  • Video 8a: What can you do fast in the LOCAL model? · 4 min
• Chapter 9: Round Elimination
  • Video 9a: Round elimination · 12 min
• Chapter 10: Sinkless Orientation · updated on 2021-11-29
  • Video 10a: Sinkless orientation · 7 min
• Chapter 11: Hardness of Coloring · updated on 2021-12-11
  • Video 11a: Hardness of coloring · 7 min
• Chapter 12: Conclusions
• YouTube playlist with all videos

Lecture slides from 2024

Lecture slides from the 2024 edition of the course (8 lectures):

• Lecture 1: Chapters 1 + 2
• Lecture 2: Chapters 3 + 4
• Lecture 3: Chapters 5 + 6
• (Lecture 4: merged with lecture 3)
• Lecture 5: Chapters 7 + 8
• Lecture 6: Chapters 9 + 10

Lecture slides from 2023

Lecture slides from the 2023 edition of the course (12 lectures, one per chapter):

• Chapter 1
• Chapter 2
• Chapter 3
• Chapter 4
• Chapter 5
• Chapter 6 (from 2022)
• Chapter 7
• Chapter 8
• Chapter 9
• Chapter 10
• Chapter 11
• Chapter 12

Exams

• Exam for Chapters 1–6 · October 2023
• Exam for Chapters 1–6 · October 2022
• Exam for Chapters 1–6 · October 2021
• Exam for Chapters 1–6 · October 2020
• Exam for Chapters 7–12 · December 2023
• Exam for Chapters 7–12 · December 2022
• Exam for Chapters 7–12 · December 2021
• Exam for Chapters 7–12 · December 2020
• Exam for the whole course · February 2021

Copyright and license

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.