The CoSMoS Project

Investigators

University of York

PI Prof Susan Stepney; CIs Prof Jon Timmis, Dr Fiona Polack, Prof Andy Tyrrell; RA Dr Paul Andrews

University of Kent

PI Prof Peter Welch; CI Dr Fred Barnes; RA Carl Ritson

Partners

Dr Jim Bown, Prof Alan Winfield.

Project Aims

Our project will build capacity in generic modelling tools and simulation techniques for complex systems, to support the modelling, analysis and prediction of complex systems, and to help design and validate complex systems. Drawing on our state-of-the-art expertise in many aspects of computer systems engineering, we will develop CoSMoS, a modelling and simulation process and infrastructure specifically designed to allow complex systems to be explored, analysed, and designed within a uniform framework. CoSMoS will comprise: a modelling and analysis process, based on computational concepts such as class, state, behaviour, and communication, and on complex system emergent properties, expressed in part as rich argumentation, modelling, analysis, and refactoring Pattern Languages; a massively parallel and distributed simulation environment, based on CSP and system modelling technologies that encompass a wide range of process granularities, targeted to the specific properties of complex systems: vast numbers of (relatively) simple agents interacting and communicating in parallel, in an (often stigmergic) environment. The development of CoSMoS will be case study driven, to ensure that it contains the necessary generic components, and so that several iterations of the method and toolset, of increasing functionality and applicability, can be produced and validated. The detailed project aims are:

back to top

Background

A complex system can be characterised by low-level agents communicating and interacting in and with an environment, exhibiting high-level (emergent) behaviours. Agents are characteristically relatively simple machines, with limited sensing and actuation capabilities. A complex system operates through the effect of many (often vastly many: "more is different") such agents communicating and interacting in an environment. The environment provides the interaction medium, including spatial and temporal context, for the agents. The collective effect of the agents is some pattern of high-level behaviours, expressible in the context of the environment. These high-level behaviours are not readily deducible from the low-level behaviour specifications of the agents, and so simulation is a key component in exploring the behaviour of such systems. Before an executable simulation can be built, however, the complex system needs to be modelled in appropriate computational terms: terms that capture the various kinds of agents, their behaviours, their communications, and their interactions in and with their environment. The (relative) simplicity of the simulated agents can lure researchers into naive techniques that fail to scale, fail to be analysable in all but the most trivial manner, and fail to be comparable across different systems. We propose an integrated method and simulation environment to address these problems: CoSMoS will provide a suite of conceptual, modelling, and executable tools for the analysis and design of complex systems, covering modelling, simulation and argumentation. Note that we are not proposing to develop individual detailed simulators for individual applications. There are many superb special-purpose simulators already available for particular domains. We are proposing instead a generic complex systems simulator, that exposes and unifies general properties across a range of complex systems, and allows such systems to be compared and analysed within a uniform framework.

Modelling process

We have critiqued the traditional naive approach to bio-inspired algorithm design, that moves straight from a simplistic description of the biology into some algorithm; we describe a "conceptual framework", including mathematical and computational modelling, abstraction of principles, and instantiation into relevant application domains. The same critique applies to much complex system simulation work that has a naive direct implementation of the components of the complex system. Here we propose a conceptual framework for modelling and simulating complex systems (rather than for designing application algorithms):
This framework drives the detailed project aims as laid out above, and the structure of the work programme. Modelling we will exploit various system modelling languages and process algebra modelling techniques that have proved applicable to complex systems. For example: UML/MOF class diagrams can capture and classify the agents within a system, and their relationships with each other and their environment; statecharts can capture the lifecycle of each kind of agent, and of the environment; sequence diagrams or process algebras can capture the temporal patterns of interactions between agents, and with the environment. Recent developments in domain specific language support and meta-modelling, and approaches for rigorously analysing UML models, and work on human-scale systems of systems, will contribute to identifying well-defined modelling approaches and analyses specialised for complex systems agents and their environments (eg, agent flow, chemical dispersion, stigmergic interactions). Scale issues may also require corresponding complex systems of environmental agents, for example, a model of a complex system of nano-scale agents (eg, antibodies), may need a model of environmental nano-scale particles (eg, antigens) as complex systems. We will start from such state-of-the-art modelling, and from current computational modelling such as Harel’s use of statecharts in modelling T-cells of an immune system, and simple organisms, and the various process algebra-like approaches to systems biology models. We will capture patterns and stratagems for complex system modelling, always with a view to validation of the models. Patterns provide a library of received wisdom, of common abstractions and structures, of model generation, and so on, from which to generate a modelling process description. Patterns also help control the freedom and flexibility (and ambiguity!) of system models, by providing a library of uniform and reusable concepts and structures common to classes of complex systems. Alexander’s original intent of pattern language theory was generative, and process oriented. However, this feature has been missing from most computer science patterns, which are mostly as static constructive, instead of dynamically active, concepts. With input from Alexander, we will base the CoSMoS process description around suitably designed generative dynamic Pattern Languages, derived from the case-study-driven process development. Refactoring is a principled technique for improving the structure of models. CoSMoS will incorporate a generative refactoring pattern language (refactorings expressed as process patterns, targeting particular modelling patterns) in its method for designing and maintaining complex system models, and for ‘refining’ initial abstract system models towards instantiated simulations, as part of the framework mapping process. This will enable the precise choice of simulation platform to be deferred until late in the modelling cycle. Argumentation and analysis It is not sufficient merely to model and simulate a complex system: there must be some aspect of the process that argues that these results bear any relation to reality. Although this is usually done to some degree in practice, it is often left implicit: CoSMoS will make this aspect of the process explicit. In particular, it will include analysis patterns for arguing about emergent properties. This aspect is crucial for establishing scientific credibility of the results when investigating natural complex systems, or for establishing evidence for dependability and certifiability arguments of designed complex systems. If an artificial complex system is to be used as part of any kind of critical application it is necessary to argue about its dependability: it must be possible to demonstrate that the system operates correctly within, and fails safely outside, its domain of applicability. Development approaches need to provide such evidence, not only through formal verification, but also through appeal to patterns of experience. Because the effects of multiple agents operating in an environment cannot always be predicted from static models, it is necessary to include evidence from simulations when arguing the dependability of a complex system. The simulation of a complex system seeks to demonstrate the high-level properties by modelling the simple agents; demonstrable dependability requires that the simulation should achieve a suitable level of realism. As part of our EPSRC-funded TUNA project, we have been investigating the York’s Goal Structuring Notation (GSN)Error! Reference source not found., suitable for developing argumentation patterns: we will use that work as a starting point for CoSMoS-specific argumentation patterns.

Simulation framework

There are two key problems in simulating complex systems. Firstly, many high-level properties depend on a large number of the simple agents; simulations with insufficient instances may not demonstrate the relevant effects. Secondly, the high-level effects may be critically dependent on the environment in which the agents are situated; simulations that do not express the right elements of the environment at the right scales are not useful models of a real system of agents. (This can occur in robotics, for example, where the simulated robotic controller does not operate as designed in the real world because the simulation has an over-simplified model of the physical world.) So for simulation, we will target platforms that provide fast simulation of vast numbers of agents, with the computational capacity to model aspects of the environment as well as the agents. Environmental modelling will treat the environment as a nested collection of (possibly) complex systems that interact with the target complex system, in an extensible and scalable way. Complex systems are inherently highly parallel. Most computer languages treat parallelism as an add-on, in an ad hoc manner, using complicated control mechanisms that make parallel programming a convoluted nightmare. Yet there is a conceptually clean formal approach to parallelism: Hoare’s CSP (Communicating Sequential Processes) forms the basis for our distribution architecture. It has a variety of executable subsets on a range of platforms, allowing a uniform investigation of the tradeoffs between granularity and parallelism. CoSMoS will support a single, uniform CSP-based architecture as a distributed simulation environment for complex systems, then instantiate it across this range of platforms and parallelism grains, described below, exploring the trade-offs between granularity (complexity of individual processes, representing cells, etc), parallelism (number of processes supported per host), and distribution (number of hosts). Different trade-offs will be appropriate to different problems. This will allow a principled design of a distributed architecture for a given problem domain. The project’s task is to develop a uniform simulation framework that can defer choice of precise platform, and can support movement between platforms, as the grain of the simulation changes or develops. Handel-C on FPGAs. Field Programmable Gate Arrays (FPGAs) provide true parallelism on a single chip, via programmable hardware. Handel was spun off from occam, to target the direct design of such specialised silicon. Now extended with data and control structures from C (and renamed Handel-C), it provides a direct high-level representation of digital design via communicating processes. It supports the same CSP subset as the original occam, supplemented with special rules over timing. It lacks the dynamic extensions (eg for channel mobility) and CSP completion (eg for multiway synchronisation) now built into occam-pi (below). Initial work shows that a range of bio-inspired population-based algorithms (genetic, immune, swarm) can be cast in a uniform generic Handel-C framework, run on a single FPGA with small populations, or distributed over multiple FPGAs for larger populations. This work has led to a subsequent design for a dynamically routable multi-FPGA system, which we will exploit in CoSMoS. This architecture represents the finest granularity: small processes consisting of simple data structures (bits, words, simple arrays) running in true parallelism per FPGA, and distributed across multiple hosts, each of which is potentially very small (a single chip). occam-pi on PC clusters. occam-pi is derived from classical occam (a similar implementation subset of CSP to Handel-C, originally designed for running on transputer arrays). It incorporates concepts from the p-calculus to support various dynamic behaviours. The TUNA project used occam-pi as a simulation language for realising CSP specifications of highly parallel agent systems. occam-pi is carefully designed to provide extremely low-overhead parallelism, and compiles to native code that can support millions of processes on a standard desktop machine, with context switch overheads in the (low) tens of nanoseconds. Under TUNA, occam-pi has been extended to support multi-processor applications, using Kent’s TUNA grid as a testbed. This comprises 32 cheap Linux boxes linked by a 1Gb Ethernet, and provides a high-performance, low-cost parallel machine. TUNA drove language developments in occam-pi: it completed the formal semantics for mechanisms such as extensions for mobile channels and multiway synchronisations (which now have a CSP definition that merges seamlessly with the non-mobile versions that directly correspond to CSP primitives); it invented an algorithm for fast resolution of choice over multiway synchronisation, which is needed to implement CSP models unconstrained by the executable subset previously supported. This architecture represents intermediate granularity: intermediate complexity processes containing intermediate scale data structures (structured arrays), millions timesliced per host, and distributed across multiple PC hosts. JCSP on White Rose Grid (WRG). JCSP is a Java class library that provides the CSP communication architecture. It implements this using Java threads, which are hidden from the user, but which results in a limit of thousands of parallel processes being supportable per host. This architecture represents the coarsest granularity: maximal complexity processes exploiting the full Java language, thousands timesliced per host, and distributed across multiple WRG nodes. Our work in the TUNA project has established that a CSP-based approach is fruitful. In its case study (blood platelets and clotting), we have reached the stage where useful experimentation has become possible. We have developed a CSP-based multi-layered multi-phased dynamic client-server architecture, modelling a (simple) 3D blood vessel, platelets, clots, chemical diffusion, and cell damage. One demonstration runs over 40 million processes (of which more than 2 million are mobile and continually created and destroyed as they flow through the simulated environment), efficiently distributed over 24 nodes of the Kent TUNA grid, and comes complete with real-time 3D visualisation and user interaction.

back to top

Programme

We have adopted a case study driven methodology, to ensure that the CoSMoS method and toolset contain the appropriate components for modelling and simulating complex systems, and so that several iterations of the method and toolset, of increasing functionality, can be produced and validated. Some case studies will be used to drive the development of the modelling process and simulation infrastructure; others will be used to validate the results. A range of case studies is chosen, to validate the choice and use of the range of modelling and simulation options, and to ensure generically applicable results. CoSMoS will be developed incrementally over 6 phases, driven by the needs of increasingly challenging case studies. Each case-study driven phase will help produce and enhance the various methodological components of CoSMoS. Phase 0 will provide the groundwork and a baseline toolset. Phase 1 will provide the initial prototype toolset, based on a complex immune system case study. Phase 2 will produce a generic single complex-system toolset, generalising the phase 1 product to encompass a complex endocrine system case study. Phase 3 will extend CoSMoS to include support for multi-component complex systems. Phase 4 will extend CoSMoS to include support for multi-level complex systems. Phase 5 will apply the method and toolset to a validation case study, and evaluate the results.

back to top

Core Research: the CoSMoS method

The core research will be performed by an RA at York and an RA at Kent, who will work closely together. The York RA will be mostly concerned with designing and evaluating the modelling method and patterns; the Kent RA with developing the simulation infrastructure. They will both develop the case studies, and perform the final evaluation of effectiveness.

back to top

Doctoral Training

RS1: Swarm Robotics (York, CS) Applying CoSMoS to the development of engineered complex systems, using embodied multi-robot systems as a modelling platform. Jennifer Owen has been appointed as RS1. RS2: FPGA requirements (York, Electronics) Investigating advanced FPGA architectures that better support CoSMoS-style simulations. Antonio Gomez Zamorano has been appointed as RS2. RS3: Plant ecology models (York, CS) Applying CoSMoS to a rich complex biological system: re-engineering an existing large plant ecology simulation (a million plants), and scaling to orders of magnitude more plants. Teodor Ghetiu has been appointed as RS3. RS4: Generative patterns (York, CS) Investigating fully generative pattern languages, how their use affects software architectures, and how they can benefit CoSMoS. Tim Hoverd has been appointed as RS4. RS5: CoSMoS occam-pi compiler (Kent) Designing and implementing simulation patterns suggested by CoSMoS as occam-pi language extensions. Doug Warren has been appointed as RS5.

back to top

Dissemination and Exploitation

Project Web site: all publications and technical reports, including pattern languages, process catalogue, case study models; discussion forum including the User Group Panel. Workshops: We will run annual CoSMoS workshops, with a published proceedings, where we will present our CoSMoS results and status, and invite other (refereed) presentations from researchers in similar fields.

back to top