7.3.1 Code Offloading

In recent years, offloading of computations between mobile devices and the cloud has been proposed to address the limitations of mobile platforms. For example, Kumar et al. [1] discuss program partitioning to support offloading, while Rahman et al. [6] suggest using virtual machine migration. In mobile cloud computing systems using the former approach, the application developer manually partitions a program and then specifies how to offload parts of an application to remote servers. In MCC systems using the latter approach, the entire process or entire OS is moved to a cloud space [7]. However, program partitioning requires substantial developer effort, while VM migration can be prohibitively inefficient [8].

An alternative is to provide automatic data-partitioning solutions for fine-grained, energy-aware offloading of computations. Mobile cloud systems such as MAUI [9] use a combination of virtual machine migration and automatic code partitioning to decide at runtime which methods of an object's code should be executed remotely. The goal of MAUI is to minimize energy consumption on mobile devices by offloading computations. However, MAUI has several limitations. First, it only supports sequential execution: The object in a mobile device is paused while it awaits the results from offloaded code. Second, MAUI only supports a single remote server and requires manual annotation of methods by the programmer and offline static analysis of the source code before execution. Other systems for offloading computations include CloneCloud [10], ThinkAir [11], and COS [8]. Each of these systems has its own limitations. For a good review, we refer interested readers to Ref. [12].

IMCM supports a concurrent application model, enabling simultaneous execution on both mobile device and multiple remote cloud resources.

7.3.2 Coordination Constraints

Actors are autonomous and decentralized, so they must explicitly synchronize when they need to coordinate their actions. A number of frameworks have been developed to simplify the expression of coordination. We review some of the important frameworks. A hierarchical model of coordination was defined in Ref. [13]. In the Directors coordination model, actors are organized into trees. Messages sent between two actors (say A and B) that need to be coordinated are delivered through the closest common ancestor: They are forwarded to a parent node (representing a director), which forward it to its parent, and so on, until a common ancestor of A and B is reached. Then the message is sent down to subdirectors until it reaches the target. This enables enforcement of hierarchical policies. Directors do not support arbitrarily overlapping constraints. Furthermore, the model does not provide semantics for dynamic reconfiguration; actors are inserted into the tree when they are constructed.

Another approach is to use computational reflection and meta-programming. An actor's mail queue buffers messages when they arrive and dispatches them to the actor. The mail queue can be programmed to reject or reorder messages, thus enforcing constraints on acceptable ordering of messages. Similarly, messages are sent to other actors through a dispatcher. The dispatcher can also be customized to reorder messages, or to communicate with a mail queue before sending a message in order to synchronize the state. In this framework, an actor's mail queue and dispatcher are considered separate actors. Astley and Agha [14] and Sturman [15] propose using actor systems with meta-actors, which require a two-level semantics. Such a semantic formalization has been developed in Refs [16,17].

In the Actor-Role-Coordinator (ARC) model [18], coordination is transparent to base-level actors; coordination tasks are divided into intrarole and interrole communication. While this hierarchical design provides load balancing for highly dynamic systems, the coordination structure itself is static. ARC systems therefore avoid security issues through reconfiguration, but require a restart to adapt to changing specifications.

A scalable coordination model must be able to cope with uncooperative actors. We discuss scoping of synchronization constraints to handle scenarios such as permanent locking of a target actor because of a malicious or buggy actor.

7.3.3 Session Types

Interaction types, used to capture communication protocols among parallel processes, were first introduced in the context of the π-calculus [19] by Honda [20]. Targeting two-party interactions, Honda's system could statically ensure that the participants have compatible behavior, by requiring dual types; that is, behaviors in which each participant expects precisely the message sequence that the other participant sends and vice versa.

Many real-world protocols involve more than two participants, which makes their description in terms of multiple two-party sessions unnatural. The Web Services Choreography Description Language [21] is an XML-based language that allows the description – from a global perspective – of protocols that involve multiple concurrent entities (Web services and clients). The notion of an end-point projection of such a global specification was first studied by Carbone et al. [22], along with the associated correctness requirements. The idea was further studied by Honda et al. [23], whose session types support multiple participants: A global type specifies the interactions among all participants from a global perspective, and a projection algorithm then mechanically derives the behavior specification of each individual participant, that is, its local type. A subtyping relation for Honda's system was first studied by Gay and Hole [24], who dealt with recursive types through an unfold function. Their system treats the substitutability concept in a syntactic manner, making subtyping statically decidable.

Asynchronous session types were first studied by Gay and Vasconcelos [25], who proposed session types for an asynchronous flavor of the π-calculus. Parameters were introduced to session types by Yoshida et al. [26], enabling type-safe interactions among a fixed, but not statically known, number of participants.

Castagna et al. [27] proposed a specification language for global types that is closer to regular expressions; they investigated the requirements for correctness after projection, and guarantee certain liveness properties. Their work was the starting point for the full version of the material in Section 7.6, by Charalambides et al. [4,28]. The theoretical foundations of runtime monitoring of protocols with assertions were laid by Bocchi et al. [29], who studied the conditions under which localized, end-point runtime checks suffice to enforce globally specified assertions. In a similar manner, Neykova et al. [30] extended Scribble [31] with timing constraints, and studied the conditions that enable purely local, end-point runtime monitoring of distributed systems with real-time constraints.

Conventional session types are not suitable for typing interactions in actors, so we discuss a programming language and session type system that capture the inherent asynchrony of actor programs.

7.4.1 IMCM Framework: Overview

Many organizations, developers, and users benefiting from cloud resources have privacy requirements, expectations, and policies in terms of how different private or public cloud resources can be used by a mobile application. Without having enough flexibility in the offloading framework to address these requirements, many users will not be able to benefit from the cloud resources. In order to accommodate these requirements, we describe a language to define policies, and explain how the IMCM framework can be customized to address them.

While addressing these policies is critical, other quantitative properties, such as performance and energy characteristics on the mobile device, greatly affect the quality of an application in meeting overall user requirements. The framework allows for configuration of policies that need to be enforced, but such policies may affect the performance and energy usage of the application. On the other hand, it may be possible to leverage optimized performance and energy to provide stronger privacy guarantees. Through the framework, we discuss mechanisms that allow developers or users to control all privacy, performance, and energy aspects of their applications via code offloading.

7.4.2 Cloud Application and Infrastructure Models

In order to formulate the application component offloading problem, a comprehensive mobile-hybrid-cloud application model is needed. This section summarizes our views on clouds, cloud applications, and mobile-cloud applications.

Over time, cloud services have moved from the model of public cloud spaces to private clouds and, recently, to a hybrid model combining both [35]. Cloud infrastructure has traditionally been provided by large third-party organizations, and thus has been referred to as the public cloud. However, storing data on third-party machines suffers from a potential lack of control and transparency in addition to having legal implications [36]. In order to address this problem, cryptographic methods are usually used to encrypt the data stored in public clouds, while decryption keys are disclosed only to authorized users. However, those solutions inevitably introduce heavy computational overhead for continuous encryption and decryption of data, distribution of decryption keys to authorized users, and management of data when fine-grained data access control is desired. Thus, cryptographic methods do not scale well, have significant overhead, are expensive to maintain, and are often slow, especially in widely geographically distributed environments such as clouds.

To address some of those limitations, several techniques, such as attribute-based encryption (ABE), proxy re-encryption and lazy re-encryption, and homomorphic encryption techniques, have been developed to provide attribute-based encryption while delegating part of the required decryption to the cloud or providing limited in-cloud computations on the ciphered text (encrypted data) without revealing data content. However, these efforts have had the traditional data-centric view of cloud computing, focused on storing data and providing services to access the stored data. If data storage is the primary use for the cloud, the required data access control is already mature enough that a fine-grained access control system can be implemented effectively.

However, in modern cloud applications, the resources stored in the cloud contain more than just data. These resources contain part of the application code that results in access operations for execution of the code inside the cloud. It is obvious that the certificate-based authorization systems fail to address these types of applications, as an encrypted piece of code within the cloud cannot be executed without decryption, thus revealing the content to the cloud provider. As a result, companies have gradually moved toward building their own private clouds [36]. Storing sensitive data within private clouds aligns with the traditional on-premises application deployment model whereby sensitive data reside within the enterprise boundary and are subject to its physical, logical, and personnel security and access control policies [35]. However, owning and maintaining a private cloud is usually not as efficient, scalable, reliable, or elastic as using one of the public ones that are offered, supported, and maintained by large third-party companies.

In recent years, a combination of both private and public cloud spaces has been used that allows users to benefit from all the advantages of the public cloud while keeping their confidential or sensitive data and algorithms in-house [37]. In order to cover different applications, our framework simply views the cloud as the most general form that combines one or multiple private and public cloud spaces. This allows the creation of a general, flexible, elastic hybrid cloud space to address the different needs of a specific organization while different users (including both internal staff and external clients) can access cloud resources with different access levels and limitations.

7.4.3 Cloud Application Model

Although the benefits of cloud computing for enterprise consumers and service providers have been thoroughly explored over the past few years, its effect on end users, applications, and application developers is still not clear. As mentioned in the previous section, the traditional data-centric view of cloud services needs to be replaced with a more general data/computation-centric view. To achieve that transition, the current common client-server-based, service-oriented architecture [38], which provides services on data stored in the cloud to external users, needs to be replaced with a more general, elastic architecture that dynamically and transparently leverages cloud resources to provide services and support resource limitations on the end user. In such an elastic application development environment, components that store data or perform computations are transparently scattered among the private clouds, public clouds, and end-user devices. When such an application is launched, an elasticity manager monitors the execution environment and resource requirements of the application to make decisions about where components should be launched and when they should migrate from device to cloud, or from cloud to device, according to changes in user preferences. Rather than a simple and rigid solution wherein nearly all processing and storage are either on the device or in the cloud, an elastic mechanism should have the ability to migrate functionality between the device and the cloud. This ability would allow the device to adapt to different workloads, performance goals, and network latencies.

An important design objective of this modern application development approach is to build an infrastructure with enabling functions such as network protocols, secure communication, and resource management, so that the new elastic computing model will introduce minimal extra considerations for application developers. Unnecessary details of distribution and move-around of application components should be masked from the programmers, while access to different components and resources is still restricted for different users. Elastic components need to access sensitive or restricted resources, and thus an authorization system is needed to give the required component access privileges. For access control, elastic application components on the cloud should adhere to the property of least privileges. Which permissions a component might have may depend on its execution location. Implicit access to device resources may require additional scrutiny when the component is no longer running local to the device.

End users interact with that elastic architecture system by using their mobile devices. That inevitably requires us to address the problem of minimizing energy usage on the mobile device (as detailed in Section 7.4.8) to support complex applications. In order to do so, we need to be able to attribute energy consumption to components of an application. The actor model lends itself naturally to defining the granularity for energy monitoring at the level of individual or groups of actors. We leverage it as the application programming model for the IMCM framework. Actors can be the primitive units for targeting energy measurements, while groupings of actors of a particular type can be considered for aggregations/higher level metrics like average energy consumption. Schedulers for actor-based languages also view actors as basic computational entities for scheduling decisions, so the underlying runtime can be instrumented to track actors running at different time intervals.

As a result, our view of a mobile-cloud application consists of actors distributed across local mobile devices and different cloud spaces.

7.4.4 Defining Privacy for Mobile Hybrid Cloud Applications

We want to enable developers and users to restrict access to different resources, and enable the mobility of a sensitive or confidential application component's resources, based on required policies. This requires the framework to follow authorization rules defined by the organizations, developers, or users. Elastic application components on the cloud should adhere to the property of least privileges. Which permissions a component should have may depend on its execution location, application requirements, or user concerns. Implicit access to device resources may require additional scrutiny when the component is no longer running local to the device [39]. A comprehensive security solution requires authentication, access control, and auditing. There has been a significant amount of work on authentication and auditing for cloud applications in the past, and the existing solutions are mature enough to address most applications [39–43]. Therefore, we focus on an approach for adding policy-based privacy to our framework that restricts the accesses, actions, and mobility of components.

Before we delve into the details of the authorization system and its language, policy description, and evaluation rules, we describe in detail the image recognition application that was first introduced in Section 7.2 as an example to demonstrate the usage of the privacy-related capabilities of our system.

7.4.5 A Face Recognition Application

An image-processing application, called Image, recognizes faces in a given image by using a database of known faces. Figure 7.2 shows a summary of different modules involved in the Image application.

In order to respect the privacy of the clients and prevent potential vulnerabilities in storing private data on third-party machines, the owner organization breaks down the database of all known faces into two main categories: (i) faces that are publicly known, such that the data contain no sensitive or confidential information and can be stored on public cloud space; and (ii) facial data that contain sensitive or confidential information and should never be placed on third-party machines, even if encrypted. In order to make this more interesting, different subcategories are also considered for each main category. Let us assume that the goal is to recognize people entering the country at an airport through image-processing of photos taken by security officers at the airport. Based on this scenario, the two main subcategories for the database of known faces would include (i) known criminals whose faces have been publicly announced, and (ii) normal people/citizens whose faces should not be stored on any third-party machines. Furthermore, faces of known criminals might be divided into international criminals and national criminals. Similarly, faces of “normal” people might be divided into citizens, permanent residents, and visa holders. Figure 7.3 shows how these databases would be stored in different public and private cloud spaces.

In the figure, DB1 stores faces of citizens, DB2 stores faces of permanent residents, DB3 stores faces of visa holders, DB4 stores faces of international criminals, and DB5 stores faces of national criminals. The image-processing application makes it possible to compare a photo taken with a phone to these databases and thereby identify the person in the photo. The main design goal of developing an authorization policy for this application is to keep confidential data away from unauthorized users and provide different levels of restrictions for different types of users, ranging from security officers (who have access to all databases) to normal airport staff (who should only be able to recognize criminals). In the next section, we use this privacy-sensitive application to demonstrate the policies that can be defined using our framework.

7.4.6 The Design of an Authorization System

Since we want to provide fine-grained authorization systems for application components, we have adopted a hierarchical approach whereby organizations can enforce an organization-wide policy, while developers and end users can fine-tune it. An organization is the primary owner of the data and resources and must be able to keep private and public cloud components separate from each other and define an overall policy in terms of resource usage for different users or different applications. Specific applications may also need to further tighten those organization-wide policy rules. End users or programmers must also be able to further restrict resource usage and component distributions for specific applications. As a result, our framework supports two types of policies: hard policies and soft policies.

Hard policies are organization-wide authorization rules defined per user or application by the organization. Users include different developers inside the organization in addition to external clients. On the other hand, soft policies are application-specific authorization rules defined in addition to the organization-wide hard policy. Despite the fact that these two types of policies have complementary roles in increasing system flexibility, a soft policy can only tighten the organization-wide policy and not vice versa. In other words, if the organization-wide hard policy allows a specific user or a specific application to access resources A and B, a soft policy can only further restrict the access to one of the resources A or B; it can never loosen the restrictions by allowing access to a new resource such as C. Separating the restriction policy definition from the application logic in this way allows organizations to define their hard policies without programmers' having to worry about compromising the predefined organization-wide policy.

Each application instance initially authenticates itself with a Policy Manager Machine (PMM) and receives a locked unchangeable hard policy that contains the organization-wide authorization rules defined by the organization. Each organization can define its authorization policy as one policy for all users, one policy for all applications, one policy per application, one policy per user, or one policy per application instance. In the end, each application instance can acquire one locked hard policy from the policy manager machine. In addition, each application instance can have one soft policy. Developers can define the initial soft policy per application or per application instance. They can also allow end users to change all or part of this soft policy through the application. To implement these rules, we follow the XACML usage model [44] and assume a Policy Enforcement Point (PEP) as part of our elasticity manager. The PEP is responsible for protecting authorization rules by sending a request that contains a description of the attempted action to a Policy Decision Point (PDP) for evaluation against available hard and soft policies. The PDP evaluates the requested action and returns an authorization decision for the PEP to enforce.

Our authorization framework needs to be able to apply the restriction rules at the granularity of actors. It still allows those rules to be defined at higher level entities, such as groups or sets of actors, but it recursively propagates all those specified authorizations (permissions or denials) to all actors contained within a set at runtime. This makes it easy to specify authorizations that hold for a larger set of actors (on the whole system, if “all” is used) and have them propagated to all the actors within that set until stopped by an explicit conflicting restriction rule [45]. Actor frameworks allow multiple actors to be placed together in a container, called the actor system or theater, to share common attributes. We respect this structuring in our language and allow authorization rules to be defined on actors, actor systems, sets of actors (each called a Group), a set of actor systems (called a Location), or a subset of multiple actors and actor systems (called a Selection).

While access control models restrict access to different components or resources, our mobile hybrid cloud framework provides more than access restriction. The actor programming paradigm allows an actor to send and receive messages, create new actors, or migrate to new locations. As a result, our authorization grammar must allow for definition of rules regulating all those actions. Note that these actions are usually bidirectional, meaning that if Actor 1 is allowed to send to Actor 2, then Actor 2 must also be allowed to receive from Actor 1 in order for the policy to be consistent. If either of those two actions is not explicitly allowed as part of the policy, the framework automatically rejects both actions, as they will always happen together.

7.4.7 Mobile Hybrid Cloud Authorization Language

Authorization decisions are made based on the attributes of the requester, the resource, and the requested action, using policy-defined rules. As a result, defining an authorization policy means defining the authorization entities and their required attributes in addition to defining rules and desired rule orderings.

In the cloud application model in which actors are the smallest entities in an application, actors are the finest granularity on which we can define access restriction. In order to provide location transparency, multiple actors running on one runtime instance on one machine are placed inside a container, called an actor system or theater as in SALSA [46]. Our language supports definition of both actors and actor systems. Every actor is defined by its related reference and a logical path to reach the actor in the runtime environment, in addition to its containing actor system. The authorization framework uses these attributes to bind the actors defined in the policy to their real-world application components.

In order for our language to be able to account for the existence and activities of to-be-developed application-specific components (while enabling the writing of organization-wide policies), anonymous types of entities are defined as part of the proposed language grammar. A rule called anonymous-actor allows restriction of the creation and number of unknown actors in a reference-actor system. Similarly, a rule called anonymous-actor system allows control of the creation and the number of unknown actor systems.

The following shows how the above supported entities can be used to define the components of the face recognition example from Section 7.4.5.

{Name: ActorSysUser, Static (URL:98.123.123.456, Port:1979)}

The above clause defines an actor system called ActorSysUser that is statically bound to the given IP address and port number.

{Name: UserImageLoader, Static(Reference:actor.tcp://[email protected]/Image-Loader, ActorSystem:ActorSysUser)}

The above clause defines an actor called UserImageLoader for the component that loads an image from disk, with the reference providing the logical path to reach the element in the runtime environment. The clause also provides the actor system to which the actor belongs. We can have similar definitions for Face-Detector, Feature-Extractor, and Face-Recognizer.

{Name:AnonymousUser, Ref-ActorSystem:ActorSysUser, Existence:FORBIDDEN}

The above clause defines an anonymous actor within the ActorSysUser actor system, to prevent the creation of additional actors within the actor system. The grammar also supports limiting of the maximum number of anonymous actors that can be created within an actor system.

{Name:Other-ActorSys-User, URL:98.123.123.456, Creation:FORBIDDEN}

Finally, the above clause defines an anonymous actor system to restrict the creation of unknown actor systems at the given URL. Note that anonymous URLs for dynamic binding can also be created to support arbitrary architecture of to-be-developed applications.

{Name:FaceActors,Actors:UserFaceDetector,UserFeatureExtractor,UserFaceRecognizer}

{Name: PrivateActorSystems, ActorSystems:ActorSysPrivate1, ActorSysPrivate2}

{Name: FaceActors, Subject (ActorSystems:ActorSysUser), Object(Actors:UserImageLoader), Operator (REMOVE)}

{Name: ActorSystemIsolation-Rule, Subject(ActorSystems:ActorSysUser), Object(ALL), Actions:ALL, Permission:DISALLOWED}

{Name: Actor-Gateway-Rule, Subject(Actors:UserFaceRecognizer), Object(Actors:ActorPublicGate, ActorPrivateGate), Actions:SEND-TO, RECEIVE-FROM, Permission:ALLOWED}

{Name: UserFaceRecognizer-Rule-Order, Subject(Rules: Actor-Gateway-Rule), Object(Rules: ActorSystemIsolation-Rule), Order: PRECEDENCE}

7.4.8 Performance- and Energy-Usage-Based Code Offloading

In the previous section, we saw the need to support code mobility to enforce policies for the privacy guarantees of an application. The target offloading goals can affect the component distribution plan in a hybrid cloud environment with multiple public and private cloud spaces in addition to fully parallel application execution. So we next examine application performance and energy usage on mobile devices as target offloading goals and create an offloading decision-making model for the same.

As an alternative to the expensive option of full-VM migration (see Section 7.3.1), we propose a code-offloading mechanism that is more selective, intelligently identifying and migrating only those parts of the mobile application that would most benefit from migration to a more powerful computing platform while keeping communication overhead low. This approach masks the details of the migration process from both users and developers, while providing for a natural partitioning of an actor-based mobile application. The key challenge is that of identifying and selecting the groups of application components (actors) that would be most beneficial to offload based on the current state of the mobile platform and the application, the application behavior, and the primary purpose of the offloading (energy or performance optimization).

7.4.8.1 Offloading for Sequential Execution on a Single Server

There can be wide variation in the goals for the offloading, depending on the usage scenario; they may range from maximizing the application performance, for example, in video games and vision-based applications, to minimizing the energy consumption on the mobile device, for example, in background processes. Regardless of the offloading purpose, however, the implementation costs are highly dependent on the remote platform on which the offloaded components are to be executed. Key factors include both the performance of the target platform and the communication properties, such as latency and bandwidth.

The goals for maximizing application performance [1] and minimizing energy use on mobile devices are shown in Equations 7.1 and 7.2, respectively. First, let

1. execution time on mobile device
2. duration of data transfer
3. execution time on remote server

then

(7.1)

Second, let

1. energy cost on mobile device
2. energy cost of data transfer
3. idle energy cost while waiting for result

then

(7.2)

These equations lead naturally to the pause-offload-resume model [9], which results in sequential execution. For this reason, using CloneCloud [10] or ThinkAir [11] ostensibly to enable opportunistic parallelism results in sequential execution in practice. Furthermore, such models only have to consider a single remote location for offloading. We consider parallelism wherein multiple remote servers work concurrently with mobile devices.

Expanding Equations 7.1 and 7.2, we observed that they are structurally similar and usually result in close decisions, if power consumption on mobile devices for computation, transfer of data to remote servers, and waiting in idle mode are all proportional. That is the case for sequential execution and is the result of assuming that the mobile screen will be on, even in the idle state [9–11].

7.4.8.3 Maximizing Performance

Fully parallel execution refers to both parallel execution on multiple remote locations and simultaneous local and remote execution. As a result, the total application execution time is the maximum time required for any of the mobile or remote spaces to finish executing program code for all of its assigned components. Since local communication between components located on the same machine is relatively fast, we can ignore local communication and only consider communications between components placed at different locations. The offloading goal can be summarized as maximizing application performance () or minimizing application execution time () using:

(7.3)

A mobile application consists of components, and each component is located at at time t. Having M different cloud spaces results in where 0 represents the local mobile device and corresponds to different cloud spaces. Assuming that we know the application component distribution between the local mobile device and the hybrid cloud spaces at time , our goal is to find the component distribution for the next time interval such that application performance is maximized.

Thus, different parts of Equation 7.3 can be extended so that the first term captures the maximum (across different cloud spaces) execution time for all components on each of those locations . This maximum can be obtained using monitoring and previous profiling for the execution time of each component in its location at time .

Similarly, the second term of Equation 7.3 captures the maximum required time for one of the locations to send out all its communications. This maximum can be obtained using the profiled amount of communication between the members of each pair of components during the elasticity manager's running time interval and the location of components across locations in time .

However, not all components of an application are offloadable, so a few constraints must be added to the above optimization problem. As we are considering a hybrid cloud that consists of multiple private and public cloud spaces, application developers or users can specify additional constraints in terms of how different components can be offloaded to different locations. These additional constraints can also address privacy issues in terms of not offloading sensitive or confidential components to public cloud spaces.

7.4.8.4 Minimizing Energy Consumption

Let us now examine the differences in terms of minimizing mobile device energy consumption instead of performance. This goal can be defined as below. Let

1. application mobile energy consumption
2. energy saved on mobile device
3. total mobile energy saving by remote component execution
4. energy loss because local communication became remote communication
5. energy saved because remote communication became local communication

then

(7.4)

in Equation 7.4 can be further elaborated into

(7.5)

where Energy(i) is the profiled energy consumption of component as it runs locally on the mobile device during the time interval Δ, and returns 1 if two given locations are identical and 0 otherwise. Note that the first term of the equation considers only components that are currently on the device, and the second term adds the condition that those elements must now be at a remote location. Thus, energy savings are counted only for components that have been migrated from the local device to a remote location. It should be noted again that our goal is to minimize energy consumption at the mobile device and not the total energy. The migration of components between remote locations does not help with that goal and therefore is not considered in the equation.

and in Equation 7.4 are obtained using the profiled amount of communication between each pair of components and the profiled mobile power during communication with remote servers.

To maximize performance, we can add constraints, for example, that offloading of components to remote locations to save local energy must not affect the performance of the application. In other words, we can specify that energy savings are allowed only as long as a certain level of service performance is maintained. An important observation we made in our fully parallel application model is that the results of our offloading goals are very different for application performance improvement and for energy savings on mobile devices. This is unlike the sequential case in which the models lead to similar configuration results. Therefore, we use the constraints to add restrictions on how much improvement in support of one goal is allowed to negatively affect the other.

7.5.1 Expressing Coordination

A number of methods have been developed to express coordination between actors separately from the functional behavior of an actor. Observe that coordination policies affect the behavior of participant actors locally. Thus, multiple policies can be specified separately and enforced. However, such policies could interfere with each other. Moreover, policies must be enforced by trusted actors and implemented through mediation of the messages between actors, so formal methods are required to support reasoning about coordination.

7.5.1.1 Synchronizers

The oldest framework for declarative expression of coordination behavior is synchronizers [3]. A synchronizer is a collection of constraints that enforce an ordering between messages processed by different actors that belong to some interacting group. Such groups may overlap, as an actor may participate in different activities with different groups of actors. When a message does not meet the constraints required for it to be processable, message dispatch is delayed until the state of the system changes (because other messages are processed) and the constraints governing the blocked message are satisfied. Synchronizers are implemented through creation of the appropriate meta-actors, and this process can be automated.

Two types of constraints that provide generality are disabling constraints and atomicity constraints. Disabling constraints prevent an actor from handling messages that match a given pattern. For example, if all types of messages except an initialization message are disabled, the actor must first receive an initialize message before it processes other messages. Atomicity constraints implement atomic processing of messages by different actors, as in the example discussed earlier.

Programmers declare synchronizers as templates. Similar to classes or actor behaviors, these templates are dynamically instantiated at runtime with concrete values filled in for the parameters. Consequently, synchronizers can have local state that changes with the observed messages. They may also overlap, that is, multiple synchronizers can constrain the same actor. Figure 7.4 shows the effects of a possible synchronizer.

Consider a sliding window protocol. The protocol prevents a sender from sending more than a specified number of messages at a time. More messages can be sent only after some of the messages sent have been processed. The protocol can prevent denial of service attacks. It is straightforward to express such a protocol using a synchronizer.

In the code below (Figure 7.5), no more than a given number of messages – as determined by the parameter size (representing the size of a “window”) – from a specified sender to a specified receiver may be pending at any one time. Each time one message within the window is processed, the number of acknowledged messages is updated, permitting another message to be sent.

7.5.1.2 Security Issues in Synchronizers

As systems are continually evolving, synchronizers may be dynamically added or removed. As systems scale, the chance that some actor will be compromised or be malicious increases. A scalable coordination model must be able to cope with uncooperative actors and gracefully degrade in the presence of failures. It must also guard its reconfiguration mechanisms against abuse. Installation of a synchronizer can lead an actor to wait for a message that never arrives, leading to failure. For example, suppose that an actor A can handle messages of types message1, message2, and so on, up to messageN. A malicious actor M can prevent A from receiving any further messages by installing a synchronizer, as shown in Figure 7.6, that disables all message handlers in A.

To address the problem, we need synchronization constraints to be scoped. A suitable scoping mechanism was introduced in Ref. [47], and the discussion in the rest of this section follows that work. The idea is to restrict the ability of a synchronization constraint to be able to limit messages only if they are coming from actors within a scope. This scoping rule means that messages from outside the scope of a synchronizer can still be received by a target actor, thus preventing the target actor from being permanently locked by a malicious or buggy actor that fails to follow the agreed-upon interaction protocol.

Synchronization constraints are complementary to object capabilities [48]. Object-capability security is a natural model of security in actor systems. An actor's address works like a capability: One cannot send a message to an actor without knowing its address, and these addresses can be guessed. If the address of an actor a₀ is provided to an actor a₁, the recipient a₁ is provided with the capability to send a₀ a message. This provides a level of security: By carefully restricting the distribution of addresses, one can prevent malicious or buggy actors from affecting the behavior of actors with which they should not be able to interact.

In contrast, synchronization capabilities determine the scope of synchronization constraints: They provide actors with the capability to join an interaction and be restrained to follow the synchronizer's constraints. Figure 7.7 shows the scoping effects of synchronization capabilities.

As with object capabilities, we assume that synchronization capabilities are unique across the system and cannot be guessed. The distribution of synchronization is similar to that of actor addresses: Actors obtain synchronization capabilities through initialization and introduction by an actor that has the capability. However, synchronization capabilities are “inherited” from the creator: When a new actor is created, it is subject to the same synchronization rules as its creator. This prevents an actor from escaping its synchronization constraints by simply creating a new actor that circumvents the constraints on its messages.

Synchronization capabilities can prevent a buggy or malicious actor from intentionally creating a deadlock through installation of a synchronizer. In the DisablingAttack synchronizer from Figure 7.6, scoping the synchronization constraint results in behavior similar to that of the lower right actor in Figure 7.7: If the synchronizers do not have a synchronization capability that affects an actor's messages, these messages will pass through. Moreover, accidental interference of constraints also becomes less likely [47].

When a message is dispatched, all synchronizers that belong to matching update patterns receive information about the event. For example, consider cooperating resource administrators that share a limited number of resources. When a resource is released by one administrator, it enables another administrator to service requests that require the resource. Synchronizers that are not constraining the sender of a message (and thus that type of message) may still need to receive information about the dispatch of a message by an actor whose other messages are being constrained. It needs that information in order to have a correct view of the state of the target actor, since it needs the information to be able to receive a specific type of message (that may need to be constrained). Although a visible message dispatch provides a consistent view of the system, it can enable malicious actors to spy on other actors, as shown in Figure 7.8. This security issue remains an open problem.

7.6.1 Session Types for Actors

Typing coordination constraints in actors pose two challenges: first, asynchronous communication leads to delays that require consideration of arbitrary shuffles; second, parameterized protocols must be considered. For example, assume that two actors are communicating through a sliding window protocol; the actors agree on the length of the window (i.e., the number of messages that may be buffered) and then proceed to a concurrent exchange of messages. Conventional session types are not suitable for typing interactions such as the sliding window protocol. The reason for this limitation is that their respective type languages depend on other formalisms for type checking (such as typed λ-calculus [49] or System T [50]), and these formalisms do not support a concurrency construct.

To overcome such limitations, we propose a programming language, Lang-A, along with a session type system, System-A, that allows type parameters in novel constructs that capture the inherent asynchrony of actor programs. In particular, the system includes novel parameterized typing constructs for expressing asynchrony, concurrency, sequence, choice, and atomicity in protocols. An inference algorithm derives local System-A types from Lang-A programs, and a type system checks those types against conformance criteria.

7.6.1.1 Example: Sliding Window Protocol

Recall the sliding window protocol. Assume that an actor a sends messages of type m to an actor b, which acknowledges every received message with an ack message. The protocol determines that at most n messages can be unacknowledged at any given time, so that a ceases sending until it receives another ack message. In this example, the window size n is a parameter, which means that we need a way to express the fact that n sending and acknowledging events can be in transit at any given instant in time. The global type of the protocol is as follows:

Here means that a sends a message of type m to b. The operator ; is used for sequencing interactions. Operator ∥ is used for the concurrent composition of its left and right arguments, while the Kleene star has the usual semantics of an unbounded – yet finite – number of repetitions.

The above type can be expressed using the notation of Castagna et al. [27,51], albeit with a fixed window size n. In System-A, on the other hand, we can parameterize the type in n and statically verify that participants follow the protocol without knowing its runtime value. Using to denote the concurrent composition of n processes, we obtain the following type:

(7.6)

7.6.2 Global Types

A global type describes a protocol to which the whole system must adhere.

For example, the sliding window protocol specification is a global type, since it describes the behavior of all participants. Table 7.1 presents the grammar that generates the syntactic category of global types. The elements of , which are instances of global types, will be denoted by variations of the variable G. Intuitively, the rules capture the following concepts:

1. (G-Interaction) denotes the sending and receiving of a message. For instance, means that participant a sends a message of type m to participant b.
2. (G-Seq) is used for the sequential composition of events.
3. (G-Choice) denotes exclusive choice between the arguments. For G_1,2 ∈ , G₁ ⊕ G₂ means that only one of G₁, G₂ will be executed.
4. (G-Paral) means that the arguments run concurrently. Interleavings are allowed, as long as the order established by the ; operator is respected. For example, means that all interleavings ABC, ACB, CAB are possible, where and . Note that B is not allowed to precede A because of how operator ; orders them. (Hence, BAC, BCA, and CBA are not valid interleavings in this example.)
5. (G-Shuffle) means that both arguments are executed atomically, in an unspecified order. Formally, G₁ ⊗ G₂ = (G₁; G₂) ⊕ (G₂; G₁) with the = relation denoting semantic equivalence, as detailed in the original work of Charalambides et al. [4].
6. (G-KleeneStar) has the usual semantics of zero or more repetitions of the argument. We assume a finite number of repetitions.

We use a and b to denote possibly indexed actor names; m to denote possibly indexed message types; variants of n for type parameters; and i for index names. For parsing purposes, we assume operators associate with the right, and that operator precedence <p is ⊗ <p || <p ⊕ <p;.

The n-ary versions of the operators express behaviors for which the values of n, n₁, and n₂ are unknown at compile time. Intuitively, the rules (G-Seq-N), (G-Choice-N), (G-Paral-N), and (G-Shuffle-N) apply the respective binary operator n₂ − n₁ times, generating a global type for each of the n₂ − n₁ + 1 values of i. (G-Exp) denotes the n-fold, sequential repetition of the argument. Note that for known parameter values, these expansions can take place during program compilation.

For parsing purposes, operators associate with the right. In terms of semantics, however, all of the operators are commutative, with the exception of sequencing. Furthermore, all operators are associative, with the exception of shuffling. In particular,

because the meaning of is that all arguments G_i are executed atomically, but in an unspecified order. Instead, the right-hand side above prevents, for example, G₃ from occurring between G₁ and G₂.

The distinction between the Kleene star and exponentiation is fundamental. The use of Gⁿ means that the protocol conformance checker will have to prove that the system is correct for any fixed value of the parameter n. G*, on the other hand, refers to an unbounded number of repetitions of G. There is no parameter fixing this number, and it may be different from instance to instance of the Kleene star and/or among executions of the same program with the same runtime values for its parameters; the Kleene star entails a choice as to when to exit the loop.

We define an event to be a single interaction and a trace to be any finite sequence e₁e_k of events. Given a global type , the set of possible traces tr(G) that it can produce determines the permissible sequences of messages that participants may exchange. We omit the full semantics of global types in this text, and refer the interested reader to the original work of Charalambides et al. [4].

7.6.3 Programming Language

Global types by themselves provide no implementation of protocols; implementations are given in the language Lang-A, which is used in the example in Figure 7.9. The figure shows an implementation of the sliding window protocol described earlier. The spawn statement launches n parallel instances of its block argument, one for each value of the provided index expression. Sends and receives coming from different spawned operations can be interleaved in any way possible. In this example, both the sender and the receiver spawn n parallel operations, each consisting of a repeating send/receive pair. This allows any interleaving of sends and receives, as long as no more than n sends are left unacknowledged.

In general, a Lang-A program begins with the declaration of the program parameters, akin to type parameters n, n₁, n₂, and so on, from Table 7.1. Then come message structure definitions, and the code for each actor. Both actor and message definitions can include an optional array syntax after their name. In the case of actors, this syntax declares as many actors as does the array parameter.

In the case of message structures, the syntax declares as many message types as does the array parameter. This allows the expression of protocols for which both actor names and message types are parameterized, such as . Lang-A is defined such that there is an almost one-to-one correspondence between the language constructs and the syntax of local types; the precise syntax and semantics are detailed in the work of Charalambides et al. [4].

7.6.4 Local Types and Type Checking

A local type specifies the abstract behavior of a single protocol participant, for example, one of the actors in the program in Figure 7.9. This section discusses System-A local types [4,28], whose syntax is shown in Table 7.2. In the grammar,

1. (L-Send) denotes sending of a message of type m to actor a.
2. (L-Recv) denotes receiving of a message of type m from actor a.
3. (L-Seq), (L-Choice), (L-Shuffle), (L-Exp), (L-KleeneStar) describe the same concepts as for the global types.
4. (L-Paral) is also defined as for global types. As before, the local type (a!t; a!u) || a?v allows three orderings of the events T = a!t, U = a!u, and V = a?v, namely, TUV, TVU, and VTU. As above, the specification a!t; a!u ensures that T happens before U.

As in the syntax of global types, we use a to denote possibly indexed actor names; m for possibly indexed message types; variants of n for type parameters; and i for index names. For parsing purposes, we assume operators associate with the right, and that operator precedence <p is ⊗ <p k <p ⊕ <p;.

Projecting a global type onto each participant in a protocol results in a set of local types, one for each actor. For example, projecting onto a, written , gives the local type b!m. Similarly, . These can then be checked against the types inferred from the Lang-A code.

Some (local) type inference rules are shown in Table 7.3. Rule (Inf-Skip) assigns the type τ to the skip construct and to all value computations, since those do not involve interactions between processes. Rules (Inf-Send) and (Inf-Recv) assign the (L-Send) and (L-Recv) constructs to send and receive actions, respectively. Sequencing is straightforward, but typing the spawn construct is a little more involved: The index i as well as the range c₁c₂ transfers into the inferred type, which includes the parameterized construct ||.

The environments S and Π contain sorts of variables and actor names, respectively. Γ assigns local types to (sequences of) statements R. We omit brace literals from the program syntax when the meaning is clear from the context. We use variants of c for both constants and type parameters. The variables a, b, m, and so on are as in Section 7.6.2.

The type-checking methodology requires the comparison of local types projected from the global type with those inferred from the program code. In order to perform the comparison on a syntactic level, local types are reduced to a normal form, in a semantics-preserving manner. For a detailed discussion of the projection function, the full list of type inference rules, and the semantics of local types and their relation to the semantics of Lang-A programs, we refer the interested reader to the original work of Charalambides et al. [4].

7.6.5 Realization of Global Types

A global type must satisfy certain properties in order to be projectable. Applying the projection function to a projectable global type will result in local types for the participants whose combined behavior is consistent with the global type.

First, to be projectable, the sequential constructs of a global type must retain their sequential semantics after projection. For example, the type does not preserve said semantics after projection, because c has to send m′ after b receives m, and programming this sequence requires interactions not captured in the above type.

In addition, a global type G₁ ⊕ G₂ is projectable if all participants can recognize which branch of the choice operator they need to take during execution. Similar requirements apply to G₁ ⊗ G₂, for which it must be possible for the constituents to be sequenced both ways, and for the participants to distinguish the two possible orderings.

Concurrent composition requires special care to prevent actions in one concurrent branch from affecting choices made on another, while for the Kleene star we need to ensure that the entry and exit conditions to the starred type can be identified by all participants.

If a global type G is projectable according to the criteria sketched above, the projection function generates local types that are functionally consistent with the global type. We use Δ_G to denote the set of local types that result from the projection of G onto each one of the participants. That is, where Π is the set of participating actors. The set of traces tr(Δ_G) producible by Δ_G is the union of the sets of traces producible by the local types in Δ_G. Now, let PR be the set of projectable global types. The key correctness property is then that G ∈ PR ⇒ tr(G) = tr(Δ_G). The proof is by induction on the structure of global types [4].