Distributed Computing
ETH Zurich

Principles of Distributed Computing (lecture collection)

Distributed computing is essential in modern computing and communications systems. Examples are on the one hand large-scale networks such as the Internet, and on the other hand multiprocessors such as your new multi-core laptop. The lecture notes on this webpage introduce the principles of distributed computing, emphasizing the fundamental issues underlying the design of distributed systems and networks: communication, coordination, fault-tolerance, locality, parallelism, self-organization, symmetry breaking, synchronization, uncertainty. We explore essential algorithmic ideas and lower bound techniques, basically the "pearls" of distributed computing. Each chapter covers a fresh topic.

Note that the order of the chapters is more or less arbitrary. Each chapter is mostly independent, with the occasional reference to another chapter.



Lecture material


Title Lecture Notes Exercises Additional Material

Chapter 0
Introduction
PDF 1:1
PDF 2:1

Chapter 1
Vertex Coloring
PDF 1:1
PDF 2:1
Exercises
Solutions
Slides by S.Schmid, TU Berlin

Chapter 2
Tree Algorithms
PDF 1:1
PDF 2:1
Exercises
Solutions
Slides by S.Schmid, TU Berlin

Chapter 3
Leader Election
PDF 1:1
PDF 2:1
Exercises
Solutions
Slides by S.Schmid, TU Berlin

Chapter 4
Distributed Sorting
PDF 1:1
PDF 2:1
Exercises
Solutions

Chapter 5
Shared Memory
PDF 1:1
PDF 2:1
Exercises
Solutions

Chapter 6
Shared Objects
PDF 1:1
PDF 2:1
Exercises
Solutions

Chapter 7
Maximal Independent Set
PDF 1:1
PDF 2:1
Exercises
Solutions
Slides by R. Wattenhofer
Slides by S.Schmid, TU Berlin

Chapter 8
Locality Lower Bounds
PDF 1:1
PDF 2:1
Exercises
Solutions
Slides by S.Schmid, TU Berlin
Ramsey Theory Slides by J. Suomela
Alternative Version thanks!

Chapter 9
Social Networks
PDF 1:1
PDF 2:1
Exercises
Solutions
Slides by S.Schmid, TU Berlin

Chapter 10
Synchronization
PDF 1:1
PDF 2:1
Exercises
Solutions

Chapter 11
Hard Problems
PDF 1:1
PDF 2:1
Exercises
Solutions
Slides some additional Slides
Animation of APSP Algorihm by Jukka Suomela

Chapter 12
Wireless Protocols
PDF 1:1
PDF 2:1
Exercises
Solutions

Chapter 13
Stabilization
PDF 1:1
PDF 2:1
Exercises
Solutions

Chapter 14
Labeling Schemes
PDF 1:1
PDF 2:1

Chapter 15
Fault-Tolerance & Paxos
PDF 1:1
PDF 2:1

Chapter 16
Consensus
PDF 1:1
PDF 2:1

Chapter 17
Byzantine Agreement
PDF 1:1
PDF 2:1

Chapter 18
Authenticated Agreement
PDF 1:1
PDF 2:1

Chapter 19
Quorum Systems
PDF 1:1
PDF 2:1

Chapter 20
Eventual Consistency & Bitcoin
PDF 1:1
PDF 2:1

Chapter 21
Distributed Storage
PDF 1:1
PDF 2:1

Chapter 22
Game Theory
PDF 1:1
PDF 2:1

Chapter 23
Dynamic Networks
PDF 1:1
PDF 2:1
Exercises
Solutions

Chapter 24
All-to-All Communication
PDF 1:1
PDF 2:1
Exercises
Solutions
Slides

Chapter 25
Multi-Core Computing
PDF 1:1
PDF 2:1
Slides

Chapter 26
Dominating Set
PDF 1:1
PDF 2:1
Exercises
Solutions

Chapter 27
Routing
PDF 1:1
PDF 2:1

Chapter 28
Routing Strikes Back
PDF 1:1
PDF 2:1

All Chapters
Principles of Distributed Computing
PDF 1:1
PDF 2:1