3.02.2005

Introducing Variable Sharing to Process Calculi

The goal of the talk is a formalisation of the notion of communication dualism and studying its impact on computational models of process calculi. Communication dualism roughly corresponds to the idea of dualism in concurrent systems first suggested informally in the famous Lauer-Needham hypothesis.
The formalisation is done in the Integrated Model of Distributed Systems (IMDS) where synchronous communication, as well as asynchronous message-passing and variable-sharing are modelled in a common framework. IMDS is characterised by that configuration and actions of a system are modelled in terms of communication items, as well as that a system can be decomposed in various ways into components.
There are two types of communication items, consumable passed items and reusable stored items. An atomic action processes a passed item and a store item on a node and creates some passed items and stored items. In a system decomposition, a system action is seen as a multi-handshake of some components which communicate in an synchronous way (by delivering the items processed in the action) or in an asynchronous passing or sharing way (by taking over some items created in the action).
In the whole spectrum of possible system decompositions, we identify two decompositions into asynchronous sequential processes. In one decomposition, processes hide message passing as the only intra-process communication and expose variable sharing as the only inter-process communication. In the other decomposition, process hide variable sharing as the only intra-process communication and expose message passing as the only inter-process communication. We call the two decompositions canonical decompositions and the transposition of the roles of passing and sharing as inter- and intra-process communication in the canonical decompositions communication dualism.
In the light of this property, any distributed system can be modelled not only in its message-passing version but in the shared variable version as well.
In most of computational models of process calculi, a system is modelled as a composition of processes communicating in a predefined way. In many models this is synchronous message passing. This approach leads to concise models, but assumes a primary (an absolute) communication on top of which other communication forms are defined. In such models, neither a communication integration can be modelled nor communication dualism can be formalised.
Moreover, some models use synchronous channels to model message passing. This approach assumes a global state access in system actions (e.g.: in the calculus). Other models avoid the global state access by introducing a synchronisation overhead in communication primitives (occam, Ada) or Java). In our opinion, in a radical solution, passing channels should be eliminated and passing and sharing should be modelled as peer communications in terms of consumable passed items and reusable shared items.
In the join calculus, channels are removed and locality is established, but passed and shared items are not distinguished. This is why, consumability of passed items and reusability of stored items have to be established at the application level.
Introducing variable sharing communication to computational models of process calculi allows extending the equitational theories to the passing and sharing versions of a system.