CS6410 Topic Outline and Reading

[8/28, 9/2] What is Systems About? (Speaker: Schneider)

• J.H. Saltzer, D.P. Reed, D.D. Clark. End-to-end arguments in system design. ACM Transactions on Computer Systems Volume 2, Issue 4 (November 1984), pages 277--288.
• B. Lampson. Hints for computer system design. Proceedings of the Ninth ACM Symposium on Operating Systems Principles (Bretton Woods, New Hampshire, United States) 1983, pages 33--48.

[9/4] Threads vs Events? (Speaker: van Renesee)

• H. C. Lauer and R. M. Needham. On the duality of operating system structures. ACM SIGOPS Operating Systems Review Volume 12, Issue 2 (April 1979), pages 3--19.
• Rob von Behren, Jereny Condit, and Eric Brewer. Why events are a bad idea (for high-concurrency servers). Proceedings of the 9th conference on Hot Topics in Operating Systems - Volume 9 (Lihue, Hawaii, 2003), page 4.

  Optional:

  • C. Hauser et al. Using threads in interactive systems: a case study. Proceedings of the Fourteenth ACM Symposium on Operating Systems Principles (Asheville, North Carolina, 1994), pages 94--105
  • A. Birrell. An introduction to programming with threads Technical Report, Microsoft Research, May 2005.
  • R. van Renesse. Goal-oriented programming, or composition using events, or threads considered harmful. Proceeding of the 8th ACM SIGOPS European Workshop on Support for Composing Distributed Applications (Sintra, Portugal, 1998), pages 82--87.
  • Matt Welsch, David Culler, and Eric Brewer. SEDA: An Architecture for Well Conditioned, Scalable Internet Services. Proceedings of the Eighteenth ACM Symposium on Operating Systems Principles (Banff, Alberta, Canada, 2001), pages 230--243.
  • Rob von Behren et al. Capriccio: Scalable threads for internet services. Proceedings of the Nineteenth ACM Symposium on Operating Systems Principles (Bolton Landing, NY, 2003), pages 268--281.
  • Maxwell Krohn, Eddie Kohler, and M. Frans Kaashoek. Events can make sense. Proceedings of the 2007 USENIX Annual Technical Conference (Santa Clara, CA, June 2007), pages 87--107..
  • Richard P. Draves, Brian N. Bershad, Richard F. Rashid, and Randall W. Dean. Using continuations to implement thread management and communication in operating systems. Proceedings of the Thirteenth ACM Symposium on Operating Systems Principles (Pacific Grove, California, 1991), pages 122--136.

[9/9, 9/11] Writing Specification (Speaker: Schneider)

• Leslie Lamport. A simple approach to specifying concurrent systems. Communications of the ACM, Volume 32, Issue 1 (Jan 1989), pages 32--45.
• Robbert van Renesse and Fred B. Schneider. Chain replication for supporting high throughput and availability. Proceedings of the 6th conference on Symposium on Operating Systems Design & Implementation, Volume 6 (San Francisco, CA, 2004), pages 91--104.

[9/16] Operating System Structure I (Speaker: Schneider)

• E.W. Dijkstra. The structure of the “THE”-multiprogramming system. Communications of the ACM Volume 11, Issue 5 (May 1968), pages 341--346.
• P, Brinch Hansen. The nucleus of a multiprogramming system. Communications of the ACM Volume 13, Issue 4 (April 1970), pages 238--241.
• Dennis M. Ritchie and Ken Thompson. The UNIX time-sharing system. Communications of the ACM Volume 17, Issue 7 (July 1974), pages 365--375.

[9/18] Operating System Structure II (Speaker: Kulkarni)

• M. Young, A Tavanian, R. Rashid, D. Golub, and J. Eppinger. The Duality of Memory and Communication in the Implementation of a Multiprocessor Operating System. Proceedings of the Eleventh ACM Symposium on Operating Systems Principles (Austin, Texas, United States), ACM, 1987, pages 63--76.
• B. Bershad et al. Extensibility, Safety and Performance in the SPIN Operating System Proceedings of the Fifteenth ACM Symposium on Operating Systems Principles (Copper Mountain, Colorado, United States) 1995, pages 267--284.

  Optional:

  • J. Liedtke. On micro-kernel construction. Proceedings of the Fifteenth ACM Symposium on Operating Systems Principles (Copper Mountain, Colorado, United States) 1995, pages 237--250.

[9/23, 9/25] Novel File System Implementations (Speaker: Bjorklund)

• Mendel Rosenblum, and John K. Ousterhout. The design and implementation of a log-structured file system. ACM Transactions on Computer Systems Volume 10, Issue 1 (February 1992), pages 26--52.
• John Hartman and John K. Ousterhout. The Zebra striped network file system. ACM Transactions on Computer Systems Volume 13, Issue 3 (August 1995), pages 274--310.
• M. Satyanarayanan. The evolution of Coda. ACM Transactions on Computer Systems Volume 20, Issue 2 (May 2002), pages 85--124.

[10/2] Virtual Machines (Speaker: Abu-Libdeh)

• Paul Barham Paul et al. Xen and the art of virtualization. Proceedings of the Nineteenth ACM Symposium on Operating Systems Principles (Bolton Landing, NY, USA), 2003. 164--177.
• Mendel Rosenblum and Tal Garfinkel. Virtual machine monitors: Current technology and future trends IEEE Computer Magazine Volume 38, No. 5 (May 2005), pages 39--47.
• S. T. King, G. W. Dunlap, and P. M. Chen. Operating system support for virtual machines. Proceedings of the annual conference on USENIX Annual Technical Conference (San Antonio, Texas, 2003), pages 71--84.
• C.A. Waldspurger. Memory resource management in VMware ESX server Proceedings of the 5th Symposium on Operating Systems Design and Implementation (San Francisco, CA, August 2002),pages 181--194.

[10/7] Distributed Systems Fundamentals (Speaker: Mathapati)

• Lamport, Leslie. Time, Clocks, and the Ordering of Events in a Distributed System. Communications of the ACM Volume 21, Issue 7 (July 1978), pages 558--565.
• Mani Chandy and Leslie Lamport. Distributed snapshots: Determining global states of distributed systems. ACM Transactions on Computer Systems Volume 3, Issue 1 (February 1985), 63--75.

[10/16] Agreement (Speaker: Khemmarat)

• Leslie Lamport, Robert Shostak, and Marshall Pease. The Byzantine generals problem. ACM Transactions on Programming Languages and Systems Volume 4, Issue 3 (July 1982), 382--401.
• Michael Fischer, Nancy A. Lynch, and Michael S. Patterson. Impossibility of distributed consensus with one faulty process. Journal of the ACM Volume 32, Issue 2 (April 1985), 374--382.

[10/21] PAXOS (Speaker: van Renesee)

• Robbert van Renesse, Mark Bickford, Danny Dolev, Fred B. Schneider, Yee Jiun Song. Agreement without tears: Stepwise refinement of consensus. Unpublished draft.

[10/23, 10/28] Replica Management (Speakers: Parvati and Teigen)

• Fred Schneider B. Implementing fault-tolerant services using the state machine approach: A tutorial. ACM Computing Surveys Volume 22, Issue 4 (December 1990), 299--319.
• T.C. Bressoud. and F. B. Schneider. Hypervisor-based fault tolerance ACM Transactions on Computer Systems Volume 14, Issue 1 (February 1996), 80--107.
• Kenneth P. Birman. The process group approach to reliable distributed computing. Communications of the ACM Volume 36, Issue 12 (December 1993), 37--53.
• Miguel Castro and Barbara Liskov. Practical byzantine fault tolerance and proactive recovery ACM Transactions on Computer Systems Volume 20, Issue 4 (Nov 2002), pages 398--461.
• Miguel Castro, Rodrigo Rodrigues, and Barbara Liskov. BASE: Using abstraction to improve fault tolerance. ACM Transactions on Computer Systems Volume 21, Issue 3 (August 2003), pages 236--269.
• Amitanand S. Aiyer et al. BAR fault tolerance for cooperative services. Proceedings of the Twentieth ACM Symposium on Operating Systems Principles (Brighton, United Kingdom, 2005), pages 45--58.

[10/30] Quorum Systems (Speaker: Chmelev)

• David Gifford K. Weighted voting for replicated data Proceedings of the Seventh ACM Symposium on Operating Systems Principles (Pacific Grove, California, United States), 1979, 150--162.
• Maurice Herlihy. A quorum-consensus replication method for abstract data types. ACM Transactions on Computer Systems Volume 4, Issue 1 (February 1986), 32--53.
• Dahlia Malkhi and Michael Reiter. Byzantine quorum systems. Distributed Computing 11, Number 4 (Oct 1998), pages 203--213.

[11/4] Peer to Peer (Speaker: Abu-Libdeh)

• Ian Clarke, Oskar Sandberg, Brandon Wiley, and Theodore W. Hong. Freenet: A distributed anonymous information storage and retrieval system. Lecture Notes in Computer Science Volume 2009, Springer Verlag, 2001.
• Ion Stoica, Robert Moris, David Karger, M. Frans Kaashoek, and Hari Balakrishnan. Chord: A scalable peer-to-peer lookup service for internet applications. Proceedings of the 2001 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (San Diego, California, United States), 2001, 149--160.
• Yang-hua Chu, Sanjay Rao, and Hui Zhang. A Case For End System Multicast. Proceedings of the 2000 ACM SIGMETRICS International Conference on measurement and Modeling of Computer Systems (Santa Clara, California, 2000) pages 1--12.

[11/6] Epidemic Algorithms (Speaker: Demers)

• Demers, Alan et al. Epidemic algorithms for replicated database maintenance. Proceedings of the Sixth Annual ACM Symposium on Principles of Distributed Computing (Vancouver, British Columbia, Canada), 1987, 1--12.
• van Renesse, Robbert, Kenneth P. Birman, and Werner Vogels. Astrolabe: A robust and scalable technology for distributed system monitoring, management, and data mining. ACM Transactions on Computer Systems Volume 21, Issue 2 (May 2003), 164--206.

[11/11, 11/13] Enforcing Integrity (Speaker: Schneider)

• Robert Wahbe et al. Efficient software-based fault isolation. Proceedings of the Fourteenth ACM Symposium On Operating Systems Principles (Asheville, North Carolina, 1994), pages 203--216.
• George C. Necula and Peter Lee. Safe kernel extensions without run-time checking Proceedings Second USENIX Symposium on Operating Systems Design and Implementation (Berkeley, CA:, 1996), pages 229--244.

[11/18, 11/20, 11/25] System Security and Trusted Computing (Speaker: Walsh)

• Butler Lampson. Computer security in the real world. Proceedings Annual Computer Security Applications Conference (New Orleans, Louisiana, USA), December 2000.
• Butler Lampson, Martin Abadi, Michael Burrows, Edward Wobber. Authentication in distributed systems: Theory and practice. ACM Transactions on Computer Systems Volume 10, Issue 4 (November 1992), 265--310.
• Andrew W. Appel and Edward W. Felten. Proof-carrying authentication. Proceedings of the 6th ACM Conference on Computer and Communications Security ( Kent Ridge Digital Labs, Singapore, 1999), pages 52--62.
• Lujo Bauer, Michael A. Schneider, Edward W. Felten. A Proof-Carrying Authorization System. Technical Report, Computer Science Dept, Princeton University. August 2001.
• R. Sailer, X. Zhang, T. Jaeger, and L van Doorn. Design and Implementation of a TCG-based Integrity Measurement Architecture. Proceedings 13th USENIX Security Sympoisum (San Diego, CA, August 2004). 223-238.

[12/2, 12/4] Large Systems (Speaker: Davis)

• Sanjay Ghemawat, Howard Gobioff, Shun-Tak Leung. The Google file system. Proceedings of the Nineteenth ACM Symposium on Operating Systems Principles (Bolton Landing, NY, 2003), pages 29--43.
• Jeffrey Dean and Sanjay Ghemawat. MapReduce: Simplified data processing on large clusters. Proceedings of Operating Systems Design and Implementation (San Francisco, CA., 2004) pages 137--150.
• Fay Chang et al. Bigtable: A distributed storage system for structured data. Proceedings of Operating Systems Design and Implementation (Vancouver, B.C., Canada, 2006), pages 205--218.
• Mohammad Al-Fares, Alexander Loukissas, Amin Vahdat. A scalable, commodity data center network architecture. Proceedings of ACM SIGCOMM 2008 (Seattle, Washington, August 2008), pages 63--74.