Relating communicating processes with different interfaces.
We present here an implementation relation intended to formalise the notion that a system built of communicating processes is an acceptable implementation of another base, or target, system in the event that the two systems have different interfaces. Such a treatment has clear applicability in the software development process, where (the interface of) an implementation component may be expressed at a different level of abstraction to (the interface of) the relevant specification component.Technically, processes are formalised using Hoare's CSP language, with its standard failures-divergences model. The implementation relation is formulated in terms of failures and divergences of the implementation and target processes. Interface difference is modelled by endowing the implementation relation with parameters called extraction patterns. These are intended to interpret implementation behaviour as target behaviour, and suitably constrain the former in connection to well-formedness and deadlock properties.We extend the results of our previous work and replace implementation relations previously presented by a single, improved scheme. We also remove all the restrictions previously placed upon target processes. Two basic kinds of results are obtained: realisability and compositionality. The latter means that a target composed of several connected systems may be implemented by connecting their respective implementations. The former means that, if target and implementation in fact have the same interface, then the implementation relation they should satisfy collapses into standard implementation pre-order.We also show how to represent processes and extraction patterns in a manner amenable to computer implementation, and detail a graph-theoretic restatement of the conditions defining the implementation relation, from which algorithms for their automatic verification are easily derived.
Introduction
The software development process often involves refining a high-level specification
into a lower-level or more concrete implementation.
In the process algebraic context [8, 16, 18], both specification and implementation
may be represented as processes, and the notion that a process Q implements
a process P is based on the idea that Q is more deterministic than (or
equivalent to) P in terms of the chosen semantics. In the following, we shall also
refer to such specifications as target or base systems.
J.Burton, M.Koutny and G.Pappalardo
The process of refining the target into the implementation also permits the
control structure of the latter to be changed. In such a case, Q is said to implement
P in the twofold sense that: (i) Q describes the internal structure of P
in a more concrete and detailed manner; and still (ii), if this new structure is
(conceptually) hidden, Q and P will exhibit the same behaviour at their external
interface, which is assumed to be the same for both. Indeed, the standard
notions of refinement, such as those of [8, 16, 18], are interested only in the behaviour
observable at the interface of processes, and require the interfaces of the
specification and implementation to be the same, so as to facilitate comparison.
Yet in deriving an implementation from a specification we will often wish to
implement abstract, high-level interface actions at a lower level of detail and
in a more concrete manner. For example, the channel connecting Q to another
component process may be unreliable, and so may need to be replaced by a pair
of channels, one for data and one for acknowledgments. Or Q itself may be liable
to fail, so that its behaviour may have to be replicated, with each new component
having its own communication channels to avoid a single channel becoming a
bottleneck [13] (such a scenario was one of the major historical motivations
behind the current work [11, 15]). Or it may simply be the case that a high-level
action of P is rendered in a more concrete, and hence more implementable, form.
As a result, the interface of an implementation process may exhibit a lower (and
so di#erent) level of abstraction to a specification process.
In the process algebraic context, dealing with this phenomenon of interface
di#erence necessitates the development of what Rensink and Gorrieri [17] have
termed a vertical implementation relation. This should correctly capture the
nature of the relationship holding between a specification and an implementation
whose interfaces di#er; and should collapse into the standard, horizontal one
whenever the interfaces happen to coincide.
Within the FD (failure-divergence) model of CSP [9], we have pioneered such
an approach in works like [11, 12, 15]), on whose results the present one introduces
major advances, as argued in the Conclusions. Our treatment deals with
interface di#erence using the notion of extraction pattern. Such a device interprets
the behaviour of a system at the level of communication traces, by relating
behaviour on a set of channels in the implementation to behaviour on a specific
channel in the specification. In addition, it allows the behaviour of an implementation
to be suitably constrained, in connection to, e.g., well-formedness of
input traces and deadlock properties. The set of all extraction patterns relating
the interface of the implementation process to that of the specification appears
as a formal parameter in the implementation relation we develop.
We now consider the potential applications of the approach outlined to ver-
ification, in order to deduce two light but natural restrictions which must be
placed upon any sensible vertical implementation relation, and are indeed met
by that presented in this work. Suppose the specification system is in the form
A is the set of events on which synchronization
among the P i components takes place. Correspondingly, let the implementation
system be Q In general, the communication
Relating Communicating Processes 3
interface need not be the same for each P i and Q i , but will be assumed to coincide
for Q and P . As a result, it would be possible to verify directly, using a
standard, horizontal relation, whether or not Q implements P .
However, we wish to verify that Q implements P using a compositional ap-
i.e., by verifying that Q There are two,
related, motivations for such a choice. To begin with, it gives us a means to tackle
the state explosion problem. Furthermore, it allows us to verify the correctness
of individual components in isolation, without needing to know in advance the
structure of the network in which they will be deployed. Hence the first requirement
for our implementation relation, i.e., that it should be compositional in the
said sense.
To introduce the second requirement, we remark that, once each Q i component
has been established to implement the respective P i , the composition Q is
known, by compositionality, to implement P according to the implementation
relation introduced. For the new relation to be meaningful, Q should also implement
P in a standard horizontal sense (recall that the interfaces of Q and
P are the same). In other words, we require that the implementation relation
'collapse' to a standard horizontal implementation relation, in the event that
the specification and implementation processes have the same interface (in our
approach, this means that all communication channels of the implementation
are 'uninterpreted'). We call this property accessibility or realisability.
In the following, in addition to presenting an implementation relation which
meets the criteria set out above, we also detail a graph-theoretic restatement
of the implementation relation conditions, from which we derive algorithms for
their automatic verification.
The paper is organised as follows. In the next section we introduce some
basic notions used throughout the paper. In section 3 we first introduce extraction
patterns - a central notion to defining the interface of an implementation.
Section 4 presents the implementation relation. Section 5 details how we may
represent extraction patterns in a manner amenable to computer
implementation, and develops results allowing automatic verification of the implementation
relation. Section 6 summarises the results and compares them with
other related works. All the proofs are included in the appendix.
Preliminaries
are represented in this paper using the failures-divergences model of
Communicating Sequential Processes (CSP) [9, 18] - a formal model for the
description of concurrent computing systems.
A CSP process can be regarded as a black box which may engage in interaction
with its environment. Atomic instances of this interaction are called actions
and must be elements of the alphabet of the process. A trace of the process is
a finite sequence of actions that a process can be observed to engage in. In this
paper, structured actions of the form b.v will be used, where v is a message and
b is a communication channel. For every channel b, b is the message set of b -
4 J.Burton, M.Koutny and G.Pappalardo
the set of all v such that b.v is a valid action. We define b} to be
the alphabet of channel b. It is assumed that b is always finite and non-empty.
The following notations are similar to that of [9] (below t, u, t 1 , t 2 , . are
traces; b is a are disjoint sets of channels; A is a set of
actions; and T , T # are non-empty sets of traces):
is the trace whose i-th element is a i , and length, |t|, is n.
is the trace obtained by appending u to t.
A # is the set of all traces of actions from A, including the empty trace, #.
is the set of all traces
denotes the prefix relation on traces, and t < u if t # u and t #= u.
is the prefix-closure of T .
- T is prefix-closed if
- t#B is a trace obtained by deleting from t all the actions that do not occur
on the channels in B.
. is an #-sequence of traces if
and strict if # T and f(#.
We use the model of CSP in which a process P is a triple (#P, #P, #P ) where
is a non-empty finite set of actions, #P - failures - is a
subset of #P # P(#P ), and #P - divergences - is a subset of #P # . Moreover,
denotes the traces of P . The conditions imposed on the
components of a CSP process are given below.
CSP1 #P is a non-empty and prefix-closed set.
CSP2 If (t, R) #P and S # R then (t, S) #P .
CSP3 If (t, R) #P and a #P satisfy t #a# /
#P then (t, R # {a}) #P .
CSP4 If t #P then (t # u, R) #P , for all u #P # and all R #P .
We will associate with P a set of channels, #P , and stipulate that the alphabet
of P is that of #P . Thus, we shall be able to identify P with the triple
(#P, #P, #P ) in lieu of (#P, #P, #P ).
A fundamental device to compare CSP processes in the failures-divergences
semantical model is the refinement order, #, defined so that Q # P if #Q #P
and #Q #P . Intuitively, this means that Q is at least as good, and perhaps
better, than P for actual deployment in any conceivable environment.
We assume that base processes are non-diverging CSP processes. This is the
only restriction placed upon base processes to be treated using the implementation
relation presented in section 4.
CSP operators For our purposes neither the syntax nor the semantics of the
whole standard CSP is needed. Essential are only the parallel composition of
processes and hiding of the communication over a set of channels. In the examples
we also use deterministic choice, P []Q, non-deterministic choice P #Q, renaming
of channels P [b # /b], and prefixing, a # P (see [9, 18] and also appendix A).
Parallel composition P#Q models synchronous communication between processes
in such a way that each of them is free to engage independently in any
Relating Communicating Processes 5
action that is not in the other's alphabet, but they have to engage simultaneously
in all actions that are in the intersection of their alphabet. Formally,
.
Parallel composition is commutative and associative; we will use P 1 #P n to
denote the parallel composition of processes P 1 , . , P n .
Let P be a process and B be a set of channels of P ; then P\B is a process that
behaves like P with the actions occurring at the channels in B made internal.
Formally, #(P\B) df
Hiding is associative in that (P\B)\B
Networks of processes Processes P 1 , . , P n form a network if no channel is
shared by more than two 's. We define P
to be the process obtained
by taking the parallel composition of the processes and then hiding all
interprocess communication, i.e., the process (P 1 #P n )\B, where B is the set
of channels shared by at least two di#erent processes P i . Network composition
is commutative and associative. As a result, a network can be obtained by first
composing some of the processes into a subnetwork, and then composing the
result with the remaining processes. Moreover, the order in which processes are
composed does not matter. In the failure model of CSP, where a process P is
identified with the pair (#P, #P ), the former property does not hold, whence the
need for the more complicated divergence model.
We can partition the channels of a process P into the input channels, in P ,
and output channels, out P . It is assumed that no two processes in a network
have a common input channel or a common output channel and that being an
input or output channel is preserved by network composition.
In the diagrams representing processes, outgoing arrows indicate output, and
incoming arrows indicate input channels. 1
3 Extraction patterns
In this section, we first explain the basic mechanism behind our modelling of behaviour
abstraction, and then provide a formal definition of extraction patterns.
Our examples here will deliberately be very simple, in order to better convey the
basic ideas rather than to demonstrate a wider applicability of our approach.
It should be noted that being an input or output channel of a process is, in general,
a purely syntactic notion, and no semantic properties can therefore be inferred.
6 J.Burton, M.Koutny and G.Pappalardo
Snd Buf
c d e
(a)
Snd # Buf #
c r
(b)
Snd # Buf #
c r
(c)
Fig. 1. Two base processes and their implementations.
Consider a pair of base processes, Snd and Buf, shown in figure 1(a). Snd
generates an infinite sequence of 0s or an infinite sequence of 1s, depending on
the signal (0 or 1) received on its input channel, c, at the very beginning of its
execution. Buf is a bu#er process of capacity one, forwarding signals received
on its input channel, d. In terms of CSP, we have:
Snd df
Buf df
where Snd i
Suppose that the signal transmission between the two processes has been
implemented using two channels, r and s, as shown in figure 1(b). The transmissions
on d are now duplicated and the two copies sent along r and s. That is,
Snd # sends the duplicated signal, while Buf # accepts a single copy of the signal
and passes it on ignoring the other one. Such a simple scheme clearly works as we
have
# Buf # . Suppose now that the transmission of signals is
imperfect and two types of faulty behaviour can occur: Snd 1
df
Snd #Stop and
df
Snd is Snd # with all the communication on channel
s being blocked. In other words, Snd 1 can break down completely, refusing to
output any signals, while Snd 2 can fail in such a way that although channel s
is dead r can still transmit the signals. 2 Since
1# Buf # it follows that Snd 2 is much 'better' an implementation
of the Snd process than Snd 1 . We will now analyse the di#erences between
the behavioural properties of the two processes and at the same time introduce
informally some basic concepts used subsequently.
We start by observing that the output of Snd 2 can be thought of as adhering
to the following two rules:
The transmissions over r and s are consistent w.r.t. message content (the
set of all traces over r and s satisfying such a property will be denoted by
Dom).
is reliable, but there is no such guarantee for s.
The output produced by Snd 1 satisfies the first rule, but fails to satisfy the
second one as its behaviour allows both channels to be blocked. To express this
could be used to model the following situation: in order to improve perfor-
mance, a 'slow' channel d is replaced by two channels, a high-speed yet unreliable
channel s and a slow but reliable backup channel r.
Relating Communicating Processes 7
di#erence formally we need to render these two conditions in some form of precise
notation.
To capture the relationship between traces of Snd and Snd 2 we will employ
an (extraction) mapping extr which for a trace over r and s returns the corresponding
trace over d. For example, keeping in mind that duplicates of signals
should be ignored by the receiving process, we have
#s.1, r.1#d.1#
#s.1, r.1, s.0#d.1, d.1#
Notice that the extraction mapping need only be defined for traces satisfying R1,
i.e., those in Dom. We further observe that, in view of R2, some of the traces in
Dom may be regarded as incomplete. For example, #s.1, r.1, s.0# is such a trace
since channel r is reliable and so the duplicate of s.0 (i.e., r.0) is bound to be
eventually be o#ered for transmission. The set of all other traces in Dom - i.e.,
those which in principle may be complete - will be denoted by dom. 3 For our
example, dom will contain all traces in Dom where the transmission on s has
not overtaken that on r. 4
Although it will play a central role, the extraction mapping alone is not
su#cient to identify the 'correct' implementation of Snd in the presence of faults
since What one also needs is an ability
to relate the refusals of Snd 1 and Snd 2 with the possible refusals of the base
process Snd. This, however, is much harder than relating traces. For suppose
that we attempted to 'extract' the refusals of Snd 2 using extr . Then, we would
have had
(#, {s.0}) #Snd 2 and extr(#,
#Snd.
This indicates that the crude extraction of refusals is not going to work. What
we need is a more sophisticated device, which in our case comes in the form of
another mapping, ref , constraining the possible refusals a process can exhibit,
on channels which will be hidden in the composed system Q, after a given trace
precisely, a sender process can admit a refusal disallowed by
ref (t) if the extracted trace extr(t) admits in the target process the refusal of all
communication on the corresponding channel and, moreover, the trace t itself
is complete, i.e., t # dom. For the example at hand, this roughly amounts to
stipulating that an unfinished communication cannot at the same time refuse
both r.0 and r.1.
3 In general, Dom = Pref (dom), meaning that each interpretable trace has, at least
in theory, a chance of being completed.
4 Another example is that if the whole sequence of events a1 , . , ak is extracted to a
single event a, i.e., #a1 , . , a i # for i < k and #a1 , . , ak #a#, then we do
not consider a transmission complete unless the whole sequence a1 , . , ak has been
transmitted.
8 J.Burton, M.Koutny and G.Pappalardo
Finally, it should be stressed that ref (t) gives a refusal bound on the sender
side (more precisely, the process which implements the sender target process).
But this is enough since if we want to rule out a deadlock in communication
between the sender and receiver (on a localised set of channels), it is now possible
to stipulate on the receiver side that no refusal is such that, when combined with
any refusal allowed by ref (t), it can yield the whole alphabet of the channels
used for transmission.
Networks of processes. Further clarity on the intuition behind the detail of the
implementation relation presented in section 4 and the detailed description of
extraction patterns presented below with respect to the notion of constraining
refusal bounds can be gleaned from considering the specification and implementation
systems discussed in section 1. There we considered a specification
system and an implementation system
We wish to ensure that (t, R) #Q implies that
(t, R) #P . Relating traces is technically not too di#cult using the extraction
mapping introduced above. However, to ensure that the above implication holds
is more di#cult.
In general, we must find those component failures from each of the Q i which
may contribute to a failure of the composed system Q. These components will
contribute to a failure of Q if the union of their refusal sets contains all actions
which are hidden during the composition to get Q. It is obviously di#cult to
check local failures for this property and it is this problem that the use of refusal
bounds deals with. In general, if two component processes keep their refusals
within the bounds specified, this will ensure that their composition will always be
able to execute at least one action on the channels on which they were composed
and so each state reached will always be unstable due to the fact that an internal
action is enabled and so none of the local failures will contribute to a failure in
the composed process.
If a local failure may contribute to a global failure of Q, then that local failure
must correspond in some way to a local failure in the corresponding specification
component. In general, the approach taken is to say that comparison will only
take place when behaviour in the implementation component is 'complete' in
some sense. When behaviour is not complete, then the refusal bounds may not
be breached, meaning that local failures where behaviour is not complete cannot
play a role in forming a failure of the system Q. This is sensible anyway, since
the fact that behaviour is incomplete implies that implementation of a high-level
action has been begun but has not been completed and we obviously do not wish
to allow our system to deadlock in the middle of implementing an action that is
atomic at the high-level.
In general, the refusal bounds may be thought of as ensuring a kind of liveness
or progress on sets of channels upon which composition will occur when
implementation components are composed to get the full system Q. Since these
channels are to be composed upon and so hidden, the progress enforced manifests
itself in the final system as the occurrence of an internal transition, which
leads to instability of the states in which those internal transitions are enabled.
Relating Communicating Processes 9
This then means that these states will not contribute a failure of Q. If we may
not be able to force progress after a complete behaviour, then we ensure that
progress will not be possible on the corresponding channel in the specification
component. Here, lack of progress on internal channels leads to stability and the
fact that the relevant state will give rise to a failure of P .
3.1 Another example
The previous example can be thought of as modelling a fail-stop communication
between two processes (s being a fail-stop channel). The next example is di#erent
in that it employs a fault tolerant mechanism based on message retransmission.
It is used to illustrate the point that implementations are not forced to preserve
the intuitive direction of the transfer of messages.
As before, suppose now that the communication on d has been implemented
using two channels, r and s, but now r is a data channel, and s is a feedback
channel used to pass acknowledgments. It is, moreover, assumed that a given
message is sent at most twice since a re-transmission always succeeds. This leads
to a simple protocol which can be incorporated into suitably modified original
processes. The resulting implementation processes shown in figure 1(c), Snd #
and Buf # , are given by:
Snd # df
where buf, Snd # i and buf # i are auxiliary processes defined thus:
df
buf df
df
It may be observed that Snd
One way of
showing this would be to compose the two pairs of processes and prove their
equality using, e.g., CSP laws [9]. This would be straightforward for
Snd# Buf,
but less so for Snd
at least by hand. However, the results in this
paper allow us to proceed compositionally: we show that Snd # and Buf # are
implementations of the respective base processes according to suitable extraction
patterns, and then derive the desired relationship using general results developed
in section 4.
3.2 Formal definition
The notion of extraction pattern (introduced in [11, 12], and slightly modified as
well as simplified here 5 ) relates behaviour on a set of channels in an implementa-
5 What we define here is a basic extraction pattern in the terminology of [11]; [12] also
allowed sets of target channels. Moreover, one can also use a partial inverse of the
extraction mapping.
J.Burton, M.Koutny and G.Pappalardo
tion process to that on a channel in a target process. It has two main functions:
that of interpretation of behaviour necessitated by interface di#erence and the
encoding of some correctness requirements.
An extraction pattern is a tuple ep df
satisfying the
EP1 B is a non-empty set of channels, called sources and b is a channel, called
target.
EP2 dom is a non-empty set of traces over the sources; its prefix-closure is
denoted by Dom.
EP3 extr is a strict monotonic mapping defined for traces in Dom; for every t,
extr(t) is a trace over the target.
EP4 ref is a mapping defined for traces in Dom such that for every t # Dom:
- ref (t) is a non-empty subset-closed 6 family of proper subsets of #B
- if a #B and t #a# /
# Dom then R# {a} # ref (t), for all R # ref (t).
As already mentioned, the mapping extr interprets a trace over the source
(in the implementation process) in terms of a trace over a channel b
(in the target process) and defines functionally correct (i.e., in terms of traces)
behaviour over those source channels by way of its domain. The mapping ref
is used to define correct behaviour in terms of failures as it gives bounds on
refusals after execution of a particular trace sequence over the source channels.
dom contains those traces in Dom for which the communication over B may be
regarded as complete, and processes may violate the constraint on refusals given
by ref only for such traces.
The extraction mapping is monotonic as receiving more information cannot
decrease the current knowledge about the transmission. #B /
# ref (t) will be
useful in that for an unfinished communication t we do not allow the sender
to refuse all possible transmission. The second condition in EP4 is a rendering
in terms of extraction patterns of a condition imposed on CSP processes that
impossible events can always be refused (see CSP3).
The various components of the extraction patterns can be annotated (e.g.,
subscripted) to avoid ambiguity and, unless stated otherwise, di#erent extraction
patterns will have disjoint sources and distinct targets. Moreover, we lift
three of the notions introduced above to any set of extraction patterns Ep df
df
- Dom Ep and dom Ep are the set of all traces t over channels
such that respectively t#B i # Dom i and t#B i # dom i , for every i # n.
and, for every t#a# Dom Ep with a #B i , extr Ep (t#a#) df
extr Ep (t) # u, where (possibly empty) u is such that extr i (t#B i
u. Note that such a u is well defined since extr i is monotonic.
Finally, for any mapping ref and t # Dom, we will denote by ref (t) the set of
all X #B such that, for every Y # ref
6 A family of sets X is subset-closed if Y # X # X implies Y # X .
Relating Communicating Processes 11
Uninterpreted channels and identity extraction patterns Not all channels will
require an extraction pattern as such to interpret their behaviour. We shall
call these channels uninterpreted (other channels being called interpreted ). In-
tuitively, these channels have the same interface in both implementation and
specification.
An uninterpreted channel c will be identified by a special 'degenerated' extraction
pattern
df
extraction mapping id is the
identity on #c # , and the ref component is left unspecified.
Another extraction pattern In order to demonstrate that Snd # and Buf # are
implementations of respectively Snd and Buf, we will need an extraction pattern
twice . We also observe that channel c is an identity channel as described above.
For the ep twice
extraction pattern, B are the source channels and
b df
d is the target channel; moreover
{ack , nak}. The
remaining components are defined as follows, where t # dom and t # u # Dom:
dom df
extr(t) #d.v# if
or
extr(t) if
Intuitively, we can extract #d.1# from the following two sequences of communi-
cations: #r.0, s.ack# and #r.0, s.nak , r.0# (and similarly for #d.1#). Thus a valid
trace in Dom is one which is a concatenation of a series of 'complete' segments
of this kind, possibly followed by an initial fragment of one of them. Any trace
for which the latter is true, is incomplete and belongs to Dom -dom; otherwise
it belongs to dom.
4 The implementation relation
Suppose that we intend to implement a base process P using another process
Q with a possibly di#erent communication interface. The correctness of the
implementation will be expressed in terms of two sets of extraction patterns, In
and Out . The former (with sources in Q and targets in P ) will be used to relate
the communication on the input channels of P and Q; the latter will serve a
similar purpose for the output channels.
Let P be a base process as in figure 2 and, for every
df
) be an extraction pattern such that B i #B #, for all
We will denote by In the set of the first m extraction patterns ep i
, and
J.Burton, M.Koutny and G.Pappalardo
bm
bm+n
Bm
Bm+n
Fig. 2. Base process P and its implementation Q.
by Out the remaining n extraction patterns. Moreover, All df
In #Out and Idch
will denote the set of all uninterpreted channels b i .
We then take any process Q with the input channels B 1 #Bm and output
channels Bm+1 #Bm+n , as shown in figure 2, where thick arrows represent
sets of channels. For such a process, we denote:
is the set of all traces of Q which belong to DomAll .
#Dom Q and #dom Q are the sets of those failures of Q in which the trace
component belongs to DomAll and domAll , respectively.
Intuitively, # Dom Q - which is subsequently referred to as the domain of Q - is
the set of those traces of Q which are of actual interest and, consequently, #Dom Q
is the set of failures of actual interest too. Given a failure (t, R) #Dom Q, we
will say that an interpreted channel b i is blocked if
and denote this by b i # Blocked(t, R). Note that in both cases this signifies that
the refusal bound imposed by the ref i has been breached.
We then call Q an implementation of P w.r.t. sets of extraction patterns In
and Out , denoted Q # In
Out P , if the following hold.
DP If t is a trace of Q such that t#in Q # Dom In , then t # Dom Q.
GE If (t i ) i#N is an #-sequence in # Dom Q, then (extr All (t i )) i#N is also #-sequence.
LC If (t, R) #Dom Q and b i # Blocked(t, R), then t#B i # dom i .
RE If (t, R) #dom Q, then (extr All (t), #Blocked(t, R) # (R #Idch)) #P .
We interpret the above conditions in the following way. DP expresses the
domain preservation property, which says that if a trace of Q projected on the
input channels can be interpreted by In, then it must be possible to interpret
the projection on the output channels by Out . Note that such a condition is
a simple rely/guarantee property in the sense of [7]. DF can be interpreted as
divergence freedom within the domain of Q (recall that CSP divergences signify
totally unacceptable behaviour). simply states that applying trace extraction
to the domain of Q yields traces of P . GE states that an unboundedly growing
sequence of traces in the domain of Q is a sequence of traces unboundedly
growing after extraction (notice, however, that we place no restriction on the
relative growth of the #-sequences means that
Relating Communicating Processes 13
going outside the bounds of allowed refusals indicates that the communication
on a given interpreted channel may be seen as locally completed (notice also that
the communication on any uninterpreted channel is always seen as locally com-
pleted). Finally, RE states a condition for refusal extraction, which means that if
a trace is locally completed on all channels, then any blocking of an interpreted
channel of P in Q is transformed into the refusal of its whole alphabet in P ;
moreover, the refusals on the uninterpreted channels in Q should be matched in
4.1 Realisability and compositionality
A direct comparison of an implementation process Q with the corresponding
base process P is only possible if there is no di#erence in the communication
interfaces, and all communication is interpreted in exactly the same way. This
corresponds to the situation that all of the channels of Q (and of P ) are unin-
terpreted. In such a case, we simply denote Q # P and then we can directly
compare the semantics of the two processes in question. Having observed that
if all channels are uninterpreted, DF states that reduces to
Theorem 1 (realisability). If
That is, the implementation relation 'collapses' to standard CSP refinement
in the event that all channels are uninterpreted. And the next result demonstrates
that the implementation relation is compositional in the sense that it is
preserved by the network composition operation. Taken with the above realis-
ability result, we have met both of the requirements stated in the introduction,
and so have a means of compositional verification in the event that corresponding
specification and implementation component processes have di#erent interfaces.
Theorem 2 (compositionality). Let K and L be two base IO processes whose
composition is non-diverging, as in figure 3, and, for X # {C, D,E,F, G, H}, let
EpX be a set of extraction patterns whose targets are the channel set X. Then
EpG#EpH L =#
K# L .
F
G
Fig. 3. Base processes in theorem 2
14 J.Burton, M.Koutny and G.Pappalardo
Hence the implementation relation is preserved through network composi-
tion, and the only restriction is that the network of the base processes should
be designed in a divergence-free way. However, the latter is a standard requirement
in the CSP approach (recall again that divergences are regarded as totally
unacceptable).
For the example in section 3, it can be shown that Snd # ep c
twice
Snd and
Buf. Hence, by theorem 2 and
Snd
and so, by theorem 1, Snd
5 Verifying the implementation relation
Extraction patterns and processes may be infinite objects. We therefore need a
means to represent them in a finite way in order to allow a computer implemen-
tation. To deal with processes we will use the standard device of a transition
system, while extraction patterns will be represented by the novel notion of an
extraction graph.
5.1 Communicating transition systems
For the purposes of this paper we simply assume that a process is given in
the form of a labelled transition system, without worrying about how such a
representation has been obtained. 7
A communicating transition system is a tuple CTS df
is a set of states (nodes); v 0 # V is the initial state; C and D are finite
disjoint sets of channels (C will represent input and D output channels); and
(#C#D#})V is the set of labelled directed arcs, called transitions,
where # is a distinguished symbol denoting an internal action. We will use the
following
- If (v, a, w) # A, we denote v
a
-# w and a # en(v), calling a enabled at v.
belongs to the set V stb of stable states.
an
# w, we denote v # w or v t
# v, for every v # V .
We shall assume that a CTS is finite, i.e., both V and A are finite.
The implementation relation which we want to verify algorithmically is expressed
in the denotational semantics of CSP, and so we must know how to derive
information on divergences, traces and failures from a given CTS. For a communicating
transition system
7 It can be obtained, e.g., using the operational semantics defined for CSP in [18].
Relating Communicating Processes 15
to be a tuple such that the following hold (below A df
Note that a divergence is represented by a cycle composed only of #-labelled
transitions which is reachable from the initial state.
Proposition 3. Let CTS be a communicating transition system as above.
1. PCTS is a CSP process.
2.
#}, provided that #.

Figure

4 shows the graphs of four communicating transition systems. It is
not di#cult to check that:
For a base process P , a CTS representation CTS will later be modified by
applying the normalisation procedure detailed in [18]. Its result can be given
as a finite CTS denoted by CTS n which is deterministic (i.e., if v
a
-# w and
a
a
-# w then a # ), together with
a mapping for its nodes, #, such that:
where V are the nodes of CTS , and v 0 and p 0 are respectively the initial states
of CTS and CTS n .
5.2 Extraction graphs
We now turn to the representation of extraction patterns. An extraction graph
is a tuple EG df
is a non-empty finite set of
channels; b is a channel; V is a set of nodes; A # V  (#B #b # )  V is a set of
labelled arcs; v 0 # V is the initial node; # is a mapping returning for every node
in V a non-empty subset-closed family 8 of proper subsets of #B; and V #
Intuitively, # corresponds to ref , and V # indicates traces in dom. We will use
the following notation:
- If (v, a, t, w) # A, we denote v
a:t
an :t n
8 As we intended to concentrate on basic ideas behind verification algorithms, we
simplified several issues which a practical implementation would need to address,
e.g., each #(v) could be represented by the set of its maximal elements.
J.Burton, M.Koutny and G.Pappalardo
CTS snd
d.1 d.1
CTS buf
d.1 d.1
r.1
r.1
e.1
r.1
Fig. 4. Communicating transition systems representing CSP processes used throughout
the paper (initial states have white centres).
-# v, for every v # V .
We then impose the following restrictions on every node v
EG1 There is w
EG2 If v
a:t
-# w and v
EG3 If R #(v) and a #B are such that there is no t satisfying v
-#, then
We now define the extraction pattern an extraction graph represents. For
an extraction graph is a set of traces and
df
given in the following way:
Relating Communicating Processes 17
u:t
- By EG2, for every u # DomEG , there are unique t and v such that v 0
u:t
v.
We then set extr EG (u) df
From the point of view of practical implementation, we will be interested only
in those extraction graphs which are finite, i.e., have a finite number of nodes V
(note that the finiteness of A follows then from #B being finite and EG2).
Proposition 4. ep EG
is an extraction pattern, and
Conversely, one can easily see that for every extraction pattern ep there
is an extraction graph EG such that
. For the identity extraction
pattern
, the corresponding extraction graph EG c will have the mapping #
#c}. The extraction
pattern ep twice defined in section 3.2, can be represented by the extraction graph
EG twice , shown in figure 5. It is easy to check that ep EG twice
twice and
. For example, that t df
belongs to the domain Dom
of ep twice
follows from the existence of the path
in EG twice . Moreover, we have
P({r.0, r.1}), and t /
# dom since v 1 # V # .
v1 and v3 P({r.0, r.1})
v2 P({s.ack , s.nak , r.1})
v4 P({s.ack , s.nak , r.0})
Fig. 5. Extraction graph EG twice , where V # df
representing the extraction pattern
twice .
In the rest of the paper, we will assume that we can extract at most one
event out of a single event over the source channels, i.e., for every extraction
mapping and a trace t #a# in its domain,
J.Burton, M.Koutny and G.Pappalardo
In terms of extraction graphs, this means that |t| # 1 whenever v
a:t
-# w. The
above assumption has been introduced to simplify the presentation; it could
be omitted at the cost of slightly complicating (but not losing) the subsequent
results.
5.3 Unambiguous CTSs of implementation processes
Extraction patterns and so extraction graphs are defined for channels in a base
process P and channels in an implementation process Q. As a result, more than
one EG will usually be required to interpret the behaviour of the implementation
process Q as a whole. Moreover, it is possible that the CTS representing Q will
be ambiguous (in the sense explained below) with respect to interpretation in
terms of the EGs.
Let us again consider a base process Buf modelling a bu#er of capacity
one, with input channel d and output channel e, defined in section 3.1, which is
modelled by the communicating transition system CTS buf shown in figure 4. Let
us also consider two extraction patterns,
and
, given by the extraction
2. The first extraction graph,
df
is the identity extraction graph for the uninterpreted channel d.
The second one, over the sources {r, s} and target e, is given in figure 6. Note
that unlike in our previous example, it is now the input channel of Buf which is
uninterpreted, while the communication on the output channel, e, is implemented
using a simple 'ping-pong' communication protocol.
w0 P({s.ack , r.0}) # P({s.ack , r.1})
w1 and w2 P({r.0, r.1})
Fig. 6. Extraction graph EG 2 , where V # df
We would like to verify the implementation conditions, with respect to ep 1
and
, for a process Q such that in Q df
{d} and out Q df
{r, s}, and whose
behaviour is described by the communicating transition system CTS shown in
figure 7(a), i.e., Although it is not di#cult to see that Q # ep 1
Buf,
it may not be clear what needs to be done to verify this using communicating
transition systems and extraction graphs. In particular, suppose that we want
to verify that possible attempt
would be to replace each of the arc annotations in CTS by its 'extracted' version
given by the corresponding extraction pattern. This could be done for all the
actions except s.ack from which we can extract either #e.0# or #e.1#, depending
on the previous actions executed by the process. Thus CTS is an ambiguous
Relating Communicating Processes 19
representation of Q w.r.t. the extraction graph EG 2 . Note that the problem is
caused by our wish to represent an extraction mapping (from traces to traces)
in terms of individually labelled arcs, and so a node in a CTS needs to encode
the appropriate history of reaching it from the initial state. But, in our case, x 3
can reached in two di#erent ways
d.0
d.1
which imply di#erent interpretation of the arc x 3
solution we propose
is to remove this ambiguity, by suitably modifying CTS . More precisely, we
split the node x 3 of CTS and separate the two arcs incoming to it, obtaining
shown in figure 7(b). We can now unambiguously interpret each of the arc
annotations, which leads to the graph G shown in figure 7(c). To verify that
holds, it now su#ces to check that the traces generated by G are also generated
by CTS buf .
(a)
x3
d.1 d.1
(b)
d.1 d.1
(c)
Fig. 7. Disambiguating an implementation of a bu#er of capacity one.
The following algorithm makes the above construction precise, generating an
equivalent unambiguous CTS, from a given CTS and a set of extraction graphs.
Algorithm 1. For
df
) be
extraction graphs such that the B i 's are mutually disjoint and the b i 's distinct.
Moreover, let communicating transition system such
that . The algorithm generates
a communicating transition system CTS u , in two steps.
J.Burton, M.Koutny and G.Pappalardo
Step 1: We first generate a labelled directed graph G, with the set of nodes
be a node in G. The
arcs outgoing from q are derived from those outgoing from v, and for each arc
a
-# w in CTS we proceed according to exactly one of the following four cases.
1. . Then we add a transition q
We also set extr(q, #) df
2. a # and there is an arc v i
a:t
-# w i in EG i , for some i # 1. 9 Then we add
a transition q
a
We also set extr(q, a) df
#, and extr(q, a) df
3. a #C and there is no t and w i such that v i
a:t
we do nothing.
4. a #D and there is no t and w i such that v i
a:t
we mark q as an unfinished node (each node is assumed to be finished at the
beginning).
Step 2: From G we obtain a communicating transition system CTS u with the
same channels as CTS , by taking q 0
df
as the initial node, and
then adding all the nodes reachable from q 0 , together with all the interconnecting
transitions. If any of the reachable nodes is marked as unfinished, we reject
CTS u . 11
The above algorithm will be executed on the CTS representation of the implementation
process Q. Its main characteristic is that the definition of the nodes
allows the unambiguous interpretation of the arc labels through the extraction
mappings (c.f. proposition 5). In practice, one can avoid generating the whole
graph G, by performing a depth first search starting from the initial node q 0 .
Then only the nodes of CTS u will be visited.
The graph G for the example in figure 6 is shown in figure 8(a), where the
#'s indicate unfinished nodes. After restricting ourselves only to the relevant
subgraph (comprising nodes reachable from the initial one), we obtain the graph
shown in figure 8(b) which is isomorphic to CTS # obtained informally before.
Note that extr((x 3 ,
We may now state why CTS u can be regarded as unambiguous.
Proposition 5. Let All be the set of extraction patterns generated by the EG i 's.
If q 0
ak
-# q k in CTS u and
extr All
df
9 There can only be one such EG i since the B i 's are mutually disjoint.
Note that extr(q, a) is a well defined single action by EG2 and (2).
11 Since this means that the traces generated by CTS u do not satisfy the condition DP
(c.f. the proof of proposition 6).
Relating Communicating Processes 21
(a)
d.1 d.1
d.1 d.1 d.1 d.1
(b)
d.1 d.1
Fig. 8. Applying disambiguating algorithm.
5.4 Checking the implementation conditions
In this section, we will outline how to check the implementation conditions,
formulated in terms of the denotational semantics of CSP, using communicating
transition systems and extraction graphs. We will assume the following:
Idch and the ep i
s are as in section 4.
are communicating transition systems representing P and
- For every i # m+ n, EG i is an extraction graph such that ep EG i
CTS u is a disambiguated version of CTS Q as in algorithm 1, with the initial
state q 0 .
is the normalised version of CTS P (see section 5.1), with the initial
state p 0 , and # is the mapping given in (1).
We first obtain that testing for DP is done while generating CTS u , and
testing for DF amounts to checking for the presence of # -loops in the graph of
CTS u .
22 J.Burton, M.Koutny and G.Pappalardo
Proposition 6. Q satisfies DP and DF i# CTS u has not been rejected (see
Step 2 of algorithm 1), and there are no nodes v and w in CTS u such that
v.
From now on, we assume that CTS u has been successfully generated and
does not contain any # -loops, and so DP and DF hold for Q.
A relation sim # VCTS u  VCTS n is a simulation for CTS u and CTS n if
and, for every (q, p) # sim,
a
#extr(q,a)#
Proposition 7. Q satisfies there is a simulation for CTS u and CTS n .
Note also that since CTS n is deterministic and # -free, if there exists a simulation
for CTS u and CTS n , then there exists the smallest one, sim min .
One can attempt to construct the minimal simulation sim min , by a depth-first
traversal of the product VCTS u  VCTS n , starting at (q 0 ,
the arcs given by the first component in the nodes representing the product. If
the construction is successful, the set of all the nodes reachable from (q 0 ,
gives the minimal simulation.
We will now additionally assume that Q satisfies TE. Then, testing for the
next implementation condition, GE, amounts to checking for extracted # -loops
in the graph of CTS u .
Proposition 8. Q does not satisfy GE i# there are nodes v 1 , . ,
in CTS u such that v 1
Finally, for every stable state
denote the set of all interpreted channels b i such that
Proposition 9. Q satisfies LC and RE i# the following are satisfied, for every
stable state
1.
2. (q, p) # sim min and v
(for all 1 # n) implies that there is
A #(p) satisfying (#Blocked(q) #Idch - en(q))) # A = #.
The first condition in the last proposition can by checked by traversing the
graph of CTS u , while the second condition can be checked on the occasion of
testing for TE.
Relating Communicating Processes 23
6 Conclusions
In this work we have investigated the notion that a system (the implementation)
implements another one (the base or specification), in the event that their interfaces
di#er. Such an issue has an obvious interest with respect to system design
and development, in which interface refinement is often a major aspect of the
added detail provided by the implementation compared to the specification.
The proposed treatment is based upon the combined use of:
- The standard CSP process model [9, 18], in which we describe both specifications
and implementations.
- The notion of extraction pattern, aimed to capture the semantics of the
interface refinement by which specification and implementation di#er.
- An implementation relation, required to hold between the behaviour of the
specification and that of the implementation, after the latter has been interpreted
according to the extraction patterns that describe how their respective
interfaces di#er.
On all the above aspects, the present work significantly extends our previous
work [11, 12, 5]: the class of admissible specifications has been enlarged to include
any, non-diverging, CSP process; the definition of extraction pattern has
been technically improved; and the multiple implementation relation schemes
previously proposed have been unified into a single one. Furthermore, the latter
appears to be most appropriate as the vertical implementation relation for CSP,
given that, by realisability (theorem 1), it collapses into the standard horizontal
implementation of [9]. In other words, an implementation in the sense of this
work turns out to be an implementation in the standard sense, as soon as it and
its intended specification possess the same interface (i.e., no interface refinement
has actually been performed, and the extraction patterns in the implementation
relation are the identity ones).
It is worth noting that the implementation relation has been 'trimmed', in
the sense that its 'weak' and `strong' counterparts of [12] were in fact too much
so. This was immaterial as to the restricted base process class treated there,
but prevented a straightforward extension of that approach to encompass all
non-diverging base process, as we manage to do now.
Our implementation relation has also been shown to be useful for verifica-
tion, for it enjoys a kind of compositionality, in that a specification composed
of several connected systems may be implemented by connecting their respective
implementations (theorem 2). This means that the process of verification
may deal separately with individual component processes. This avoids a major
cause of the state explosion problem, and permits a bottom-up style reuse of
verifications carried out separately for specific components.
In the framework at hand, in which interfaces of the implementation and
the specification may di#er, compositionality, together with realisability, ensures
that the specification can actually be built by 'plugging' the implementation into
a suitable environment. A technical treatment of this issue has not been provided
here, for it would essentially adhere to the lines of our work [11].
J.Burton, M.Koutny and G.Pappalardo
Finally, in the present work we build on the preliminary results of [4] (which
was based on older implementation relations), and develop e#cient algorithms
for automatically verifying the present implementation relation. In this pro-
cess, we take further advantage of compositionality, which allows us to verify
each component of an implementation system separately, against the respective
specification component. This avoids, now from the point of computer-aided
verification, one of the great sources of the state explosion problem, i.e., the
generation of a state space which is a (substantial) subset of the product of all
the component state spaces.
As the basis for mechanical verification, we render both processes and extraction
patterns as graphs (communicating transition systems and extraction
graphs, respectively). This enables us to establish a graph-theoretic characterization
of the implementation relation, from which we directly derive e#cient
algorithms for the modular verification of the conditions DP, DF, TE, GE, LC,
RE whose conjunction amounts to the relation as a whole.
Future work will explore possibilities for further optimisation, as well as including
examples and a case study to evaluate the performance of the verification
algorithms in practice. Envisaged application areas range over the entire field of
distributed systems; in particular, fruitful results can be expected in the realm of
fault tolerance, exploiting the experience accrued from our analysis of N-Modular
Redundancy [11] and Coordinated Atomic Actions [6].
Related work We now compare the work presented in this paper with other
approaches whose goal is similar or somehow related.
Looking at the general issue of behaviour abstraction, some approaches (e.g.,
[2]) describe system behaviour by sequences of state tuples with an internal
component; they then require that, for every possible state sequence of a correct
implementation, there should exist one of the specification such that the two
sequences coincide after deleting the internal state component. A similar treatment
is presented in [10], using infinite action sequences (i.e., infinite traces)
instead of state sequences; the interface of the specification must be a subset of
the interface of the implementation, and it is required that every trace of the
implementation can be turned into one of the specification by deleting actions
not in the specification's interface. These two approaches and other comparable
ones (like, e.g., [14, 20]) are based on abstraction by hiding. In contrast, our notion
of abstraction is essentially based on the interpretation of traces over a set
of channels, as traces over another channel. Abstraction by hiding is certainly
useful but, unlike our notion of abstraction by interpretation, does not cater for
interface refinement, an essential tool for system design.
The interface displacement approach proposed in [3] has interesting similarities
with our work: (1) their interface transducers play a role comparable to
that of our disturbers and extractors of [11]; (2) both treatments constrain the
system's and the environment's mutual refusals.
The essential di#erence is that the treatment of [3] is geared to the refinement
of a specification compound system, whose components interact through an in-
terface, into a compound implementation, whose components interact through a
Relating Communicating Processes 25
di#erent (typically refined) interface. This refinement is then validated by checking
that the interface change is acceptable in some appropriate sense, and, above
all, that the compound implementation is correct with respect to the compound
specification. This notion of correct implementation is however a traditional (hor-
izontal in the words of [17]) one, for compound specification and implementation
have exactly the same interface, the (di#erent) interfaces where their respective
components interact being hidden. Essentially, in the interface displacement, it
is possible to compare only processes at one side of the interface; the addition
or removal of the interface transducers serves as the parameter of the interface
refinement.
Abstraction and refinement are clearly complementary and apt to be related,
once the formal framework to work in is selected. However, it should be noted
that in many refinement-based approaches, such as that of action refinement
dating back to [1], every high level action must be refined into a precise behaviour
made up of low level actions. It would appear, then, that this kind of
refinement is mainly suited for the design of a well-identified implementation
from a specification. It can, for example, be employed in contexts where the implementor
decides to replace any actions a and b performed by the specification,
by the sequences a 1 a 2 a 3 and b 1 b 2 b 3 by the implementation.
While we do not see any reason why abstraction could not be used in a
similar way, we believe it also a#ords a distinct benefit. It allows one to stipulate,
for example, that whenever an implementation performs any of a i and a j for
actions occur between them, this should be
construed as a occurring at the abstract level. This is clearly suited to modelling
the relative unpredictability of a fault-prone environment in important fault-tolerant
applications like N-Modular Redundancy, as we did, e.g., in [11]. It is
di#cult to see how similar accomplishments could be performed within most
treatments adhering to the action refinement approach.
Similar remarks can be found in Rensink and Gorrieri's work [17], which
aims at overcoming these and other limitations, while staying within the realm
of action refinement. Their solution is, like ours, based upon a parametric vertical
implementation relation. Their parameter is a refinement function; conversely,
ours is essentially an abstraction mapping. They maintain their approach has
some decisive advantages over other action refinement based ones:
- flexibility: it allows multiple implementations for a given specification, and
does not dictate a strict ordering for the low level actions implementing an
high level one;
- simplicity: it does not require the introduction of a concurrency model more
complex than any of the standard interleaving ones;
- the vertical implementation relation collapses to a standard horizontal one
when the refinement is the identity;
- deadlock properties carry over from the abstract to the concrete level;
- it allows compositional verification in the same sense as our approach;
- it can be endowed with a decision procedure for verification of the implementation
relation.
26 J.Burton, M.Koutny and G.Pappalardo
We have highlighted these merits simply to remark that they also characterize
the approach of the present paper. We do lack, however, at least for the time
being, a proof system where the implementation relation can be decided.
Nonetheless, our approach and that of [17] di#er greatly from a technical
point of view. This is a consequence of the di#erent concurrency models em-
ployed. In this respect, it can be noted that our CSP model has the advantage
of being firmly rooted in intuitive notions like traces and refusals. This has two
appealing consequences: (i) our abstraction mappings can be defined in a natural
fashion, directly over traces and refusals, (ii) we do not need to change the
model in any way for our purposes. On the other hand, the treatment of [17] is
based upon bisimulation semantics and refines actions into processes, as is customary
in action refinement. As a result, in order to regain flexibility, it has to
tweak horizontal bisimulation quite a bit in order to obtain the intended vertical
version. Of course, any preference for either approach, in this respect, may be a
matter of taste.
A crucial issue for comparison, instead, would be to assess to what extent the
approach of [17] is applicable to fault-tolerant systems in the sense highlighted
above for ours (see also [11]). The fact that in [17] actions can only be refined
into deterministic (# free) processes could indicate that some limitations can be
expected in this field of application.
Finally with respect to [17], we mention the fact that their decision procedure
may be used only in very restricted cases, since, during verification, when a
concrete action is explored in the implementation it may be necessary to 'guess'
which abstract action it is refining, unless the restrictions are imposed.
It is also interesting to compare the implications of the di#erences between
the concurrency models underlying our work and [10]. Both models are action-
based, but [10] employs infinite traces and only caters for asynchronous com-
munication. In contrast, our CSP model has finite traces and refusals, permitting
asynchronous as well as synchronous communication, and enabling deadlock
properties to be described. As a result, no artificial constraint has to be placed on
the behaviour of the implementation system: faulty channels need not communicate
asynchronously, and faulty modules (within fault-tolerant implementations)
need not be processes of a restricted class (e.g., IO). This is certainly desirable
in order to reflect faithfully the unpredictable nature of faults, but is impossible
in the model of [10] or in other models of asynchronous communication. On
the other hand, it is fair to add that liveness, in the sense of [10] or temporal
logic, cannot be expressed with our finite traces; however, the ability to place
constraints on refusals is generally deemed a reasonable alternative in the CSP
philosophy.
The approach of [19] to the formal analysis of fault-tolerance is quite di#erent
from ours, which basically provides a criterion whereby a system, albeit fault-
prone, may be abstractly viewed as an implementation of a correct specification
system. In contrast, in [19] the system under study (modelled using the CSP
trace model) may embed fault-prone components, but its externally observable
behaviour must be correct itself, without the filter of abstraction.
Relating Communicating Processes 27

Acknowledgments

The first author was supported by an EPSRC grant. We would also like to thank
Marta Pietkiewicz-Koutny for her comments on an earlier version of this paper.



--R

Towards Action-Refinement in Process Algebras
The Existence of Refinement Mappings.
Refining Interfaces of Communicating Sys- tems
Verifying Implementation Relations in the Event of Interface Di
Implementing Communicating Processes in the Event of Interface Di
Compositional Development in the Event of Interface Di
Enhancing the Tractability of Rely/Guarantee Specifications in the Development of Interfering Operations.
Algebraic Theory of Processes.
Communicating Sequential Processes.
Compositional Specification and Verification of Distributed Systems.
Two Implementation Relations and the Correctness of Communicated Replicated Processing.
Behaviour Abstraction for Communicating Sequential Processes.
The Implementation of Reliable Distributed Multiprocess Systems.
Hierarchical Correctness Proofs for Distributed Al- gorithms
Towards a Theory of Replicated Processing.
Communication and Concurrency.
Vertical Implementation.
The Theory and practice of Concurrency.

Proving Entailment Between Conceptual State Specifications.


Dom Ep is the prefix-closure of dom Ep
extr Ep is monotonic and strict.

extr Ep
For every derivation
For every
For every
Suppose that CTS u has not been rejected and 1
q k is stable i
if the above holds
--TR
Communicating sequential processes
Hierarchical correctness proofs for distributed algorithms
Proving entailment between conceptual state specifications
Algebraic theory of processes
Towards a theory of replicated processing
Communication and concurrency
Refining interfaces of communicating systems
The existence of refinement mappings
Compositional specification and verification of distributed systems
Towards action-refinement in process algebras
Behaviour abstraction for communicating sequential processes
Vertical implementation
Verifying Implementation Relations
Trace-Based Compositional Reasoning about Fault Tolerant Systems
Implementing Communicating Processes in the Event of Interface Difference
communicating sequential processes;theory of parallel and distributed computation;refinement;behaviour abstraction;compositionality;verification