Pearls of Computer Science III
From Self-Organizing Systems Group
This lecture on selected areas in computer science is meant for interested students who want to look beyond the mainstream content of their bachelor courses. In the winter term 2009/2010, Riko Jacob and Thomas Fuhrmann present some especially beautiful ideas that form the basis of self-organizing systems:
- Overlay networks form virtual topologies on top of existing networks. Thereby, such networks can circumvent restrictions in the underlying network. Skype and BitTorrent, e.g., do not need central servers so that they have very low operational cost. In this lecture, we study the principles behind such systems. Starting from distributed hash tables we discuss distributed algorithms that allow us to build up overlay graphs from arbitrary network graphs. We also see how these ideas can provide self-organized routing in large-scale ad-hoc networks.
- Selfish nodes can cooperate, provided they adhere to certain rules. Engineering self-organizing systems requires to cleverly craft these rules. Studying several simple algorithms and considering game theoretical results we learn the dos and don'ts in self-organizing systems.
- Thinking about self-organizing systems requires models of such systems. But models may betray us so that theoretical results only correctly describe the model, not what we intended to model. Reviewing several illustrative examples, we learn not to trust a result unless we are sure that we can trust the model behind the analysis.
The lecture is given approximately weekly - depending on the schedule of the prospective students and the lecturers. Please contact Thomas Fuhrmann if you are interested to attend this lecture. The course language is a mix German and English.
| Date | Topic | Notes |
|---|---|---|
|
9. Nov |
Kick-off Meeting | |
|
16. Nov | Introduction to Computer Networks | |
|
23. Nov | Skip Graphs (Riko Jacob) | |
|
30. Nov | Overview: Peer-to-Peer Networks | |
|
7. Dez | Selfish Overlay Network Formation (Georgios Smaragdakis, Deutsche Telekom Labs) | |
|
14. Dez | Free Riding, Fairness, and BitTorrent | |
|
21. Dez | Network Coordinates | |
|
11. Jan | Linearization (Riko Jacob) | |
|
25. Jan | Routing Overhead (Riko Jacob) | Lecture Notes |
