Distributed Computing Group


Principles of Distributed Computing (SS 2003)

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, Christian Cachin, Wednesday 8.15-10.00 @ HRS F5.

Exercises by Fabian Kuhn, Regina Bischoff, Wednesday 10.15-11.00 @ HRS F5.

Note that room and time have been changed!

Useful references

Lecture material


Title Lecture Notes (PDF) References

Chapter 0
Introduction
2002/04/02
Download [peleg] Preface & Chapter 1

Chapter 1
Vertex Coloring
2002/04/02
Download [peleg] Chapter 7

Chapter 2
Leader Election
2002/04/09
Download [attiya] Chapter 3

Chapter 3
Tree Algorithms
2002/04/16
Download [peleg] Chapter 3
[peleg] Chapter 5

Chapter 4
Routing
2002/04/23
Download [leighton] Chapter 1.7

Chapter 5
Basic Network Topologies
2002/04/30
Download [leighton] Chapter 3.1.1
[leighton] Chapter 3.2.1

Chapter 6
Routing Strikes Back
2002/04/30
Download [leighton] Chapter 3.4

Chapter 7
Quorum Systems
2002/05/07
Download ---

Chapter 8
Fault-Tolerant Distributed Systems
2002/05/14
Download ---

Chapter 9
Shared Variables
2002/05/21
Download ---

Chapter 10
Sorting
2002/05/28
Download [leighton] Chapter 1.6
[leighton] Chapter 3.5
[clr] Chapter 28

Chapter 11
Asynchronous Byzantine Agreement
2002/06/04
Download ---

Chapter 12
Graph Algorithms
2002/07/02
Download [peleg] Chapter 8

Guest Lecture by Hagit Attiya
Algorithms that Adapt to Contention
2002/06/18
Download ---

Exercises material


Title Exercise Sample Solution

Exercise 1
Assigned: 2002/04/02
Due: 2002/04/09
Download  

Exercise 2
Assigned: 2002/04/09
Due: 2002/04/16
Download  

Exercise 3
Assigned: 2002/04/16
Due: 2002/04/23
Download  

Exercise 4
Assigned: 2002/04/23
Due: 2002/04/30
Download  

Exercise 5
Assigned: 2002/05/07
Due: 2002/05/14
Download  

Exercise 6
Assigned: 2002/05/14
Due: 2002/05/21
Download  

Exercise 7
Assigned: 2002/05/21
Due: 2002/05/28
Download  

Exercise 8
Assigned: 2002/05/14
Due: 2002/05/21
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: Quorum Systems

Chapter 8: Fault-Tolerant Distributed Systems

Chapter 9: Shared Variables

Chapter 10: Sorting

Chapter 11: Asynchronous Byzantine Agreement

Chapter 12: Graph Algorithms

Guest Lecture by Hagit Attiya