By Rob Knies
March 5, 2009 3:12 PM PT
The Hall of Fame Award bestowed by the Association for Computing Machinery’s Special Interest Group on Operating Systems (SIGOPS) was instituted in 2005 to recognize the most influential papers on operating systems to appear in peer-reviewed literature.
To be nominated for the Hall of Fame honor, papers must have stood the test of time. At least a decade must have passed before a paper can be considered.
Since the award was established, 15 have been presented, and 40 percent of those included at least one author who currently works at Microsoft Research.
Of the papers named to the Hall in 2008, two boast authorship by computer scientists now at Microsoft Research:
For Rashid, senior vice president of Microsoft Research, the SIGOPS Hall of Fame Award comes as further recognition of the seminal work he and his colleagues at the Department of Computer Science at Carnegie Mellon University performed on the Mach operating system in the 1980s. The honored paper was first published in October 1987 in Proceedings of the Second Architectural Support for Programming Languages and Operating Systems.
The paper traces the design and implementation of virtual-memory management in Mach, which has been influential in the design of modern operating systems and remains at the core of several commercial systems. The paper discusses what was learned in the process of deploying the system to a number of distinct computer architectures. The technique separated software memory management from hardware support and enabled additional examination of hardware memory management.
Today, the paper written by Rashid and colleagues almost 22 years ago has become a standard text in the computer-science curricula at many of the foremost universities around the world.
The second honored paper is noteworthy in that each of the authors has played a key role in shaping the research agenda of Microsoft Research. The fourth author of the paper, Needham, who died in 2003, founded Microsoft Research Cambridge in 1997.
“The paper describes the rationale, design, and early operational experience with a system called Grapevine,” Schroeder recalls. “The title references the spread of information by word of mouth. Information received this way is said to be ‘heard on the grapevine.’ The Grapevine system was distributed over many servers interconnected by an internet. It delivered e-mail by passing it from one server to another, so it was a sort of electronic Grapevine.”
To comprehend the magnitude of the achievement, consider this: The Grapevine paper was published in December 1981, in Proceedings of the Eighth ACM Symposium on Operating System Principles. To most of us, in 1981, “e-mail” was a typo.
As Birrell notes, before Grapevine, in the “x@y” structure of e-mail addresses, “y” denoted the name of a particular computer. Grapevine enabled “y” to be a virtual name, looked up in a distributed name service.
“In addition to delivering e-mail,” Schroeder says, “it also had an active-directory-like function to maintain a database of user names, mailbox locations, and distribution lists. The system contained some of the first examples of data distribution, replication, and consistency mechanisms—and failover for functions to other servers in the event of a server crash.
“Such ideas are widely used today, and there are many platforms available that incorporate these facilities. The designer of a distributed application these days simply focuses on the application functionality. But in Grapevine, we had to build all this from the ground up, including designing the protocols used for communicating actions and data from one server to another. Part of the reason that the system was successful and influential, I think, was that in addition to being computer scientists, we were good engineers. We incorporated many schemes, such as caching, that made the system perform well and robustly. It put a stake in the ground that demonstrated that practical systems could be built this way.”
Indeed, the Grapevine concept of Internet-connected computer services implementing a coherent service—devised while Birrell, Levin, and Schroeder were working at Xerox’s Palo Alto Research Center (PARC) and Needham was associated with the University of Cambridge Computer Lab—remains relevant more than 27 years after they published the paper.
“Grapevine’s naming ideas were a direct precursor of today’s Domain Name Service, which is the glue that holds the Internet together,” says Birrell, who won a Hall of Fame citation for the second consecutive year. “It was a fun system to build, and it had a substantial impact on how people built—and still build—client-server distributed systems. The paper is still used in graduate courses as a good starting point in understanding the principles of building distributed systems.”
Schroeder notes the relative paucity of resources with which the team had to work in constructing Grapevine.
“Recall that we didn’t have much computing power, storage, or network bandwidth available,” he says. “The Alto servers we used ran at about 3 Mhz and had 128K of memory and a 3-megabyte disk. The network, a precursor to the Internet, was carried on 10- to 56-Kbps physical links. Replacing these server computers with today’s cellphones and the data links with the 3G data network would provide a vast increase in hardware capability. Nevertheless, a five-server system eventually provided production e-mail service to several thousand users.”
For Levin, the Grapevine work summons memories of inspired brainstorming.
“My fondest recollection of the Grapevine project,” he says, “was an intensive week of meetings when Roger Needham was visiting PARC. We took over a small conference room at the end of the building, far from the rest of the lab, and essentially closeted ourselves there for the entire week, designing the system on a whiteboard. At the end of it, Roger went back to Cambridge, and the rest of us set about building the system, pretty much the way it was designed.
“It was a very stimulating and productive week—the best way to do research, I think—and certainly consistent with Roger’s maxim to ‘do research with a shovel, not a tweezers.’ “
Nominations for the SIGOPS Hall of Fame Award are made by SIGOPS members, and winners are chosen by the Hall of Fame Award Committee—consisting of program chairs from each of the four most recent ACM Symposiums on Operating Systems Principles and a co-chair from each of the four most recent USENIX Symposiums on Operating System Design and Implementation (OSDI). Papers nominated are selected for the award based on their long-term impact and the quality of the research described.
Winners receive a plaque naming the paper, its authors, the conference or journal in which the paper appeared, and the conference during which the award was made. The 2008 winners were announced in San Diego on Dec. 9 during OSDI 2008.
Other papers inducted in 2008:
Microsoft Research personnel garnered three of the five awards presented in 2007:
Butler Lampson, a Microsoft Research technical fellow based in Cambridge, Mass., was one of four inaugural inductees into the SIGOPS Hall of Fame, honored for his Hints for Computer Science Design, published in the Proceedings of the Ninth ACM Symposium on Operating Systems Principles in October 1983.