Welcome to the homepage of

Interactive Computation:
The New Paradigm

by Dina Goldin, Scott Smolka, Peter Wegner

 

Basic Details    |    Table of Contents    |    Errata    |    Miscellaneous Links


Basic Details

Published by Springer-Verlag, September 2006
487 pages
ISBN: 978-3540346661


Table of Contents

I. Introduction

1. Robin Milner, Turing, Computing, and Communication

In this chapter, Milner discusses how computer science has changed substantially since Turing's founding ideas, advancing from prescription to description, from hierarchical to heterarchical design, from determinism to nondeterminism, and from end results to interaction. The evolution of computer science to include interaction would have excited and been approved by Turing.

2. Farhad Arbab, Computing and Interaction

This chapter offers a rough sketch of the landscape of computing with the specific aim of interrelating well established
topics such as computability and concurrency to newer areas such as interaction and composition of behavior.

3. Peter Wegner and Dina Goldin, Principles of Interactive Computation

This chapter explores Wegner and Goldin's contributions to interactive computing, with special emphasis on the philosophical question of how truth has been used (and misused) in computing and other disciplines. They suggest that interaction provides an empiricist model of computation that differs from rationalist mathematical algorithms models proposed in the 1960s by theoretical computer scientists, and point out that the Strong Church-Turing thesis, which reinterprets the Church-Turing thesis by applying it to all computation, contradicts the original thesis and is technically incorrect.

II. Theory

4. Manfred Broy, A Theory of System Interaction: Components, Interfaces, and Services

This chapter studies models, specification, and refinement techniques for distributed interactive software systems composed of interfaces and components. A theory for the interaction between such systems is given that refers to the interaction among systems and their environments, as well as the interaction among the components of systems. Interfaces and interactions are modeled by logical formulas in the style of design by contract, by state machines, and by streams of messages and signals. This leads to a theory of interface abstraction of systems that is essential for an interaction view. In particular, this theory treats interaction refinement and introduces a service concept based purely on interaction.

5. Orna Kupferman and Moshe Vardi, Verification of Open Systems

This chapter considers the verification of interactive systems. In formal verification, one verifies that a system meets a desired property by checking that a mathematical system model satisfies a formal specification of the property. Since assumptions about the environment and its interaction a system are a natural part of the specification in robust model checking, the model studied in this chapter subsumes extensions that can be expressed in terms of properties of the environment and its interaction with the system.

6. Jan van Leeuwen and Jiri Wiedermann, A Theory of Interactive Computation

This chapter asks what a computational theory of interactive, evolving programs should look like. The authors point out that a theory of interactive computation must necessarily lead beyond the classical, finitary models of computation. A simple model of interactive computing is presented consisting of one component and an environment, interacting using single streams of input and output signals. This model elegantly characterizes interactive computation in a stream setting and enables the authors to study the computational implications of interaction, building on the theory of w-automata. Viewing components as interactive transducers, they obtain several interesting theoretical results.

7. Susanne Albers, Online Algorithms

Online algorithms are a theoretical framework for studying problems in interactive computing. They model the situation in which the input to an interactive system arrives not as a batch but as a sequence of input portions, and in which at any point in time the future input is unknown. This chapter explores online algorithms for diverse applications, including resource management in operating systems, data structuring, scheduling, networks, and computational finance.

8. Yuri Gurevich, Interactive Algorithms 2005

In this chapter, Gurevich asserts that computer science is largely about algorithms, and broadens the notion of algorithms to include interaction by allowing intra-step interaction of an algorithm with its environment. This chapter discusses various forms of intra-step interaction and shows that numerous disparate phenomena are best understood as special cases of it. A survey of recent work on interactive algorithms follows.

9. Giorgi Japaridze, Computability Logic: A Formal Theory of Interaction

This chapter presents an introduction to computability logic, which is a formal theory of interactive computability in the same sense as classical logic is a formal theory of truth. It views computational problems as games played by a machine against the environment: if there exists a machine that always wins the game, then the problem is computable.

III. Applications

10. Michel Beaudouin-Lafon, Human-Computer Interaction

Human-computer systems are systems with a human user in the loop; to give the user a sense of control, they must be prepared to receive virtually any input at any moment and react to it in a way the user can understand. In this chapter,
Beaudouin-Lafon evaluates some unique aspects of human-computer systems with respect to these characteristics.
The chapter covers a wide range of user-interface styles and techniques, from traditional graphical user interfaces to
advanced research, and considers the full lifecycle of human-computer systems from design to evaluation.

11. Shriram Krishnamurthi, Robert Findler, Paul Graunke and Matthias Felleisen, Modeling Web Interactions and Errors

Interactive web programs permit consumers to navigate at whim among the various stages of a dialogue, leading to unexpected outcomes. In this chapter, the authors develop a model of web interactions that reduces the panoply of browser-supported user interactions to three fundamental ones. The model is used to formally describe two classes of errors in web programs and to suggest techniques for detecting and eliminating these errors.

12. Farhad Arbab, Coordination of Interactive Concurrent Computations

Coordination models and languages are a recent approach to design and development of concurrent systems. In this chapter, Arbab presents a brief overview of coordination models and languages and a framework for their classification. He then focuses on a specific coordination language, called Reo, that serves as a good example of a constructive model of computation in which interaction is treated as a first-class concept, and demonstrates that it provides a powerful and expressive model for flexible composition of behavior through interaction.

13. Rahul Singh and Ramesh Jain, From Information-Centric to Experiential Environments

User expectations of information-management systems are changing: rather than providing answers in response to queries, users want the system to let them interact with the data so that they can gain insights about it. In this chapter, the authors explore the paradigm of experiential computing for designing information-management systems.

14. Chris Barrett, Stephen Eubank, and Madhav Marathe, Modeling and Simulation of Large Biological, Information and Socio-Technical Systems: An Interaction-Based Approach

In this chapter, the authors describe an interaction-based approach to computer modeling and simulation systems composed of a large number of interacting components---be they biological, physical, or informational. Examples of such systems are transportation systems, electric power grids, gene regulatory networks, and the Internet. Their approach allows the authors to specify, design, and analyze simulations of extremely large systems, and implement them on massively parallel architectures.

IV. New Directions

15. Andrea Omicini, Alessandro Ricci, and Mirko Viroli, The Multidisciplinary Patterns of Interaction from Sciences to Computer Science.

In this chapter, Omicini et al. take a multidisciplinary view of interaction by drawing parallels between research outside and within computer science. They point out some of the basic patterns of interaction emerging from a number of heterogeneous research fields, and show how they can be brought to computer science to provide new insights on interaction in complex computational systems.

16. Peter Denning and Thomas Malone, Coordination

This chapter discusses coordination, an area of computing concerned with managing the interactions among multiple activities so that they achieve a single, collective result. Principles of coordination have been employed for many years by those who design, build, and evaluate interactive systems. Coordination plays a similarly fundamental role in management science. The chapter presents two complementary views of coordination in human-machine systems, in the belief that coordination principles will play a central role in the new theoretical paradigms of interactive computation.

17. Eric Pacuit and Rohit Parikh, Social Interaction, Knowledge, and Social Software

Social procedures are interactions in which humans must engage to reach some goal, whether to build a house or take a train. The authors ask whether it is possible to create a theory of how social procedures work, with a view to creating better ones and ensuring the correctness of the ones we have. This chapter surveys some of the logical and mathematical tools that address this question.

18. Lynn Stein, Interaction, Computation, and Education

This volume as a whole documents a fundamental shift in the culture of computation from a focus on algorithmic problem solving to a perspective in which interaction plays a central role. In this chapter, Stein points out that such a shift must be accompanied by a corresponding shift in computer science education, in the fundamental ``story'' we tell our students in their introductory courses.


Errata

In the first printing of the book, Figure 6 on page 292 is incorrect. Here is a link to the correct version of p. 292 (in PDF), with  Figure 6 on top.


Miscellaneous Links


Maintained by Dina Goldin <dqg AT cs.brown.edu>