CS 655 - Literature

Note: For off-campus access to digital libraries, please see Connect from Home. Burkay Genc has kindly written a firefox plugin that simplifies the process. On any page, right-click and select "MyLibrary" to be redirected to the library login page (if necessary) and then the proxy-based web page.

(*) - research proposal suitable for critical review

[C] - discussed in class

Remote Service Invocation (June 8)

A Survey of Remote Procedure Calls. B.H. Tay and A.L. Ananda. ACM SIGOPS Operating Systems Review, 24(3):68-79. Jul 1990. - early overview of remote procedure calls.

(*)[C] Network Objects. Andrew Birrell, Greg Nelson, Susan Owicki, and Edward Wobber. ACM SIGOPS Operating Systems Review (Proceedings of SOSP '93), 27(5):217-230. Dec 1993 - introduction of object orientation.

(*)[C] The JBoss Extensible Server. Marc Fleury and Francisco Reverbel. Middleware '03 Proceedings of the ACM/IFIP/USENIX 2003 International Conference on Middleware, LNCS 2003:344-373. Jun 2003. - state of the art web services system.

The Impact of Research on the Development of Middleware Technology. Wolfgang Emmerich, Mikio Aoyama, and Joe Sventek. ACM Transactions on Software Engineering and Methodology, 17(4). Aug 2008. - comprehensive overview of middleware history.

Global State / Synchronization (June 15)

(*) Robust Synchronization of Software Clocks Across the Internet. Darryl Veitch, Satish Babu and Attila Pàsztor. IMC'04 - Proceedings of the 4th ACM SIGCOMM Conference on Internet Measurement. pp. 219-232. Oct 2004. - physical clock synchronization is difficult.

(*) Robust Synchronization of Absolute and Difference Clocks Over Networks. Darryl Veitch, Julien Ridoux, and Satish Babu Korada. IEEE/ACM Transactions on Networking, 17(2):417-430. Apr 2009. - physical clock synchronization is difficult.

[C] Time, Clocks, and the Ordering of Events in a Distributed System. Leslie Lamport. Communications of the ACM, 21(7):558-565. Jul 1978. - introduction of logical clocks.

Detecting causal relationships in distributed computations: In search of the holy grail. Reinhard Schwarz and Friedemann Mattern. Distributed Computing, 7(3):149-174. Mar 1994. - improved logical clocks.

Understanding the Limitations of Causally and Totally Ordered Communication. David R. Cheriton and Dale Skeen. ACM SIGOPS Operating Systems Review (Proceedings of SOSP '93), 27(5):44-57. Dec 1993. - debate about strict event ordering.

[C] Why bother with CATOCS?. Robbert van Renesse. ACM SIGOPS Operating Systems Review, 28(1):22-27. Jan 1994. - debate about strict event ordering.

Practical Impact of Group Communication Theory. Andre Schiper. Future Directions in Distributed Computing, LNCS 2584. 2003. - application of event ordering.

Total Order Broadcast and Multicast Algorithms: Taxonomy and Survey. Xavier Defago, Andre Schiper, and Peter Urban. ACM Computing Surveys, 36(4):372-421. Dec 2004. - survey / application of event ordering.

(*) Plausible clocks: Constant size logical clocks for Distributed Systems. Francisco J. Torres-Rojas and Mustaque Ahamad. Distributed Algorithms, LNCS 1151:71-88. 1996. - proposal for efficient logical clocks,

(*)[C] Interval Tree Clocks. Paulo Sergio Almeida, Carlos Baquero, and Victor Fonte. Principles of Distributed Systems, LNCS 5401:259-274. 2008. - recent proposal for efficient logical clocks,

(*) The Chubby Lock Service for Loosely-Coupled Distributed Systems. Mike Burrows. Proceedings of OSDI 2006, pages 335-350. November 2006. - Google's synchronization service.

Storage and Replication (June 22)

[C] A Unified Theory of Shared Memory Consistency. Robert C. Steinke and Gary J. Nutt. Journal of the ACM, 51(5):800-849. Sep 2004. - consistency models

[C] Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services. Seth Gilbert and Nancy Lynch. ACM SIGACT News, 33(2):51-59. Jun 2002. - problem description for replicated storage.

[C] Database Replication: a Tale of Research across Communities. Bettina Kemme and Gustavo Alonso. Proceedings of the VLDB Endowment, 3(10):5-12. Sep 2010. - the database perspective.

(*) The Costs and Limits of Availability for Replicated Services. Haifeng Yu and Amin Vahdat. ACM Transactions on Computer Systems, 24(1):70-113. Feb 2006. - research proposal.

(*) PRACTI Replication. Nalini Belaramani, Mike Dahlin, Lei Gao, Amol Nayate, Arun Venkataramani, Praveen Yalagandula, and Jiandan Zheng. Proceedings of NSDI 2006, pages 59-72. May 2006. - research proposal.

(*) 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. Proceedings of OSDI 2006, pages 205-218. November 2006. - Google's system.

(*)[C] Dynamo: Amazon's Highly Available Key-value Store. Giuseppe DeCandia, Deniz Hastorun, Madan Jampani, Gunavardhan Kakulapati, Avinash Lakshman, Alex Pilchin, Swaminathan Sivasubramanian, Peter Vosshall and Werner Vogels. ACM SIGOPS Operating Systems Review (Proceedings of SOSP '07), 41(6):205-220. Dec 2007. - Amazon's system.

(*)[C] Megastore: Providing Scalable, Highly Available Storage for Interactive Services. Jason Baker, Chris Bond, James Corbett, JJ Furman, Andrey Khorlin, James Larson, Jean-Michel Leon, Yawei Li, Alexander Lloyd, and Vadim Yushprakh. Proceedings of CIDR 2011, pages 223-234. Jan 2011. - Google's system.

Fault Tolerance (June 29)

[C] Reaching Agreement in the Presence of Faults . Marshall Pease, Robert Shostak, and Leslie Lamport. Journal of the ACM, 27(2):228-234. Apr 1980. - classical paper on fault tolerance

[C] The Byzantine Generals Problem. Leslie Lamport. ACM Transactions on Programming Languages and Systems, 4(3):382-401. Jul 1982. - classical paper on fault tolerance

[C] Impossibility of Distributed Consensus with One Faulty Process. Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson. Journal of the ACM, 32(2):374-382. Apr 1985. - classical paper on fault tolerance

Implementing Fault-Tolerant Services Using the State Machine Approach: A Tutorial. Fred B. Schneider. ACM Computing Surveys, 22(4):299-319. Dec 1990. - systematic approach to building fault-tolerant services.

Fault Tolerance for Highly Available Internet Services: Concepts, Approaches, and Issues. Narjess Ayari and Denis Barbaron, and Pascale Primet. IEEE Communications Surveys & Tutorials, 10(2):34-46. May 2008. - survey paper.

A Comparative Analysis of Network Dependability, Fault-tolerance, Reliability, Security, and Survivability. M. Al-Kuwaiti, N. Kyriakopoulos, and S. Hussein. IEEE Communications Surveys & Tutorials, 11(2):106-124. May 2009. - survey paper.

(*) Practical Byzantine Fault Tolerance and Proactive Recovery. Miguel Castro and Barbara Liskov. ACM Transactions on Computer Systems, 20(4):398-461. Nov 2002. - research proposal.

(*) BASE: Using Abstraction to Improve Fault Tolerance. Miguel Castro, Rodrigo Rodrigues and Barbara Liskov. ACM Transactions on Computer Systems, 21(3):236-269. Aug 2003. - research proposal.

(*)[C] DepSpace: A Byzantine Fault-Tolerant Coordination Service. Alysson Neves Bessani, Eduardo Pelison Alchieri, Miguel Correia, and Joni Silva Fraga. ACM SIGOPS Operating Systems Review (Proceedings of Eurosys '08), 42(4):163-176. May 2008. - research proposal.

(*) Prophecy: Using History for High-Throughput Fault Tolerance. Proceedings of NSDI 2010. Apr 2010. - research proposal.

Security (July 6)

[C] A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. R. L. Rivest, A. Shamir, and L. Adleman. Communications of the ACM, 21(2):120-126. Feb 1978. - classical paper.

[C] How to Share a Secret. Adi Shamir. Communications of the ACM, 22(11):612-613 Nov 1979. - classical paper.

A Simple Active Attack Against TCP. Laurent Joncheray. Proceedings of 5th USENIX Security Symposium. Jun 1995. - early TCP attack.

Why Cryptosystems Fail. Ross Anderson. Communications of the ACM, 37(11):32-40. Nov 1994. - low-tech problems with crypto-based security.

XML and Web Services Security Standards. Nils Agne Nordbotten. IEEE Communications Surveys & Tutorials, 11(3):4-21. Aug 2009 - survey paper re web services.

A Survey of DHT Security Techniques. Guido Urdaneta, Guillaume Pierre, and Maarten Van Steen. ACM Computing Surveys, 43(2):8. Jan 2011. - survey paper re DHT security.

(*)[C] k-Anonymity: a Model for Protecting Privacy. Latanya Sweeney. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 10(5):557-570. Oct 2002. - research proposal.

(*) Achieving k-Anonymity Privacy Protection using Generalization and Suppression. Latanya Sweeney. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 10(5):571-588. Oct 2002. - research proposal.

Privacy-Preserving Data Publishing: A Survey of Recent Developments. Benjamin C. M. Fung, Ke Wang, Rui Chen, and Philip S. Yu. ACM Computing Surveys, 42(4):14. Jun 2010. - recent survey paper.

(*)[C] Distributed Key Generation for the Internet. Aniket Kate and Ian Goldberg. Proceedings of ICDCS 2009, pages 119-128. June 2009. - research proposal.

(*) TrInc: Small Trusted Hardware for Large Distributed Systems. Dave Levin, John R. Douceur, Jacob R. Lorch, and Thomas Moscibroda. Proceedings of NSDI 2009. Apr 2009. research proposal.

Operating System Integration (July 13)

Reflections on the Memory Wall. Sally A. McKee. Proceedings of the 1st conference on Computing Frontiers (CF'04), 5 pages. Apr 2004. - basic observation.

Overcoming the Memory Wall in Packet Processing: Hammers or Ladders?. Jayaram Mudigonda, Harrick M. Vin, and Raj Yavatkar. Proceedings of ANCS 2005, pages 1-10. Oct 2005. - router perspective, but also applicable to servers..

(*) IO-Lite: A Unified I/O Buffering and Caching System. Vivek S. Pai, Peter Druschel, and Willy Zwaenepoel. ACM Transactions on Computer Systems, 18(1):37-66. Feb 2000. - kernel buffer management.

(*) Lazy Asynchronous I/O For Event-Driven Servers. Khaled Elmeleegy, Anupam Chanda, Alan L. Cox, and Willy Zwaenepoel. Proceedings of USENIX ATC 2004, pages 241-254. Jun 2004. - cost of user/kernel interactions.

(*)[C] Highly Scalable Web Applications with Zero-Copy Data Transfer. Toyotaro Suzumura, Michiaki Tatsubori, Scott Trent, Akihiko Tozawa, and Tamiya Onodera. Proceedings of WWW 2009, pages 921-930. Apr 2009. - cost of user/kernel interactions.

(*)[C] FlexSC: Flexible System Call Scheduling with Exception-Less System Calls. Livio Soares and Michael Stumm. Proceedings of OSDI 2010. October 2010. - cost of user/kernel interactions.