Francisco Javier Velázquez-García

Pål Halvorsen

Håkon Kvale Stensland
email: haakonks@ifi.uio.no

Frank Eliassen

Autonomic adaptation of multimedia content adhering to application mobility

Keywords: self-configuration, self-adaptive, self-optimization, self-awareness, application mobility, multimedia pipelines, MAPE-K, DSPL

Today, many users of multimedia applications are surrounded by a changing set of multimedia-capable devices. However, users can move their running multimedia applications only to a pre-defined set of devices. Application mobility is the paradigm where users can move their running applications (or parts of) to heterogeneous devices in a seamless manner. In order to continue multimedia processing under the implied context changes in application mobility, applications need to adapt the presentation of multimedia content and their internal configuration. We propose the system DAMPAT that implements an adaptation control loop to adapt multimedia pipelines. Exponential combinatorial growth of possible pipeline configurations is controlled by architectural constraints specified as high-level goals by application developers. Our evaluation shows that the pipeline only needs to be interrupted a few tens of milliseconds to perform the reconfiguration. Thus, production or consumption of multimedia content can continue across heterogeneous devices and user context changes in a seamless manner.

Introduction

Multi-device environments with heterogeneous multimedia capabilities are common environments for many people. However, users of multimedia applications can offload their applications or redirect multimedia sessions only to a limited set of pre-defined devices or running environments. This limitation is due to the current paradigm where multimedia applications are designed to start and end execution in the same device. One approach to solve this limitation is to develop applications that adhere to the application mobility paradigm [START_REF] Yu | Application mobility in pervasive computing: A survey[END_REF]. In this paper, we refer to such applications as mobile applications.

Application mobility is the paradigm where users can move parts of their running applications across multiple heterogeneous devices in a seamless manner. This paradigm involves context changes of hardware, network resources, user environment, and user preferences. If such context changes occur during an ongoing multimedia session, the application should adapt: 1) the presentation of the multimedia content to fulfill user preferences, and 2) the internal configuration of the application to continue execution in a different running environment.

To move the process of the application from one device to another during runtime, and during an ongoing multimedia session, the needed mechanisms, such as for process migration [START_REF] Milojičić | Process migration[END_REF], should be part of DAMPAT. In this paper, we do not address these mechanisms, but focus on the aspects to adapt the presentation of multimedia content.

Multimedia content is composed by a collection of media streams and modalities; e.g., video, audio, and text; which makes a specific multimedia presentation. If a mobile application aims to adapt multimedia presentations in a variety of ways, such as bitrate adaptation, modality adaptation, or content retargeting, the more complex it is for developers to design and implement it. Creating complex computing systems that adapt themselves in accordance with high-level guidance from humans (developers or users) has been recognized as a grand challenge, and has been widely studied by the autonomous computing scientific community [START_REF] Huebscher | A survey of autonomic computing-degrees, models, and applications[END_REF]. Yet, multimedia mobile applications introduce new scenarios and new challenges. For example, in a videoconferencing use case, suppose the user Alice is using a mobile device while commuting. When she arrives in her office, she wishes to continue the same videoconferencing session by moving parts of the application to a dedicated office videoconferencing system. The new challenges in autonomic computing in this scenario are: 1) changes in availability or appropriateness of I/O interfaces to produce or consume multimedia content, 2) changes in application running environment, 3) strict deadlines of multimedia systems, 4) changes in user's physical environment, and 5) changes of user preferences.

It is fair to assume that usability and high QoE are among the main goals of developers of multimedia applications. We translate these goals as a safety predicate based on two requirements: 1) the collection of multimedia streams has to be processed on time and in synchrony to a reference clock, and 2) the configuration of components has to provide a high enough utility to the user, where user utility is defined by a utility function provided by the developer. To satisfy this safety predicate in application mobility, we identify four self-* properties as requirements: 1) Self-adaptive: applications should react to changes in the context by changing their safety predicate accordingly. 2) Self-configuration: applications should react to context changes, and change the connections or components of the application, to restore or improve the safety predicate. 3) Selfoptimization: applications should improve (maximize or minimize) the value of a predefined objective function. 4) Self-awareness: applications should be able to monitor and analyze its context.

To meet these requirements, we propose the system DAMPAT: Dynamic Adaptation of Multimedia Presentations in Application Mobility. The goal of DAMPAT is two-fold. The first goal is to reduce the development burden when creating context-aware applications that autonomously adapt the presentation of multimedia content. The second goal is to allow users to (easily) influence the selection of the best configuration at runtime, where best is defined as the con-figuration that produces the highest utility according to the current contextual situation and user preferences.

DAMPAT follows the Dynamic Software Product Lines (DSPL) engineering approach [START_REF] Bashari | Dynamic Software Product Line Engineering: A Reference Framework[END_REF]. In DSPL, designing a runtime adaptive system is considered to be a variability management problem, where the variability of the system is captured at design time. In our approach, the sequences of components to process multimedia streams are seen as pipelines. Therefore, the variability depends on the number of available components, their tuning parameters, and the topology alternatives. This variability creates a combinatorial explosion and makes the problem NP-hard.

The main contribution of this paper is a holistic presentation of the motivation, design, implementation and evaluation of the functional relation between parts of DAMPAT. This paper presents: 1) the model of available, appropriate and preferred I/O interfaces of users and multimedia-capable devices, 2) how functional stages and functional paths control exponential growth due to component, parameterization, and topology variability of multimedia pipelines, 3) the definition of high-level multimedia pipelines, and 4) the definition of a multi-dimensional utility function that takes into consideration context changes for decision making of pipeline selection. For completeness, related contributions for DAMPAT in [START_REF] Velázquez-García | DAMPAT: Dynamic Adaptation of Multimedia Presentations in Application Mobility[END_REF] and [START_REF] Velázquez-García | Dynamic adaptation of multimedia presentations for videoconferencing in application mobility[END_REF] are also presented.

Results from evaluating a videoconferencing prototype show that the time to create the adapted pipeline from scratch is in the order of tenths of milliseconds in average. The time to reconfigure a pipeline can be as much as 1000 faster than building the pipeline from scratch. Therefore, we conclude that adaptation of multimedia pipelines is a viable approach to seamlessly adapt multimedia content in a variety of ways, e.g., bitrate, modality, and content retargeting (using components such as [START_REF] Ravik | A Real-Time Video Retargeting Plugin for GStreamer[END_REF]), in the application mobility paradigm.

In the remainder of the paper, Section 2 explains the main challenges of design and implementation decisions of the proposed system. Section 3 evaluates the parts of the system that can negatively impact the seamlessness of multimedia mobile applications. Section 4 compares DAMPAT with related work. Finally, Section 5 concludes the paper.

The DAMPAT system

Our system adopts the DSPL engineering approach. In order to separate the concerns of DAMPAT, we follow the Monitor, Analyze, Plan, and Execute (MAPE)-K adaptation control loop [START_REF] Kephart | The vision of autonomic computing[END_REF], where K is the knowledge created and used across the MAPE phases (see Fig. 1). Next, we describe in a top-down manner how the MAPE-K loop is applied in DAMPAT. developers using high-level goals. It uses the monitored data from sensors and internal knowledge of the system to plan and execute the low-level actions that are necessary to achieve these goals. The autonomic manager separate the adaptation concerns in four phases: Monitor, Analyze, Plan, and Execute, which create and share information (Knowledge) that impacts the production or consumption of multimedia content. These phases are explained in Sections 2.2 to 2.5.

Monitor, Analyze, Plan, and Execute (MAPE) phases

The managed element represents any software or hardware resource that is given autonomic behaviour by coupling it with an autonomic manager. In DAMPAT, the managed element is a multimedia pipeline.

Sensors refer to hardware or software devices that collect information about the running environment of the managed element. DAMPAT also collects information about: the user's available human senses, e.g., a noisy environment prevents a user from producing or consuming audio; user preferences, e.g., always activate close captioning; and modality appropriateness, e.g., no video modality while driving.

The data to asses the availability or appropriateness of modalities can be collected by, for example, setting parameters via a graphical user interface, or complex event processing subsystems. The implementation of these mechanisms, however, is out of scope of this paper. Finally, effectors in Fig. 1 carry out changes to the managed element.

Phase 1: Monitor

In order for the autonomic manager to relieve humans of the responsibility of directly managing the managed element, the autonomic manager needs to collect data to recognise failure or suboptimal performance of the managed element and effect appropriate changes. Monitoring gives DAMPAT the selfawareness property, which it is a prerequisite for self-optimization and selfconfiguration. Monitoring involves capturing properties of the environment, either external or internal, e.g., user surroundings or running environment, and physical or virtual, e.g., noise level or available memory. This variation of data sources and data types makes the monitored context multi-dimensional.

For the Monitor phase, we group the information that can impact the processing or appropriateness of multimedia presentations in two categories. 1) User context: set of I/O capabilities of user to produce or consume multimedia content, physical environment, and user preferences. As for user input capabilities, we consider hearing, sight, and touch senses as interfaces to support audio, video, text, and tactition modalities. As for user output capabilities, we consider speaking, and touching availabilities as interfaces to support audio, and tactition modalities. User context registers user preferences, which are predicates that express additional user constraints or needs. 2) Application context: application running environment including I/O capabilities to produce or consume multimedia content. As for device input capabilities, we consider microphone, camera, keyboard and tangible (haptic) interfaces. As for device output capabilities, we consider display, loudspeaker, and tangible interfaces. The model also contains software and hardware descriptors for dependencies of pipeline components. Software descriptors include the available software components to build multimedia pipelines, such as encoders, parsers, and encryptors. Hardware descriptors include CPU, GPU, battery, memory, and network adapters.

The design of DAMPAT also takes into account context that impacts the appropriateness of modalities in a given situation, namely, current activity, geographical location, physical environment, date, and time. The information needed to estimate the modality appropriateness is taken from both, user-and applicationcontext. The monitored data is part of the knowledge K in DAMPAT.

Phase 2: Analysis

We say that an application is in a legal or consistent configuration in a given context, when the corresponding safety predicate holds. A safety predicate in application mobility is not only violated by bugs or failures in software or hardware, as in traditional scenarios in autonomic computing, but also by changes in user and application context, that change the initial high-level goal of the application. For example, when a user changes preferences from audio to text modality due to a noisy environment or when an audio card is not longer available in a multimedia session after an application has moved.

To meet the self-adaptive requirement in DAMPAT, we declare two characteristics of safety predicates: 1) safety predicates hold if a pipeline configuration is adequate for the available resources of the application running environment so that buffers arrive on time in the final sink, and 2) safety predicates might change with changes in context.

Therefore, if the user changes her environment or preferences, the autonomic manager treats such changes as a threat to the safety predicate and addresses them. In a more obvious manner, if the application moves to another device where the initial configuration cannot continue execution, the autonomic manager addresses this problem as well. The self-optimization requirement is met by objective functions implemented in components. For example, a DASH (Dynamic Adaptive Streaming over HTTP) component that proactively checks the available resources to optimize its parameterization and process the highest bitrate.

The problem-diagnosis component in the Analysis phase analyzes the data collected in the Monitor phase. This component can evaluate whether the safety predicate holds. If the safety predicate is violated, it means that a problem is detected, and the Plan phase is started. The implementation of the problemdiagnosis component can be, for example, implemented based on a Bayesian network. This implementation is left as future work.

The current design of the Analysis phase of DAMPAT, takes into consideration the monitored data of the device where an application starts execution (source), and the device where the application will be moved to (destination). As future work, we plan to incorporate the special purpose negotiation protocol in [START_REF] Andic | Negotiation and Data Transfer for Application Mobility[END_REF] to aggregate the monitored data of all the surrounding devices to which an application can move.

Phase 3: Plan

In the Plan phase, the autonomic manager creates variants of multimedia pipelines, and selects the best one among the ones that guarantee to hold the safety predicate in the current context. The Plan phase addresses the challenge of combinatorial explosion of pipeline variants caused by compositional and parameterization variability. In the current state of DAMPAT, the Plan phase assumes infinite resources of application running environment, and do not consider other applications running in the same device.

Multimedia pipeline model Multimedia pipelines are built with components that are linked with compatible connectors, and process streams in a sequential order. Multimedia pipelines can be modeled as directed acyclic multigraphs G = (V, E). In this abstraction, V is the set of vertices v that represent the pipeline components, and E is the set of edges e that represents the connection or pipe between the output and input connectors of two vertices. Each edge has a modality type m, and multiple edges (e ∈ E) connecting components of the same components can have different modalities. Therefore, multigraphs have a set of modalities M . Pipeline components for the same functionality might have different implementations, for example; 1) the components vp8dec and avdec vp8 are two different implementations of the VP8 decoder, and 2) the components glimagesink, and waylandsink are two different implementations that differ in hardware offloading and memory allocation (among many other differences). Therefore, in the multimedia pipeline model represented in Fig. 2, each component v can have more than one implementation candidate, and some components can dynamically (on-demand) create a set of input (i ∈ v.I) or output (o ∈ v.O) connectors. We refer to this configuration variability as compositional variability. In a similar manner, every component has parameterization variability due to assignable property values of components (v.P ), connectors (i.P and o.P ) and modalities (m.P ). Compositional and parameterization variability can create a rapid growth of complexity due to combinatorial explosion.

Typically, multimedia presentations are composed by more than one multimedia stream, e.g., video and audio stream. In our multimedia model, a path is a sequence of successive edges through the graph (where a vertex is never visited more than once) for a given stream. In complex multimedia pipelines, a stream can be split or mixed, increasing or reducing the numbers of streams. For example, a video stream that is split to be 1) rendered in a display, and 2) sent over a network card, or a video and audio streams that are multiplexed to be sent through a network card. Therefore, we define the term functional path as the path w of one stream from its original source to its final sink. For example, in the left pipeline of Fig. 3, there are five functional paths, w 1 , w 2 , w 3 , w 4 , and w 5 , where paths w 4 , w 5 share source (a), w 1 , w 2 share the source (d), w 1 , w 5 share sink (g), and w 2 , w 3 share sink (j). The right part of the figure is explained in Section 3.

Pipelines have a set of behavioral and interaction rules that aim to minimize the processing latency of the stream in the pipeline. Mechanisms to create, manage and dynamically reconfigure multimedia pipelines include: connector compatibility check, connector linking, stream flow control to handle delayed buffers in sinks due to limitations in local resources or bandwidth, pipeline state management, components instantiation, and memory allocation type check to avoid memory copying. To the best of our knowledge, GStreamer [START_REF]GStreamer community: GStreamer Open Source Multimedia Framework[END_REF] is the only free and open source, multi-platform, multimedia framework actively implementing and maintaining these mechanisms. Therefore, we leverage GStreamer pipelines in DAMPAT. Control of combinatorial growth due to compositional and parameterization variability We arrange functional paths (W ) in a sequence of functional stages (s ∈ S) that group components by functionality, e.g., file sources, demuxers or decoders. Functional stages act as architectural constraints to enforce directed graphs, and they avoid unnecessary checks of connector's compatibility, which are most likely to fail. An architectural constraint is defined as the design knowledge introduced by the application developer with the purpose to reduce combinatorial growth (by limiting configuration variability).

(h) (d) (j) (c) (i) (f) (b) (g) (
(k) (l) (m) (h) (d) (j) (c) (i) (f) (b) (g) (
For example, in Fig. 4, the developer defines a functional path (w) to capture video taken from a webcam, and render it in a display. This functional path is defined with four functional stages (s 1 , s 2 , s 3 , s 4 ). The functional stage s 1 groups the components that capture video, stage s 2 is a specific component to fix the desired output of s 1 , s 3 does conversion of color space, and s 4 groups the components to render video. In this example, since there are two candidates in s 1 , and four candidates in s 4 , there are 8 possible functional paths. Functional stages are defined at different levels, where deeper levels filter components more accurately. In this way, application developers can define high-level architectures of multimedia pipelines without knowing the details of each functional stage. For example, developers can define a pre-processing stage that automatically includes components of the type of protocol handlers, parsers, and video converters. For further details about this approach, the reader is referred to [START_REF] Velázquez-García | DAMPAT: Dynamic Adaptation of Multimedia Presentations in Application Mobility[END_REF].

GStreamer multimedia components and enumerated parameters have a rank to describe their priority with competing candidates. Functional stages is a list of stages, where each stage is a list of candidates sorted by rank, just as the vanilla auto plugin strategies in the GStreamer do, and build the variability search space of functional paths by sequentially testing each sorted candidate. As a result, the produced search space is a sorted list of functional paths.

Linking the connectors across the defined functional stages produces a unixstyle configuration file that is part of the knowledge of DAMPAT. This file contains the settings of all configuration options for every component in the functional stage. Listings 1.1 and 1.2 show snippets of the configuration file for one functional path in Fig. 4. Control of functional path combinations Due to the compositional variability in functional stages, functional paths may have a set of alternative paths, consequently, alternative topologies. In order to restrict path combinations, the application developer can introduce an architectural constraint with specifying the bound of allowed path combinations per functional path. The combinatorial growth of this approach is evaluated in Section 3.1.

To enforce the path combination constraint, the autonomic manager computes the Binary Reflected Gray Code (BRGC) algorithm. The output of the BRGC algorithm is a set of subgraphs G = {g} n 1 that creates the variant search space. Each element g ∈ G represents a pipeline that can be configured in the Execute phase. Each pipeline (g) has the set of properties (P ∈ v) of each component (v ∈ g), the set of modality types (M ∈ g) processed by the pipeline, the properties of each modality (P ∈ M ), and the set of edges E ∈ g. In practice, the description of each g is stored in a configuration file similar to Listings 1.1 and 1.2, but its values are the location of files describing the set of functional paths (W ∈ g). G is part of the knowledge base of DAMPAT, and its elements are used as input for the utility function used in the decision making process.

Variant selection

The autonomic manager evaluates the variants in the search space and selects the alternative that matches best the goals defined by the application developer, user preferences, and contextual information. The challenge in this selection is how to define high-level goals and how to trade off conflicting contextual information. High-level goals are usually expressed using eventcondition-action (ECA) policies, goal policies or utility function policies [START_REF] Huebscher | A survey of autonomic computing-degrees, models, and applications[END_REF]. ECA policies suffer from the problem that all states are classified as either desirable or undesirable. Thus, when a desirable state cannot be reached, the system does not know which among the undesirable states is least bad. Goal policies require planning on the part of autonomic manager and are thus more resource-intensive than ECA policies. Utility functions allow a quantitative level of desirability to each context. Therefore, we use multi-dimensional utility functions.

The proposed multi-dimensional utility function [START_REF] Velázquez-García | DAMPAT: Dynamic Adaptation of Multimedia Presentations in Application Mobility[END_REF] is composed of functions defined for the properties that describes the pipeline (g.P ). Developers of pipeline components define and implement the component and its utility function. Since the overall pipeline utility is calculated based on the components that form the pipeline, the more utility functions are implemented in the components, the better overall estimation can be calculated. Utility functions take as argument two property-value tuples, one argument represents the user preference (u.p), and the other argument is the property value (g.p) obtained from the running environment, e.g., hardware characteristics or metadata of stream. As a result, the signature of utility functions in components are of the form ut(u.p, g.p).

If a modality is unavailable or inappropriate for a user in a given context, the modality is marked as negative. Therefore, pipeline variants matching negative modalities do not provide the highest utility, and thus they are not selected. One analogy to see this approach, is to think of the human senses as connectors (interfaces). In this analogy, DAMPAT matches the best compatibility between the possible pipeline configurations to use the computer's interfaces, and the human's interfaces. Fig. 5 illustrates this analogy in a oversimplified pipeline that processes video and audio modalities. Fig. 5. Oversimplified pipeline to make an analogy of a human consumer as a component in a multimedia pipeline. In this analogy, the input connectors (interfaces) of human consumer are the hearing and sight senses. DAMPAT selects the pipeline variant with connectors that are compatible with the available and appropriate user interfaces in a given context.

Final sink

Weights (we)

Weights are provided by users to (easily) influence the selection of the configuration at runtime. Weights help to trade off conflicting interests, and they can be seen as ranks or importance associated to a property, i.e., u.p.we. For example, suppose a user prefers video-resolution=4K (2160 progressive) and framerate=60fps. In case a device can reproduce either 1080p at 60 fps, or 4k at 30 fps, weights are used to rate the alternatives. Thus, the resulting weighted multi-dimensional utility function is Υ (u, g) = l j=1 ut(u.p j , g.p j ) • u.p j .we [START_REF] Velázquez-García | DAMPAT: Dynamic Adaptation of Multimedia Presentations in Application Mobility[END_REF]. Finally, if all the pipelines in the variability search space provide 0 utility, DAMPAT interprets this situation as if adaptation is impossible for the given context. If the application cannot continue execution in the current running environment, DAMPAT stops the application.

Phase 4: Execute

The task of the this phase is to safely introduce, remove, or re-configure components in the pipeline according to the selected subgraph g, i.e., pipeline variant with highest utility for a given context. g contains the description of the pipeline variant to be executed (described in Section 2.4). Then, the autonomic manager decides between create the pipeline from scratch or reconfigure it. The Execute phase meets the self-configuration requirement in DAMPAT.

The autonomic manager compares the current pipeline configuration (if already instantiated) with the new selected variant. In our implementation design, the autonomic manager executes the diff Linux command with the .conf files from the current and new graph descriptors as arguments. If the output of diff includes changes in source components in the pipeline, the new variant is instantiated from scratch, because new sources typically require several changes that are more complex to automate, and thus are prone to errors.

Dynamic reconfiguration If a component is removed while it is processing a buffer, the thread processing the stream can potentially enter in a deadlock state, because some other component(s) in the path might indefinitely wait for the expected data to arrive. To prevent this situation, the autonomic manager blocks the data flow in the preceding connector of the component that will be removed, and installs a callback to be notified about the state changes in the data flow. After changing components, the state of all components is synchronized to avoid deadlocks.

A potential race condition when reconfiguring pipelines occurs when a component in the pipeline waits for some timestamp or other specific data that was in the buffer or a just removed component. The adaptation manager handles this situation by flushing the buffers of the components to be removed. If the Execution phase fails to instantiate the selected variant, DAMPAT blacklist the just failed variant, and runs the variant selection process again.

State preservation for stream processing is achieved by reading the timestamps of the stream. We assume that states of components and pipelines are preserved when moving between devices. This can be achieved, for example, by implementing component's interfaces that retrieve and store the state of the components.

Evaluation

In this section, we present and discuss the evaluation of the time overhead that has a direct impact in multimedia session interruption. In principle, this overhead is the time to select and execute the plan, either by instantiating a pipeline from scratch or reconfiguring it. However, if the variability search space is not ready by the time adaptation is needed, its creation can also add interruption time. Results of experiments are from two evaluations from our previous work in [START_REF] Velázquez-García | DAMPAT: Dynamic Adaptation of Multimedia Presentations in Application Mobility[END_REF], and [START_REF] Velázquez-García | Dynamic adaptation of multimedia presentations for videoconferencing in application mobility[END_REF].

For completeness, we briefly describe both prototypes and the experiments. In evaluation 1 [START_REF] Velázquez-García | DAMPAT: Dynamic Adaptation of Multimedia Presentations in Application Mobility[END_REF], we evaluate the Plan phase to adapt a video player prototype application that consumes video and audio modalities. The experiments evaluate the creation of the search space with four and six functional stages, and an initial repository of 1379 pipeline components.

In evaluation 2 [START_REF] Velázquez-García | Dynamic adaptation of multimedia presentations for videoconferencing in application mobility[END_REF], we evaluate the Plan and Execution phases of a videoconferencing prototype application that simulated the production and consumption of: video, audio, and text modalities. The pipeline in this evaluation is of a peer videoconferencing application that has to adapt since (for any reason) its peer cannot process audio any longer. However, the user of this pipeline prefers to interact with the audio I/O interfaces of the device. The initial and reconfigured pipeline of this evaluation is the same as in Fig. 3. The initial repository is of 1420 pipeline components.

As a testbed, evaluations 1 and 2 use the same computer that resembles hardware characteristics of commodity hardware. The computer is a MacBook Pro 7,1 with Intel Core 2 Duo CPU P8800 at 2.66GHz running the 64-bit Ubuntu 17.10 operating system.

Plan phase

In this section, we discuss results from our previous work ( [START_REF] Velázquez-García | DAMPAT: Dynamic Adaptation of Multimedia Presentations in Application Mobility[END_REF] and [START_REF] Velázquez-García | Dynamic adaptation of multimedia presentations for videoconferencing in application mobility[END_REF]) to create the variability search space, and to select the variant with highest utility. The main scaling factors that influence the time spent when creating the search space are: 1) the time to instantiate components with hardware dependencies, 2) the query handlers in GStreamer components to check the processing capabilities of connectors, 3) the length of the pipeline, 4) the number of functional stages per functional path, and 5) the number of candidates per stage.

Results from the evaluations show that the time to create the entire variability search space is between the order of a few seconds and hundreds of milliseconds. Observations about the number of queries are: number of queries does not have a linear correlation with the number of functional stages or number of components in each stage due to the different implementations of query handlers in the involved components, and number of queries increases as the path length increases due to the recursion of queries.

To evaluate the scalability issues when combining functional paths, we use binomial coefficients to calculate how many unsorted combinations exist to select k ≥ 0 path configurations. That is n k + ... + n 0 , where n is the cardinality of the set of configurations for a specific path definition. As a result, when the developer decides to restrict functional path configurations to one (k = 1) in an application with three needed paths; e.g., video rendering, video transmission, and audio transmission (n = 3), the combinatorial growth is reduced to the polynomial form of O(n k ), i.e., O(3).

Evaluation and analysis of the multi-dimensional utility function, described in Section 2.4, shows that its complexity is linear. Since the maximum number of pipeline variants in our experiments are below 300, a brute force approach to find the variant with the highest utility does not introduce intolerable service interruption. However, greedy techniques, such as Serene Greedy [START_REF] Scholz | Co-ordinated utility-based adaptation of multiple applications on resource-constrained mobile devices[END_REF], should be implemented in DAMPAT to tackle larger search spaces. The implementation of greedy techniques, however, is left as future work.

Execution phase

In this section, we discuss results from our previous work ( [START_REF] Velázquez-García | DAMPAT: Dynamic Adaptation of Multimedia Presentations in Application Mobility[END_REF] and [START_REF] Velázquez-García | Dynamic adaptation of multimedia presentations for videoconferencing in application mobility[END_REF]) that evaluates the time to execute a plan by two means: by instantiating a pipeline from scratch or by reconfiguring it. The main factors when instantiating a pipeline from scratch are the same as in the Plan phase, but not when reconfiguring a pipeline. Reconfiguration of pipelines is faster mainly due to the re-utilization of already instantiated components with hardware dependencies, and the need for less queries to check compatibility of components' connectors. However, the reduction of queries does not correlates linearly. The removal of functional paths reduces the number of queries drastically, in some cases 0 queries needed, as opposed to instantiating the adapted pipeline from scratch. Therefore, further implementation of DAMPAT should aim at removing functional paths only by reconfiguration.

Results show that the execution of a plan (involving functional paths with similar characteristics as in Fig. 3) is under 10 ms when instantiating a pipeline from scratch. There is a clear pattern of approximately 1000 times faster (from tens of milliseconds to tens of microseconds) when reconfiguring a pipeline, if the already instantiated hardware-dependent components are reused.

The speed gain from pipeline reconfiguration over instantiating pipelines from scratch is applicable when adaptation occurs in the same device. Clearly, if an application is moved from one device to another, the components with hardware dependencies have to be initialized in the destination device. Therefore, in such mobility cases, there are no advantages in reconfiguring a pipeline.

Reconfiguration in the same device is, however, still a valid use case in peer to peer mobile applications, such as in the videoconferencing use case illustrated in Fig. 3. Pipeline reconfiguration can be also very advantageous when creating the variability search space, specially in the current design of DAMPAT where the variability search space is created based on local components only. In order for DAMPAT to know whether reconfiguration is a better alternative (than instantiation from scratch), pipeline components must be annotated to indicate whether they have hardware dependencies or not. This annotation and the cre-ation of the variability search space using the reconfiguration mechanisms are future work.

Related Work

MUSIC [START_REF] Hallsteinsen | A development framework and methodology for self-adapting applications in ubiquitous computing environments[END_REF] is a development framework for self-adapting applications in ubiquitous computing environments; it follows the MAPE-K reference model, and it uses utility functions for adaptation decision making. MUSIC combines componentbased software engineering with service-oriented architectures (SOA) to allow applications on mobile devices to adapt to and benefit from discoverable services in their proximity. Applications in MUSIC can offload services to devices in close vicinity; these close devices must, however, have pre-installed the MU-SIC middleware and application-specific components. Therefore, the application developer has to be aware of the characteristics of the devices where applications can move. As a result, the set of devices constituting the ubiquitous environment is defined at design time of the application. Hallsteinsen et al. [START_REF] Hallsteinsen | A development framework and methodology for self-adapting applications in ubiquitous computing environments[END_REF] recognized that support for multimedia content adaptation in a challenging research alley, and left it as future work.

PLASMA [START_REF] Layaida | Designing self-adaptive multimedia applications through hierarchical reconfiguration[END_REF] is a component-based framework for building adaptive multimedia applications. This framework relies on a hierarchical composition, similar concept to levels in functional stages (described in Section 2.4), and a reconfiguration model, similar to the Execute phase (Section 2.5). The authors describe at a high-level the mechanisms needed to build and reconfigure pipelines. However, they do not discuss the needed mechanisms to process multiple media types in synchrony. Therefore, we regard their design valid for adaptation of only one stream. PLASMA does not handle any scalability issue due to parameterization or compositional variability. PLASMA is implemented in DirectShow (moved to Windows SDK in 2005), which implies support for devices running Windows operating systems only. Adaptation policies in PLASMA are based on event-condition-actions (ECA), and they are triggered on changes of hardware resources only, e.g., bandwidth fluctuations, but not changes between devices, therefore PLASMA-applications do not adhere to the application mobility paradigm.

Infopipes [START_REF] Black | Infopipes: An abstraction for multimedia streaming[END_REF] provides abstractions to build distributed streaming applications, that adapt based on resource monitoring, such as CPU and bandwidth. Therefore, adaptation is achieved by adjusting the parameters of components only, and it limits the adaptation types that can be achieved with compositional variability. The authors define pipelines with pipes, filters, buffers, and pumps, but do not define the mechanisms to process multiple streams in synchrony.

Conclusions

We have identified the self-adaptive, self-optimization, self-configuration, and self-awareness properties as requirements for multimedia applications to adapt the presentation of multimedia content across the multimedia-capable devices that surround users. To ease the development of multimedia applications that meet these requirements, we have presented DAMPAT, which follows the MAPE adaptation control loop, and DSPL engineering approach. DAMPAT enables application developers and users to describe the application goals at their level of expertise via: configuration files (functional stages, and functional paths), user preferences, and importance of preferences. This approach allows users of mobile applications to take advantage of heterogeneous devices that were unknown at design time. DAMPAT makes decisions at runtime on how to adapt multimedia presentations; it enables modality adaptation, and any other adaptation technique implemented in the pipeline components such as bitrate adaptation, or content retargeting.

The main contribution of this paper is the holistic presentation of the motivation, design, implementation, and evaluation of DAMPAT. Evaluation shows that the average time spent to adapt multimedia pipelines is in the order of milliseconds. This delay is acceptable when users of mobile applications have to physically move their attention and control from one device to another.

As future work, we plan to explore the creation of a model to quantify the effects of the previous configuration when reconfiguring a pipeline; as first approach, we suggest to do analysis of variance, and regression in experiments to process more than three media types. To create this model, we plan to investigate what are the currently available GStreamer components that can be instantiated in a sample of multimedia devices in typical homes, offices and public transportation in industrialized countries. Additionally, we plan to add more managed elements to adapt different parts of mobile applications, e.g., reconfiguration of endpoint connections.

Fig. 1 Fig. 1 .

 11 Fig. 1 represents an autonomic manager, a managed element, sensors, and effectors. The autonomic manager is a software component configured by human

Fig. 2

 2 illustrates a simplified version of two connected pipeline components representing a multigraph G. Each component v has a set of input connectors v.I and output connectors v.O. Connectors are the interfaces of components. Data flows from one component's output connector v.O to another component's input connector v.I. The specific data type (modality) that the component can handle is described in the component's connectors.

Fig. 2 .

 2 Fig. 2. Multigraph that shows vertices v1, v2 ∈ V representing pipeline components. P represent a set of properties, i and o represent input and output connectors, m ∈ M the supported modalities by the connectors, and e ∈ E represent links or pipes between connectors.

a) w 5

 5

a) w 4 Fig. 3 .

 43 Fig.3. Graph abstraction of multimedia pipeline of one videoconferencing peer before and after adaptation. On the left, pipeline that consumes and produces video and audio. On the right, pipeline that consumes video and text from a peer that cannot process audio, this pipeline allows its user to produce and consume audio by changing the text-to-audio and audio-to-text modalities. The vertices represent the following components: (a) networksrc, (b) demuxer, (c) audiosink, (d) webcamsrc, (e) splitter, (f) videomixer, (g) videosink, (h) audiosrc, (i) muxer, (j) networksink, (k) text-to-audio, (l) audio-to-text, and (m) text-overlay. {w}7 1 represent functional paths.

Fig. 4 .

 4 Fig.[START_REF]GStreamer community: GStreamer Open Source Multimedia Framework[END_REF]. Example of functional path (w) that captures video from a webcam and renders it in a display. In this example, w has four functional stages ({s}4 1 ) and eight possible path combinations.

Listing 1 . 1 .

 11 Snippet 1 of w1.conf 1 [ f u n c t i o n a l -path ] 2 name=webcam2display 3 v e r t i c e s=v i d e o s r c , f i l t e r , \ 4 t e e , queue , g l i m a g e s i n k Listing 1.2. Snippet 2 of w1.conf 6 [ v e r t e x v i d e o s r c ] 7 name=v 4 l s r c 0 8 output-conn=v 4 l s r c 0 . s r c . 0 9 d e v i c e =/dev / v i d e o 0


Adrian Francalanza
email: adrian.francalanza@um.edu.mt

Claudio Antares Mezzina

Emilio Tuosto
email: emilio@le.ac.uk

Reversible Choreographies via Monitoring in Erlang

Keywords:

We render a model advocating an extension of choreographies to describe reverse computation via monitoring. More precisely, our extension imbues the communication behaviour of multi-party protocols with minimal decorations specifying the conditions triggering monitor adaptations. We show how, from these extended global descriptions, one can (i) synthesise actors implementing the normal local behaviour of the system prescribed by the global graph, but also (ii) synthesise monitors that are able to coordinate a distributed rollback when certain conditions (denoting abnormal behaviour) are met.

Introduction

Runtime Monitoring [START_REF] Francalanza | A Theory of Monitors[END_REF][START_REF] Francalanza | A Foundation for Runtime Monitoring[END_REF] (or Monitor Oriented Programming [START_REF] Chen | Towards Monitoring-Oriented Programming: A paradigm combining specification and implementation[END_REF][START_REF] Meredith | An overview of the MOP runtime verification framework[END_REF][START_REF] Cassar | On Implementing a Monitor-Oriented Programming Framework for Actor Systems[END_REF]) is a code structuring principle whereby ancillary system functionality (dealing with aspects such as security and reliability) is separated from the core functionality of a system and compartmentalised into separate code units called monitors. These monitors are occasionally assigned their own thread of control and operate by observing the execution of the core system and reacting to it: typical monitor functionality includes aggregating system information, comparing the execution against some correctness specification, or attempting to modify the execution of the observed systems via filtering, adaptation or enforcement procedures. Monitoring complements traditional verification techniques such as model checking and testing [START_REF] Artho | Combining test case generation and runtime verification[END_REF][START_REF] Bocchi | Monitoring networks through multiparty session types[END_REF][START_REF] Cassar | Runtime Adaptation for Actor Systems[END_REF][START_REF] Desai | Combining model checking and runtime verification for safe robotics[END_REF][START_REF] Kejstová | From Model Checking to Runtime Verification and Back[END_REF] because it allows verification checks to be offloaded to a post-deployment phase: these checks are typically either too expensive to perform statically or else intrinsically dependent on (missing) run-time information. Experience has also shown that often, computation misbehaviour still arises even after the software has undergone rigorous scrutiny prior to deployment. In such cases, monitors provide a natural mechanism to mitigate this misbehaviour.

The goal of this work is to show that monitoring can be used to attain reversible computation in models using asynchronous message-passing, such as those found in distributed computing and actor-based languages. Reversible computing [START_REF] Perumalla | Introduction to Reversible Computing[END_REF] has been show to be a suitable abstraction for a variety of application domains from software debugging, to transactions, to fault tolerant schemes [START_REF] Nishida | A reversible semantics for erlang[END_REF][START_REF] Gray | Transaction Processing: Concepts and Techniques[END_REF][START_REF] Elnozahy | A survey of rollback-recovery protocols in message-passing systems[END_REF]. Mechanisms for reversible computing can also be useful to describe and execute recovery strategies in distributed setting, where it is hard to anticipate all the conditions under which parts of computation is carried out: the ability to reverse computation would allow a system to Research partly supported by the EU COST Action IC1405. Fig. 1. A model for specifying monitors (reproduced from [START_REF] Cassar | Reliability and fault-tolerance by choreographic design[END_REF]) backtrack certain execution steps that have been invalidated by the violation of certain conditions, and subsequently execute alternative commands instead.

In spite of its utility, the programming of recovery strategies for asynchronous communicating software can be hard and error-prone. To this end, mechanisms for dealing with reversed execution in asynchronously communicating computation have been introduced. For instance, in [START_REF] Field | Transactors: a programming model for maintaining globally consistent distributed state in unreliable environments[END_REF] an approach based on checkpoints has been developed to cope with transactional behaviour in actor-based systems. But despite providing these convenient abstractions for reversibility, this approach still leaves the programmer with the burden of specifying checkpoints at judicious points within her program. In another work [START_REF] Nishida | A reversible semantics for erlang[END_REF], a reversible Erlang dialect has been proposed, maintaining the fundamental features of Erlang while automating the mechanism associated with reversibility. In spite of its advantages, the framework requires the development of a new run-time support (and the adoption of a special-purpose Erlang VM) to handle reversibility.

In this paper, we explore a third approach to tackle this problem. We combine "correctness-by-design" of choreographies, checkpoint-based mechanisms, and runtime monitoring to attain disciplined interweaving of forward and reversed execution. Unlike existing approaches, we fully exploit the benefit of choreographies to guarantee communication soundness by construction. For instance, our checkpoints are automatically derived from global views of choreographies unlike [START_REF] Field | Transactors: a programming model for maintaining globally consistent distributed state in unreliable environments[END_REF]. Moreover, we use runtime monitors to handle reversed executions while avoiding modifications to the standard runtime setup of Erlang (as is done in [START_REF] Nishida | A reversible semantics for erlang[END_REF]). This, in turn, facilitates the adoption and portability of our approach.

Technically, we concretise a proof-of-concept realisation of the methodology presented in [START_REF] Cassar | Reliability and fault-tolerance by choreographic design[END_REF] (see Fig. 1), for designing and implementing monitors for message-passing software. The main ingredient of this methodology is the use of choreographies for distributed applications and, in particular, the so-called top-down approach illustrated in the left part of Fig. 1. The starting point of our approach are the global graph models called global views, which are algorithmically "projected" on the local views (one for each "participant" of a choreography). Global views can, on the one hand, be checked for errors at an early stage of the design process and, on the other hand, be automatically projected on distributed components interacting via message-passing, to the participants in the local view in top-down fashion (see Fig. 1, left). The software components implementing each participant can, in turn, be checked against their corresponding local view; this guarantees communication soundness whenever the global view satisfies some conditions (e.g., see [START_REF] Honda | Multiparty asynchronous session types[END_REF]). The right part of Fig. 1 mirrors the top-down approach of choreographies for the realisation of the recovery logic, i.e., activities that a distributed system should carry out to handle undesired states of the computation reached at runtime. Concretely, starting from a global description of the recovery logic, local strategies can be derived and rendered as dedicated monitors for every participant. The realisation of such a scheme poses various research questions:

Q1. What global models are suitable to specify the recovery logic? Q2. How should components and monitors smoothly interact with each other? Q3. What are the properties should the recovery logic have to facilitate such a scheme?

The challenges illustrated in Fig. 1 correspond to the above questions (e.g., Challenge 1 relates to Q1 and so forth). These challenges should also observe a separation-ofconcerns principle espoused by monitor-oriented programming, namely that of decoupling the application logic from the recovery logic (as much as possible) [START_REF] Cassar | Reliability and fault-tolerance by choreographic design[END_REF].

Contributions. This paper describes a proof-of-concept solution for Q1 and Q2 in the setting of Erlang programs. More precisely, (i) we propose reversibility-enabling global graphs (REGs for short) as a suitable model for the global view of the recovery logic and intertwine this general specification language with Erlang's support for monitoring. Also, (ii) we show how to project REGs into Erlang monitors that steer the execution of the system according to some conditions. A basic feature of REGs is the possibility of specifying conditions allowing distributed components to execute distributed choices more flexibly. Specifically, the designer can specify conditions in the global views, dubbed reversion guards on distributed choices that are orthogonal to the application logic and depend on the run-time state of the computation. In this way, branches of distributed choices may be reversed when their reversion guards flag an undesired state of the computation. Alternatively, these conditions may be easily ignored during projection if desired or updated, without altering the application logic produced. We illustrate this with the following example that will help us throughout the paper.

Example 1. Consider a protocol where iteratively participant C sends a newReq message to a logging service L. In parallel, a C's partner, A makes either requests of either type req 1 or type req 2 to a service B, which, in turn, replies via two different types of responses, namely res 1 and res 2 . Once a request is served, B also sends a report to A, which logs this activity on L. A possible reversion guard for B could specify that the port required to respond A needs to be available at the time of communication, or that the size of the communication buffer for this port does not exceed a given threshold. At runtime, both of these conditions may prohibit the respective participants from completing the execution of the specified protocol. By reversing the choice taken (i.e., A making requests of either type req 1 or of type req 2 ), the participants involved can make alternative choices.

A definition of global graphs enabling reversible computations that is able to handle the aforementioned case would contribute towards answering Q1. Moreover, an automated projection of these graphs in terms of actors and monitors would start to address Q2. Question Q3 above requires some theoretical results not in scope here. However, this paper already sheds some light on possible desirable properties such as the requirement for "distributability" (over the respective participants) of the recovery logic.

Background

We begin by overviewing the preliminaries relating to Global Graph descriptions and the target actor model.

Global Specifications

Global graphs, originally proposed in [START_REF] Deniélou | Multiparty session types meet communicating automata[END_REF] and recently generalised in [START_REF] Tuosto | Semantics of global view of choreographies[END_REF][START_REF] Guanciale | An abstract semantics of the global view of choreographies[END_REF], are a convenient specification language for the global views of message-passing systems. They yield both a formal framework and a simple visual representation that we review here adapting notation and definition from [START_REF] Tuosto | Semantics of global view of choreographies[END_REF].

Hereafter we fix two disjoint sets P and M ; the former is a finite set of participants (ranged over by A, B, etc.) and M is the set of message (ranged over by m, x, etc.).

To exchange messages and coordinate with each other, participants use asynchronous point-to-point communication via channels. Basically, we adopt the actor model [START_REF] Hewitt | A Universal Modular ACTOR Formalism for Artificial Intelligence[END_REF][START_REF] Agha | Actors: A Model of Concurrent Computation in Distributed Systems[END_REF]. We remark that global graphs abstract away from data; the messages specified in interactions of global graphs have to be thought of as data types rather than values.

The syntax of global graphs is defined by the grammar

G ::= A-→B : m G;G G | G G+G repeat {G}
A global graph can be a simple interaction A-→B : m (for which we require A = B), the sequential composition G;G of G and G , the parallel composition (for which the participants of G and of G are disjoint), a nondeterministic choice G+G between G and G , or the iteration repeat {G} of G.

An example of global graph is given below. Example 2. The example discussed in Example 1 of Section 1 can be modelled with the graph

G = repeat { G 1 | G 1 ;G 2 ;G 3 } where G 1 =C-→L : newReq G 2 =L-→C : ack | B-→A : rep G 3 =A-→L : log G 1 =A-→B : req 1 ;B-→A : res 1 + A-→B : req 2 ;B-→A : res 2
The decision to leave or repeat the loop is non-deterministically taken by one of the participants (which one is immaterial) which then communicates to all the others what to do. This will become clearer in Section 4.

The syntax captures the structure of a visual language of distributed workflows illustrated in Fig. 2 nodes are drawn as • and a dotted edge from/to a •-node singles out the source/sink nodes the edge connects to. For instance, in the diagram for the sequential composition, the top-most edge identifies sink node of G and the other edge identifies the source node of G ; intuitively, • is the node of the sequential composition of G and G obtained by "coalescing" the sink of G with the source of G . In our diagrams, branches and forks are marked respectively by and nodes; also, to each branch/fork nodes corresponds a "closing" gate merge/join gate. The (forward) semantics of global graphs can be defined in terms of partial orders of communication events [START_REF] Tuosto | Semantics of global view of choreographies[END_REF][START_REF] Guanciale | An abstract semantics of the global view of choreographies[END_REF]. We do not present this semantics here (the reader is referred to [START_REF] Tuosto | Semantics of global view of choreographies[END_REF][START_REF] Guanciale | An abstract semantics of the global view of choreographies[END_REF]) for space limitations; instead, we give only a brief and informal account based on an example through a "token game" similar to the one of Petri nets.

Example 3. The diagram in Fig. 3 is the visual counterpart of G in Example 2. The token game semantics in the example of Fig. 3 would start from the source node and flow down along the edges in the diagram as described by the test in Fig. 3.

For the semantics of global graphs to be defined, well-branchedness [START_REF] Tuosto | Semantics of global view of choreographies[END_REF][START_REF] Guanciale | An abstract semantics of the global view of choreographies[END_REF] is a key requirement. This is a condition guaranteeing that all the participants involved in a distributed choice follow a same branch. Well-branchedness is quite simple and requires that each branch in a global graph (i) has a unique active participant (that is a unique participant taking the decision on which branch to follow) and (ii) that any other participant is passive, namely that it is either able to ascertain which branch was selected from the messages it receives or it does not play any role in the branching.

Example 4. In the branch of Example 2, A is the active participant while the others are passive; in fact, C and L are not involved in the choice, while B can determine that the left or the right branch was selected depending on which type of request it receives.

Erlang Model

Erlang [START_REF] Armstrong | Programming Erlang: Software for a Concurrent World[END_REF][START_REF] Cesarini | Erlang Programming[END_REF] is a general-purpose, industry-strength concurrent programming language. Actors-implemented as lightweight processes-constitute its concurrent units of decomposition: (in principle) actors do not share any mutable memory but rather interact

A-→B : req 1 A-→B : req 2 B-→A : res 1 B-→A : res 2 C-→L : newReq B-→A : rep L-→C : ack A-→L : log
The topmost gate is the entry point of a loop which simply lets the token to flow. At the first gate, the token is duplicated, forking the computations along the two threads. In the leftmost thread, the token enables the interaction C-→L : newReq; this allows the output event from C (which then waits for the ack message from L) and later the input event of L. The token on the leftmost thread then enables the last interaction L-→C : ack. Observe that, after the input of message ack, C can start the next iteration of the loop while the other threads may still be completing the current iteration. Concurrently, the token flowing on the rightmost thread reaches another branch gate which non-deterministically routes the token either on the left or on the right branch. On both branches A and B execute a requestresponse type of protocol similarly to what C and L run on the leftmost thread. When the token flows through the merge gate at the end of the choice, it enable a last interaction from B to A (which allows B to go the next iteration) and subsequently, the last logging interaction between A and L. Finally, also A and L can repeat the loop. Note that the body of an iteration is executed at least once. with one another via asynchronous messages, changing their internal state in response to the messages received. Every actors is uniquely identified via a process ID (PID); it owns a message queue, called a mailbox, to which messages are sent in a non-blocking fashion. Messages may be sent to an actor's mailbox only if its PID is known, and, once received, these messages can be selectively (and exclusively) consumed by the recipient actor using pattern matching. Actors may spawn other actors dynamically (at run-time): the PID of a newly spawned actor is originally known only by the spawning actor, but this can then be communicated to other actors via messaging.

Concurrent Erlang actors are typically organised as supervision tiers. Using the process-linking and exit-trapping mechanisms [START_REF] Armstrong | Programming Erlang: Software for a Concurrent World[END_REF][START_REF] Cesarini | Erlang Programming[END_REF], an actor (referred to as a supervisor) may be notified via a message that a linked actor has terminated abnormally (i.e., crashed), which allows it to take remedial action (e.g., avoid waiting indefinitely for a message, or spawn a replacement actor). Erlang supervision hierarchies admit a form of monitor-oriented programming [START_REF] Cassar | On Implementing a Monitor-Oriented Programming Framework for Actor Systems[END_REF], whereby the recovery logic is teased apart from the application logic, so as to keep the latter as clear as possible; the recovery logic can instead be encapsulated within the supervision structure encasing the application.

Finally, our mapping from REGs to Erlang programs heavily uses atoms, that is literal constants which do not carry any value but can be used as a value; Erlang atoms corresponds to values of some unit types in typed languages.

Global Graphs for Reversibility

We propose a variant of global graphs, dubbed reversibility-enabling (global) graphs (REGs for short) that generalises the branching construct to cater for reversibility. We will use REGs to render the recovery model described in Section 1. The syntax of REGs uses control points 4 to univocally identify positions where choices have to be made on how to continue the protocol. Syntactically, control points are written as i • A, where i is a strictly positive integers and A ∈ P is the participant responsible for taking the decision.

Definition 1 (Reversibility-enabling global graphs). The set G of reversibility-enabling global graphs (REGs) consists of the terms G derived by the grammar obtained by replacing the last two productions of the grammar in Section 2.1 with

G ::= . . . sel i • A G 1 unless φ 1 + G 2 unless φ 2 ( 1
)
repeat i • A {G} (2)
that satisfy the following conditions:

in i • A G, A is the active participant of G and for any two control points i • A and j • B occurring in different positions of a REG it must be the case that the indices are distinct, i = j.

In (1), the formulas φ h (for h ∈ {1, 2}) are reversion guards expressed in terms of boolean expressions.

In Definition 1, the participant A in (1) non-deterministically decides which branch to follow; in (2) it decides whether to repeat the body G or exit an iteration. Hereafter, we consider equivalent REGs that differ only in the indices of control points (the indices of control points are, in fact, irrelevant as long as they are unique) and may omit control points when immaterial, e.g., writing

G unless φ + G unless φ instead of sel i • A G unless φ + G unless φ .
The new branching construct (1) extends the usual branching construct of choreographies to control reversible computations. The semantics of this constructs is rendered by the encoding in Section 4 which realises the following intended behaviour. To execute sel i • A G 1 unless φ 1 + G 2 unless φ 2 we first non-deterministically choose branch h ∈ {1, 2} and execute the REG G h . If the guard φ h is false once the execution of G h terminates then the execution stops (i.e., it executes as normal); otherwise, if the other branch has not been tried yet, the execution of G n is reversed and the other branch is executed. Note that, by keeping track of all reversed branches and fully executing the last branch when all the others have been reversed, we can easily generalise to a branching construct sel i • A G 1 unless φ 1 + • • • + G h unless φ h with h ≥ 2; for simplicity we just consider h = 2 here.

Definition 1 parameterises REGs on the notion of reversion guard. However, our study required us to address crucial design choice and resolve how reversion guards are to be rendered in a language like Erlang (without a global state). Roughly, reversion guards can be thought of as propositions predicating on the state of the forward execution. A key requirement for a proper projection, however, is that the evaluation of such guards must be "distributable", i.e., we want revision guards to be "projectable" from the global view to the components realising the behaviour of the participants. To meet this requirements, we use local guards, i.e., boolean expression that predicate on the state of a specific participant and assume that a revision guard is a conjunction of the local guards at each participant. More concretely, we exploit Erlang's support [START_REF]Erlang Run-Time System Application[END_REF] for accessing the status of a process implementing a participant via system functions such as process info or system info, which return a dictionary with miscellaneous information about a process or a physical node respectively. Predicate queue_len checks if the size of the mailbox is above a threshold, whereas message_exists checks for the presence of a message matching some pattern in a mailbox. Other examples of reversion guards are conditions on PIDs and port identifiers, heap size, or the status of processes (e.g., waiting, running, runnable, suspended).

Our reversible semantics still requires well-branchedness: a REG, say G, is wellbranched when so is the global graph obtained by removing reversion guards from G. This guarantees communication soundness in presence of reverse executions.

From REGs to Erlang

This section shows how we map REGs into Erlang programs. This mapping corresponds to the definition of projecting the global view provided by REGs into Erlang implementations of their local view. Our encoding embraces the principles advocated in [START_REF] Cassar | Reliability and fault-tolerance by choreographic design[END_REF] and reviewed in Section 1: we strive for a solution yielding a high degree of decoupling between forward and reverse executions. Unsurprisingly, the most challenging aspect concerns how branches are projected. This is done by realising a coordination mechanism which interleaves forward and reversed behaviour, as described in Section 3. In the following, we first describe the architecture of our solution. We then show how forward and reversed executions are rendered in it. We discuss our design choices and a few possible alternative solutions in Section 5.

Participant Actor Selector Actor

Participant Monitor

Selector Monitor

Forward Attempt (Phase 2)

< l a t e x i t s h a 1 _ b a s e 6 4 = " A 4

d 8 A x S 2 S Y 5 Q E F Y i i i v q 5 s Q T u t w = " > A A A B 7 H i c b V B N T 8 J A E J 3 i F + I X 6 t H L R j D x R F o u 6 o 3 E i 0 d M L J B A Q 7 b L F l a 2 u 8 3 u 1 o Q 0 / A c v H t R
B 5 W v w Y j S d K Y C k M 4 1 r r v u Y k J M q w M I 5 z O K 4 N U 0 w S T K R 7 T v q U C x 1 Q H W X 7 t H F 1 Y Z Y Q i q W w J g 3 L 1 9 0 S G Y 6 1 n c W g 7 Y 2 w m e t V b i P 9 5 / d R E 1 0 H G R J I a K s h y U Z R y Z C R a v I 5 G T F F i + M w S T B S z t y I y w Q o T Y w O q 2 B C 8 1 Z f X i
E F Y i i i v q 5 s Q T u t w = " > A A A B 7 H i c b V B N T 8 J A E J 3 i F + I X 6 t H L R j D x R F o u 6 o 3 E i 0 d M L J B A Q 7 b L F l a 2 u 8 3 u 1 o Q 0 / A c v H t R
B 5 W v w Y j S d K Y C k M 4 1 r r v u Y k J M q w M I 5 z O K 4 N U 0 w S T K R 7 T v q U C x 1 Q H W X 7 t H F 1 Y Z Y Q i q W w J g 3 L 1 9 0 S G Y 6 1 n c W g 7 Y 2 w m e t V b i P 9 5 / d R E 1 0 H G R J I a K s h y U Z R y Z C R a v I 5 G T F F i + M w S T B S z t y I y w Q o T Y w O q 2 B C 8 1 Z f X i
E F Y i i i v q 5 s Q T u t w = " > A A A B 7 H i c b V B N T 8 J A E J 3 i F + I X 6 t H L R j D x R F o u 6 o 3 E i 0 d M L J B A Q 7 b L F l a 2 u 8 3 u 1 o Q 0 / A c v H t R
B 5 W v w Y j S d K Y C k M 4 1 r r v u Y k J M q w M I 5 z O K 4 N U 0 w S T K R 7 T v q U C x 1 Q H W X 7 t H F 1 Y Z Y Q i q W w J g 3 L 1 9 0 S G Y 6 1 n c W g 7 Y 2 w m e t V b i P 9 5 / d R E 1 0 H G R J I a K s h y U Z R y Z C R a v I 5 G T F F i + M w S T B S z t y I y w Q o T Y w O q 2 B C 8 1 Z f X i

Architecture

The abstract architecture of our proposal is given in Fig. 4. Each participant of a REG is mapped to a pair of Erlang actors, the participant actor and the participant monitor which liaise with one another in order to realise reversible distributed choices. The execution of a distributed choice is supported by another pair of (dynamically generated) actors, the selector actor which liaises with its corresponding selector monitor. The basic idea is that participant and selector actors are in charge of executing the forward logic part the choice while their respective monitors deal with the reversibility logic.

A key structural invariant of the architecture is that monitors can interact only with their corresponding participant or with the monitors of the selectors currently in execution. This is emphasised by the arrows in Fig. 4, which are meant to represent the information and control flow of our solution. The coordination protocol required to resolve a distributed choice specified in a REG is made of the following phases:

1. Inception: The selector actor (started at a branching point) decides which branch to execute and communicates its decision to the participants involved. 2. Forward attempt: Participant actors execute the selected branch accordingly and report their local state at the end of the branch to their participant monitor. 3. Guards checking: Participant monitors check their reversion guard and communicate the outcome to the selector monitor. 4. Continuation: The selector monitor aggregates the individual outcome of all participant monitors and reports the aggregated result to the selector actor. 5. Decision: Based on suggestion forwarded by the selector monitor, the selector actor decides whether to continue forward or reverse the execution and communicates the decision to all participants, which in turn propagate it to their participant monitor.

These phases roughly correspond to the arrows in Fig. 4.

Branching actors & monitors

We now describe the behaviour of actors and monitors in a choice, with the help of their automata-like representation in Fig. 5. The coordination protocol that we describe here resembles a 2-phase commit protocol where participants report the outcome of local computations to a coordinator that then decides how to continue the execution.

When participant actors (start to) reach a branching point, the inception phase begins. The actor corresponding to the (unique) active participant of the choice spawns the selector actor and waits from the selector message telling which branch to take in represents that an input action is expected from all participant monitors involved into a branch; likewise, the fat arrow in the selector actor represent that the outputs will be done for all participant actors. The fat dashed arrow in the selector monitor indicates that an input action is expected from all the participant monitors and that at least one of them is a rev message.

Fig. 5. Automata-like description of actors and monitors for the projection of branches the choice; all other participant actors just wait for the selector's decision. The act of spawning the selector arrow by the active participant is represented in Fig. 5 via the gray arrow and the cloud in the automaton of the participant actor. Subsequently, all the actor participants involved in a branch will wait from the selector to instruct them with the branch (either left or right) to take-the yellow arrows in the automaton of Fig. 5. Upon the receipt of such a message, participant actors first forward this message to their monitor and then enter the second phase executing the branch-represented by the cloud in the automaton. The third phase starts (if the chosen branch does not diverge) when participant actors finish the branch (possibly at different times) and they signal to their monitor that they are ready to exit the choice. This is done by the exit message which also carries the local state of execution (described in Section 3). At this point, participant actors take part only in the last phase: they receive from the selector either an ack message (confirming that the choice has been resolved) or a rev message to reverse the execution. In either case they propagate the message to their monitor and either "commit" the branch or return to the state that waits for the message dictating the next branch to take. Participant actors behave uniformly but for the active one, which has the additional task of spawning the selector at the very beginning (for non-active participants the gray transition is an internal step not affecting communications). Each participant monitor waits for the message carrying the local state that its participant actor sends at the end of the second phase in the exit message. The state is used to check whether the reversion guard of the branch, say φ, holds or not. If φ holds for the local state of the participant actor, the participant monitor sends the selector monitor either a request to reverse the branch (message rev). Otherwise the monitor sends a message to commit the choice (message exit). In Fig. 5 this is represented by the label sel m!d, where d stands for decision. After this, the monitor waits from its participant actor for the rev or the ack message sent in the last phase: if rev is received the monitor returns to its initial state and leaves the branch otherwise.

The selector actor spawned in the inception phase starts by spawning a selector monitor and then deciding which branch to take initially-represented in Fig. 5 by the grey transition and the cloud in the automaton of the selector. After communicating its decision to all participant actors, the selector waits for the request of its monitor and starts phase five of Section 4.1 by deciding whether to reverse the branch or not. The decision process is as follows: if the selector receives an ack message then the branch is committed and the selector monitor terminates. Otherwise, the selector participants receive a rev message to reverse the branch. If there are branches that have not been tried yet then the last executed branch is marked as "tried", a branch not been attempted yet is selected, and a rev message is sent to all participant actors. Otherwise, the decision to commit the branch is taken and the ack message is sent to all participant actors. In the former case, the selector returns to its initial state, and terminates otherwise.

The selector monitor participates to the fourth phase. It first gathers all the outcomes from the guard-checking phase from all the participant monitors involved into the choice. Recall that a rev message is received from any participant monitor whose revision guard becomes true otherwise, while an ack message is received from any participant monitor whose revision guard does not hold. Then, the selector monitor computes an outcome to be sent to the selector actor: if all received messages are ack then an ack message is sent to the selector actor, otherwise the monitor sends a rev message to the selector actor. In both cases, the selector monitor terminates; a new selector monitor is spawned by the selector actor if the branch is actually reversed.

Iteration is a simplification of a distributed choice: we just generate a selector for an iteration but not its monitor. The reason for not having a monitor for the selector is quite straightforward: there is no reversible semantics to be implemented for the iteration. This does not imply that within the body of an iteration a reversible step can not be taken (e.g., there can be an inner choice), but just that iterations are not points at which the computation can be reversed. The selector (instantiated by the active participant of the iteration, similarly to choices) just decides whether to iterate or exit the loop. A participant actor within a loop, after completing an iteration, awaits the decision from the selector actor and continues accordingly.

Compiling to Erlang

The code generated for the projections from REGs to Erlang is discussed below. We focus on the compiled code for the branches constructs, since the compilation of the other constructs is standard and therefore omitted. Our discussion uses auxiliary functions for which the code is not reported 5 phase of Section 4.1, waiting for the message from its monitor, and decides accordingly how to continue the execution of the choreographed choice. As in the case of the participant actor, the snippet of the participant monitor (lines 22-43) does not make it explicit the code for the monitoring of the left and right branches (commented lines 25 and 30). The auxiliary function check_guard returns the evaluation of the guard for the state provided by the participant (lines 26-28 and 31-33). The function get_selector_monitor retrieves the PID of the selector monitor from the control point value cp.

The selector monitor, spawned by the selector process, is registered with the name sel_mon_cp (lines 45-47) where cp is the value passed through the second parameters CP when invoking sel_act. Note that the invocation to get_selector_monitor on line 35 returns the atom sel_mon_cp. The snippet for the selector monitor uses the auxiliary function participants returning the list of participant actors involved in the branch cp. The outcome Msg is computed on lines 72-78 and sent to the selector on line 79. The selector monitor awaits a message from all the participant monitors involved in the branch (lines 72-73), and then it decides the message to communicate to the selector actor. If at least one of the messages received is rev, then the final message is rev, otherwise the final message is ack.

Design Choices & Alternatives

We now discuss our design choices and some potential alternatives. As remarked earlier, the architecture and the coordination proposed here strives for a high degree of decoupling between the run-time support of the application and revision logics. In light of this, we tried to limit the overhead required to manage the reversible semantics proposed in Section 3.

Not surprisingly, the design choices we had to make mainly concerned the implementation of branches and the corresponding reversible behaviour. A first decision we had to take related to the realisation of the application logic part of the branches. Our solution introduces selector actors to implement the policy for selecting a branch. A plausible alternative could have been to let the actor corresponding to the active participant to manage the choice. We argue that such alternative has two main drawbacks. Firstly, it makes the projection of active and non-active participants less uniform, negatively impacting on the cohesion of the architecture. This lack of symmetry would also impact on the corresponding monitors, which would invariably become more complex-ideally, the monitor logic is kept as simple as possible, since this is conducive to correct, efficient code. Also, Erlang does not allow multi-threaded actors, hence this alternative would have introduced unnecessary dependencies between actors and monitors.

We remark that the decision process would typically be specified in the application logic of the active participant. For instance, one could specify priorities on branches or allow the same branch to be tried more than once and reversed only after a certain number of attempts have failed. Our current solution abstracts away from this, and adopts a non-deterministic policy (using an Erlang randomisation function) for simplicity.

Instead of dynamically spawning selector actors, we could statically generate them. This solution would simplify the projection operation trading on efficiency since, at run-time, not all branches are typically executed (e.g., in the case of nested branching).

Local guards are designed to attain locally checkable conditions (cf. Section 3). A less ad-hoc mechanism could possibly be considered following the approach taken in [START_REF] Bocchi | A theory of design-by-contract for distributed multiparty interactions[END_REF] where "global" logical formulae (dubbed global assertions) are projected into local ones. This is a more complex approach that nevertheless could be worth exploring as it could lead to more expressive frameworks. For instance, it would allow the definition of hyperproperties [11] such as as those that compare the size of message queues at different actors over time. Note that this could require non-trivial interactions among monitors for exchanging local information (or more complex aggregation at the branch monitor). An intriguing research direction would be to explore to which extent these non-trivial interactions could be automatically derived by the projection of global conditions. Another crucial decision we had to contend with concerned the execution points at which the reversion guards should be checked. Here the range of possibilities is fairly broad and we opted for an "optimistic" policy, leaving the realisation of other alternative policies for future work. For instance, another alternative would be one where each monitor would continuously check the guard and trigger the reverse execution as soon as it is breached (instead of waiting for the completion of the branch). This option is interesting because it avoids the wasteful execution of the entire branch before trying to then reverse it. However, such a "preemptive" approach would also make actors and monitors more complex (e.g., participant and selector actors would need to "poll" for message arrival ) and would increase monitoring overheads as well.

Final remarks

We have presented a minimally-intrusive extension to global graph choreographies [START_REF] Guanciale | An abstract semantics of the global view of choreographies[END_REF] for expressing reversible computation. We showed how these descriptions could be realised into executable actor-based Erlang programs that compartmentalise the reversion logic as Erlang monitors, minimally tainting the application logic.

Related Work. The closest work to ours is [START_REF] Nishida | A reversible semantics for erlang[END_REF][START_REF] Neykova | Let it recover: multiparty protocol-induced recovery[END_REF][START_REF] Field | Transactors: a programming model for maintaining globally consistent distributed state in unreliable environments[END_REF]. In [START_REF] Nishida | A reversible semantics for erlang[END_REF] a reversible semantics for a subset of Erlang is given. The goal of [START_REF] Nishida | A reversible semantics for erlang[END_REF] is a debugger based on a fully reversible semantics. To achieve this, the Erlang virtual machine is modified in order to keep track of computational history. Our goal is different since we focus on controlled reversibility [START_REF] Lanese | Controlled reversibility and compensations[END_REF]. Our framework automates the derivation of rollback points (namely the exact point at which the execution has to revert) from the recovery logic. Also, the use of monitors avoids any changes to Erlang's run-time support. Choreographies are used in [START_REF] Neykova | Let it recover: multiparty protocol-induced recovery[END_REF] to devise an algorithm that optimises Erlang's recovery policies. More precisely, global views specify dependencies from which a global recovery tables are derived. Such tables tell which are the safe rollback points. The framework then exploits the supervision mechanism of Erlang to pair participant with a monitor. In case of failure, the monitor restarts the actor to a consistent rollback point. One could combine our approach with the recovery mechanism of [START_REF] Neykova | Let it recover: multiparty protocol-induced recovery[END_REF] so as to generalise our reversible semantics to harness fault tolerance. This is not a trivial task, because the fault-tolerance mechanism of [START_REF] Neykova | Let it recover: multiparty protocol-induced recovery[END_REF] needs to follow a specific protocol, making it unclear whether participants can be automatically derived. In [START_REF] Field | Transactors: a programming model for maintaining globally consistent distributed state in unreliable environments[END_REF] actors are extended with checkpoints primitives, which the programmer has to specify in order to rollback the execution. In order to reach globally-consistent checkpoints severe conditions have to be met. Thanks to the correctness-by-design principle induced by global views, our approach automatically deals with checkpoints, relieving this burden from the programmer.

Other works [START_REF] Phillips | A reversible process calculus and the modelling of the ERK signalling pathway[END_REF][START_REF] Mezzina | Causally consistent reversible choreographies: a monitorsas-memories approach[END_REF][START_REF] Mezzina | Reversibility in session-based concurrency: A fresh look[END_REF] have investigated the use of monitors to steer reversibility in concurrent systems. In [START_REF] Phillips | A reversible process calculus and the modelling of the ERK signalling pathway[END_REF] a monitored reversible process algebra is presented where each agent is paired with a monitor. But, unlike our approach, the monitor tells the agent what to do both in the forward and in the reverse way. In [START_REF] Mezzina | Causally consistent reversible choreographies: a monitorsas-memories approach[END_REF][START_REF] Mezzina | Reversibility in session-based concurrency: A fresh look[END_REF] the authors investigate the use of monitors to steer reversibility in message oriented systems. Here monitors are used as memories storing information about the forward execution of the monitored participants, and exploit this information to reconstruct previous states. As in our approach, in [START_REF] Mezzina | Reversibility in session-based concurrency: A fresh look[END_REF] participants and their monitors are derived from a global specification as well. We diverge from [START_REF] Mezzina | Causally consistent reversible choreographies: a monitorsas-memories approach[END_REF][START_REF] Mezzina | Reversibility in session-based concurrency: A fresh look[END_REF] in several aspects. Firstly, our monitors do not store any information about the forward computation. Secondly, all the monitors coordinate amongst each other to decide whether to revert a particular computation or not. The coordination mechanism of our monitors is automatically derived. Moreover in our approach reversibility is triggered at run-time when certain conditions (specified at design-time in the recovery logic) are met.

Conclusions. We have presented a method to automatically derive reversible computation as Erlang actors. A key aspect of our approach is the ability to express, from a global point of view, when a reverse distributed computation has to take place and not how. Starting from a global specification of the system, branches can be decorated with conditions that at run-time will enable the coordinated undoing of a certain branch. Another novelty of our approach is the use of monitors to enact reversibility. We leave as future work the measurement of the overhead of our approach on the normal forward semantics of the actors, in terms of messages and memory consumption.

Fig. 3 .

 3 Fig. 3. The diagram of a global graph and its semantics

Example 5 .

 5 Consider the following concrete examples of revision guards: queue_len(Threshold, State) -> Info = from_list(State), {_,Len} = find(message_queue_len, State), (Len > Threshold). message_exists(Filter, State) -> Info = from_list(State), {_,messages} = find(message_queue_len,State), Filter(messages).

  4 9 Q d 5 8 9 + 4 l B 4 U f M k k L + / N Z G Z e m H C m j e t + O 6 W N z a 3 t n f J u Z W / / 4 P C o e n z S 0 T J V h P p E c q l 6 I d a U M 0 F 9 w w y n v U R R H I e c d s P p 7 c L v P l G l m R Q P Z p b Q I M Z j w S J G s L F S p z 5 I J q w + r N b c h p s D r R O v I D U o 0

d 9 s 3 D

 3 T c + 2 a t 5 R Z p l O E M z u E S P L i C F t x B G 3 w g 8 A j P 8 A p v j n R e n H f n Y 9 l a c o q Z U / g D 5 / M H M 2 e O W g = = < / l a t e x i t > < l a t e x i t s h a 1 _ b a s e 6 4 = " A 4 d 8 A x S 2 S Y 5 Q

  4 9 Q d 5 8 9 + 4 l B 4 U f M k k L + / N Z G Z e m H C m j e t + O 6 W N z a 3 t n f J u Z W / / 4 P C o e n z S 0 T J V h P p E c q l 6 I d a U M 0 F 9 w w y n v U R R H I e c d s P p 7 c L v P l G l m R Q P Z p b Q I M Z j w S J G s L F S p z 5 I J q w + r N b c h p s D r R O v I D U o 0

d 9 s 3 D

 3 T c + 2 a t 5 R Z p l O E M z u E S P L i C F t x B G 3 w g 8 A j P 8 A p v j n R e n H f n Y 9 l a c o q Z U / g D 5 / M H M 2 e O W g = = < / l a t e x i t > < l a t e x i t s h a 1 _ b a s e 6 4 = " A 4 d 8 A x S 2 S Y 5 Q

  4 9 Q d 5 8 9 + 4 l B 4 U f M k k L + / N Z G Z e m H C m j e t + O 6 W N z a 3 t n f J u Z W / / 4 P C o e n z S 0 T J V h P p E c q l 6 I d a U M 0 F 9 w w y n v U R R H I e c d s P p 7 c L v P l G l m R Q P Z p b Q I M Z j w S J G s L F S p z 5 I J q w + r N b c h p s D r R O v I D U o 0

d 9 s 3 DFig. 4 .

 34 Fig. 4. Our architecture

-

  The syntax of labels is of the form id!msg or id?msg indicating respectively the act of sending (!) or receiving (?) the message msg to or from the actor id.-Messages e, st, r, l stand respectively for exit, state, right and left. -Transitions of different automata are coloured to help the reader understanding the flow of the communication: outputs or inputs of actors match when the corresponding transitions in the automata have the same colour. -The fat arrow in the selector monitor

  . Each global graphs G can be represented as a rooted diagram with a single source node and a single sink node respectively represented as • and . Other

						branch gate
			fork gate	branch gate
	source node
		G
	A-→B : m	G	G	G	G	G
		G
	sink node
		join gate	merge gate		merge gate
	interaction	sequential	parallel	branching		iteration
		Fig. 2. A visual notation for global graphs

  .

	1	act_A_cp() ->	44	sel_act(Attempt,CP) ->
	2	%Pid = list_to_atom("sel_act_"
	3	%++ integer_to_list(cp)),
	4	%register("Pid,
	5	%	spawn(sel_act,[cp])),
	6	receive
	7	{cp,left} ->
	8		mon_A ! {cp, left}
	9		%CODE OF LEFT BRANCH
	10		;
	11	{cp,right} ->
	12		mon_A ! {cp, right}
	13		%CODE OF RIGHT BRANCH
	14	end,
	15	mon_A!{cp, exit, process_info(self())},
	16	receive
	17	{cp,ack} -> mon_A ! {cp, ack};
	18	{cp,rev} ->
	19	mon_A ! {cp, rev},
	20	act_A_cp()
	21	end.
	22	mon_A_cp() ->
	23	receive
	24	{cp, left} ->
	25	%CODE FOR LEFT BRANCH MONITOR%
	26	receive{cp, exit, Info} ->
	27	G = check_guard(Left_guard, Info)
	28	end;
	29	{cp, right} ->
	30	%CODE FOR RIGHT BRANCH MONITOR%
	31	receive{cp, exit, Info} ->
	32	G = check_guard(Right_guard, Info)
	33	end
	34	end,
	35	Sel_m = get_selector_monitor(cp),
	36	case G of
	37	true -> Sel_m ! {cp, rev};
	38	_	-> Sel_m ! {cp, ack}
	39	end,
	40	receive
	41	{cp, rev} -> mon_A_cp();
	42	{cp, ack} -> ok
	43	end.

Control points can be automatically generated; for simplicity, we explicitly put them in the syntax of REGs.

These can however be found at http://staff.um.edu.mt/afra1/rgg.

Note that the value cp is statically determined by the compiler.

The code for the participant actor (lines 1-21) is parametrised with respect to cp, the value of the control point 6 univocally identifying the point of branch in the REG. The commented lines 2-5 are generated only for the code of the active participant which spawns the selector actor of the branch cp. Note that the process is registered under a unique name sel_act_cp (which is an atom). This snippet is actually a template which would be filled up with the code generated for the participant communications respectively on the left and on the right branches (i.e., the commented lines 9 and 13).

The Erlang process spawned by a participant actor implementing the selector actor executes the function on lines 44-69. This function takes two parameters: the Attempt representing the branches chosen so far and the control point CP identifying the choice. The former parameter is a list of atoms left and right; note that the empty list is passed initially when the process is spawned and that (in our case) the size of this list should never exceed 1. As discussed above, the selector chooses a branch (lines 48-54) and communicates its decision to the participants of the branch (lines 55-56, where participants is computed at compile time (from the global graph script) and returns the participants of a branch given its control point). Finally, the selector enters the fourth