Distributed Computing
ETH Zurich

Principles of Distributed Computing (SS 2005)

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 basics of distributed computing, highlighting common themes and techniques. We study the fundamental issues underlying the design of distributed systems: communication, coordination, synchronization, uncertainty. We explore essential algorithmic ideas and lower bound techniques.

One of the main themes of recent research in distributed algorithms is "locality" (as utilized by decentralized/peer-to-peer systems). Networks grow fast, thus locality and scalability become first-class issues. We discuss some of the most fascinating local distributed algorithms in the second part of the course.

Course pre-requisites: Basic networking knowledge (e.g. Vernetzte Systeme), and fundamentals of algorithms & complexity (e.g. Theoretische Informatik). Note that this course is in both the theory and the distributed systems major.

Course language: English.

Prospective written exam date: October 12, 2005.
Previous exams: SS 03, SS 04.

Lecture by Roger Wattenhofer, Peter Widmayer,
Wednesday 8.15-10.00 @ RZ F21.

Exercises by Regina O'Dell, Fabian Kuhn, Pascal von Rickenbach,
Wednesday 10.15-11.00 @ RZ F21. Next and final exercise meeting: June 22, 2005.

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 ---

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

Chapter 9
Graph Algorithms
Download [peleg] Chapter 8

Fault Tolerance I
--- [attiya] pp. 91-94, 102-105, and 109-111

Fault Tolerance II
--- [attiya] pp. 111-114
[garg] pp. 307-314

Chapter 10
Distributed Dominating Set Approximation
Download ---

--- see Articles

Exercises material

Title Exercise Sample Solution

Exercise 1
Assigned: 2005/04/06
Due: 2005/04/13
Download Download

Exercise 2
Assigned: 2005/04/13
Due: 2005/04/20
Download Download

Exercise 3
Assigned: 2005/04/20
Due: 2005/04/27
Download Download

Exercise 4
Assigned: 2005/04/27
Due: 2005/05/04
Download Download Revised!

Exercise 5
Assigned: 2005/05/04
Due: 2005/05/11
Download Download

Exercise 6
Assigned: 2005/05/11
Due: 2005/05/25
Download Download

Exercise 7
Assigned: 2005/05/25
Due: 2005/06/01
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
[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