Seminar: Algorithmen für Peer-to-Peer Netzwerke
Allgemeines
- Betreuung: Klemens Böhm (KB), Marco Gaertler (MG), Dr. rer. nat. Robert Görke (RG), Peter Sanders (PS), Prof. Dr. Dorothea Wagner (DW)
- Teilnahme: Die Teilnehmerzahl ist auf zwölf Personen begrenzt. Der Kurs kommt ab einer Mindestzahl von vier Teilnehmern zustande.
Die Anmeldung ist abgeschlossen.
Termine
| Vortragender | Thema | Betreuer | Datum | Ausarbeitung |
|---|---|---|---|---|
| Max Laier | Verteilter Mechanismenentwurf | KB | 31.05 | |
| Joel Lang | verteiltes Pagerank [SYYW03] | RG | 07.06 | |
| Kevin Kilgour | Robustheit von Pagerank und Trust-Metriken | KB | 14.06 | |
| Tsoncho Vasiler | Gossipping/Rumor Spreading | PS | 21.06 | |
| Florian Hübner | Overlay Netzwerke [SMK+01],[KK03] | MG | 28.06 | |
| Pehr Söderman | Lastbalancieren [KR04] | PS | 05.07 |
Inhalt
Ein Peer-to-Peer-Netzwerk ist ein verteiltes System, in dem die Teilnehmer sowohl Client als auch Server-Aufgaben wahrnehmen. Hierfür stehen den Teilnehmern nur bidirektionale Verbindungen zur Verfügung, wobei zentrale Strukturen absichtlich vermieden werden. Durch Datentauschbörsen im Internet wie der ehemalige Napster oder Gnutella sind solche Netzwerke bekannt geworden. In Wirklichkeit ist der Peer-to-Peer-Ansatz aber viel breiter und hat zahlreiche Anwendungen, z. B. verteiltes Wissensmanagment, Anonymisierung, Online-Archivierung.
Im Rahmen dieses Seminars werden algorithmische Fragestellungen von Peer-to-Peer-Netzwerken betracht, etwa:
- Wie baut man ein solches Netzwerk auf?
- Wie kann man effizient darin navigieren und suchen?
- Welche Probleme lassen sich in diesen verteilten Netzwerken (effizient) lösen und welchen Preis muß man gegenüber einer zentralistischen Struktur bezahlen?
- Wie kann man anfallende Aufgaben und Lasten gerecht verteilen?
- Wie groß sind die Unterschiede, wenn nicht alle Teilnehmer über die gleiche Ressourcen verfügen?
- Wie vertrauenswürdig bzw. robust sind diese Netzwerke?
- Gibt es Zensur oder Anonymität?
Literatur
- [SYYW03] Shu Ming Shi, Jin Yu, Guang Wen Yang, and Ding Xing Wang. Distributed page rank in structured p2p networks. In ICPP '03: Proceedings of the 32ns International Conference on Parallel Processing, pages 179-186. IEEE Computer Society Press, 2003.
www - [SMK+01] Ion Stoica, Robert Morris, David R. Karger, M. Frans Kaashoek, and Hari Balakrishnan. Chord: A scalable peer-to-peer lookup service for internet applications. In SIGCOMM '01: Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, pages 149-160. ACM Press, 2001.
www - [KK03] M. Frans Kaashoek and David R. Karger. Koorde: A simple degree-optimal distributed hash table. In Peer-to-Peer Systems II: Second International Workshop, volume 2735 of Lecture Notes in Computer Science, pages 98-107. Springer-Verlag, October 2003.
www - [KR04] David R. Karger and Matthias Ruhl. Simple efficient load balancing algorithms for peer-to-peer systems. In SPAA '04: Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, pages 36-43. ACM Press, 2004.
www