CIS 6930.008: Internet-Scale Networked Systems

Theme: Exploiting Emergent Patterns in Large-Scale Distributed Systems

Spring 2008

Professor: Adriana Iamnitchi (Anda)
Semester: Spring 2008
Time and Venue: Tu-Th: 12:30pm-1:45pm in SOC 384
Office Hours: Wednesdays 2-4pm and by appointment
Office: ENB 334

announcements

Announcements

top

Syllabus

The focus of this class will be the study of large-scale distributed systems, which are collections of Internet-connected autonomous computing nodes spread across administrative domains. Participation in these federated systems allows access to potentially unique or large sets of resources such as data, storage space, computing power, or services. Examples of federated systems include computational grids, peer-to-peer networks, and wide-area testbeds such as PlanetLab.

This course is a tour through various research topics in federated distributed systems. We will explore solutions and learn design principles for building large network-based computational systems. Our readings and discussions will help us identify research problems and understand methods and general approaches to design, implement and evaluate distributed systems. Topics include resource management (discovery, allocation), data management (replication, location), security, fault-tolerance, system characterization, and overlay construction. Our discussions will often be grounded in the context of deployed distributed systems such as Grids and peer-to-peer networks.

The course involves discussions of four papers a week and a final project.

Grading is based on paper reviews and contributions to the class discussions (45%) and the final project (55%).

Reading materials: Most of the papers are available on the Internet. There is no required textbook for this class.

Prerequisites: This is a graduate-level class. Undergraduate students are welcome with instructor's consent (email to anda at cse dot usf dot edu).

top

Course format

The course is structured to provide (a) an in-depth understanding of current topics in large-scale, distributed system research; (b) experience with reviewing and presenting advanced technical material; (c) exercising writing papers. The class workload has a participation component and a final project.

Participation

In each class we discuss two research papers. Read the papers before class (be an efficient reader!) and write a review for each paper that includes the following:

State the main contribution of the paper
Critique the main contribution.

Rate the significance of the paper on a scale of 5 (breakthrough), 4 (significant contribution), 3 (modest contribution), 2 (incremental contribution), 1 (no contribution or negative contribution). Explain your rating in a sentence or two.
Rate how convincing the methodology is. You may consider some of the following questions (use what is relevant): do the claims and conclusions follow from the experiments? Are the assumptions realistic? Are the experiments well designed? Are there different experiments that would be more convincing? Are there other alternatives the authors should have considered? (And, of course, is the paper free of methodological errors?)
What is the most important limitation of the approach?

What are the three strongest and/or most interesting ideas in the paper?
What are the three most striking weaknesses in the paper?
Name three questions that you would like to ask the authors.
Detail an interesting extension to the work not mentioned in the future work section.
Optional comments on the paper that you’d like to see discussed in class.

Reviews must be submitted by noon before class to the relevant Rotisserie Discussion on H2O. Papers are discussed in class. Discussions will be lead by one or more students and may include a brief (5-minute) presentation of the paper. Discussion leaders do not need to submit reviews, but they need to:

Prepare discussion plan and email it to instructor (by 11am before class).
Take notes of the conclusions of the in-class discussions.
Post the master critique on H2O based on in-class discussions (due before the following class).

top

Final Project

The final project is an opportunity for hands-on research in distributed systems. It involves literature survey, programming, running experiments or analytical modeling, analyzing results and writing a 10-page report. A list of project ideas is posted, but students are highly encouraged to propose topics of their own interest. Teams of two students are highly recommended. Please see me if you want to form a 3-student team.

Milestones (tentative dates):

01/30: Email instructor a one-page statement of your project, noting the problem, proposed approach, and relevant reading. (Stop by ahead of time to discuss your project plans). Use John Wilkes' outline of a project document to craft your own. Use either the ACM or IEEE formatting guidelines for all deliverables related to the class project.
01/31: In-class presentation and discussion of project plans.
02/26: Email instructor a 3-page project write-up that includes: Problem Statement, Related Work and Motivation.
03/31: Email instructor a 5-page summary of the problem you are tackling, the proposed approach, preliminary results, and expected structure of the final paper (which should be about 10 pages).
04/01: In-class midterm project presentations.
04/24: In-class presentation of final projects.
05/01: Final projects due.

top

Schedule

DATE	TOPICS AND ARTICLES	RELATED POINTERS	DISCUSSION LEADERS
01/08	Introduction to the class, goals, and structure. [ppt]
01/10	System Models (lecture) Emergent (mis)behavior vs. Comples Systems Software, Jeffrey C. Mogul, EuroSys 2006	Earth Simulator Overview of the Blue Gene/L System Architecture
01/15	Inter-system communication: Ethernet, TCP/IP, Bluetooth, WiFi (lecture)
01/17	Time and Global State (lecture) Impossibility of Distributed Consensus with One Faulty Process, Ficher, Lynch, Paterson, 1984 Time, clocks and the ordering of events in a distributed system, Leslie Lamport, 1978 (Also, refer to this page for overview and interesting historical background: PODC Influential Paper Award 2000)
01/22	Peer-to-Peer Systems: a Historical Overview (lecture)
01/24	Real systems (1): Google The Google File System, Ghemawat et al. [pdf]		Sumit.
01/29	Real Systems (2): Amazon Web Services Dynamo paper		David
01/31	In-class discussion of project proposals. No reviews required. Good reading: You and Your Research, R. W. Hamming [pdf] [html] Technology and Courage, I. Sutherland [pdf]
02/05	Evaluating Decentralized Systems: Fallacies in Evaluating Decentralized Systems Andreas Haeberlen, Alan Mislove, Ansley Post (Rice University / Max Planck Institute for Software Systems), Peter Druschel (Max Planck Institute for Software Systems). Talk slides: PPT Using PlanetLab for Network Research
02/07	Social Interactions in Computer Systems (1) Exploiting Social Interactions in Mobile Systems
02/12	Social Interactions in Computer Systems (2) Geographic place and community information preferences Reality mining: sensing complex social systems Different Aspects of Social Network Analysis
02/14	Social Interactions in Computer Systems (3) Group formation in large social networks: membership, growth, and evolution Facilitating Social Networking in Inner-City Neighborhoods A trust based approach for protecting user data in social networks
02/19	Back to the theme (and leftovers): A Preliminary Investigation of Worm Infections in a Bluetooth Environment Exploiting Emergent Behavior for Inter-Vehicular Communication
02/21	Distributed Storage (new theme) Using Utility to Provision Storage Systems, John D. Strunk, Eno Thereska, Christos Faloutsos, Gregory R. Ganger, FAST 2008
02/26	Literature surveys due. No class (IPTPS workshop in St Petersburg)
02/28	Distributed Storage (2) Pergamum: Replacing Tape with Energy Efficient, Reliable, Disk-Based Archival Storage
03/04	Distributed Storage (3) TierStore: A Distributed Filesystem for Challenged Networks in Developing Regions
03/06	A Complexity Metric for Networked System Designs. Byung-Gon Chun, Sylvia Ratnasamy, and Eddie Kohler, NSDI 2008
Spring break
03/18	DieCast: Testing Distributed Systems with an Accurate Scale Model. Diwaker Gupta, Kashi Vishwanath, and Amin Vahdat, NSDI 2008
03/20	Brainstorming on project proposal.
03/25	(no class)
03/27	MapReduce
04/01	Midterm project status report: in class 10-minute presentation and discussions. Midterm project reports due [12pt font, 5 pages].
04/03	Friendstore
04/08	Talk Nicolas on data replication in sparse mobile networks
04/10	BotNets: A Multifaceted Approach to Understanding the Botnet Phenomenon The Anatomy of Clickbot.A
04/15	On Next-Generation Telco-Managed P2P TV Architectures, Meeyoung Cha (KAIST), Pablo Rodriguez (Telefonica Research, Barcelona), Sue Moon (KAIST), and Jon Crowcroft (University of Cambridge) Offloading Servers with Collaborative Video on Demand, Paweł Garbacki, Dick H. J. Epema, Johan Pouwelse (TU Delft), and Maarten van Steen (VU Amsterdam)
04/17	Wrap-up and review material
04/22	Final project presentations (1)
04/24	Final project presentations (2)
05/01	Final project reports due.

Paper Candidates: these papers are considered for the final schedule

SybilGuard: Defending against Sybil Attacks via Social Networks
DDoS Defense by Offense
Understanding the Network-level Behavior of Spammers
Distributed Quota Enforcement for Spam Control Michael Walfish, J.D. Zamfirescu, Hari Balakrishnan, and David Karger, Scott Shenker
Shark: Scaling File Servers via Cooperative Caching
Siddhartha Annapureddy, Michael J. Freedman, and David Mazières
To appear in 2nd USENIX/ACM Symposium on Networked Systems Design and Implementation
(NSDI '05) Boston, MA, May 2005.
[ ps ] [ ps.gz ] [ pdf ] Slides: [ pdf ]
Minimizing Churn in Distributed Systems
Beyond Bloom Filters: From Approximate Membership Checks to Approximate State Machines
Tycoon: an Implementation of a Distributed, Market-based Resource Allocation System
RE: Reliable Email, Scott Garriss, Carnegie Mellon University; Michael Kaminsky, Intel Research Pittsburgh; Michael J. Freedman, New York University and Stanford University; Brad Karp, University College London; David Mazières, Stanford University; Haifeng Yu, Intel Research Pittsburgh and Carnegie Mellon University
PRESTO: Feedback-driven Data Management in Sensor Networks, Ming Li, Deepak Ganesan, and Prashant Shenoy, University of Massachusetts, Amherst
Practical Data-Centric Storage, Cheng Tien Ee, University of California, Berkeley; Sylvia Ratnasamy, Intel Research Berkeley; Scott Shenker, ICSI and University of California, Berkeley
Virtualization Aware File Systems: Getting Beyond the Limitations of Virtual Disks, Ben Pfaff, Tal Garfinkel, and Mendel Rosenblum, Stanford University
Olive: Distributed Point-in-Time Branching Storage for Real Systems, Marcos K. Aguilera, Susan Spence, and Alistair Veitch, Hewlett-Packard Laboratories, Palo Alto
OverCite: A Distributed, Cooperative CiteSeer, Jeremy Stribling, MIT Computer Science and Artificial Intelligence Laboratory; Jinyang Li, New York University and MIT Computer Science and Artificial Intelligence Laboratory via University of California, Berkeley; Isaac G. Councill, Pennsylvania State University; M. Frans Kaashoek and Robert Morris, MIT Computer Science and Artificial Intelligence Laboratory
Colyseus: A Distributed Architecture for Online Multiplayer Games, Ashwin Bharambe, Jeffrey Pang, and Srinivasan Seshan, Carnegie Mellon University
Pip: Detecting the Unexpected in Distributed Systems, Patrick Reynolds, Duke University; Charles Killian, University of California, San Diego; Janet L. Wiener, Jeffrey C. Mogul, and Mehul A. Shah, Hewlett-Packard Laboratories, Palo Alto; Amin Vahdat, University of California, San Diego
Exploiting Availability Prediction in Distributed Systems, James W. Mickens and Brian D. Noble, University of Michigan
Efficient Replica Maintenance for Distributed Storage Systems , Byung-Gon Chun, University of California, Berkeley; Frank Dabek, MIT Computer Science and Artificial Intelligence Laboratory; Andreas Haeberlen, Rice University/MPI-SWS; Emil Sit, MIT Computer Science and Artificial Intelligence Laboratory; Hakim Weatherspoon, University of California, Berkeley; M. Frans Kaashoek, MIT Computer Science and Artificial Intelligence Laboratory; John Kubiatowicz, University of California, Berkeley; Robert Morris, MIT Computer Science and Artificial Intelligence Laboratory
Understanding Pollution Dynamics in P2P File Sharing.
Uichin Lee (UCLA), Min Choi (KAIST), Junghoo Cho, M. Y. Sanadidi, Mario Gerla (UCLA).
Proactive replication for data durability.
Emil Sit (MIT), Andreas Haeberlen (Rice / MPI-SWS), Frank Dabek (MIT), Byung-Gon Chun, Hakim Weatherspoon (UC Berkeley), Robert Morris, M. Frans Kaashoek (MIT), John Kubiatowicz (UC Berkeley).
F2F: Reliable Storage in Open Networks.
Jinyang Li, Frank Dabek (MIT).
On Object Maintenance in Peer-to-Peer Systems.
Kiran Tati, Geoffrey M. Voelker (UCSD).
Talk slides: PPT
Tribler: A Social-Based Peer-to-Peer System.
J. Pouwelse, P. Garbacki, J. Wang (Delft University of Technology), A. Bakker (Vrije Universiteit), J.Yang, A.Iosup, D.Epema, M.Reinders (Delft University of Technology), M. van Steen (Vrije Universiteit), H.Sips (Delft University of Technology).
Fair File Swarming with FOX.
Dave Levin, Rob Sherwood, Bobby Bhattacharjee (University of Maryland, College Park).
Group Therapy for Systems: Using link attestations to manage failures
Michael J. Freedman (NYU), Ion Stoica (UC Berkeley), David Mazieres (Stanford), Scott Shenker (ICSI/UC Berkeley).

top

Projects

Some ideas will be suggested in class. You're strongly encouraged to propose your own project ideas. Be innovative and aim high!

Preliminary ideas:

Use Google's Android platform to write a new application for mobile computing.
Develop the infrastructure for supporting a scientific application on Amazon Web services.
...

Adriana Iamnitchi (anda at cse usf edu)