Distributed Computing Group

Principles of Distributed Computing (SS 2004)

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. It reaches the fundamental issues underlying the design of distributed systems communication, coordination, synchronization, uncertainty, and essential algorithmic ideas and lower bound techniques.

One of the main themes of recent research in distributed algorithms is "locality" (also known as decentralized computing, or peer-to-peer computing). 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 (Vernetzte Systeme 37-019), and fundamentals of algorithms & complexity (Theoretische Informatik 37-402). Note that this course is in both the theory and the distributed systems major.

Course language: English

Lecture by Roger Wattenhofer, Wednesday 8.15-10.00 @ HRS F5.

A corrected version of Chapter 11 is now online.

Exercises by Fabian Kuhn, Regina O'Dell, Wednesday 10.15-11.00 @ HRS F5.

Useful references

The exam will take place on Monday, October 4th. Here is a copy of last year's exam to help in your preparation. The exam will last 90 minutes, no aids allowed.

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

Chapter 3
Tree Algorithms
Download [peleg] Chapter 3
[peleg] Chapter 5

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
Fault-Tolerant Distributed Systems
Download ---

Chapter 9
Asynchronous Byzantine Agreement
Download ---

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

Chapter 11
Graph Algorithms
Download [peleg] Chapter 8

Chapter 12
Distributed Dominating Set Approximation
Download ---

Exercises material

Title Exercise Sample Solution

Exercise 1
Assigned: 2004/03/31
Due: 2004/04/07
Download Download

Exercise 2
Assigned: 2004/04/07
Due: 2004/04/14
Download Download

Exercise 3
Assigned: 2004/04/14
Due: 2004/04/21
Download Download

Exercise 4
Assigned: 2004/04/21
Due: 2004/04/28
Download Download

Exercise 5
Assigned: 2004/05/05
Due: 2004/05/12
Download Download

Exercise 6
Assigned: 2004/05/12
Due: 2004/05/26
Download Download

Exercise 7
Assigned: 2004/05/26
Due: 2004/06/02
Download Download

Exercise 8
Assigned: 2004/06/02
Due: 2004/06/09
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
[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: Fault-Tolerant Distributed Systems

Chapter 9: Asynchronous Byzantine Agreement

Chapter 10: Sorting

Chapter 11: Graph Algorithms

Chapter 12: Distributed Dominating Set Approximation