:: Site map:: Intranet
:: Research Areas:: Projects :: About CfPC:: News & Events:: Publications
  Modelling and Validation of Distributed Systems  
    Research themes  

Design and Analysis of Communication Protocols and Other Kinds of Distributed Systems
It is generally recognised that the design of the communication and synchronisation in concurrent/distributed systems is a complex task. A major reason is that the execution of such systems may proceed in many different ways, e.g., depending on whether messages are lost, the speed of the processes involved, and the time at which inputs are received from the environment.

Coloured Petri Nets (CP-nets) provide a framework for the design and analysis of such systems. CP-nets are based on Petri Nets, which is one of the most widely accepted formalisms for modelling and analysis of concurrent and distributed systems. CP-nets are also based on concepts and terminology from modern programming languages and hence they are relatively easy to learn and use for people with some programming experience. Construction of CPN models are in many respects similar to construction of prototypes. They allow the designer to make a concrete and thorough evaluation of the key design issues. This may not only reveal shortcomings, but also increase the designer’s understanding of the fundamental concepts in the new system.

A CPN model describes the states that the system may be in and the transitions between these states. By means of simulation a number of what-if scenarios be investigated. Furthermore, it is also possible to investigate the behaviour of systems by means of state space techniques. Then it is possible to consider all execution sequences and prove that the system possesses certain desired properties. The proofs are constructive in the sense that a negative answer identifies one or more counter-examples that can be used to locate the source of the problem.

Performance Analysis and Capacity Planning
CPN models can also be used to investigate the performance of a system, i.e., the efficiency of the system. Timed CPN models can be used to investigate the quality of service (e.g., waiting and processing time) and the quantity of service (e.g., throughput). In this way it becomes possible to predict the efficiency of a system before it is built and installed. By changing a few parameters in the CPN model, it is easy to experiment with different ways of improving the efficiency. In this way, it can be seen in which areas the development efforts should be concentrated to achieve the best results.

Capacity planning is similar to performance analysis, but the aim is slightly different. In capacity planning the goal is to choose the most suitable system configuration efficient enough to fulfil its tasks, now and in the foreseeable future, but without being overly costly by offering unused power. Capacity planning is an art performed by skilled individuals. Their creativity and experience is indispensable, but their work can be supported by allowing them to evaluate different system configurations by means of simulation models.

Tools, Algorithms, and Techniques
The tools, algorithms, and techniques for the practical use of CP-nets are under continuous development and improvement. Over the last years we have developed a very fast CPN simulation engine which is now integrated in the CPN tool set.

One of the main challenges in industrial application of state space techniques is to cope with the so-called state explosion problem, i.e., the large number of states and state changes in industrial sized concurrent systems. We have started a total redesign and reimplementation of the tool support for state space techniques. It is based on the new CPN simulation engine, contains improved data structures for state space storage, and implements a number of state-of-the-art analysis and verification algorithms alleviating the state explosion problem.

We are also in the process of implementing a totally new user interface for the CPN tools. The principles behind this interface may be of interest for many other graphical applications. Unlike standard graphical interfaces, the new user interface does not use menu bars, scrollbars or dialog boxes, and there is no need to select objects before editing them. Yet, the system is much faster to operate than a traditional desktop interface. Windows are replaced by pages that can be bound together into binders, making it easy to flip between pages and organise the workspace. A trackball, operated by the left-hand (if you are right-handed) complements the mouse. Using these two input devices, it is possible to resize and zoom objects by stretching them as one would do with a physical object. It is also possible to move an object with the right hand while flipping pages with the left hand to find its destination. Another two-handed input technique consists in moving a translucent palette called a toolglass with the left hand while clicking through the palette tools with the right hand. This type of interaction is up to 40% faster than traditional tool palettes. Finally, circular menus that pop-up where the mouse is clicked allow a very quick selection of commands, up to three times faster than traditional menu bars. The menu does not even appear when the selection gesture is made quickly. This allows for very fast selection without the need to learn keyboard shortcuts. Objects are aligned by sticking them to magnetic guidelines. Moving a guideline then moves all the attached objects at once.

CPN Tools: http://www.daimi.au.dk/CPNtools/



Related projects
UML + CPN @ Nokia
IPv6: Design and Validation
of Protocol
   CfPC©, updated: 14-nov-05