Publications

Butler W. Lampson
(root)

The papers and other items are listed approximately in chronological order of publication. Each has an abstract. Nearly all are available on-line at least in Acrobat form.  Many of them also appear as Web pages and as Microsoft Word documents. Some have Postscript files. When an item is about a system that I worked on, there is a cross-reference to a brief description of that system.

There are some items that are not regular publications but internal memos, interviews, etc. For the most part they have labels of the form 10a, 10b, etc.

1.      Interactive machine-language programming. Proc. AFIPS Conf. 27 (1965), pp 473-482. Abstract, Acrobat. See SDS 940.

2.      A user machine in a time-sharing system. Proc. IEEE 54, 12 (Dec. 1966), pp 1766-1774. Reprinted in Computer Structures, ed. Bell and Newell, McGraw-Hill, 1971, pp 291-300 (with M. Pirtle and W. Lichtenberger). Abstract, Postscript, Acrobat, Web page, Word. See SDS 940.

3.      A critique of  ‘An exploratory investigation of programmer performance under on-line and off-line conditions’. IEEE Trans. Human Factors in Electronics HFE-8, 1 (Mar. 1967), pp 48-51. Abstract, Acrobat.

4.      An on-line editor. Comm. ACM 10, 12 (Dec. 1967), pp 793-799 (with P. Deutsch). Abstract, Acrobat, Acrobat as published, Web page, Word. See QED.

5.      A scheduling philosophy for multi-processing systems. Comm. ACM 11, 5 (May 1968), pp 347-359. Abstract, Acrobat, Acrobat, SOSP version, Acrobat, CACM version, Web page, Word. See Berkeley Computer Corporation.

6.      Dynamic protection structures. Proc. AFIPS Conf. 35 (1969), pp 27-38. Abstract, Acrobat. See Berkeley Computer Corporation.

6a.    Some Remarks on a Large New Time-Sharing System. Internal memo, Berkeley Computer Corporation, September 1970. Abstract, Acrobat. See Berkeley Computer Corporation.

7.      On reliable and extendible operating systems. Proc. 2nd NATO Conf. on Techniques in Software Engineering, Rome, 1969. Reprinted in The Fourth Generation, Infotech State of the Art Report 1, 1971, pp 421-444. Abstract, Acrobat (InfoTech version), Word, Web page, Acrobat. See Cal TSS.

8.      Protection. Proc. 5th Princeton Conf. on Information Sciences and Systems, Princeton, 1971. Reprinted in ACM Operating Systems Rev. 8, 1 (Jan. 1974), pp 18-24. Abstract, Postscript, Acrobat, Web page, Word.

8a.    Teaching of computer design to computer science undergraduates. In The Teaching of Computer Design, Proceedings of the joint IBM-University of Newcastle Seminar, September, 1971. Abstract, Acrobat.

9.      Protection and access control in operating systems. In Operating Systems, Infotech State of the Art Report 14, 1972, pp 309-326. Abstract, Acrobat.

10.    Remarks on the nature of programming. Guest editorial, Software-Practice and Experience 2, 3 (Jul. 1972), pp 195-196. Abstract, Postscript, Acrobat, Web page, Word.

10a.  The control structure of an operating system. IBM Research Report RC3949, July 1972 (with J. Gray, B. Lindsay, and H. Sturgis). Abstract, Acrobat, Web Page, Word. See Cal TSS.

11.    A note on the confinement problem. Comm. ACM 16, 10 (Oct. 1973), pp 613-615. Abstract, Postscript, Acrobat, Web page, Word.

12.    Redundancy and robustness in memory protection. Invited paper, Proc. IFIP Cong., North-Holland, 1974, pp 128-132. Abstract, Acrobat.

13.    On the transfer of control between contexts. Lecture Notes in Computer Science 19, Springer, 1974, pp 181-203 (with J. Mitchell and E. Satterthwaite). Abstract, Acrobat. See Mesa, Mesa architecture.

14.    An open operating system for a single-user machine. Rev. Francaise d'Automatique, Informatique et Recherche Operationnelle 9, B-3 (Sept. 1975), pp 8-15. Substantially revised as [22]. See Alto OS.

15.    Reflections on an operating system design. Comm. ACM 19, 5 (May 1976), pp 251-265 (with H. Sturgis). Abstract, Postscript, Acrobat, Web page, Word. See Cal TSS.

15a. Alto User’s Handbook. Xerox Palo Alto Research Center, 1976. Abstract, Acrobat. See Alto, Bravo.

16.    Storage allocation in typed languages. Proc. 5th Ann. III Conf: Implementation and Design of Algorithmic Languages, Guidel, France, 1977, pp 315-322. Abstract, Acrobat, Web page, Word. See Euclid, Mesa.

17.    Report on the programming language Euclid. ACM Sigplan Notices 12, 2 (Feb. 1977), pp 1-85 (with J. Horning, R. London, J. Mitchell, and G. Popek). Revised as Technical Report CSL-81-12, Xerox Palo Alto Research Center. Abstract, Acrobat. See Euclid.

18.    Notes on the design of Euclid. ACM Sigplan Notices 12, 3 (Mar. 1977), pp 11-18. (with J. Horning, R. London, J. Mitchell, and G. Popek). Abstract, Acrobat. See Euclid.

19.    A terminal-oriented communication system. Comm. ACM 20, 7 (Jul. 1977), pp 486-494 (with P. Heckel). Abstract, Acrobat. See Berkeley Computer Corporation.

20.    Proof rules for the programming language Euclid. Acta Informatica 10, 1 (Jan. 1978), pp 1-26 (with J. Guttag, H. Horning, R. London, J. Mitchell, and G. Popek). Abstract, Acrobat. See Euclid.

21.    Crash recovery in a distributed data storage system. Unpublished technical report, Xerox Palo Alto Research Center, June, 1979, 25 pp. Abstract, Postscript, Acrobat, Web page, Word. See Stable storage, Juniper.

22.    An open operating system for a single-user machine. ACM Operating Systems Rev. 11, 5 (Dec. 1979), pp 98-105 (with R. Sproull). Substantially revised version of [14]. Abstract, Postscript, Acrobat, Web page, Word. See Alto OS.

23.    Experience with processes and monitors in Mesa. Comm. ACM 23, 2 (Feb. 1980), pp 106-117 (with D. Redell). Abstract, Postscript, Acrobat, Web page, Word. See Mesa, Mesa architecture, Mesa monitors and processes.

23a.  Mesa Language Manual. Technical Report CSL-79-3, Xerox Palo Alto Research Center. By James G. Mitchell, William Maybury, and Richard Sweet. Abstract, Acrobat. See Mesa.

24.    A processor for a high-performance personal computer. Proc. 7th IEEE Symposium on Computer Architecture, La Baule, France, 1980, pp 146-160 (with K. Pier). Reprinted in 25 years of the International Symposia on Computer Architecture (selected papers), 1998, pp 180-194. Also in Technical Report CSL-81-1, Xerox Palo Alto Research Center. Abstract, Acrobat as published, Acrobat (produced by scanning and OCR, with some errors), Word, Web page. See Dorado.

25.    Alto: A personal computer. In Computer Structures: Principles and Examples, second edition, ed. Siewiorek, Bell and Newell, McGraw-Hill, 1981, pp 549-572. Also appeared as Technical Report CSL-79-11, Xerox Palo Alto Research Center, August 1979 (with C. Thacker, E. McCreight, R. Sproull, and D. Boggs). Abstract, Acrobat. See Alto.

26.    Distributed Systems-Architecture and Implementation, Lecture Notes in Computer Science 105, Springer, 1981 (editor, with M. Paul and H. Siegert).

27.    Atomic transactions. In [26], pp 246-265 (with H. Sturgis). Abstract, Acrobat. See Juniper.

28.    Remote procedure calls. In [26], pp 357-370. Abstract, Acrobat.

29.    The memory system of a high-performance personal computer. IEEE Trans. Computers C-30, 10 (Oct. 1981), pp 715-732 (with D. Clark and K. Pier). Abstract, Acrobat. See Dorado.

30.    Fast procedure calls. Proc. 1st International Symposium on Architectural Support for Programming Languages and Operating Systems, ACM Sigplan Notices 17, 4 (Apr. 1982), pp 66-75. Abstract, Acrobat.

31.    Practical use of a polymorphic applicative language. Proc. 10th ACM Symposium on Principles of Programming Languages, Austin, 1983, pp 237-255 (with E. Schmidt). Abstract, Acrobat. See system modeling.

32.    Organizing software in a distributed environment. Proc.1983 ACM SIGPLAN Symposium on Programming Language Issues in Software Systems, ACM Sigplan Notices 18, 6 (Jun. 1983), pp 1-13 (with E. Schmidt). Abstract, Acrobat. See system modeling.

32a.  A description of the Cedar language. Technical Report CSL-83-15, Xerox Palo Alto Research Center, December 1983. Abstract, Acrobat. See Cedar.

33.    Hints for computer system design. ACM Operating Systems Rev. 17, 5 (Oct. 1983), pp 33-48. Reprinted in IEEE Software 1, 1 (Jan. 1984), pp 11-28. Abstract, Postscript, Acrobat, Web page, Word.

34.    An instruction fetch unit for a high-performance personal computer. IEEE Trans. Computers C-33, 8 (Aug. 1984), pp 712-730 (with G. McDaniel and S. Ornstein). Abstract, Acrobat. See Dorado.

35.    A kernel language for modules and abstract data types. In Semantics of Data Types, Lecture Notes in Computer Science 173, Springer, 1984, pp 1-50 (with R. Burstall). Revised version appeared as [39]. Abstract, Acrobat. See System modeling.

35a.  VOR: VAX on a RISC. Internal memo, Digital Systems Research Center, December 1984. Abstract, Acrobat.

35b.  Ideas for a simple fast VAX. Internal memo, Digital Systems Research Center, October 1985. Abstract, Acrobat.

36.    Designing a global name service. Proc. 4th ACM Symposium on Principles of Distributed Computing, Minaki, Ontario, 1986, pp 1-10. Abstract, Postscript, Acrobat, Web page, Word. See global name service.

37.    A global authentication service without global trust. Proc. IEEE Symposium on Security and Privacy, Oakland, April 1986, IEEE order number 716, pp 223-230 (with A. Birrell, R. Needham, and M. Schroeder). Abstract, Postscript, Acrobat, Web page, Word. See global name service.

37a.  Interview with Susan Lammers. In Programmers at Work, Microsoft Press, 1986, pp 24-39. Abstract, Acrobat, Web page, Word.

38.    Personal distributed computing: The Alto and Ethernet software. In A History of Personal Workstations, ed. A. Goldberg, Addison-Wesley, 1988, pp 293-335. Abstract, Postscript, Acrobat, Web page, Word. See Alto, Alto OS, Bravo, Mesa, Interpress. A companion paper by C. P. Thacker on the Alto hardware is here.

38a.  Why Alto. Internal memo, Xerox PARC, December 1972. Abstract, Postscript, Acrobat, Web page, Word. See Alto.

38b.  Alto OS design notes. Internal memo, Xerox PARC, February 1973. Abstract, Acrobat. See Alto OS.

39.    Pebble: A kernel language for modules and abstract data types. Information and Computation 76, 2/3 (Feb./Mar. 1988), pp 278-346 (with R. Burstall). Revision of [35]. Abstract, Acrobat. Slides with a synopsis of Pebble are here. See System modeling.

40.    Specifying distributed systems. In Constructive Methods in Computer Science, ed. M. Broy, NATO ASI Series F: Computer and Systems Sciences 55, Springer, 1989, pp 367-396. Abstract, Acrobat.

41.    The Digital distributed system security architecture. Proc. 12th National Computer Security Conf., NIST/NCSC, Baltimore, 1989, pp 305-319 (with M. Gasser, A. Goldstein, and C. Kaufman). Abstract, Word, Web page, Acrobat, Postscript as published, Acrobat as published. See distributed security.

41a.  A distributed systems architecture for the 1990’s. Digital Systems Research Center, December 1989 (with M. Schroeder and A. Birrell). Abstract, Acrobat.

42.    Authentication and delegation with smart-cards. Science of Computer Programming 21, 2 (Oct. 1993), pp 91-113 (with M. Abadi, M. Burrows, and C. Kaufman). Abstract, Postscript, Acrobat.

43.    Requirements and Technology for Computer Security. In Computers at Risk, National Academy Press, Washington, 1991, pp 74-101. Abstract, Postscript, Acrobat, Web page, Word.

44.    A calculus for access control in distributed systems. ACM Trans. Programming Languages and Systems, 15, 4 (Oct. 1993), pp 706-734 (with M. Abadi, M. Burrows, and G. Plotkin). Abstract, Postscript, Acrobat. See Taos authentication.

45.    Authentication in distributed systems: Theory and practice. ACM Trans. Computer Systems 10, 4 (Nov. 1992), pp 265-310 (with M. Abadi, M. Burrows, and E. Wobber). Abstract, Postscript, Acrobat, Web page, Word. See Taos authentication.

46.    On-line data compression in a log-structured file system. ACM Sigplan Notices 27, 9 (Sept. 1992), pp 2-9 (with M. Burrows, C. Jerian, and T. Mann). Abstract, Postscript of SRC technical report, Acrobat of SRC technical report, Acrobat as published. See compressed file system.

47.    Reliable messages and connection establishment. In Distributed Systems, ed. S. Mullender, 2nd ed., Addison-Wesley, 1993, pp 251-281. Abstract, Postscript, Acrobat, Web page, Word.

48.    Principles of Computer Systems. Lecture notes for 6.826, MIT (with W. Weihl, N. Lynch, M. Rinard and D. Jackson). These links are for the 2006 edition of the course. Abstract, Acrobat (2.6 MB, about 450 pages), Word (5.5 MB), Web page (the course Web page at MIT).

49.    A new presumed commit optimization for two phase commit. Proc. 19th VLDB Conference, Dublin, 1993, pp 630-640 (with D. Lomet). Abstract, Postscript, Acrobat.

50.    Correctness of at-most-once message delivery protocols. Proc. 6th International Conference on Formal Description Techniques, Boston, 1993, pp 387-402 (with N. Lynch and J. Søgaard-Andersen). Abstract, Postscript, Acrobat.

51.    Authentication in the Taos operating system. ACM Trans. Computer Systems 12, 1 (Feb. 1994), pp 3-32 (with E. Wobber, M. Abadi, and M. Burrows). Abstract, Postscript, Acrobat of SRC report, Acrobat of TOCS version, Word, Web page, Acrobat of Word version.. See Taos authentication.

52.    Implementing coherent memory. In A Classical Mind: Essays in Honour of C.A.R. Hoare, ed. A. Roscoe, Prentice-Hall, 1994, pp 259-274. Abstract, Postscript, Acrobat.

53.    Putting Telecommunications on the Technology Curve: Architecture and Economics. Lecture notes for 6.892, MIT/LCS/RSS-23, Laboratory for Computer Science, MIT, February 1994 (with S. Gillett and D. Tennenhouse).

54.    Interconnecting computers: Architecture, technology, and economics. Proc. Conference on Programming Languages and System Architectures, Lecture Notes in Computer Science 782, Springer, 1994, pp 1-20. Abstract, Postscript, Acrobat, Web page, Word.

55.    Executive summary. In Evolving the High Performance Computing and Communications Initiative to Support the Nation's Information Infrastructure, National Academy Press, Washington, 1995, pp 1-12 (with I. Sutherland, E. Lazowska, and others). Abstract, Acrobat. The latest (2002) version of the tiretracks diagram that shows how computing research has spawned multi-billion dollar industries in Acrobat or Word format.

56.    Analysis and caching of dependencies. ACM SigPlan International Conference on Functional Programming, Philadelphia, May 1996, pp 83-91 (with M. Abadi and J. Levy). Abstract, Postscript, Acrobat. See Vesta 2.

57.    Virtual infrastructure: Putting information infrastructure on the technology curve. Computer Networks and ISDN Systems 28, 13 (Oct. 1996), pp. 1769 - 1790 (with D. Tennenhouse, S. Gillett, and J. Klein). Abstract, Postscript, Acrobat, Web page, Word.

58.    How to build a highly available system using consensus. In Distributed Algorithms, ed. Babaoglu and Marzullo, Lecture Notes in Computer Science 1151, Springer, 1996, pp 1-17. Abstract, Postscript, Acrobat, Web page, Word. See Paxos.

59.    SDSI: A Simple Distributed Security Infrastructure. http://theory.lcs.mit.edu/~cis/sdsi.html, 1996 (with R. Rivest). Abstract, Postscript, Acrobat, Web page. See SDSI.

60.    Revisiting the Paxos algorithm. Proc. WDAG'97, Lecture Notes in Computer Science 1320, Springer, 1997, pp 111-125 (for extended version see [63a])  (with R de Prisco and N. Lynch). Abstract, Acrobat. See Paxos.

61.    IP lookup using multiway and multicolumn binary search. IEEE/ACM Transactions on Networking, 7, 3 (June 1999), pp 324-334 (also in Infocom 98, April 1998) (with V. Srinivasan and G. Varghese). Abstract, Postscript, Acrobat.

62.    SPKI Certificate Theory. Internet RFC 2693, http://www.cis.ohio-state.edu/htbin/rfc/rfc2693.html (Sept. 1999) (with C. Ellison, B. Frantz, B. Lampson, R. Rivest, B. Thomas, T. Ylonen). Abstract, Postscript, Acrobat, Web page, Word. See SDSI.

63.    Information systems security. In Realizing the Potential of C4I: Fundamental Challenges, National Academy Press, 1999 (with T. Berson and R. Kemmerer). Abstract, Postscript, Acrobat, Web page, Word.

63a. Revisiting the Paxos Algorithm. Theoretical Computer Science 243, 1-2 (July 2000), pp 35-91 (for shorter version see [60]) (with R. de Prisco and N. Lynch). Abstract, Acrobat. See Paxos.

64.    Computer security in the real world. Proc. Annual Computer Security Applications Conference, 2000. Abstract, , Acrobat, Web page, Word. For a revised and condensed version, see [69].

65.    The ABCD’s of Paxos. Invited talk at Principles of Distributed Computing, August 2001. Abstract, Acrobat, Web page, Word. See Paxos.

66.    Getting computers to understand. J. ACM 50, 1 (Jan. 2003), pp 70-72. Abstract, Acrobat, Web page, Word.

67.    Computing meets the physical world. The Bridge, 33, 1 (Spring 2003), National Academy of Engineering, pp 4-7. Abstract, Acrobat, Web page, Word.

68.    A trusted open platform. IEEE Computer 36, 7 (July 2003), pp 55-62 (with P. England, J. Manferdelli, M. Peinado, and B. Willman). Abstract, Acrobat. See Palladium.

69.    Computer security in the real world. IEEE Computer 37, 6 (June 2004), pp 37-46. Abstract, Acrobat, Acrobat as published, Web page, Word. For an earlier, expanded version, see [64].

70.    Software Components: Only the Giants Survive. In Computer Systems: Theory, Technology, and Applications, K. Sparck-Jones and A. Herbert (editors), Springer, 2004, pp 137-146. Abstract, Acrobat, Web page, Word.

71.    A conceptual authorization model for web services. In Computer Systems: Theory, Technology, and Applications, K. Spark-Jones and A. Herbert (editors), Springer, 2004, pp 165-172 (with P. Leach et al.). Abstract, Acrobat, Web page, Word. See Web services security.

72.    Getting Up to Speed: The Future of Supercomputing, National Academy Press, 2004 (contributor). Abstract, Acrobat.

73.    The ongoing computer revolution. The Bridge, 34, 2 (Summer 2004), National Academy of Engineering, pp 39-40. Abstract, Acrobat, Acrobat as published, Web page, Word. See Alto.

74.    Security, lectures at TCS Excellence in Computer Sciences Week, Pune, India, 2005. Abstract, Acrobat, Word

75.    Practical principles for computer security, In Software System Reliability and Security, NATO Security through Science Series D: Information and Communication Security, vol. 9, IOS Press, 2007, pp 151-195. Abstract, Acrobat, Web page, Word

76.    Principles for computer system design, Turing Award lecture, 1993. Abstract, Acrobat, Word

77.    Lazy and speculative execution, Proc. 13th ACM Sigplan International Conference on Functional Programming (ICFP ’08), Sigplan Notices 43, 9 (Sept. 2008), pp 1-2. Abstract, Acrobat, Powerpoint

78.    Viewpoint: Usable  security—How to get it, Comm. ACM 52, 11 (Nov. 2009), pp 25-27. Abstract, Acrobat, Word

79.    Declarative programming: The light at the end of the tunnel, in Points of View:A tribute to Alan Kay, Viewpoints Research Institute, Glendale CA, 2010, pp 151-163. Abstract, Acrobat, Web page, Word

80.    Technical perspective: Making untrusted code useful, Comm. ACM 54, 11 (Nov. 2011), p 92. Abstract, Acrobat, Web page, Word.

81.    What Computers Do: Model, Connect, Engage, 9th Conf.  Theory and Applications of Models of Computation (TAMC), LNCS 7287 (May 2012),  pp. 23-26. Abstract, Acrobat, Web page, Word.

82.    Textual features for programming by example. CoRR abs/1209.3811 (Sept, 2012) (with Aditya Menon, Omer Tamuz, Sumit Gulwani, and Adam Kalai). Abstract, Acrobat. Early version of 83.

83.    A machine learning framework for programming by example, Proc. 30th International Conference on Machine Learning (ICML), JMLR Workshop and Conference Proceedings 28, 1, (June 2013), pp 187-195 (with Aditya Menon, Omer Tamuz, Sumit Gulwani, and Adam Kalai). Abstract, Acrobat.

84.    A colorful approach to text processing by example, Proc. 26th ACM Symposium on User Interface Software and Technology (UIST), Oct 2013, pp 495-504 (with Kuat Yessenov, Shubham Tulsiani, Aditya Menon, Robert C. Miller, Sumit Gulwani, and Adam Kalai ). Abstract, Acrobat, Web page, Word.

85.    Bulk Collection of Signals Intelligence: Technical Options, National Academies Press, 2015 (by the Committee on Responding to Section 5(d) of Presidential Policy Directive 28, Computer Science and Telecommunications Board, National Research Council). Abstract, Acrobat.

86.    Verifying concurrent software using movers in CSPEC, 13th USENIX Symposium on Operating Systems Design and Implementation (OSDI 2018), Oct. 2018, pp 306-322. (with Tej Chajed, M. Frans Kaashoek, and Nickolai Zeldovich). Abstract, Acrobat

87.    Hints and principles for computer system design, September 2019. Abstract, Acrobat

(root)