Interaction is a pervasive aspect of today’s software science. 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: A computational problem entails performing a task or providing a service, rather than algorithmically producing an answer to a question.

Observable Behavior: A computing component is now modeled not as a functional transformation from input to output, but rather in terms of an observable behavior consisting of interaction steps. For example, interactions may be interleaved inputs and outputs modeled by dynamic streams; later input values may depend on earlier output values 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. The environment cannot be assumed to be static, or even effectively computable; for example, it may include humans or other elements of the real world. 

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

The interaction paradigm provides a new conceptualization of computational phenomena that emphasizes interaction rather than algorithms. The recognition that these characteristics are inherently outside the traditional conceptualization of computation is the basis for this new paradigm for computing, built around the unifying concept of interaction. Concurrent, distributed, reactive, embedded, component-oriented, agent-oriented and service-oriented systems all exploit interaction as a fundamental paradigm.

Peter Wegner’s claim (CACM, May 1997) that “interaction is more powerful than algorithms” challenges our fundamental assumptions about the nature of computation and the notion of computational problems, reinterpreting the Church-Turing thesis without attacking it directly. This claim is an open invitation to researchers to develop models, tools, and methods that can lend credence to it. Since then, pervasive/ubiquitous computing – which epitomizes interaction – has been proposed as the leading computing paradigm for the 21^st century. Now that many models capturing different aspects of interaction have been introduced, including interaction automata, process algebras, and co-algebraic approaches, we believe it is time for researchers involved in interactive systems to join their efforts to develop a common framework.

This workshop provides an opportunity for direct interaction among researchers in this new area, with the following goals:

• To understand the fundamental issues underlying the paradigm of interactive computation;

• To develop a roadmap for the design space of models of interaction;

• To establish a common language- and domain-independent framework for a theory of interactive computation;

• To identify the principles of effective and reliable engineering of interactive systems;

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

Our goal of bridging the theory and practice of interactive computation is designed to appeal to ETAPS participants from a variety of fields, representing research interests of most of the main ETAPS conferences.

Luca Cardelli, Microsoft Research

Title: Abstract Machines of Molecular Biology

Abstract: Living cells are extremely well-organized autonomous systems, consisting of discrete interacting components. Key to understanding and modeling their behavior is modeling their system organization. Four distinct chemical toolkits (classes of macromolecules) have been characterized, each combinatorial in nature. Each toolkit consists of a small number of simple components that are assembled (polymerized) into complex structures that interact in rich ways. Each toolkit abstracts away from chemistry; it embodies an abstract machine with its own instruction set and its own peculiar interaction model. These interaction models are highly effective, but are not ones commonly used in computing or concurrency theory (or mathematics): proteins stick together, genes have fixed output, membranes carry activity on their surfaces. "Systems biology" consists, largely, in understanding how these interaction models work, separately and together. To that end, biologists have invented a number of notations attempting to describe, abstractly, these abstract machines and the processes and networks they implement. I discuss the notations currently used by biologists, the (possible) advantages of using process calculus approaches, the need for new process calculi, and some calculi I have worked on. The long-term goal is to represent the structure and function of biological systems via formal languages, for description, simulation, analysis and (eventually) synthesis.

The Role of Agent Interaction in Models of Computing

In furthering the workshop goals, the panel will address the following questions:

• how do interactive models change our notion of a computational problem?

• how do models of interaction contribute to the study of AI, networking, and other applications?

• how do "interactive systems" relate to "open multiagent systems"?

• how practice and experience on multiagent systems can influence the theory of interaction?

• is interaction the foundation for the multidisciplinary study of complex systems like biology and social life?

After opening statements from each panelist to identify the points of agreement and disagreement, the discussion will be based on questions from the moderator and the audience.

Moderator: Peter Wegner, Brown University, USA

Panelists (in alphabetic order):

Gul Agha, UIUC, USA

Farhad Arbab, CWI & Leiden U., the Netherlands

Dina Goldin, Univ. of Connecticut, USA

Peter McBurney, Univ. of Liverpool, UK

Dave Robertson, Univ. of Edinburgh, UK

Dina Goldin Computer Science & Eng. University of Connecticut 371 Fairfield Rd., Unit 1155 Storrs, CT 06269, USA   Email: dqg_AT_cse.uconn.edu URL: http://www.cse.uconn.edu/~dqg

Mirko Viroli DEIS Università degli Studi di Bologna via Venezia 52 47023 Cesena, Italy   Email: mviroli_AT_deis.unibo.it URL: http://www.ingce.unibo.it/~mviroli

Peter Wegner Computer Science Brown University Box 1910 Providence, RI 02912, USA   Email: pw_AT_cs.brown.edu URL: http://www.cs.brown.edu/people/pw

Program Committee

Gul Agha, UIUC, USA Luca de Alfaro, UC Santa Cruz, USA Farhad Arbab, CWI & Leiden U., the Netherlands Antonio Brogi, U. Pisa, Italy Manfred Broy, TU Munchen, Germany Giorgio Delzanno, U. Genova, Italy Jon Doyle, N. Carolina State U., USA Ramesh Jain, Georgia Tech, USA R. Prescott Loui, Washington U. in St. Louis, USA Peter McBurney, U. Liverpool, UK John-Jules Meyer, Utrecht U., the Netherlands

Andrea Omicini, U. Bologna/Cesena, Italy Catuscia Palamidessi, INRIA, France Rohit Parikh, CUNY, USA Doug Schmidt, Vanderbilt U., USA Scott Smolka, SUNY Stony Brook, USA Lynn Andrea Stein, Olin College, USA Bernhard Thalheim, U. Kiel, Germany Jan van Leeuwen, Utrecht U., the Netherlands Rob van Glabbeek, NICTA, Australia Mike Wooldridge, U. Liverpool, UK

• paper submission: Dec. 20, 2004

• notification of acceptance: Jan. 24, 2005

• final versions: Feb. 11, 2005

• workshop: Apr. 9, 2005

 

Miscellaneous

• Here is the final CALL FOR PAPERS (pdf)

• Here is the final CALL FOR PAPERS in ASCII

• The proceedings of the workshop will be published by ENTCS. Some accepted papers will likely be selected for a special issue of an international journal.

• Two of the workshop organizers are serving as co-editors (together with Scott Smolka) of the book “Interactive Computation: The New Paradigm”, currently in preparation (http://www.cse.uconn.edu/~dqg/inter_book.html). Some of the book’s authors will be invited to speak at the workshop. 

• ACCEPTED PAPERS
   

  • Interactive Computation: Stepping Stone in the Pathway from Classical to Developmental Computation
    Antônio Carlos da Rocha Costa, Gracaliz Pereira Dimuro (Univ. Catolica de Pelotas, Brazil)

  • A Mathematical Model of Dialog
    Mark W. Johnson, Peter McBurney, Simon Parsons

  • A Reflective Higher-order Calculus
    L.G. Meredith, Matthias Radestock

  • Time-awareness and Proactivity in Models of Interactive Computation
    Leo Motus, Merik Meriste

  • Interactive Computation and Platform-Based Design: an Equivalence Relation
    Francesco Gianfelici (University Politecnica delle Marche, Italy)

  • Interactions in Transport Networks
    Nigel Walker, Marc Wennink (BT Research, UK)

  • Towards a Logical  Analysis of Interactive Systems
    Carolyn Talcott (SRI International), Ian Mason (Univ. of New England)

  • Coordination in Normative Multiagent Systems
    Guido Boella, Joris Hulstijn, Leendert van der Torre

  • Adaptation and Evolution in Dynamic Persistent Environments
    David Keil, Dina Goldin (University of Connecticut, USA)

  • Interactive Models for Design of Software-Intensive Systems
    Dina Goldin, David Keil (University of Connecticut, USA)

Maintained by Dina Goldin dqg_AT_cse.uconn.edu