Computer Science

Bookchapter

http://werner.yellowcouch.org/Papers/chubiqcomp/

Other: Papers, Dissertations, Presentations, Posters, Reports, Course notes, Proposals

Ambient Actors as a Formalism for Ubiquitous and Mobile Computing

Werner Van Belle¹^*⁺ - werner@yellowcouch.org, werner.van.belle@gmail.com
Jessie Dedecker²⁺ - jededecker@vub.ac.be

1- Internet & Communication Technology; Norut IT; Research Park; 9294 Tromsø; Norway
2- Programming Technology Lab (PROG); Department of Computer Science (DINF); Vrije Universiteit Brussel (VUB); Pleinlaan 2; 1050 Brussel; Belgium
* Corresponding author; + Equal Contribution

Abstract: Networks formed by the interconnection of mobile wireless devices are often called mobile ad-hoc networks. Such networks are highly volatile because communication partners can move in and out of range. This leads to unwanted interruptions of communication sessions, which in turn complicates the development of software that relies on a long term distributed state. Standard solutions seem inadequate because all too often they assume an inherent client server role or they assume a bound latency on communication sessions. One cannot make such assumptions in mobile ad-hoc networks. In order to resolve this matter a programming model must support the ability to pick up previous communication sessions; it must remember the devices/resources it has seen in the past; and it must provide a realistic approach towards concurrency, taking into account the limitations of a peer to peer ad-hoc network. This article presents the ambient actor model which extends the operational semantics of the actor model to capture the limitations posed by this novel paradigm

Keywords: ambient pervasive ubiquitous computing asynchronous distributed systems actor systems
Reference: Werner Van Belle, Jessie Dedecker; Ambient Actors as a Formalism for Ubiquitous and Mobile Computing; Handbook for Ubiquitous and Mobile Computing; American Scientific Publishers; October 2006

1 Motivation

Networks formed by the interconnection of mobile wireless devices are often called mobile ad-hoc networks. Such networks are highly volatile because communication partners can move in and out of range. This leads to unwanted interruptions of communication sessions, which in turn complicates the development of software that relies on a long term distributed state. Standard solutions seem inadequate because all too often they assume an inherent client server role or they assume a bound latency on communication sessions. One cannot make such assumptions in mobile ad-hoc networks.

In order to resolve this matter a programming model must support the ability to pick up previous communication sessions; it must remember the devices/resources it has seen in the past; and it must provide a realistic approach towards concurrency, taking into account the limitations of a peer to peer ad-hoc network.

This article presents the ambient actor model which extends the operational semantics of the actor model to capture the limitations posed by this novel paradigm.

Pervasive computing captures the idea that computing technology will gracefully integrate into our everyday life such that the user is no longer aware of the technology [Wei91]. From a hardware point of view much progress has been made the past couple of years. Technology such as WiFi, Bluetooth [Var03] and 802.11 [MSG02] provide already decent hardware abstractions and improvements in chip design already led to the creation of ultra-low power chips that organize themselves automatically into time synchronized ad-hoc networks [Int06,Inc06,Lam77]. Research into such sensory networks concerns itself with the question on how to aggregate information properly. This can be useful to acquire and query sensory information from different locations, such as in vibration monitoring of buildings [Pes01].

Such highly visible and interesting applications provide a radical rework of the software layer [HAAC⁺00] but provide little help for more common 'personal digital assistant' (PDA) applications. As a working example in this article, we consider a PDA, that travels along with its user. As the user moves about, the software on the PDA encounters new environments, each possibly containing new devices to provide useful information and resources (e.g: other PDA's, printers, local computers and so on). We find that this kind of applications tend to rely heavily on abstraction layers that might not be feasible to realize because they assume inherent client-server roles, stable connections and/or availability of specific communication partners.

Based on such scenarios, we determined a number of novel concepts for, and restrictions on, the communication architecture for mobile ad-hoc networked devices.

Local communication: In pervasive computing, the single most outstanding concept is probably 'location'. Whether we work with ad-hoc sensor networks or PDA's, such devices are mobile and in order to allow to software to react and recognize its environment, the communication architecture needs to link every computation to a physical location. Furthermore, unlike most desktop computers today, mobile devices are not necessarily continuously connected to a network such as the Internet. Local direct device-to-device communication might be the only means for devices to communicate with other devices in their immediate proximity.
Connection Volatility: The limited communication range of the wireless technology combined with the fact that users can move out of range can result in broken connections at any point in time. Therefore, communicating devices that perform a meaningful task together cannot assume a stable connection. However, upon re-establishing a broken connection, users typically expect the task to resume and performed, regardless of the quality and availability of connections.
Finding Resources: If a user moves about with his/her mobile device, remote resources become dynamically available or unavailable. This is in contrast with stationary networks in which references to remote resources are obtained based on the explicit knowledge of the availability of the resource. A challenge in mobile ad-hoc networks is how to recognize particular resources and services [GPVM99]. The problem of unreliable availability of communication partners connections can also be present in open distributed systems, such as Internet, but they are less prominent, because the incidence rate of unavailable communication partners is much lower and communication partners are often unavailable for only small amounts of time.
Autonomy: Most distributed applications today are developed using the client-server approach. The server often plays the role of a ``higher authority'' which coordinates interactions between the clients. In mobile networks a connection to such a ``higher authority'' is not always available. Every device should be able to act as an autonomous computing unit. This means that no device should indefinitely postpone its own processing when waiting for information from other devices.

Currently none of the formalisms we studied was able to capture those four basic premises into a coherent formal model. Therefore, we felt the need to take these basic facts and incorporate them into a formalism for ubiquitous computing, which is sometimes also called 'ambient intelligent computing' [DBS⁺01].

2 Related Work & Comparative Analysis

Based on the concepts identified in the previous section, we now analyse the state of the art of programming models for ubiquitous computing systems. The presented formalisms were mainly conceived in the context of peer to peer networks, open distributed systems or mobile multi agent research. Table 1 presents the overview of our findings. For every model we investigated whether the model a) provides the concept of locations, b) whether communication can only occur within the same locations. We were also interested in c) whether the model supports the detection of incoming or outgoing communication candidates and will notify the program layer. d) The 'resource' column describes whether remote resources can be detected using some form of resource descriptor (e.g: pattern-matching on capabilities). Finally, we probed the autonomy of every model by looking at the synchronicity of the model (The reason for this will become clear in section 3.1

**Table 1:** Comparative analysis of a number of different formalisms.
	Only Local	Detection of incoming	Finding of	Asynchronous
Name	Communication	and leaving devices	Resources	Communication
Linda	No	No	No, possible	No
Locality Based Linda	No	No	No, possible	No
Mobile Ambient Calculus	Yes	No	No, possible	No
Distributed Join Calculus	No	Extension	Yes	No
$\Pi$ -calculus	No	Half	No	No
ActorSpaces	No	No	Yes	Yes
Actor systems	No	No	No	Yes
Ambient Actors	Yes	Yes	Yes	Yes

2.1 Tuple Spaces: Linda & Locality Based Linda

Linda [Gel85,CG89] is a coordination language based on Tuple spaces. There are several primitives that make communication explicit in the code. There is a primitive for putting values in the Tuple space (asynchronous) and primitives for getting values from the Tuple space (blocking). Tuple spaces are interesting because they allow communication without the need to specify the communication address of the receiver (which is also known as anonymous communication). If used properly, such a Tuple space might be usable for local communication. Nevertheless, the standard Linda architecture is based on a central server architecture, with one central Tuple space in which to put tuples. This makes it not suitable for ad-hoc wireless network environments.

Locality based Linda [DFP97] is an extension to Linda but with the explicit notion of locations. Primitives in Locality based Linda now work on a specific Tuple space. Anonymous communication becomes impossible, because the location needs to be provided. In our context this would mean that the addresses of communicating devices need to be known, which is impossible to determine in ad-hoc wireless network environments. The model also does not define what happens with communications when the target location is unavailable or unreachable.

Local communication: Standard Tuple-spaces rely on a centralized architecture, which does not provide a concept for the locality of an agent. Extensions exist that take into account locality (e.g: locality based Linda), but in these communication remains global by prefixing every Tuple with a target Tuple space.
Detection of incoming and leaving devices: Tuple spaces do not provide a standardized way to detect incoming or outgoing devices since there is no concept of direct communication between the devices (all communication goes through the global Tuple space).
Finding Resources: Tuple spaces can be used to detect specific resources, based on some form of pattern matching, however, there is no standard provision that dictates how resources are to be found and to what kind of messages a resource/device needs to reply. On the other hand, standard Tuple space provide for anonymous communication which is already an important concept to realize automated resource finding. Therefore, we marked 'finding resources' as 'No, but possible'.
Autonomy: Tuple spaces provide asynchronous events, however these are often wrapped in blocking primitives which makes the models not suitable for networks with unbound latencies.

2.2 Mobile Ambient Calculus

The mobile ambient calculus [CG00] expresses an abstraction between mobile computing and mobile computation in administrative domains. Mobile computation is the physical movement of devices between administrative domains, while mobile computing is the movement of a logical process (also called migration). The mobile ambient calculus describes movement of processes between different locations and communication between Ambients that are located in an ambient. Mobile Ambients allow the posting of anonymous messages (without explicitly targeting the receiver). This is a concept that can be used for detection of resources since a mobile ambient can post its own information. Notwithstanding, the model itself does not provide a standardisation how such a mechanism needs to work.

Locations and local communication: The mobile ambient calculus provides the concept of 'ambient' to represent locations and location awareness. It also assumes that only local communication between Ambients in the same environment is possible.
Detection of incoming and outgoing Ambients and notification to the program is not provided by the mobile ambient calculus.
Finding resources: The mobile ambient calculus provides anonymous communication, which might be used to set up some form of resource recognition. Notwithstanding, there is no standard provided.
Autonomy: The mobile ambient calculus relies on distributed computation, in which parts of the computation can be redirected elsewhere. This means that any device can receive new incoming Ambients. We perceive this as problematic because device might leave indefinitely and thus delete part of the computational trace. Furthermore, typical communications are written in a blocking manner.

2.3 Distributed Join Calculus

The distributed join calculus [FGL⁺96] gives semantics for logical movement (migration), failures and failure detection of agents. The distributed join calculus comes with a number of possible extension, among which locality as defined in the mobile ambient calculus and failure detection.

Local communication is not available in the standard model, instead it assumes a fully interconnected network.
Connection Volatility: Detection of incoming and outgoing devices can be realized as an extension to the system.
Finding Resources seem standard in the Distributed Join Calculus.
Autonomy: Blocking primitives are standard in this formalism and thus is not reconcilable with the autonomy of devices.

2.4 The $\Pi$ -calculus

The $\Pi$ calculus as defined by Milner et al. [MPW92,Mil99] describes a calculus that exchanges channels between processes in order to achieve both mobility and communication. It is an attractive model because it could allow the detection of failures (broken channels), but it does not provide any means to actually set up a connection by finding appropriate partners in the neighbourhood because there is no concept of locality introduced.

Local communication: The $\Pi$ -calculus has no concept of locality and thus there is also no assumption that only local communication is possible.
Connection Volatility: processes in this model communicate through channels. Those channels, comparable to TCP connections, might allow for the detection of leaving devices. There is no standard support to notify the presence of new processes.
Finding Resources: The $\Pi$ -calculus does not provide a means to recognize and anonymously detect new resources.
Autonomy: Similar to the observations on the mobile ambient calculus: the migration of channels and processes does not respect the autonomy of the receiving device and the standard use of blocking primitives does not work well in networks with unbound latencies.

2.5 Actors

The actor model was developed by Hewitt [Hew77] in the late seventies and later further developed by Agha [Agh86,AH88]. It was only in the late nineties that Agha et. al published a description of the operational semantics [AMST97] of an actor system. Since the ambient actor model we will present, bases itself on the standard actor model, we will elaborate on some of its details. This will provide the reader with a better understanding of what lies at the heart of actors.

The Actor programming language [Agh90] was designed for use in open distributed network environments (i.e. the Internet). A distributed application is modelled with actors that are distributed throughout the network. Communication between actors occurs solely with asynchronous message passing. Figure 1 shows the conceptual representation of an actor. Each actor has a behavior associated with it, which defines how it handles incoming messages. Incoming messages are handled by the actor its own thread of control. An actor is fully encapsulated and can only be addressed by other actors through its mailbox. In other words if an actor sends a message to another actor or itself it always places a message in this mailbox. A message is transparently and non-deterministically selected from the mailbox and processed according to the actor its behavior. Fairness is assumed such that all messages are eventually processed.

**Figure 1:** Each box represents an actor. All actors communicate with one another by means of messages. Messages are transmitted between implicit mailboxes. An internal thread, individual to each actor, handles incoming messages. The internal state of an actor is inaccessible to the outside world.

The semantics of the actor programming language [AMST97] are defined as an extension of the operational semantics of a simple functional language. The behavior of an actor is modelled using functions, each taking one parameter, which is a message. Based on this parameter a number of expressions can be evaluated. In the operational semantics of the actor language the functional language is conceptualized by the untyped lambda calculus [Mog89,SJ75] which is further extended with three actor primitives to support programming in a distributed environment:

New actors can be created using the letactor primitive. The letactor primitive takes one argument, a function that is the initial behavior of that actor and returns the mail address of an actor.
Messages are sent to known actors using the send primitive. The send primitive takes two arguments, the recipient's actor address and a message. Such a message can contain the address of other actors.
An actor can modify its own behavior using the become primitive. The become primitive takes one argument, a function that is the new behavior of the actor. There is no shared data between actors.

These primitives are illustrated by the example shown below, which is an implementation of an ML reference cell expressed in the actor language defined by the operational semantics. This cell example also illustrates how the become operator can be used to model state.

$B\sb{cell}$ = rec( $\lambda$ b. $\lambda$ c. $\lambda$ m.
    if(get?(m),
       seq(become(b(c)), send(cust(m), c)),
       if(set?(m),
          become(b(contents(m))),
          become(b(c)))))

In the $\lambda$ -calculus functions are first-class entities and do not necessarily have a name. Such anonymous functions are of the form $\lambda a.exp$ where a is an argument and exp is the body of the function. The last expression that is evaluated determines the return-value of the function. In the $\lambda$ -calculus functions take only one argument at a time. Multiple arguments are simulated by currying. This is the process where one function returns another function that takes one argument and this process is repeated for all arguments.

The function $B_{cell}$ describes the behavior of a cell actor. The function call to rec calculates the fixed-point of a function [MT91] and calls the $\lambda$ -expression with that fixed-point as its argument. Hence, $B_{cell}$ refers to a function which takes two arguments c and m as its arguments and where b has been bound to the fixed point in the lexical environment of that function. The argument c refers to the contents of the cell and the variable m refers to the message that an actor receives.

The cell-behavior responds to two kinds of messages, get- and set-messages. The get-messages are responded to in two steps: first, the become operation is used to define the replacement behavior of the actor. The replacement behavior is defined with a recursive call through the fixed-point and the contents of the cell remains unchanged. Hence, the replacement behavior of the actor will refer to a function that takes one argument m that has b bound to the fix-point and c bound to the original contents of the cell. Next, the contents of the cell is sent to the customer of the message. The set-messages are responded to by changing the function to a new one with the variable c bound to the contents found in the message m.

In the code that handles the get-message, we find that a become is placed before a send instruction. This order of statement influences the degree of concurrency. Once the become operation has been performed the actor can process its next message while the expressions that follow the become are executed concurrently. The become operation dynamically creates a new anonymous (An anonymous actor is an actor whose address is not known by any other actor in the system). actor which executes the following expressions, in this case the send, while the current actor processes its next message in the context of its new behavior. Accordingly the actor model supports intra-object concurrency. What is more, this intra-object concurrency does not lead to race conditions on the internal state of an actor. The main reason for this is that the state change (achieved by installing another function using the become operation) of an actor occurs in a single operation, because naturally the functional language does not include assignments. Hence, only a become can change the state of an actor.

The function which describes the behaviour of the cell can now be used to initialize the actor:

$letactor(a := B\sb{cell}(0))\sb{e}$ where

seq(send(a, mkset(3)), send(a, mkset(4)), send(a, mkget(a)))

The letactor primitive binds a new cell actor to the variable a and the expression e is evaluated in this context. The set-messages are created using mkset and similarly get-messages are created using mkget. The actor model does not define the order in which messages are consumed and accordingly, the response to the get-message will depending on the order of the messages be 0, 3 or 4.

The actor language relies on an actor system to support parallelism and communication between actors. An actor system hosts multiple actors. These actors may concurrently process messages from one another, irrespective of their individual states. Conceptually, an actor system can be modelled as a message set and the behavior of the actors running on the system. This message set contains two types of messages: 1) messages received, but not yet processed and 2) messages sent, but not yet transmitted. Both types are discussed below:

A message, whose target address is that of an actor running in the actor system, is taken from the message set and passed as an argument to the function that is assigned to the target actor address. When the message set is empty the system waits for a new message to arrive. As explained above, an actor can handle the next message from the moment it has performed the become operation.
When a message is sent then the message is put in the message set. When the target actor address of the message is that of an actor running on another actor system then the message is transparently transferred to the message set of that actor system. The operational semantics of the actor language do not define any order in which the messages from the message set are processed, but it assumes fairness so that no starvation can occur.

We now discuss the applicability of actor systems in light of mobile ad-hoc networks.

Local Communication: The actor model was designed for open distributed networks, where communication partners are sometimes unavailable for a short period of time. The model guarantees delivery through the use of message sets: messages sent to actors running on an unavailable actor system are kept in the message set until the actor system becomes available again for communication. Each actor system has its own message set that contains the messages sent, but not yet transmitted to another actor system and the messages received, but not yet processed. An actor system is therefore self-sufficient and does not rely on a general server infrastructure from the environment for its communication. The abstraction of an actor system however does not fit well with the concept of a location since every single device will need to run their own actor system. Actor systems rely on a virtual full interconnected network, without taking into consideration the mobility of devices nor the restriction that only local communication might be possible.
Connection Volatility: A message set enables transparent asynchronous communication in intermittently connected environments, because a message is transparently and automatically transferred from the message set of the sender to the message set of the receiver whenever communication is possible. Hence, the connection between two actor systems is automatically restored after it was broken. This is important because it permits transparent communication in networks where failures are common, whereas many other asynchronous protocols put the burden of expressing delivery guarantees on the developer.
Autonomy: The actor model explicitly states that no expressions containing closures can be communicated. Agha et al. [AMST97] argue that this is not a serious limitation, because the actor address can be communicated instead and by sending messages to this actor address one can indirectly access the lambda-abstraction. We agree with this view and point out that, in order to remain autonomous, an actor cannot assume that incoming code will behave properly, and thus must treat transmitted data differently from other code. Furthermore, in the actor model, communication amongst actors can only occur by means of the send primitive. Compared to other distributed frameworks, no implicit communication is allowed through shared data. The send operation is also non-blocking and thus preserves the autonomy of a mobile device.
Finding Resources: Finding and detecting new resources with the standard actor model seems complicated. In the actor model all resources that can be shared are modeled as actors and actors are referred to by actor addresses. Actors can only communicate with one another if they have an actor mail address. Miller et al. [Mil04] noted that in capability secure languages, such as the actor model, actors can only make acquaintance with one another in four modes: connectivity by introduction (a message containing an actor address sent to another actor); connectivity by parenthood (when an actor creates another actor using letactor, then the creating actor has the address of the created actor); connectivity by endowment (an actor is initialized with the address of another actor); connectivity through system bootstrapping. This means that he actor model does not provide a means for an actor to independently get a reference to a remote actor in its direct environment. In other words, if two devices move in the communication range of one another then there is no rule that permits one actor running on a device to get a reference to another actor running elsewhere, unless they both have a reference to a third party acting as a middleman. Such a middleman could be a naming server or name registry which is used in middleware approaches, such as Java RMI [CFKL91] and CORBA [EFF⁺97,SAKAT⁺96]. However, such a middleman would imply that infrastructure always needs to be present in the environment. This would not only conflict with the autonomy of mobile devices as explained in section 1 but the actor address of the software running on that infrastructure would need to be bootstrapped in all mobile devices. In other words: the standard actor model is unaware of the appearance and disappearance of other actors.

2.6 ActorSpaces

An extension of the actor model, named ActorSpaces, was proposed by Agha and Callsen [AC93] and defines how actors can be resolved in a distributed namespace. Distributed naming is a useful abstraction to address actors based on a specification rather than an explicit reference. The Actor-Space model extends the actor model with three new concepts:

Attributes: In the ActorSpace model, actors can be addressed by their actor address or by attributes. Attributes are patterns which provide an abstract specification of an actor. In contrast to an actor address, which is associated with exactly one actor, patterns can denote a group of actors; namely all actors that fulfill the abstract specification determined by the attributes.
ActorSpaces: An ActorSpace is a computationally passive entity that determines the scope in which the pattern matching of attributes occurs.
Capabilities: The security model is based on capabilities [Lev84], which are unforgeable keys. Those keys can be created dynamically, compared and communicated over the network by actors. The correct capability is needed to change properties with respect to the distributed naming of an actor or ActorSpace.

Although the ActorSpace model introduces an interesting model to deal with the distributed naming problems of the actor model, there are a number of limitations that make the concepts impossible to use in the context of ad-hoc distributed systems. The problems originate from the fact that ad-hoc distributed systems typically involve network partitions (only small local communicating groups of devices). For example, suppose a number of actors are contained in an ActorSpace but some of these actors run on mobile devices that are currently not in the communication range. Hence, the ActorSpace is partitioned and it is undefined what happens when messages are sent to the actors in that ActorSpace. Also, it is unclear on which device the data structure that holds the configuration of the ActorSpace should be placed. When the node that maintains that data structure is not in the communication range at the moment a send or broadcast operation is performed, then the semantics is undefined. Another point where semantics of the operations of the ActorSpace model is not clear is when managers change the configuration of an ActorSpace in the face of such a network partition. Note that replication of the ActorSpaces data structure is not feasible, because an ActorSpace can be manipulated at runtime and keeping the replicas up-to-date and provide consistent access does not scale and leads to inconsistencies.

Local communication: the ActorSpace model offers the idea of locations since it provides a range in which pattern searches occur. Communication is global and a full interconnect is assumed after the actor name has been resolved.
Connection Volatility: incoming and outgoing devices are not detected and thus not notified towards the program.
Finding Resources: The ActorSpace model provides an interesting mechanism to find and recognize resources within the local search environment.
Autonomy: actors communicate asynchronously, resulting in non-blocking primitives.

3 The Ambient Actor Model

We find that none of the presented formalisms integrate the crucial concepts laid out earlier: a concept of locations; the restriction that only local communication might be possible; awareness of the local environment including notification towards the application when it changes; and a standardized mechanism to find anonymous resources and communication primitives that do not jeopardize the autonomy of a single actor.

In this section we introduce the ambient actor model, an extension of the operational semantics and the syntax of the standard actor model such that the few limitations of the actor model are resolved. We will refrain from giving all the definitions of the standard actor model, which can be found in [AMST97]. We will however repeat definitions that we adapted to extend the operational semantics of the actor model or when they are essential to understanding the extensions.

The main addition to the actor model is the introduction of explicit mailboxes for each actor [DV04]. A number of mailboxes are used within the model to guarantee communication between local and remote actors. In a sense these are necessary to support the meta communication protocol between actors. The mailboxes are the standard inbox, which keeps track of incoming messages, the standard outbox, which keeps track of messages that should be delivered, the sent- and the rcvbox which keep track of, respectively, which messages have been sent and which messages have been processed by an actor. In this section we show that the introduction of these four first-class mailboxes addresses the reïfication of the communication traces, which was one of the missing criteria we identified in the original actor model. We will show that through the manipulation of these mailboxes actors are able to adapt their delivery strategy based on the needs of the application. What is more, actors can use the mailboxes to determine their communication state and as such implement customized schemes based on this state.

Aside from these mailboxes four other mailboxes are introduced to reïfy the environmental context of actors. Actors are usually interested the availability, appearance and disappearance of specific resources from the environment. For this reason, two mailboxes provided and required are added. These mailboxes contain the names of services that are provided to and required by an actor, respectively. These names of services determine what part of the environment is reïfied. The environment is reïfied through the introduction of the joined and disjoined mailboxes. These two mailboxes are transparently updated by the actor system and contain the actor addresses of resources that have appeared and disappeared. As such they reveal the environmental context to the actors.

3.1 Design

We briefly touch upon 4 design decision we made for the ambient actor model [BFDV01,BUOA].

Isolated data-model: Since programs running on different devices can be written in different programming languages we need a formal model that provides a well defined and language independent communication protocol. Such a communication protocol must allows actors to remain in full control of their execution state when receiving messages [GMPS97]. This means that one should not allow messages to be executed automatically or treated such that arbitrary code execution becomes possible. This effectively means that we are especially reluctant to include well know and widely adored features such as transmission of closures (allows for arbitrary code execution) and direct remote addressing (remote references to local objects). We believe that isolated data-models such as XML [ES,BBCV99] or KQML [FFMM94] or other form of graph or tree serialization are the proper way forward.
Non-blocking communication: Writing applications for volatile networks is difficult by means of synchronous communication (such as RPC [BN83] and RMI [WRW96]). With synchronous communication there is a condition that the communication partner on the other end must be available. This condition does not hold anymore in a wireless network environment as communication partners are often not available and can become unavailable for communication at any point in time. Hence, existing synchronous communication models (such as the ones mentioned above) are not suitable for pervasive communication. With asynchronous (a.k.a. non-blocking) communication on the other hand there is no correlation between the sent-time and the receive-time of messages. This decouples the availability of communication partners in time and thus makes it appropriate in wireless network environments.
Reïfied Message History: Asynchronous communication comes with the cost that one must remember a previous communication state. Contrary to synchronous communication where such state is carefully managed on the runtime execution stack, the application program now needs to concern itself with session management. Such a message history kept by every individual partner effectively distributes the computational state such that all involved devices have only trace of the computation. In order to allow the application program to manage such a message history, we choose to reïfy it.
Reïfied Environmental Context: Mobility of devices implies changing environments, which further implies that the software needs to adapt to new environments. A formalism for mobile networks must thus provide a first class representation of the surrounding environment that is automatically updated as changes occur.

Despite the limitations of the actor model, it adheres to the non-blocking communication criterion and provides an isolated data model. Although the actor model does not completely support programming for mobile ad-hoc networks, we believe it provides a solid starting point to extend it such that the missing criteria, namely the reïfication of communication traces and environmental context, are supported too.

3.2 Extensions to Actors

The ambient actor model extends the call-by-value lambda in the same manner as the standard actor model introduces primitives such as send, become and letactor. However, dissimilar to the standard actor model, the letactor primitive has been decomposed into two primitives newadr and initbeh. The former creates a new actor address and the latter initializes the behavior linked to this actor address. Next to the standard actor primitives we added a number of primitives to manipulate mailboxes:

messages(e) returns the set of messages of mailbox e.
add(mbxName, e) adds a message e to the mailbox with name mbxName. A message added to a mailbox that does not exist creates the mailbox.
delete(mbxName, e) deletes a message e from the mailbox with name mbxName

In the following subsections we define the operational semantics of these operations as an extension of the standard actor model. These operational semantics are defined as transitions of configurations.

3.3 Messages and Mailbox Associations

We now define a number of sets related to the representation of messages and mailboxes in the ambient actor model. We take as given countable sets $\mathbb{A}{\tt t}$ (atoms) and $\mathbb{X}$ (variables including actor mail addresses).

Definition 1 ( $\mathbb{V}$ $\mathbb{E}$ ) : The set of , $\mathbb{V}$ , the set of $\mathbb{E}$ , and, the set of actor , $\mathbb{A}s$ are defined inductively:

$\mathbb{V} = \mathbb{A}t \cup \mathbb{X} \cup \lambda\mathbb{X}.\mathbb{E} \cup pr(\mathbb{V},\mathbb{V})$

$\mathbb{E} = \mathbb{V} \cup app(\mathbb{E}, \mathbb{E}) \cup \mathbb{F}_{n}(\mathbb{E}^{n})$ where $\mathbb{F}_{n}(\mathbb{E}^{n})$ is all arity-n primitives.

$\mathbb{A}s = (?_{\mathbb{X}}) \cup (\mathbb{V}) \cup [\mathbb{E}]$

Say Y is a set then ${\bf P}_\omega[{\tt Y}]$ is the set of finite subsets of Y. ${\bf M}_\omega[{\tt Y}]$ is the set of finite multi-sets with elements in Y. $Y_{0} \overset{{\tt f}}{\rightarrow}Y_{1}$ is the set of finite maps from $Y_{0}$ to $Y_{1}$ . be the domain of .

A message is represented as a nested pair of value expressions, this is in contrast with the message representation as defined in [AMST97] (where a message was denoted with $<{b}{\overset{}{\Leftarrow}}{cv}>$ ). By representing the messages as a pair of values the message becomes a first class value in the actor language. This will prove useful to manipulate the mailboxes. Another difference with the standard actor model is that the message includes the sending actor (called the source). To make a clear distinction in the definitions between messages and other pair values, we will identify a pair that is used as a message with ${b}{\overset{a}{\Leftarrow}}{cv}$ .

Definition 2 (Messages ( $\mathbb{M}$ ))

$\displaystyle \mathbb{M} = \{ pr(a, pr(b,cv)) \in \mathbb{V} \enskip\vert\enskip a, b, cv \in \mathbb{V}\}$

A message is a nested pair (pr) of:

, the actor address of the source actor.
, the actor address of the target actor.
, a communicable value, constructed from atoms and actor addresses, but not containing closures.

In the spirit of dynamic typing (as in [AMST97]) we do not restrict the target of the message to the set of actor addresses, the correctness is checked in the rules that define the operational semantics.

In the ambient actor model a message can be associated with multiple mailboxes. To denote these mailbox associations in the actor model we introduce the following set:

Definition 3 (Mailbox Associations ( ${\tt m}\mathbb{B}$ ))

$\displaystyle {\tt m}\mathbb{B} = \{ \beta \in \mathbb{X} \overset{f}{\rightarr... ...) \enskip\vert\enskip ct \in \mathbb{V}, a \in \mathbb{X}, mbx \in \mathbb{S}\}$

$\mathbb{S}$ is the set of identifiers for mailboxes, $\mathbb{S} \subset \mathbb{A}{\tt t}$ . The set of mailbox associations is a mapping from an actor mail address to a mapping of the names of its mailboxes to their contents. To increase the readability, mappings of $\beta$ will be written as $<ct\enskip\vert\enskip{mbx_a}>$ with $a \in Dom(\beta)$ and $\beta(a) = \delta$ . Furthermore, $mbx \in Dom(\delta)$ and $\delta(mbx) = ct$ . $ct \in \mathbb{V}$ denotes the content associated with mailbox

. The name of the mailbox is written as the identifier $mbx \in \mathbb{S}$ , subscribed with the actor address $a \in \mathbb{X}$ to which the mailbox belongs. E.g.,

denotes the inbox of actor

. Typically, messages are associated with a mailbox, but other value types can also be associated with a mailbox.

3.4 Actor Configurations

The operational semantics of the model itself is based on actor-configurations and reduction rules defined on these configurations. Conceptually, an actor configuration can be perceived as the runtime state of an actor system (discussed in section 2.5). Such an actor system runs on any computational device, such as a mobile phone or desktop.

Definition 4 (Actor Configurations ( $\mathbb{K}$ ))

$\displaystyle \bigl\langle\!\!\bigl\langle \alpha\enskip\vert\enskip\mu\bigr\rangle\!\!\bigr\rangle ^{\rho}_{\chi}$

where $\rho$ , $\chi \in {\bf P}_\omega[\mathbb{X}], \alpha \in \mathbb{X} \overset{f}{\rightarrow}\mathbb{A}s$ , and $\mu \in {\bf M}_\omega[{\tt m}\mathbb{B}]$

An actor configuration contains:

the state of the actors in a configuration is given by an actor map $\alpha$ . Such an actor map is a finite map from actor addresses to actor states. Each actor state is one of
- uninitialized actor state created by an actor with address
- actor state ready to accept a message where is its behavior represented by a closure
- actor in a busy state executing expression . is either a value expression or a reduction context R filled with a redex (written as ${\tt R[}r{\tt ]}$ ). The reduction context is used to describe internal transitions while a message is being evaluated by the $\lambda$ -function associated with the behavior. The current expression that is evaluated is decomposed into a reduction context with a unique hole. For the formal elaboration on reduction contexts we refer to the standard actor model [AMST97]. Suffice it to say that here that R in the following definitions ranges over the reduction contexts. The redexes that are not actor-specific expressions, namely the purely functional fragment of the language, are inherited from the operational semantics of the standard actor model. The redexes related to the actor operations are newadr(), init( ), become( ), send( $v_{0}, v_{1}$ ), add( ), delete( ) and messages( ).
Each mapping of an actor address to an actor state is subscribed by their actor address. E.g. denotes an uninitialized actor that was created by actor .
$\mu$ , a multi-set of mailbox associations.
$\rho$ , receptionists, the actor addresses from this configuration that are accessible from other actor configurations
$\chi$ , external actors, the addresses of actors from other actor configurations that can be accessed from this actor configuration.

It is required that all actor configurations satisfy the following well-formed-edness constraints (

=Dom( $\alpha$ )):

$\rho \subseteq A$ and $A \cap \chi = \emptyset$ ,
if $\alpha(a) = (?_{a'})$ , then $a' \in A$ ,
if $a \in A$ , then FV $(\alpha(a)) \subseteq A \cup \chi$ ,
if $<ct\enskip\vert\enskip mbx_a> \in \mu$ , then $a \in A$
if $<ct\enskip\vert\enskip mbx_a> \in \mu$ then FV $(ct) \subseteq A \cup \chi$

FV(

) is the set of all free variables encountered in an expression

as defined by Agha et al [AMST97].

The fourth constraint is a new constraint and denotes that each mailbox in an actor configuration should be owned by an actor from the actor configuration.

3.5 Operational Semantics of Actor Configurations

Now that we have defined the necessary sets involved in the formalization of the operational semantics of the ambient actor model we can define the actual operational semantics. The operational semantics are defined as reduction rules on actor configurations. Conceptually, such a rule can be regarded as an evaluation step of an actor system. Each rule contains a label

that consists of a tag indicating its name and a set of parameters. In all cases, except for the i/o transitions (with tags

), the first parameter names the

actor of the transition.

As in the paper of Agha et al. [AMST97] we use the following notation for maps: if the mapping $\alpha'(a) = (b)$ and if $\alpha$ differs from $\alpha'$ in that is omitted from its domain then we write $\alpha'$ as $\alpha,(b)_a$ such that the focus is on the state of actor . We follow the same convention for other maps with actor addresses in their domain, such as mailbox associations.

In our model the transitions ( $\mapsto$ ) are extended with an environmental context set $\tau$ . The set $\tau$ contains the actor configurations that are available (in the communication range of the actor configuration on which the transition is defined) while the reduction is performed. The introduction of this set is important to reïfy the notion of environmental context in our extended model. Below we explain and discuss the different rules.

Definition 5 ( $\underset{\tau}{\mapsto}$ ) $\tau \in {\bf M}_\omega[\mathbb{K}]$

${\tt <fun:}a{\tt >}$

$e\buildrel\lambda\over\mapsto_{\hbox{Dom}(\alpha)\cup{\{a\}}}e' \Rightarrow \b... ...ngle \alpha,[e']_a\enskip\vert\enskip\mu\bigr\rangle\!\!\bigr\rangle ^\rho_\chi$

${\tt <new:}a,a'{\tt >}$

$\bigl\langle\!\!\bigl\langle \alpha,\hbox{\tt [R}[{\tt newadr()}]\hbox{\tt ]}_... ...enskip\vert\enskip\mu\bigr\rangle\!\!\bigr\rangle ^{\rho}_{\chi}\qquad a' fresh$

${\tt <init:}a,a'{\tt >}$

$\bigl\langle\!\!\bigl\langle \alpha,\hbox{\tt [R}[{{\tt init(}a',v{\tt )}}]\hb... ...tt ]}_a,v_{a'}\enskip\vert\enskip\mu\bigr\rangle\!\!\bigr\rangle ^{\rho}_{\chi}$

${\tt <become:}a,a'{\tt >}$

$\bigl\langle\!\!\bigl\langle \alpha,\hbox{\tt [R}[{{\tt become(}v{\tt )}}]\hbo... ...gle \alpha,v_a\enskip\vert\enskip\mu\bigr\rangle\!\!\bigr\rangle ^{\rho}_{\chi}$

${\tt <send:}a,m{\tt >}$

$\bigl\langle\!\!\bigl\langle \alpha,\hbox{\tt [R}[{{\tt send(}v_0,v_1\hbox{\tt... ...ox{\tt ]}_a\enskip\vert\enskip\mu, m\bigr\rangle\!\!\bigr\rangle ^{\rho}_{\chi}$

with $m=<{v_0}{\overset{a}{\Leftarrow}}{v_1}\enskip\vert\enskip{outbox_a}>$

${\tt <local:}m{\tt >}$

$\bigl\langle\!\!\bigl\langle \alpha\enskip\vert\enskip\mu,m\bigr\rangle\!\!\bi... ...ngle \alpha\enskip\vert\enskip\mu, M\bigr\rangle\!\!\bigr\rangle ^{\rho}_{\chi}$

with $m=<{b}{\overset{a}{\Leftarrow}}{cv}\enskip\vert\enskip{outbox_a}>$

and $M=\{<{b}{\overset{a}{\Leftarrow}}{cv}\enskip\vert\enskip{sentbox_a}>, <{b}{\overset{a}{\Leftarrow}}{cv}\enskip\vert\enskip{inbox_b}>\}$

if $a, b \in Dom(\alpha)$ and $x = a \vee b$ then $\nexists \alpha(x) = [g]$ with $g \in \mathbb{A}s$

${\tt <out:}m{\tt >}$

$\bigl\langle\!\!\bigl\langle \alpha\enskip\vert\enskip\mu,m\bigr\rangle\!\!\bi... ...bigr\rangle\!\!\bigr\rangle ^{\rho\cup\{a\}\cup(FV(cv)\cap Dom(\alpha))}_{\chi}$

with $m=<{b}{\overset{a}{\Leftarrow}}{cv}\enskip\vert\enskip{outbox_a}>$ if $b \in\chi, a \in Dom(\alpha)$ and

$\nexists \alpha(a) = [g]$ with $g \in \mathbb{A}s$

${\tt <in:}m{\tt >}$

$\bigl\langle\!\!\bigl\langle \alpha\enskip\vert\enskip\mu\bigr\rangle\!\!\bigr... ...u,m\bigr\rangle\!\!\bigr\rangle ^{\rho}_{\chi\cup\{a\}\cup(FV(cv)-Dom(\alpha))}$

with $m=<{b}{\overset{a}{\Leftarrow}}{cv}\enskip\vert\enskip{inbox_b}>$ , $b \in\rho$ and $FV(cv) \cap Dom(\alpha) \subseteq \rho$ ,

if $\nexists \alpha(b) = [g]$ with $g \in \mathbb{A}s$

${\tt <ack:}m{\tt >}$

$\bigl\langle\!\!\bigl\langle \alpha\enskip\vert\enskip\mu\bigr\rangle\!\!\bigr... ...angle \alpha\enskip\vert\enskip\mu,m\bigr\rangle\!\!\bigr\rangle ^{\rho}_{\chi}$

with $m=<{b}{\overset{a}{\Leftarrow}}{cv}\enskip\vert\enskip{sentbox_a}>$ , $FV(cv) \cap Dom(\alpha) \subseteq \rho$ ,

if $b \in\chi, a \in Dom(\alpha)$ and $\nexists \alpha(a) = [g]$ with $g \in \mathbb{A}s$

${\tt <rcv:}a,m{\tt >}$

$\bigl\langle\!\!\bigl\langle \alpha,(v)_a\enskip\vert\enskip\mu, m\bigr\rangle... ...{\tt )]}_a\enskip\vert\enskip\mu, m'\bigr\rangle\!\!\bigr\rangle ^{\rho}_{\chi}$

with $m=<{a}{\overset{b}{\Leftarrow}}{cv}\enskip\vert\enskip{inbox_a}>$ and $m'=<{a}{\overset{b}{\Leftarrow}}{cv}\enskip\vert\enskip{rcvbox_a}>$

${\tt <messages:}a,mbx{\tt >}$

$\bigl\langle\!\!\bigl\langle \alpha,\hbox{\tt [R}[{{\tt messages(}mbx{\tt )}}]... ...}]\hbox{\tt ]}\enskip\vert\enskip\mu\bigr\rangle\!\!\bigr\rangle ^{\rho}_{\chi}$

with $ct_i \in \{ct \enskip\vert\enskip<ct \enskip\vert\enskip mbx_a> \in \mu\}$

${\tt <add:}a,mbx,ct{\tt >}$

$\bigl\langle\!\!\bigl\langle \alpha,\hbox{\tt [R}[{{\tt add(}mbx,ct{\tt )}}]\h... ...box{\tt ]}_a\enskip\vert\enskip\mu,m\bigr\rangle\!\!\bigr\rangle ^{\rho}_{\chi}$

with $m=<ct\enskip\vert\enskip mbx_a>$

${\tt <delete:}a,mbx,ct{\tt >}$

$\bigl\langle\!\!\bigl\langle \alpha,\hbox{\tt [R}[{{\tt delete(}mbx,ct{\tt )}}... ...hbox{\tt ]}_a\enskip\vert\enskip\mu'\bigr\rangle\!\!\bigr\rangle ^{\rho}_{\chi}$

with $\mu'=\mu \backslash \{<ct\enskip\vert\enskip mbx_a>\}$

${\tt <join>}$

$\bigl\langle\!\!\bigl\langle \alpha_0\enskip\vert\enskip\mu_0\bigr\rangle\!\!\... ...ip\vert\enskip\mu_0,M\bigr\rangle\!\!\bigr\rangle ^{\rho_0}_{\chi_0 \cup \{a\}}$

if $\exists \kappa \in \tau$ with $\kappa = \bigl\langle\!\!\bigl\langle \alpha_1\enskip\vert\enskip\mu_1\bigr\rangle\!\!\bigr\rangle ^{\rho_1}_{\chi_1}$ and $\nexists \alpha_{0}(b) = [g]$ with $g \in \mathbb{A}s$ and

$M=\{ <pr(a,cv)\enskip\vert\enskip{joined_{b}}>, <{b}{\overset{b}{\Leftarrow}}{... ...{required_{b}}>\in \mu_0 \wedge <cv\enskip\vert\enskip{provided_{a}}> \in \mu_1$ }

${\tt <disjoin>}$

$\bigl\langle\!\!\bigl\langle \alpha_0\enskip\vert\enskip\mu_0\bigr\rangle\!\!\... ...p\vert\enskip\mu_0\backslash T,M\bigr\rangle\!\!\bigr\rangle ^{\rho_0}_{\chi_0}$

if $\nexists \kappa \in \tau$ with $\kappa = \bigl\langle\!\!\bigl\langle \alpha_1\enskip\vert\enskip\mu_1\bigr\rangle\!\!\bigr\rangle ^{\rho_1}_{\chi_1}$ and $\nexists \alpha_{0}(b) = [g]$ with $g \in \mathbb{A}s$ and

$M=\{ <pr(a, cv)\enskip\vert\enskip{disjoined_{b}}>, <{b}{\overset{b}{\Leftarrow}}{\tt disjoin}\enskip\vert\enskip{inbox_b}> \,\vert\,$

$<pr(a, cv)\enskip\vert\enskip{joined_{b}}> \in \mu_0 \wedge a \in Dom(\alpha_1)\}$

$T = \{<pr(a, cv)\enskip\vert\enskip{joined_b}> \,\vert\, <pr(a,cv)\enskip\vert\enskip{joined_{b}}> \in \mu_0 \wedge a \in Dom(\alpha_1)$ }

3.5.1 Basic Actor Operations

The first three reduction rules (

, letactor and

) remain unchanged with regard to the actor model. The become on the other hand had to be modified to ensure correct semantics with respect to the first-class mailboxes.

The rule above delegates the purely functional expressions used in the actor program to the functional redexes. The functional redex contains reduction rules for function calls, cons-cell manipulation, branch-testing, type-testing and equality. For the exact definition of these reduction rules we refer the reader to [AMST97].
The semantics of the letactor primitive is formalized by two rules, and . The rule is used to create a new actor with address a'. The new actor is not initialized after this reduction. We say that a variable is fresh with respect to a context of use if it does not occur free or bound in any syntactic entity. The new uninitialized actor is denoted with $(?_a)_{a'}$ .
With the rule a new actor is initialized with behavior . Only the actor that created the actor a' can initialize it.
With the rule the actor can change its state and behavior, similar to the become rule in the standard actor model. However, in the rule defined by Agha et al. [AMST97] the expressions evaluated after a become will be further reduced in the context of a new anonymous actor. It is this anonymous actor that introduces the intra-object concurrency in the actor model.
In the changes we have made, this remaining expression is not further reduced, changing its semantics similar to a break instruction found in many programming languages. The reason we removed intra-object concurrency is to ensure mailbox manipulations have correct semantics. Indeed, if the remaining expression is reduced in the context of an anonymous actor and mailboxes would be manipulated then the mailboxes of the anonymous actor would be manipulated instead of the actor that started to process the message. This would lead to awkward semantics. An alternative to this solution would be to let an anonymous actor manipulate the mailboxes of the actor that spawned it. However, this would introduce race conditions on the mailboxes. The topic of safe access to mailboxes is further discussed below in section 3.5.3.

3.5.2 Communication Rules

The remainder of the rules have been adapted to include the notion of mailboxes:

The rule mildly differs from the send rule found in the actor model. The new rule reduces the send operation to placing the message in the outbox of the actor in which the send operation is reduced.
is a new rule that was added to model local communication between actors. If the message can be delivered locally (within the same actor configuration), it is placed both in the target its inbox, and the sentbox of the sender. The rule is defined such that communication can only occur when the two actors involved in the communication are not in a busy state. Similar conditions are also specified for the other i/o-transitions. These conditions are necessary to preserve the model from race conditions. This will be discussed in section 3.5.3.
The out reduction rule is used at the sending side for messages that cannot be delivered locally, to transmit a message to another actor configuration. Similar to the original model, the set of receptionists is expanded with the local actor addresses that were communicated in the message. The outgoing message is removed from the outbox.
an actor configuration receives a message from an external actor that runs on another actor system. In this situation, the message is placed in the inbox of the target actor.
an actor configuration receives an acknowledgment for a message it send and places that message in the sentbox of the sending actor. This allows the actor to verify which messages have actually been sent.
When a message is available in the inbox of an actor, it can be received by the actor and when it is processed by the actor, it is moved to the rcv mailbox. As a result, an actor has a history of the messages that it processed. This proves to be useful for determining the communication state of an actor as is shown in the examples in section 4.

3.5.3 Mailbox Manipulation

Some reduction rules have been added to manipulate and inspect the mailboxes from within the actor language. With the rule one can access the content of a mailbox. The rule creates a mailbox when it does not exist, if the mailbox exists, the content will be added to the mailbox. The rule delete a message from a mailbox, when the last message of a mailbox has been removed, the mailbox itself is removed. The above reduction rules allow actors to manage mailboxes explicitly. Note that there is no rule in which a message automatically disappears from the system. This means that memory management will have to be handled manually by the programmer. This is because it depends on the semantics of the program whether a message has become irrelevant to the program. For example, when a certain task has completed and its associated messages are not relevant anymore.

When scrutinizing the ambient actor model, one has to investigate whether if there are concurrency issues involved with the reïfication of the mailboxes. For example, a possible race condition is an actor that deletes a message from its outbox at the moment it is transferred to the target actor its inbox. The operational semantics of the ambient actor model exhibit two mailbox properties that are important to avoid race conditions on the mailboxes of an actor.

Mailbox Privacy
Each mailbox has a unique name within an actor. A mailbox is associated with exactly one actor and an actor cannot communicate a reference to one of its mailboxes. However, it is possible to communicate the name of a mailbox, but this name refers to the local mailbox of the receiving actor and not to the mailbox of the sending actor. Hence, mailboxes are never shared among multiple actors.
Serial Mailbox Access
In the ambient actor model a mailbox is manipulated by two different entities: the actor owning the mailbox and the actor system which updates mailboxes when communication events occur, for example when a message is transmitted. The operational semantics of the ambient actor model is defined in such a way that the manipulation of mailboxes by these two entities cannot occur concurrently. Indeed, the rules where the actor system manipulates mailboxes as a result of a communication event have the explicit condition that the actor whose mailboxes are being manipulated is not in a busy state. Hence, while an actor is processing a message its mailboxes can only be changed by itself, not by the actor system. Messages that the actor system cannot send at that time remain in the out mailboxes of the corresponding actors until they can be transmitted.

Both the mailbox privacy and the serial mailbox access properties are important in the context of implementations based on this model, because they preserve the encapsulation of the actors and avoid race conditions on mailboxes.

3.5.4 Handling Environmental Contexts

Applications running on mobile nodes need to have access to the reïfied environmental as discussed in the introduction, so that they can address local resources. The reïfication of the environmental context is supported with two reduction rules:

and

. When two devices are in the communication range of one another, their actor systems will automatically ``join''. They disjoin when they leave each others communication range. Actors are usually interested in the appearance and disappearance of specific types of resources. To this end, four extra mailboxes have been added for each actor: provided, required, joined and disjoined. The mailboxes provided and required are used to let an actor specify an abstract description of what kind of behavior it provides or requires, this abstract description is called a pattern. The pattern is specified in the model as a communicable value. When a pattern in the provided and required mailboxes of different actors match, then the actor that required the pattern will be notified. This notification happens through the use of the joined and disjoined mailboxes. Thus, the joined and disjoined mailboxes keep track of the relevant actors, specified through the use of the provided and required mailboxes, that are in communication range. This mechanism is defined in the model through the

and

rules:

when two actor configurations come in the communication range of one another then every actor that requires a certain pattern , which has become available in another actor configuration $\kappa$ that is in communication range, will be informed of this by receiving a ``join'' message in its inbox. Also, for every matching pair of required-provided patterns, the corresponding joined mailbox is updated. In the joined mailbox, a special kind of message is stored, called a resolution. A resolution contains a) the pattern ( ) that has been matched and b) a provider actor who provides the service represented by the pattern. Hence, the resolutions found in the mailbox of an actor specify the actor addresses of the resources that matched the pattern.
The rule specifies the semantics of two actor configurations that leave each others communication range. Every actor that is aware of another joined actor that has left the communication range, will be informed of the disjoin. Once an actor is informed the corresponding resolution is removed from the joined mailbox. Actors that have removed the matching messages from their joined mailbox will not be informed.

The join and disjoin operations are not the inverse of one another. After joining and disjoining two actor configurations, the state of the involved actor configurations is not necessarily the same as before the join operation. This is due to the fact that for every join or disjoin a number of messages are sent, which might influence the behavior of the involved actors.

4 Case Studies

Now that we have defined the operational semantics of the ambient actor model we show that it is useful in the context of mobile networks by means of two examples. The examples are defined with actor code based on the semantics of the ambient actor model from the previous section. The first example shows how anonymous communication can be expressed. In the second example we elaborate on a meeting scheduler application for use in a mobile ad-hoc network.

In the examples below we use the convention that functions prefixed with mk create the respective messages and functions that end with a ``?'' are predicates. For example, mkPrint is a function that creates the print message and print? is a function that returns true if its argument is a print message.

4.1 Pattern-Based Communication

In section 3.1 we discuss that distributed naming is a good abstraction to communicate with resources in the environment for which the address is unknown. For example, an actor that wants to print a file on a printer first needs to locate a suitable printer in the environment and then communicate with it. With a distributed naming scheme both actions can be abstracted in a single communication instruction psend that allows an actor to be named based on its properties rather than on a specific address. Below is the definition of an actor using the psend abstraction to print a file from the moment it comes into communication range of an actor that provides a printing service.

$B\sb{Customer}$ = $\lambda$ file. $\lambda$ m.
seq(psend('printer@300dpi, mkPrint(file)),
become(handleJoin))

In the ambient actor model the addresses of resources can be retrieved based on the pattern through the mailboxes that reïfy the environmental context. Hence, an actor can be described using a pattern that embeds the type information [KB02] or more semantic information about the service. We define a new communication primitive psend that takes two parameters: a service description pattern of the required actor and the message that is to be sent.

psend = $\lambda$ pattern. $\lambda$ msg.
seq(add('required, pattern),
add('pending, msg))

We add the description pattern of the required actor to the required mailbox. This way the actor will be notified when the actor configuration joins with another actor configuration providing this pattern. The message that is to be communicated is placed in a custom mailbox pending. Hence, the pending mailbox can be regarded is a special outbox for messages that have a pattern as destination instead of an actor address.

The handleJoin definition listens for join messages that indicate that the joined mailbox has been changed. In such an event it runs through the resolutions in the joined mailbox. Each time a pattern that corresponds with the target of the messages in pending mailbox is found, the message is sent to the provider of the pattern and removed from the pending mailbox.

handleJoin = $\lambda$ msg.
   if(join?(msg),
       for-each( $\lambda$ resolution.
           for-each( $\lambda$ pmsg.
               if(eq?(target(pmsg), pattern(resolution)),
                  seq(send(provider(resolution), pmsg),
                      delete('pending, pmsg))),
               messages('pending)),