Ferienakademie 2008, Course 1
Algorithms for Modern Communication Networks

• "M/S: Peer-to-Peer-Netzwerke" denotes the textbook:
  Peter Mahlmann and Christian Schindelhauer. Peer-to-Peer-Netzwerke. Springer, 2007.

• "KPR" denotes the lecture notes:
  Friedhelm Meyer auf der Heide. Kommunikation in Parallelen Rechenmodellen.

Topics

Please download the password protected pdf-files (denoted by ) to your system (right mouse click and "Save target as ...")

1. Parallel Computing Networks
   1. Online Routing on the Mesh and Offline Routing on the Benes Network [Protsenko,M.]
      • Einleitung und Permutationsrouting auf (n,d)-Gittern from KPR
   2. Online Routing on the Butterfly-Netzwerk: Probabilistic Analysis [Gubichev, A.]
      • For your talk just use the sections beginning with 6.2 from Oblivious Routing from KPR
      • Section 3.4.4 "The Average-Case Behavior of the Greedy Algorithm" (and Sec. 3.4.5) from "F. T. Leighton: Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes".
   3. Deterministic Routing on the Multibutterfly Network [Diebold, F.]
      • Das Multibutterfly-Netzwerk from KPR
      • F. T. Leighton and B. M. Maggs. Fast algorithms for routing around faults in multibutterflies and randomly-wired splitter networks. IEEE Transactions on Computers, 41:578-587, 1992.
      • F. T. Leighton and B. M. Maggs. Expanders might be practical: fast algorithms for routing aroundfaults on multibutterflies. Proc. 30th IEEE Symp. on Foundations of Computer Science (FOCS) pp. 384-389, 1989
2. Internet Algorithms
   4. Routing und Packet Forwarding: Shortest Paths and Autonomic Systems [Schmidt, T.]
      • Chapter 2 Das Internet - unter dem Overlay from M/S: Peer-to-Peer-Netzwerke to p. 28.
   5. Establishing the Connection and Avoiding of Congestion [Koopmann, G. B.]
      • Kapitel 2 Das Internet - unter dem Overlay von M/S: Peer-to-Peer-Netzwerke, pp. 28-47.
3. Peer-to-Peer Networks
   6. Peer-to-Peer Networks: Early Networks, Self-Organization, the Small-World Phenomenon [Baier, P.]
      • Chapter 3 Die ersten Peer-to-Peer-Netzwerke from M/S: Peer-to-Peer-Netzwerke.
      • Chapter 9 Selbstorganisation from M/S: Peer-to-Peer-Netzwerke to p. 183.
   7. Distributed Hash-Tables and CAN [Abdelghani, I.]
      • Kapitel 4 CAN: Ein Netzwerk mit adressierbaren Inhalten von M/S: Peer-to-Peer-Netzwerke.
      • The original paper for Distributed Hash Tables:
        D. Karger, E. Lehman, T. Leighton, R. Panigrahy, M. Levine, D. Lewin. Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web . In: Proc. 29th ACM Symposium on Theory of Computing (STOC), 1997, pp. 654-663.
   8. Chord: Taking Locality into Account [Rasoulian, A.]
      • Chapter 5 Chord von M/S: Peer-to-Peer-Netzwerke.
      • The original paper:
        I. Stoica, R. Morris, D. Liben-Nowell, D. R. Karger, M. F. Kaashoek, F. Dabek, H. Balakrishnan. Chord: A Scalable Peer-to-Peer Lookup Protocol for Internet Applications . IEEE/ACM Transactions on Networking 11 (2003) 17-32.
   9. Plaxton's Routing Method [Wederhake, L.]
      • C. G. Plaxton, R. Rajamaran, A. W. Richa. Accessing Nearby Copies of Replicated Objects in a Distributed Environment . In: Proc. 9th. ACM Symp. on Parallel Algorithms and Architectures (SPAA), 1997, pp. 311-320.
      • Chapter 6 Pastry und Tapestry from M/S: Peer-to-Peer-Netzwerke to p. 99.
   10. Pastry: Taking the Neighborhood into Account [Himmelmann, R.]
       • Chapter 6 Pastry und Tapestry von M/S: Peer-to-Peer-Netzwerke, pp. 100-114.
   11. Viceroy: Minimizing the Node Degree [Barthels, A. M.]
       • Chapter 7 Gradminimierte Netzwerke von M/S: Peer-to-Peer-Netzwerke, bis S. 136.
       • D. Malkhi, M. Naor, D. Ratajczak. Viceroy: a scalable and dynamic emulation of the butterfly. Proc. 21st ACM Symp. on Principles of Distributed Computing (PODC), pp. 183-192, 2002.
   12. Distance Halving: The Continuous-discrete Approach [Ohst, M.]
       • Chapter 7 Gradminimierte Netzwerke from M/S: Peer-to-Peer-Netzwerke, pp. 136-144.
   13. Ordered Indexing: Skip-Net [Xue, L.]
       • Chapter 7 Geordnete Indizierung from M/S: Peer-to-Peer-Netzwerke, pp. 162-172.
       • N. Harvey, M. B. Jones, S. Saroiu, M. Theimer, A. Wolman. SkipNet: a scalable overlay network with practical locality properties. Proc. 4th USENIX Symposium on Internet Technologies and Systems - Volume 4. (14 pages)
       • N. Harvey, M. B. Jones, S. Saroiu, M. Theimer, A. Wolman. SkipNet: a scalable overlay network with practical locality properties. (long version: 38 pages)
   14. A Censorship Resistant Peer-to-Peer Network [Minnerup, P.]
       • A. Fiat, J. Saia. Censorship Resistant Peer-to-Peer Content Addressable Networks , 13th ACM-SIAM Symp. on Discrete Algorithms (SODA), 2002, pp. 94-103.
       • Chapter 10 Sicherheit from M/S: Peer-to-Peer-Netzwerke, pp. 206/7.

Navigation in the textbook "Peer-to-Peer-Netzwerke"

• Vorwort und Inhaltsverzeichnis von M/S: Peer-to-Peer-Netzwerke.
• Alle Kapitel des Buchs Peer-to-Peer-Netzwerke bei Springerlink.
• Die Anhänge, das Literaturverzeichnis und der Index von M/S: Peer-to-Peer-Netzwerke.

References for all

• Peter Mahlmann and Christian Schindelhauer. Peer-to-Peer-Netzwerke. Springer, 2007.
• Friedhelm Meyer auf der Heide. Kommunikation in Parallelen Rechenmodellen. Vorlesungsskript
• Th. H. Cormen, Ch. E. Leiserson, R. L. Rivest, C. Stein.
  • Introduction to Algorithms. The MIT Press (2nd ed.) September 2001.
  • Algorithmen - Eine Einführung. Oldenbourg, (2.Aufl.) März 2007.
• Th. Schickinger, A. Steger. Diskrete Strukturen 2: Wahrscheinlichkeitstheorie und Statistik. Springer, 2002.
• S. Androutsellis-Theotokis, D. Spinellis. A Survey of Peer-to-Peer Content Distribution Technologies . ACM Computing Surveys, Vol. 36, No. 4, Dec. 2004, pp. 335-371. (a survey paper)