MIT Reports to the President 1994-95

Laboratory for Computer Science

The MIT Laboratory for Computer Science (LCS) is an interdepartmental laboratory whose principal goal is research in information technology.

Founded as Project MAC in 1963, the Laboratory developed one of the world's earliest time-shared computer systems. This early research on the Compatible Time Sharing System (CTSS) and its successor, MULTICS, made possible in the 60s and early 70s innovative developments such as the writing of operating systems in high-level programming languages, virtual memory, tree directories, on-line scheduling algorithms, line and page editors, secure operating systems, concepts and techniques for access control, computer-aided design, and two of the earliest computer games, space wars and computer chess.

These early developments laid the foundation for the Laboratory's work in the 1970s on knowledge based systems -- for example, the MACSYMA program for symbolic mathematics -- natural language understanding, and (with BBN) the development and use of packet networks via the ARPANET. During this same period, the Laboratory developed theoretical results in complexity theory and linked cryptography to computer science through concepts and algorithms for public encryption. In the late 1970s, Project MAC, renamed as the Laboratory for Computer Science, embarked on research in clinical decision making, public cryptography, distributed systems and languages and parallel systems. These led to the RSA encryption algorithm, data abstractions, the CLU and ARGUS distributed systems, the dataflow principle and associated languages and architectures of parallel systems, local area ring networks, program specification and workstation development, where the Laboratory contributed the earliest UNIX ports and compilers, and the Nubus architecture, now used in commercial computers, such as Apple's Macintosh. This research also led to the X Window System, a computer intercommunication and user interface system, developed together with Project Athena and widely used by industry.

The Laboratory's current research falls into four principal categories: Information Infrastructure and Distributed Systems; Human Interaction/Intelligent Systems; Computationally Intense Systems; and Theory. The principal goals of these four categories are as follows:

In the areas of Information Infrastructure and Distributed Systems, we wish to understand principles and pursue technologies for the architecture and use of highly scalable information infrastructures from the organizational to the international level. Transactions among such distributed systems are likely to involve beyond conventional electronic mail and file transfer, the purchase and sale of information and information services (electronic commerce), electronic shopping, healthcare, education, groupwork across space and time, and so on. This research is expected to have a broad impact on future systems because virtually every machine will be connected to some information infrastructure.

In the Human Interaction/Intelligent Systems area, our technical goals are to understand and construct programs and machines that have greater and more useful sensory and cognitive capabilities so that they may communicate with one another and with people toward useful ends. Examples include the use of advanced graphics and interactive spoken dialogue between people and machines. This area also includes programs that reason about clinical issues and help in clinical decision making and healthcare.

In the Computationally Intense Systems area, we strive to harness the power and economy of numerous processors working on the same task. Research in the area involves the analysis and construction of various parallel hardware architectures, programming languages and operating systems that yield, over a broad set of applications, cost-performance improvements of several orders of magnitude relative to single processors. We are also carrying out research on the uses of computationally intense systems in several application areas for the purpose of improving architectures and programs that we develop, based on their utility.

Taken together, these three thrusts in infrastructure, human interaction/intelligent systems and computationally intense systems define the Laboratory's overarching goal: development, understanding and better human communication with tomorrow's information systems.

In the Laboratory's fourth category of research, Theory, we strive to discover and understand the fundamental forces, rules, and limits of Information Science and Technology. As a result, theoretical work permeates our research efforts in the other three areas; for example, in the pursuit of parallel algorithms, fault tolerant computer networks, and privacy and authentication of communications. Theory also touches on the logic of programs, the inherent complexity of computations, and the use of cryptography and randomness in the formal characterization of knowledge. The Laboratory expends a great deal of effort in theoretical computer science because its impact upon our world is expected to continue its past record of improving our understanding and helping us pursue new frontiers with new models, concepts, methods, and algorithms.

Research highlights during the reporting period are as follows:

The World Wide Web (W3)

The Laboratory has founded a W3 Consortium similar to the X Consortium. As of this report, over 50 organizations have joined this consortium in order to participate in the W3 standard setting process. That process, and the consortium, are directed by Mr. Tim Berners-Lee, the inventor of W3. A team of researchers and developers is being assembled at LCS and at our European affiliate INRIA (France), to staff the consortium effort. The team, which is currently at half of its planned size, will entail some 25 full-time people and several students. We are proud to be involved in the continued development of W3, which is widely used by millions of people and which, as a result, enhances the pursuit of our objectives in the evolution of scalable international information infrastructure architectures.

Multiprocessor Architectures

(1) Professor Arvind's group, in collaboration with Motorola, is currently engaged in building the *T (StarT) parallel machine, using a Power PC 620 SMPs. StarT will support both efficient message passing as well as cache-coherent shared-memory across SMPs, and will run all the standard software for PowerPC based machines. The group also continues to use the Monsoon Dataflow multiprocessors and to develop applications and compilers for implicitly parallel languages. (2) The MIT Alewife machine has been tested over an expanding suite of applications. Alewife's unique features include the integration of message passing and shared memory into a single coherent interface, and a software coherent shared-memory called limitless directories.

Spoken Language Systems

Our Spoken Language Systems Group has expanded and strengthened its capabilities through continued development of its constituent component technologies. The speech recognizer was completely restructured to make it more modular, efficient, and portable. The language generator was expanded to enable multilingual paraphrasing and response generation. Research in dialogue modeling was conducted in the area of "displayless" human-computer interactions. Spoken language access to subsets of the world wide web has been introduced, and a new knowledge domain of automobile classified ads has been developed.

Advanced Graphics

A new effort has begun at LCS under the leadership of Professor Seth Teller. It involves the automatic digitization of large physical environments, such as the City of Cambridge, through use of vehicular cameras that travel the streets of the city. In this work and the associated rendering of the scanned environments, emphasis is placed on computational savings through exploitation of geometrical/optical properties.

Computational Biology

Professor Bonnie Berger has identified certain computational rules that are believed to govern the construction of the outer shells of most viruses. This work, which has received widespread attention in the scientific press, may eventually lead to the development of methods for halting viral reproduction by interrupting the shell formation process. This is joint work with Drs. Peter Shor of AT&T Bell Labs and Jonathan King of the MIT Biology Department.

During this reporting period, the Laboratory's Distinguished Lecturer Series included presentations by Dr. Rick Rashid, Microsoft Corporation; Professor Manuel Blum, University of California, Berkeley; Professor Barbara Grosz, Harvard University; and Professor Andries van Dam, Brown University.

The Laboratory is organized into 20 research groups, an administrative unit, and a computer service support unit. The Laboratory's membership comprises a total of 466 people, including 95 faculty and research staff, 188 graduate students, 95 undergraduate students, 51 visitors, affiliates, and postdoctoral associates and fellows, and 37 support staff. The academic affiliation of most of the Laboratory's faculty and students is with the Department of Electrical Engineering and Computer Science (EECS).

About one half of the Laboratory's funding comes from the US Government's Advanced Research Projects Agency. The Laboratory is also funded by and has extensive links with industrial organizations. These include partnerships for the construction of major hardware systems, consortia for the development and maintenance of standards, such as the World Wide Web, and joint studies on research areas of common concern.

Michael L. Dertouzos

MIT Reports to the President 1994-95