Download this page as a tarball

Stanford University Systems Quals -2000
including paper summaries and treasure trove summaries
*reading list borrowed from Gurmeet Manku's quals page. Paper summaries provided by George Candea, Ramesh Chandra, Andy Chou, Andy Huang, Emre Kiciman, and Gurmeet Manku.

Networks and Distributed Systems



Textbooks



1. A.S. Tanenbaum. Computer Networks. Prentice-Hall, 3rd edition, 1996.

2. Jean Walrand, "Communication Networks: a First Course," 2nd edition.

3. Coulouris, Dollimore and Kindberg, Distributed Systems: Concepts and Design." Addison Wesley, 2nd edition, 1994.

4. S. Mullender. Distributed Systems. ACM Process, 1990.




Networks


1. 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. [ summary ]

2. V. Jacobson, Congestion Avoidance and Control,  Proc. ACM SIGCOMM '88, Aug. 1988, pp. 314-329. [summary]

3. W. E. Leland, M. S. Taqqu, W. Willinger and D. V. Wilson, "On the Self-Similar Nature of Ethernet Traffic, " Proc. ACM SIGCOMM'93, pp. 183-193. [ summary | tt]




Overview/Systems

1. B. Walker, et al., "The LOCUS Distributed Operating System."  Proceedings of the 9th SOSP, October 1983. [summary]         

2. 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. [summary]         

3. D. Cheriton, The V Distributed System, Communications of the ACM, March 1988. [ summary ]

4. J. Ousterhout et al., The Sprite Network Operating System,  IEEE Computer, February 1988. [ summary ]

5. B. Oki et al., The Information Bus - An Architecture for Extensible Distributed Systems,  Proceedings of the 14th SOSP, December 1993. [ summary ]

6. R. Pike et al., Plan 9 from Bell Labs, Computing Systems, Vol 8, No 3, Summer 1995, pp. 221-254 [ summary | tt]




Distributed Shared Memory

1. K. Li and P. Hudak, Memory Coherence in Shared Virtual Memory Systems, ACM Trans. Computer Systems, Vol 7, No 4, Nov 1989, p. 321-359. [ summary ]

2. J. Carter, J. Bennett, and W. Zwaenepoel, Implementation and Performance of Munin, Proceedings of the 13th SOSP, October 1991. [ summary ]




Object-oriented Distributed Systems

1. Andrew Birrell, Greg Nelson, Susan Owicki, and Edward Wobber Network Objects, Proceedings of the 14th SOSP, December 1993. 95 version (DEC-SRC Report). [ summary ]

2. Steve Vinoski, CORBA: Integrating Diverse Applications Within  Distributed Heterogeneous Environments,  IEEE Communications Magazine, Vol. 14, No. 2, February, 1997. [ summary ]




Clocks: Real, Virtual and Logical

1. David L. Mills, Internet Time Synchronization: the Network Time  Protocol, IEEE Transactions on Communications, vol. 39, no. 10, Oct. 1991. [ summary ]

2. David Jefferson et al., Distributed Simulation and the Time Warp Operating System,  Eleventh ACM Symposium on Operating Systems Principles. Nov. 1987.  In Operating Systems Review (1987) vol.21, no.5, p. 77-93. [summary]

3. David Cheriton and Dale Skeen, Understanding the Limitations of Causally and Totally Ordered Communication, Proceedings of the 14th  SOSP, December 1993. [ summary | tt ]




Distributed/Network File Systems

1. Russel Sandberg et al., Design and Implementation of the Sun Network Filesystem, Proceedings of the Summer 1985 USENIX Conference, June 1985. [ summary | tt ]

2. Hitz J., Lau J., Malcolm M., File System Design for an NFS File Server Appliance USENIX Winter Conference, San Francisco, CA, 1994. [ summary ]

3. C. Gray and D. Cheriton, Leases: An Efficient Fault-Tolerant Mechanism  for Distributed File Cache Consistency,  Proceedings of the 12th SOSP, December 1989. [ summary ]

4. B. Liskov, et al., Replication in the Harp File System, Proceedings of the 13th SOSP, October 1991.[ summary ]

5. Kistler, J. J., and Satyanarayanan, M., Disconnected Operation in the Coda File System, ACM Transactions on Computer Systems, vol. 10, vol. 1 (Feb. 1992), pp 3-25. [ summary | tt ]

6. J. Hartman and J. Ousterhout, The Zebra Striped Network File System, Proceedings of the 14th SOSP, December 1993. [ summary | tt ]

7. T. Anderson et al.,  Serverless Network File Systems,  Proceedings of the 15th ACM Symposium of Operating Systems Principles, Dec. 1995. [ summary ]




Transactions

1. D. Duchamp, Analysis of Transaction Management Performance, Proceedings of the 12th SOSP, December 1989. [ summary ]

2. D. Gifford, "Weighted Voting for Replicated Data." Proceedings of the 7th SOSP, December 1979. [ summary ]




Directories and Naming

1. Butler W. Lampson, Designing a Global Name Service, ACM Reprint No. 0-89791-198-9/86/0800-0001, Sept. 1986. [ summary ]

2. David Cheriton and Timothy Mann, Decentralizing a Global Naming Service for Improved Performance and Fault Tolerance , ACM Transactions on Computer Systems, vol. 7, no. 2, May 1989, pages 147-183. [ summary ]




Authentication

1. S. M. Bellovin and M. Merritt, Limitations of the Kerberos Protocol, Computer Comm. Review, vol. 20, no. 5, October 1990. [ summary ]

2. John Kohl, B. Clifford Neuman, and Theodore Ts'o, The Evolution of the Kerberos Authentication Service, EurOpen Conference Proceedings,  Norway, May 1991.[ summary ]

3. Butler Lampson, Martin Abadi, Michael Burrows, and Edward Wobber,  Authentication in Distributed Systems: Theory and Practice, Proceedings of the 13th SOSP, October 1991. [ summary ]




Distributed Scheduling

1. F. Douglis and J. K. Ousterhout, Transparent Process Migration: Design Alternatives and the Sprite Implementation, Software Practice and Experience, vol. 21, no. 8 (August 1991), pp 757-785. [ summary ]




Communication Support

1. Birrell, A. D. and Nelson, B. J, "Implementing Remote Procedure Calls," ACM Transactions on Computer Systems, vol 2, no. 1, Feb. 1984, pp 39-59. [ summary ]
Operating Systems



Operating System Structure


1. Dijkstra, E.W., The Structure of the THE Multiprogramming System,  Communications of the ACM, Vol. 11, No. 5 (May 1968), 341-346. [ summary | tt ]

2. Ritchie, D.M., and Thompson, K., The UNIX Time-Sharing SystemThe Bell System Technical Journal, Vol. 57, No. 6 (July-August 1978), Part 2, pp. 1905-1929. [ summary]

3. Thompson, K., "UNIX Implementation," The Bell System Technical Journal, Vol. 57, No. 6 (July-August 1978), Part 2, pp. 1931-1946. [ summary | tt]

4. [Cher88] Cheriton, D.R., The V Distributed System, Communications of the ACM, Vol. 31, No. 3 (March 1988), pp. 314-333. [ summary | tt ]

5. Mullender, S.J., van Rossum, G., Tanenbaum, A.S., van Renesse, R., and van Staveren, H., "Amoeba: A Distributed Operating System for the 1990s," Computer Vol. 23, No. 5 (May 1990), pp. 44-53. [ summary | tt ]

6. Jones, A. K., The object model: A conceptual tool for structuring software. In Operating Systems: An Advanced Course, R. Bayer, et al. Ed., Springer-Verlag, 1979, pp. 7-16. [ summary ]



Extending the Operating System


1. 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.
[ summary | SPIN Website | tt ]


2. 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.
[ summary | Exokernel Webpage | tt ]


3. Cheriton, D., and Duda, K., A caching model of operating system kernel functionality, In Proceedings of the First Symposium on Operating Systems Principles," Pages 179-193. November 1994. [ summary | tt ]

4. Liedtke, J., On micro-kernel construction, In Proceedings of the 15th Symposium on Operating System Principles, December 1995. [ summary ]



Synchronization and Communication


1. Hoare, C.A.R.,Monitors: An Operating System Structuring Concept, Communications of the ACM, Vol. 17, No. 10 (Oct. 1974), pp. 549-557. [ summary | summary2 ]

2. 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. [ Postscript version | summary | tt ]

3. Hoare, C.A.R., "Communicating Sequential Processes," Communications of the ACM, Vol. 21, No. 8 (Aug. 1978), pp. 666-677. [ summary | summary2 ]

4. 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. [ summary | tt ]

5. Bershad, B.N., Anderson, T.E., Lazowska, E.D., and Levy, H.M., Lightweight Remote Procedure Call, ACM Transactions on Computer Systems, Vol. 8, No. 1 (February 1990), pp.37-55. [ summary | tt ]

6. Coffman, Jr., E.G., Elphick, M.J., and Shoshani, A., "System Deadlocks", Computing Surveys, Vol. 3, No. 2, June 1971, pp. 67-78. [ summary ]

7. Bershad, B.N., " Practical Considerations for Non-Blocking Concurrent Objects, Proceedings of the 13th International Conference on Distributed Computing Systems, May 1993. [ summary ]

8. Lauer, H.C., and Needham, R. M., ‘‘On the Duality of Operating System Structures.’’ Proc. Second Int’l Symposium on Operating Systems, IRIA, October 1978, reprinted in Operating Systems Review, Vol. 13, No. 2, April 1979, pp. 3-19. [ summary | summary2 | summary3 | tt ]



Virtual Memory


1. 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. [ summary | tt ]

2. 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. [ summary | tt ]

3. Denning, Peter J., "Working Sets, Past and Present," IEEE Transactions on Software Engineering, SE-6, 1 (January 1980), pp. 64-84. [ summary | tt ]

4. 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. [ summary | tt ]

5. Talluri, M., Hill, M.D., and Khalidi, Y.A., A New Page Table for 64-bit Address Spaces, Proceedings of the 15th SOSP, Operating Systems Review, Vol. 29, No. 5, December 1995, pp. 184-200. [ summary ]

6. Rashid, R.F., et al., Machine-Independent Virtual Memory Management for Paged Uniprocessor and Multiprocessor Architectures, IEEE Transactions on Computers, Vol. 37 No. 8 (August 1988), pp. 896-908. [ summary | tt ]

7. Young, M., et al, The Duality of Memory and Communication in the Implementation of a Multiprocessor Operating System Proceedings of the 11th Symposium on Operating Systems Principles, November 1987, pp. 63-76. [ summary | tt ]

8. 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. [ summary | summary2 | summary3 ]

9. 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. [ summary | tt ]

10. 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. [ summary ]



File Systems


1. Feiertag, R.J. and Organick, E.I. , "Multics Input/Output System." Proceedings of the 3rd SOSP, 1971, pp. 35-41. [ summary ]

2. Ritchie, D.M., and Thompson, K., The UNIX Time-Sharing System, Communications of the ACM, Vol. 17, No. 7, July 1974, pp. 365-375. [ summary ]

3. Smith, Alan Jay, "Input/Output Optimizations and Disk Architectures: A Survey," Performance Evaluation, Vol. 1, 1981, pp. 104-117. [ summary ]

4. 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. [ summary | tt ]

5. 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. [ summary ]

6. 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. [ summary ]

7. 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. [ summary ]

8. Rosenthal, D., Evolving the Vnode Interface, Proceedings of the Summer Usenix Conference, Anaheim, CA, June 1990, pp. 107-117. [ summary ]

9. 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. [ summary | tt ]



Transactions and Reliability


1. Verhofstad, J.S.M., "Recovery Techniques for Database Systems," Computing Surveys, Vol. 10, No. 2 (June 1978), pp. 167-195. [ summary | tt ]

2. Gray, J., "The Transaction Concept: Virtues and Limitations," Proc. 7th International Conference on Very Large Data Bases, September 1981, pp. 144-154. [ summaries | tt ]

3. Stonebraker, M., "Operating System Support for Database Management," Communications of the ACM, Vol. 24, No. 7 (July 1981), pp. 412-418. [ summary | tt ]

4. Liskov, B., and Scheifler, R., "Guardians and Actions: Linguistic Support for Robust, Distributed Programs," ACM Trans. on Programming Languages and Systems, Vol. 5, No. 3 (July 1983), pp. 381-404. [ summary ]

5. 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. [ summary ]

6. Bartlett, J., "A NonStop Kernel", Proceedings of the 8th SOSP, Operating Systems Review, Vol. 11, No. 5, November 1977, pp.23-31. [ summary | tt ]

7. Stonebraker, M., DuBourdieux, D., Edwards, W., "Problems in Supporting Database Transactions in an Operating System Transaction Manager," Operating Systems Review, vol. 19, no. 1, January 1985, pp. 6-14. [ summary ]

8. 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. [ summary | tt ]

9. 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. [ summary ]



Protection and Security


1. Schroeder, M.D. and Saltzer, J.H., "A Hardware Architecture for Implementing Protection Rings," Communications of the ACM, Vol. 15, No. 3 (March 1972), pp. 157-170. [ summary | tt ]

2. 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. [ summary | tt ]

3. Saltzer, Jerome H., The Protection of Information in Computer Systems Proceedings of the IEEE, Vol. 63, No. 9 (September 1975), pp. 1278-1308. [ summary | tt ]

4. Denning, D.E. and Denning, P.J., "Data Security," Computing Surveys, Vol. 11, No. 3 (September 1979), pp. 227-249. [ summary | tt ]

5. 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. [ summary | tt ]

6. Steiner, J.G., Neuman, C., and Schiller, J.I., Kerberos: An Authentication Service for Open Network Systems, USENIX Winter Conference Proceedings, February 1988, pp. 191-202. [ summary | tt ]

7. 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. [ summary | tt ]

8. 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. [ summary ]

9. Morris, R., and Thompson, K., Password Security: A Case History, Communications of the ACM, Vol. 22, No. 11, November 1979, pp. 594-597. [ summary ]

10. Butler W. Lampson, A Note on the Confinement Problem, Communications of the ACM, Vol. 16, No. 10, October 1973, pp.613-615. Postscript version. [ summary ]

11 Thompson, K., Reflections on Trusting Trust, Communication of the ACM, Vol. 27, No. 8, August 1984, pp. 761-763. [ summary ]

12. Anderson, R.J., Why Cryptosystems Fail, Communications of the ACM, Vol. 37, No. 11, November 1994. [ summary ]



Multiprocessors


1. Li, K., Hudak, P., Memory Coherence in Shared Virtual Memory Systems, ACM Trans. on Computer Systems, Vol. 7, No. 4 (November 1989), pp. 321-359. [ summary | tt ]

2. 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. [ summary ]

3. 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. [ summary ]

4. Chapin, J., Rosenblum, M., Devine, S., Lahiri, T., Teodosiu, D., and Gupta, A., Hive: Fault Containment for Shared-Memory Multiprocessors., in The 15th ACM Symposium on Operating Systems Principles, December 1995. [ summary ]



Miscellaneous


1. 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). [ summary ]

2. Goldberg, R.P., "Survey of Virtual Machine Research," Computer, Vol. 7, No. 6 (June 1974), pp. 34-45. [ summary | tt ]

3. Lampson, B.W., Hints for Computer System Design, Proceedings of the 9th Symposium on Operating Systems Principles, October 1983, pp. 33-48. Postscript version. [ summary | tt ]

4. 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. [ summary ]

5. Hoare, C.A.R., ‘‘The Emperor’s Old Clothes", Communications of the ACM, Vol. 24, No. 2, February 1981, pp. 75-83. [ summary | tt ]

6. 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. [ summary ]

7. 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. [ summary ]

8. 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. [ summary ]

9. 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. [ summary ]


Useful links:
ACM Classic Papers
Online publications (only for Stanford fellas)
EECS 582, U Mich, Winter 2000
CSE 506 Suny SB

  Last updated on Sunday May 6
Maintained by Emre Kiciman