acm-header
Sign In

Communications of the ACM

Experimental computer science

Introduction


In many fields of science (such as physics and chemistry) theory and experimentation complement and challenge one another. Theory may make predictions that can be confirmed or refuted only through experimentation. Experimentation may find new phenomena that must be explained theoretically. In computer science, however, theory seems to play a more dominant role, typically with little if any direct connection to experimentation. But experimentation is increasingly recognized as necessary and beneficial both as a complement to theory and as an element in constructing systems.


Systems—from microprocessors to the complete Internet—are increasingly complex and require observations and objective measurements to be studied and understood.


Experimentation involves several types of activities, including observation, measurement under controlled conditions, and replication of previous work. Despite their historic lack of emphasis, each could play a similarly important role in computer science. Regarding interaction with theory, experimentation is needed to verify the relevance of theory, probe corners that cannot be analyzed or that have been overlooked, and expose and explore phenomena that must be explained. A notable example of an effect that was first observed experimentally is the phenomenon of phase transitions in NP-complete problems, as described in this special section by Catherine C. McGeoch.

Observations are needed because systems—from microprocessors to the complete Internet—are increasingly complex and require objective measurement to be studied and understood. Likewise, how humans interact with computer systems must be studied experimentally to understand both how we use computers and how we construct new systems and programs. Victor R. Basili and Marvin V. Zelkowitz discuss how knowledge can be built through experiments involving programmers and students, as well as by observing people at work.

Experimental engineering is a unique notion in computer science, where complex systems cannot be analyzed in advance and must be built and evaluated iteratively in a real setting. This enables designers to verify that the systems will work and ensures that there are no lingering invalid assumptions that could undermine operations later. A notable example of this approach is provided by PlanetLab, "a global platform for experimentally evaluating wide-area network services," as described here by Larry Peterson and Vivek S. Pai. Meanwhile, new system designs must be evaluated in the context of representative workloads, as discussed by Alan Jay Smith.

Evaluations under controlled conditions are critical for progress in the development of practical systems, especially in a synthetic (as opposed to analytic) field like computer science where individual researchers may construct unique and possibly incompatible systems. Examples include the Text REtrieval Conferences and the Defense Advanced Research Projects Agency robotics programs, as described here in articles by Ellen M. Voorhees and by Larry D. Jackel et al., respectively.

Our goal is to showcase current work and achievements in experimental computer science. Together with the workshop on Experimental Computer Science (www.expcs.org/) held for the first time last June as part of the Federated Computing Research Conference in San Diego, it attests to the growing interest in the experimental approach and to increased recognition of the benefits of—and indeed the need for—experimentation. One may hope that in the future this need will be taken for granted, and experimentation in computer science will be second nature for students and practitioners alike.

Back to Top

Author

Dror G. Feitelson (feit@cs.huji.ac.il) is an associate professor and the head of the Parallel Systems Lab in the School of Computer Science and Engineering at The Hebrew University, Jerusalem, Israel.


©2007 ACM  0001-0782/07/1100  $5.00

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.

The Digital Library is published by the Association for Computing Machinery. Copyright © 2007 ACM, Inc.


 

No entries found