Page Content
Foundations of Distributed Systems (Integrated course, SoSe 2012)
All computing systems nowadays are distributed, ranging from Internet-scale services to multiprocessors. Therefore, understanding the principles of distributed computing is increasingly important in all aspects of designing and engineering modern computing systems.
Students that complete this module will get a basic understanding of how to design distributed algorithms, reason about their correctness, and derive complexity bounds for distributed computing problems. The notion of a system implementation is treated here in the algorithmic sense (there will be no Java or C code).
Overview
Lecturers: | Petr Kuznetsov, Stefan Schmid, Uwe Nestmann (FG MTV) |
Additional contact person: | Srivatsan Ravi |
Event type: | Integrated course (Integrierte Veranstaltung) |
Area: | Master of Computer Science: Dependabale Systems, Communication-based Systems (Master Informatik: Verlässliche Systeme, Kommunikationsbasierte Systeme) Master of Computer Engineering: Software Engineering (Master Technische Informatik: Software Engineering) |
Module: | MINF-VS-FDS.S12 |
exam&module registration: | tba |
SWS: | 4 |
ECTS/LP: | 6 |
Time: | tuesdays, 12–2 p.m., weekly |
First meeting: | 10 April 2012 |
Room: | Auditorium 2 (TEL 20) |
Tutorial: | mondays, 4–6 p.m., weekly TEL 1118/19 |
Course ID: | 0432 L 819 / 0434 L 350 |
Audience: | bachelor students after their basic studies (from the fifth semester on), master students, and Diplom students |
Prerequisites: | No particular module, but maturity in mathematics, algorithms, and programming is expected. |
Exam: | oral, further details will be announced later |
Further information: | see corresponding ISIS page |
Content
Shared-memory and message-passing algorithms; fault-tolerance; shared-memory transformations; consensus and state-machine replication; message passing; network topologies and architectures; local algorithms and scalability; time and message complexity; leader election, medium access, graph coloring; robust algorithms for dynamic networks; peer-to-peer networks; social networks: game theory and incentive-compatible algorithms
Registration
If you are interested in attending, please make sure you are subscribed to this course in ISIS to receive information and announcements.
A module registration is also obligatory for Master studetns. Further information will be given in the lecture or via ISIS.
Download of lecture slides
- Class 01a: Overview: Message Passing (FDS 2012) PDF, 788 KB
- Class 01b: Overview: Shared memory (FDS 2012) PDF, 7 MB
- Class 02: safety and liveness (FDS 2012) PDF, 200 KB
- Class 03: shared memory basics (FDS 2012) PDF, 148 KB
- Class 04: implementing an atomic bit (FDS 2012) PDF, 194 KB
- Class 05: atomic and immediate snapshots (FDS 2012) PDF, 213 KB
- Class 06: atomic and immediate snapshots (part 2; FDS 2012) PDF, 179 KB
- Class 07: consensus and set agreement (FDS 2012) PDF, 198 KB
- Class 08: universality and consensus numbers (FDS 2012) PDF, 121 KB
- Class 09: Topology (FDS 2012) PDF, 2 MB
- Class 10: Leader Election (FDS 2012) PDF, 362 KB
- Class 11: Trees (FDS 2012) PDF, 915 KB
- Class 12: Vertex Coloring (FDS 2012) PDF, 448 KB
- Class 13: Distributed Maximal Independent Sets (FDS 2012) PDF, 782 KB
- Class 14: Locality Lower Bounds (Coloring; FDS 2012; UPDATED) PDF, 568 KB
Exercise sheets
- Exercise Set 01: shared memory transformations (FDS 2012) PDF, 41 KB
- Exercise Set 02: atomic-bit construction (due May 7, FDS 2012) PDF, 56 KB
- Exercise Set 03: atomic and immediate snapshot (due May 14, FDS 2012; updated) PDF, 40 KB
- Exercise Set 04: immediate snapshot (due May 21; FDS 2012; updated) PDF, 50 KB
- Exercise Set 05: consensus (due June 4; FDS 2012) PDF, 39 KB
- Exercise Set 06: Asymptotic Notations and Graph Terminologies (due June 11; FDS 2012) PDF, 125 KB
- Exercise Set 07: Topology (due June 11; FDS 2012) PDF, 132 KB
- Exercise Set 08 (due June 18; FDS 2012) PDF, 50 KB
- Exercise Set 09 (due June 25; FDS 2012) PDF, 103 KB
- Exercise Set 10 (due July 9; FDS 2012) PDF, 103 KB
General Literature
- Lynch, N: Distributed Algorithms. Morgan Kaufmann Publishers, 1996.
- H. Attiya, J. Welch. Distributed Computing: Fundamentals, Simulations and Advanced Topics (2nd edition). Wiley. 2004
- M. Herlihy and N. Shavit. The art of multiprocessor programming. Morgan Kaufman, 2008
- David Peleg, Distributed Computing: A Locality Sensitive Approach, SIM, 1987.
Zusatzinformationen / Extras
Quick Access:
Auxiliary Functions
0432 L 819 / 0434 L350
Integrierte LV (VL mit UE)
Lecturer: Petr Kuznetzsov, Stefan Schmid, Uwe Nestmann
Period:
10.04.2012 to 31.08.2012
Mo 16:00 - 18:00 o'clock
Tu 12:00 - 14:00 o'clock
Location: Auditorium 2 (tue/Di), TEL 1118/19 (mon/Mo)
Website
ISIS
Hint:
Tue: Lecture; Mon: Tutorial