CSEP590SG PMP Distributed Systems: paper list

• P.V. Mockapetris and K.J. Dunlap, Development of the Domain Name System. Proceedings of ACM SIGCOMM 1988, pages 123-133, August 1988.

• Peter B. Danzig, Katia Obraczka, and Anant Kumar, An Analysis of Wide-area Name Server Traffic: A Study of the Domain Name System. In Proceedings of SIGCOMM 92, pages 281-292, January 1992.

• Jaeyeon Jung, Emil Sit, Hari Balakrishnan, and Robert Morris, DNS Performance and the Effectiveness of Caching. ACM SIGCOMM Internet Measurement Workshop, November 2001.

  Background reading from textbook: intro material in chapters 1, 2, 3.1, and name services in chapter 9.

  Related papers we won't cover:

  • Derek C. Oppen and Yogen K. Dalal, The Clearinghouse: a Decentralized Agent for Locating Named Objects in a Distributed Environment. ACM Transactions on Information Systems (TOIS), 1(3):230-253, July 1983.

  • Brent Welch and John K. Ousterhout, Prefix Tables: A Simple Mechanism for Locating Files in a Distributed System. Proceedings of the 6th International Conference on Distributed Computing Systems (ICDCS), New York, May 1986, pages 184-189.

• F. Cristian, A Probabilistic Approach to Distributed Clock Synchronization. Proceedings of the 9th International Conference on Distributed Computing Systems (ICDCS), pages 288-296, Newport Beach, California, June 1989.

• Leslie Lamport, Time, Clocks, and the Ordering of Events in a Distributed System. Communications of the ACM, 21(7):558-565, July 1978.

• K. Mani Chandy and Leslie Lamport, Distributed Snapshots: Determining Global States of Distributed Systems. ACM Transactions on Computing Systems (TOCS), 3(1):63-75, February 1985.

  Background reading from textbook: chapter 10.

• Kenneth P. Birman, The Process Group Approach to Reliable Distributed Computing. Communications of the ACM (CACM), 36(12):37-53, December 1993.

• D.R. Cheriton and D. Skeen, Understanding the Limitations of Causal and Totally Ordered Multicast. Proceedings of the 14th Symposium on Operating System Principles (SOSP '93), December 1993.

• S. Floyd, V. Jacobson, C. Liu, S. McCanne, and L. Zhang, A Reliable Multicast Framework for Light-weight Sessions and Application Level Framing. IEEE/ACM Transactions on Networking, 5(6):784-803, December 1997.

  Background reading from textbook: chapters 4.5 and 11.4.

  Related papers we won't cover:

  • Kenneth P. Birman and Thomas A. Joseph, Exploiting virtual synchrony in distributed systems. Proceedings of the 11th ACM Symposium on Operating Systems Principles (SOSP), pages 123-138, November 1987.

  • Kenneth P. Birman, Andre Schiper, Pat Stephenson, Lightweight Causal and Atomic Group Multicast. ACM Transactions on Computer Systems (TOCS), 9(3): 272-314 (1991).

  • D.R. Cheriton and W. Zwaenepoel, Distributed Process Groups in the V Kernel. ACM Transactions on Computer Systems, 3(2):77--107, May 1985.

• L. Lamport, R. Shostak, and M. Pease, The Byzantine Generals Problem. ACM Transactions on Programming Languages and Systems, 4(3):382-401, July 1982.

• Leslie Lamport, The Part-time Parliament. ACM Transactions on Computer Systems (TOCS), 16(2):133-169, May 1998.
  • lecture notes on paxos
  • an alternate explanation of Paxos by Butler Lampson- read before doing assignment 3

  Background reading from textbook: chapter 11.

  Related papers we won't cover:

  • Joseph Y. Halpern and Yoram Moses, Knowledge and common knowledge in a distributed environment. Proceedings of the Third Annual ACM Symposium on Principles of Distributed Computing, Vancouver, BC, Canada, August 1984.

• Fred B. Schneider, Implementing Fault-tolerant Services using the State Machine Approach: a Tutorial. ACM Computing Surveys (CSUR), 22(4):299-319, December 1990.

• Miguel Castro and Barbara Liskov, Practical Byzantine Fault Tolerance. Proceedings of the Third Symposium on Operating Systems Design and Implementation (OSDI), New Orleans, USA, February 1999.

• David E. Lowell, Subhachandra Chandra, and Peter M. Chen, Exploring Failure Transparency and the Limits of Generic Recovery. Proceedings of the Fourth Symposium on Operating Systems Design and Implementation (OSDI 2000), October 2000
  • lecture notes on rollback recovery

  Background reading from textbook: chapter 13.

  Related papers we won't cover:

  • Miguel Castro and Barbara Liskov, Proactive Recovery in a Byzantine-Fault-Tolerant System. Proceedings of the Fourth Symposium on Operating Systems Design and Implementation (OSDI), San Diego, USA, October 2000.

  • Robert Haskin, Yoni Malachi, and Gregory Chan, Recovery Management in QuickSilver. ACM Transactions on Computer Systems (TOCS), 6(1):82-108, February 1988.

  • Frank Schmuck and Jim Wyllie, Experience with Transactions in QuickSilver. Proceedings of the Thirteenth Symposium on Operating Systems Principles, pages 239-253, October 1991.

• Bruce G. Lindsay, Laura M. Haas, C. Mohan, Paul F. Wilms, and Robert A. Yost, Computation and Communications in R*: a Distributed Database Manager. ACM Transactions on Computer Systems (TOCS), 2(1):24-38, February 1984.

• Alan Demers, Dan Greene, Carl Hauser, Wes Irish and John Larson, Epidemic Algorithms for Replicated Database Maintenance. Proceedings of the Sixth Annual ACM Symposium on Principles of Distributed Computing, pages 1-12, 1987.

• D. B. Terry, M. M. Theimer, Karin Petersen, A. J. Demers, M. J. Spreitzer, and C. H. Hauser, Managing Update Conflicts in Bayou, a Weakly Connected Replicated Storage System. Proceedings of the Fifteenth ACM Symposium on Operating Systems Principles (SOSP), 1995.

  Background reading from textbook: chapter 14.

  Related papers we won't cover:

  • D. Parker, G. Popek, G. Rudisin, A. Stoughton, B. Walker, E. Walton, J. Chow, D. Edwards, S. Kiser, C. and Kline, Detection of Mutual Inconsistency in Distributed Systems. IEEE Transactions on Software Engineering, 9(3):240--247, May 1983.

  • Brian M. Oki and Barbara H. Liskov, Viewstamped Replication: a General Primary Copy Method to Support Highly Available Distributed Systems. Proceedings of the Seventh Annual ACM Symposium on Principles of Distributed Computing, pages 8-17, 1988.

  • C. Gray and D. Cheriton, Leases: an Efficient Fault-tolerant Mechanism for Distributed File Cache Consistency. Proceedings of the Twelfth ACM Symposium on Operating Systems Principles (SOSP), pages 202-210, Litchfield Park, Arizona, December 1989.

  • R. Ladin, B. Liskov, L. Shira, and S. Ghemewat, Providing High Reliability using Lazy Replication. ACM Transactions on Computer Systems (TOCS), 10(4):360--391, 1992.

  • 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, pages 288-301, 1997.

• Roger M. Needham, Michael D. Schroeder, Using Encryption for Authentication in Large Networks of Computers. Communications of the ACM, 21(12): 993-999, December 1978.

• B. Clifford Neuman and Theodore Tso, Kerberos: An Authentication Service for Computer Networks. IEEE Communications, 32(9):33-38. September 1994. (This is a very short paper- you do not need to submit a summary for this paper.)

• Steven M. Bellovin and Michael Merritt, Limitations of the Kerberos Authentication System. USENIX Conference Proceedings, pp. 253--267, Winter 1991.

• Michael Burrows, Martin Abadi, and Roger Needham, A Logic of Authentication. ACM Transactions on Computer Systems (TOCS), 8(1):18-36, February 1990.

  Background reading from textbook: chapter 7.

  Related papers we won't cover:

  • D. Otway and O. Rees, Efficient and timely mutual authentication. Operating Systems Review, 21(1):8-10, January 1987.

  • Dorothy E. Denning and Giovanni Maria Sacco, Timestamps in Key Distribution Protocols. Communications of the ACM (CACM), 24(8):533-536, August 1981.

  • T. Mark Lomas, Li Gong, Jerome H. Saltzer, and Roger M. Needham, Reducing Risks from Poorly Chosen Keys. In Proceedings of the 12th ACM Symposium on Operating Systems Principles, pages 14-18, December 1989.

  • Butler Lampson, Martin Abadi, Michael Burrows, and Edward Wobber, Authentication in Distributed Systems: Theory and Practice. Proceedings of the 13th Symposium on Operating System Principles (SOSP '91), pages 165-182, 1991.

  • Andrew D. Birrell, Butler W. Lampson, Roger M. Needham, and Michael D. Schroeder, A Global Authentication Service Without Global Trust. In Proceedings of the IEEE Symposium on Security and Privacy, pages 223-230, April 1986.

  • Martin Abadi and Roger Needham, Prudent Engineering Practices for Cryptographic Protocols. DEC SRC research report 125, June 1994.

• Alex C. Snoeren, Craig Partridge, Luis A. Sanchez, Christine E. Jones, Fabrice Tchakountio, Stephen T. Kent, and W. Timothy Strayer.Single-Packet IP Traceback. IEEE/ACM Transactions on Networking (ToN), Volume 10, Number 6, December 2002.

• David Moore, Geoffrey Voelker, and Stefan Savage.Inferring Internet Denial of Service Activity. Proceedings of the 2001 USENIX Security Symposium, Washington D.C., August 2001.

• David Moore, Colleen Shannon, Geoffrey M. Voelker, and Stefan Savage.Internet Quarantine: Requirements for Containing Self-Propagating Code. Proceedings of Infocom 2003, San Francisco, CA, April 2003.

  Related papers we won't cover:

  • Stuart Staniford, Vern Paxson, and Nicholas Weaver.How to Own the Internet in Your Spare Time. Proceedings of the 2002 USENIX Security Symposium, San Francisco, CA, August 2002.

• Eric A. Brewer.Lessons from Giant-Scale Services. IEEE Internet Computing, 5(4): pp.46-55.

• Yasushi Saito, Brian Bershad, and Henry Levy. Manageability, Availability and Performance in Porcupine: A Highly Scalable Cluster-Based Mail Service. Proc. of the 17th ACM Symp. on Operating Systems Principles, December 1999.

• Armando Fox, Steven D. Gribble, Yatin Chawathe, and Eric A. Brewer.Scalable Network Services. Proceedings of the 16th ACM Symposium on Operating Systems Principles (SOSP-16), St. Malo, France, October 1997.

• John Ousterhout, The Role of Distributed State. CMU Computer Science: A 25th Anniversary Commemorative, ACM Press Anthology Series, R. Rashid (Ed.), July 1991.

• Michael D. Schroeder, Andrew D. Birrell, Roger M. Needham, Experience with Grapevine: the growth of a distributed system. ACM Transactions on Computer Systems (TOCS) 2(1):3-23, February 1984.

  Related papers we won't cover:

  • Andrew D. Birrell, Roy Levin, Roger M. Needham, and Michael D. Schroeder, Grapevine: An Exercise in Distributed Computing. Communications of the ACM, 25(4):260-274, April 1982.

  • Sape J. Mullender, Guido van Rossum, Andrew S. Tanenbaum, Robbert van Renesse, and Hans van Staveren, Amoeba: a Distributed Operating System for the 1990s. IEEE Computer 23(5):44-53, May 1990.

  • David Cheriton, The V Distributed System. Communications of the ACM, 31(3):314-333, March 1988.