direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

Theory of Distributed Computing 1: Algorithms and Lower Bounds (Integrated course, SoSe 2011)

We live in the age of distributed systems: Virtually any computer architecture or application today is distributed. Examples include multi-core computers, peer-to-peer systems, or sensor networks. All these applications have in common that the entities have certain degrees of freedom (e.g., have their own hardware or code) and many entities are active at any time. Despite these commonalities, there are important differences, e.g., peer-to-peer systems may operate more asynchronously than multi-core computers.

In this lecture we study what can and cannot be computed in the different kinds of distributed systems. We start with the shared memory model and consider fundamental problems such as the election of a leader. We then extend our investigations to distributed systems that connect the entities via a communication network. We compare different networks and introduce different complexity measures such as time and message complexity. We then revisit important problems such as leader election or vertex coloring for this model. Finally, if time permits, dynamic, robust, and selfish networks are discussed.


  • The lecture is over.


Petr Kuznetsov [1], Stefan Schmid,
Uwe Nestmann [2] (FG MTV)
Additional contact person:

Srivatsan Ravi [3]
Event type:

Integrated course (Integrierte Veranstaltung)
Diplom Informatik: tba
Master of Computer Science: Dependabale Systems (Master Informatik: Verlässliche Systeme)
Master of Computer Engineering: Software Engineering (Master Technische Informatik: Software Engineering)

exam&module registration:
via exam office (Prüfungsamt)
tuesdays, 12–2 p.m., weekly
First meeting:
12 April 2011
Auditorium 1 (TEL 20)

Course ID:
0432 L 817
bachelor students after their basic studies (from the fifth semester on), master students, and Diplom students
No particular module, but maturity in mathematics and programming is expected.
written, further details will be announced later
Further information:

see corresponding ISIS page [4]



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.


There will be exercises (exercise sheets). You need 50% of the possible points to pass.


Written exam. Further information will be announced in the lecture or via ISIS.

More slides and further information (research papers, exercises) are available on the ISIS page [5].


General Literature

  • Nancy Lynch. Distributed Algorithms. Morgan Kaufmann Publishers, 1996. (english)
  • H. Attiya and J. Welch. Distributed Computing: Fundamentals, Simulations and Advanced Topics (2nd edition). Wiley. 2004 (english)
  • M. Herlihy and N. Shavit. The art of multiprocessor programming. Morgan Kaufman, 2008. (english)
  • David Peleg. Distributed Computing: A Locality-Sensitive Approach. SIAM, Philadelphia, PA, USA, 2000. (english)
  • Juraj Hromkovic, Ralf Klasing, Andrzej Pelc, Peter Ruzicka, and Walter Unger.Dissemination of Information in Communication Networks.Springer. 2005 (english)
  • Frank Thomson Leighton.Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes.Morgan Kaufmann Publishers, 1991 (english)
  • Thomas Cormen, Charles Leiserson, and Ronald Rivest.Introduction to Algorithms.The MIT Press, 1998 (english)

Further Literature on certain topics

  • Fabian Kuhn, Stefan Schmid, and Roger Wattenhofer. Towards Worst-Case Churn Resistant Peer-to-Peer Systems. Journal Distributed Computing (DIST), 22(4), 249-267, Springer, May 2010. (pdf [6])
  • Moni Naor, Udi Wieder. Novel architectures for P2P applications: The continuous-discrete approach. ACM Transactions on Algorithms (TALG), 3(3), August 2007. (link [7])
  • J. Kleinberg. Navigation in a Small World. Nature, Volume 406(2000), 845 (pdf [8])
  • Thomas Locher, Stefan Schmid, and Roger Wattenhofer. eDonkey & eMule's Kad: Measurements & Attacks. Fundamenta Informaticae, Volume 110, IOS Press, 2011.
  • Riko Jacob, Andréa Richa, Christian Scheideler, Stefan Schmid, and Hanjo Täubig. A Polylogarithmic Time Algorithm for Distributed Self-Stabilizing Skip Graphs. 28th ACM Symposium on Principles of Distributed Computing (PODC) 2009. (pdf [9])
  • Christian Scheideler and Stefan Schmid. A Distributed and Oblivious Heap. 36th International Colloquium on Automata, Languages and Programming (ICALP) 2009. (pdf [10])

Lehre / Teaching, SoSe 2011

  • Internet Routing (VL) [11]
  • Internet Security (VL) [12]
  • Network Optimization by Randomization (IV) [13]
  • Theory of Distributed Computing 1 (IV) [14]
  • NA: Internet Measurement (SE) [15]
  • Routerlab (PR) [16]

Registration at Prüfungsamt

Exam and module
registration at INET
take place via the
Prüfungsamt (exam

Theory of Distributed Computing 1: Algorithms and Lower Bounds
0432 L 817
Integrierte LV (VL mit UE)

Lecturer: Petr Kuznetsov, Stefan Schmid, Uwe Nestmann

12.04.2011 to 12.07.2011

Tu 12:00 - 14:00 o'clock

Location: Auditorium 1 (TEL 20)

Website [17]
ISIS [18]

Complete domains

...of e-mail addresses
@inet =
@tub = @tu-berlin.de
------ Links: ------

Zusatzinformationen / Extras

Quick Access:

Schnellnavigation zur Seite über Nummerneingabe

Auxiliary Functions

Copyright TU Berlin 2008