Session types and contracts are two formalisms used to study client–server protocols. In this paper, we study the relationship between them. The main result is the existence of a fully abstract model of session types; this model is based on a natural interpretation of these types into a subset of contracts.

Relaxing the isolation requirements on transactions leads to systems in which transactions can now co-operate to achieve distributed goals. However in the absence of isolation it is not easy to understand the desired behaviour of transactional systems, or the extent to which the other standard ACID properties of transactions can be maintained: atomicity, consistency and durability. In this talk I will give an overview of some recent work in this area, outlining semantic theories for a process calculus which has been augmented by a new construct for co-operating transactions.

We view channels as the main form of resources in a message-passing programming paradigm. These channels need to be carefully managed in settings where resources are scarce. To study this problem, we extend the pi-calculus with primitives for channel allocation and deallocation and allow channels to be reused to communicate values of different types. Inevitably, the added expressiveness increases the possibilities for runtime errors. We define a substructural type system, which combines uniqueness typing and affine typing to reject these ill-behaved programs.

Abstract We take a fresh look at strong probabilistic bisimulations for processes which exhibit both non-deterministic and probabilistic behaviour. We suggest that it is natural to interpret such processes as distributions over states in a probabilistic labelled transition system, a pLTS; this enables us to adapt the standard notion of contextual equivalence to this setting. We then prove that a novel form of bisimulation equivalence between distributions are both sound and complete with respect to this contextual equivalence. We also show that a very simple extension to HML, Hennessy–Milner Logic, provides finite explanations for inequivalences between distributions. Finally we show that our bisimulations between distributions in a pLTS are simply an alternative characterisation of a standard notion of probabilistic bisimulation equivalence, defined between states in a pLTS.

In 1992 Wang & Larsen extended the may- and must preorders of De Nicola and Hennessy to processes featuring probabilistic as well as nondeterministic choice. They concluded with two problems that have remained open throughout the years, namely to find complete axiomatisations and alternative characterisations for these preorders. This paper solves both problems for finite processes with silent moves. It characterises the may preorder in terms of simulation, and the must preorder in terms of failure simulation. It also gives a characterisation of both preorders using a modal logic. Finally it axiomatises both preorders over a probabilistic version of CSP.

In 1992 Wang & Larsen extended the may- and must preorders of De Nicola and Hennessy to processes featuring probabilistic as well as nondeterministic choice. They concluded with two problems that have remained open throughout the years, namely to find complete axiomatisations and alternative characterisations for these preorders. This paper solves both problems for finite processes with silent moves. It characterises the may preorder in terms of simulation, and the must preorder in terms of failure simulation. It also gives a characterisation of both preorders using a modal logic. Finally it axiomatises both preorders over a probabilistic version of CSP.

The topic of this paper is the rôle-based trust-management language RT0, a formalism inspired by logic programming that handles trust in large scale, decentralised systems. We provide a purely operational semantics for the language in which credentials can be established using a simple set of inference rules. We then extend RT0to include time validity and boolean guards that control the availability of credentials. In such an extended framework, credentials are conditional on the availability of supporting credentials in the execution context. In addition to a set-theoretic and a logic-programming semantics, we develop for the extended language a series of increasingly powerful inference systems for establishing these conditional credentials. By means of simple but realistic examples, we demonstrate the expressiveness and usability of our language, warranting its integration into existing trust-management tools

We develop a semantics theory for SAP, a variant of Levi and Sangiorgi's Safe Ambients, SA.The dynamics of SA relies upon capabilities (and co-capabilities ) exercised by mobile agents , called ambients , to interact with each other. These capabilities contain references, the names of ambients with which they wish to interact. In SAP we generalize the notion of capability: in order to interact with an ambient n , an ambient m must exercise a capability indicating both n and a password h to access n ; the interaction between n and m takes place only if n is willing to perform a corresponding co-capability with the same password h . The name h can also be looked upon as a port to access ambient n via port h .In SAP, by managing passwords/ports, for example generating new ones and distributing them selectively, an ambient may now program who may migrate into its computation space, and when. Moreover in SAP, an ambient may provide different services/resources depending on the port accessed by the incoming clients. Then we give an lts -based operational semantics for SAP and a labelled bisimulation equivalence, which is proved to coincide with reduction barbed congruence .We use our notion of bisimulation to prove a set of algebraic laws that are subsequently exploited to prove more significant examples.

We propose a simple global computing framework, whose main concern is code migration. Systems are structured in sites, and each site is divided into two parts: a computing body, and a membrane, which regulates the interactions between the computing body and the external environment. More precisely, membranes are filters which control access to the associated site, and they also rely on the well-established notion of trust between sites. We develop a basic theory to express and enforce security policies via membranes. Initially, these only control the actions incoming agents intend to perform locally. We then adapt the basic theory to encompass more sophisticated policies, where the number of actions an agent wants to perform, and also their order, are considered.

We study typed behavioural equivalences for the -calculus in which the type system allows a form of subtyping. This enables processes to distribute different capabilities selectively on communication channels. The equivalences considered include typed versions of testing equivalences and barbed bisimulation equivalences.We show that each of these equivalences can be characterised via standard techniques applied to a novel labelled transition system of configurations. These consist of a process term together with two related type environments; one constraining the process and the other its computing environment.

The security π-calculus is a typed version of the asynchronous π-calculus in which the types, in addition to constraining the input/output behaviour of processes, have security levels associated with them. This enables us to introduce a range of typing disciplines which allow input or output behaviour, or both, to be bounded above or below by a given security level. We define typed versions of may and must equivalences for the security π-calculus, where the tests are parameterised relative to a security level. We provide alternative characterisations of these equivalences in terms of actions in context; these describe the actions a process may perform, assuming the observer is constrained by a given typing environment. Using these alternative characterisations we prove non-interference results with respect to may and must testing. These show that information flow between security levels can be controlled using our typing systems.

We study a variant of Levi and Sangiorgi's Safe Ambients (SA) enriched with passwords (SAP). In SAP by managing passwords, for example generating new ones and distributing them selectively, an ambient may now program who may migrate into its computation space, and when. Moreover in SAP an ambient may provide different services depending on the passwords exhibited by its incoming clients. We give an lts based operational semantics for SAP and a labelled bisimulation based equivalence which is proved to coincide with barbed congruence. Our notion of bisimulation is used to prove a set of algebraic laws which are subsequently exploited to prove more significant examples. 1

We propose an extension of the asynchronous π-calculus in which a variety of security properties may be captured using types. These are an extension of the input/output types for the π-calculus in which I/O capabilities are assigned specific security levels. The main innovation is a uniform typing system that, by varying slightly the allowed set of types, captures different notions of security.We first define a typing system that ensures that processes running at security level σ cannot access resources with a security level higher than σ. The notion of access control guaranteed by this system is formalized in terms of a Type Safety Theorem.We then show that, by restricting the allowed types, our system prohibits implicit information flow from high-level to low-level processes. We prove that low-level behavior can not be influenced by changes to high-level behavior. This is formalized as a noninterference theorem with respect to may testing.

In wide area distributed systems it is now common for higher-order code to be transferred from one domain to another; the receiving host may initialise parameters and then execute the code in its local environment. We propose a fine-grained typing system for a higher-order /spl pi/-calculus which can be used to control the effect of such migrating code on local environments. Processes may be assigned different types depending on their intended use. This is in contrast to most of the previous work on typing processes where all processes are typed by a unique constant type, indicating essentially that they are well-typed relative to a particular environment. Our process type takes a form of an interface limiting the resources to which it has access, and the types at which they may be used. Allowing resource names to appear both in process types and process terms, as interaction ports, complicates the typing system considerably. For the development of a coherent typing system, we use a kinding technique, similar to that used by the subtyping of the system F, and order-theoretic properties of our subtyping relation. Various examples illustrate the use of our fine-grained typing system for distributed systems. As a specific application we define a new typed behavioural equivalence for the higher-order /spl pi/-calculus. The expressiveness of our types enables us to state and prove interesting identities between typed processes.

We present a partially-typed semantics for Dπ, a distributed π-calculus. The semantics is designed for mobile agents in open distributed systems in which some sites may harbor malicious intentions. Nonetheless, the semantics guarantees traditional type-safety properties at "good" locations by using a mixture of static and dynamic type-checking. We show how the semantics can be extended to allow trust between sites, improving performance and expressiveness without compromising type-safety.

We describe a foundational language for specifying dynamically evolving networks of distributed processes, Dπ. The language is a distributed extension of the π-calculus which incorporates the notions of remote execution, migration, and site failure. Novel features of Dπ include 1. Communication channels are explicitly located: the use of a channel requires knowledge of both the channel and its location. 2. Names are endowed with permissions: the holder of a name may only use that name in the manner allowed by these permissions.A type system is proposed in which-the types control the allocation of permissions; in well-typed processes all names are used in accordance with the permissions allowed by the types. We prove Subject Reduction and Type Safety Theorems for the type system. In the final section we define a semantic theory based on barbed bisimulations and discuss its characterization in terms of a bisimulation relation over a relativized labelled transition system.

Concurrent ML (CML) is an extension of Standard ML of New Jersey with concurrent features similar to those of process algebra. In this paper, we build upon John Reppy's reduction semantics for CML by constructing a compositional operational semantics for a fragment of CML, based on higher-order process algebra. Using the operational semantics we generalise the notion of weak bisimulation equivalence to build a semantic theory of CML. We give some small examples of proofs about CML expressions, and show that our semantics corresponds to Reppy's up to weak first-order bisimulation.

We develop decision procedures based on proof tableaux for a number of non-interleaving equivalences over processes. The processes considered are those which can be described in a simple extension of BPP r , Basic Parallel Processes with communication, obtained by omitting the restriction operator from CCS. Decision procedures are given for both strong and weak versions of location equivalence and ST-bisimulation.

Concurrent ML (CML) is an extension of Standard ML of New Jersey with concurrent features similar to those of process algebra. In this papes we build upon John Reppy's reduction semantics for CML by constructing a compositional operational semantics for a fragment of CML, based on higher-order process algebra. We use this to build a semantic theory for CML, based on weak bisimulation equivalence. We give some small examples of proofs about CML expressions, and show that our semantics corresponds to Reppy's up to weak first-order bisimulation.

Abstract We give sound and complete proof systems for a variety of bisimulation based equivalences over a message-passing process algebra. The process algebra is a generalisation of pure CCS where the actions consist of receiving and sending messages or data on communication channels; the standard prefixing operator a.p is replaced by the two operators c?x.p and c!e.p and in addition messages can be tested by a conditional construct. The various proof systems are parameterised on auxiliary proof systems for deciding on equalities or more general boolean identities over the expression language for data. The completeness of these proof systems are thus relative to the completeness of the auxiliary proof systems.

Abstract We study a notion of observation for concurrent processes which allows the observer to see the distributed nature of processes, giving explicit names for the location of actions. A general notion of bisimulation related to this observation of distributed systems is introduced. Our main result is that these bisimulation relations, particularized to a process algebra extending CCS, are completely axiomatizable. We discuss in detail two instances of location bisimulations, namely the location equivalence and the location preorder.

A higher-order process calculus is defined in which one can describe processes which transmit as messages other processes; it may be viewed as a generalization of the lazy lambda -calculus. The authors present a denotational model for the language, obtained by generalizing the domain equation for S. Abramsky's (1990) model of the lazy lambda -calculus. It is shown to be fully abstract with respect to three different behavioural preorders. The first is based on observing the ability of processes to perform an action in all contexts, the second on testing, and the final one on satisfying certain kinds of modal formulae.>

Abstract In this paper we show how the testing equivalences and preorders on transition systems may be interpreted as instances of generalized bisimulation equivalences and prebisimulation preorders. The characterization relies on defining transformations on the transition systems in such a way that the testing relations on the original systems correspond to (pre)bisimulation relations on the altered systems. On the basis of these results, it is possible to use algorithms for determining the (pre)bisimulation relations in the case of finite-state transition systems to compute the testing relations.

Abstract A semantic theory of an imperative language which allows value-passing and assignments as a simple action prefixing is described. Three different semantic approaches are given: denotational based on the mathematical model Acceptance Trees, axiomatic based on inequations and behavioural in terms of testing. The equivalence of these different approaches is shown. The results are compared with similar results for other languages such as CSP and Occam .

In this paper, a process algebra that incorporates explicit representations of successful termination, deadlock, and divergence is introduced and its semantic theory is analyzed. Both an operational and a denotational semantics for the language is given and it is shown that they agree. The operational theory is based upon a suitable adaptation of the notion of bisimulation preorder. The denotational semantics for the language is given in terms of the initial continuous algebra that satisfies a set of equations E , CI E . It is shown that CI E is fully abstract with respect to our choice of behavioral preorder. Several results of independent interest are obtained; namely, the finite approximability of the behavioral preorder and a partial completeness result for the set of equations E with respect to the preorder.

Abstract A proof system for a version of CCS with value-passing is proposed in which the reasoning about data is factored out from that about the structure of processes. The system is shown to be sound and complete for finite terms with respect to a denotational semantics based on Acceptance Trees.

A simple process algebra which supports a form of refinement of an action by a process is presented and the question of an appropriate equivalence relation for it is addressed. The main result is that an adequate equivalence can be defined in a very intuitive manner and moreover can be axiomatized in much the same way as the standard behavioral equivalences.>

A new equivalence between concurrent processes is proposed. It generalizes the well-known bisimulation equivalence to take into account the distributed nature of processes. The result is a noninterleaving semantic theory; concurrent processes are differentiated from processes that are non-deterministic but sequential. The new equivalence, together with its observational version, is investigated for a subset of the language CCS, and various algebraic characterizations are obtained.

We re-examine the well-known observational equivalence between processes with a view to modifying it so as to distinguish between concurrent and purely nondeterministic processes. Observational equivalence is based on atomic actions or observations. In the first part of this paper we generalise these atomic observations so that arbitrary processes may act as observers. We show, for a particular language based on finite (CCS) terms, that the generalised equivalence coincides with observational equivalence; the more powerful observers do not lead to a finer equivalence. In the second part of the paper we consider observers which can distinguish the beginning and ending of atomic actions. The resulting equivalence distinguishes a concurrent process from the purely nondeterministic process obtained by interleaving its possible actions. We give a complete axiomatisation for the congruence generated by the new equivalence.

A language for describing communicating systems is described. It is sufficiently expressive to describe both the desired behavior of systems, their specifications , and their actual implementations in terms of simpler components. We say I satisfies S if 1 is a correct implementation of the specification S . We briefly discuss a semantic treatment of this notion of satisfaction, but the main emphasis of the paper is on a proof technique for proving statements of the form I satisfies S , based on syntactic transformations and induction. Two examples are given, both systolic systems from the literature.

A simple model, AT, for nondeterministic machines is presented which is based on certain types of trees. A set of operations, Σ, is defined over AT and it is shown to be completely characterized by a set of inequations over Σ. AT is used to define the denotational semantics of a language for defining nondeterministic machines. The significance of the model is demonstrated by showing that this semantics reflects an intuitive operational semantics of machines based on the idea that machines should only be differentiated if there is some experiment that differentiates between them.

Since a nondeterministic and concurrent program may, in general, communicate repeatedly with its environment, its meaning cannot be presented naturally as an input/output function (as is often done in the denotational approach to semantics). In this paper, an alternative is put forth. First, a definition is given of what it is for two programs or program parts to be equivalent for all observers; then two program parts are said to be observation congruent if they are, in all program contexts, equivalent. The behavior of a program part, that is, its meaning, is defined to be its observation congruence class. The paper demonstrates, for a sequence of simple languages expressing finite (terminating) behaviors, that in each case observation congruence can be axiomatized algebraically. Moreover, with the addition of recursion and another simple extension, the algebraic language described here becomes a calculus for writing and specifying concurrent programs and for proving their properties.

Article Free Access Share on Modelling fair processes Author: Matthew Hennessy View Profile Authors Info & Claims STOC '84: Proceedings of the sixteenth annual ACM symposium on Theory of computingDecember 1984 Pages 25–30https://doi.org/10.1145/800057.808662Published:01 December 1984Publication History 1citation171DownloadsMetricsTotal Citations1Total Downloads171Last 12 Months14Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Nondeterministic recursive procedures are considered in which parameters may be passed by use of call-by-value or one of two different formulations of call-by-name. These procedures are given an operational semantics via an evaluation mechanism. We define a denotational semantics using so-called nondeterministic domains, which are function spaces endowed with two partial orders. An operational characterization of equality of procedures under this denotational semantics is then given.

The problem of defining an adequate semantics for recursive definitions which allow various types of parameter-passing mechanisms has generated a considerable amount of interest in the literature. (See [B1], [M4], [R3], [V2]) Consider for example the well-known recursive definition