8/24/2006

Net&System Reading List @ Stanford

original link http://www-cs-students.stanford.edu/phd/net-ds.html

Texts:

  1. A.S. Tanenbaum. Computer Networks. Prentice-Hall, 3rd edition, 1996.
  2. Coulouris, Dollimore and Kindberg, "Distributed Systems: Concepts and Design." Addison Wesley, 2nd edition, 1994.
  3. S. Mullender. Distributed Systems. ACM Process, 1990.

Papers:

  1. D. Aguayo et al., "Link-level Measurements from an 802.11b Mesh Network." SIGCOMM 2004.
  2. T. Anderson et al., "Serverless Network File Systems, " Proceedings of the 15th ACM Symposium of Operating Systems Principles, Dec. 1995.
  3. Luiz Barroso et al., "Web Search for a Planet: The Google Cluster Architecture." IEEE Micro, 2003.
  4. S. M. Bellovin and M. Merritt, "Limitations of the Kerberos Protocol." Computer Comm. Review, vol. 20, no. 5, October 1990.
  5. A. Birrell and B. Nelson, "Implementing Remote Procedure Calls," ACM Transactions on Computer Systems, vol 2, no. 1, Feb. 1984, pp 39-59.
  6. Mike Burrows, "The Chubby Lock Service for Loosely-Couplted Distributed Systems." OSDI 2006.
  7. B. Carpenter, "Architectural Principles of the Internet." RFC 1958.
  8. David Cheriton and Dale Skeen, "Understanding the Limitations of Causally and Totally Ordered Communication." Proceedings of the 14th SOSP, December 1993.
  9. Alan Demers et al., "Analysis and Simulation of a Fair Queueing Algorithm." SIGCOMM 1989.
  10. A. Fox et al., "Cluster-Based Scalable Network Services." Proceedings of the 16th SOSP, 1997.
  11. C. Gray and D. Cheriton, "Leases: An Efficient Fault-Tolerant Mechanism for Distributed File Cache Consistency." Proceedings of the 12th SOSP, December 1989.
  12. Krishna Gummadi et al., "Measurement, Modeling, and Analysis of a Peer-to-Peer File-Sharing Workload." SOSP 2003.
  13. M. Handley, "Why the Internet only Just Works." BT Technology Journal, Vol 24, No. 3, 2006.
  14. J. Hartman and J. Ousterhout, "The Zebra Striped Network File System." Proceedings of the 14th SOSP, December 1993
  15. Ryan Huebsch et al., "Querying the Internet with PIER." VLDB 2003.
  16. V. Jacobson, "Congestion Avoidance and Control" Proc. ACM SIGCOMM '88, Aug. 1988, pp. 314-329.
  17. S. Katti et al., "XORs in the Air: Practical Wireless Network Coding." SIGCOMM 2006.
  18. J. Kistler and M. Satyanarayanan, "Disconnected Operation in the Coda File System," ACM Transactions on Computer Systems, vol. 10, vol. 1 (Feb. 1992), pp 3-25.
  19. John Kohl, B. Clifford Neuman, and Theodore Ts'o, "The Evolution of the Kerberos Authentication Service." EurOpen Conference Proceedings, Norway, May 1991.
  20. Butler Lampson, Martin Abadi, Michael Burrows, and Edward Wobber, "Authentication in Distributed Systems: Theory and Practice." Proceedings of the 13th SOSP, October 1991
  21. David L. Mills, "Internet Time Synchronization: the Network Time Protocol." IEEE Transactions on Communications, vol. 39, no. 10, Oct. 1991.
  22. J. Ousterhout et al., "The Sprite Network Operating System." IEEE Computer, February 1988.
  23. R. Pike et al., "Plan 9 from Bell Labs." Proceedings of the UK Unix Users Group Summer 1990 Conference, London, 1990.
  24. J. H. Saltzer, D.P. Reed and D. D. Clark, "End-to-End Arguments in System Design, " ACM Transactions on Computer Systems, vol. 2, no. 4, November 1984, pp. 277-288.
  25. Russel Sandberg et al., "Design and Implementation of the Sun Network Filesystem." Proceedings of the Summer 1985 USENIX Conference, June 1985.
  26. M. Schroeder, A. Birrell, and R. Needham, "Experience with Grapevine: The Growth of a Distributed System," ACM Transactions on Computer Systems, vol. 2, no. 1 (February 1984), pp 3-23.
  27. David Wetherall, "Active Network Vision and Reality: Lessons from a Capsule-Based System." SOSP 1999.

8/07/2006

OS Reading List @ Stanford V200607

original link - http://xenon.stanford.edu/phd/OSReadingList.php

OS Qualifying Exam Reading List: 2006-07

Concurrency
Experience with Processes and Monitors in Mesa Lampson, Redell
Scheduler Activations: Effective Kernel Support for the User-Level Management of Parallelism Thomas E. Anderson, Brian N. Bershad, Edward D. Lazowska, and Henry M. Levy
Borrowed-Virtual-Time (BVT) scheduling: supporting latency-sensitive threads in a general-purpose scheduler Duda and Cheriton
An Investigation of the Therac-25 Accidents Leveson and Turner
Eraser: A Dynamic Data Race Detector for Multithreaded Programs Stefan Savage
Capriccio: Scalable Threads for Internet Services Rob von Behren, Jeremy Condit, Feng Zhou, George C. Necula, and Eric Brewer
Why Threads Are a Bad Idea (for most purposes) John Ousterhout
Cooperative Task Management without Manual Stack Management (up to and including Section 3) Atul Adya, Jon Howell, Marvin Theimer, William J. Bolosky, John R. Douceur
Threads cannot be implemented as a library Hans-J. Boehm
Virtual Memory
Virtual Memory Primitives for User Programs Appel and Li
Virtual Memory Management in the VAX/VMS Operating System Levy and Lipman
Practical, Transparent, Operating System Support for Superpages Navarro, Iyer, Druschel, and Cox
Memory Resource Management in VMware ESX Server Waldspurger
Reliability
Improving the Reliability of Commodity Operating Systems [Nooks] Swift, Bershad, Levy
A Dynamic Technique for Eliminating Buffer Overflow Vulnerabilities (and Other Memory Errors) Rinard, Cadar, Dumitran, Roy, Leu
Enhancing Server Availability and Security Through Failure-Oblivious Computing Rinard, Cadar, Dumitran, Roy, Leu, Beebee
Networking
Eliminating Receive Livelock in an Interrupt-Driven Kernel Mogul and Ramakrishnan
The End to End Argument in System Design Saltzer, Reed, Clark
File Systems
The HP AutoRAID hierarchical storage system John Wilkes, Richard Golding, Carl Staelin, and Tim Sullivan
Design and Implementation of the SUN Network Filesystem Sandberg et al.
The Design and Implementation of a Log-Structured File System Rosenblum and Ousterhout
Leases: An Efficient Fault-Tolerant Mechanism for Distributed File Cache Consistency Gray and Cheriton
A Low-Bandwidth Network File System Muthitacharoen, Chen, and Mazieres
MapReduce: Simplified Data Processing on Large Clusters Dean and Ghemawat
Soft Updates: A Solution to the Metadata Update Problem in File Systems McKusick, Ganger
A Case for Redundant Arrays of Inexpensive Disks (RAID) Patterson, Gibson, and Katz
Virtualization
Xen and the Art of Virtualization Barham et. al
A Comparison of Software and Hardware Techniques for x86 Virtualization Adams and Ageson
Distributed Systems
The Chubby lock service for loosely-coupled distributed systems Burrows
OS Security
Making Information Flow Explicit in HiStar Nickolai Zeldovich, Silas Boyd-Wickizer, Eddie Kohler, and David Mazi`eres
Experience
Application Performance and Flexibility on Exokernel Systems Kaashoek et. al
The Rise of "Worse is Better" Richard Gabriel
Hints for Computer System Design Butler Lampson

8/01/2006

OS Reading List @ Stanford

The following references cover the topics of which every researcher in operating systems should be aware. Students who read the following references and can apply the ideas presented in papers should do well on the Operating Systems part of the Systems Ph.D. Qualifying examination.
List last revised: 10/06/03
Links added: 01/26/06 by Brian D. Carlstrom



Operating System Structure
[Dijk68] Dijkstra, E.W., "The Structure of the THE Multiprogramming System" Communications of the ACM, Vol. 11, No. 5 (May 1968), 341-346. ACM PDF
[Ritc78] Ritchie, D.M., and Thompson, K., "The UNIX Time-Sharing System," The Bell System Technical Journal, Vol. 57, No. 6 (July-August 1978), Part 2, pp. 1905-1929. Author PDF
[Thom78] Thompson, K., "UNIX Implementation," The Bell System Technical Journal, Vol. 57, No. 6 (July-August 1978), Part 2, pp. 1931-1946. CiteSeer PDF
[Cher88] Cheriton, D.R., "The V Distributed System," Communications of the ACM, Vol. 31, No. 3 (March 1988), pp. 314-333. ACM PDF

Extending the Operating System
[Bers95] Bershad, B.N., Savage, S., Pardyak, P., Sirer, E.G., Fiuczunski, M., Becker, D., Chambers, C., and Eggers, S., "Extensibility: Safety and Performance in the SPIN Operating System," Proceedings of the 15th Symposium on Operating System Principles, December 1995, pp. 267-284. ACM PDF
[Engl95] Engler, D.R., Kaashoek, M.F., and O'Toole Jr., J., "Exokernel: an operating system architecture for application-specific resource management.", In Proceedings of the 15th Symposium on Operating System Principles, December 1995, pp. 251-266. ACM PDF
[Lied95] Liedtke, J., "On micro-kernel construction," In Proceedings of the 15th Symposium on Operating System Principles, December ACM PDF 1995.

Synchronization and Communication
[Lamp80] Lampson, B.W., and Redell, D.D., "Experience with Processes and Monitors in Mesa," Communications of the ACM, Vol. 23, No. 2 (Feb. 1980), pp. 105-117. ACM PDF
[Hoar78] Hoare, C.A.R., "Communicating Sequential Processes," Communications of the ACM, Vol. 21, No. 8 (Aug. 1978), pp. 666-677. ACM PDF
[Mass89] Massalin, H. and Pu, C., "Threads and Input/Output in the Synthesis Kernel," Proceedings of the 12th Symposium on Operating Systems Principles, December 1989, pp. 191-200. ACM PDF
[Coff71] Coffman, Jr., E.G., Elphick, M.J., and Shoshani, A., "System Deadlocks", Computing Surveys, Vol. 3, No. 2, June 1971, pp. 67-78. ACM PDF
[Bers93] Bershad, B.N., "Practical Considerations for Non-Blocking Concurrent Objects," Proceedings of the 13th International Conference on Distributed Computing Systems, May 1993. IEEE PDF
[Laue78] Lauer, H.C., and Needham, R. M., "On the Duality of Operating System Structures." Proc. Second International Symposium on Operating Systems, IRIA, October 1978, reprinted in Operating Systems Review, Vol. 13, No. 2, April 1979, pp. 3-19. ACM PDF
[Sava97] Savage, S., Burrows, M., Nelson, G., Sobalvarro, P., Anderson, T., "Eraser: A Dynamic Data Race Detector for Multi-Threaded Programs" SOSP '97. ACM PDF
[Mogu96] J. C. Mogul and K. K. Ramakrishnan. Eliminating receive livelock in an interrupt-driven kernel. In Proc. of the 1996 Usenix Technical Conference, pages 99--111, 1996. ACM PS

Virtual Memory
[Dale68] Daley, R.C., and Dennis, J.B., "Virtual Memory, Processes and Sharing in MULTICS," Communications of the ACM, Vol. 11, No. 5 (May 1968), pp. 306-312. ACM PDF
[Bens72] Bensoussan, A., Clingen, C.T., and Daley, R.C., "The MULTICS Virtual Memory: Concepts and Design," Communications of the ACM, Vol. 15, No. 5 (May 1972), pp. 308-318. ACM PDF
[Denn80] Denning, Peter J., "Working Sets, Past and Present," IEEE Transactions on Software Engineering, SE-6, 1 (January 1980), pp. 64-84. CiteSeer PDF
[Levy82] Levy, H.M., and Lipman, P.H., "Virtual Memory Management in the VAX/VMS Operating System," Computer, Vol. 15, No. 3 (March 1982), pp. 35-41. CS 240 PDF
[Hart92] Harty, K., and Cheriton, D., "Application-Controlled Physical Memory using External Page-Cache Management," Proceedings of the Fifth International Conference on Architectural Support for Programming Languages and Operating Systems, Boston, MA, October 1992, pp. 187-199. ACM PDF
[Bolo89] Bolosky, W., Fitzgerald, R., and Scott, M, "Simple But Effective Techniques for NUMA Memory Management." Proceedings of the 12th SOSP, Operating Systems Review, Vol. 23, No. 5, December 1989, pp. 19-31. ACM PDF
[Verg96] Verghese, B., Devine, S., Gupta, A., and Rosenblum, M., "Operating System Support for Improving Data Locality on CC-NUMA Compute servers," In Proceedings of the Seventh International Conference on Architectural Support for Programming Languages and Operating Systems, Cambridge, MA, 1996. ACM PDF
[Nav02] Navarro, J., Iyer, S., Druschel, P., Cox, A., "Practical, Transparent, Operating System Support for Superpages," Proceedings of USENIX OSDI 2002. ACM PDF
[Wald02] Waldspurger, C. Memory Resource Management in VMware ESX Server. Proceedings of USENIX OSDI 2002. ACM PDF

File Systems
[Smit81a] Smith, Alan Jay, "Input/Output Optimizations and Disk Architectures: A Survey," Performance Evaluation, Vol. 1, 1981, pp. 104-117. TBD TBD
[McKu84] McKusick, M.K., Joy, W.N., Leffler, S.J., and Fabry, R.S., "A Fast File System For UNIX," ACM Transactions on Computer Systems, Vol. 2, No. 3 (August 1984), pp. 181-197. ACM PDF
[Rose91] Rosenblum, M., and Ousterhout, J.K., "The Design and Implementation of a Log-Structured File System," ACM Transactions on Computer Systems, Vol. 10, No. 1 (February 1992), pp. 26-52. ACM PDF
[Kron86] Kronenberg, N.P., Levy, H.M., and Strecker, W.D., "VAXclusters: A Closely-Coupled Distributed System" ACM Transactions on Computer Systems Vol. 4, No. 2 (May 1986), pp. 130-146. ACM PDF
[Ritc74] Ritchie, D.M., and Thompson, K., "The UNIX Time-Sharing System." Communications of the ACM, Vol. 17, No. 7, July 1974, pp. 365-375. ACM PDF
[Klei86] Kleiman, S.R., "Vnodes: An Architecture for Multiple File System Types in Sun UNIX," Proceedings of the Summer Usenix Conference, Atlanta, GA, 1986. pp. 238-247. CiteSeer PDF
[Rose90] Rosenthal, D., "Evolving the Vnode Interface," Proceedings of the Summer Usenix Conference, Anaheim, CA, June 1990, pp. 107-117. CiteSeer PDF
[Hagm87] Hagmann, R., "Reimplementing the Cedar File System Using Logging and Group Commit," Proceedings of the 11th Symposium on Operating Systems Principles, Operating System Review, Vol. 21, No. 5, Nov. 1987, pp. 115-162. ACM PDF
[Sand85] Russel Sandberg and David Goldberg and Steve Kleiman and Dan Walsh and Bob Lyon, "Design and Implementation of the Sun Network Filesystem," Proc. Summer 1985 USENIX Conf. CiteSeer PDF
[Patt88] Patterson, D., Gibson, G. and Katz, R., `A Case for Redundant Arrays of Inexpensive Disks (RAID)', Proc. of 1988 ACM SIGMOD Conf. on Management of Data, Chicago, IL, June 1988. ACM PDF
[Ganger95] G. Ganger, Y. Patt, "Soft Updates: A Solution to the Metadata Update Problem in File Systems", Technical Report CSE-TR-254-95, University of Michigan, Ann Arbor, August 1995. ACM PDF

Transactions and Reliability
[Verh78] Verhofstad, J.S.M., "Recovery Techniques for Database Systems," Computing Surveys, Vol. 10, No. 2 (June 1978), pp. 167-195. ACM PDF
[Gray81] Gray, J., "The Transaction Concept: Virtues and Limitations," Proc. 7th International Conference on Very Large Data Bases, September 1981, pp. 144-154. CS 240 PDF
[Ston81] Stonebraker, M., "Operating System Support for Database Management," Communications of the ACM, Vol. 24, No. 7 (July 1981), pp. 412-418. ACM PDF
[Borg83] Borg, A., Blau, W., Graetsch, W., Herrmann, F., and Oberle, W., "Fault Tolerance Under UNIX," ACM Transactions on Computer Systems, Vol. 7, No. 1 (February 1989), pp. 1-24. ACM PDF
[Bart81] Bartlett, J., "A NonStop Kernel", Proceedings of the 8th SOSP, Operating Systems Review, Vol. 11, No. 5, November 1977, pp.23-31. ACM PDF
[Ston81] Stonebraker, M., DuBourdieux, D., Edwards, W., "Problems in Supporting Data Base Transactions in an Operating System Transaction Manager," Operating Systems Review, vol. 19, no. 1, January 1985, pp. 6-14. ACM PDF
[Hask88] Haskin, R., Malachi, Y., Sawdon, W., and Chan, G., "Recovery Management in QuickSilver." ACM Trans. on Computer Systems 6(1), February 1988, pp. 82-108. ACM PDF
[Chen96] Chen, P.M, Ng, W.T., Chandra, S., Aycock,C., Rajamani,G. Lowell,D., "The Rio File Cache: Surviving Operating System Crashes", Proceedings of the 1996 International Conference on Architectural Support for Programming Languages and Operating Systems, October 1996. ACM PDF
[Gray89] C. Gray and D. Cheriton, "Leases: An Efficient Fault-Tolerant Mechanism for Distributed File Cache Consistency." Proceedings of the 12th SOSP, December 1989 ACM PDF

Protection and Security
[Wulf74] Wulf, W. et al, "HYDRA: The Kernel of a Multiprocessor Operating System," Communications of the ACM, Vol. 17, No. 6 (June 1974), pp. 337-345. ACM PDF
[Salt75] Saltzer, Jerome H., "The Protection of Information in Computer Systems," Proceedings of the IEEE, Vol. 63, No. 9 (September 1975), pp. 1278-1308. IEEE PDF Author HTML
[Denn79] Denning, D.E. and Denning, P.J., "Data Security," Computing Surveys, Vol. 11, No. 3 (September 1979), pp. 227-249. ACM PDF
[Need78] Needham, R.M. and Schroeder, M.D., "Using Encryption for Authentication in Large Networks of Computers," Communications of the ACM, Vol. 21, No. 12 (December 1978), pp. 993-999. ACM PDF
[Burr90] Burrows, M., Abadi, M., and Needham, R., "A Logic of Authentication," ACM Transactions on Computer Systems, Vol. 8, No. 1 (February 1990), pp. 18-36. ACM PDF
[Lamp91] Lampson, B., Abadi, M., Burrows, M., and Wobber, E., "Authentication in Distributed Systems: Theory and Practice," Proceedings of the Thirteenth ACM Symposium on Operating Systems Principles, Operating Systems Review, Vol. 25, No. 5, Pacific Grove, California, October 1991, pp. 165-182. ACM PDF
[Morr79] Morris, R., and Thompson, K., "Password Security: A Case History," Communications of the ACM, Vol. 22, No. 11, November 1979, pp. 594-597. ACM PDF
[Lamp73] Butler W. Lampson, "A Note on the Confinement Problem," Communications of the ACM, Vol. 16, No. 10, October 1973, pp.613-615. ACM PDF
[Thom84] Thompson, K., "Reflections on Trusting Trust," Communication of the ACM, Vol. 27, No. 8, August 1984, pp. 761-763. ACM PDF
[Ande94] Anderson, R.J., "Why Cryptosystems Fail," Communications of the ACM, Vol. 37, No. 11, November 1994. ACM PDF
[Eng00] Dawson Engler, Benjamin Chelf, Andy Chou, and Seth Hallem. "Checking System Rules Using System-Specific, Programmer-Written Compiler Extensions." In Proceedings of the Fourth Symposium on Operating Systems Design and Implementation, San Diego, CA, October 2000 Usenix PDF

Multiprocessors
[Cart91] Carter, J.B., Bennett, J.K., and Zwaenepoel, W.. "Implementation and Performance of Munin," Proceedings of the 13th ACM Symposium on Operating Systems Principles, October 1991, pp. 152-164. ACM PDF
[And92] Anderson, T., Bershad, B., Lazowska, E., and Levy, H.. "Scheduler Activations: Effective Kernel Support for the User-Level Management of Parallelism," ACM Transactions on Computer Systems, Vol. 10, No. 1 (February 1992), pp. 53-79. ACM PDF
[Bugn97] E. Bugnion, S. Devine, and M. Rosenblum. "Disco: Running Commodity Operating Systems on Scalable Multiprocessor." In SOSP 16, October 1997. ACM PDF

Miscellaneous
[Sher72] Sherman, S.W., Baskett, F., and Browne, J.C., "Trace-Driven Modeling and Analysis of CPU Scheduling in a Multiprogramming System," Communications of the ACM, Vol. 15, No. 12 (December 1972). ACM PDF
[Gold74] Goldberg, R.P., "Survey of Virtual Machine Research," Computer, Vol. 7, No. 6 (June 1974), pp. 34-45. CiteSeer PDF
[Lamp83] Lampson, B.W., "Hints for Computer System Design," Proceedings of the 9th Symposium on Operating Systems Principles, October 1983, pp. 33-48. ACM PDF
[Bour78] Bourne, S. R., "The Unix Time-Sharing System: The Unix Shell.", Bell System Technical Journal, Vol. 57, No. 6, July-August 1978, pp. 1971-1990. TBD TBD
[Hoar81] Hoare, C.A.R., "The Emperor's Old Clothes", Communications of the ACM, Vol. 24, No. 2, February 1981, pp. 75-83. ACM PDF
[Laue81] Lauer, H.C., "Observations on the Development of an Operating System.", Proceedings of the 8th SOSP, Operating Systems Review, Vol. 15, No. 5, December 1981, pp. 30-36. ACM PDF
[Salt84] J. H. Saltzer, D.P. Reed and D. D. Clark, "End-to-End Arguments in System Design, " ACM Transactions on Computer Systems, vol. 2, no. 4, November 1984, pp. 277-288. ACM PDF

Specific operating systems
[Corb72] Corbato, F.J., Saltzer, J.H., and Clingen, C.T., "Multics - The first seven years", Proc. Spring Joint Computer Conference, AFIPS, May 1972, pp. 571-583. Author HTML
[Ausl81] Auslander, M.A., Larkin, D.C., and Scherr, A. L., "The Evolution of the MVS Operating System," IBM Journal of Research and Development, Vol. 25, No. 5, September 1981, pp. 471-482. IBM PDF
[Seaw79] Seawright, L.H., and MacKinnon, R.A., "VM/370: A study of multiplicity and usefulness", IBM Systems Journal Vol 18, No 1. 1979, pp. 4-17. IBM PDF
[Cust82] Custer, H., Inside Windows NT, Microsoft Press, 1992. CiteSeer books24x7

One of the best ways to understand operating systems concepts is to look at specific operating systems such as: UNIX [Ritc78], V[Cher88], Mach[Youn87], Multics[Corb72], OS/360 and MVS[Ausl81], Tandem NonStop[Bart81], VM/370[Seaw79], and Windows NT[Cust92].