Distributed Computing
ETH Zurich

Principles of Distributed Computing (FS 2009)

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, self-organization, 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 has been revised; a few topics (e.g. multi-core computing, self-organization) have been added, a few others have been dropped.

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

Course language: English.

Exam: The exam took place on Monday, 3rd of August, 9-11 am.
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.

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

Exercises by Christoph Lenzen and Thomas Locher
Wednesday 10.15-11.00 @ CAB G52.

Useful references

Lecture material


Title Lecture Notes (PDF) References

Chapter 0
Introduction
2009/02/18
Download [peleg] Preface & Chapter 1

Chapter 1
Vertex Coloring
2009/02/18
Download [peleg] Chapter 7

Chapter 2
Leader Election
2009/02/25
Download [aw] Chapter 3
[hkpru] Chapter 8

Chapter 3
Tree Algorithms
2009/03/11
Download [peleg] Chapters 3-5
[hkpru] Chapter 7

Chapter 4
Maximal Independent Set
(Section 4.2 not covered by the course)
2009/03/18
Download [peleg] Chapters 8

Chapter 5
Shared Memory
2009/03/25
Download [aw] Chapter 4

Chapter 6
Consensus
2009/04/01
Download [aw] Chapter 5 & 14.3
slides from two years ago

Chapter 7
Shared Objects
2009/04/08
Download ---

Chapter 8
Synchronizers
2009/04/22
Download [peleg] Chapter 6 & 25
[aw] Chapter 11

Chapter 9
Stabilization
2009/04/29
Download ---

Chapter 10
All-to-All Communication
2009/05/06
Download slides

Chapter 11
Distributed Sorting
2009/05/13
Download [leighton] Chapter 1.6 & 3.5
[clr] Chapter 28

Chapter 12
Peer-to-Peer Computing
2009/05/20
Download slides from talk at P2P

Chapter 13
Multi-Core Computing
2009/05/27
Download slides

Complete Script
Principles of Distributed Computing
Download

Exercises material


Title Exercise Sample Solution

Exercise 1
Assigned: 2009/02/18
Due: 2009/02/25
Download Download

Exercise 2
Assigned: 2009/02/25
Due: 2009/03/11
Download Download

Exercise 3
Assigned: 2009/03/11
Due: 2009/03/18
Download Download

Exercise 4
Assigned: 2009/03/18
Due: 2009/03/25
Download Download

Exercise 5
Assigned: 2009/03/25
Due: 2009/04/01
Download Download

Exercise 6
Assigned: 2009/04/01
Due: 2009/04/08
Download Download

Exercise 7
Assigned: 2009/04/08
Due: 2009/04/22
Download Download

Exercise 8
Assigned: 2009/04/22
Due: 2009/04/29
Download Download

Exercise 9
Assigned: 2009/04/29
Due: 2009/05/06
Download Download

Exercise 10
Assigned: 2009/05/06
Due: 2009/05/13
Download Download

Exercise 11
Assigned: 2009/05/13
Due: 2009/05/20
Download Download

Exercise 12
Assigned: 2009/05/20
Due: 2009/05/27
Download Download

Exercise 13
Assigned: 2009/05/27
Due: at will
Go swimming (in parallel)!

References

Books:

[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

Chapter 3: Tree Algorithms

Chapter 4: Maximal Independent Set

Chapter 5: Shared Memory

Chapter 6: Consensus

Chapter 7: Shared Objects

Chapter 8: Synchronizers

Chapter 9: Stabilization

Chapter 10: All-to-All Communication

Chapter 11: Distributed Sorting

Chapter 12: Peer-to-Peer Computing

Chapter 13: Multi-Core Computing