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
Introduction
2006/04/05
Download [peleg] Preface & Chapter 1

Chapter 1
Vertex Coloring
2006/04/05
Download [peleg] Chapter 7

Chapter 2
Leader Election
2006/04/12
Download [attiya] Chapter 3
[hkpru] Chapter 8

Chapter 3
Tree Algorithms
2006/04/19
Download [peleg] Chapter 3
[peleg] Chapter 5
[hkpru] Chapter 7

Chapter 4
Routing
2006/04/26
Download [leighton] Chapter 1.7

Chapter 5
Basic Network Topologies
2006/05/03
Download [leighton] Chapter 3.1.1
[leighton] Chapter 3.2.1

Chapter 6
Routing Strikes Back
2006/05/17
Download [leighton] Chapter 3.4

Chapter 7
Shared Variables
2006/05/24
Download Ivy Amortized Analysis

Chapter 8
Sorting
2006/05/31
Download [leighton] Chapter 1.6
[leighton] Chapter 3.5
[clr] Chapter 28

Chapter 9
Graph Algorithms
2006/06/07
Download [peleg] Chapter 8

Chapter 10
Distributed Dominating Set Approximation
2006/06/28
Download ---

Chapter 11
PRAM
2006/06/14
Download
pp. 233-238 (Introduction)
p. 241 (Brent's Lemma)
pp. 246-249 (Prefix Sum)
[jaja]

Chapter 12
Sorting on PRAM
2006/06/21
Download
[jaja]

Chapter 13
Self-Stabilization
2006/07/05
Download
Download
Chapters 1, 2 & 3
Download
For interested students
[garg]

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

References

Books:

[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