Group
THEORETICAL
FOUNDATIONS OF
COMPUTER
SCIENCE
Project:
Modelling And Analysis Of Time Constrained And Hierarchical Systems (MATCH)
Diese Seite ist teilweise in
Deutsch verfügbar.
Project in the scope of the EC-program 'Humankapital und Mobilität'
Partners are the Universities of Eindhoven, Paris VI, Turin, Vienna, Zaragoza
Duration:
October 1994 - September 1997
Keywords:
hierachical and modular models of information systems,
realtime systems, Petri nets
1. OBJECTIVES
The objectives of the network are twofold.
The first objective of the network is to allow its members to share
skills, in
order to progress faster in the definition of models on which
both qualitative
and quantitative analyses can be performed. These models
will tend to unify and
extend the existing theoretical models, and adapted
analysis techniques will be
proposed.
The second objective is to
develop a common culture in the domain of the
verification of timed
systems.
1.1 Description of Technical Tasks
The work will be
divided into 6 technical tasks, each of them involving several
participants
of the network.
- Extension of
structural properties (ESP)
A very important point in the
analysis of structural properties is the
possibility of obtaining
parameterized results, in order not to repeat the
computation when tuning
the values of the system parameters. Only few
parameterized results exist,
and the first aim of this task will be the
investigation of classes of
models and classes of properties that allow a
parameterized
analysis.
Temporal logic formulas are very useful to prove the correct
behaviour of a
system. The extension of temporal logic from state graphs to
Petri net like
models will be studied. The aim is to provide efficient
algorithms to verify
the correctness of a system.
Most structural
analysis results apply to models of systems with single
arrivals and
services. Structural analysis will be extended to models with bulk
arrivals
and services.
- Approximate performance
evaluation methods (APM)
Very few techniques exist for the
performance analysis of synchronized systems,
so that only simulation can
be used in most cases. And when techniques exist,
they usually apply only
to one particular and restricted formalism. The first
aim of this task will
be to work on the unification of existing theories so
that they can be
applied independently of the modelling formalism.
Combinations of exact
analytic techniques and approximate methods based on
aggregation and
decomposition techniques will be developed for systems
including
synchronizations.
- Influence of
structural properties on performance methods (ISP)
The major
point of this task will be to study the interactions of validation
and
evaluation methods, i.e., how the results obtained at the validation
step
can be reused to improve the efficiency of quantitative analysis
techniques.
The accuracy of an approximate method can be tested by
comparing its results to
results obtained by a simulation. If the
comparison is satisfying for a set of
examples, the method is considered as
valid. As many simulations are needed,
the definition of new theoretical
methods suited for the parallel and
distributed implementation of
evaluation and simulation tools will be
considered. These methods will use
the structural properties of the models.
The integration of qualitative
and quantitative analyses will require a
synthesis of the formalisms that
are used for one or the other goals. We will
investigate how structural
properties of the model can be reused to recognize
particular structures of
a Markov chain. We will also consider the use of
structural theory of Petri
nets to derive performance results, such as bounds
or approximation
computations. Finally, the influence of structural properties
in the
approximate computation of performance indices will be investigated.
- Hierarchical and modular analysis of models
(HMA)
The development of hierarchical analysis techniques is
necessary to face the
complexity of industrial systems. For these methods
different levels of
approximation correspond to the successive refinements
that occur in the design
of the application. At each step of the design
process, the validity of these
approximations must be checked, so that the
final prototype be coherent with
the early specifications. The problems of
a consistent semantics from top to
bottom, performance prediction and
verification from specification to
prototyping will be especially
investigated.
Modular approaches will also be considered, i.e., the
design of a model by
composition of submodels, which is very difficult if
the timing constraints are
taken into account, due to the composition of
probability distributions.
- Prototyping
(PRO)
The automatic achievement of a prototype from a formal
specification gives an
idea of how the system will behave in a real
environment. This task will focus
on the performance evaluation of a
prototype, which is complex as it depends
both on the choices of conception
that are made at the specification level, and
on the mapping of the code on
a system and architecture.
Prototyping is based on the identification
of the processes that compose the
application. Existing techniques only
consider an a posteriori
identification of the processes. An a
priori approach, where the
different components of the program are
modelled separately, will be
investigated. The aim is to define composition
techniques that preserve
qualitative and quantitative properties.
- Cooperation of tools
(COT)
Several partners already develop software tools that
implement validation and
evaluation techniques. The new theoretical results
obtained during the three
years' cooperation will be a basis to the
development of extended software
tools. Due to the strong interaction of
this task with all the others, not all
the results will be implemented, yet
requirements will be proposed for a better
cooperation of the existing
tools and for the integration of the new
techniques.
1.2
Training and Staff Exchange / Recruitment
- Training
The network aims at developping a
common approach in teaching in the field of
time- constrained and
hierarchical systems. In this goal, the outline of a
series of courses
common to all the partners will be defined. The courses will
concern
different levels of curriculums and will be based on a synthesis of
the
courses already given in this field by the partners, which tackle the
problem
with different points of view.
The definition of the common
courses will include a selected bibliography that
will be the basis for a
survey of the domain, and the writing of a book
synthetizing the different
aspects dealt with in the cooperation : the choice
of formalisms and their
relations, structural and behavioural properties,
performance evaluation,
integration of qualitative and quantitative analysis,
hierarchical and
modular modelling, presentation and use of software tools,
application to
prototyping. This book will be used as proceedings for the
advanced course
that is planned as the third main meeting of the cooperation.
- Staff exchange
For the first
two years of the cooperation, tripartite meetings are planned on
every
task, except the cooperation of tools. These meetings will require
the
exchange of researchers for a duration going from 10 days up to one
month.
During the last year, meetings will gather all the partners involved
in a task.
When necessary, extra travels will be organized to work on a
specific point.
One main meeting will be organized every year with all the
members of the
network.
The recruitment of young researchers will be
necessary for the development and
integration of software tools and for
modelling experimentation.
1.3
Methodology
- Interactions between
tasks
The tasks are strongly interconnected as structural
properties are used to
develop performance methods and define prototypes of
applications. Performance
methods must be used to predict the performance
of a prototype. Hierarchical
methods are necessary for applying both
structural and performance results to
large industrial models. And it is
indispensable to plan the integration of new
results in software
tools.
Every task is planned to last until the end of the
cooperation.
- Validation and evaluation
of the results
The results obtained within the network will be
valuated and evaluated by case
studies taken from different industrial
domains : flexible manufacturing
systems, communication networks or
massively parallel applications.
The future development of software
tools is also planned so that the results
will be available to a range of
non-expert users and their performance can be
compared to previously
developped tools.
- Organization of the
network
To ensure a good coordination between the partners, a
delegate will be
designated in each team. Once a year, a meeting of all the
delegates will
discuss the planning for the next year. The planning will
aim at synchronizing
the missions when more than two laboratories are
involved on a particular
topic. This way, meetings of small groups will be
prepared. When only two
laboratories are involved, missions will be decided
on a bilateral discussion,
and the information will be transmitted to the
coordinator.
Current communication in the network will be performed via
e-mail or fax
exchange.
Depending on its duration, each exchange will
produce either a report or a
draft paper that will be sent to the
coordinator. The coordinator will be in
charge of dispatching the
information to all the participants. These documents
will be used as a
basis for the publication of an annual advancement
report.
Also,
the cooperation will take advantage of conferences on subjects that are
of
interest for all the partners. Under the responsibility of the
coordinator,
one day meetings will be held around these conferences, that
will allow a
survey of the work in progress.
- Organization of network meetings
Three
main meetings are scheduled. Each of them will last five days. For each
of
these meetings, guests who have obtained significant results in the
domains
of interest will be invited to present their work.The first meeting
mainly aims
at strenghtening the links between the partners, whereas the
two other meetings
will be used for the dissemination of
results.
- The first main meeting will take place in France six
months after the
beginning of the cooperation. It will concern only
researchers from the
cooperating labs. They will present a state of the art
in their domain of
excellence that will be used as a basis for further
discussions, and they will
also present the open problems on which they are
currently working. The aim is
to plan precisely the issues that will be
tackled during the following year.
The deliverable will be a report on the
state of the art.
- The second meeting is planned in Italy and will be
open to researchers who do
not belong to the network. The papers they will
present will allow to review
the advances in domains related to the
cooperation and to establish a
comparison with the results obtained during
the first 18 months. The
deliverable will be a proceeding book.
- The
third meeting will be an advanced course and will take place in Spain.
This
course will aim among others at a presentation of the
industrial
perspectives of the work performed during the past two and a
half years. The
proceedings of the advanced course will be improved
according to the
suggestions of the participants to the meeting. The last
year deliverable will
be the final version of the book corresponding to the
advanced course.
2.ROLE OF PARTICIPANTS
The technical
work of the project is divided into 6 tasks, each of them under
the
responsibility of one of the partners. We specify thereafter
the
involvement of each team in the different tasks and we summarize in an
array
the contributions to every task.
- Eindhoven (responsible for
HMA)
* application of temporal logic to time analysis in
networks (ESP)
* semantics of hierarchical models, analysis of process
and data models (HMA)
* Prototyping of the temporal behaviour of a
system related to its functional
behaviour. Validation of analysis results
that were based upon a simplified
model of the system (PRO)
* Linking
the tool ExSpect to various tools for analysis (COT)
- Hamburg (responsible for
ESP)
* investigation of structural invariants, development of
distributed
algorithms from central to distributed solutions with
preservation of
specification and proof (ESP)
* hierarchical modelling
of software systems by colored Petri nets and
distributed algorithms
(HMA)
* abstraction of net models from applications, generation of
executable nets
(PRO)
- Paris
(responsible for PRO)
* approximate methods for performance
analysis of discrete-event systems
(APM)
* use of structural properties
for performance analysis methods (ISP)
* definition of a hierarchical
and modular high-level model for the functional
specification of systems,
proposition of transformation rules into Petri nets
(HMA)
* generation
of a distributed prototype from a validated Petri net model,
mapping of the
programs according to architecture constraints (PRO)
* Proposition of a
software architecture for the platform realizing the
integration of tools
and the management of the associated data and control
(COT)
- Torino (responsible for
ISP)
* approximate analysis methods for large, hierarchical
stochastic net models
(APM)
* relations between structural qualitative
properties of models and performance
evaluation methods
(ISP)
* development of interface mechanisms allowing
property-preserving, composition
of large models (HMA)
* definition of
standard types and access libraries for efficient model and
analysis
results storage and reutilization (COT)
- Vienna (responsible for
COT)
* exploitation of structural properties for parallel
execution (ISP)
* prototyping of parallel applications including
performance predictions
(PRO)
* prototype implementation of parallel
and distributed discrete-event
simulation, interfacing with Petri net tools
(COT)
- Zaragoza (responsible for
APM)
* structural analysis of models with bulk arrivals and
services (ESP)
* approximate computation of performance indices for net
subclasses (APM)
* integration of functional and performance structural
analysis (ISP)
* modular analysis of high-level models of real-time
systems (HMA)
Moreover for the three meetings that are
planned along the cooperation, the
local teams, namely Paris, Torino and
Zaragoza, will be in charge of the
organization.
3.COMPLEMENTARY
PROJECTS
IRENA : Industrial Requirements
Engineering Based on Nets for
Value-added Applications
(EUREKA Project
EU 389, 1991-1995)
Participants : ALCATEL-ISR, SLIGOS, GIE-EMERAUDE,
PRISMA, University Paris 6
The goal of the project is to provide an
industrial distributed environment
with configurable workstations for
developing heterogeneous distributed
applications. The method covers the
whole development cycle from the capture of
the requirement to the system
exploitation.
QMIPS : Qualitative Modelling
in Parallel Systems
(Esprit B.R.A. Project ndeg. 7269)
Participants
: Universities of Erlangen, Newcastle, Paris 5, Torino, Zaragoza,
INRIA
Sophia-Antipolis, London Imperial College, CWI Amsterdam
The goal of
the project is the assessment of current performance evaluation
techniques
and the development of new ones for application to parallel and
distributed
computer systems.
The first project focusses on the conception and
validation of distributed
systems using Petri net models, but completely
drops the performance aspect. On
the contrary, the second one focusses only
on the performance problem. One of
the aims of the MATCH project is to link
both approaches.
[Research]
[TGI]
[Informatics]
Last Change: 15:10 07/02/1997
Imprint/Disclaimer