• 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

1. Distributed Systems Background
   • The Eight Fallacies of Distributed Computing - Peter Deutsch, Jim Gosling, Arnon Rotem-Gal-Oz
   • Introduction to Distributed System Design - Google Code University
2. Sample System
   • 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.

Scalability

1. Request distribution
   • Locality-Aware Request Distribution, Vivek Pai, Guarav Banga, ASPLOS-VIII
     • Background: The Power of Two Choices in Randomized Load Balancing. Michael Mitzenmacher. IEEE Trans. on Parallel and Distributed Systems, October 2001.
     • Background: How Useful is Old Information? Michael Mitzenmacher. IEEE Trans. on Parallel and Distributed Systems. January 2000.
     • Background: Interpreting Stale Load Inforamtion. Michael Dahlin. IEEE Trans. on Parallel and Distributed Systems. October 2000.
   • 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
2. Large-scale services
   • Web Search for a Planet: The Google Cluster Architecture. Luiz André Barroso, Jeffrey Dean and Urs Hölzle, IEEE Micro, March-April 2003.
   • Lessons from Giant-Scale Services. Eric A. Brewer. IEEE Internet Computing. Vol. 5, No. 4. pp. 46-55. July/August 2001.
     • Background: Harvest, Yield, and Scalable Tolerant Systems. Armando Fox and Eric Brewer. Hot OS 1999.
     • Background: On Designing and Deploying Internet-Scale Services. James Hamilton. LISA 2007.

Distributed Operating Systems

1. Designs
   • The LOCUS Distributed Operating System, Bruce Walker, Gerald Popek, Robert English, Charles Kline and Greg Thiel. Proceedings of the 9th Symposium on Operating Systems Principles, Nov. 83
     • Background: LOCUS a network transparent, high reliability distributed system G. Popek, B. Walker, J. Chow, D. Edwards, C. Kline, G. Rudisin, and G. Thiel. In SOSP '81 Proceedings of the eighth ACM symposium on Operating systems principles. 1981.
2. Processor Pools
   • D. Thain, T. Tannenbaum and M. Livny, "Distributed Computing in Practice: The Condor Experience", Concurrency and Computation: Practice and Experience 17, 2-4, February-April 2005, pp. 323-356
     • Background; Douglas Thain and Miron Livny, Building Reliable Clients and Servers, in Ian Foster and Carl Kesselman, editors, The Grid: Blueprint for a New Computing Infrastructure, Morgan Kaufmann, 2003, 2nd edition. ISBN: 1-55860-933-4
     • Background: Michael Litzkow, Todd Tannenbaum, Jim Baseny and Miron Livny. Checkpoint & Migration of UNIX Processes in the Condor Distributed Processing System,University of Wisconsin-Madison Computer Sciences Technical Report #1346, 1997

Consistency

1. Time and Ordering
   • L. Lamport, Time, Clocks, and the Ordering of Events in a Distributed System, Communications of the ACM, July 1978, pages 558-564.
     • Background: Network Time Protocol
     • Background: Detection of Mutual Inconsistency in Distributed Systems D. S. Parker, G. J. Popek, G. Rudisin , A. Stoughton, B. J. Walker, E. Walton, J. M. Chow, D. Edwards, S. Kiser, C. Kline. IEEE Transactions on Software Engineering, Volume 9 Issue 3, May 1983/
   • M. Chandy and L. Lamport. Distributed snapshots: determining global states of distributed systems. ACM Trans. Comput. Syst., 3(1):63-75, 1985.
2. 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.
   • 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
     • Background: Fisher, Lynch, and Paterson. Impossibility of Distributed Consensus with One Faulty Process, Journal of the ACM, 1985
3. Process Groups
   • 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.

Replication

1. Demers et al., Epidemic algorithms for replicated database maintenance, PODC 1987.
   • Background: Jerome H. Saltzer and M. Frans Kaashoek, Principles of Computer System Design, Chapter 10: Consistency.
   • Background: David K. Gifford, Weighted voting for replicated data. Proceedings of the seventh ACM symposium on Operating systems principles, 1979
   • Background: 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.
2. 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.
   • Eventually Consistent. Werner Vogels. ACM Queue, December 2008.
   • Choosing Consistency. Werner Vogels, allthingsdistributed.com blog posting, Feb. 2010

Agreement

1. The Part-Time Parliament. Leslie Lamport; ACM Transactions on Computer Systems, Vol. 16, No. 2, May 1998
2. Leslie Lamport. Paxos Made Simple. ACM SIGACT News (Distributed Computing Column) 32, 4 (Whole Number 121, December 2001) 51-58.
3. Tushar Chandra, Robert Griesemer, and Joshua Redstone. Paxos Made Live – An Engineering Perspective. PODC '07: 26th ACM Symposium on Principles of Distributed Computing, 2007.

Storage

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

Advanced Topics

• 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.
  • Background:Pete Keleher, Alan L. Cox, Sandhya Dwarkadas and Willy Zwaenepoel. TreadMarks Distributed Shared Memory on Standard Workstations and Operating Systems. IN PROCEEDINGS OF THE 1994 WINTER USENIX CONFERENCE, 1994.
• 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.

conference

Cloud Computing

• Brian Hayes. Cloud Computing. Communications of the ACM, Volume 51, Issue 7 (July 2008). Pages 9-11.
• 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.

Data Manipulation Models

• MapReduce: Simplified Data Processing on Large Clusters. 
Jeffrey Dean and Sanjay Ghemawat 
OSDI'04
  • MapReduce and parallel DBMSs: friends or foes? Michael Stonebraker, Daniel Abadi, David J. DeWitt, Sam Madden, Erik Paulson, Andrew Pavlo, Alexander Rasin. Communications of the ACM, Volume 53 , Issue 1 (January 2010), Pages: 64-71.
  • MapReduce: a flexible data processing tool Jeffrey Dean and Sanjay Ghemawat. Communications of the ACM, Volume 53 , Issue 1 (January 2010). Pages: 72-77.
• DryadLINQ: A System for General-Purpose Distributed Data-Parallel Computing Using a High-Level Language Yuan Yu, Michael Isard, Dennis Fetterly, Mihai Budiu, Ulfar Erlingsson, Pradeep Kumar Gunda, and Jon Currey. Symposium on Operating System Design and Implementation (OSDI), San Diego, CA, December 8-10, 2008.
  • Distributed Data-Parallel Programs from Sequential Building Blocks 
Michael Isard, Mihai Budiu, Yuan Yu, Andrew Birrell, and Dennis Fetterly 
European Conference on Computer Systems (EuroSys), Lisbon, Portugal, 
March 21-23, 2007

Cloud Infrastructure

• The Chubby Lock Service for Loosely-Coupled Distributed Systems
• Bigtable: A Distributed Storage System for Structured Data
• Interpreting the Data: Parallel Analysis with Sawzall Rob Pike, Sean Dorward, Robert Griesemer, Sean Quinlan
• The Google File System 
Sanjay Ghemawat, Howard Gobioff, Shun-Tak Leung 
SOSP'03
  • GFS: Evolution on Fast-Forward. Kirk McKusick, Sean Quinlan, Communications of the ACM, Vol. 53 No. 3, Pages 42-49.
• Autopilot: Automatic Data Center Management Michael Isard April 2007.
• X-Trace: A Pervasive Network Tracing Framework Rodrigo Fonseca, George Porter, Randy H. Katz, Scott Shenker, Ion Stoica. NSDI'07

Cloud Scheduling

• Quincy: Fair Scheduling for Distributed Computing Clusters. Michael Isard, Vijayan Prabhakaran, Jon Currey, Udi Wieder, Kunal Talwar, and Andrew Goldberg, October 2009.
• Resource overbooking and application profiling in shared hosting platforms Bhuvan Urgaonkar, Prashant Shenoy and Timothy Roscoe. OSDI 2002
• Managing energy and server resources in hosting centers. Jeffrey S. Chase, Darrell C. Anderson, Prachi N. Thakar, Amin M. Vahdat and Ronald P. Doyle. SOSP 2001.
• Making Scheduling ``Cool'': Temperature-Aware Workload Placement in Data Centers, by J. Moore, J. Chase, P. Ranganathan. In the 2005 USENIX Annual Technical Conference (USENIX '05), April 2005.
• Delay Scheduling: A Simple Technique for Achieving Locality and Fairness in Cluster Scheduling. Zaharia, Matei, Dhruba Borthakur, Joydeep Sen Sarma, Khaled Elmeleey, Scott Shenker and Ion Stoica. Eurosys 2010

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

Other possible papers

extra-reading