• View
• Edit
• History
• Print

ReadingList

Note

Many of these files are under copyright so they cannot be distributed to the whole internet. As a result, access is limited to hosts on the wisc.edu network. If you want to access these files from another network, such as from home, you have two options:

1. Use google to search for an accessible copy of the file
2. Use WiscVPN to connect to the campus network.

Introduction

• Introduction to Distributed System Design - Google Code University
• Experience with Grapevine: The growth of a distributed system Michael D. Schroeder, Andrew Birrell, Roger M. Neednam. ACM Transactions on Computer Systems, Feb 1984.
  • Background: Grapevine: An Exercise in Distributed Computing 
Andrew D. Birrell, Roy Levin, Roger M. Needham, Michael D. Schroeder, 
Communications of the ACM, 25 4, April 1982, pp. 260-274.

Scaling

• Load balancing
  • Locality-Aware Request Distribution, Vivek Pai, Guarav Banga, ASPLOS-VIII
  • Karger, D.; Sherman, A.; Berkheimer, A.; Bogstad, B.; Dhanidina, R.; Iwamoto, K.; Kim, B.; Matkins, L.; Yerushalmi, Y. (1999). "Web caching with consistent hashing". Computer Networks 31 (11): 1203–1213.
  • Background: Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web. David Karger, Eric Lehman, Tom Teighton, Matthew Levine, Daniel Lewin, Rina Panigrahy. STOC 1997.
  • Background: Algorithms in the Real World: Consistent Hashing. Bruce Maggs
• Partitioning
  • Dynamo: Amazon's Highly Available Key-Value. Store 
Giuseppe DeCandia, Deniz Hastorun, Madan Jampani, Gunavardhan Kakulapati, Avinash Lakshman, Alex Pilchin, Swami Sivasubramanian, Peter Vosshall and Werner Vogels 
Proceedings of the 21st ACM Symposium on Operating Systems Principles, Stevenson, WA, October 2007
  • Lessons from Giant-Scale Services. Eric A. Brewer. IEEE Internet Computing. Vol. 5, No. 4. pp. 46-55. July/August 2001.
• Replication
  • Demers et al., Epidemic algorithms for replicated database maintenance, PODC 1987.
    • If that version is hard to read, try this one.
  • Karin Petersen, Mike J. Spreitzer, Douglas B. Terry, Marvin M. Theimer and Alan J. Demers. Flexible update propagation for weakly consistent replication. Proceedings of the sixteenth ACM symposium on Operating systems principles, 1997.
  • Background: David K. Gifford, Weighted voting for replicated data. Proceedings of the seventh ACM symposium on Operating systems principles, 1979
  • Background Optimistic Replication. Yasushi Saito and Marc Shapiro. Computing Surveys, Vol. V, No. N, 3 2005, Pages 1–44.
  • Data replication in Mariposa. Sidell, J.; Aoki, P.M.; Sah, A.; Staelin, C.; Stonebraker, M.; Yu, A.; Proceedings of the Twelfth International Conference on Data Engineering, 1996.
  • Chain Replication for Supporting High Throughput and Availability Robbert van Renesse and Fred B. Schneider. OSDI 2004.
  • Brewer's CAP Theorem
• Ordering
  • L. Lamport, Time, Clocks, and the Ordering of Events in a Distributed System, Communications of the ACM, July 1978, pages 558-564.
  • M. Chandy and L. Lamport. Distributed snapshots: determining global states of distributed systems. ACM Trans. Comput. Syst., 3(1):63-75, 1985.
  • Causally and totally ordered communication
    • Kenneth P. Birman and Thomas A. Joseph. Reliable communication in the presence of failures. ACM Transactions on Computer Systems (TOCS), Volume 5 Issue 1, Feb. 1987.
    • Background: Understanding the limitations of causally and totally ordered communication. David Cheriton and Dale Skeen. SOSP 1993.
    • Background: A response to Cheriton and Skeen's criticism of causal and totally ordered communication. Ken Birman, Operating Systems Review, 1994.
• Byzantine Failures
  • L. Lamport, R. Shostak, and M. Pease, The Byzantine Generals Problem, ACM Transactions on Programming Languages and Systems, July 1982, pages 382-401.
  • Alternate: Practical Byzantine Fault Tolerance;Miguel Castro and Barbara Liskov,OSDI'99
  • Yoram Moses, Danny Dolev, Joseph Y. Halpern. Cheating husbands and other stories (preliminary version): a case study of knowledge, action, and communication, Proceedings of the fourth annual ACM symposium on Principles of distributed computing, 1985
• Consistency and Paxos
  • The Part-Time Parliament. Leslie Lamport; ACM Transactions on Computer Systems, Vol. 16, No. 2, May 1998
  • Leslie Lamport. Paxos Made Simple. ACM SIGACT News (Distributed Computing Column) 32, 4 (Whole Number 121, December 2001) 51-58.
  • Tushar Chandra, Robert Griesemer, and Joshua Redstone. Paxos Made Live – An Engineering Perspective. PODC '07: 26th ACM Symposium on Principles of Distributed Computing, 2007.
  • The Chubby Lock Service for Loosely-Coupled Distributed Systems. Mike Burrows. OSDI 2006.
• Cloud security
  • Hey, You, Get Off of My Cloud: Exploring Information Leakage in Third-Party Compute Clouds Thomas Ristenpart, Eran Tromer, Hovav Shacham, and Stefan Savage, Proceedings of Computer and Communications Security -- CCS '09
  • Michael Armbrust, Armando Fox, Rean Griffith, Anthony D. Joseph, Randy H. Katz, Andrew Konwinski, Gunho Lee, David A. Patterson, Ariel Rabkin, Ion Stoica and Matei Zaharia. Above the Clouds: A Berkeley View of Cloud Computing. EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2009-28
February 10, 2009
  • Computer security in the Real world. Butler Lampson. Proc. Annual Computer Security Applications Conference, 2000.
• Decentralized systems
  • I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H. Balakrishnan. Chord: A scalable peer-to-peer lookup service for internet applications. In SIGCOMM '01: Proceedings of the 2001 on Applications, technologies, architectures, and protocols for computer communications, 2001. ACM.
  • C. Amza, A.L. Cox, S. Dwarkadas, P. Keleher, H. Lu, R. Rajamony, W. Yu, and W. Zwaenepoel, TreadMarks: Shared Memory Computing on Networks of Workstations IEEE Computer, Vol. 29, No. 2, pp. 18-28, February 1996.
• Distributed Storage
  • E. K. Lee and C. A. Thekkath. Petal: Distributed virtual disks. In Proc. 7th Int. Conf. Architectural Support for Programming Languages and Operating Systems (ASPLOS) , pages 84--92, October 1996.
  • Background: Chandramohan Thekkath, Timothy Mann, and Edward Lee. Frangipani: A Scalable Distributed File System. Proc. of the 16th ACM Symposium on Operating Systems Principles, October 1997, pages 224-237.
  • J. J. Kistler and M. Satyanarayanan, Disconnected Operation in the Coda File System, Proceedings of the Thirteenth ACM Symposium on Operating Systems Principles, October 13-16, 1991, pages 213-225.
  • Background: Coda: A Highly Available File System for a Distributed Workstation Environment Satyanarayanan, M.; Kistler, J.J.; Kumar, P.; Okasaki, M.E.; Siegel, E.H.; Steere, D.C.; IEEE Transactions on Computers, Apr 1990, Volume: 39 Issue:4, page(s): 447 - 459.
  • FARSITE: Federated, available, and reliable storage for an incompletely trusted environment Atul Adya, William J. Bolosky, Miguel Castro, Gerald Cermak, Ronnie Chaiken, John R. Douceur, Jon Howell, Jacob R. Lorch, Marvin Theimer, and Roger P. Wattenhofer. Proceedings of the 5th Symposium on Operating Systems Design and Implementation (OSDI), 2002.
  • The Google File System 
Sanjay Ghemawat, Howard Gobioff, Shun-Tak Leung 
SOSP'03
  • background: GFS: Evolution on Fast-Forward. Kirk McKusick, Sean Quinlan, Communications of the ACM, Vol. 53 No. 3, Pages 42-49.
• Cloud computing
  • Michael Armbrust, Armando Fox, Rean Griffith, Anthony D. Joseph, Randy H. Katz, Andrew Konwinski, Gunho Lee, David A. Patterson, Ariel Rabkin, Ion Stoica and Matei Zaharia. Above the Clouds: A Berkeley View of Cloud Computing. EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2009-28
February 10, 2009
  • Luiz André Barroso and Urs Hölzle. The Datacenter as a Computer: An Introduction to the Design of Warehouse-Scale Machines. Synthesis Lectures on Computer Architecture, Morgan & Claypool Publishers, 2009. Read chapters 1 and 2.
• Cloud-scale programming
  • MapReduce: Simplified Data Processing on Large Clusters. 
Jeffrey Dean and Sanjay Ghemawat, 
OSDI'04
  • Orleans: Cloud Computing for Everyone, Sergey Bykov, Alan Geller, Gabriel Kliot, James Larus, Ravi Pandya, and Jorgen Thelin. In: ACM Symposium on Cloud Computing (SOCC 2011)
• Cloud Storage
  • Bigtable: A Distributed Storage System for Structured Data. Fay Chang, Jeffrey Dean, Sanjay Ghemawat, Wilson C. Hsieh, Deborah A. Wallach, Mike Burrows, Tushar Chandra, Andrew Fikes, and Robert E. Gruber. OSDI'06: Seventh Symposium on Operating System Design and Implementation, Seattle, WA, November, 2006.
  • FAWN: A Fast Array of Wimpy Nodes David G. Andersen and Jason Franklin and Michael Kaminsky and Amar Phanishayee and Lawrence Tan and Vijay Vasudevan. In Proc. 22nd ACM Symposium on Operating Systems Principles (SOSP) , Oct 2009
  • Fast Crash Recovery in RAMCloud, Diego Ongaro, Stephen M. Rumble, Ryan Stutsman, John Ousterhout, and Mendel Rosenblum, SOSP 2011
  • Onix: A Distributed Control Platform for Large-scale Production Networks, Koponen, M. Casado, N. Gude, J. Stribling, L. Poutievski, M. Zhu, R. Ramanathan, Y. Iwata, H. Inoue, T. Hama, S. Shenker, OSDI 2010.

Other lists of papers

• Last year's reading list
• Comprehensive list of papers
• Another list of possible papers