Details of Grant 

EPSRC Reference:	GR/J87022/01
Title:	TRACTABLE BEHAVOIUR ANALYSIS FOR DISTRIBUTED SYSTEMS
Principal Investigator:	Kramer, Professor J
Other Investigators:
Researcher Co-Investigators:
Project Partners:
Department:	Computing
Organisation:	Imperial College London
Scheme:	Standard Research (Pre-FEC)
Starts:	01 October 1994	Ends:	30 September 1997	Value (£):	178,287
EPSRC Research Topic Classifications:	Networks & Distributed Systems
EPSRC Industrial Sector Classifications:
Related Grants:
Panel History:
Summary on Grant Application Form
To provide automated techniques for behaviour analysis of large-scale concurrent and distributed systems by investigating and developing the following:1) polynomial algorithms for approximate behaviour analysis of preliminary designs;2) incremental algorithms for analysis of subsystem behaviour subject to context constraints enforced by other components in the same system;3) compositional algorithms for exhaustive analysis of system behaviour; and4) an integration of approximate and exhaustive analysis techniques in order to provide a more general, flexible and effective approach for concurrent and distributed systems.Progress:The software architecture of a distributed system is described as a hierarchical composition of subsystems, with interacting processes as the leaves of the hierarchy. Process behaviour is specified using finite-state machines. Each finite-state process in the compositional hierarchy is modelled as a labelled transition system (LTS or state space graph) whose transitions are labelled by communicating actions. The research objective is to develop effective techniques with tool support for analysing the behaviour of such concurrent and distributed systems. The analysis aims to expose behavioural anomalies (both safety and liveness) in the design and implementation of these systems. To handle scalability, the techniques emphasise compositionality and support incremental analysis. To facilitate practical use, the approach incorporates both a fast approximate technique for preliminary analysis and an exhaustive technique for detailed analysis. For approximate analysis, we have adapted a low-order polynomial dataflow algorithm which is capable of detecting some synchronisation errors in preliminary designs. Approximate analysis uses a conservative error detection strategy such that any errors detected would also occur in the actual system where data value of variables are considered. However, not all errors will be detected. For exhaustive analysis, we utilise a state space enumerative technique which enhances existing reachability analysis techniques with recent work on compositionality and automatic derivation of context constraints. Context constraints are restrictions on a components behaviour imposed by its neighbours. In our existing exhaustive technique, however, the context constraints derived may not be sufficiently strict to prune all globally forbidden subsystem behaviours during local analysis. Those remaining forbidden subsystem behaviours can still accumulate in subsequent steps of exhaustive analysis and lead to a combinatorial state explosion. We are currently refining the existing context constraints derivation algorithm such that they can be combined with user specified constraints to provide a stronger set of constraints. These context constraints are specified in terms of an interface process. The interface is composed with the constituent processes in the analysed subsystem to produce a transition system using conventional reachability analysis technique. The transition system is then minimised and can be used as a substitute for the original subsystem in subsequent analysis. The automated technique is intended to facilitate identification of deadlock, starvation and undesirable behaviours. We are investigating the use of an integration of the approximate and exhaustive techniques. The research is intended to make behavioural analysis accessible and applicable to the development of real distributed systems. The resulting techniques will be provided as automated tools with graphical user interfaces and applied to large-scale distributed systems. In particular, we intend to integrate the tools into the System Architects Assistant (SAA), an environment for the design and construction of distributed systems being developed in a complementary project.
Key Findings
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Potential use in non-academic contexts
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Impacts
Description This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk Summary Date Materialised
Sectors submitted by the Researcher
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Project URL:
Further Information:
Organisation Website:	http://www.imperial.ac.uk