Butler W Lampson

Butler Lampson was born in Washington DC and educated at The Lawrenceville School, an elite boarding school 6 miles from Princeton New Jersey.

Lampson’s first computer was an underutilized IBM 650 at Princeton, which an enterprising high school classmate found and got permission to use while it was idle. It had a drum memory with 2000 words of ten decimal digits, and the only I/O aside from the console was a card reader/punch, controlled partly by the computer and partly by a plug board.

As an undergraduate at Harvard, Lampson learned the APL programming language from Ken Iverson, who spent a year on sabbatical there. At that time there was no implementation of the language, and Ken didn’t want one because he was sure that it would make compromises that would wreck the language. While still an undergraduate Lampson also programmed a PDP-1 to analyze spark chamber photographs from the Cambridge Electron Accelerator and wrote a display editor for the PDP-1’s one-point-at-a-time display.

Lampson went to the University of California at Berkeley in the fall of 1964 as a graduate student in physics. At the Fall Joint Computer Conference in San Francisco that year he ran across Steve Russell from MIT, who told him about the Genie project hidden behind an unmarked door in Cory Hall. There he met Peter Deutsch and Mel Pirtle, the Principal Investigator, and was quickly seduced away from physics to study computers.

The Genie project modified a Scientific Data Systems SDS 930 minicomputer to create the first time-sharing system with character-by-character interaction. Later SDS marketed it as the SDS 940, the first commercially available general purpose time-sharing system. Lampson wrote parts of the operating system and several programming languages, notably Cal, an interactive language for numerical computation derived from Cliff Shaw’s Joss, and the QSPL system programming language done with Peter Deutsch.

At Berkeley he also designed the Cal time-sharing system for a CDC 6400 in the computer center, together with Jim Gray, Charles Simonyi, Howard Sturgis and Bruce Lindsay, who all went on to later fame. This was the first capability-based system to have a real user community. It pioneered the ideas of shadow pages and redo logs, but also taught us that capabilities are not a good basis for long-term security.

The Genie project researchers couldn’t figure out how to build the much more grandiose second system at Berkeley, so in 1969 they started Berkeley Computer Corporation (BCC) to do it. After two years it burned through $4,000,000 and built just one working system before folding. Lampson designed and coded most of the microcoded parts of the operating system and worked on the SPL system programming language. Around this time he also devised the access matrix model for computer security, unifying the ideas of capabilities and access control lists.

Luckily, as BCC was ending the Xerox Palo Alto Research Center (PARC) was getting started, and Bob Taylor found the core of his Computer Science Laboratory (CSL) there: Chuck Thacker, Peter Deutsch, Charles Simonyi, Jim Mitchell and Butler Lampson. The charter of CSL and its System Science Laboratory partner was to invent and deploy the office of the future. No one knew what that meant, but it provided a lot of scope and just the right amount of direction. The standard research machine at the time was the DEC PDP-10 with its Tenex operating system (descended from the 940), but since Xerox had just bought DEC’s main competitor SDS, CSL had to home-build a PDP-10 from scratch in 1971.

Two years later the same technology and tools went into the Alto, the first recognizable modern personal computer. It had a 600 x 800 display (black and white with only one bit per pixel, but that still used half the machine’s 128 KB memory), a hard disk, an Ethernet local area network, and a laser printer. Lampson designed some of the machine, wrote the operating system, and with Ron Rider designed the electronics and software for the prototype laser printer that Gary Starkweather built, which was later adapted to make the Xerox 9700 laser printer. The Alto software included Bravo, the first what-you-see-is-what-you-get text editor, designed by Lampson and Charles Simonyi and coded by Charles’ software factory. Bravo eventually led to the development of Microsoft Word. Lampson and Alan Kay designed the byte code machine language scheme used for Smalltalk, Mesa, and later versions of Alto software that were widespread in universities, the White House, and several other field test sites.

Other significant work at PARC included the first widely published description of using information flow control for security, the invention (with Howard Sturgis) of two-phase commit for distributed transactions, and the technique of scrubbing disk storage. Lampson also designed much of the system programming language Mesa, especially the module system and the process mechanism, which later was the basis for most modern thread systems. Mesa modules led to early work with Eric Schmidt on systems for building large systems. Another spinoff was Euclid, the first language specifically designed to be amenable to program verification. Mesa later led to Cedar, an only partially successful attempt to combine the virtues of Mesa and Lisp; Lampson did some of the design and wrote a comprehensive description of the language. All of this hardware and software work led to him write a paper on hints for computer system design that has been quite influential.

Later at PARC Lampson led the design of the Dorado, a personal computer that was much more powerful than the Alto, and of the Wildflower, a less expensive 1979 version of the Alto. The Wildflower was the basis for the hardware of the Star, Xerox’s office automation system, built by a development group spun out of PARC led by Dave Liddle. Lampson also designed the electronics for the Dover, a much cheaper laser printer that was widely used within Xerox and in several universities.

With Paul Rovner and others, Lampson designed Modula 2+, an extension of Niklaus Wirth’s Modula 2, which provides a safe subset, automatic storage deallocation, runtime types, exceptions, and concurrency. The language has been used to write more than a million lines of code. Lampson worked with Rod Burstall on languages for describing how a system is built from its component modules. After several false starts this work eventually led to the Vesta system-building system, created by Roy Levin, Yuan Yu and others, and currently remains the state of the art for efficient and reliable construction of large software systems with many developers and many versions.

By 1983 the influential group at PARC was beginning to break up, and many of the senior individuals, including Lampson , went to work for the Systems Research Center (SRC) of Digital Equipment Corporation (DEC). By this time Lampson was living in Philadelphia, where his wife Lois was teaching at the University of Pennsylvania. He turned his interests to the developing e-mail systems. Earlier work by Mike Schroeder, Roger Needham, Andrew Birrell and others on the Grapevine distributed e-mail system led to a design and a formal specification for a decentralized, fault-tolerant distributed name service; this later came to be known as “eventual consistency” and was widely used in highly available systems. Thinking about how to make e-mail secure led to the first scheme for distributed authentication. Another major SRC project that Lampson started was two high-speed switched local area networks with an unprecedented combination of speed, availability, and security.

The work on authentication led to a series of papers that laid the foundations of security for distributed systems. Some of this work was done with Morrie Gasser, Andy Goldstein and Charlie Kaufman for the Digital Distributed Systems Security Architecture, which unfortunately was never implemented. Work at SRC with Mike Burrows, Martin Abadi and Ted Wobber introduced the idea of describing trust in terms of principals “speaking for” other principals, and extended the notion of principal from just users to keys, groups, and programs. It was more formal, and it did have an implementation. It evolved further at MIT in the SDSI/SPKI design done with Ron Rivest and Carl Ellison, and in the Microsoft Palladium scheme, done with Paul England, for platforms that can prove to a third party what software they are running. An attempt at a comprehensive security architecture with Paul Leach and others has been implemented only in fragments. Lampson’s later work on security deals with the economic factors that cause deployed security to be much worse than the best we know how to do technically.

In 1987 Lampson moved to Cambridge Massachusetts because Lois had joined the faculty of the Harvard Medical School. He continued to work for DEC, and also became an Adjunct Professor in the Electrical Engineering and Computer Science Department at MIT. There he worked with Nancy Lynch on formal specifications and proof for TCP connection establishment (also known as at-most-once messages) and for Leslie Lamport’s Paxos protocol. He worked to persuade the systems community that Paxos and Leslie’s replicated state machines are the right way to build fault-tolerant systems, and after about 15 years it has been widely adopted. He also became interested in how computing evolves, studying how software components have failed and succeeded. With Dave Tennenhouse he analyzed the combination of technical and economic factors that drive or impede the evolution of telecommunications. The wave of interest in Grand Challenges for computing led to proposals for some very concrete grand challenges: reducing highway traffic deaths to zero with self-driving cars, and getting a computer to write a program from its specification as well as a team of programmers could do it.

In 1995 Lampson joined Microsoft Research, where he worked on tablet PC software, security, and end-user programming of rich applications. He has served on the Computer Science and Telecommunications Board and on National Academy panels, studying computer security and directing funding for computing research, military command and control, and supercomputing. His work with the Academy gave rise to the infamous tiretracks diagram that explains how government and industry support of basic research in computing has led to dozens of multi-billion-dollar industries.

Butler Lampson has had a very active career. He has made contributions to computer architecture, local area networks, raster printers, page description languages, operating systems, remote procedure call, programming languages and their semantics, programming-in-the-large, fault-tolerant computing, transaction processing, computer security, WYSIWYG editors, and tablet computers. He was a co-designers of many systems, including the SDS 940 time-sharing system, the Alto personal distributed computing system, the Xerox 9700 laser printer, two-phase commit protocols, the Autonet LAN, the SDSI/SPKI system for network security, the Microsoft Tablet PC software, the Microsoft Palladium high-assurance stack, and several programming languages.

Author: Roy Levin