The Design and Analysis of Evolvable Systems

Welcome to the Evolvable Systems Homepage

This is a resource page for The Evolvable Systems Project in the School of Computer Science, The University of Manchester, UK.

It contains explanatory material, published and draft papers, activities of the group and some relevant links.

What do we mean by Evolvable Systems?

The traditional understanding of computational systems and their analysis in terms of their semantics, logics and behavioural specification assumes that their syntactical descriptions determine the range of computational behaviours.

Increasingly, however, we build systems which may respond to external stimuli and change their computational behaviour accordingly, not by internal options but by reconfigurations determined externally. These external influences may either reflect an adaptive mode in which changes of environment determine changes in the computational system, or may be determined by internal imperatives in which a `monitoring process' (or a `supervisor') examines the computational behaviour of a system and determines appropriate evolutionary actions when the system behaviour requires modification. This is clearly related to the notion of `run-time monitoring' for system verification.

Examples of such evolvable systems are:

  • Adaptive query processing - evaluating queries over changing databases
  • Responsive memory management - variable capacity memory allocation
  • Supervisory control, for example, for reactive planning
  • Business structure and process evolution - businesses responding to internal or external imperatives to modify structure and processes
  • Hybrid systems which are adaptive to changing environments and which may influence their environments
  • Automatic, or user-determined, system updates, e.g. for operating system security, or virus detection software.

Evolvable systems can, of course, when viewed in their entirety, including the computational behaviour of the supervisor process, be treated as a closed system in the usual form and therefore open to standard treatments of semantics and logics.

However, this account misses crucial common structure which is present in these systems and makes their analysis quite different from ordinary computational systems. The common structure resides in (1) the way that monitoring processes have the ability to examine the behaviour of the underlying system, (2) the way that evolutionary steps interrupt computation and modify systems and their associated behaviour. Of considerable interest also is the assembly of systems from evolvable components, with evolutionary steps available at the various levels of a structural hierarchy.

[ Meta Buffers ]
Hierarchical structure of evolvable systems: Monitoring an evolvable buffer system.

Models and logics of evolvable systems

The Project involves: (1) devising suitable logics and models of evolvable systems, and (2) applications to the design, construction and verification of actual systems.

We have devised a logical framework for describing evolvable systems based on logics of revision and meta-level logics. We are now developing a theory of programming for hierarchical component-based evolvable systems.

Personnel

Members of the group include: Also involved are members of the Informatics Process Group:

Publications

Slides from talks

  • The slides from a Dagshtul talk (Jan 2007) summarising a basic logic framework for evolution.
  • Slides from the TASE talk (June 2007, Shanghai) summarising the logical framework for evolutionary component-based systems.

Seminars

We have recently introduced a seminar series on evolvable systems. Current seminars are:

  • Modelling evolvable systems: The Blocks World example. Howard Barringer, David Rydeheard.
  • Adaptive Query Processing. A Foundation for the Replacement of Pipelined Physical Join Operators in Adaptive Query Processing. Norman Paton (with Kwanchai Eurviriyanukul and Alvaro A.A. Fernades).
  • On the architecture and form of flexible process support. The talk concerns the architecture of business process support systems, where change is essential. A business supply chain scenario is used to illustrate the ideas. The scenario has been implemented in ProcessWeb thus providing some concrete examples of some of the issues involved. If time permits it may be possible to demonstrate the implementation. Bob Snowdon
  • A logical framework for monitoring and evolving software components

    Howard Barringer, Dov Gabbay and David Rydeheard
    12pm on Friday, January 19th 2007, KB 2.15

    We present a revision-based logical framework for modelling hierarchical assemblies of evolvable component systems. An evolvable component is a tight coupling of a pair of components, comprising a supervisor and a supervisee, with the supervisor able to both monitor and evolve its supervisee. An evolvable component pair is itself a component so may have its own supervisor, or may be encapsulated as a part of a larger component.

    Components are modelled as logical theories containing actions which describe state revisions together with a program over the actions. Supervisor components are modelled as theories which are logically at a meta-level to their supervisee. Revision actions at the meta-level can describe theory changes in the supervisee at the object-level and correspond to various evolutionary changes in the supervisee component. We will outline the framework and show how it enables us to describe the architecture, logical structure and logical programming of evolvable systems.

For details of forthcoming seminars, contact David Rydeheard.

Links

The notion of `reactivity' in computational systems is closely related to that of evolvability. As well as this work of evolvable systems we are investigating some reactive models of computation.

Here are few useful external links:

  • The Formal Methods webpages have a large volume of material including recommended books, publications, guide to conferences etc.
  • The Runtime Verification webpage is a guide to the RV workshops and other information.


Contact the Website Administrator with comments or queries about this website.
All material copyright ŠThe University of Manchester. Last update Jan 2007.