You are here: Home Lehre Frühere Veranstaltungen Universität Freiburg Peer-to-Peer Networks WS15
Document Actions

Peer-to-Peer Networks


Lecture of Prof. Christian Schindelhauer


  • 12.10.2015 Webpage online
  • 19.10.2015 First lecture
  • 10.02.2016 last lecture


Peer-to-peer networks started in 1999 when the 19 year old Shawn (Napster) Fanning programmed a simple network software which facilitated a distributed file sharing over the Internet. The direct access is called peer to peer since the server of this small network just served as a mediator and not as a database system storing all the data. The following year Gutella was released as the first full peer-to-peer network allowing also the indexing and search in full peer-to-peer mode. Yet, Gnutella was slow and unreliable. The inefficiency of Gnutella was the chief motivation to invent better peer-to-peer networks. In 2001 the scientific world saw CAN and Chord as such networks with an efficient search and soon further networks followed. While researcher kept improving the distributed network algorithms, programmers released better software implementing these ideas. The dark side of this story is the misuse of theses peer-to-peer networks for massive copyright infringements. Although this is not a problem specific to peer-to-peer networks, the lack of a central client providing the material made it harder to find the evil-doers.  The goal of this lecture is to present methods and algorithms suited for the design of up-to-date peer-to-peer networks. The lecture aims at students studying at least four semester of computer science for bachelor or master of science. As prerequisites participants should have basic knowledge in algorithms and computer networks (as being taught in Datenstrukturen und Algorithmen and Systeme II). 

Possible topics of the lectures are among the following

  • Napster
  • Gnutella
  • CAN
  • Chord
  • Pastry
  • Distance-Halving, Koorde
  • Self-organization
  • Kelips, epidemic algorithms
  • Anynomity
  • Security




  • Lecture
    • Monday, 16:15 - 18:00, room 101-01-018
    • Wednesday, 10:15 - 11:00, room 101-01-018
  • Exercises
    • Joan Bordoy and Sebastian Sester
    • Wednesday, 11:15 - 12:00, room 101-01-018 
  • Exams
    • 19.02.2016 09:00-11:50, room 051-002-007
    • 26.02.2016 09:00-10:05, room 051-002-007
    • 04.03.2016 09:00-15:45, room 051-002-007
    • 11.03.2016 09:00-17:30, room 051-002-007


Please use the forum for general questions about the lecture. Maybe your question and the answer is probably interesting to other students. Please feel free to start new threads and interesting discussion.

Please provide us with feedback for this course



  1. Lecture Introduction, Motivation, Napster and Gnutella (19.10.2015, version 19.10.2015)  01 - Intro (pdf), 02 - Napster & Nutella pdf
  2. Lecture Napster and Gnutella (21.10.2015, version 19.10.2015) 02 - Napster & Nutella pdf 
  3. Lecture CAN (26./28.10.2015, version 19.10.2015) 03 - CAN (pdf), annotated slides pdf
  4. Lecture Chord (02.11.2015, version 27.10.2015) 04 - Chord (pdf), annotated slides pdf
    Dhash++, 04.11.2015 annotated slides pdf
  5. Lecture Pastry (09.11.2015, slides pdf, annotated slides pdf)
  6. Lecture Probability Theory, 11.11.2015, slides pdf, annotated slides pdf
  7. Lecture Distance Halving & Koorde (16./18.11.2015,  slides pdf annotated slides part 1, part 2)
  8. Lecture Kelps & Epidemic Algorithms (23.11.2015, ,  slides pdf, annotated slides part 1,  part 2)
  9. Lecture Random Graphs (02.12.2015,  slides pdf,  annotated slides part 1)
  10. Lecture Fast Download (07.12.2015, pdf annotated slides part 1part 2 part 3)
  11. Lecture Game Theore (21.12.2015, slides pdf, annotated slides pdf)
  12. Lecture Past (23.12.2015, slides pdf, annotated slides pdf
  13. Lecture The Internet (11.01.2016,  slides pdf
  14. Lecture Security (20.01.2016, slides pdf annotated slides part 1, part 2 part 3, part 4)
  15. Lecture Self-Organization (02.02.2016, slides pdf, annotated slides pdf)
  16. Lecture P2P in the Wild (08.02.2016, slides pdf, annotated slides pdf)


  1. 19.10.2015 Napster (avi, mp4)
  2. 21.10.2015 Gnutella (avi, mp4)
  3. 26.10.2015 - due to broken cable no recording (old recordings on CAN)
  4. 28.10.2015 CAN (avi, mp4)
  5. 02.11.2015 Chord (avi, mp4)
  6. 04.11.2015 Dhash++ (avi, mp4)
  7. 09.11.2015 Pastry (avimp4)
  8. 11.11.2015 Chernoff  (avimp4)
  9. 16.11.2015 Distance Halving  (avimp4)
  10. 18.11.2015 Koorde (avimp4)
  11. 23.11.2015 Kelips (avimp4)
  12. 25.11.2015 Push (avi, mp4)
  13. 30.11.2015 Push (avimp4)
  14. 02.12.2015 Simple Switching (avimp4)
  15. 07.12.2015 Pointer-Push&Pull, Flipper (avimp4)
  16. 09.12.2015 IP Multicast (avimp4)
  17. 14.12.2015 Bittorrent (avi, mp4)
  18. 16.12.2015 Network Coding (avi, mp4)
  19. 21.12.2015 Game Theory (avi, mp4)
  20. 23.12.2015 Past  (avimp4)
  21. 11.01.2016 The Internet (avimp4)
  22. 13.01.2016 Routing (avimp4)
  23. 18.01.2016 TCP (avimp4)
  24. 20.01.2016 Security  (avimp4)
  25. 25.01.2016 Cryptography (avi, mp4)
  26. 01.02.2016 Freenet & Byzantine Generals (avi, mp4)
  27. 03.02.2016 Self-Organization (avi, mp4)
  28. 08.02.2016 T-Chord  (avi, mp4)
  29. 10.02.2016 P2P in the Wild (avimp4)


  • 1st exercise: Pareto distributions (21.10.2015) pdf
  • 2nd exercise: CAN (28.10.2015) pdf
  • 3rd exercise: Chord and PNS (4.11.2015) pdf
  • 4th exercise: Chernoff (11.11.2015) pdf
  • 5th exercise: Pastry and Koorde (18.11.2015) pdf
  • 6th exercise: Distance-Halving (25.11.2015) pdf
  • 7th exercise: Rumor Spreading, Simple Switching and Push & Pull (02.12.2015) pdf
  • 8th exercise: 1-Flipper and Push & Pull (09.12.2015) pdf
  • 9th exercise: Network Coding (16.12.2015) pdf
  • 10th exercise: Basic Routing, TCP and UDP (23.12.2015) pdf
  • 11th exercise: Distance Vector Routing and TCP II (14.01.2016) pdf
  • 12th exercise: TCP Tahoe, Basic Security Terms, (D)DoS, AES/RSA (22.01.2016) pdf
  • 13th exercise: Secret Sharnig, cryptographic functions (29.01.2016) pdf
  • 14th exercise: Byzantine Generals, Freenet, Onion Routing (03.02.2016) pdf


  • Mahlmann, Schindelhauer: Peer-to-Peer-Netzwerke - Methoden und Algorithmen, Springer 2007
  • S. Ratnasamy, P. Francis, M. Handley, R. Karp, and S. Shenker. A scalable content-addressable network. In Computer Communication Review, volume 31, pages 161–172. Dept. of Elec. Eng. and Comp. Sci., University of California, Berkeley, 2001.
  • Ion Stoica, Robert Morris, David Karger, Frans Kaashoek, and Hari Balakrishnan. Chord: A scalable Peer-To-Peer lookup service for internet applications. In Roch Guerin, editor, Proceedings of the ACM SIGCOMM 2001 Con- ference (SIGCOMM-01), volume 31, 4 of Computer Communication Review, pages 149–160, New York, August 27–31 2001. ACM Press.
  • Antony Rowstron and Peter Druschel. Pastry: Scalable, decentralized object location, and routing for large-scale peer-to-peer systems. Lecture Notes in Com- puter Science, In Proc. of the International Conference on Distributed Systems Platforms (IFIP/ACM), 2218:329–350, 2001.
  • Druschel, Peter, and Antony Rowstron. "PAST: A large-scale, persistent peer-to-peer storage utility." Hot Topics in Operating Systems, 2001. Proceedings of the Eighth Workshop on. IEEE, 2001.
  • Kirsten Hildrum, John D. Kubiatowicz, Satish Rao, and Ben Y. Zhao. Distributed object location in a dynamic network. In SPAA ’02: Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, pages 41–52, New York, NY, USA, 2002. ACM Press.
  • Moni Naor and Udi Wieder. Novel architectures for p2p applications: the continuous-discrete approach. In SPAA ’03: Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, pages 50–59, New York, NY, USA, 2003. ACM Press.
  • M. Frans Kaashoek and David R. Karger. Koorde: A simple degree-optimal distributed hash table. In 2nd International Workshop on Peer-to-Peer Systems, Berkeley, California, 2003.
  • Nicholas J. A. Harvey, Michael B. Jones, Stefan Saroiu, Marvin Theimer and Alec Wolman, SkipNet: A Scalable Overlay Network with Practical Locality Properties, USENIX Symposium on Internet Technologies and Systems, 2003.
  • Peter Mahlmann, Christian Schindelhauer, Distributed Random Digraph Transformations for Peer-to-Peer Networks,18th ACM Symposium on Parallelism in Algorithms and Architectures, Cambridge, MA, USA. July 30 - August 2, 2006
  • Peter Mahlmann, Christian Schindelhauer,  Peer-to-Peer Networks based on Random Transformations of Connected Regular Undirected Graphs,  17th ACM Symposium on Parallelism in Algorithms and Architectures 2005,155-164 (SPAA 2005)
  • Awerbuch, Baruch, and Christian Scheideler. "Towards a scalable and robust DHT." Theory of Computing Systems 45.2 (2009): 234-260
  • Montresor, Alberto, Márk Jelasity, and Ozalp Babaoglu. "Chord on demand." Peer-to-Peer Computing, 2005. P2P 2005. Fifth IEEE International Conference on. IEEE, 2005.
  • Kurose, James F. Computer Networking: A Top-Down Approach Featuring the Internet, Pearson, 2005
  • Andrew S. Tannenbaum, Computer Networks, Prentice Hall, 2010


Personal tools