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.

News
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
Introduction
2007/03/21
Download [peleg] Preface & Chapter 1

Chapter 1
Vertex Coloring
2007/03/21
Download [peleg] Chapter 7

Chapter 2
Leader Election
2007/03/28
Download [attiya] Chapter 3
[hkpru] Chapter 8

Chapter 3
Tree Algorithms
2007/04/04
Download [peleg] Chapter 3
[peleg] Chapter 5
[hkpru] Chapter 7

Chapter 4
Distributed MST
2007/04/11
Download

Chapter 5
Small World
2007/04/18
Download

Chapter 6
Graph Algorithms
2007/04/25
Download [peleg] Chapter 8

Chapter 7
Shared Variables
2007/05/02
Download Ivy Amortized Analysis

Chapter 8
Basic Network Topologies
2007/05/09
Download [leighton] Chapter 3.1.1
[leighton] Chapter 3.2.1

Chapter 9
Routing Strikes Back
2007/05/16
Download [leighton] Chapter 3.4

Chapter 10
Network Flows I
2007/05/23
Notes [clr]

Chapter 11
Network Flows II
2007/05/30
Notes [clr]

Chapter 12
Network Flows III
2007/06/06
Notes [clr]

Chapter 13
Network Failure
2007/06/13
Notes [clr]

Chapter 14
Network Failure
2007/06/20
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

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