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


New:
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
Introduction
2004/03/31
Download [peleg] Preface & Chapter 1

Chapter 1
Vertex Coloring
2004/03/31
Download [peleg] Chapter 7

Chapter 2
Leader Election
2004/04/07
Download [attiya] Chapter 3

Chapter 3
Tree Algorithms
2004/04/14
Download [peleg] Chapter 3
[peleg] Chapter 5

Chapter 4
Routing
2004/04/21
Download [leighton] Chapter 1.7

Chapter 5
Basic Network Topologies
2004/04/28
Download [leighton] Chapter 3.1.1
[leighton] Chapter 3.2.1

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

Chapter 7
Shared Variables
2004/05/12
Download ---

Chapter 8
Fault-Tolerant Distributed Systems
2004/05/26
Download ---

Chapter 9
Asynchronous Byzantine Agreement
2004/06/02
Download ---

Chapter 10
Sorting
2004/06/09
Download [leighton] Chapter 1.6
[leighton] Chapter 3.5
[clr] Chapter 28

Chapter 11
Graph Algorithms
2004/06/16
Download [peleg] Chapter 8

Chapter 12
Distributed Dominating Set Approximation
2004/06/23
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

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