Topics in Data-Intensive Computing Systems

 

Instructor: Matei Ripeanu

Schedule: Tue/Thu, 4:30-6:00

Location: KAIS4018. 

 

Announcements:

[01/16] Register with the H2O system and join project EECE571R. To submit your paper review please go to the appropriate “Rotisserie Discussion”. Reviews for Tuesday class are due by midnight on Monday.

 

Syllabus

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:

1.      State the main contribution of the paper

2.      Critique the main contribution. 

a.       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.

b.      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?)

c.       What is the most important limitation of the approach?

3.      What are the three strongest and/or most interesting ideas in the paper?

4.      What are the three most striking weaknesses in the paper?

5.      Name three questions that you would like to ask the authors.

6.      Detail an interesting extension to the work not mentioned in the future work section.

7.      Optional comments on the paper that you’d like to see discussed in class.

Reviews must be submitted by midnight the day before the 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: (a) Prepare discussion plan, (b) Post the master critique on H2O based on in-class discussions (due before the following class).

·        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.

 

 

Course schedule

 

 

 

Topic

Extra papers

W1

01/09

Introduction to the class, goals, and structure [ppt].

 

01/11

Introduction (cont.) Performance enhancement techniques: replication, caching, striping, prefetching,   Data consistency. [ppt, ppt-1]

[1]     Constructing Collaborative Desktop Storage Caches for Large Scientific Datasets, S. Vazhkudai et al. ACM Transaction on Storage (TOS), 2006. [pdf]

[2]     FreeLoader project

W2

01/16

Distributed file systems. (Matei)

[1]     Scale and Performance in a Distributed File System, J. H. Howard et al., ACM Transactions on Computer Systems Feb. 1988, Vol. 6 (1). [pfd]

[2]     The Google File System, Ghemawat et al., SOSP 2003 [pdf]

NFS summary slides [ppt]

xFS Project: Serverless Network File Service

01/18

Data replication (Elizeu)

[1]     Efficient Replica Maintenance for Distributed Storage Systems, Byung-Gon Chun et al., NSDI’06. [pdf]

[2]   Drafting Behind Akamai (Travelocity-Based Detouring), Ao-Jan Su et al.. SIGCOMM’06. [pdf]

 

W3

01/23

Storage management (Discussion leader: Armin)

[1]     An end-to-end approach to globally scalable programmable networking, Beck et al., ACM SIGCOMM Workshop on Future Directions in Network Architecture, 2003. [pdf]

[2]     Storage Resource Managers: Middleware Components for Grid Storage, A. Shoshani, A. Sim, J. Gu, 19th IEEE Symposium on Mass Storage Systems, 2002 (MSS '02). [pdf] [slides]

[1]     Implementation Tradeoffs in Storage Allocation for Grid Computing, D. Thain, Technical Report [pdf].

[2]     An End-to-End Approach to Globally Scalable Network Storage, M. Beck et al., ACM SIGCOMM 2002 [pdf]

01/25

Semantics: (Discussion leader: Caleb)

[1]     Semantically-Smart Disk Systems, Muthian Sivathanu et al., FAST’03  [pdf]

[2]     Providing Tunable Consistency for a Parallel File Store, Murali Vilayannur, Partho Nath, and Anand Sivasubramaniam, FAST’05 [pdf]

 

W4

01/30

Papers on data stream analysis and data-mining (no links, emailed)

[1]     Medusa: Distributed stream processing [link]

[2]     Multi-site cooperative data stream analysis, ACM SIGOPS Operating Systems Review, 40(3), 31 – 37,  2006.  [pdf]

02/01

[1]     Project discussion. (Discussion leader: Elizeu)

[2]     Design and Evaluation of a Continuous Consistency Model for Replicated Services, Haifeng Yu and Amin Vahdat, OSDI’00 [pdf].

[1]     The TACT project: Tunable Availability and Consistency Tradeoffs

W5

02/06

Availability: (Discussion leader: Armin)

[1]     TotalRecall: System Support for Automated Availability Management, R. Bhagwan, K. Tati, Y. Cheng, et al., NSDI , 2004. [pdf]

[2]     Exploiting Availability Prediction in Distributed Systems, James W. Mickens, Brian D. Noble, NSDI 2006. [pdf]

 

02/08

Check-pointing for parallel applications (Discussion leader: Caleb)

[1]     Adaptive incremental checkpointing for massively parallel systems, Saurabh Agarwal, Rahul Garg, Meeta S. Gupta, Jose E. Moreira 18th International Conference on Supercomputing, Malo, France, 2004 [pdf]

[2]     Blocking vs. Non-Blocking Coordinated Checkpointing for Large-Scale Fault Tolerant MPI, Thomas Herault, Pierre Lemarinier, Franck Cappello, SC2006, Tampa, FL. [pdf]

 

W6

02/13

DHTs. Slides: [ppt]

DHT systems: Chord, Pastry, Tapestry, Bamboo, Kelips, Symphony, SkipNet

02/15

Midterm project discussion.

 

W7

02/27

DHTs (cont). Slides: [ppt][ [ppt]

OpenDHT: A Public DHT Service and Its Uses. Sean Rhea, Brighten Godfrey, Brad Karp, John Kubiatowicz, Sylvia Ratnasamy, Scott Shenker, Ion Stoica, and Harlan Yu. SIGCOMM 2005, August 2005. [ppt], [pdf])

A Case Study in Building Layered DHT Applications, Yatin Chawathe, Sriram Ramabhadran, Sylvia Ratnasamy, Anthony LaMarca, Scott Shenker, Joseph Hellerstein, SIGCOMM’05

03/01

Disk failures (Discussion leader: Samer)

[1]     Disk Failures in the Real World: What Does an MTTF of 1,000,000 Hours Mean to You?, Bianca Schroeder and Garth A. Gibson (FAST 07) [pdf]

[2]     Failure Trends in a Large Disk Drive Population, Eduardo Pinheiro, Wolf-Dietrich Weber, and Luiz André Barroso (FAST’07) [pdf]

 

W8

03/06

Performance Evaluation / Evaluating Distributed Systems:

[1]     Fallacies in Evaluating Decentralized Systems
Andreas Haeberlen, Alan Mislove, Ansley Post (Rice University / Max Planck Institute for Software Systems), Peter Druschel, IPTPS’06 [pdf]

[2]     Using PlanetLab for Network Research, Myths, Realities and Best Practices. [pdf].

[3]     Should computer scientists experiment more? W.F. Tichy, IEEE  Computer, May 1998 (32-40). [pdf]

The Many Faces of Systems Research - and How to Evaluate Them, Aaron B. Brown, Anupam Chanda, Rik Farrow, Alexandra Fedorova, Petros Maniatis, and Michael L. Scott, HotOS’05 [pdf]

03/08

No class.

 

W9

03/13

System characterization (I) (Discussion leader: Caleb)

[1]     Passive NFS Tracing of Email and Research Workloads, Daniel Ellard, Jonathan Ledlie, Pia Malkani, Margo Seltzer, FAST 2003. [pdf]

[2]     Feasibility of a Serverless Distributed File System Deployed on an Existing Set of Desktop PCs, William J. Bolosky, John R. Douceur, David Ely, and Marvin Theimer, SIGMETRICS 2000 [pdf]

[1]     An Empirical Study of a Highly Available File System, B. D. Noble and M. Satyanarayanan. ACM SIGMETRICS’94.

[2]     A Five-Year Study of File-System Metadata, Nitin Agrawal, William J. Bolosky, John R. Douceur, and Jacob R. Lorch, FAST’07. [pdf]

[3]     Farsite project

03/15

DHTs (cont) [ppt]

 

[1]     File System Benchmarking: Fallacies and Pitfalls, Nikolai Joukov, Avishay Traeger, Charles P. Wright, and Erez Zadok, Technical Report FSL-05-04b [pdf][ppt].

[1]     The Impact of DHT Routing Geometry on Resilience and Proximity, K.P. Gummadi, et al. SIGCOMM 2003, Karlsruhe, Germany, August 2003. [pdf]

[2]     Designing a DHT for Low Latency and High Throughput,  Frank Dabek et al. NSDI 2004. [pdf]

W10

03/20

System characterization (II) (Discussion leader: Elizeu)

[1]     Web Caching and Zipf-like Distributions: Evidence and Implications, Lee Breslau, Pei Cao, Li Fan, Graham Phillips, Scott Shenker, INFOCOM 1999: 126-134. [pdf]

[2]     Small-World File-Sharing Communities, Adriana Iamnitchi, Matei Ripeanu, Ian Foster, Infocom 2004, Hong Kong, March 2004. [ps

[4]     A Comparison of File System Workloads, Drew Roselli, Jacob R. Lorch, Thomas E. Anderson, USENIX’00 [pdf]

[5]     File system usage in Windows NT 4.0, Werner Voegels, SOSP’99 [pdf]

[6]     Filecules in High-Energy Physics: Characteristics and Impact on Resource Management, Adriana Iamnitchi, Shyamala Doraimani, Gabriele Garzoglio, HPDC 2006, Paris, June 2006. [pdf]

[7]     Interest-Aware Information Dissemination in Small-World Communities, Adriana Iamnitchi, Ian Foster, HPDC 2005, Raleigh, NC, July 2005 [pdf].

03/22

Network coding and data reliability. [pdf].

[1]     High Availability in DHTs: Erasure Coding vs. Replication, Rodrigo Rodrigues and Barbara Liskov, IPTPS'05, [PostScript | PDF] [PowerPoint Slides]

[2]     Erasure Coding vs. Replication: A Quantitative Comparison, Hakim Weatherspoon and John Kubiatowicz.  IPTPS 2002 [pdf]

[3]     Assessing the performance of Erasure Codes in the Wide Area, Rebecca L. Collins and James S. Plank, DSN-2005 [pdf]

W11

03/27

Network attached storage / Specialized IO (Discussion leader: Armin)

[1]     Network Attached Storage Architecture. Garth A. Gibson and Rodney Van Meter. Communications of the ACM, November 2000, Vol.43, No.11. [pdf]

[2]     Making the Most out of Direct Access Network-Attached Storage, Kostas Magoutis, Salimah Addetia, Alexandra Fedorova, Margo I. Seltzer, FAST'03, [pdf]

[3]     Structure and Performance of the Direct Access File System, Kostas Magoutis, Salimah Addetia, Alexandra Fedorova, Margo I. Seltzer, Jeffrey S. Chase, Andrew J. Gallatin, Richard Kisley, Rajiv G. Wickremesinghe, Eran Gabber, USENIX’02 [pdf]

[1]     Application Performance on the Direct Access File System, Alexandra Fedorova, Margo Seltzer, Kostas Magoutis, and Salimah Addetia, WOSP'04.

[2]     A Performance Comparison of NFS and iSCSI for IP-Networked Storage, Peter Radkov, Li Yin, Pawan Goyal and Prasenjit Sarkar, Prashant Shenoy, FAST’04 [pdf]

[3]     End-System Optimizations for High-Speed TCP, Jeff Chase, Andrew Gallatin, and Ken Yocum, IEEE Communications, 39 (4), 2001. [Postscript], [PDF]

03/29

Journaling, Log structured FS

[1]     File System Logging versus Clustering: A Performance Comparison. M. Seltzer, Smith, K., Balakrishnan, H., Chang, J., McMains, S., Padmanabhan, V., USENIX’95. [pdf]

[2]     Journaling Versus Soft Updates: Asynchronous Meta-data Protection in File Systems, Margo I. Seltzer, Gregory R. Granger, M. Kirk McKusick, Keith A. Smith, Craig A. N. Soules, Christopher A. Stein, USENIX’00 [pdf]

[3]     The Design and Implementation of a Log-Structured File System, Mendel Rosenblum and John K. Ousterhout, SOSP’91 [pdf]

[4]     Soft updates: a solution to the metadata update problem in file systems, Gregory R. Ganger,  Marshall Kirk McKusick,  Yale N. Patt, Craig A. N. Soules, ACM Transactions on Computer Systems (TOCS), 18(2), 2000 [pdf]

[5]     Whitepaper: Red Hat's New Journaling File System: ext3,  Michael K. Johnson [link]

W12

04/03

Security / Trust

[1]     Strong Accountability for Network Storage, Aydan R. Yumerefendi and Jeffrey S. Chase, FAST’07 [pdf]

[2]     Samsara: Honor Among Thieves in Peer-to-Peer Storage, Landon Cox, Brian Noble, SOSP’03, [pdf]

[3]     Data Staging on Untrusted Surrogates, Jason Flinn; Shafeeq Sinnamohideen, Niraj Tolia, and M. Satyanaryanan, FAST’03

[4]     Plutus: Scalable Secure File Sharing on Untrusted Storage, Mahesh Kallahalla, Erik Riedel,; Ram Swaminathan, Qian Wang, and Kevin Fu, FAST’03

[5]     Strong Security for Network-Attached Storage, Ethan Miller and Darrell Long, William Freeman, Benjamin Reed, FAST

04/05

Data archival / Backups:

[1]     A Cooperative Internet Backup Scheme, Mark Lillibridge, Sameh Elnikety, Andrew Birrell, Mike Burrows, and Michael Isard, USENIX’03 [pdf]

 

W13

04/16

Massive multiplayer online games

[1]     Applicability of Group Communication for Increased Scalability in MMOGs, Knut-Helge Vik et al. NetGames 2006 [pdf]

[2]     The Effects of Loss and Latency on User Performance in Unreal Tournament 2003, Tom Beigbeder, Rory Coughlan, Corey Lusher, John Plunkett, Emmanuel Agu, Mark Claypool, NetGames 2004 [pdf]

 

04/18

No class. Project presentations TBA during the exam period.

 

 

Other papers:

More systems

§    Pond: The OceanStore Prototype, Sean Rhea, Patrick Eaton, Dennis Geels, Hakim Weatherspoon, Ben Zhao, and John Kubiatowicz, FAST’03

§    GPFS: A Shared-Disk File System for Large Computing Clusters, Frank Schmuck and Roger Haskin, FAST’01

§    Flexibility, Manageability, and Performance in a Grid Storage Appliance, John Bent, Venkateshwaran Venkataramani, Nick LeRoy, Alain Roy, Joseph Stanley, Andrea C. Arpaci Dusseau, Remzi H. Arpaci-Dusseau, Miron Livny, HPDC

§    Metadata Efficiency in Versioning File Systems,  Craig A. N. Soules, Garth R. Goodson, John D. Strunk, and Gregory R. Ganger,

§    yFS: A Journaling File System Design for Handling Large Data Sets with Reduced Seeking, Zhihui Zhang and Kanad Ghose,

§    The Direct Access File System , Matt DeBergalis, Peter Corbett, Steve Kleiman, Arthur Lent, Dave Noveck, Tom Talpey, and Mark Wittle

§    Bayou

§    Ivy: A Read/Write Peer-to-peer File System. Athicha Muthitacharoen, Robert Morris, Thomer Gil, and Benjie Chen. 5th OSDI. Boston, MA. December 2002.

§    Venti, a new approach to archival storage, S. Quinlan and S. Dorward, FAST’02

§    Safety, Visibility, and Performance in a Wide-Area File System, Minkyong Kim, Landon P. Cox, and Brian D. Noble, http://www.sagecertification.org/events/fast02/full_papers/kim/kim.pdf

§    P. F. Corbett and D. G. Feitelson. The Vesta Parallel File System. In High Performance Mass Storage and Parallel I/O: Technologies and Applications. IEEE Computer Society Press and Wiley, 2001.

Trust / Security

§    Data Staging on Untrusted Surrogates, Jason Flinn; Shafeeq Sinnamohideen, Niraj Tolia, and M. Satyanaryanan, FAST’03

§    Plutus: Scalable Secure File Sharing on Untrusted Storage, Mahesh Kallahalla, Erik Riedel,; Ram Swaminathan, Qian Wang, and Kevin Fu, FAST’03

§    Strong Security for Network-Attached Storage, Ethan Miller and Darrell Long, William Freeman, Benjamin Reed, FAST

Miscellaneous

§    D. Anderson, J. Chase, and A. Vahdat. Interposed Request Routing for Scalable Network Storage. Transactions on Computer Systems (TOCS), 20(1), February 2002.

§    A. C. Arpaci-Dusseau and R. H. Arpaci-Dusseau. Information and Control in Gray-Box Systems. In Proceedings of the 18th ACM Symposium on Operating Systems Principles (SOSP ’01), pages 43–56, Banff, Canada, October 2001.

§    Beyond Bloom Filters: From Approximate Membership Checks to Approximate State Machines, F. Bonomi, M. Mitzenmacher, R. Panigraphy, S. Singh, G. Varghese, SIGCOMM’06