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
CPN Tools: http://www.daimi.au.dk/CPNtools/