Distributed Computing
ETH Zurich

Principles of Distributed Computing (FS 2010)

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

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. This course introduces 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. We will cover a fresh topic every week.

Note that last year's lecture will be revised; a few topics will be added, a few others will be dropped.

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

Course language: English.

Exam: The exam will take place on Tuesday, 24th of August, 9-11 am in room HG E 7.
Previous exams: SS 03 (Problems 3 & 4 not covered), SS 04 (Problem 3 not covered).
Here are some tips for your preparation from Christoph Lenzen.
Question session: Christoph reserved some time to answer questions arising while studying for the exam.
Please go to this poll to fix a time slot (first come, first serve).

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

Exercises by Christoph Lenzen Wednesday 10.15-12.00 @ CAB G56.

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

Guest Lecture
Vertex Cover
Slides ---

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

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

Chapter 5
Shared Memory
Download [aw] Chapter 4

Chapter 6
Shared Objects
Download ---

Chapter 7
Dynamic Networks
Download ---

Chapter 8
Peer-to-Peer Computing
Download slides from talk at P2P

Chapter 9
Social Networks
Download ---

Chapter 10
Maximal Independent Set
Download [peleg] Chapter 8

Chapter 11
Locality Lower Bounds
Download [peleg] Chapter 7.5
Slides about Ramsey Theory
by Jukka Suomela (thanks!)
(alternative version)

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

Chapter 13
Download ---

Complete Script
Principles of Distributed Computing

Exercises material

Title Exercise Sample Solution

Exercise 1
Assigned: 2010/02/24
Due: 2010/03/03
Download Download

Exercise 2
Assigned: 2010/03/03
Due: 2010/03/10
Download Download

Exercise 3
Assigned: 2010/03/10
Due: 2010/03/17
Download Download

Exercise 4
Assigned: 2010/03/17
Due: 2010/03/24
Download Download

Exercise 5
Assigned: 2010/03/24
Due: 2010/03/31
Download Download

Exercise 6
Assigned: 2010/03/31
Due: 2010/04/14
Download Download

Exercise 7
Assigned: 2010/04/14
Due: 2010/04/21
Download Download

Exercise 8
Assigned: 2010/04/21
Due: 2010/04/28
Download Download

Exercise 9
Assigned: 2010/04/28
Due: 2010/05/05
Download Download

Exercise 10
Assigned: 2010/05/05
Due: 2010/05/12
Download Download

Exercise 11
Assigned: 2010/05/12
Due: 2010/05/19
Download Download

Exercise 12
Assigned: 2010/05/19
Due: 2010/05/26
Download Download

Exercise 13
Assigned: 2010/05/26
Due: 2010/06/02
Download Download



[peleg] Distributed Computing: A Locality-Sensitive Approach
David Peleg.
Society for Industrial and Applied Mathematics (SIAM), 2000, ISBN 0-89871-464-8
[aw] Distributed Computing: Fundamentals, Simulations and Advanced Topics
Hagit Attiya, Jennifer Welch.
McGraw-Hill Publishing, 1998, ISBN 0-07-709352 6
[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
[clr] Introduction to Algorithms
Thomas Cormen, Charles Leiserson, Ronald Rivest.
The MIT Press, 1998, ISBN 0-262-53091-0 oder 0-262-03141-8

Articles chapter by chapter:

Chapter 0: Introduction

Chapter 1: Vertex Coloring

Chapter 2: Leader Election

Lecture 3: Vertex Cover

Chapter 3: Tree Algorithms

Chapter 4: Distributed Sorting

Chapter 5: Shared Memory

Chapter 6: Shared Objects

Chapter 7: Dynamic Networks

Chapter 8: Peer-to-Peer Computing

Chapter 9: Social Networks

Chapter 10: Maximal Independent Set

Chapter 11: Locality Lower Bounds

Chapter 12: Synchronizers

Chapter 13: Stabilization