Distributed Computing
ETH Zurich

Principles of Distributed Computing (SS 2007)

(Network Algorithms)

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.

Written exam: HG F5, 14:00-15:30, August 23, 2006.
Previous exams: SS 03, SS 04.

Lecture by Roger Wattenhofer, Peter Widmayer, Subhash Suri,
Wednesday 8.15-10.00 @ CAB G51.

Exercises by Thomas Locher, Yvonne Anne Oswald, Davide Bilo,
Wednesday 10.15-11.00 @ CAB G52. No exercise meeting: March 21, 2007.

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

Chapter 5
Small World

Chapter 6
Graph Algorithms
Download [peleg] Chapter 8

Chapter 7
Shared Variables
Download Ivy Amortized Analysis

Chapter 8
Basic Network Topologies
Download [leighton] Chapter 3.1.1
[leighton] Chapter 3.2.1

Chapter 9
Routing Strikes Back
Download [leighton] Chapter 3.4

Chapter 10
Network Flows I
Notes [clr]

Chapter 11
Network Flows II
Notes [clr]

Chapter 12
Network Flows III
Notes [clr]

Chapter 13
Network Failure
Notes [clr]

Chapter 14
Network Failure
Notes [clr]

Exercises material

Title Exercise Sample Solution

Exercise 1
Assigned: 2007/03/28
Due: 2007/04/04
Download Download

Exercise 2
Assigned: 2007/04/04
Due: 2007/04/11
Download Download

Exercise 3
Assigned: 2007/04/11
Due: 2007/04/18
Download Download

Exercise 4
Assigned: 2007/04/25
Due: 2007/05/02
Download Download

Exercise 5
Assigned: 2007/05/02
Due: 2007/05/09
Download Download

Exercise 6
Assigned: 2007/05/09
Due: 2007/05/16
Download Download

Exercise 7
Assigned: 2007/05/16
Due: 2007/05/23
Download Download

Exercise 8
Assigned: 2007/05/23
Due: 2007/05/30
Download Download

Exercise 9
Assigned: 2007/05/30
Due: 2007/06/06
Download Download

Exercise 10
Assigned: 2007/06/06
Due: 2007/06/13
Download Download

Exercise 11
Assigned: 2007/06/13
Due: 2007/06/20
Download Download

Exercise 12
Assigned: 2007/06/20
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 or 0-262-03141-8
[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: Distributed MST

Chapter 5: Small World

Chapter 6: Graph Algorithms

Chapter 7: Shared Variables

Chapter 8: Basic Network Topologies

Chapter 9: Routing Strikes Back

Chapter 10 - 12: Network Flows I - III