Coordination Models and Languages

Petri Nets are a well-known model of concurrency and provide an ideal setting for the study of fundamental aspects in concurrent systems. Despite their simplicity, they still lack a satisfactory causally reversible semantics. We develop such semantics for Place/Transitions Petri Nets (P/T nets) based on two observations. Firstly, a net that explicitly expresses causality and conflict among events, e.g., an occurrence net, can be straightforwardly reversed by adding reversal for each of its transitions. Secondly, the standard unfolding construction associates a P/T net with an occurrence net that preserves all of its computation. Consequently, the reversible semantics of a P/T net can be obtained as the reversible semantics of its unfolding. We show that such reversible behaviour can be expressed as a finite net whose tokens are coloured by causal histories. Colours in our encoding resemble the causal memories that are typical in reversible process calculi.

Process calculi based in logic, such as \(\uppi \)DILL and CP, provide a foundation for deadlock-free concurrent programming, but exclude non-determinism and races. \(\text {HCP}\) is a reformulation of CP which addresses a fundamental shortcoming: the fundamental operator for parallel composition from the \(\uppi \)-calculus does not correspond to any rule of linear logic, and therefore not to any term construct in CP.

We introduce \(\text {HCP}^{-} _{\text {ND}}\), which extends \(\text {HCP}\) with a novel account of non-determinism. Our approach draws on bounded linear logic to provide a strongly-typed account of standard process calculus expressions of non-determinism. We show that our extension is expressive enough to capture many uses of non-determinism in untyped calculi, such as non-deterministic choice, while preserving \(\text {HCP}\) ’s meta-theoretic properties, including deadlock freedom.

Recent work in the area of coordination models and collective adaptive systems promotes a view of distributed computations as functions manipulating computational fields (data structures spread over space and evolving over time), and introduces the field calculus as a formal foundation for field computations. With the field calculus, evolution (time) and neighbor interaction (space) are handled by separate functional operators: however, this intrinsically limits the speed of information propagation that can be achieved by their combined use. In this paper, we propose a new field-based coordination operator called share, which captures the space-time nature of field computations in a single operator that declaratively achieves: (i) observation of neighbors’ values; (ii) reduction to a single local value; and (iii) update and converse sharing to neighbors of a local variable. In addition to conceptual economy, use of the share operator also allows many prior field calculus algorithms to be greatly accelerated, which we validate empirically with simulations of a number of frequently used network propagation and collection algorithms.

Although many research efforts have been spent on the theory and implementation of data-based coordination languages, not much effort has been devoted to constructing programming environments to analyze and reason on programs written in these languages. This paper proposes a simple workbench for describing concurrent systems using a Linda-like language, for animating them and for reasoning on them using a fragment of linear temporal logic. In contrast to some tools developed for traditional process algebras like CCS, a key feature of our workbench is that it maintains a direct relation between what is written by the user and its internal representation in the workbench. Another feature, particularly useful for didactic purposes, is the production of trace examples, replayable, when LTL formulae are satisfied.

CHOReVOLUTION is a platform for the tool-assisted development and execution of scalable applications that leverage the distributed collaboration of services specified through service choreographies. It offers an Integrated Development and Runtime Environment (IDRE) comprising a wizard-aided development environment, a system monitoring console, and a back-end for managing the deployment and execution of the system on the cloud. We describe the platform by using a simple example and evaluate it against two industrial use cases in the domain of Smart Mobility & Tourism and Urban Traffic Coordination.

Attribute-based communication is a promising paradigm for modelling and programming complex interactions in open distributed systems such as collective adaptive systems (CAS). This new paradigm has been formalized in AbC, a kernel calculus with a minimal set of primitives that can be used to model formally verifiable CAS. The calculus assumes an underlying coordination infrastructure that has to guarantee the wanted communication and leaves open the actual implementation of the way communication partners are selected. The proposed implementations of messages exchange for AbC are either not in full agreement with the original semantics or do miss detailed performance evaluations. In this paper, we continue the search for efficient implementations of AbC and present ABEL - a domain specific framework that offers programming constructs with a direct correspondence to those of AbC. We use Erlang to implement ABEL inter- and intra-components interaction that together faithfully model AbC semantics and enable us to verify properties of ABEL program. We also consider a number of case studies and, by experimenting with them, show that it is possible to preserve AbC semantics while guaranteeing good performance. We also argue that even better performances can be achieved if the “strong” AbC requirement on the total order of message delivery is relaxed.

We explore the frontiers between coordination and control systems by discussing a number of contributions to bridging the gap between supervisory control theory and coordination of services. In particular, we illustrate how the classical synthesis algorithm from supervisory control theory to obtain the so-called most permissive controller can be modified to synthesise orchestrations and choreographies of service contracts formalised as contract automata. The key ingredient to make this possible is a novel notion of controllability. Finally, we present an abstract parametric synthesis algorithm and show that it generalises the classical synthesis as well as the orchestration and choreography syntheses.

Serverless computing, also known as Functions-as-a-Service, is a recent paradigm aimed at simplifying the programming of cloud applications. The idea is that developers design applications in terms of functions, which are then deployed on a cloud infrastructure. The infrastructure takes care of executing the functions whenever requested by remote clients, dealing automatically with distribution and scaling with respect to inbound traffic.

While vendors already support a variety of programming languages for serverless computing (e.g. Go, Java, Javascript, Python), as far as we know there is no reference model yet to formally reason on this paradigm. In this paper, we propose the first core formal programming model for serverless computing, which combines ideas from both the \(\lambda \)-calculus (for functions) and the \(\pi \)-calculus (for communication). To illustrate our proposal, we model a real-world serverless system. Thanks to our model, we capture limitations of current vendors and formalise possible amendments.

Engineering distributed applications and services in emerging and open computing scenarios like the Internet of Things, cyber-physical systems and pervasive computing, calls for identifying proper abstractions to smoothly capture collective behaviour, adaptivity, and dynamic injection and execution of concurrent distributed activities. Accordingly, we introduce a notion of “aggregate process” as a concurrent field computation whose execution and interactions are sustained by a dynamic team of devices, and whose spatial region can opportunistically vary over time. We formalise this notion by extending the Field Calculus with a new primitive construct, spawn, used to instantiate a set of field computations and regulate key aspects of their life-cycle. By virtue of an open-source implementation in the ScaFi framework, we show basic programming examples and benefits via two case studies of mobile ad-hoc networks and drone swarm scenarios, evaluated by simulation.

Formally describing and analysing quantitative requirements of software components might be important in software engineering; in the paradigm of API-based software systems might be vital. Quantitative requirements can be thought as characterising the Quality of Service – QoS provided by a service thus, useful as a way of classifying and ranking them according to specific needs. An efficient and automatic analysis of this type of requirements could provide the means for enabling dynamic establishing of Service Level Agreements – SLA, allowing for the automatisation of the Service Broker.

In this paper we propose the use of a language for describing QoS contracts based on convex specification, and a two-phase analysis procedure for evaluating contract satisfaction based on the state of the art techniques used for hybrid system verification. The first phase of the procedure responds to the observation that when services are registered in repositories, their contracts are stored for subsequent use in negotiating SLAs. In such a context, a process phase of contract minimisation might lead to great efficiency gain when the second, and recurrent, phase of determining QoS compliance is run.

DiRPOMS permits to verify if the specification of a distributed system can be faithfully realised via distributed agents that communicate using asynchronous message passing. A distinguishing feature of DiRPOMS is the usage of set of pomsets to specify the distributed system. This provides two benefits: syntax obliviousness and efficiency. By defining the semantics of a coordination language in term of pomsets, it is possible to use DiRPOMS for several coordination models. Also, DiRPOMS can analyze pomsets extracted by system logs, when the coordination model is unknown, and therefore can support coordination mining activities. Finally, by using sets of pomsets in place of flat languages, DiRPOMS can reduce exponential blows of analysis that is typical in case of multiple threads due to interleaving. (Demo video available at https://​youtu.​be/​ISYdBNMxEDY. Tool available at https://​bitbucket.​org/​guancio/​chosem-tools/​).

VirtuosoNext\(^{\text {TM}}\) is a distributed real-time operating system (RTOS) featuring a generic programming model dubbed Interacting Entities. This paper focuses on these interactions, implemented as so-called Hubs. Hubs act as synchronisation and communication mechanisms between the application tasks and implement the services provided by the kernel as a kind of Guarded Protected Action with a well defined semantics. While the kernel provides the most basic services, each carefully designed, tested and optimised, tasks are limited to this handful of basic hubs, leaving the development of more complex synchronization and communication mechanisms up to application specific implementations. In this work we investigate how to support a programming paradigm to compositionally build new services, using notions borrowed from the Reo coordination language, and relieving tasks from coordination aspects while delegating them to the hubs. We formalise the semantics of hubs using an automata model, identify the behaviour of existing hubs, and propose an approach to build new hubs by composing simpler ones. We also provide tools and methods to analyse and simplify hubs under our automata interpretation. In a first experiment several hub interactions are combined into a single more complex hub, which raises the level of abstraction and contributes to a higher productivity for the programmer. Finally, we investigate the impact on the performance by comparing different implementations on an embedded board.