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.
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.
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).
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] |
|
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, |
|
|
W6 |
02/13 |
DHTs.
Slides: [ppt] |
DHT
systems: Chord, Pastry, Tapestry,
Bamboo, Kelips, Symphony, SkipNet |
02/15 |
Midterm
project discussion. |
|
|
W7 |
02/27 |
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 [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
§
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.
§
Venti,
a new approach to archival storage,
§
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,
§
Beyond
Bloom Filters: From Approximate Membership Checks to Approximate State Machines,
F. Bonomi, M. Mitzenmacher, R. Panigraphy, S. Singh, G. Varghese, SIGCOMM’06