Peer-to-Peer-Networks

Lecture of Prof. Christian Schindelhauer

News

• 05.10.2012 Webpage online
• 31.10.2012 First exercise
• 21.01.2013 Teaching Evaluation online

Contents

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
• Tapestry
• Minimal networks: Viceroy, Distance-Halving
• Skip-Graph, Skipnet
• Self-organization
• Kelips, epidemic algorithms
• Anynomity
• Security

• Download
• P2P in the wild
• P2P and the Law

Organisation

Schedule

• Lecture
  • Monday, 10:15 - 12:00, room 106-00-007
  • Wednesday, 10:15 - 12:00, room 106-00-007
• Exercises
  • Wednesday, 10:15 - 12:00, room 106-00-007 

Forum

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! 

Material

Slides

• 1. Lecture Introduction and Motivation (22.10.2012, version 23.10.2012) pdf
• 2. Lecture Napster and Gnutella (22.10.2012, version 23.10.2012) pdf
• 3. Lecture Content Addressable Networks (24.10.2012, version 23.10.2012) pdf
• 4. Lecture DHT and Chord (29.10.2012/05.11.2012, version 04.11.2012) pdf
• 5. Lecture Pastry (05.11.2012, version 04.11.2012) pdf
• 6. Lecture Tapestry (07.11.2012, version 06.11.2012) pdf
• 7. Lecture Minimal Degree Networks (12.,19,21.11.2012, version 18.11.2012) pdf
• 8. Lecture Skipnet & Skipgraphs (21.11.2012) pdf
• 9. Lecture Self-Organisation (26.11.2012, version 25.11.2012) pdf
• 10. Lecture Random Graphs (03.12.2012, version 04.12.2012) pdf
• 11. Lecture Kelips and Epidemic Algorithms (05./10./17.12.2012 version 04.12.2012) pdf
• 12. Lecture Anonymity (19.12.2012, version 17.12.2012)  pdf
• 13. Lecture Security (06.01.2013, version 06.01.2013)  pdf
• 14. Lecture Network Coding and Fast Download (13.01.2013, version 11.01.2013)  pdf
• 15. Lecture Game Theory (28.01.2013, version 28.01.2013)  pdf
• 15. Lecture Hole Punching (30.01.2013, version 30.01.2013)  pdf

Recordings

• 01 Intro 22.10.2012 mp4
• 02 Napster Gnutella 22.10.2012 mp4
• 03 CAN part 1 24.10.2012 mp4
• 03 CAN part 2 24.10.2012 mp4
• 04 CAN part 3 - Chord part 1 - 29.10.2012 mp4
• 05 CAN Chord part 2 - 29.10.2012 mp4
• 06 Chord part 3 - 05.11.2012 mp4
• 07 Pastry part 1 - 05.11.2012 mp4
• 08 Pastry part 2 - 07.11.2012 mp4
• 09 Tapestry - 07.11.2012 mp4
• 10 Viceroy - 12.11.2012  mp4
• 11 Distance Halving - 12.11.2012 mp4
• 12 Multiple Choice, Chernoff Bounds, 19.11.2012 mp4
• 13 Koorde, 19.11.2012 mp4
• 14 Skiplists, 21.11.2012  mp4
• 15 Skipnet, 21.11.2012 mp4
• 16 Pareto-Distribution, 26.11.2012 mp4
• 17 Self-Organization, 26.11.2012 mp4
• 18 Random networks 03.12.2012 mp4
• 19 Push & Pull 05.12.2012 mp4
• 20 Flipper 05.12.2012 mp4
• 21 Kelips 10.12.2012 mp4
• 22 Epidemics 10.12.2012 mp4
• 23 Epidemics Push Communication 12.12.2012 (new 15.01.2013)  mp4
• 24 Epidemics Pull Communication 12.12.2012 (new 15.01.2013) mp4
• 25 Anonymity 19.12.2012 (new name15.01.2013) avi
• 26 Security 07.01.2013 (new name 15.01.2013) mp4
• 27 Security: Sibil Attack 19.12.2012 (new name) mp4
• 28 Byzantine Generals 14.01.2013 mp4
• 29 Cockoo Chord 14.01.2013 mp4
• 30 IP-Multicast 16.01.2013 mp4
• 31 Scribe 16.01.2013 mp4
• 32 BitTorrent, Finite Fields 21.01.2013 avi
• 33 Paircoding 28.01.2013 mp4
• 34 Game Theory 28.01.2013 mp4
• 35 Nash equilibrium 30.01.2013 mp4
• 36 Incentives BitTorent 30.01.2013 mp4
• 37 Reciprocity 04.02.2013 mp4
• 38 NAT 04.02.2013 mp4
• 39 UDP Holepunching 11.02.2013 mp4
• 40 TCP Holepunching 11.02.2013 mp4
• 41 TCP NATBlaster 13.02.2013 mp4

Exercises

• 1. Excercise (24.10.2012) pdf
• 2. Excercise (07.11.2012) pdf
• 3. Excercise (21.11.2012) pdf
• 4. Excercise (06.12.2012) pdf
• 5. Excercise (09.01.2013) pdf
• 6. Excercise (23.01.2013) pdf
• 7. Excercise (06.02.2013) pdf

Literature

• 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.
• 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.
• Dahlia Malkhi, Moni Naor, and David Ratajczak. Viceroy: a scalable and dynamic emulation of the butterfly. In PODC ’02: Proceedings of the twenty-first annual symposium on Principles of distributed computing, pages 183–192, 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.
• Harvey and Munro, Deterministic SkipNet, IPL: Information Processing Letters, Vol. 90, 2004.
• James Aspnes and Gauri Shah. Skip graphs. ACM Transactions on Algorithms, 3(4):37, November 2007. An earlier version appeared in Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 2003, pp. 384–393.