Bisimilarities over stable configuration structures can be divided into three families. In the first one - including interleaving, step, pomset, and forward-reverse bisimilarities - no isomorphism is required between the events matched during the bisimulation game. In the second one - including weak history-preserving, weak history-preserving pomset, and weak hereditary history-preserving bisimilarities - a labeling- and causality-preserving isomorphism is required between matched events, which is specific to each pair of configurations related by the bisimulation relation and hence can vary for a matched event from pair to pair. In the third one - including history-preserving and hereditary history-preserving bisimilarities - a single isomorphism is built incrementally, which is therefore fixed for all matched events. We revisit true concurrency bisimilarities by introducing variants that additionally check that the backward ready multisets of related configurations coincide. While the distinguishing power of the bisimilarities of the second and third families does not change, the power of the revised bisimilarities of the first family is equal to that of the bisimilarities of the second family. The latter bisimilarities can thus be characterized by replacing variable isomorphisms with simply counting incoming transitions. In contrast, backward ready multisets are not enough to characterize the third family in the simultaneous presence of autoconcurrency and non-local conflicts. We show that a further check for the existence of diamond and half-diamond substructures is necessary in that case to achieve the same distinguishing power as incremental isomorphisms.

In addition to forward computations, a reversible system also features backward computations along which the effects of forward ones can be undone. This is accomplished by reverting executed actions starting from the last one. Since the last performed action may not be uniquely identifiable in a concurrent setting, Danos and Krivine proposed causal reversibility: an executed action can be undone provided that all of its consequences have been undone already. Phillips and Ulidowski then showed how to define nondeterministic process calculi that meet causal reversibility by construction. Lanese, Phillips, and Ulidowski subsequently classified the basic properties that ensure causal reversibility. In this paper we investigate the extent to which those techniques apply to reversible nondeterministic process calculi that include quantitative aspects. Firstly, we consider the introduction of time described via numeric delays with action execution separated from time passing like in the calculus of Moller and Tofts, where actions can be lazy or eager and time is subject to time determinism and time additivity. Secondly, we address the introduction of probabilities like in the calculus of Hansson and Jonsson, in which action execution and probabilistic choices alternate. We show that both resulting reversible calculi satisfy causal reversibility provided that suitable variants of the aforementioned techniques are developed to guarantee the proper forward and backward interplay of nondeterminism and quantitative aspects. The use of the former calculus is illustrated on a timeout mechanism, whereas the use of the latter is exemplified on quantum teleportation.

Abstract We provide two alternative characterizations of hereditary history-preserving bisimilarity: a denotational one, on stable configuration structures, and an operational one, on a reversible process calculus. The characterizing equivalence is forward-reverse bisimilarity extended with a check for backward ready multiset equality. Unlike previous approaches, the focus is thus on counting identically labeled events rather than uniquely identifying them. We also investigate the relationships between event identifier logic, characterizing the former bisimilarity, and backward ready multiset logic, characterizing the latter bisimilarity.

The theory of noninterference supports the analysis of information leakage and the execution of secure computations in multi-level security systems. Classical equivalence-based approaches to noninterference mainly rely on weak bisimulation semantics. We show that this approach is not sufficient to identify potential covert channels in the presence of reversible computations. As illustrated via a database management system example, the activation of backward computations may trigger information flows that are not observable when proceeding in the standard forward direction. To capture the effects of back-and-forth computations, it is necessary to switch to a more expressive semantics, which has been proven to be branching bisimilarity in a previous work by De Nicola, Montanari, and Vaandrager. In this paper we investigate a taxonomy of noninterference properties based on branching bisimilarity along with their preservation and compositionality features, then we compare it with the taxonomy of Focardi and Gorrieri based on weak bisimilarity.

Abstract Reversibility is the capability of a system of undoing its own actions starting from the last performed one, in such a way that a past consistent state is reached. This is not trivial for concurrent systems, as the last performed action may not be uniquely identifiable. There are several approaches to address causality-consistent reversibility, some including a notion of forward-reverse bisimilarity. We introduce a minimal process calculus for reversible systems to investigate compositionality properties and equational characterizations of forward-reverse bisimilarity as well as of its two components, i.e., forward bisimilarity and reverse bisimilarity, so as to highlight their differences. The study is conducted not only in a nondeterministic setting, but also in a stochastic one where time reversibility and lumpability for Markov chains are exploited.

Causal reversibility blends reversibility and causality for concurrent systems. It indicates that an action can be undone provided that all of its consequences have been undone already, thus making it possible to bring the system back to a past consistent state. Time reversibility is instead considered in the field of stochastic processes, mostly for efficient analysis purposes. A performance model based on a continuous-time Markov chain is time reversible if its stochastic behavior remains the same when the direction of time is reversed. We bridge these two theories of reversibility by showing the conditions under which causal reversibility and time reversibility are both ensured by construction. This is done in the setting of a stochastic process calculus, which is then equipped with a variant of stochastic bisimilarity accounting for both forward and backward directions.

Context awareness is a first-class attribute of today software systems. Indeed, many applications need to be aware of their context in order to adapt their structure and behavior for offering the best quality of service even in case the software and hardware resources are limited. Modeling the context, its evolution, and its influence on the services provided by (possibly resource constrained) applications are becoming primary activities throughout the whole software life cycle, although it is still difficult to capture the multidimensional nature of context. We propose a framework for modeling and reasoning on the context and its evolution along multiple dimensions. Our approach enables (1) the representation of dependencies among heterogeneous context attributes through a formally defined semantics for attribute composition and (2) the stochastic analysis of context evolution. As a result, context can be part of a model-based software development process, and multidimensional context analysis can be used for different purposes, such as non-functional analysis. We demonstrate how certain types of analysis, not feasible with context-agnostic approaches, are enabled in our framework by explicitly representing the interplay between context evolution and non-functional attributes. Such analyses allow the identification of critical aspects or design errors that may not emerge without jointly taking into account multiple context attributes. The framework is shown at work on a case study in the eHealth domain.

Behavioural equivalences are a means of establishing whether computing systems possess the same properties. The specific set of properties that are preserved by a specific behavioural equivalence clearly depends on how the system behaviour is observed and can usually be characterised by means of a modal logic. In this paper we consider three different approaches to the definition of behavioural equivalences – bisimulation, testing and trace – applied to three different classes of systems – non-deterministic, probabilistic and Markovian – and we survey the nine resulting modal logic characterisations, each of which stems from the Hennessy–Milner logic. We then compare the nine characterisations with respect to the logical operators, in order to emphasise the differences between the three approaches in the definition of behavioural equivalences and the regularities within each of them. In the probabilistic and Markovian cases we also address the issue of whether the probabilistic and temporal aspects should be treated in a local or global way and consequently whether the modal logic interpretation should be qualitative or quantitative.

In this paper we provide an incremental methodology to assess the effect of the introduction of a dynamic power manager in a mobile embedded computing device. The methodology consists of two phases. In the first phase, we verify whether the introduction of the dynamic power manager alters the functionality of the system. We show that this can be accomplished by employing standard techniques based on equivalence checking for noninterference analysis. In the second phase, we quantify the effectiveness of the introduction of the dynamic power manager in terms of power consumption and overall system efficiency. This is carried out by enriching the functional model of the system with information about the performance aspects of the system, and by comparing the values of the power consumption and the overall system efficiency obtained from the solution of the performance model with and without dynamic power manager. To this purpose, first we employ a more abstract performance model based on the Markovian assumption, then we use a more realistic performance model - to be validated against the Markovian one - where general probability distributions are considered. The methodology is illustrated by means of its application to the study of a remote procedure call mechanism - through which a battery-powered device is used by some application requesting information - and of a streaming video service - which is accessed by a mobile client equipped with a power-manageable network interface card.

Multithreading provides an adequate support for concurrent programming, but requires the software developer to take care of the correct synchronization and exchange of data among threads. In this paper we propose an architecture-driven approach to the thread synchronization management, which is completely transparent to the software developer. This is realized by implementing a suitable Java package - which adheres to a general synchronization model and is inspired by the main architectural abstractions - by means of which well-synchronized multithreaded Java programs can be synthesized from their architectural specifications. The approach is illustrated by means of a real-time audio processing system.

Value passing process algebras with infinite data domains need to be equipped with symbolic semantic models in order for their analysis to be possible. This means that appropriate symbolic models and the related verification algorithms must be developed, together with suitable semantic rules mapping the value passing process descriptions to such symbolic models. In this article, we first introduce the model of the symbolic transition graphs with lookahead assignment (STGLAs), a variant of the symbolic transition graphs with assignment (STGAs) of Lin that can undergo to the strong, weak and observational bisimulation equivalence checking algorithms of Li and Chen. We then define a set of symbolic semantic rules that map a useful fragment of value passing CCS to finite STGLAs without making any assumption about the variable names. We demonstrate that the symbolic semantic rules are correct with respect to both the usual concrete semantic rules and the novel issue of the assignment application order. Finally, we prove that, for the considered fragment of value passing CCS, the STGLAs produced by the symbolic semantic rules are optimal with respect to a certain compactness criterion, thus improving on the symbolic models and the semantic rules previously proposed in the literature.

The architecture of component based software systems is classified as being static or dynamic, depending on whether the component number and the component connections are fixed a priori or can change at run time. Most work in the field of formal method based architectural description languages has focused on static architectures, as well as dynamic architectures where the architectural specification does not scale with respect to the components that can be created or destroyed at run time. In this paper we start from PADL, a graphical, hierarchical, process algebra based language for the description of static software architectures. We then enrich its syntax and semantics in order to provide scalable specifications of software architectures where some components are dynamically created and destroyed. We show that the construction of the new language allows the architectural checks developed for PADL to be reused for the detection of architectural mismatches in the description of dynamic software architectures.

Software components can give rise to several kinds of architectural mismatches when assembled together in order to form a software system. A formal description of the architecture of the resulting component-based software system may help to detect such architectural mismatches and to single out the components that cause the mismatches. In this article, we concentrate on deadlock-related architectural mismatches arising from three different causes that we identify: incompatibility between two components due to a single interaction, incompatibility between two components due to the combination of several interactions, and lack of interoperability among a set of components forming a cyclic topology. We develop a process algebra-based architectural description language called PADL, which deals with all three causes through an architectural compatibility check and an architectural interoperability check relying on standard observational equivalences. The adequacy of the architectural compatibility check is assessed on a compressing proxy system, while the adequacy of the architectural interoperability check is assessed on a cruise control system. We then address the issue of scaling the architectural compatibility and interoperability checks to architectural styles through an extension of PADL. The formalization of an architectural style is complicated by the presence of two degrees of freedom within the set of instances of the style: variability of the internal behavior of the components and variability of the topology formed by the components. As a first step towards the solution of the problem, we propose an intermediate abstraction called architectural type, whose instances differ only for the internal behavior of their components. We define an efficient architectural conformity check based on a standard observational equivalence to verify whether an architecture is an instance of an architectural type. We show that all the architectures conforming to the same architectural type possess the same compatibility and interoperability properties.

Formalizing the description of software systems helps to detect the presence of architectural mismatches that can arise when assembling software components together. The authors identify three causes of architectural mismatches: incompatibility between two components due to a single interaction, incompatibility between two components due to the combination of several interactions, and lack of interoperability among a set of components forming a cyclic topology. We then show how to deal with all of them within a uniform, process algebraic framework. We begin with the first two causes by strengthening a previously defined architectural compatibility check based on observational equivalences, in order to achieve a deadlock freedom result for the set of components interacting via a certain connection. We subsequently concentrate on the third cause by defining a novel architectural interoperability check based on observational equivalences, which guarantees absence of deadlock within a set of interacting components forming a cyclic topology. We finally assess the adequacy of our architectural interoperability check by applying it to the description of a cruise control system.

Architectural styles play an important role in software engineering as they convey codified principles and experience which help the construction of software systems with high levels of efficiency and confidence. We address the problem of formalizing and analyzing architectural styles in an operational setting by introducing the intermediate abstraction of architectural type. We develop the concept of architectural type in a process algebraic framework because of its modeling adequacy and the availability of means, such as Milner's weak bisimulation equivalence, which allow us to reason compositionally and efficiently about the well formedness of architectural types.

Abstract. A case study is presented which concerns the design of an adaptive mechanism for packetised audio for use over the Internet. During the design process, the audio mechanism was modelled with the stochastically timed process algebra EMPA and analysed via simulation by the EMPA based software tool TwoTowers in order to predict the percentage of packets that are received in time for being played out. The predicted performance figures obtained from the algebraic model illustrated in advance the adequacy of the approach adopted in the design of the audio playout delay control mechanism. Based on these performance figures, it was possible to implement and develop the complete mechanism without incurring additional costs due to the late discovery of unexpected errors or inefficiency. Performance results obtained from experiments conducted on the field confirmed the predictive simulative results.

Extended Markovian Process Algebra (EMPA) is a stochastic process algebra equipped with an interleaving semantics, a Markovian semantics and a net semantics. The main drawback of its net semantics is that is usually associates huge nets with EMPA terms. Here we propose a new net semantics, based on contextual nets, in order to obtain more compact net representations for EMPA terms.