Distributed Computing
ETH Zurich

Principles of Distributed Computing (FS 2014)

This page is no longer maintained. Up-to-date versions of lecture and exercise material can be found here.

Distributed computing is essential in modern computing and communications systems. Examples are on the one hand large-scale networks such as the Internet, and on the other hand multiprocessors such as your new multi-core laptop. This course introduces the principles of distributed computing, emphasizing the fundamental issues underlying the design of distributed systems and networks: communication, coordination, fault-tolerance, locality, parallelism, self-organization, symmetry breaking, synchronization, uncertainty. We explore essential algorithmic ideas and lower bound techniques, basically the "pearls" of distributed computing. We will cover a fresh topic every week.

Course pre-requisites: Interest in algorithmic problems. (No particular course needed.)

Course language: English.

Lecture by Roger Wattenhofer Wednesday 8.15-10.00 @ CAB G 51.

Exercises organized by Philipp Brandes, Wednesday 10.15-12.00 @ CAB G 52 and Wednesday 13.15-15.00 @ LFW E 13

The exam will take place on Saturday, August 16 from 9am to 11am @ HIL F61

Sample exams: 2003, 2004, 2005, 2006, 2007, 2009
Please note that the topics covered in this course change from year to year and thus some of the questions in those exams are not covered this year.

You can take a look at your corrected exam on Wednesday, the 17th of September, and on Monday, the 22nd of September. To do so, please visit our secretary Friederike Brütsch(office ETZ G88) on one of these days from from 9:30am to 11am or 12:30pm to 3pm.


Lecture material


Title Lecture Notes Exercises Responsible Assistant Additional Material

Chapter 0
Introduction
PDF 1:1
PDF 2:1
Exercises

Chapter 1
Vertex Coloring
Array
PDF 1:1
PDF 2:1
Exercises
[Slides] http://www.net.t-labs.tu-berlin.de/~stefan/netalg13-5-coloring.pdf
[ by S.Schmid, TU Berlin]
/members/pbrandes

Chapter 2
Leader Election
Array
PDF 1:1
PDF 2:1
Exercises
[Slides] http://www.net.t-labs.tu-berlin.de/~stefan/netalg13-3-leader.pdf
[ by S.Schmid, TU Berlin]
/members/bissigp

Chapter 3
Tree Algorithms
Array
PDF 1:1
PDF 2:1
Exercises
[Slides] http://www.net.t-labs.tu-berlin.de/~stefan/netalg13-4-tree.pdf
[ by S.Schmid, TU Berlin]
/members/bissigp

Chapter 4
Distributed Sorting
Array
PDF 1:1
PDF 2:1
Exercises
[Slides] http://www.net.t-labs.tu-berlin.de/~stefan/netalg13-9-sort.pdf
[ by S.Schmid, TU Berlin]
/members/kolsteph

Chapter 5
Shared Memory
Array
PDF 1:1
PDF 2:1
Exercises
[Slides] http://www.net.t-labs.tu-berlin.de/~stefan/netalg13-9-shared-mem.pdf
[ by S.Schmid, TU Berlin]
/members/juitto

Chapter 6
Shared Objects
Array
PDF 1:1
PDF 2:1
[Slides] http://www.net.t-labs.tu-berlin.de/~stefan/netalg13-9-shared-objects.pdf
[ by S.Schmid, TU Berlin]
/members/brandts

Chapter 7
Maximal Independent Set
Array
PDF 1:1
PDF 2:1
Exercises
[Slides] references/MISnLocalitySlidesRW.pdf
[ by R. Wattenhofer] Slides
[http://www.net.t-labs.tu-berlin.de/~stefan/netalg13-6-MIS.pdf] by S.Schmid, TU Berlin
/members/langnert

Chapter 8
Locality Lower Bounds
Array
PDF 1:1
PDF 2:1
Exercises
[Slides] http://www.net.t-labs.tu-berlin.de/~stefan/fds07-lowerbound.pdf
[ by S.Schmid, TU Berlin] Ramsey Theory Slides
[references/locality_slides.pdf] by J. Suomela
[Alternative Version] references/locality_slides_alternate.pdf
[ thanks!]
/members/foklaus

Chapter 9
Social Networks
Array
PDF 1:1
PDF 2:1
[Slides] references/stefan/class03-social.pdf
[ by S.Schmid, TU Berlin]
/members/mikoenig

Chapter 10
Synchronizers
Array
PDF 1:1
PDF 2:1
Exercises
[Slides] http://www.net.t-labs.tu-berlin.de/~stefan/netalg13-9-synchronizers.pdf
[ by S.Schmid, TU Berlin]
/members/seidelj

Chapter 11
Hard Problems
Array
PDF 1:1
PDF 2:1
[Slides] references/diameter.pdf
[ some additional Slides] Animation of APSP Algorihm
[http://users.ics.aalto.fi/suomela/apsp/] by Jukka Suomela
/members/brandts

Chapter 12
Wireless Protocols
Array
PDF 1:1
PDF 2:1
[Slides] references/podc_wireless.pdf
[ by Y.-A. Pignolet]
/members/pbrandes

Chapter 13
Stabilization
Array
PDF 1:1
PDF 2:1
/alumni/barkelle

Chapter 14
Peer-to-Peer Computing
Array
PDF 1:1
PDF 2:1
Exercises
[Slides] references/stefan/class01mp-topology.pdf
[ by S.Schmid, TU Berlin] Slides
[references/p2p_slides.pdf] from a talk at P2P
/members/mikoenig


References

These books are available at CS text book collection.

[]
[]
[]
[]
[]