Distributed Computing
ETH Zurich

Principles of Distributed Computing (SS 2006)

This page is no longer maintained. Up-to-date versions of lecture and exercise material can be found here.

In the last two decades, we have experienced an unprecedented growth in the area of distributed systems and networks; distributed computing now encompasses many of the activities occurring in today's computer and communications world. This course introduces the principles of distributed computing, highlighting common themes and techniques. We study the fundamental issues underlying the design of distributed systems: communication, coordination, fault-tolerance, locality, parallelism, symmetry breaking, synchronization, uncertainty. We explore essential algorithmic ideas and lower bound techniques, basically the "pearls" of distributed computing. We will cover a fresh topic every week.

Course pre-requisites: Interest in algorithmic problems. (No particular course needed.)

Course language: English.

Lecture by Roger Wattenhofer, Fabian Kuhn,
Wednesday 8.15-10.00 @ CAB G51.

Exercises by Thomas Locher,
Wednesday 10.15-11.00 @ CAB G52.
No exercise meeting: March 21, 2007.

Useful references

Lecture material

Title Lecture Notes (PDF) References

Chapter 0
Download [peleg] Preface & Chapter 1

Chapter 1
Vertex Coloring
Download [peleg] Chapter 7

Chapter 2
Leader Election
Download [attiya] Chapter 3
[hkpru] Chapter 8

Chapter 3
Tree Algorithms
Download [peleg] Chapter 3
[peleg] Chapter 5
[hkpru] Chapter 7

Chapter 4
Download [leighton] Chapter 1.7

Chapter 5
Basic Network Topologies
Download [leighton] Chapter 3.1.1
[leighton] Chapter 3.2.1

Chapter 6
Routing Strikes Back
Download [leighton] Chapter 3.4

Chapter 7
Shared Variables
Download Ivy Amortized Analysis

Chapter 8
Download [leighton] Chapter 1.6
[leighton] Chapter 3.5
[clr] Chapter 28

Chapter 9
Graph Algorithms
Download [peleg] Chapter 8

Chapter 10
Distributed Dominating Set Approximation
Download ---

Chapter 11
pp. 233-238 (Introduction)
p. 241 (Brent's Lemma)
pp. 246-249 (Prefix Sum)

Chapter 12
Sorting on PRAM

Chapter 13
Chapters 1, 2 & 3
For interested students

Exercises material

Title Exercise Sample Solution

Exercise 1
Assigned: 2006/04/12
Due: 2006/04/19
Download Download

Exercise 2
Assigned: 2006/04/19
Due: 2006/04/26
Download Download

Exercise 3
Assigned: 2006/05/03
Due: 2006/05/10
Download Download

Exercise 4
Assigned: 2006/05/10
Due: 2006/05/17
Download Download

Exercise 5
Assigned: 2006/05/17
Due: 2006/05/24
Download Download

Exercise 6
Assigned: 2006/05/24
Due: 2006/05/31
Download Download

Exercise 7
Assigned: 2006/05/31
Due: 2006/06/07
Download Download

Exercise 8
Assigned: 2006/06/07
Due: 2006/06/14
Download Download

Exercise 9
Assigned: 2006/06/21
Due: 2006/06/28
Download Download



[attiya] Distributed Computing: Fundamentals, Simulations and Advanced Topics
Hagit Attiya, Jennifer Welch.
McGraw-Hill Publishing, 1998, ISBN 0-07-709352 6
[clr] Introduction to Algorithms
Thomas Cormen, Charles Leiserson, Ronald Rivest.
The MIT Press, 1998, ISBN 0-262-53091-0 oder 0-262-03141-8
[garg] Elements of Distributed Computing
Vijay Garg.
Wiley, 2002, ISBN 0-471-03600-5
[hkpru] Disseminatin of Information in Communication Networks
Juraj Hromkovic, Ralf Klasing, Andrzej Pelc, Peter Ruzicka, Walter Unger.
Springer-Verlag, Berlin Heidelberg, 2005, ISBN 3-540-00846-2
[jaja] An Introduction to Parallel Algorithms
Joseph JaJa.
Addison-Wesley, 1992, ISBN 0-201-54856-9
[leighton] Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes
Frank Thomson Leighton.
Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991, ISBN 1-55860-117-1
[peleg] Distributed Computing: A Locality-Sensitive Approach
David Peleg.
Society for Industrial and Applied Mathematics (SIAM), 2000, ISBN 0-89871-464-8

Articles chapter by chapter:

Chapter 0: Introduction

Chapter 1: Vertex Coloring

Chapter 2: Leader Election

Chapter 3: Tree Algorithms

Chapter 4: Routing

Chapter 5: Basic Network Topologies

Chapter 6: Routing Strikes Back

Chapter 7: Shared Variables

Chapter 8: Sorting

Chapter 9: Graph Algorithms

Chapter 10: Distributed Dominating Set Approximation

Chapter 11: PRAM

Chapter 13: Self-Stabilization