Distributed Computing
ETH Zurich

Principles of Distributed Computing (FS 2008)

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.

Note that this lecture has been revised. Several topics are covered for the first time this year, while other topics treated in previous years are not covered anymore.

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

Course language: English or German (depending on the audience).

If you want to review the corrections of your exam, go to our secretary, Monica Fricker (ETZ G88), either on Tuesdays or Thursdays between 9 and 11 AM.

Written exam: 9:00-11:00, August 18, 2008.
Previous exams: SS 03 (Problems 3 & 4 not covered), SS 04 (Problem 3 not covered).

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

Exercises by Thomas Locher, Yvonne Anne Oswald, Christoph Lenzen
Wednesday 10.15-11.00 @ CAB G52.
First (short) exercise meeting: February 20, 2008.

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 [aw] Chapter 3
[hkpru] Chapter 8

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

Chapter 4
Maximal Independent Set
Download [peleg] Chapter 8

Chapter 5
Dominating Set
Download ---

Chapter 6
Download [peleg] Chapter 6 & 25
[aw] Chapter 11

Chapter 7
All-to-All Communication
Download Slides (from previous year)

Chapter 8
Download [aw] Chapter 5 & 14.3
Slides (from previous year)

Chapter 9
Distributed Sorting
Download [leighton] Chapter 1.6 & 3.5
[clr] Chapter 28

Chapter 10
Peer-to-Peer Computing
Download Slides (from talk at P2P)

Chapter 11
Locality Lower Bounds
Download [peleg] Chapter 7.5

Chapter 12
Shared Objects
Download ---

Chapter 13
Shared Memory
Download [aw] Chapter 4

Exercises material

Title Exercise Sample Solution

Exercise 1
Assigned: 2008/02/20
Due: 2008/02/27
Download Download

Exercise 2
Assigned: 2008/02/27
Due: 2008/03/05
Download Download

Exercise 3
Assigned: 2008/03/05
Due: 2008/03/12
Download Download

Exercise 4
Assigned: 2008/03/12
Due: 2008/03/19
Download Download

Exercise 5
Assigned: 2008/03/19
Due: 2008/04/02
Download Download

Exercise 6
Assigned: 2008/04/02
Due: 2008/04/09
Download Download

Exercise 7
Assigned: 2008/04/09
Due: 2008/04/16
Download Download

Exercise 8
Assigned: 2008/04/16
Due: 2008/04/23
Download Download

Exercise 9
Assigned: 2008/04/23
Due: 2008/04/30
Download Download

Exercise 10
Assigned: 2008/04/30
Due: 2008/05/14
Download Download

Exercise 11
Assigned: 2008/05/14
Due: 2008/05/21
Download Download

Exercise 12
Assigned: 2008/05/21
Due: 2008/05/28
Download Download



[aw] 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
[hkpru] Dissemination 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
[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: Maximal Independent Set

Chapter 5: Dominating Set

Chapter 6: Synchronizers

Chapter 7: All-to-All Communication

Chapter 8: Consensus

Chapter 9: Distributed Sorting

Chapter 10: Peer-to-Peer Computing

Chapter 11: Locality Lower Bound

Chapter 12: Shared Objects

Chapter 13: Shared Memory