Simon Bliudze, Joseph Sifakis
Causal Semantics for the Algebra of Connectors (2008)
Causal Semantics for the Algebra of Connectors (2008)
TR-2008-4.pdf
Keywords: interaction, algebra of connectors, causal semantics, boolean representation, connector synthesis
Abstract: The Algebra of Connectors AC(P) is used to model structured interactions in the BIP component framework. Its terms are connectors, relations describing synchronization constraints between the ports of component-based systems. Connectors are structured combinations of two basic synchronization protocols between ports: rendezvous and broadcast. In a previous paper, we have studied interaction semantics for AC(P) which defines the meaning of connectors as sets of interactions. This semantics reduces broadcasts into the set of their possible interactions and thus blurs the distinction between rendezvous and broadcast. It leads to exponentially complex models that cannot be a basis for efficient implementation. Furthermore, the induced semantic equivalence is not a congruence. For a subset of AC(P), we propose a new causal semantics that does not reduce broadcast into a set of rendezvous and explicitly models the causal dependency relation between triggers and synchrons. The Algebra of Causal Trees CT(P) formalizes this subset. It is the set of the terms generated from interactions on the set of ports P, by using two operators: a causality operator and a parallel composition operator. Terms are sets of trees where the successor relation represents causal dependency between interactions: an interaction can participate in a global interaction only if its father participates too. We show that causal semantics is consistent with interaction semantics. Furthermore, it defines an isomorphism between CT(P) and the set of the terms of AC(P) involving triggers. Finally, we define for causal trees a boolean representation in terms of causal rules. This representation is used for their manipulation and simplification as well as for synthesizing connectors.
