Author name cluster

I. Castellani

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers

1 author row

I&C Journal 1994 Journal Article

Flow Models of Distributed Computations: Three Equivalent Semantics for CCS

G. Boudol
I. Castellani

We introduce three notions of computation for processes described as CCS (Calculus of Communicating Systems) terms. The first one uses an adaptation of the equivalence by permutations of Berry and Lèvy. In this setting, a computation is an equivalence class of sequences of transitions, up to the permutation of independent steps. The second notion of computation is given by means of an interpretation of CCS into a new class of event structures, the flow event structures. This can be seen as a reformulation of Winskel′s semantics for CCS by means of stable event structures. Here a computation is a configuration of an event structure. Finally, our third notion of computation is determined by an interpretation of CCS terms as Petri nets, and more precisely as flow nets. Here a computation is a set of events that are firable in sequence in the net. We then show that these three computation interpretations of CCS coincide, in the sense that for a given term, the three domains of computations are isomorphic. To this end we use an intermediary transition system for CCS, where the past is recorded; this appears to be a system of "trace computations, " which provides another means of define the same abstract domain of computations.

Details DOI

TCS Journal 1993 Journal Article

Observing localities

G. Boudol
I. Castellani
M. Hennessy
A. Kiehn

We introduce a refined version of observation for CCS which allows the observer to see the distributed nature of processes. Using several examples, we argue that a semantic theory based on such observations is not only intuitive but may also be of use when formalising the relationship between implementations and specifications. Technically, we show that the resulting theory of location equivalence is very similar to that of bisimulation equivalence, e. g. it can be characterised by a simple modal logic. A comparison with distributed bisimulations is also given.

Details DOI

TCS Journal 1988 Journal Article

Concurrency and atomicity

G. Boudol
I. Castellani

The overall intention of this work is to investigate the ability to regard a finite computation as a single event, in dealing with the semantics of concurrency. We propose a calculus of concurrent processes that embodies this ability in two respects: the first one is that of execution, the second that of operation. As usual, we formalize the execution of a process as a labelled transition relation. But our point is that at each step the performed action is a compound one, namely a labelled poset, not just an atom. The action reflects the causal and concurrent structure of the process, and we claim that the bisimulation relative to such transition systems brings out a clear distinction between concurrency and sequential nondeterminism. Next we introduce a second transition relation, formalizing the operation of a process on data. As in the usual semantics of sequential programs, a process operates on data by means of its terminated sequences of computations. Then we obtain atomic actions by abstracting the whole operation of a process as a single event. We show that this abstraction mechanism, together with the idea of compound actions, allows us to deal with a variety of synchronization and communication disciplines.

Details DOI