22C:196:003 Peer-to-peer and Social Networks
Spring 2013

Instructor

Sukumar Ghosh, 201P Maclean Hall, 319-335-0738, sukumar-ghosh@uiowa.edu
Class meeting time: 2:00P-3:15P TTh 22SH (3 sh)
Office hours: 10:30AM-12:00PM TTh

TA

Zeng Dai, zeng-dai@uiowa.edu
Office hours: Mondays 1:00-2:30 PM in 317 MLH Thursdays: 6:00-7:00PM in 301 MLH

Textbook

There is no required textbook. Good reference books in social networks are
[1] Albert-Laszlo Barabasi: Linked: How Everything Is Connected to Everything Else and What It Means. Perseus publishing (2002)
[2] David Easley, Jon Kleinberg. Networks, Crowds, and Markets: Reasoning About a Highly Connected World. Cambridge University Press, 2010 [The pre-publication draft is available for free download]
For peer-to-peer networks, we will use this list of papers .

Course Outline

Attempts to understand how social networks evolve and to quantify their characteristics started some fifty years ago. Since then, much work has been done to measure, classify and derive important properties of these networks. Comparatively, Peer-to-Peer (P2P) systems are a more recent development in Internet information systems. The major focus is to see how a meaningful distributed system can be built by the millions of machines at the edges of the Internet without the help of a distinguished node like a central server. Important applications include file sharing, searching, storage, streaming, multicast, publish-subscribe etc. Topics will include:
Introduction to Social and P2P networks
Random graphs, power-law graphs, small-world graphs and various metrics
First generation P2P networks: Napster, Gnutella
Unstructured vs. DHT-based structured networks
KaZaA, Chord, CAN, Pastry, BitTorrent, Kademlia, Skip graph
Self-organization, routing, replication, storage, security, selfishness, etc

Tests and assignments

Two quizzes (20%), two assignments (20%), a project (50%) and one class presentation (10%); There is no final examination. Project topics will be posted during the first week of classes.

Quiz 1: February 21, 2013 (in class: duration 30 mins)
Quiz 2: April 18, 2013 (in class: duration 30 mins)

Final Project Presentation Schedule

Tentative presentation schedule

List of papers for presentation by students

Assignments

Homework 1 (Assigned 2/7 due 2/14)
Homework 2 (Assigned 3/28 due 4/9)

Lecture Notes

January 22, 2013
Lecture 1. Introduction to Social and P2P Networks
January 24, 2013
Lecture 2. Random vs Power-law Graphs
January 29, 2013
Lecture 3. Power-law & small-world graphs
January 31, 2013
Lecture 4. Centrality Measures & Community Detection (.pptx) (.pdf)
February 5, 2013
Lecture 5. Revisiting small-world graph
February 7, 2013
Lecture 6. Gnutella P2P network
February 12, 2013
Lecture 7. Gia: Scalable Gnutella
February 14, 2013
Lecture 8. Plaxton routing
February 19, 2013
Lecture 9. Chord P2P Network (.ppt) (.pdf)
February 21, 2013
Lecture 10. Chord: Advanced Issues (.ppt) (.pdf)
February 26, 2013
Lecture 11. Skip list and Skip graph (.ppt) (.pdf)
February 28, 2013
Lecture 12. Skip graph (continued)
March 05, 2013
Lecture 13. Measurement, Modeling, and Analysis of a Peer-to-Peer File-Sharing Workload (.ppt) (.pdf)
March 12, 2013
Lecture 14. Replication Strategies in Unstructured Peer-to-Peer Networks (.pdf)
March 26, 2013
Lecture 15. Replication Strategies in Unstructured Peer-to-Peer Networks (.pdf) (continued)
April 02, 2013
Lecture 16. Pastry (.pdf)
April 09, 2013
Lecture 17. Oceanstore
April 18, 2013
Lecture 18. Bittorrent
April 25, 2013
Lecture 19. Kademlia