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 Responsible Assistant Additional Material

Chapter 0
Introduction
PDF 1:1
PDF 2:1

Chapter 1
Vertex Coloring
exercise1
PDF 1:1
PDF 2:1
Exercises

Chapter 2
Tree Algorithms
exercise2
PDF 1:1
PDF 2:1
Exercises

Chapter 3
Leader Election
exercise3
PDF 1:1
PDF 2:1
Exercises

Chapter 4
Distributed Sorting
exercise4
PDF 1:1
PDF 2:1

Chapter 5
Shared Memory
exercise5
PDF 1:1
PDF 2:1

Chapter 6
Shared Objects
exercise6
PDF 1:1
PDF 2:1

Chapter 7
Maximal Independent Set
exercise7
PDF 1:1
PDF 2:1
Exercises

Chapter 8
Locality Lower Bounds
exercise8
PDF 1:1
PDF 2:1
Exercises

Chapter 9
Social Networks
exercise9
PDF 1:1
PDF 2:1
Exercises

Chapter 10
Synchronization
exercise10
PDF 1:1
PDF 2:1

Chapter 11
Hard Problems
exercise11
PDF 1:1
PDF 2:1
Exercises

Chapter 12
Wireless Protocols
exercise12
PDF 1:1
PDF 2:1

Chapter 13
Stabilization
exercise13
PDF 1:1
PDF 2:1

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
dyn
PDF 1:1
PDF 2:1

Chapter 24
All-to-All Communication
all2all
PDF 1:1
PDF 2:1
Exercises

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

Chapter 26
Dominating Set
dominating
PDF 1:1
PDF 2:1

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