Efficiency of Asynchronous Systems

Start date: 01.01.1995
Funded by: Universität Augsburg
Local head of project: Walter Vogler
Publications: Publication list


see description


Supported by the German Science Foundation DFG 1994-1999

Characteristically, components of asynchronous systems cannot use time for coordinating their behaviour. In this project, such systems are modelled in process algebras or with Petri nets.

  • Petri nets are more accessible for practitioners due to their graphical representation, and therefore give a useful interface between practitioners and theoreticians; they are also conceptually attractive since they directly represent causality.
  • Process algebras model systems with algebraic terms; hence, by nature, they support the practically essential modular construction of systems.

Also Petri nets can be built from components, and the respective parallel composition operator plays a major role in the project. Both, Petri nets and process algebras, can model specifications as well as implementations of systems.

 If time is added to Petri nets or process algebras, this usually leads to models of synchronous systems, i.e. the enhancement with time changes the functionality of systems; furthermore, modularity is usually not a major issue. In the project, time is only used to compare the efficiency of asynchronous systems, their functionality is not changed.

Efficiency Testing

For system analysis, it is obviously important to consider aspects of behaviour that are observable for the users; observability can be formalised in the testing approach of De Nicola and Hennessy, which usually leads to a compositional semantics. Efficiency testing, developed in the project, is a variant of the testing approach leading to a faster-than relation comparing systems on the basis of their worst-case performance.

Important results are a testing-independent characterisation of this faster-than relationand the proof that this relation is the same for continuous and for discrete time. Based on discrete time, which is easier to handle, the tool FastAsy has been developed in order to decide whether one system (modelled as a Petri net) is faster than another for any user. Some realistic examples have been studied, and a close relationship to fairness has been developed; the latter is essential for system verification.

These studies were first based on Petri nets (cooperation with E. Bihler and L. Jenner, Uni. Augsburg), and more recently on the process algebra PAFAS (cooperation with F. Corradini and M.-R. Berardini, Uni. Camerino, Italien). This demonstrates that the results are model-independent.

Efficiency testing requires - as any usual testing approach - that the faster system serves any user in a shorter time; but in practice, a faster system only has to serve specific users better. Based on such a restricted class of users, it has been shown that pipeling gives a better performance, and further results for quantitative performance calculation have been obtained.

Faster-Than and Bisimulation

As an alternative to the testing approach, faster-than relations can also be defined on the basis of the standard equivalence bisimulation, which usually makes finer distinctions. In cooperation with G. Lüttgen (Uni. York, UK), the common process algebra CCS has been suitably enhanced with time. A faster-than relation was defined as a combination of bisimulation on actions and simulation on time, and this technically simple definition was validated by showing its equivalence to more intuitive, but also more complex alternative definitions.