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)