Interactive Computation: The New Paradigm

to be published by Springer-Verlag in September 2006

1. Objectives of the book

Interactive computation involves interaction, or communication, with the external world during the computation -- in contrast to traditional, or algorithmic, computation which proceeds in closed-box fashion. Concurrent and reactive computation are both interactive. Embedded, agent-oriented, distributed and component-based computation are also part of the interactive paradigm.

The proposed book, tentatively titled "Interactive Computation: The New Paradigm", has the following objectives:

  1. To challenge traditional answers to some fundamental questions related to the nature of computation and the scope of computer science.

  2. To increase the awareness of this change in computational paradigms among the wider CS community.

  3. To stimulate further practical and theoretical research related to interactive computation.

2. What do we mean by Interactive Computation

The paradigm shift from algorithms to interactive computation captures the technology shift from mainframes to networks, wireless devices, and intelligent appliances, from number-crunching to embedded systems and graphical user interfaces, and from procedure-oriented to object-based and distributed computation.

The following characteristics distinguish this new, interactive notion of computation:

Computational Problem: The notion of a computational problem is that of performing a task or providing a service, rather than that of algorithmically producing an answer to a question.

Dynamic Streams: Input and output are modeled by dynamic streams which are interleaved; later values of the input stream may depend on earlier values in the output stream and vice versa.

Environments: The world, or environment of the computation is part of the model, playing an active part in the computation by dynamically supplying the computational system, or agent, with the inputs, and consuming the output values from the system.

Concurrency: Computation is concurrent; the computing agent computes in parallel with its environment, and with other agents that may be in it.

Non-computability: The environment cannot be assumed to be static or effectively computable; for example, it may include humans, or other elements of the real world.  Hence we cannot always precompute input values or predict the effect of the system's output on the environment.

The notion that these characteristics are inherently outside the traditional algorithmic conceptualization of computation is the basis for this new paradigm for computing, built around the unifying concept of interaction.

3. Intended audience

Computer science researchers, and others with interest in computational paradigms, in current computer science research, or in future directions for computing theory and applications.  A background in computer science at the level of core undergraduate curriculum will be assumed.

4. Book contents

The book will have three sections, one on theory, the second on applications, and the third on other related areas.

We plan to include about 15 chapters of 15-25 pages each, written by leading researchers who have contributed to the theory and/or applications of interactive computing.  We expect the chapters to discuss the work done in the past, and/or to provide a vision for the future, in a manner furthering the book's objectives.

A list of potential topics for all three areas is in a separate section, below. The editors will be available to discuss with individual authors their choice of topic or presentation.

5. The editors

The editorial team consists of three members, representing a spectrum of computer science research, and embodying strong experience in editing high-quality books on various topics in computer science.  They are, in alphabetical order:

Dina Goldin, U. of Connecticut, CT

Scott Smolka, SUNY Stony Brook, NY

Peter Wegner, Brown U., RI

6. Potential topics

The following set of subjects represents a wide spectrum of issues related to interactive computation. We hope that it serves as guidance for authors in selecting their topics.

online algorithms/dynamic data structures
game theory
interactive/zero-knowledge proofs
interactive approaches to complexity theory
distributed computing
communication protocols
communicating/concurrent processes/objects
interactive/reactive systems
specification/verification of infinite-state systems
temporal/paraconsistent/non-classical logics
programming languages/mobile programs
component-based/object-oriented software engineering
robot programming
agent-oriented/mobile/embedded computing
dynamic environments for agents/systems
sensor networks/distributed systems/internet computing
bio-computing/amorphous systems
grid computing/hyper computing/global computing
cellular automata/swarm intelligence
human-computer interaction/software usability/user interfaces
intelligent/aware/virtual environments
agoric/market-oriented/equilibrium computing
education: reinventing CS1 and Theory 101?
history of computing
applications to mathematics and sciences

7. Organizational issues 

Our goal is to help authors write articles on topics that they are comfortable with, while contributing to the objectives of the book. Towards this end, we will ask authors to submit a short draft (3-5 pages) prior to writing a full article. These drafts will allow the editors to ensure a consistent and coherent overall presentation of the book's material, leading to a high-quality book.

8. Some of the authors

Gul Agha (modeling interactive computation -- lessons from Actors)
Mehmet Aksit (software process perspective)
Susanne Albers (online algorithms)
Farhad Arbab (coordination models & languages)
Manfred Broy (components)
Michel Beaudouin-Lafon (human-computer interfaces)
Peter Denning & Tom Malone (user interaction and coordination science)
Giorgi Japaridze (computability logic)
Ramesh Jain (databases)
Sven Kosub (models of computation)
Shriram Krishnamurthy (programming languages)
Jan van Leeuwen (embedded systems)
Robin Milner (formalizing Interactive Computation)
Andrea Omicini (patterns of interaction, with Alessandro Ricci and Mirko Viroli)
Rohit Parikh (economics and interactive computer science)
Howard Smith & Peter Fingar (business workflow management)
Lynn Stein (introductory CS education)
Moshe Vardi & Orna Kupferman (logic)
Yuri Gurevich (interactive algorithms)