Systems

Butler W. Lampson
(root)

In addition to the formal publications listed here, I have done a large amount of system design and implementation. Many of these systems are described in papers, but much of the work is embodied in the functioning result rather than the paper, Also, the work is often documented in papers written by other participants in the design, or in patents. The numbers in brackets are references to the list of publications.

Hardware

MAXC (1971-3): I designed and implemented the micro-programmed processor for a machine which emulated a PDP-10 [E. R. Fiala, The MAXC systems, IEEE Computer 11, 5 (May 1978), pp 57-67]. It ran somewhat faster than a KA-10, and much more reliably, more than once attaining an interval of 2000 hours between crashes while running the Tenex time-sharing system. Two of these machines were built; each operated for about 9 years before being decommissioned. See Micro.

Video terminal system (1971-72): With Roger Bates (who implemented it) I designed a multi-font high-resolution character generator for a 1023-line raster-scan display system [US patents 3,911,419 and 3,911,420]. About 50 were built and used at PARC.

Alto (1972-75): With Chuck Thacker (the principal designer), Ed McCreight and Bob Metcalfe, I worked on the design of the Alto personal computer [25]. About two thousand of these machines were built for use within Xerox and limited sale. The Alto was the prototype for the workstations of the mid 1980s and the windowed personal computers of the late 1980s. Here are the original memo describing the Alto project [38a], the design notes for the Alto OS [38b] and the 1976 Alto Userís Handbook [15a]. The latter is the standard Alto documentation for non-programmers.

Ethernet (1973-75): I worked with Bob Metcalfe (the principal designer) and others on the design of the Ethernet, a high-bandwidth local network [Boggs and Metcalfe, Ethernet: Distributed packet switching for local computer networks. Comm. ACM 19, 7 (Jul. 1976), pp 395-407; US patent 4,063,220].

Ears (1973-75): With Ron Rider (who implemented it) I designed a high-performance character generator for a one-page-per-second, 500 dpi raster printing system [US patent 4,079,458]. A modification of this design is used in the Xerox 9700 computer printer; I designed the basic digital architecture of the 9700.

Mesa architecture (1975-78): With Chuck Geschke and later John Wick, I designed the byte-coded instruction set for the Mesa system implementation language [Johnsson et al., An overview of the Mesa processor architecture. ACM Sigplan Notices 7, 4 (Apr. 1982), pp 20-29]. See Mesa, Mesa processes and monitors.

Orbit (1975): With Severo Ornstein and Bob Sproull (who implemented it), I designed this highly flexible, low cost scan converter which allows an Alto to drive a 384 dpi, 1 page/sec raster printer [US patent 4,203,154]. About 50 were built and used within Xerox, in some universities, and in a few test marketing sites.

Dorado (1976-79): I had principal design responsibility for this fairly powerful new personal computer. For non-numeric computation it has about the power of a 370-168, but it is implemented in about 2500 DIPS and packaged to fit (rather uncomfortably) in an office. I also did the detailed design and implementation of the cache memory system [24, 29, 34]. About 75 of these machines were built, though they were not put in offices.

Wildflower (1978): I designed a fast and economical processor for a high-performance office workstation. It includes a micro-programmed engine suitable for emulating byte-coded instruction sets for Mesa and Lisp, as well as input/output controllers for high-resolution display, hard disk and Ethernet. A modification of this design became the Dandelion processor, used in many Xerox 8000 series products.

Dragon (1980-83): With Chuck Thacker (the principal designer) and Bob Sproull, I worked on the pipeline, instruction set, procedure call mechanism and memory architecture of this high-speed LSI multi-processor [Monier and Sindhu, The architecture of the Dragon. Proc. 30th IEEE Int. Conf., 1985, pp 118-121]. A much evolved version became the basis for Sunís multiprocessors in 1993.

Stable storage (1982-83): With Severo Ornstein (who implemented it) I designed a very reliable device which provides low-latency stable storage to a computer system, to speed up transactional data storage systems and high-reliability distributed systems.

Autonet (1987-89): With Mike Schroeder, Roger Needham, Chuck Thacker and others, I designed a high-speed mesh network with 100 Mbit/sec link data rates, 1-2 usec switch transit times, and 150 ms reconfiguration time after a failure, as well as adapters that can deliver these data rates to host computer memory [M. Schroeder et al., Autonet: A high-speed, self-configuring local area network using point-to-point links, IEEE J. Selected Areas in Communications, 9, 8 (Oct. 1991), pp 1318-1335].

Ethernet encryption (1988-90): With Bill Hawe, Pini Lozowick, and others, I designed an Ethernet bridge that can encrypt and decrypt packets flowing through it. The bridge has been implemented in a single chip with one auxiliary RAM (U.S. patents 5,161,193 and 5,235,644).

AN2 (1990-93) With Chuck Thacker, Mike Schroeder, and others, I designed an Asynchronous Transfer Mode switch and host adapter with 155 Mbit and 1 Gbit links, constant and variable bit rate traffic, flow controlled circuits, and very fast circuit setup [T. Anderson et al., High-speed switch scheduling for local-area networks. ACM Trans. Computer Systems 11, 4 (Nov 1993), pp 319-352].

Virtual book (1994-5). With Mark Hayter, Jay Kistler, and Chuck Thacker, I designed a hand-held device (sometimes called Lectrice) meant to be a comfortable alternative to paper for reading documents that are formatted to print on 8.5 x 11 or smaller paper. Andrew Birrell wrote the Lectern software [D. Chaiken et al., The Virtual Book, Technical Report SRC-RR-157, Digital Systems Research Center, November 1998].

Palladium (1997-2005): With Paul England, John DeTreville, Bryan Willman, John Manferdelli and others, I designed the architecture for secure program authentication and execution of a high-assurance OS stack built on hardware attestation and protection of software on a machine that is simultaneously running an arbitrary operating system [68]. [U.S. patents 6,327,652 and 6,330,670].

Operating systems

SDS 940 (1964-67): With Mel Pirtle, Wayne Lichtenberger and Peter Deutsch, I designed and implemented this system at Berkeley [2]. It was subsequently marketed by SDS as the first commercial time-sharing which allowed user programming in machine language. About 60 machines were sold, and they were the initial hardware base for many time-sharing service companies, including Tymshare. This system was copied directly in the design of the Tenex system for the PDP-10, except for the memory management. Tenex later evolved into TOPS-20, the standard operating system for the DecSystem 20. Some of the 940 system's ideas are also embodied in Unix, whose designer Ken Thompson worked on the 940 while at Berkeley.

Cal TSS (1968-71): This was the first working capability based operating system, and for many years the only one done for a large computer [7, 10a, 15]. With Howard Sturgis and others I did the design, though I did not write any code. Many of the ideas in the Hydra system for C.mmp and its descendants are identical to those in Cal, though usually derived independently several years later. This system ran successfully at Berkeley for about a year, and then was abandoned for a combination of technical and political reasons.

Berkeley Computer Corporation (1969-71): With the SDS 940 group from Berkeley, I founded a computer company to make large time-sharing systems. I did the overall design of the operating system, including the functions of the three specialized micro-coded processors which do most of the overhead work [6, 6a]. I also implemented the scheduling micro-processor and parts of the terminal-handling micro-processor [19]. One machine was built and ran successfully at the University of Hawaii for a number of years, though the company was a commercial failure. See SPL.

Alto OS (1973-76): I designed (and, with Gene McDaniel and Bob Sproull, implemented) a single-user operating system, based on Stoy and Strachey's OS6, for the Alto personal computer built at PARC [14, 15a, 22, 38, 38b]. The system is written in BCPL and was used in about two thousand installations.

Juniper (1974-78): With Howard Sturgis and others, I designed a system for reliable distributed storage of data [27; Sturgis et al., Issues in the design and use of a distributed file system. ACM Operating Systems Rev. 4, 3 (Jul. 1980), pp 55-69; Mitchell and Dion, A comparison of two network-based file systems, Comm. ACM 25, 4 (Apr. 1982), pp 233-245].

Mesa monitors and processes (1978): With Dave Redell and others, I designed the concurrency facilities for Mesa [23]. These have been used in a large number of concurrent and distributed systems built in Mesa and Cedar. The Posix standard for threads is a direct descendant. See Mesa.

Cedar nucleus (1983): With Roy Levin and Andrew Birrell (who implemented it), I planned the overall architecture for the Cedar nucleus. This system provides the basic operating facilities for the Cedar programming environment [Swinehart et al., A structural view of the Cedar programming environment. ACM Trans. Programming Languages and Systems 8, 4 (Oct. 1986), 419-490]. See Cedar.

Name service (1985-86): With Andrew Birrell, Roger Needham and Mike Schroeder, I designed a successor to the Grapevine name service which is intended to be usable in a world-wide network involving billions of entities [36]. We designed a new authentication scheme for this service, which formally addresses the problems of global mistrust [37]. The OSF/DCE name service is derived from this design.

Fast remote procedure call (1987-88): With Mike Schroeder and Mike Burrows (who did the implementation) I designed a high performance implementation of remote procedure call which can do a complete null call from a user process over the Ethernet in 2.7 ms on a multiprocessor with 4 1 MIPS processors [M. Schroeder and M. Burrows, Performance of Firefly RPC, ACM Trans. Computer Systems 8, 1 (Feb. 1990), pp 1-17].

Distributed systems security (1988-89): With Charlie Kaufman, Morrie Gasser and Andy Goldstein, I designed a security architecture for distributed systems which provides authentication of users and systems without global trust, secure bootstrapping and loading of programs, and authenticated delegation of authority from one system to another [41, 42, 44, 46].

Taos authentication (1990-91): With Martin Abadi, Mike Burrows, and Ted Wobber, I designed a theory of authentication derived from the security architecture [44, 46]. The theory underlies the implementation of security in the Taos operating system for the Firefly [51].

Compressed file system (1992): With Mike Burrows, Chuck Jerian, and Tim Mann (who did the implementation) I designed an extension to the Sprite log structured file system that uses compression to store more data on the disk and speed up transfers [45].

Tablet PC (1999-2002): With Chuck Thacker, Bert Keely, Alex Loeb and others, I designed the architecture for extending Windows to run on a tablet PC, using a pen for input instead of a keyboard and mouse. This system has been shipping since November 2002.

Programming languages and compilers

Cal (1965-68): This language was a derivative of Joss, but used statement-level incremental compilation. I designed it and did all the implementation. It was widely used on the SDS 940, and many of its techniques were adopted by Tymshare for their interactive SuperBasic system.

Snobol (1965-69): I designed two Snobol systems for the SDS 940, one for Snobol 3 (which I implemented), and the other for Snobol 4 without user data types (implemented by two students). Both were interactive and received considerable use at various 940 installations. Snobol 4 had a large (slow) workspace and did incremental compilation at the statement level.

QSPL (1967-68): Peter Deutsch and I designed and implemented this system implementation language, which is contemporary and comparable with BCPL; it has better data structuring facilities and worse control structures. It was used for a great deal of systems programming on the SDS 940 at a number of research institutions.

SPL (1969-71): Deutsch and I also designed this implementation language and programming system; it included an editor and source-language debugger. I implemented the parser, and four other people worked on the system. It was used to implement all the system software at Berkeley Computer Corporation, including the entire operating system, which had no machine language. This was rather unusual at the time.

Micro (1971-72): Together with Peter Deutsch (who implemented it) and Ed Fiala, I designed this macro-assembler for microprogrammed processors [E. R. Fiala, The MAXC systems, IEEE Computer 11, 5 (May 1978), pp 57-67]. It has a high degree of machine independence and has been used to make widely-used microassemblers for three very different machines.

Mesa (1972-79): With Jim Mitchell, Chuck Geschke and Ed Satterthwaite, I designed this programming language [13, 23; Geschke et al., Early experience with Mesa, Comm. ACM 20, 8 (Aug. 1977), pp 540-553; Mitchell et al., Mesa Language Manual, Technical Report CSL-79-3, Xerox PARC, 1979 (23a)]. It is based on Pascal, but has unified facilities for coroutines and parallel processes, and for specifying interfaces among many modules in a large system. I designed much of this.

Euclid (1976-79): With Horning, Mitchell, London and Popek I designed this language for writing verifiable system software [17, 18, 20]. It has been implemented at the University of Toronto, and has had several descendants (Concurrent Euclid, Turing, and less directly, Ada).

Cedar (1979-82): With Jim Horning, Paul Rovner and others, I designed the extensions which produced Cedar by adding a safe subset, automatic storage deallocation, and runtime types to Mesa. I wrote a definition of Cedar semantics in terms of a much simpler kernel language, and a language manual [32a]. See Cedar nucleus.

Modula 2+ (1984-86): With Paul Rovner and others, I designed extensions to Modula 2 which provide a safe subset, automatic storage deallocation, runtime types, exceptions, and concurrency. The language has been used at SRC and several universities to write more than a million lines of code [P. Rovner, Extending Modula 2 to build large, integrated systems. IEEE Software 3, 6 (Nov. 1986)].

Other

QED (1965-66): Peter Deutsch and I designed this editor for the SDS 940, which he and Dana Angluin implemented [4]. It is the ancestor of Ken Thompson's family of qed and ed editors for CTSS, Multics and Unix.

Bravo (1973-79): Charles Simonyi and I designed this display-oriented text editor and formatter, which he and others implemented. It allows what-you-see-is-what-you-get editing of nearly publication-quality documents with multiple fonts, leading, justification, etc., displaying them continuously on the screen in their final form. Later versions had a style sheet facility. Bravo was the first system with these capabilities. It was very widely used within Xerox as well as at a number of customer sites. The capabilities and implementation techniques in Bravo were a major influence on the design and implementation of the Xerox Star product and especially of Microsoft Word [B. Lampson, Bravo Manual. In Alto User's Handbook, Xerox PARC, Oct. 1976, pp 27-58 (15a)].

Interpress (1980-82): With Bob Sproull, I designed this standard for describing a document to be electronically printed. It includes a programming language with careful control of side-effects, so that portions of several Interpress documents can be easily assembled into another document. It is implemented in the Xerox computer printer product line, and was a major influence on Adobe's Postscript language [Interpress Electronic Printing Standard, version 3.0, XNSS 048601, Xerox Corporation, Jan. 1986].

Interscript (1982-83): With Bob Ayers, Jim Horning and Jim Mitchell, I designed this standard for describing editable documents. The main innovations are semantics which allow editing of parts of the document by an editor which doesn't understand other parts (e.g., captions within figures), provision for what-you-see-is-what-you-get editing, a fully integrated mechanism for style sheets, and a layout model based on regular expressions.

System modeling (1978-83): I designed this scheme for describing the assembly of modules into a complete system, which Eric Schmidt and Ed Satterthwaite implemented part [30, 31]. By mid-1983, it had been used for development of about 70,000 lines of Cedar code. See Vesta, Vesta 2.

Vesta (1988-91): With Roy Levin, Chris Hanna, and others, I designed this second generation implementation of system modeling. It has been used to develop about 1.5 million lines of Modula 2+ code at SRC [R. Levin and P. McJones, The Vesta approach to precise configuration of large software systems. SRC Research Report 105, June 1993]. See System modeling, Vesta 2.

Vesta 2 (1993-95): With Roy Levin, Jim Horning, Alan Heydon, and Tim Mann, I designed this third generation implementation of system modeling. It has much better modularity for tools, a language that can be used to program tool interfaces, server-based caching of derived objects that greatly improves performance [56], and a multi-site repository. It is highly portable and should scale to systems with a million components [Allan Heydon, Roy Levin, Timothy Mann, and Yuan Yu, Software Configuration Management Using Vesta, Springer, 2006]. See System modeling, Vesta.

SDSI/SPKI (1995- ): With Ron Rivest and Carl Ellison, I designed this Simple Distributed Security Infrastructure for distributing public keys on the Internet and easily establishing a wide variety of access control schemes. It has been partially implemented by Wei Dai at Microsoft and by various other people [59, 62].

Paxos (1990-2001): I worked to understand and popularize Leslie Lamportís Paxos algorithm for distributed consensus and the Byzantine variant designed by Miguel Castro and Barbara Liskov [63a, 65].

Web Services Security (2000-2002). With Chris Kaler, John Shewchuck, and others I designed an architecture for authentication and authorization in heterogeneous distributed systems. This work builds on DSSA, Taos authentication, and SDSI/SPKI work described above [71].

National Academies reports (1990-2005): I served on panels of the National Academies that studied computer security [43], the nationís computing research program in the context of the High Performance Computing and Communications Initiative [55], the military command and control system [63], and supercomputing [72].

(root)