MAGE: A Distributed Programming Model
MAGE: A Distributed Programming Model
By
Earl T. Barr
DISSERTATION
DOCTOR OF PHILOSOPHY
in
Computer Science
in the
of the
UNIVERSITY OF CALIFORNIA
DAVIS
Approved:
2009
i
Earl T. Barr
June 2009
Computer Science
Abstract
This thesis explores computation mobility. We view mobility, the selection of an execution
a novel programming abstraction, which we call a mobility attribute, that specifies where
mobility attributes to program components, nonempty sets of functions and their state. Once
bound to a component, mobility attributes apply prior to each execution of that component.
For example, a mobility attribute can specify that a computation should be collocated with
Mobility attributes are the primitives that form MAGE, a new programming model
that allows a programmer runtime control over the location of a program’s components.
This control can improve the program’s robustness or its runtime efficiency by co-locating
components and resources. To illustrate the utility of MAGE, this thesis presents the design
and implementation of the MAGE programming model in a Java library that extends Java’s
ii
To my family — Kerrean, Nathan, and Nicolas
iii
Contents
List of Algorithms ix
List of Listings xv
1 Introduction 1
1.2 Mobility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 MAGE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2 Two Π Tutorials 10
2.1 RMI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.1.1 Server . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.1.2 Client . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2 MAGE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3 Mobility Attributes 20
3.1 Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
iv
3.3.1 Operational Semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.1 Primitives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.4 Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.4.4 Invocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
v
4.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
5 Location Services 78
5.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
5.3 Correctness of FP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
6 Implementation 115
vi
6.3.2 Distributed Garbage Collection . . . . . . . . . . . . . . . . . . . . . . 121
7 Evaluation 147
vii
8 Related Work 182
9 Conclusion 196
References 199
viii
List of Algorithms
ix
List of Figures
x
3.17 Invocation Evaluation Rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.4 d-Attributes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
4.5 a-Attributes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
4.6 StaticPartition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
xi
5.8 The FI Race . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
xii
8.1 Reconfigurable Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
xiii
List of Listings
1.1 An Invocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.3 ComputeEngine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.4 ComputePi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.1 An Invocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4.2 MobilityAttribute . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.7 MajorityRules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
4.8 Populating the MAGE Resource Manager with Resident Component Counts . 67
4.9 CPULoad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
xiv
4.10 The MAGE find Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
xv
List of Tables
7.2 Mean MAGE Overhead Relative to RMI as Fraction of Total Time. . . . . . 154
xvi
Acknowledgments
I would like to thank my advisor, Raju Pandey, for his patience and for the time he
Ron Olsson and Prem Devanbu served on both my dissertation and qualifying exam
committees. I am grateful to Ron for his time, and his prompt and careful feedback. I am
grateful to Prem for showing that there is room in research for polymaths. I am grateful to
Felix Wu who has been unstinting with his time and unfailingly positive. I am especially
grateful to Zhendong Su, without whose generous support, both intellectual and financial, I
I want to thank Kim Reinking for her belief in me when my drive to finish flagged.
Talking and working with my fellow graduates students has been the best part of my
graduate school experience. Most of the computer science I know, I learned from them. I
have been fortunate to work with and learn from two generations of graduate students.
The first generation includes Michael Haungs, to whose mad skillz I pay homage, Eric
Hyatt, who has been my omnipresent sounding board, Aaron Keen, Fritz Barnes, Ghassan
David Hamilton, who challenges me to be precise, Mark Gabel, Rennie Archibald, and
Christian Bird.
I want to thank Michael Nadler who helped me design and implement MAGE.
xvii
1
Chapter 1
Introduction
The days of single address space computing are behind us. Driven by the power wall [77],
multicores are upon us — dual core machines are already ubiquitous, 16 core machines
are commercially available [35], and Intel Corporation is prototyping 80 core machines [65].
the resources of a single machine, turning it into a virtual cluster [62]. The World Wide
Web (WWW) [11] and peer to peer applications, like BitTorrent [84] and Gnutella [34],
are inherently distributed. Scientific computation is moving from its traditional super-
computer environment to distributed systems, lured by the expandability and cost savings.
To capitalize on this trend, companies now rent out processor farms [104, 114]; in academia,
In short, a wide variety of services and data is dispersed on architectures that are
heterogeneous and evolving. To cope with such change, distributed systems must support
resource discovery, incorporate new hardware, and handle variation in resource availability
such as network latency and bandwidth. For example, over time a host that was CPU-bound
may become idle, and one data source may be exhausted while another comes online.
To fully exploit the runtime environment, distributed programming models should provide
1.1. The Layout Problem 2
mechanisms that allow programs to control where their computations occur and thereby
support load balancing, respond to network congestion, and adapt to the appearance,
disappearance, and shifting of resources. This thesis presents one such programming model.
communicating components. A component has state and code, and communicates with other
components via messages. For example, the application could be a Web 2.0 service [115]
that runs across a browser on a home PC, middleware servers, and a backend database. At a
coarse granularity, the browser, the middleware, and the backend database are components;
implementation language. This thesis focuses on this latter, finer-grained view of components.
components that may intercommunicate in the lifetime of the application. The vertices are
components. The edges model communication channels. The principle of locality [24] means
that, at any point in time, the active components in an application’s working set comprise a
Figure 1.1b are execution engines and are not created equal. Some possess unique resources,
like a user or a database. The edges subsume the interconnection tissue of the network, such
the problem of mapping that application’s component graph onto a network of execution
engines. All distributed applications must confront the layout problem, which Figure 1.1
depicts. Both graphs are dynamic — the application can create and destroy components,
while execution engines can come online or go offline and their resource profiles can change.
Thus, an application must be able to dynamically adapt and refine its layout as it learns
1.1. The Layout Problem 3
=⇒
component should execute, and thus move. Two axes span the space of migration policies —
are often either manual or heuristic. Deployment specifications are migration policies
that statically map components to execution engines, where they remain for the life of
the application. Such specifications are usually manual, but tools exist that tackle static
automatic layout, notably Coign [46] and J-Orchestra [100]. These tools employ heuristics,
simplify the problem, and resort to human aid. Gang scheduling forms policies that
automatically change the layout of running applications at regular intervals [75]. FarGo
Programmers can use programming models that control component location to write
migration policies that change an application’s layout at runtime [63, Chapter 3]. These
policies allow the application to adapt to its environment. They straddle the automatic versus
This thesis falls into this last category. It presents a novel programming model for writing
1.2 Mobility
A travel agent application is often used to motivate mobile code, e.g., [109]. Figure 1.2
depicts two different implementations. Figure 1.2a uses mobile code, while Figure 1.2b uses
messages.
In Figure 1.2a, the application creates mobile code that travels the network searching for
the lowest fare to Ulan Bator, Mongolia. First, it searches all sites. Then it returns to the
site with the lowest fare, Southwest Airlines, where it purchases a ticket. Finally, it returns
This movement of code from one site to another, denoted by dashed lines in Figure 1.2a,
is just a message that contains the mobile code. In addition to the logic it uses to determine
which ticket to buy, this code must specify its itinerary, as well as contain the messages and
protocol logic for interacting with the airlines. The benefit of mobile code is that it converts
the messages that interact directly with the airlines from remote to local messages. The
Whatever the initial cost of migration, that cost increases as the code gathers state. In
Figure 1.2a, the mobile code collects and carries with it the lowest price it has yet seen.
When the actor and the airlines are in different administrative domains, two security concerns
arise: first, servers must accept and execute untrusted code; and second, clients must trust
that no server alters their code or its data. All attempts to address these security concerns
either add messages or additional state, such as proofs, to authenticate and validate mobile
In contrast, Figure 1.2b’s message-based implementation sends only data in its messages.
Thus, all of its messages and their replies are remote messages that must traverse the
network. The size of these messages are independent of the number of ticket vendor sites
searched. Because intermediate results return to the actor’s machine, the actor can monitor
1.2. Mobility 5
the progress of the search and potentially modify it. The message passing model only forces
airlines to expose a narrow API that supports the relevant ticket search protocol, not an
execution engine, which exposes a much larger surface for an attacker to probe.
ment has dominated server applications, ironically even this travel agent application, the
canonical example of a mobile agent application. For years, mobile programming languages
have not taken off outside of research prototypes. Like functional languages, mobile code
has had ardent supporters, but little traction in industry. The reason is simple. For many
applications, like the travel agent example, a message-passing implementation requires less
bandwidth and raises no security concerns related to executing untrusted code. Additionally,
the rate of change in computing environments has been slow enough for static approaches to
be adequate. Put another way, mobile code has lacked a “killer” application.
In spite of its problems, mobile code has always found its niches, especially within
can be delegated to a component. Such delegation is profitable when the savings from
collocating the participants in that subprotocol exceeds the cost of migration. Applications
1.2. Mobility 6
for which subprotocol delegation pays for itself form one such niche. The travel agent
application as presented does not fall into this niche because the site-specific subprotocol,
shown in Figure 1.2a, consists of a single message exchange. If instead, the mobile component
exchanged many messages with each airline it visited, the savings of collocation might have
Another niche is formed by applications that interact with large datasets and do not
know in advance how to group the elements in those datasets into result sets. Such an
application could build its result set, element by element, by sending a message to request
each element, at great cost. Of course, a single, specialized message that defines a specific
result set would be more efficient, but we do not know that results set in advance. In these
situations, a program is the most flexible and compact way to define a result set. When sent
as messages, these programs are mobile code. Complex SQL queries dispatched to remote
DBMS are one example of such programs. If the SQL queries a client could send were
replaced with distinct messages, their number would be bounded only by the combinatorics
Today, extensible browsers have changed the economics of startups [40]. Entirely new
services, like Gmail, run user interfaces and perform calculations, in their clients’ browsers.
The browser has evolved from a markup renderer to an extensible execution engine that
runs code sent by servers. The Web 2.0, built on the WWW using javascript and flash, is
Web 2.0 applications are easy to deploy and cheap to maintain. Unlike standalone
binaries, both initial installation and updates can happen whenever a user accesses the
application. These applications demonstrate that mobility can improve performance when
migration is cheap. Web 2.0 applications use mobile code principally in their user interfaces
to eliminate messages and network latency. Google Docs could not work without it.
Web 2.0 applications fundamentally rely on trust, although they do utilize techniques
such as sandboxing, certificates, and encryption. If you visit a Web 2.0 service, you trust
content including code from that service. Like Web 2.0, this thesis presents a programming
model that trusts both the components and the execution engines those components run on.
1.3. MAGE 7
1.3 MAGE
When invoked, a mobile component can move before executing. In Listing 1.1, c is a mobile
The invoker i runs the invocation in Listing 1.1. Relative to the invoker i, c is either local or
remote. In a dynamic, evolving distributed system, a program may wish to collocate c and
the external resources it needs or collocate c and i prior to c’s execution. This placement
problem becomes even more complicated when c needs more than one resource from different
hosts.
x = c.f (p1 , p2 );
Code requires a processor and storage to execute. We contend that mobile code requires
a third attribute, a migration policy, to address the layout problem. We present a novel
and binds to a program’s components. Before invoking c, the invoker i binds a mobility
A mobility attribute is the migration policy for the component to which it is bound. A
Mobility attributes capture all programming models proposed to date that incorporate
dynamic layout. They isolate migration logic from an application’s core logic. Because a
mobility attribute only moves a component when that component receives an invocation,
no time is wasted moving components not in use. Using mobility attributes, distributed
applications can employ migration policies that move components at runtime. They can
also bind different attributes to a component, as the runtime environment evolves. Finally,
programmers can combine simple mobility attributes to form attributes that apply complex
policies. For example, a programmer could combine an “execute on the least loaded host”
1.3. MAGE 8
attribute with one whose policy is “execute on the host with the most available bandwidth”
to form a new attribute whose policy is “execute on the least loaded host while compute
bound, then move to the host with the most available bandwidth to transmit results.”
This thesis presents and investigates the properties of MAGE (Mobility Attributes Guide
The principal contribution of this thesis is the MAGE programming model and its
realization. The novelty of MAGE rests on the above features it combines. MAGE defines
distributed invocations as configurations of invoker and invoked. The analysis of all combi-
and allows MAGE to encompass all proposed mobile programming models. Isolating an
object migration policy into mobility attributes relieves the programmer of the burden of
simultaneously thinking about layout and application logic. MAGE integrates invocation
and mobility, so it applies a migration policy only to objects currently exchanging messages,
i.e. currently in the working set. This relieves the programmer of the difficult task of,
and the performance cost of incorrectly, statically inferring such working sets. MAGE’s
attribute composition can construct complex policies from simple policies. MAGE provides
these qualitative benefits at low cost (Section 7.1). A programmer would choose MAGE for
projects that require dynamic layout adaptation because MAGE (1) separates the migration
concern into attributes; (2) facilitates policy reuse via attribute composition; and (3) offers
powerful, flexible, and elegant control over object and invocation placement.
1.3. MAGE 9
MAGE is best suited for applications whose optimal component placement is highly
is a case in point. A MAGE application can use mobility attributes to push the load-
balancing decision into clients, thereby eliminating a dedicated load-balancing tier and
improving scalability. For example, mobility attributes could round-robin SQL queries across
The rest of this thesis is organized as follows. Chapter 2 begins with a gentle introduction
to MAGE in which we re-implement Sun’s RMI tutorial under MAGE and contrast the
two solutions. Chapter 3 presents the semantics of MAGE’s mobility attributes. Chapter 4
presents the MAGE programming model, its primitives and operators. We show how mobility
attributes arose from an analysis of existing distributed programming models that incorporate
mobility, discuss the MAGE work published at ICDCS 2001 [8], and then generalize to
increase the power and flexibility of mobility attributes. Chapter 5 compares forwarding
pointers against a centralized directory, and shows that the invocation protocol MAGE
initially used, the self-routing invocations protocol, which combines lookup and invocation
messages into a single message, uses more bandwidth on average than the “find, then invoke”
protocol, which uses two distinct messages. Chapter 6 describes the implementation of
RMI, then presents the implementation of MAGE as a set of extensions to RMI. Chapter 7
measures the overhead of our implementation of mobility attributes and presents peripatetic
places MAGE into the context of its related work. Chapter 9 summarizes the thesis and
Chapter 2
Two Π Tutorials
Samuel Johnson
Rasselas, 1759
In July 2007, Sun’s remote method invocation (RMI) tutorial presents a generic framework
for moving code from a client to server for execution [69]. The code the client sends to the
server calculates π. Here, we introduce RMI and describe Sun’s tutorial. We then describe
2.1 RMI
Java’s Remote Method Invocation (RMI) mechanism allows an object, the client, running in
one Java virtual machine to invoke methods on an object, the server, running in another
Java virtual machine. These invocations are the arcs labeled RMI in Figure 2.1.
In Figure 2.1, the server object first registers with the rmiregistry, as shown by the
RMI arc from the RMI server to the rmiregistry. Then the client downloads a stub,
or proxy, for that server from the rmiregistry. For this to work, both client and server
must statically share the name the server used when it registered in the rmiregistry.
To send an invocation, the client locally invokes a method on the stub. The stub
2.1. RMI 11
marshals that invocation and sends it to the server. The arc directly from RMI Client
to RMI Server represents such an invocation. Upon receiving the invocation, the server
unmarshals the invocation, decodes the method, executes that method in its address space,
1 package compute;
3 import java.rmi.Remote;
4 import java.rmi.RemoteException;
8 }
For this to work, both the client and the server must share this method’s signature. Here,
that shared interface is Compute, shown in Listing 2.1. Compute defines the executeTask
The executeTask method contains a formal of type Task. Listing 2.2 defines Task.
As noted, Sun’s RMI tutorial presents a framework that allows clients to send code to servers.
This technique is called remote evaluation (REV) [93] and is discussed in greater depth in
2.1. RMI 12
1 package compute;
4 T execute();
5 }
RMI supports the code mobility of parameters, other than a method’s receiver, or this,
parameter. When a client wants to pass subclasses or classes that implement an interface
(the case here) as actuals to a RMI invocation, the classes of the actuals may be unknown
to the server. RMI annotates each invocation with a codebase attribute, which contains a
URL that points to the client’s codebase that contains such classes. When the server cannot
resolve a class, it attempts to find the class at that URL using its URLClassLoader.
Thus, Task allows clients to define classes that are statically unknown to the server, but
In Figure 2.1, the web servers serve these codebases. When the server object registers
itself, the rmiregistry downloads the server object’s class from the web server running on
the same host as the server object. When the client sends unknown classes that implement
Task to the server, the server downloads those classes from the client-side web server.
2.1.1 Server
Listing 2.3 depicts the initialization of the ComputeEngine server. To dynamically exchange
a stub, an RMI client and server must statically share a name under which to upload and
2.1. RMI 13
download that stub in the rmiregistry. Line 25 contains the declaration and initialization of
such a name.
In lines 27-8, the server implicitly starts the RMI infrastructure, publishes engine,
and receives a stub for engine. At this point, if the client had a statically deployed stub
or the server could send stub to the client, the client could invoke executeTask on
engine. In our example, the client dynamically acquires its stub, so the server gets a
stub for the rmiregistry on line 29, and then binds the name Compute to stub in the
2.1.2 Client
In Listing 2.4 on line 14, the client initializes the name that it statically shares with the server
in order to dynamically exchange stubs via the rmiregistry. On line 15, the client gets a
stub to the rmiregistry running on arg[0], the server’s host. The client immediately,
line 16, uses that stub to get a stub to the server’s ComputeEngine instance, engine.
On line 18, the client instantiates the Pi class. Its class definition follows.
Pi must implement the Task interface so that the server can execute it; it must
Machin’s formula [105], Equation 2.1, to compute π. We do not show the rest of Pi’s
π 1 1
= 4 arctan − arctan (2.1)
4 5 239
To start the server, we first start the rmiregistry, then the ComputeEngine, as
web server that accepts requests for Java classes. It fills the role of the web server in
2.1. RMI 14
Figure 2.1. It listens at port 2001, which codebase reflects. This RMI implementation
requires ClassFileServer so that engine server object can request and download the
Pi application.
2.2 MAGE
instance itself (the receiver of the invocation), are mobile. This means an application can
Listing 2.7 illustrates how MAGE simplifies the server-side of the RMI tutorial. MAGE
transparently manages mobile object stubs, so there is no need to explicitly exchange them
in the application code. Further, the client and server have no need to statically share the
name of a stub. A MAGE server simply executes the methods of mobile objects that visits
The only programmer-visible action here is to initialize the MAGE infrastructure on line
13. The corresponding activity in RMI occurs implicitly when the server publishes engine
MAGE directly supports mobility. Thus, there is no server object, like engine in the
RMI solution. Nor is there any need of the cumbersome indirection of the Task interface to
move the Pi class to the server. Instead, Pi extends MageMobileObject and moves to
MAGE’s version of ComputePi dispenses with the shared name and any interactions
with the rmiregistry. It adds the declaration and binding of an REV mobility attribute,
2.2. MAGE 17
on lines 11 and 13. Chapter 3 is dedicated to mobility attributes. For our immediate
purposes, a mobility attribute moves an object when that object is invoked. Here, the
mobility attribute rev takes the server’s name arg[0] as its target. When the Pi instance
task is invoked on line 14, rev moves it to the server where it executes. After printing out
the result, main calls System.exit(0) because instantiating the task object implicitly
calls MageServer.init() because all MAGE hosts are potentially servers. The exit
becomes
Although the MAGE server that handles incoming HTTP requests for classes is not
programmer visible, it is still present. Under MAGE, class serving functionality is built-in;
2.3. Summary 19
sets the path where the MAGE class server looks for classes. The RMI implementation pulls
For comparison with Listings 2.5 and 2.6, Listings 2.9 and 2.10 contain transcripts of
2.3 Summary
In this chapter, we have presented Sun’s RMI tutorial, which uses a statically shared interface
need for a shared interface, as well as the server-side engine object. We made the Pi class
mobile, instantiated it, and bound that instance to a remote evaluation mobility attribute.
When we invoked that instance, the mobility attribute dispatched the Pi instance to its
remote target for execution. In so doing, we have used mobility attributes without defining
Chapter 3
Mobility Attributes
While high over your heads you will see the best best
Who never quite know, while they zoop and they zoom,
Whether which will catch what one, or who will catch whom
Dr. Seuss
If I Ran The Circus, 1956
In this chapter, we introduce mobility attributes and define their semantics. We rely on
set theory and operational semantics. Our goal is to capture the essence of MAGE using a
In Section 3.1, we define the terminology used in this chapter. In particular, we define
component motion. Mobility attributes arose from the realization that these paradigms can
21
be characterized by the locations of an invoker and the invoked program component before
and after the invocation or as a pair of hosts — a starting host and a target host.
In Section 3.3, we define primitive mobility attributes to be precisely these pairs, then
show how existing programming paradigms fit into a taxonomy formed from these mobility
attributes. Classifying these paradigms yields a new paradigm, and surprisingly reclassifies
one paradigm as an instance of another. We then show how a programmer can bind these
attributes and their related programming model, form the work we presented at ICDCS in
2001 [8].
In Section 3.4, we lift the start and target hosts of primitive mobility attributes to sets
of start and target hosts. This generalization is natural and allows us to relax primitive
need to coerce a primitive mobility attribute when we do not care where a component starts,
i.e. where it receives an invocation, but only that it execute on a specified target.
Dynamic attributes allow programs to use mobility attributes to define migration policies
that react and adapt to a program’s environment at runtime. When policies, such as “execute
on lightly loaded systems” and “execute on systems that have a resident DBMS,” complement
each other, MAGE allows a programmer to compose them. Section 3.5 presents mobility
attribute composition and shows how a programmer might use composition to create complex
All the attributes presented to this point are client-side attributes. In Section 3.6, we
introduce server-side mobility attributes that bind directly to a component. These attributes
allow a component, in its role as a server, input into where it executes. For example,
programmers may wish, due to security concerns, to restrict where a component moves and
3.1 Terminology
Definition 3.1.1 (Execution Engine). An execution engine or host runs code. Execution
Remark. Because “execution engine” is a cumbersome phrase, we variously use host and
location as synonyms for it in the text that follows wherever that substitution is clear from
system image (SSI) cluster. The fact that execution engines do not nest implies that they
do not move.
associated data state. Components do not nest. Components reside within an execution
engine. Components can move, or change execution engines. An active component has
execution state — stack and register file. An inactive component has no execution state.
Remark. An active component is an actor [41]; it has its own thread of control. Since an
inactive component is just an active component with no execution state, we assume active
We have kept these definitions simple to closely reflect existing practice. Next, we use
them to model existing distributed programming paradigms, as well as propose new ones.
Listing 3.1, which repeats Listing 1.1 in Chapter 1, is an invocation statement in a component
statement differs from a local procedure call (LPC), in that i and c are not necessarily
collocated. What must happen when i calls an operation on c? Since c could be at a different
host than i, the system must find it. Let H denote the set of all hosts that comprise a
When i and c are not collocated, i needs some way to identify c. Let I be the set of unique
identifiers for C. If c is at the remote host r ∈ H, then the system must marshal the call’s
arguments2 , forward the arguments to the component, execute the call at r, and return the
When the location of the remote component is fixed and statically known, the find is
superfluous and we have a remote procedure call (RPC), as defined by Birrell et al. [13].
Figure 3.1 depicts an RPC invocation. Let find : I → H be the function that returns a
component’s location. When find(idi ) = l is the local host of i, then R = H − {l} is the set
of all hosts remote to l. From l, the invoker i calls c, which runs on r ∈ R. While running, c
accesses the resource d. When c finishes the computation, it returns the result to i. A remote
method invocation (RMI) is an object-oriented form of RPC in which the remote object is
an implicit parameter of the procedure call. Although Birrell et al.’s original definition of
RPC and Java’s RMI differ in some technical details, we give pride of place to RPC since it
came first and consider it the superset and RMI the subset3 . Further, we use RMI to denote
Now consider adding component mobility to the programming model. Find is no longer
static. Component location becomes a primitive and requires operators to manipulate it.
These operators can either be explicit or implicit. An obvious explicit operator is move(c, t),
l r
d
invocation
i c
result
hc
c
l
invocation move
i
h0c
result
c
to move a component for two reasons: first, the principle of locality assures us that the
component is in use and that the work required to move it is less likely to be wasted and,
second, at that time we can best decide where to move the component, since an application
can use its state at the time of the call as well as the current state of the system. In short, the
mobility with invocation eliminates the clutter of explicit move calls in an application’s
source code: it separates an application’s core logic from its mobility aspect.
Figure 3.2 depicts all possible single-step moves an invoked component can make relative
to its invoker. In Figure 3.2, hc ∈ H is component c’s host when the call reaches it, and
h0c ∈ H is the host on which it executes. When hc = h0c , the move arc becomes a self-loop
implicit to Figure 3.2 are well-known, albeit as “mobile design paradigms,” or architec-
tures [16]. In MAGE, we view these patterns as building blocks from which to construct
3.2. Integrating Invocation and Mobility 25
l r l r
c
d move d
result
i c
invocation i
l r l r
c move d d
invocation result
i i c
such architectures, not architectures themselves. We describe these three patterns next.
Figure 3.3 depicts Code on demand (COD). In COD, a function invocation requires
remote code c to execute locally because c requires the resource d. The code moves from the
remote site to the caller’s site. In the client-server model, COD allows the server to extend
the capabilities of the client. Java applets [6], JavaScript [112], and Adobe Flash [110]
are popular instances of this mobility pattern. In terms of Figure 3.2, COD occurs when
l 6= hc ∧ l = h0c .
Figure 3.4 depicts Remote evaluation (REV) [93]. In REV, the component is initially
local to the invoker, then moves to a remote target where it executes and accesses d. In
the client-server model, REV allows the client to extend the capabilities of the server.
Dispatching an SQL query to a database server is an example of REV. We also used REV
in Chapter 2, when we discussed Sun’s RMI example and converted it to MAGE. In terms
l = hx r = hy r = hx l0 = hy
d1 d1
d0 invocation d0 result
Figure 3.5 illustrates Mobile Agent 4 (MA) [21, 99]. MA makes most sense when resources
are distributed over time or space. Here, c uses both d0 and d1 . In MA, the invoker calls
itself — the invoker is the component. Thus, the component is necessarily active, unlike
COD and REV, and l changes as i moves. In terms of Figure 3.2, MA occurs when
l = hc ∧ l0 = h0c ∧ i = c.
At this point, we have exhausted all patterns implicit to Figure 3.2 that have appeared
in the literature and been named, not all the patterns it contains. These patterns can be
and the location at which it executes that invocation. These pairs uniquely identify each
pattern. In particular, they specify each pattern we have discussed so far. For example,
invocation used. Specified before an invocation, these pairs can select the paradigm an
invocation must use. Distributed systems are complex. Mobile components make them
more so. Controlling which paradigm an invocation uses helps the programmer manage that
complexity.
Primitive mobility attributes reify these pairs; they specify the host, start, at which a
4
Carzaniga et al. calls this pattern mobile agent. We would prefer to eschew the word agent because of
its AI connotations. However, the use of agent in the name of this pattern has gained widespread currency in
the literature, so, to avoid confusion, we follow convention. In this thesis, our focus is mobility; whether or
not the code is “intelligent” does not concern us.
3.3. Primitive Mobility Attributes 27
l hc
d
mobility
attribute
invocation
i c
component must receive an invocation and the host, target, at which it must execute that
invocation. Mobility attributes apply before an invocation and control which paradigm an
invocation uses. An attribute’s start and target pair are constraints that are enforced after
attribute has been bound, the component’s actual location must match the attribute’s
starting location or the component does not move, the invocation fails, and the invoker is
notified. Upon receipt of an invocation, a component moves to the attribute’s target host,
In Figure 3.6a, nodes are components and edges denote communication. The edges
combine the arc from an invoker to a component along which an invocation travels and the
corresponding back-arc along which the result returns, as depicted in the pattern figures,
such as Figure 3.4 (REV) above. Mobility attributes bind to program components in the
Definition 3.3.1. MAGE is the programming model that incorporates mobility attributes
Thinking about mobility attributes in terms of before and after pairs helps us see new
hc hc
d0 d0
c
l l
invocation move
i i
h0c h0c
result
c
d1 d1
invoked component moves. The new attribute move before execution (MBE) arises from this
observation. MBE generalizes COD, REV, and MA and encompasses all primitive mobility
attributes in which a component moves. Figure 3.7 depicts MBE. In terms of Figure 3.2,
MBE only requires hc 6= h0c . From hx = hy , we form the attribute execute in place (EIP)
which generalizes LPC and RPC, those attributes in which the component does not move.
Together, EIP and MBE partition the set of all single step component moves in a network
relative to an invoker, as depicted in Figure 3.2. If we view the set of mobility attributes as a
relation R, EIP is the set of all reflexive pairs in R, i.e. all subsets where if (x, y) ∈ R, x = y;
while MBE is the set of all irreflexive pairs in R, or all subsets where if (x, y) ∈ R, x 6= y. In
MAGE, we assume that EIP is always allowed: that is, the null move (a self-loop) is always
allowed.
find(idc ) at
Attribute Invocation Execution Notes
EIP h h
LPC l l h=l
RPC r r h=r
MBE hx hy hx 6= hy
COD r l hx = r ∧ hy = l
REV l r hx = l ∧ hy = r
RMC rx ry rx , ry ∈ R ∧ rx 6= ry
Mobility attributes bring into focus and define a taxonomy that encompasses both these
new attributes and the mobile code paradigms previously defined in the literature. Table 3.1
Table 3.1 does not include MA, because REV and MA are the same with respect to
At first glance, it might seem strange to see LPC in Table 3.1. It is included because its
pair (l, l) is one of the combinations inherent to Figure 3.2. Further, LPC arises naturally in
via COD. Every invocation other than the first one is LPC; indeed, that is the point of COD.
The Notes column in Table 3.1 shows how each attribute specializes either EIP or MBE.
The remote mobile code (RMC) attribute is the pair (rx , ry ), for rx , ry ∈ R, rx =
6 ry . It
differs from REV, in that it expects to find its bound component at rx , not l. In other words,
The operational semantics for a programming language describes how to interpret a valid
program as sequences of computational steps. These sequences then are the meaning of the
program. Often these steps are defined in terms of a state transition system that abstractly
captures the state of a program as it executes [82, 113]. Operational semantics has two
in its sequence. Here, we present the big-step operational semantics of primitive mobility
attributes.
To model the state of a distributed system, we first project the state of a single machine
onto an array. We concatenate all the machine arrays to form an array that represents
the state of the entire distributed system. To handle machine arrival and departure, we
assume an infinite array and that the block of indices assigned to a machine is never reused:
3.3. Primitive Mobility Attributes 30
when a machine returns to operation after going offline, we assign it a fresh name and a
fresh range of indices5 . Since symbolic indices are convenient, let that global state array
be associative. When Loc is the set of symbolic indices and Z is the set of cell values, the
function σ : Loc → Z models that associative array. The value of the global state array at x
is σ(x) = y. Any change in the contents of any cell generates a new function σ 0 . Let Σ be
the set of all possible σ functions, or all possible configurations of the global state array, i.e.
It therefore models time in terms of this sequence. Consider the case of the machine h going
offline. Since h is unique, we can use it to store its status — whether it is off- or on-line —
in global state. Going off-line then means that at some step h was on-line, then a subsequent
step marked it off-line. There is a total ordering of events on a single machine. To order
remote events of interest at a particular machine, we use a Lamport clock to define the
“happened before” relation [56]. Time is either discrete or continuous. If discrete, we can
events have a natural total ordering: Let p be the continuous probability mass function
denote the times at which a and b occurred. Then the probability that ta equals tb is 0 since
R ta
ta p(tb ) dtb = 0.
σ[x := n](x) = n
Changing state involves transitioning from one global configuration to another, from σ
Recall that C is the set of all components and that H is the set of hosts6 . Let c ∈ C and
use a unique identifier to refer to and find a component. Let I be the set of component
identifiers. MAGE uses I to query the global state to find a component’s current location,
so I ⊂ Loc. The function find : I → H takes a component identifier and returns that
component’s current location. The function reads global state, so I ⊂ Loc, H ⊂ Z and
Remark. For (s, t) ∈ A, s is the host at which the bound component must receive the
invocation; that is, find(idc ) = s must hold when c is invoked. The host t is the host at
which the bound component must execute; that is, find(idc ) = t must hold when c executes.
MAGE is a library that extends a host language. Let L denote that language. MAGE
requires L to implement some form of RPC; that is, L must support marshaling, a name
service, components either as objects or closures, and define P , a set of RPC proxies for
components. Below, MAGE assumes L supports exceptions, but this is not essential. MAGE
does not extend L’s type system or require L to provide any other features, not already
mentioned. We do not formally specify the semantics of a proxy-mediated RPC call, but
assume it. Informally, a proxy is generated for a component and has the same interface
as that component. When an operation is invoked on a proxy, the proxy marshals the
operation’s parameters and sends them to its component’s host, which in RPC is immutable.
If execution generates a return value, the proxy unmarshals it before returning it to the
caller.
An RMI proxy contains the host, port pair that identifies its component’s invocation
server and a component identifier the invocation server uses to route an incoming call to
the component. A MAGE proxy additionally contains a mobility attribute binding. That
binding may be null, as when no mobility attribute has yet been bound to a MAGE proxy.
6
As before, C is the vertex set of Figure 1.1a; H is the vertex set of Figure 1.1b.
3.3. Primitive Mobility Attributes 32
We denote the null binding as {NULL} and let A0 = A ∪ {NULL}. To add MAGE proxies
Note that bind ⊂ σ. Thus, Pm is the set of MAGE proxy variables. An RPC proxy also
contains a unique identifier for its component, so the MAGE’s proxy’s I component does
not distinguish the two. The I component in the MAGE proxy is lifted out of its RPC
proxy for notational convenience in the rules that follow. The essential difference between
a MAGE and an RPC proxy is the inclusion of A0 , which represents a mobility attribute
binding. A MAGE proxy need not always be bound to a mobility attribute. To denote an
unbound MAGE proxy, we bind NULL to it. Thus, A0 represents all possible bindings of
let x̂i be its ith basis. Initially, no mobility attribute is bound to any MAGE proxy, so
∀pm ∈ Pm , x̂2 • bind(pm ) = NULL7 . Figure 3.12 contains the rules that define the semantics
Definition 3.3.4 (Judgment). The judgment he, σi ⇓ n means that e evaluates to n in state
which divides an argument’s premises from its conclusion using a horizontal line, called the
Fitch bar. The premises are written above the line, the conclusion below [29]. In operational
semantics, the judgments above the bar are hypothesis judgments that must hold before we
can infer that the conclusion judgment below the bar holds.
When a rule has no judgment above the bar, it is a primitive evaluation rule that always
holds.
There are two ways to read an evaluation rule — forward, starting with the hypothesis
judgments, and backward, starting with the conclusion judgment. In the forward direction, if
we know that the hypothesis judgments hold, then we can infer that the conclusion judgment
holds. In the backward direction, they provide a mechanism for evaluating an expression.
Consider Figure 3.13a which contains the evaluation rule that defines the semantics of a
7
Here, we use the ith unit basis vector to extract the ith component. Recall that Kronecker delta
δij = 1 if i = j and 0 if i 6= j. Since δij = x̂i • x̂j , x̂i • ~v is the ith component of ~v .
3.3. Primitive Mobility Attributes 33
e ::= L expressions
|h for h∈H
com ::= L commands | idc for idc ∈ I
| bind(e, e) | pm for pm ∈ M
| unbind(e) | (s, t) for (s, t) ∈ A0
| move(e, e) | get(e)
| find(e)
| proxy(e)
hpm , σi ⇓ σ(pm ) : I × P × A0
he, σi ⇓ idc
hproxy(e), σi ⇓ σ(pm ) : I × P × A0
the forward direction, we see that if no attribute is bound, hpm , σi ⇓ (idc , p, NULL), and a
standard RPC invocation on pm ’s internal RPC proxy p transitions global state from σ to
σ 0 , hp.f (E), σi ⇓ σ 0 , then we can conclude hpm .f (E), σi ⇓ σ 0 , that a MAGE proxy-mediated
invocation will also transition the global state from σ to σ 0 . In the backward direction, we
see that to evaluate any MAGE proxy-mediated invocation we must first lookup up the
current values bound to pm . If no mobility attribute is bound to pm , the next and final step
MAGE extends L with the commands and expressions in the grammars in Figure 3.8.
In operational semantics, commands change state thus causing the transition σ → σ 0 , while
Figure 3.9 specifies the rules for evaluating the MAGE primitives. In particular, idc and
pm are variables. Figure 3.10 depicts the evaluation rule associated with the MAGE proxy
3.3. Primitive Mobility Attributes 34
generator function. Given an idc , the MAGE proxy generator produces a fresh MAGE proxy
that contains the passed idc . A MAGE proxy also contains an RPC proxy. For brevity, we
assume L provides a mechanism for creating a proxy from a component, which the MAGE
proxy generator uses implicitly to assign p to the MAGE proxy it creates. Finally, it assigns
Figure 3.11 presents the semantics of find and move which query and modify a component’s
location; Figure 3.12 defines how the bind and unbind commands associate mobility attributes
to proxies, and how the get expression returns a proxy’s current binding.
In Figure 3.13, L defines the semantics of sequence (;) and the semantics of an RPC call,
which we denote p.f . Let E = e0 , e1 , · · · , en−1 denote the, possibly empty, list of expressions
from which the actuals of a call are derived. Recall Definition 3.1.2: The component c is a
nonempty set of functions and their associated state. By definition, both p and pm must wrap
and export the same set of functions. In Figure 3.13, p.f denotes an RPC proxy-mediated
invocation of f ∈ c.
Primitive mobility attributes throw an exception when their starting location constraint
of two hosts or does not care where the component receives an invocation? What if a
Set mobility attributes provide just this flexibility: they generalize primitive mobility
attributes by lifting the start and target constraints from single hosts to nonempty sets
of hosts. A programmer can define these sets in terms of functions that are evaluated at
runtime.
By allowing the programmer to define the sets at runtime using functions, MAGE allows
migration, policies. For example, a programmer can define an attribute whose start set
3.4. Set Mobility Attributes 36
h(S, T ), σi ⇓ (S, T )
invocations that raise the start exception allow the programmer to write code that moves
In this, MAGE contrasts with other programming models that provide code mobility.
These other models either restrict a program to a small set of static migration policies,
or allow the programmer to express arbitrary migration policies, but at cost of writing
such policies themselves. For example, Java provides RMI, a form of RPC, and COD,
between static layout or the code migration policy that COD provides — “execute locally.”
Using sets for the start and target allows MAGE to introduce a continuum of constraints
from all hosts to a single host, i.e. from “don’t care” to a specified host. Indeed, set mobility
attributes are a strict superset of primitive mobility attributes. A mobility attribute whose
start set and target sets have only a single element is a primitive mobility attribute. For
this reason, unless otherwise specified, henceforth, we abbreviate set mobility attribute to
fs , ft ∈ H → Boolean.
Remark. For (S, T ) ∈ A, S is where the bound component must start; that is, find(idc ) ∈ S
must hold when c is invoked; t ∈ T is where the bound component may execute; that
precondition of primitive mobility attributes to a set of hosts relaxes the precondition. Under
3.4. Set Mobility Attributes 37
this definition of a mobility attribute, the “unspecified” or “don’t care” location is H and R
The redefinition of A changes every appearance of (s, t) in the grammar extensions and
evaluation rules defined in Section 3.3.1 must change to (S, T ) to reflect the change in the
definition of mobility attributes. In particular, the primitive evaluation rule for mobility
attributes in Figure 3.9 and the mobility attribute expressions and commands in Figure 3.12
As in Figure 3.13, the host language L that MAGE extends defines the semantics
of sequence (;), and the semantics of an RPC call, which we denote with p.f . E =
e0 , e1 , · · · , en−1 denotes the, possibly empty, list of expressions from which the actuals of a
call are derived. Thus, p.f denotes a proxy mediated invocation of f in the context of the
component idc names, meets the constraint imposed by the mobility attribute (S, T ). If
h 6∈ S, MAGE throws an exception, as the rule in Figure 3.17b specifies. If the rule in
Figure 3.17c applies, the component c moves, only if it is not already at a host in T , as
When we do not care where a component is, we simply find it. This use case motivates the
new attributes listed in Table 3.2. The d suffix refers to the fact that these attributes largely
“don’t care” where the component bound to them is found when invoked. For example,
CODd is that form of COD that does not care where the invoked component is, so long as
that component is not initially local (S = H − {l}) but becomes local and executes locally.
When a programmer simply wishes to invoke c and does not care where c executes,
At invocation, At execution,
Attribute find(idc ) ∈ S = find(idc ) ∈ T = Notes
CLE H H EIP with h = find(idc ) ∈ H
FMC H − {hy } {hy } MBE with hx ∈ H − {hy }, hy ∈ {hy }
CODd H − {l} {l}
REVd H − {r} {r}
RMCd H − {l, r} {r}
CLE does not express mobility, but, at the same time, makes sense only in the context of
mobile components, which can move and therefore must be found. Figure 3.18 depicts CLE.
Symmetrically, when a programmer does not care where c starts, so long as it moves to and
executes on the specified host hy ∈ H, we introduce find mobile code (FMC), which is MBE
when the host where the component receives an invocation does not matter, so long as that
location is not the target execution environment. CLE is a synonym for EIPd; FMC is a
RMCd differs from REVd in that RMCd requires l 6∈ S in addition to the requirement,
l hc
d
invocation
i c
result non-move
The d-attributes are clearly more flexible than primitive mobility attributes. This fact
raise the question: “Why not always use d-attributes?” We address this question next.
Consider an invocation on the component c, bound to an REV mobility attribute ({l}, {r})
that is already at the specified execution target r8 . At invocation, the attribute mis-
matches, since find(idc ) 6∈ first(REV) = {l}, but would match at execution, since find(idc ) ∈
8
Since set mobility attributes subsume primitive mobility attributes, we incarnate primitive mobility
attributes, here REV, in set form.
3.4. Set Mobility Attributes 40
The former approach emphasizes execution location: since c is already at r, let it execute;
who cares how or when c arrived at r? This approach coerces the REV attribute into an RPC
attribute. In general, mobility coercion handles a starting location mismatch by coercing the
mobility attribute into another attribute that has the same execution target and specifies a
starting location compatible with a component’s actual location if possible, thereby allowing
computation to proceed.
The latter approach allows mobility attributes to not only control a program’s layout,
programming model necessarily makes that model more complex. As assertions, mobility
attributes allow a programmer to write code that reacts to a program’s layout and enforces
layout invariants. For example, when a programmer has an invoker bind LPC to a component,
the programmer is asserting that the component should be local to that invoker, and, if not,
he wants to be informed. Further, the choice of mobility attribute could reflect lack of trust:
a programmer may not want to use COD and localize code from an untrusted server.
We proposed mobility coercion [8] and, in so doing, ruled out using mobility attributes
as assertions. This decision also muddied the definition of the application of mobility
attributes: when REV coerces to RPC, the actual mobile invocation pattern applied after
the computation completes was RPC, not REV. Thus, the attribute that was bound was not
applied and vice versa. This thesis makes the opposite choice: we preserve the semantics
coercion. The discovery of new categories of mobility attributes allows us to capture coercion
semantics as attributes!
So the short answer to the question — “why not always use d-attributes?” that we posed
above — is “to allow the usage of mobility attributes as assertions.” When the programmer
3.4. Set Mobility Attributes 41
does care about a component’s starting location, the programmer can use a primitive mobility
attribute or otherwise restrict S to a subset of H; when he does not, he can use a d-attribute.
However, the FMC derived d-attributes are all forms of MBE and specify movement; that
is, when find(idc ) = hx = hy , we have CLE, not FMC. Thus, they allow the programmer
to specify that a bound componenent must move. So, while they are more flexible than
primitive attributes, they still have a role as assertions. Rather than coerce d-attributes to
CLE generally, and lose their meaning as the assertion that a move must occur, we propose
Table 3.3 lists these attributes. The category mobility attribute is execute here (EH).
Each of the listed attributes is the corresponding d-attribute plus explicit coercion to CLE.
So, CODa is CODd with explicit coercion; REVa is derived from REVd; RMCa from RMCd;
To this point, we have focused on set mobility attributes that relax S, the set of valid
start locations. CLE is the exception: it relaxes both S and T by setting them both to H.
In general, setting T = Q ⊂ H is useful when one wishes to move the components in the
current working set to Q. In the next section, we turn our attention to mobility attributes
Static migration policies, while more flexible than static layout, limit a programmer’s ability
to write code that adapts to its environment, such as to take advantage of new resources
or make do with fewer. To demonstrate the semantics of MAGE’s support for dynamic
3.4. Set Mobility Attributes 42
migration policies, we abstractly redefine the Itinerary mobility attribute first introduced
in Chapter 4.
For any set X, we can define an indicator or characteristic function that indicates whether
an element is a member of subset Y of X [111, 86]. Here, we focus on target sets T that
change over time. The indicator functions, fs and ft , that we introduced in Definition 3.4.1
true when 0 ≤ i < n ∧ h = itinerary[i++]
∀h ∈ H, ft (h) = (3.1)
false otherwise
MAGE defines the target set T of its default Itinerary in terms of its indicator
function ft (h) as shown in Equation 3.1. An Itinerary attribute has an n length array of
advances the index i into itinerary. Note that ft has side-effects, since it depends on
the persistence of the index i which counts the invocations of ft . Figure 4.8, in Chapter 4,
depicts the itinerary of c across three invocations, after having been bound to an Itinerary
mobility attribute can also naturally capture the expressivity of dynamic S. Consider this
use case: the programmer who bound Itinerary to c wishes exclusive control over the
previous host in the itinerary. Equation 3.2 defines an fs that accomplishes just this task:
at the ith invocation, it restricts c’s starting location to the target of the i − 1th invocation,
true when 0 = i ∧ h = s
∀h ∈ H, fs (h) = true when 0 < i < n ∧ h = itinerary[i − 1] (3.2)
false otherwise
9
In fact, MAGE’s Java implementation defines S and T in terms of their indicator functions fs and ft ,
which simply return S and T when they are static and we suspect that doing so will be convenient in other
languages as well.
3.5. Mobility Attribute Operators 43
As we have seen, mobility attributes can express complex migration policies. To mitigate
this complexity, MAGE allows programmers to compose mobility attributes and reuse their
attribute with Evacuate — a mobility attribute that moves components off systems that
are going to be taken down for maintenance — to make a mobility attribute that selects
from among those least loaded systems that will remain online.
Since mobility attributes are pairs of sets, we can use set operations to compose them.
When Tx specifies systems with light CPU load and Ty contains those systems that have a
certain resource, like a DBMS, z is the mobility attribute whose policy is “execute on lightly
For convenience, MAGE defines operators to directly compose mobility attributes. Set
operations are not enough, because a programmer may wish to compose two attributes by
relaxing the start sets via union, while taking one target and discarding the other. For this
purpose, we define two operators in Equation 3.3: the C operator simply returns its left
xCy =x
xBy =y (3.3)
∀(Sa , Ta ), (Sb , Tb ) ∈ A,
O ∈ {∪, ∩, C, B},
Equation 3.4 defines the binary operators one can use to compose mobility attributes.
To round out its operators, MAGE also lifts set complement to mobility attributes:
∀(Sa , Ta ), (Sb , Tb ) ∈ A,
!S (Sa , Ta ) = (!Sa , Ta )
runtime, the complement of a set than the set itself. For example, say a particular host h
is going off-line. After h goes off-line, H will reflect that fact, but, in the meantime, valid
hosts are !{h}10 . Also, the addition of complement allows MAGE to define the set difference
To build intuition about this operators, observe that the C and B operators override one
of the operands, ∪ acts to relax the constraints to which it is applied, while ∩ tightens the
MAGE makes these operators available to programs by again extending L’s expression
grammar, as Figure 3.19 depicts. Figure 3.20 defines the operational semantics of these
operators.
To this point, we have considered only client-side mobility attributes. Here, we apply the
e ::= L expressions
| e oS oT e for oS , oT ∈ {∪, ∩, C, B}
| !ST e
| !S e
| !T e
may play both roles — client and server — even simultaneously, over the runtime of an
application. Clients, as invokers, define an application’s working set and are often active at
different times, have different resource needs, and therefore apply different layout policies to
a shared server component. Client-side mobility attributes allow different clients to bind
different attributes to their view of the same server component, and thereby naturally meet
this need.
However, when a development project has multiple teams that produce loosely coupled
code or a code base is sufficiently large, the authors of a component may know more about
that component’s needs when it is invoked as a server than the authors of its clients. To
execute correctly, a component, in the server role, may require hosts that have a particular
resource, such as a spectrometer. Even when the clients do, or should, know a server
When a component’s clients can agree on a shared policy, server-side mobility attributes
allow programmers to bind a single attribute once in the context of the component, instead
of forcing developers to bind clones of an attribute to each client’s proxy of that server.
Additionally, server-side mobility attributes can specify security policies that restrict where
l r
mobility
attribute
d
invocation
i c
In this section, we present server-side mobility attributes that bind directly to a com-
ponent. Figure 3.21 depicts server-side binding of mobility attributes. When a client-side
mobility attribute also mediates an invocation, its target set T is part of the invocation
message. S does not appear in an invocation message, as its check is enforced at the client
and is thus superfluous at the server. MAGE composes T with the component mobility
attribute’s target set Tc using the operators defined in Section 3.5. Note that find(idc ) ∈ S
Remark. Unlike client-side mobility attributes, component mobility attributes do not specify
a set of valid starting hosts Sc for a bound component. Three observations motivate this
difference:
1. Invokers use the S member of a client mobility attribute for assertions; that is, when
the invoker, which can then react to and correct the problem. The component c can
end up on a host that is undesirable from the point of view of an invoker, because that
attribute mediates all calls to c, so it can prevent c from ever moving to undesirable
hosts. For instance, a programmer can define the CMA Tc = {acceptable targets} and
bind it to c using ∩ as the mobility attribute operator. Then, no matter what T the
client sends, the CMA will cut it down to its acceptable subset T ∩ Tc .
then all invocations will cause c to throw an exception, before ever moving or executing.
provides no way to recover. Therefore, there is a single sensible value for Sc , namely
H. Since there is only one sensible value, we implicitly set Sc to H, which obviates
3. Again assume CMA includes Sc . There is no natural recipient for exceptions thrown
when find(idc ) 6∈ Sc . This is because of the disconnect between the server-side thread
that bound a CMA to c and threads that invoke c. The server thread cannot reasonably
resolve exceptions raised by the activity of the invoking threads, since it knows nothing
about the invoker’s context. If, on the other hand, we send the exception to the
invoker, the client, who does not know or bind Sc , clearly disagrees since find(idc ) ∈ S
or the invocation would not have reached c, and, in any case, can do nothing about
So an Sc starting location check does nothing useful; it only creates new ways to shoot
Here, we present the minimal set of rules necessary to define component mobility attributes,
as a delta against the rules already presented. The rules below are either new or extend
existing rules. Let O = {∪, ∩, C, B, !} ∪ {} be the operators that compose a client’s mobility
attribute with a component mobility attribute in the server’s context. To denote a null
binding, ∈ O.
3.6. Component Mobility Attributes 48
Figure 3.22 extends the grammar in Figure 3.19 which, in turn, extends the grammar
defined in Figure 3.8. It adds operators as terminals and a three parameter bind, where
the new parameter is a mobility attribute operator. Figure 3.23 adds these operators as a
primitives and associates an operator and component mobility attribute with the component
c.
Figure 3.24 makes clear why we need primitive operators: we need to bind them to
components along with the component mobility attribute T 0 to know how to compose T
with the incoming Ti that the invoker specified. Here, c is not the proxy pc , it is the address
of a component.
Figure 3.25 specifies how to compose the client mobility attribute’s target with the
component’s attribute. Figure 3.25a handles the case where no CMA is bound to c. Whether
do not repeat that invocation rule here. The move command semantics are unchanged.
the client-side mobility attribute’s T to a hint that the component is free to ignore. A
server component is already free to ignore client invocations and unpublish itself, so giving
it control over its mobility does little to change the power relation between it and its clients.
When c executes on t ∈ Tc ∧ t 6∈ T , the invoker i gets its reply from an unexpected source,
3.7 Summary
In this chapter, we have seen how mobility attributes arose from the analytical discovery
that existing distributed programming paradigms that integrate invocation and mobility
that pair of hosts to a pair of sets of hosts to form set mobility attributes and showed
how these attributes are usefully more powerful than primitive mobility attributes: they
obviate coercion, and they facilitate both the composition of attributes and the definition of
described how to dynamically define set mobility attributes using their indicator functions,
and provided three examples drawn from MAGE’s library of mobility attributes to illustrate
the point. We introduced operators on mobility attributes that allow one to compose new
mobility attributes out of other, simpler attributes. Finally, we presented server-side mobility
attributes that allow the authors of components, and not just their users, input into where
Chapter 4
Thomas Carlyle
Sartor Resartus, 1834
Email is classically deployed under the client server paradigm. External mail arrives at
the server, which delivers to its clients upon request. Unfortunately, a client often does not
want much of the mail the server delivers to it. When all of the mail server’s clients agree on
what constitutes spam, the server can perform the requisite filtering on their behalf. However,
the clients may not agree: for instance, I may wish to receive emails from Orbitz.com,
while you may not. Moreover, my filtering needs may change over time: once I finalize my
travel itinerary, I may no longer wish to see emails from Orbitz.com. Today’s dominant
solution to this problem is to use message passing. This wastes network resources: it requires
Mobile code can optimize and load-balance resource access via collocation. It can also
customize behaviour. Given mobility, I can dispatch a personalized filter to the server. In
so doing, I trade local work and network utilization for work at the server. Stamos et al.
51
proposed remote evaluation (REV)1 to solve such problems [93]. REV occurs when a client
class that implements EmailFilter. All distributed systems, including MAGE, comprise
a registry service that tracks the location of resources, such as mobile objects. Publishing
is the act of binding a name to a resource in the registry; it makes the resource available
within the system. On lines 2–3, the programmer publishes efi by binding it to the name
and returns ef, a proxy to efi. On line 4, the programmer creates an REV attribute whose
line 5. The invocation of getMail() at line 6 causes efi to move to mailServer where
Mobility attributes not only change the location of a mobile object, they also make
assertions about where that mobile object should be when they are applied. In Listing 4.1,
the REV attribute asserts that efi, to whose proxy the attribute is bound, is initially local.
efi is no longer local, if the programmer wishes to use efi in place at mailServer,
she must replace ef’s binding to an REV attribute with a remote procedure call, or RPC,
attribute, as shown on lines 7–8. If a method were called on ef while it was still bound to
1
REV was first introduced in Section 2.1 and is discussed in detail in Section 3.2.
4.1. Primitives 52
invocation
i p o
result
an REV object, but after efi had already moved, the call would inform the programmer of
efi to execute at mailServer and did not care where efi was when it received the call,
she could have chosen to bind REVa, which expresses exactly this policy: it specifies a target,
but imposes no restrictions on mobile object’s location when that object receives a call. For
more details about REVa and related attributes, please refer to Section 3.4.3.
This example introduces three mobility attributes — RPC, REV, and REVa, the mobile
class EmailFilterImpl, a proxy to an instance of that class, and associates them with
4.1 Primitives
To ease deployment, MAGE is implemented as a library. Built on Java, MAGE provides all
the usual Java statements and expressions, as well as Java’s panoply of types, such as int,
char, and plain old Java objects (POJOs). To Java’s types, MAGE adds mobile objects,
Figure 4.1 describes the relation between a proxy and a remote object. A remote object is an
object that can publish itself to a name service and receive remote invocations. An instance
of the proxy design pattern [32], a proxy marshals an invocation, including its parameters,
In RMI, remote objects cannot be marshaled; instead, they are replaced with proxies.
4.1. Primitives 53
POJOs that implement Java’s Serializable interface can be marshaled, but cannot be
invoked remotely. MAGE mobile objects are a modified version of RMI’s remote objects
that can both receive remote invocations and be marshaled. MAGE moves all the heap
objects reachable from the fields of a mobile object. It does not move the stack, registers, or
heap reachable from either the stack or registers of a thread executing within that mobile
object. Thus, MAGE supports weak mobility [16]. In RMI, a remote class implements Java’s
A MAGE proxy is a Java RMI proxy that supports the binding operations and contains a
MAGE is not unique in providing mobile objects; there are many such systems. The mobility
pair of sets — S, the set of hosts at which a bound object can receive an invocation, and T,
A mobility attribute binds to a mobile object and its proxies. By binding to the proxies
of a mobile object as well as directly to the mobile object itself, MAGE allows different
invokers to apply different placement policies to their interactions with the mobile object,
without incurring the cost of competing over directly binding to the mobile object itself.
class, shown in Listing 4.2. The starts method defines a mobile object’s start set S; it is an
assertion about where a mobile object should be when the mobility attribute is applied. For
4.1. Primitives 54
an application whose objects can move, such assertions are a useful control mechanism. When
this assertion is not met, MAGE throws StartException. The targets determines
where the object should move before executing; that is, it defines T. Thus, this method is
the principal means by which a MAGE application adapts to its environment. As we will see
in Section 4.3.3, a mobility attribute can interact with its environment to select a suitable
Programmers can use the Method parameter in both starts and targets to tie a
mobility attribute’s behavior to the method invoked, rather than the set of methods defined
by an interface. Usually a programmer uses the Method parameter to ignore all but a subset
of the methods in an interface thus allowing method granular binding of mobility attributes.
Listing 4.3 illustrates how one can use the Method parameter of starts and targets to
class in MAGE’s ml (for “MAGE library”) package which contains all mobility attributes that
MAGE defines. Its constructor takes the method instance to which to bind and delegates
the actual implementation of the target selection logic to its subclasses via the abstract
targets method. The if-else forwards the call to targets if the call was made on the
bound method, otherwise it converts the call into a local procedure call. The if-else can
be expanded to select any partition of an interface’s methods, not just a single method as
shown here.
4.2. Mobility Attribute Class Hierarchy 55
The MAGE programming model rests upon mobility attributes. In this section, we present
the Java class library of predefined mobility attributes MAGE provides. Figure 4.2 presents
a high-level overview of the class hierarchy of MAGE’s library of mobility attributes. The
triangles represent subtrees, which we address in turn with dedicated figures below. Static
attributes are those that implement a migration policy that is independent of the runtime
environment of the program; while dynamic attributes are those that express migration
Recall that H is the set of hosts that comprise a MAGE system. For an invoker, l ∈ H
is the invoker’s local host and R = H − {l} is the set of hosts remote to that invoker. In the
figures discussed in the section, r ∈ R and, in set theoretic terms, Set<String> represents
the type 2H .
Figure 4.3 depicts primitive attributes, described in Section 3.3, implemented as single-
ton set mobility attributes. The base class MobilityAttribute defines the starts
set of valid starting locations S and an immutable set of valid targets T, then overrides
4.2. Mobility Attribute Class Hierarchy 56
These attributes do not vary their behavior with resource utilization and layout, but
rather unconditionally apply their starting host test and move (or not) their bound object.
Although a MAGE application can still use these attributes to dynamically adapt to its
environment via judicious binding and rebinding, doing so intersperses logic to manage
the application’s layout with the application’s domain-specific logic. Fortunately, MAGE
provides an alternative — dynamic mobility attributes that both isolate layout logic and
react to their environment. We describe how to use these attributes in Section 4.3.3.
EIP instances are attributes that do not move an object to which they are bound. Here,
the two subclasses are assertions. An LPC attribute differs from a local procedure call in
that it asserts that a mobile object bound to it is local; an RPC attribute differs from a
remote procedure call in that it asserts that a mobile object to it is at the remote host r. If
MBE instances, in contrast, are attributes that must move the object to which they are
bound, if that object meets their starting host condition. The COD attribute realizes code
on demand [16] and requires that a bound object start at r and move to the invoker’s host
before executing; REV requires that a bound object start at invoker’s host and move to
the remote target r before executing. The remote move code (RMC) attribute requires the
bound object to move between two distinct hosts remote to the invoker. We introduced and
A programmer can either instantiate and bind an attribute MAGE provides, such as
one in Figure 4.3, or define their own. To do that, the programmer need only extend an
Listing 4.4 contains MAGE’s definition of the RPC attribute, which we used in Listing 4.1,
the example that opens this chapter. RPC’s constructor checks that the passed in target
Listing 4.5 gives their definitions. EIP instances simply return the field, a set of strings,
Figure 4.4 depicts d-attributes, described in Section 3.4.2. The d-attributes differ from the
primitive attributes in that they relax the starting location requirement embodied by S.
The FMC subclasses still require movement to occur. The a-attributes address this issue: a
4.2. Mobility Attribute Class Hierarchy 59
programmer uses them when she does not care where a component starts out or whether
it moves, just so long as it executes on the target. These attributes effectively ignore S by
setting it to H, and are semantically equivalent to explicitly moving the invoked component
to the execution target prior to its execution. Figure 4.5 depicts the a-attributes, which
Figure 4.6 depicts the StaticPartition attribute. Unlike primitive, d-, and a-
attributes, this static attribute is not derived from distributed invocation paradigms. The
The mobility attributes presented so far immutably define their S and T sets. In Figure 4.7,
When building a distributed application from mobile objects, programmers often write code
to control the route a mobile object takes while moving through the network. So often, in
fact, that such code has been identified as the itinerary pattern [101]. MAGE represents the
mobile object through a proxy bound to Itinerary advances the index i into itinerary.
Itinerary binds to all methods in a MAGE interface, and thus ignores its Method
parameter. Figure 4.8 depicts the itinerary of c, starting from s, across three invocations,
after having been bound to an Itinerary mobility attribute whose list is (x, y, z). If
4.3. Dynamic Mobility Attributes 61
s x y z
d0 d1 d2
inv
2
on
oc
ati
at
oc
ion
inv
inv
oca
1
tion
0
desired, a programmer can define Itinerary instances whose lists contain repetitions, such
as (x, x, y, z, z).
Itinerary contains a list of sets of hosts. When this is a list of singletons, the attribute
realizes a standard itinerary. Since Itinerary sets S = H, it does not care where its
component is before application, and is useful in the context of a component that an invoker
shares with other invokers and therefore does not know where the component may be prior to
an invocation. When a component is not shared and the programmer wants complete control
over the component’s itinerary, she can use FixedItinerary which defines starts to
ItineraryMA takes an array of mobility attributes, through which it steps to form the
itinerary. Since any one of its constituent mobility attributes could be dynamic, we have
included it here.
A system built from mobile components is susceptible to the problem of moving its compo-
nents so frequently that the cost of that movement outweighs the benefit of the resulting
layout. When this happens, movement impedes useful work and the time-to-completion
of services provided by the system suffers. By analogy to page thrashing [23], we call
4.3. Dynamic Mobility Attributes 63
b
COD COD
a c
COD
x move y x y
b b move
a invocation
c a invocation c
x y x y
b move a b a
invocation c c
this problem migration thrashing. In the limit, migration thrashing leads to a form of
livelock [117] in which the system does nothing but move its components.
Figure 4.9 depicts a scenario that can lead to migration thrashing. The mobile objects
a, b, c ∈ C are interdependent: they represent computations and associated state that should
be collocated. Their pairwise dependency manifests itself as a cycle in the call graph. The
programmer saw their pairwise interdependence, but not the cycle, and incorrectly bound
Figure 4.10 depicts what happens when COD applies and the invocation order a →
b.f, c → a.f , and b → c.f occurs. In Figure 4.10d, the mobile objects have swapped hosts
but are otherwise in the same configuration. As long as these mobile objects are scheduled
MAGE cannot prevent migration trashing in general, but it does allow a programmer to
write concise policies that can prevent specific instances of it. For instance, if the programmer
had noticed the cycle in the call graph that links a, b and c, he could have have bound the
An instance of MajorityRules, Listing 4.7, tracks the location of the set of components
passed to its constructor. Its targets method finds each component, then returns that
subset of hosts with the highest count: thus, its target is a host on which a majority of those
components resides. Thus, its application causes a component bound to it to move the host
If the programmer had bound MajorityRules to the proxies a, b and c use to commu-
nicate with each other instead of COD, migration trashing would not have occurred. When a
invokes b.f in Figure 4.10a, b would remain on host y, since a majority of the set {a, b, c}
already resides on y. Then c’s invocation of a.f would cause a to join b and c on y, where
all three mobile objects would remain for the duration of their intercommunication.
whose policy causes components to which it is bound to collocate with the component in its
singleton set. When an instance of MajorityRules both tracks and is bound to the same
their program should occur and thus how they should combine message passing and code
migration to accomplish a task. To this end, MAGE must be resource aware [85] and provide
programmers a source of system state that they can query when defining a mobile object
A great deal of work has gone into load information management systems [71]. MAGE
stands on the shoulders of giants and leverages this work: MAGE provides its mobility
attributes a generic interface to such systems via its resource manager service. The MAGE
resource manager maps strings to arbitrary objects that contain resource data. This service
4.3. Dynamic Mobility Attributes 66
is globally accessible within the address space of a MAGE host. Since each MAGE host has
leaves the population of the resource manager to the application. To use the MAGE resource
manager, a programmer must first populate the service with information about a resource of
interest. For example, the programmer could write code that polls Java’s JMX API [68] to
learn a system’s CPU load, then stores it in the local resource manager. MAGE does not
synchronize the data stored in resource managers on different hosts. To get information from
remote resource managers, the programmer must write code to query the remote resource
managers and add the results to the local resource manager. Since it is the programmer’s
responsibility to populate the MAGE resource manager, the freshness of the data is entirely
delegated to the programmer. Section 6.3.7 in Chapter 6 discusses the realization of this
Threshold and its subclasses make use of the MAGE resource manager through their
is that subclass of Threshold that binds key to “CPU;” while ComponentCount binds
Threshold’s key to “count.” Invokers that employ ComponentCount cause the target
Listing 4.7 in Chapter 4 rather expensively finds its component set upon each invocation.
Listing 4.8 depicts componentCount, a method an application could use to update the
MAGE resource manager with component counts by host. Implicitly, if the map contains no
mapping for a host, that host’s count is zero. The name parameter allows an application to
application would need to run componentCount periodically for each set of components on
each host. The targets method of MajorityRules would then query the local resource
Listing 4.9 defines CPULoad, a mobility attribute that relies on the MAGE resource
through rms, a field initialized in its constructor. This attribute defines the policy of
4.4. Operations 67
Listing 4.8: Populating the MAGE Resource Manager with Resident Component Counts
1 protected void
2 componentCount(String name, Set<String> components) {
3 Map<String,Integer> countByHost =
4 new HashMap<String,Integer>();
5 String h;
6 Integer t;
7 for (String c : components) {
8 h = MageRegistryServer.find(c);
9 t = countByHost.get(h);
10 if (t == null)
11 countByHost.put(h, 1);
12 else
13 countByHost.put(h, t+1);
14 }
15 //overwrite previous binding
16 ResourceManagerServer.put(name, countByHost);
17 }
executing on lightly loaded systems. Here, we assume that the application periodically
updates the map to which “cpuload” is bound. This map binds host names to the output of
the UNIX uptime command, which reports the length of the run queue for the past 1, 5,
and 15 minutes. In Listing 4.9, the targets method queries the MAGE resource service to
discover the CPU load of each host. The index field selects which of the three load averages
to use in the comparison. CPULoad then builds a set that contains those hosts whose selected
load average does not exceed the programmer-specified threshold threshold, passed into
4.4 Operations
MAGE provides four families of operators over its primitives — find, composition operators,
MageRegistryServer defines these methods. The name parameter must have the RMI
In this format, object is the mobile object’s name and host:port is that object’s origin
4.4. Operations 69
server, the server on which the mobile object was first bound to a registry using the first
form of the bind method defined in Listing 4.18. Each mobile object’s name must be unique
constraint.
The find method returns the current location of the named mobile object as a string
invocation. The lookup method returns a proxy to the named mobile object. Each distinct
invoker of a mobile object must call this method before it can invoke operations on that
mobile object.
A programmer must statically know a mobile object’s origin server host, in order to
download a proxy from the registry at the well-known port 1099. Embedded in the proxy is
Mobility attributes are Java classes, so their methods are Turing-complete. Further, mobility
and inheritance. These allow us to compose attributes in arbitrary ways, but are usually
more powerful than is necessary. We may just want to complement an attribute’s target.
We may want to select a target from the union or the intersection of the two target sets
returned by application of two distinct attributes. Listing 4.11 illustrates the boilerplate the
programmer would have to write to intersect the start sets while returning the union of the
Mobility attribute operators obviate such boilerplate. Mobility attributes define sets —
S, the set of valid locations at which a bound object can receive an invocation and T, the
target set of hosts at which we want a bound object to execute. Since mobility attributes
are essentially sets, we can apply standard set theoretic operators to them. Conceptually,
mobility attribute operators leverage this fact to realize a domain-specific language for
elegantly combining attributes. Listing 4.12 contains MAGE’s Operator class which
Because a mobility attribute is a pair of sets, we must apply two operators, one for
each set, when composing two mobility attributes. The LEFT and RIGHT operators just
return either their left or right operand. These two operators are useful when you want to
compose one of S or T, while ignoring the other. For example, for the two mobility attributes
a = (S, T ) and b = (S 0 , T 0 ), (a.S LEFT b.S 0 , a.T RIGHT b.T 0 ) = (S, T 0 ), while (a.S RIGHT
b.S 0 , a.T RIGHT b.T 0 = (S 0 , T 0 ) = b. For more detail, refer to Section 3.5 which defines these
4.4. Operations 71
Listing 4.13 shows the mobility attribute operations that MobilityAttribute defines.
Rather than create a method for each of the possible combinations of operators applied
to each of S and T , MAGE provides the combine method, shown in Listing 4.14. The
programmer calls this method on the left operand, passes in the right operator, and the
appropriate operators in opS and opT. The combine method returns a mobility attribute
instance whose starts method combines the starts methods of its operands using the
opS and the targets methods using opT. For the mobility attributes m0 , m1 , the union of
their S sets combined with the intersection of their T sets, denoted m0 ∪S ∩T m1 , becomes
attributes defined earlier in Listing 4.11. The combine method returns redux, a new
mobility attribute whose starts method returns the intersection of the results of the
starts methods of o1 and o2 and whose targets method returns the union of the results
Listing 4.16 illustrates how a programmer might use mobility attribute operators to
combine mobility attributes. FarmerImpl is a class that gathers and parses the results of
Ebay auctions, before storing them in a database. The Bandwidth attribute, instantiated
on line 2, is a subclass of Threshold specialized to return as targets all systems that are con-
suming less bandwidth than the threshold passed into its constructor. We defined CPULoad
in Section 4.3.3 to return systems whose CPU load falls below some user-defined threshold
and discussed the implementation of its targets(Method m) method in Listing 4.9. The
4.4. Operations 73
programmer wants farmer to run on lightly loaded systems that also have at least 1MB of
available network bandwidth. On lines 3–4, the programmer intersects the target sets of the
CPULoad and Bandwidth attributes to capture this policy in llBandwidth, then applies
StaticPartition becomes
partition.
Figure 4.11: Mobility Attribute Operator Tree
Listing 4.17 shows an extended
erator tree shown in Figure 4.11. In the example, we know that a particular system is going
down for maintenance. To build a mobility attribute whose target avoids that system, we
to either run on relatively unloaded systems (1 minute load average less than 2.0) or, to
minimize network traffic, on systems where a majority of the components c0-3 are executing.
MAGE borrows the first form of its binding operator from RMI. Defined in the class
MageRegistryServer, this form binds the mobile object o to the identifier name, thereby
publishing o so that it can receive remote invocations. After o has bound itself to name,
clients typically contact the MAGE registry and use name to acquire a proxy to o. This
4.4. Operations 74
operator returns a proxy because even in a server context no object should have a direct
reference to a mobile object, to avoid inadvertently cloning the mobile object and its
Defined by the MageMobile interface, the second form binds mobility attributes to a
proxy, so that the attribute can intercept calls mediated by that proxy, as described above
in Section 4.1.3.
Defined by MageMobileObject, the third form of the bind operator ties a mobility
attribute directly to a mobile object, not to a proxy to that mobile object. While a mobility
attribute bound to a proxy intercepts a call in the invoker’s context, a mobility attribute
directly bound to a mobile object intercepts a call in that mobile object’s context, at the
server on which the mobile object is residing when it receives the call.
In this context, the start set S, and the starts method that defines it, make no sense.
First, only invocations that meet the invoker’s starting location constraint are delivered.
4.4. Operations 75
Second, the mobile object’s current host must always be in the start set of the attribute
directly bound to it, because, if not, every attempt to invoke the mobile object would throw
StartException and the mobile object would never move or execute. Contrast this with a
proxy-mediated invocation, where the invoker can bind a different, more permissive, attribute
Since a mobile object’s current location must always be in the start set of an attribute bound
directly to that mobile object, the start set S of directly bound attributes is superfluous and
ignored.
The set of targets to which to move the mobile object directly bound to an attribute,
is another matter. In MAGE, each time a mobile object is invoked, two targets sets are
potentially generated — Ti from the invoker’s attribute bound to its proxy and Td from
the attribute directly bound to the invoked mobile object. Rather than simply ignore
the invoker’s target set Ti , MAGE reuses its attribute composition operators to allow the
programmer to decide whether and how to combine Td and Ti . Allowing the programmer
attribute to a mobile object can always select Operator.LEFT, thereby causing MAGE to
ignore Ti .
With this groundwork laid, we can now unpack and explain this final bind operator’s
signature. Called on an instance of a mobile object, this bind operator takes a mobility
attribute and an mobility attribute composition operator. After the binding, MAGE
intercepts invocations on the mobile object in the context of server on which the mobile
object is currently residing, generates the target set of the bound mobility attribute Td ,
extracts the client’s target set Ti from the incoming invocation, then uses the bound operator
to combine the two target sets. If the mobile object’s current host is in Td Op Ti , the mobile
and component mobility attributes, i.e. attributes directly bound to a mobile object, are
Listing 4.19 illustrates the utility of binding mobility attributes directly to mobile objects.
Partition is an attribute that partitions H, the set of hosts, into “good” and “bad” subsets,
4.4. Operations 76
Ti ∩ Td
move1
call:Ti move0
o
”good” = Td ”bad”
as shown in Figure 4.12. For instance, a programmer can instantiate a Partition attribute
that maps hosts that are going down for maintenance to the “bad” set and those that will
not to Td , the “good” set. On line 1, Partition’s constructor takes the good subset and
instantiates p. Let Ti be the target set of the invoker’s mobility attribute, embedded in the
invocation. On line 3, we bind p directly to the mobile object o whose execution we wish
to restrict to hosts in the “good” partition, using the intersection operation. Subsequently,
no matter what Ti is, MAGE restricts o’s executions to the intersection of Td and Ti , that
subset of Ti that falls within “good” partition of hosts. In Figure 4.12, move0 is to a host not
in the intersection, while move1 is. If the intersection is empty, MAGE informs the invoker
4.4.4 Invocation
MAGE proxies are always bound to a mobility attribute. An unbound attribute is implicitly
bound to an instance of CLE, which instructs MAGE to execute the target mobile object in
place, wherever it is. Thus, an invocation on a MAGE proxy first applies the bound attribute
to discover its S and T sets. MAGE then finds the component to determine whether its
MAGE builds and sends the invocation, along with T , to the target component’s current
location.
The receiving host first checks whether a mobility attribute is directly bound to the
target mobile object. If a mobility attribute is directly bound to the target mobile object,
the receiving host applies that attribute to produce T 0 , then generates Ts = T 0 Op T , where
T is the client’s target set and Op is the operator used in the call to the third form of the
bind method above. If no mobility attribute is directly bound to the mobile object, Ts = T .
If the receiving host is itself in Ts , it simply executes the target component. Otherwise, it
adds the target component to the invocation which it forwards to some t ∈ Ts . Conceptually,
4.5 Summary
In this chapter, we have explored the MAGE programming model. We have discussed its
primitives — mobile objects, proxies, and mobility attributes — and its families of operations
over those primitives — find, mobility attribute operators, bind, and invocation.
78
Chapter 5
Location Services
A distributed system that supports mobile components, such as MAGE, must send
service finds resources, such as a mobile component. Dynamic location services include
broadcasts, directories, and forwarding pointers. These approaches differ in their lookup
and maintenance costs, and their degree of fault tolerance. Forwarding pointers [30] trade
lookup for maintenance cost. In this chapter, we show that, for mobile resources, forwarding
pointers require fewer messages on average than a centralized directory. Thus, to minimize
the number of messages (Section 5.2) and to avoid a bottleneck and a single point of failure,
In short, this chapter first juxtaposes forwarding pointers and a centralized directory,
then presents and contrasts invocation protocols built using forwarding pointers; it describes
5.1 Background
Definition 5.1.1. A directory maps entities, some of which either are or may become
remote, to locations.
Remark. An execution environment (host) necessarily knows about local entities. The
constraint that some entities must be actually or potentially remote distinguishes a directory
uses directories, it can have 1 to n directories. When there are n directories, every system
within the network is a directory. A common directory service employs a single, centralized
directory (D). Under D, whenever a mobile component moves, it updates its binding at
the designated directory. Alternately, we can partition the network or the resources and
employ one directory per partition. Each partition, however, reduces to a single, centralized
Under the forwarding pointer location service (FP), every host in the distributed system
is a directory, albeit one whose binding for a mobile component may be stale or that may not
even have a binding for a given mobile component. Each mobile component starts at some
host, which we call its origin. Whenever it moves, it updates its binding in the directory of
the host it is leaving to point to the host to which it is moving. This entry is a forwarding
pointer since it does not necessarily indicate where the mobile component is, but rather that
To statically bootstrap D, the application must statically know the name of the directory.
To statically bootstrap FP, the application must statically know the origin of each mobile
component, although this burden can be reduced by starting all mobile components at the
same host. If there is a single, shared origin, then FP starts out as D. By default, Java uses
the former method to statically bootstrap RMI: For each remote object capable of receiving
and executing incoming, remote calls, the programmer must statically specify the server on
5.1. Background 80
c
nd
Find Fi
c Ask h1 h3
k
As
h2 h3
c c
Find c
i c
c is here
which that remote object resides in order to download a proxy to the remote object. The
To dynamically bootstrap D, one must resort to broadcast — either the directory must
broadcast its identity to all hosts or each host must broadcast to discover the directory. FP,
in contrast, needs only broadcast until it finds any host that has a forwarding pointer for a
Figure 5.1 illustrates how a lookup proceeds under FP. Let C be the set of components;
let H be the set of hosts and h0 , h1 , h2 , h3 ∈ H. Assume that c’s origin is statically known.
For i, c ∈ C, i is searching for c. The invoker i first contacts h0 , c’s origin server which refers
i to h1 , which was c’s destination when c left h0 . Then i contacts h1 which refers i to h3
origin server for all mobile components, as components move and lookups occur over time, a
system using FP reduces its dependency on that origin server. As a result, D has a single
point of failure while, after sufficient movement by mobile objects, FP does not1 . FP, on
the other hand, is more fault-sensitive in that the failure of any host on the path from an
1
Quantifying “sufficient movement,” either by using the Poisson model we describe in Section 5.2 or an
application-specific model, is future work.
5.1. Background 81
invoker to an object would prevent that invoker from reaching the object. For clarity, the
Of course, we could augment D to use replication or elect a new directory or even fall
back to lookup via broadcast. We could use multiple directories, each responsible for a
partition of hosts and thereby reduce the number of hosts affected by a directory failure.
Replication increases and complicates the cost of updating the information stored in the
directory service. Partitioning the network among a set of directories recreates the problem
of a single centralized directory within the partition. Thus, D embodies core functionality
that these variants either layer upon or reduce to. Therefore, we take D as our point of
departure and defer these variants and their analogs for FP to future work.
Initially, D appears superior to FP. For a system with n = |H| hosts, D requires Θ(|C|)
space in the worst case. Under FP, all nodes are directories, so FP requires O(n|C|) space
in the worst case. In the worst case, D requires a single lookup message. In FP, the
number of lookup messages is the length of a chain of forwarding pointers, or the staleness
of the information in the first pointer, and depends on the itinerary of the tracked mobile
Figure 5.2 captures these differences for three location services — broadcast (B), D, and
FP. The X-axis is the worst case number of directories in a network. The Y-axis is the worst
case number of lookup messages to locate a resource. Again, while that resource is mobile,
we assume that it does not move during lookup. We include B as an additional point of
reference.
Another way to view the Y-axis is as a measure of the worst case staleness of a particular
directory’s information. Zero on the Y-axis means no messages were sent to the directory
service to find the target resource. This occurs when the searcher and target are collocated
B does not require a directory. Thus, B appears on the Y-axis. A broadcast method
that sends a single message to each node in a network requires the broadcaster to know
every destination. Broadcasting via flooding, in which every node that does not have the
queried resource resends the query on every link on which it has not already received a query,
5.2. Directory vs. Forwarding Pointers: Message Cost 82
O(n2 ) ♦
B
...
n−1 FP
♦
worst case
lookup ...
messages
2
D
1 ♦
0
1 2 ... n
directories
does not have this requirement [97]. In the worst case, broadcasting via flooding requires
Thus far, it would appear that FP is a non-starter. Consider, however, the message cost of
keeping the information in the two location services current. Let m denote the number of
moves that the mobile resource made before the lookup under consideration. D requires m
update messages, while FP requires 0, because FP builds the cost of update into lookup.
Moreover, if the mobile resource returns to a host it already visited, the chain of forwarding
pointer is split into two, shorter chains, while the work to update D is unchanged.
To analyze the two location services in terms of their total message costs, we employ
the machinery of probability to model the movement of the target resource, so that we can
discover the expected length of the FP chain in terms of the number of expected moves of
the target resource. In so doing, we dispense with the assumption above that the target
link and host latency. More to the point, we can derive the time cost from messages.
When comparing the message cost of D against that of FP, there are two sources of
5.2. Directory vs. Forwarding Pointers: Message Cost 83
randomness — the movement of a target mobile component and the occurrence of searches
or invocations, since, in MAGE, searchers are invokers. We use the Poisson distribution in
Definition 5.2.1 to model these events [76, p57]. This distribution is continuous and requires
that the modeled events be independent. Since Z ⊂ R, the use of a continuous distribution
is more parsimonious: it does not impose the assumption that sample space be discrete.
Our events are the movements of mobile resources and searches for them. A computer
program creates, moves, and searches for these mobile objects, so movement and searches
and instead thinking in terms of any such program, the assumption of independence for
these two variables is, however, a reasonable first approximation of their behavior. Even in
the presence of a particular program, this model can serve to measure the degree to which
that program’s behavior is dependent by comparing the results of this model against the
e−λt (λt)k
P r(k) = (5.1)
k!
When k is the number of moves the mobile component c makes, Equation 5.2 gives the
e−λt (λt)0
P r(k = 0) = = e−λt (5.2)
0!
Recall that C is the set of components. Without loss of generality, let a searcher be
an invoker and I ⊆ C be the set of invokers. Let M be the number of moves the mobile
ourselves to a stream of invocations issued by a single invoker, so our model can incorporate
5.2. Directory vs. Forwarding Pointers: Message Cost 84
i D h0 h1 i h0 h1
find find
c race c race
starts starts
r0 r0
th th
0 0
ca r1 c ca r1 c
r2 c at h0
invoke invo
c ke c
r3 r3
cache effects. Both M and V are Poisson random variables. Then λm is the rate at which a
mobile component moves and λi is the rate at which an invoker begins its search protocol.
We consider M and V over the same period te , the period of the experiment.
The mobile component c ∈ C moves when it changes host. This definition does not
Let r be the rate at which an invoker sends messages and tr denote a network’s round trip
time (RTT). The variable tr is a parameter of the model. By fixing tr , we ignore variance in
1
RTT, such as congestion or link failure, in order to keep the model simple. If r > tr , the
invoker issues some messages before it knows the results of previous messages. Further, if
λm ≥ r, then mobile components are moving at least as fast as invokers are sending messages,
1
and invocations may never complete. Thus, we assume λm < r ≤ tr .
Both D and FP are subject to data races, since a mobile component may move at any
time. Figure 5.3a contains two races, one between r0 and r2 and the other between r1 and
r3 . Both races start when D receives “find c.” If r0 occurs before r2 , then i receives incorrect
information. Since r2 depends on r1 , it depends on the sending and receiving of two messages
— c itself from h0 to h1 and then the update from h1 to D. Together, these messages take
time greater than or equal to tr to propagate. If r3 loses its race with r1 , i’s invocation fails.
5.2. Directory vs. Forwarding Pointers: Message Cost 85
Event r3 depends on r0 , so its race too occurs in a period of time of duration at least tr .
In FP, there is no directory to update, so the two races in Figure 5.3b both involve r1
directly. If r1 occurs before ”find c” arrives at h0 , then c moves before the invoker is told
that c is on h0 , and i just follows another link in the chain of forwarding pointers. To i, this
case is indistinguishable from a longer chain. If r1 occurs after r0 but before r3 , then c has
the time until the find reply reaches and i and i’s invocation arrives at r3 to move, or RTT.
Therefore, the period of time during which these races can occur has duration greater
than tr . From Equation 5.2, the probability that a message wins the race with a mobile
component is e−λm tr , for tr = RTT, because this is the probability of 0 moves after a
successful find reply is sent and the message arrives. For simplicity and because our concern
is to compare D and FP, we do not model the time between events occurring on a single
The analysis that follows does not include either the cost of movement, nor the cost of
sending an invocation. For concision, we ignore replies to lookup messages, and assume
lossless communication.
Whenever a mobile component moves, it must update the directory. Thus, D’s message cost
per move is 1. A lookup may fail due to racing with a move. Equation 5.3 calculates the
expected number of find messages, hDi, that must be issued given that races are possible2 .
Its first line captures the expected cost of a mobile component moving in each race window
infinitely often as an infinite series. At the start of each race window, we send a message,
the 1 in both terms. If the mobile component does not move during the race window, we
have found the mobile object. If it does move, we begin a new race window.
mechanism for implicitly introducing a variable into an equation. Here, we use A to make
A = e−λm tr + (1 − e−λm tr )A
A − (1 − e−λm tr )A = e−λm tr
Ae−λm tr = e−λm tr
A=1
hDr i = 1
1
Assuming that c’s location is uniformly distributed across H, n is the chance that i and
n−1
c are collocated and n is the chance that c is remote to i. D’s lookup cost is zero when i
1
and c are collocated. This is the n0 term in Equation 5.4.
1 n−1 n−1
hDl i = hDr i( 0 + )= (5.4)
n n n
Caching a resource’s last known location is a simple and common optimization. Equa-
tion 5.5 defines the expected lookup cost under D in the presence of caching. If the cache
is up-to-date, no find message is sent, but, if not, the invocation that was sent becomes
a find, which costs 1 message, and then a normal lookup occurs, whose cost is given by
n−1
Equation 5.4. Together, these terms compose the factor 1 + n . Notice that ti , the time
host.
5.2. Directory vs. Forwarding Pointers: Message Cost 87
n−1
hM i + hV i(1 − e−λm ti )(1 + ) (5.6)
n
When a mobile component moves under FP, it leaves behind a forwarding pointer, which
costs no message. However, when an invoker seeks to invoke an operation on that mobile
component, it must traverse the chain of forwarding pointers built by that mobile component’s
itinerary. At the time of the j th invocation, let fj be such a chain of forwarding pointers
be zero.
was found after each invocation, as shown in Figure 5.4. Thus, an FP invocation does not
start from the target mobile component’s origin on each invocation. This point is crucial to
understanding the upper bound: each invocation traverses part of the path formed by c’s
hM i moves. This is because the path starts from the invoker i, not a directory.
hV i
hM i X
≤ |fj | ≤ hM i (5.7)
2
j=0
Equation 5.7 bounds FP. The lower bound occurs when c collocates with i every other
move. Note that the lower bound cannot be zero, given our definition of a move as a change
of host. The component c can revisit a host during its expected budget of hM i moves, thus
5.2. Directory vs. Forwarding Pointers: Message Cost 88
c c
nd nd
Find Fi Find Fi
c Ask h1 h3 c Ask h1 h3
A sk As
k
h2 h3 h2 h3
c c c c
Find c Find c
i c i c
c is here c is here
splitting its chain of forwarding pointers. When it does so, it shortens the chain for invokers
both ahead and behind the revisited node. The longest path c can form is n − 1. The
component c can repeatedly form a longest path by moving n − 1 times between invocations.
Recall that I is the set of invokers. When |I| > 1, D’s expected total message cost becomes
Phvi
hM i+|I|hV i, while FP’s total becomes |I| j=0 |fj |. Collapsing FP chains is an optimization
that improves the performance of FP when there are many invokers. Because it reduces the
expected length of a chain of forwarding pointers, it also reduces the fault sensitivity of FP.
FPc is forwarding pointers with path compression. Under FPc , an invoker that traverses a
chain of forwarding pointers, revisits the hosts along the chain to update their pointers to
point to the target mobile component’s current host, after it has found the target mobile
component. It does not revisit the penultimate hop in the chain or the target component’s
current host as these hosts have current information. By collapsing the path, an invoker
c c
nd nd
Find Fi Find Ask at
c
Fi
c Ask h1 h3 c h1 h3 h3
k k
As As
h2 h3 h2 h3
c c c c
Find c Find c
i c i c
c is here c is here
In Figure 5.5, i not only updates its local pointer for c on h2 to point to h3 after it has
found c, but asynchronously collapses the chain of forwarding pointers to c by updating c’s
entry on h0 to point to h3 .
The function u : N → N defined in Equation 5.8 represents the cost of both traversing
and collapsing the chain of forwarding pointers |fj | at the time of invocation j.
|fj |
if |fj | ≤ 2
u(j) = (5.8)
2|fj | − 2 otherwise
Table 5.1 summarizes the expected messages required to both find a component and update
hV i
−λm ti n−1 X
hM i + hV i(1 − e )(1 + )= |fj | ≤ hM i
n
j=0
n−1
hV i(1 − e−λm ti )(1 + ) ≤ hM i − hM i
n
n−1
hV i(1 − e−λm ti )(1 + )≤0 (5.9)
n
To compare D and FP for a single invoker, we set their total costs equal and solve.
Equation 5.9 implies FP sends fewer messages than D on average, since FP’s cost is
independent of hV i, the expected number of invocations, even assuming the worst case
movement of the target mobile object, where the adversary makes the invoker perform a
traversal for each move. Intuitively, D does a lot of needless work to keep its directory
up-to-date: When a mobile object moves three times between invocations, only the last
Multiple invokers will only strengthen this result for FP, as an arbitrary invoker is likely
to benefit from the shortcut performed by another invoker along its path to the object. FPc
only makes sense in the context of multiple invokers. Future work will extend this analysis
to multiple invokers.
5.3 Correctness of FP
Here, we assume that moves are instantaneous. In practice, we approximate this assumption
by tolerating inconsistency in the tree forwarding pointers for a bounded period of time, see
Section 6.5.4. Our proofs use induction on states, so there can be no simultaneous transitions.
In particular, we assume a total ordering over message arrival within the network. We also
assume that r is not moving faster than the finds that are chasing it. In practice, we enforce
this assumption with a bound on the length of the path to a resource that a finder follows
Let R denote a set of mobile resources. The origin of r ∈ R is the host at which r enters
the network. Let F be the set of finders. F 6= ∅. Let HF ⊆ H be the set of hosts on which
5.3. Correctness of FP 91
Initially, Equations 5.11 and 5.12 hold. The nil in Equation 5.12 means that the host
σ[x := n](x) = n
Below we use the prime operator from Lamport’s Temporal Logic of Actions [57].
FP Rules
the searcher updates its local forwarding pointer to hr , the host at which it found r.
y) ∧ (f p(x) 6= nil)}.
Definition 5.3.1. A directed tree is a digraph whose underlying graph is a tree. A rooted
tree is directed tree with a root and a natural edge orientation either toward or away from
Below, we consider only rooted trees whose arcs are oriented toward their root; our root
is the vertex reachable from all other vertices. Thus, the root is Rome and “Tutte le strade
Proof by Induction.
edges and is connected. Therefore, it is a tree. Each edge is an arc whose terminus is origin,
Two FP rules mutate the tree of forwarding pointers — Rule 2, a resource move, and
Case Local Update: Let l ∈ H be the host of the finder f ∈ F . By the inductive
as is the subtree rooted at hr after the l subtree has been removed. Rule 3 forms G0 by
changing l’s parent pointer to hr , thus directly hanging l subtree from hr . This change
preserves connectivity, the number of nodes, and edges. Thus, G0 is a directed tree.
Case Move: When the n + 1 tree mutation is a move, let r moves from hs to hd , for
hs , hd ∈ H.
rooted at r.
Case f p(hd ) 6= nil: Since any connected subgraph of a directed tree is also a directed
tree, the subtree rooted at hd is a directed tree and so is the subtree rooted at hs after
the subtracting the subtree rooted at hd . Rule 2 removes the arc from hd to its parent
of G0 . Rule 2 also adds a new arc from hs to hd . This arc connects the tree rooted at
hd and the remaining tree rooted at hs . Since the number of nodes is constant, the
Figure 5.6 demonstrates that cycles can arise if one naively adds path collapsing to the
follows the chain of forwarding pointers to r at h3 i.e. at a host not depicted in Figure 5.6.
The finder f then creates messages to update the forwarding pointers along the chain of
forwarding pointers it traversed while searching for r. The purpose of these messages is to
and to h1 , but not h2 , because its pointer is already current, or h3 , r’s current residence. In
Figure 5.6b, r moves backwards along the chain of forwarding pointers to h0 , before h1 ’s
collapse message arrives. In Figure 5.6c, the collapse message for h2 arrives and creates a
cycle.
relation for forwarding pointers. As Fowler observed, counting the moves a mobile object
makes is sufficient to distinguish which of two forwarding pointers is more recent [30].
h0 h1 h2 h3
c c c c
h0 h1 h2 h3
c c c c
c c c c
(b) c moves to h0
h0 h1 h2 h3
c c c c
c at h3
(c) i updates h1
physical clock, such as how old a forwarding pointer is. A Lamport clock requires the
pairwise exchange of messages between all nodes interested in totally ordering some event.
This can be expensive and unnecessary if one knows some statistical properties of the physical
clocks that compose the system. Below, we implement a very simple and cheap clock and, in
so doing, allow a location service to retain, but not rely on, physical clocks. A proof using a
Proof Idea: Realizing FP with path collapse (FPc ) requires additional rules. For each
search, a finder creates a unique marker, a “bread crumb,” with which it marks the hosts it
traverses while following the chain of forwarding pointers to a particular resource. Then it
sends collapse messages that share the bread crumb marking to each host along the chain.
The host only accepts the collapse message if its marking matches the host’s current marking.
5.3. Correctness of FP 95
Let B = N × N denote the set of “bread crumbs.” The first component of a bread crumb
either uniquely identifies a finder or denotes the null, or “scrubbed,” marking, and ranges
finds issued by that finder. Let m : H × R → B mark the fact that a finder has deposited
a bread crumb on h for some r. Let F M = R × B be the set of find messages. Let
messages. The collapse message c ∈ CM is a four tuple consisting of a target host, a resource,
a forwarding pointer, and a bread crumb. Note the constraint that the target host and the
forwarding pointer must be distinct. Let HCM = {h | (h, r, hi , b) ∈ CM } denote the subset
1. Create Find Message: At the start of a search for r, the finder f creates the find
2. Drop Crumb: Whenever the host h responds to the find message (r, b) with a
3. Eat Crumb on Move: In addition to the actions in Rule 2 above, the arrival of r at
4. New Collapse Messages: Each search issued by each finder adds an element to
CM for each host it visits along its path to r, except the host on which the finder is
Equation 5.13 uses a binary bread crumb to illustrate why each crumb must be unique.
Unique crumbs can prevent collapse messages from being processed out of order; however,
here we use them only to kill all collapse messages sent prior to a scrubbing.
i0 marks h =⇒ m(h, r) = T
r transits h =⇒ m(h, r) := F
i1 visits h =⇒ m(h, r) := T
Theorem 5.3.2. Under FPc with path scrubbing, ∀r ∈ R, ∀hc ∈ HCM , G = (Hk , E) is a
directed tree rooted at hr , the current location of r, after n > 0 tree mutations.
Base case: This base case is identical to that in Theorem 5.3.1 above.
Under FPc , three rules that mutate the tree of forwarding pointers, local update, the
Case Local Update: See this case in Theorem 5.3.1 above: the effect of the collapse
messages that occur prior to this local update do not violate the tree invariant because
Case Move: See this case in Theorem 5.3.1 above: the effect of the collapse messages prior
to this move do not violate the tree invariant because of the inductive hypothesis.
Case Collapse Message: Let receipt of the collapse message c = (hc , hd , b) ∈ CM be the
Case m(hc , r) 6= b: Another find overwrote b at hc with its bread crumb, or r transited
hypothesis.
Case m(hc , r) = b: At the time that b was dropped, hc was the root of a direct
subtree and hd was the root of a directed subtree at that same time, by the strong
inductive hypothesis. Any moves r made after b was dropped also created trees,
subtree, thereby moving a host formerly in those subtrees to the root, the hc and
hd subtrees remained trees. At the time of the receipt of c, the hd ’s subtree, with
Under a location service that uses a central directory, a natural invocation protocol for
mobile components is to first find the target mobile component, then invoke an operation
on it. We call this protocol “find, then invoke” (FI). This protocol generalizes easily to
forwarding pointers — the invoker simply issues finds to follow the chain of forwarding
pointers.
A location service based on forwarding pointers also makes feasible another invocation
protocol that integrates name resolution and routing — self-routing invocations (SI). Under
SI, when a host receives an invocation message for an absent component, it forwards that
invocation to the next host in the chain of forwarding pointers to that component. The SI
protocol does not make much sense in the absence of forwarding pointers, because each host
that receives an invocation that fails would be burdened with querying the directory on the
h0 h1 h2 h0 h1 h2
move0 move1 move0 move1
c c c c c c
lt 5 lt 6
i3 i4 su su
re re
f3 f4
h3 f2 h3
i2 i5
a a
show below, suffers from a narrower race window than does FI. As this section unfolds, we
show that, to the contrary, FI is superior except in the pathological case of the target mobile
object moving at very nearly the rate at which invocations are generated. The decisive
difference between the two protocols is message size. This chapter shows that successfully
integrating name resolution and routing depends on the ratio of the size of a find message to
the size of the message routed to target. This ratio is an important, and heretofore neglected,
consideration for any project that proposes protocols that integrate name resolution and
routing, such as intentional naming [3] and location independent invocation [14].
operation on c. In both figures, the last known location of c at h3 is h0 . Before a’s invocation
reaches it, c moves twice, reaching h2 . Each message is subscripted with its temporal order.
In SI, an invocation itself follows the chain of forwarding pointers to the component for
which it was launched, as shown in Figure 5.7a. Figure 5.7b depicts an invocation under FI.
Here, the invoker a sends find messages to follow the chain of forwarding pointers for c to
Under MAGE, the collocation of an invocation message and its target mobile component
at a particular host does not necessarily imply execution at that host, as a mobility attribute
is unlikely to have specified that host as the execution target. Thus, for both SI and FI,
a MAGE invocation usually entails an additional hop to its execution target, where the
5.4. A Comparison of Two Invocation Protocols under FP 99
host at which the invocation caught up to its target mobile object forwards the invocation
message, swollen with the mobile object. This additional work adds the constant cost of
a single additional invocation message to both protocols, which we do not include in the
The two protocols trade-off the number of messages for their size. For x ∈ {fq , fr , i}, let
|x| be the size of the message. The message fq is a find query, and fr , a find reply. For brevity
and because we usually work with the find messages as a unit, we define |f | = |fq | + |fr |.
Almost always, |f | << |i| holds, since a find query contains only the name of its target
mobile component and a find reply contains only a location, while an invocation message
minimally contains not only the name of its target mobile component, but also a target
method name, not to mention that method’s parameters, each one of which may be quite
large.
Intuitively, it would seem that this observation about messages sizes closes the case: FI
is superior to SI. However, while both protocols are subject to races with their target mobile
component, FI’s race window has twice the duration of SI’s since FI must both send fq and
As in Section 5.2, we use M to denote the moves a mobile component makes and V
the invocations an invoker makes, both over the same time interval. M and V are Poisson
distributed random variables. Recall that r is the rate at which an invoker sends messages
1
and that we assume λm < r ≤ tr , for tr = RTT. The analysis that follows assumes a single
invoker, abstracting other invokers into the moves made by the target component.
Consider Figure 5.7b again. What if c moves before the invocation arrives at h2 ? After
FI’s find phase ends, a race occurs between c leaving h2 for some other host h4 and the
arrival of the invocation at h2 . To handle this race, FI restarts, and begins a new find phase.
Figure 5.8 depicts the FI race in a sequence diagram. The actor a’s find request reaches
h2 while c is still on h2 . Once h2 replies saying it hosts c, the race starts. There are two
races, both involving r1 . If r1 occurs before r0 , then a will know to continue following the
chain of forwarding pointers. This case is indistinguishable from the case where c was simply
not at h2 when a’s find arrived. The second race is between r1 and r2 ; the race window is
5.4. A Comparison of Two Invocation Protocols under FP 100
a at h3 h2 h4
find
c race
starts
h 2 r0
c at
r1 c
invo
ke c
r2
lower-bounded by RTT, the time for h2 to send its reply to a’s find and a dispatch of its
invocation message to arrive at r2 . If r2 wins the race, then c executes the invocation and
the FI protocol ends; if not, the chase continues. In Figure 5.8, r1 wins the race.
The probability that FI wins the latter race with its target mobile component is e−λm tr ,
for tr = RTT, because this is the probability of zero moves after a successful find reply is
h1 h2 h4
invo
ke c r0 c
r1
time
SI too is subject to a race. Figure 5.9 starts in the configuration that Figure 5.7a depicts.
Here, r0 , c’s departure from h2 for h4 , races against r1 , i’s arrival at h2 . Ignoring i’s size, i’s
tr
travel time, and thus the race window, has duration 2, since neither the invoker nor the
this is the probability of 0 moves after an invocation message has arrived at h0 and before it
arrives at h1 .
5.4. A Comparison of Two Invocation Protocols under FP 101
services and show that, in the expected case, FI uses less bandwidth than SI, in spite of its
The moves the target mobile component made before the beginning of an invocation
must first be consumed. Figure 5.10 defines tb , the time between the end of one invocation
protocol and the start of another. We do not consider the interval between the start of
the two invocation protocols because, at the time of the successful invocation, the invoker,
by definition, knew the location of the target mobile component. Ignoring the possible
collocation of invoker and its target component, tb > 1r , inverse of the rate at which the
invocation
protocol tb
pointers formed by these moves takes time, during which the mobile component can again
move, and so on. The time to traverse the forwarding pointers formed while traversing
the path formed during tb is (λm tb )tr , so the expected number of moves that occur during
this time is λm (λm tb )tr . In turn, the time to traverse the path of forwarding pointers
formed by the moves made while traversing these moves is (λm (λm tb )tr )tr , which generates
Let U be the number of moves until the invoker first catches up to its target component.
5.4. A Comparison of Two Invocation Protocols under FP 102
= λm tb (1 + λm tr + λ2m t2r + · · ·
∞
X
= λm tb (λm tr )i
j=0
1 1
= λm tb λm <
1 − λm tr tr
λm tb
= (5.14)
1 − λm tr
Under FI, an invoker has caught up with its target mobile component c, when it receives a
reply to a find message that states “c is here.” FI alternates between sending finds to catch
up to its target mobile component, and sending invocations. After each failed invocation, it
must again catch up. As a simple optimization, the reply to a failed invocation contains the
forwarding pointer, which FI can immediately follow upon restarting the find phase of its
protocol. Equation 5.14, for tr = RTT, is the message cost of FI initially catching up to c,
The time it takes the invoker to again catch up with the mobile component is Equa-
tion 5.14, but with tb replaced by λm tr multiplied by RTT, the time to traverse the forwarding
pointer chain created by any moves that occurred during the transit time of the reply to
the successful find and that of the failed invocation message. Since λm tr RTT = λm t2r , the
λm λm t2r (λm tr )2
= (5.15)
1 − λm tr 1 − λm tr
5.4. A Comparison of Two Invocation Protocols under FP 103
hFIac i = |i| + P (j > 0 moves before call arrives)[|f |(E(finds) after a failed call)
+ |i| + P (j > 0 moves before call arrives)(|f |(E(finds) after a failed call) + · · · )]
(λm tr )2 (λm tr )2
= |i| + (1 − e−λm tr )[|f | + |i| + (1 − e−λm tr )(|f | + · · · )] (5.16)
1 − λm tr 1 − λm tr
In Equation 5.16, |i| is the cost of an invocation (call) and |f | is the cost of a find message.
After a successful find, the chance that a message, in particular an invocation, reaches the
mobile component’s host before it moves is P (no moves in tr ) = e−λm tr , from the definition
of Point Poisson. Thus, after each find phase, the chance that the invocation we dispatch
wins the race with the mobile component and arrives in time is e−λm tr and the chance it
Each time the find phase of FI catches up with the mobile component, it sends an
invocation message which either succeeds or fails. An invocation fails whenever the target
mobile component moves after the reply to a successful find is sent from a host and while
the invocation is in transit to that host. If it fails, the invoker must first catch up again
(λm tr )2
and then send another invocation message. 1−λm tr is the E(finds) after a failed call from
Equation 5.15.
(λm tr )2
a = |f | + |i|
1 − λm tr
b = 1 − e−λm tr (5.17)
Next, we derive a closed form solution of Equation 5.16. We form Equation 5.18 from
Equation 5.16, using a and b, as defined in Equation 5.17. We then rearrange Equation 5.18
(λm tr )2
hFIac i = |i| + (1 − e−λm tr )[|f | + |i| + (1 − e−λm tr )[· · · ]]
1 − λm tr
= |i| + (1 − e−λm tr )[(a + b)[(a + b)[(a + b)(· · · ]]]
Finally, we undo the rewriting and simplify. Equation 5.19 captures the expected total
data, and implicitly the expected messages, FI transmits, after the invoker has first caught
(λm tr ) 2
−λm tr
|f | 1−λ m tr
+ |i|
hFIac i = |i| + (1 − e )
1 − (1 − e−λm tr )
2
(λm tr )
−λm tr
|f | 1−λ m tr
+ |i|
= |i| + (1 − e )
e−λm tr
(λm tr )2
= |i| + (eλm tr − 1)(|f | + |i|) (5.19)
1 − λm tr
For |ir | = |i| + |fr |, Df i is the data sent by FI, until the invocation i and its target
We use |ir | to denote the size of invocation message paired with a find reply, the
The expected data transfer required (and implicitly the number of invocation messages)
used under SI, hDsi i, differs from hDf i i in two ways: We replace
tr
1. tr with 2, because, under SI, an invocation is a find, so at each step on the chain
of forwarding pointers, we do not notify the invoker, but rather simply dispatch the
invocation; and
2. |f | with |i|.
5.4.3 FI vs. SI
In these figures, we use RTT = tr = .606ms. The UNIX utility ping run for ten minutes
in February 2008 on the switched 100Mb Ethernet LAN in our laboratory reported this
number as the average RTT. Unless otherwise noted, we fix the remaining variables in
Equations (5.20) and (5.21) to following values, which we believe are reasonable to assume:
.1
|i| = 5|f |, λm = tr , tb = 10tr = 6.06ms, and |fr | = .5|f | so |ir | = |i| + .5|f |. The dependent
Figure 5.11 varies |i| as a multiple of |f |. Figure 5.12 varies λm as a fraction of RTT.
Figure 5.13 varies tb in multiples of RTT. Except in in Figure 5.12, hDsi i > hDf i i, and, even
here, SI only sends less data when a component moves often relative to RTT. Thus, we
conclude that FI is the superior invocation protocol, in spite of its wider data race window.
5.4. A Comparison of Two Invocation Protocols under FP 106
100|f |
80|f |
60|f |
data
sent
40|f |
20|f |
0|f |
0|f | 20|f | 40|f | 60|f | 80|f | 100|f |
|i| in units of |f |
200|f |
hDsi i
hDf i i
150|f |
data 100|f |
sent
50|f |
0|f |
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
λm ( t1r )
100|f |
hDsi i
80|f | hDf i i
60|f |
data
sent
40|f |
20|f |
0|f |
0ms 20ms 40ms 60ms 80ms 100ms
tb
Forwarding pointers are not new. They were first used in the DEMOS/MP distributed
system [83], which called them links and updated them only when a process moved to a
machine that had links pointing at that process. They were widely used in other early
mobile objects systems [14, 48, 96]. A number of distributed garbage collection techniques
use forwarding pointers [71, 81]. Researchers have also proposed and evaluated location
services that incorporate forwarding pointers for Personal Communication Services (PCS),
In general, these projects describe the design and implementation of location services
based on forwarding pointers, but do not prove their correctness or analyze their cost. Below,
we review the work that, like this chapter, does tackle these questions.
Section 5.2 presents concurrent models of three location services in the presence of mobility
— a directory and two variants of forwarding pointers. Thus, our expected cost analysis
handles (1) multiple invokers; and (2) mobile objects moving while lookups and invocations
5.5. Related Work 108
occur. As a result, our analysis incorporates data races between invocations and moves. We
report bounds in terms of messages. Section 5.3.1 proves the correctness of a concurrent
Fowler’s “The complexity of using forwarding addresses for decentralized object finding”
is the seminal analytic work on forwarding pointers [30]. Fowler was the first to observe that
incrementing a counter in a mobile object each time it moves is a sufficient timestamp for
a forwarding pointer since we only need to know which of the two pointers is more recent.
Fowler formulates and analyzes three forwarding pointer variants, which he calls Lacc, Jacc,
and PCacc. Lacc is the naı̈ve forwarding pointer protocol with no updates; Jacc includes
redirecting the local forwarding pointer after a successful find; and PCacc collapses the path.
Fowler considers only forwarding pointers. He does not consider integrating name
resolution and routing. Like us (Section 5.2), Fowler assumes that machines do not fail, so
he does not consider fault tolerance and FP’s fault sensitivity. Fowler does not prove the
correctness of his forwarding pointer protocols. Unlike our analysis, Fowler counts access
(find) attempts; that is, the injections of an access message. He does not count the re-sends
of that message during the traversal of a chain of forwarding pointers. Thus, Fowler’s model
does not account for races between moves and accesses. Fowler’s PCacc does not handle
concurrent accessors (invokers), as our FPc does. In short, he analyzes a simpler and less
Shapiro et al. proposed a form of forwarding pointers with a focus on garbage collec-
tion [90, 91]. They gave their proposal the sobriquet “SSP Chains,” where SSP stands
for stub scion pairs. Scions are skeletons and are used during local garbage collection to
reach and keep alive stubs. A stub has fixed targets, usually scions, and does not contain a
universal unique identifier (UUID) for its target mobile object; Shapiro et al. claim removing
UUIDs from stubs is essential for performance. Sending a remote reference or migrating
an object extends SSP chains. The former complicates the use and maintenance of SSP
chains and is a direct consequence of the fact that SSP stubs do not contain a UUID and
therefore cannot query a name service to follow the chain to their target object. In this
5.5. Related Work 109
thesis, a remote reference is a stub that does contain a UUID and can therefore directly
query the name service to traverse the FP chain to its object. Practically, this is why the
FP variants proposed in this thesis do not extend an FP chain when a reference moves from
Shapiro et al. never shorten an SSP chain, except to reclaim the chain when it has no
users. A shortcut is the update of the local forwarding pointer after a successful lookup.
In SSP, a shortcut is only a hint, stored as a weak reference. Finds do not alter strong
SSP chain, which is created by object and reference movement creates. These properties
allow SSP chains to support concurrent access. They suggest path-collapse as a possible
optimization, but, like a shortcut, only as a hint. In contrast, this thesis proposes, analyzes,
and proves correct FP variants that do alter shared forwarding pointer chains.
Shapiro et al. consider machine failure although they rely on the strong assumption of a
failure detection oracle. We have left machine failure for future work. They do not provide
The Arrow Distributed Directory Protocol is a simple protocol that acquires exclusive
access to a mobile object [22]. When a node issues a find for a target mobile object, each
arc in the forwarding pointer tree that the message traverses on its path from the finder to
the object flips to point toward the finder. When the find messages reaches the object, a
new tree rooted at the finding node forms. The object then traverses the newly formed path
to the finder, which then has exclusive access to the mobile object. The arc-flipping caused
by a find message traversal disconnects the tree while the find message is progressing toward
its target. This fact handles contention elegantly. An invoker in the finder’s subtree will
find the finder and block there waiting for the finder to release the object. An invoker in
the object’s subtree proceeds normally. Demmer et al. prove the correctness and complexity
The Arrow protocol only handles exclusive access: in it, the accessed mobile object
always moves to the finder’s location. In terms of MAGE, this is equivalent to an invoker
using only COD. The protocols analyzed in this chapter allow executing operations in place,
as well as moving the target object to an arbitrary node in the graph. The Arrow protocol
5.5. Related Work 110
is well-suited for use in realizing write access in distributed shared memory, as a review of
Moreau formalizes a fault tolerant forwarding pointer location service [72, 73]. He
describes a mechanical proof of its correctness using the proof assistant Coq [12]. As we
have noted above, naı̈ve forwarding pointer protocols are fault sensitive: the probability
that an object becomes unreachable increases with the length of a forwarding pointer chain.
Moreau’s protocol addresses this problem by collapsing a length n suffix of the forwarding
pointer chain. A mobile agent remembers the last n hosts it visited. Upon arrival to a new
Moreau’s protocol enqueues messages at a mobile object’s last host during migration
rather than tolerating transient cycles (as we do), which works well when you include a
laptop as a possible host. After arriving at its new host, the mobile object itself collapses
the path and is unavailable until it finishes. Multiple invokers simply queue at the mobile
object’s last location. Their finds can race with the suffix collapse, but if they lose, they
simply follow a longer path to the object. Thus, Moreau’s protocol handles concurrent
invokers. Recall that we named our the path-collapsing FP variant FPc . The price FPc pays
asynchronously after an invocation, Moreau pays during migration, since the suffix collapse
occurs during migration. Many invokers cooperatively drive the FPc cost to zero; Moreau’s
Moreau does not analyze the bounds of his protocols, except when he considers the
cost of collapsing the suffix of an FP chain. Thus, he does not confront the difficulty of
accounting for races between moves and finds. Relying on 25,000 Coq tactics3 , Moreau’s
correctness proofs are much longer and more complex than the ones we have presented in
this chapter.
3
A deduction rule links premises and a conclusion. In backward reasoning, the conclusion is the goal and
the premises are subgoals. Tactics implement backward reasoning. When applied to a goal, a tactic replaces
the goal with its subgoals. Thus, a Coq tactic is a command that realizes one or more steps of a proof [98,
Chapter 8].
5.5. Related Work 111
Section 5.2.4 compares the lookup and maintenance cost of a single directory to two forwarding
pointers variants using expected analysis that incorporates races between invocations and
moves.
In a distributed setting with mobile objects, like MAGE, Alout et al. use Markov models
to compare the access (find) cost of FP and D [5]. Their model is quite detailed: for instance,
it uses random variable to model such things like migration time, where our model implicitly
uses expected time via RTT. An important difference is that they consider only access time,
not the time to update the directories. Further, their analysis assumes a mobile object does
not revisit a host. They assume that chains of forwarding pointers are not shared, that each
accessor/object pair has its own chain. Under this assumption, path collapse does not make
sense. However, they do not consider shortcuts, which are relevant to and could improve the
performance of their protocol. Like us, they assume hosts do not fail.
costs and improve service. Thus, a number of researchers have compared forwarding pointers
Jain et al. attack precisely the question we have asked: under what circumstances is FP
superior to D [47]. Their callers do not shortcut, i.e. cache the result of a find. They do
not consider path collapse. They bound the length of forwarding pointers: every k move,
they update the HLR. In the PCS context, a FP protocol must send a message back to the
previous visitor-location register (VLR), which is analogous to a host in our analysis, because
a mobile device can only detect that it has left that VLR after the fact. These differences
lead them to show, under various probabilistic assumptions about a mobile user’s movement
behavior, that FP only wins when the call to move ratio is less than 0.5, in contrast to our
Krishna addresses the D vs. FP question in his dissertation [54, Chapter 3]. He models
the problem using time-cost, not messages. He considers two variants of bounded-chain FP,
5.5. Related Work 112
one which, like the variant of Jain et al., updates the HLR every k moves and another which
updates the HLR after some k searches. Finally, he introduces shortcutting, which he calls
“search-update,” versions of these two variants. Like Jain et al., he shows that FP performs
Chang et al. propose a hybrid location service that uses forwarding pointers to build a
virtual local directory out of adjacent VLRs that a user frequently visits [18]. Only when
a user moves out of the virtual directory does the HLR need to be updated. To compare
their scheme to competing alternatives, including directory and FP, they count the update
messages sent to the HLR and VLRs during a single itinerary. Under this itinerary, the FP
variant they consider sends 1 message to the HLR and 9 to VLRs, the directory approach
sends 5 messages to the HLR and 5 to VLRs, while their approach sends 1 message to the
HLR and 6 to VLRs. Unsurprisingly, their approach performs best under the itinerary they
choose. The FP variant they consider does not shortcut or collapse paths.
5.5.3 FI vs. SI
Section 5.4 compares two invocation protocols based on forwarding pointers — one that
maintains the traditional separation of name resolution and routing (FI) and one that
integrates them (SI). We show that message size is a critical factor in determining which to
use, and that integration does not make sense when the routed message is larger than a find
message, as generally holds when the routed message is an invocation. We demonstrate this
result holds when the routed message is 5 times larger than an find message.
The Hermes project integrates name resolution and routing in its invocation protocol [14].
“Intentional naming” [3] proposes a location service that integrates name resolution and
message routing. Neither of these projects consider the conditions under which integrating
name resolution and message routing makes sense. To our knowledge, we are the first to
This chapter focuses on two directory schemes — a single, centralized directory and forwarding
pointers. An interesting avenue for further research is to analyze other directory schemes in
terms of their message cost. For instance, a D-FP hybrid that partitions the hosts among a
set of directories. Under this scheme, when a mobile component leaves one directory’s region,
it forms a chain of forwarding pointers that connect each region’s directory. It would also be
interesting to extend this analysis to the distributed hash tables, such as Chord [94], used in
P2P settings. We showed that FP is superior to D for a single invoker in Section 5.2.4. We
The random model of movement and invocation presented here uses Poisson random
variables. With the aid of application specific knowledge, such as traces, it may be possible
to build more accurate models. For presentation clarity, the analysis presented in this
chapter assumed that machines do not fail. We plan to revisit our analyses in the presence
of machine failure and explore fault tolerant versions of the protocols we have considered,
in addition to quantifying the fault tolerance protection afforded by frequent path collapse.
Finally, one could use simulation and experiment to further explore this problem space and
5.7 Summary
In this chapter, we have discussed location services in the presence of mobility. We presented
forwarding pointers and contrasted them with a single centralized directory, and showed that
forwarding pointers require fewer find messages on average. We defined and proved correct a
two invocation protocols built on forwarding pointers — “find, then invoke,” which maintains
the traditional separation of name resolution and routing, and “self-routing invocations,”
which integrates the two. Conservatively assuming invocations are larger than finds, we
show that the “find, then invoke” protocol requires a smaller expected data transfer before a
5.7. Summary 114
successful invocation than “self-routing invocations” except when a mobile component moves
rapidly, which given the cost of movement, is unlikely to persist in well-behaved applications.
115
Chapter 6
Implementation
Niklaus Wirth
In this chapter, we discuss the challenges faced in the implementation of MAGE. First,
we set the stage with a brief description of RMI’s runtime, against which we present the
MAGE runtime as a sequence of modifications and extensions. Then, we broadly follow the
outline of Chapter 4, and describe the challenges in implementing the MAGE primitives
and operations on those primitives. In closing, we discuss the limitations of the current
6.1 Challenges
In principal, MAGE could be built on any language that provides mobility, such as Java,
D’Agents [36], Messengers [31], or Ajanta [102]. We choose Java as our implementation
platform because of its platform independence, widespread availability, and support for
remove calls via RMI and serialization, hereafter referred to as marshaling1 . We realized
1
So far as the author knows, Sun introduced the use of the term serialization, as opposed to marshaling,
to refer to the writing of data, such as an object, to a bit string. In fact, Sun distinguishes serialization and
marshaling, which it restricts to codebase-annotated serialization [87]. This distinction is highly Java-centric.
In spite of Sun’s marketing prowess and the success of Java, this author prefers “marshaling” because
serialization already has a useful technical definition in concurrent programming where it refers to the
6.1. Challenges 116
MAGE as a Java class library to ease and facilitate its deployment. The MAGE runtime
system is built upon and extends the Java RMI class library and its runtime system.
single host, not a cluster. MAGE uses forwarding pointers, to decentralize MAGE’s directory
service and for efficiency, as described in Chapter 5. This decision means that every MAGE
host must store forwarding pointers for each mobile object that either visits or is invoked
from that host. The principal challenge in implementing a forwarding pointer directory
service is preventing the formation of cycles. A simpler solution would have been to use a
The decision to use Java means that MAGE inherited Java’s assumption that objects are
immobile, that they spend their entire lifespan in a single address space. This assumption
means that
1. the client leases that Java’s Distributed Garbage Collector (DGC) server hands out
3. a Remote object can always be replaced with a proxy during marshaling, as when it
To solve the DGC challenge, MAGE modifies Java’s DGC to follow an object’s chain
of forwarding pointers to renew its lease, just as a MAGE invocation must. From the
point of view of MAGE applications, DGC occurs out-of-band. Although DGC could, in
principle, compete with applications for the CPU and bandwidth, preliminary tests showed
when defining mobile classes. To prevent RMI always replacing a mobile object with a proxy,
MAGE extended the marshaling framework to distinguish whether or not to marshal the
execution of a critical section by one thread at a time.
6.1. Challenges 117
mobile itself or a proxy to it. The cost of this solution is single condition on a reflective call
Mobility complicates a remote invocation protocol, not so much because a mobile object
may have moved once an invocation arrives, but because the mobile object may be preparing
to move. When the mobile object has already moved, the protocol can simply be restarted.
To move, a mobile object must capture all updates to its state made prior to departure.
To capture these updates, MAGE prevents new threads from entering a moving object
and waits for threads already running in that object to finish. MAGE sends exceptions to
the invokers of post-moving invocations to block the entry of new threads. These invokers
immediately restart their invocation protocol, subject to a starvation limit. Draining can,
of course, take a long time and fending off invokers that immediately restart is wasteful.
Blocking the post-moving invocations in a lock queue and then freeing them all at once,
when the executing threads had drained and the mobile object had departed, is likely to
lead to better performance. Locking issues surrounding handling movement in the presence
of asynchronous incoming calls are tricky, and discussed in detail in Section 6.5.4 which
Mobility attributes further complicate the invocation protocol. The remote invoker must
run his local mobility attribute, and embed the result in the invocation. Then the mobile
object’s host must run the server, or component mobility attribute, if one is bound, and
When an invocation reaches a mobile object at a host other than the ultimate execution
target, the mobile object must move. The connection over which the invoker sent the
invocation and, under RMI, would expect to receive the result is to the host at which the
mobile object was found. Two solutions leap to mind: 1) The invocation can either be
forwarded to the execution target and the result routed back to the invoker via a listener; or
2) the mobile object can move, be locked in place, and the invoker instructed to re-issue its
invocation to the execution target. The current implementation chooses the former solution,
because no other invocations can occur between arrival at the execution target and the
“There are known knowns. There are things we know that we know. There are
known unknowns. That is to say, there are things that we now know we don’t
know. But there are also unknown unknowns. There are things we do not know
we don’t know.”
Donald Rumsfeld
There are undoubtedly many ways to improve the MAGE implementation, many of
which are unknown unknowns. Two known known and one known unknown suggestions for
Since the set of hosts in a MAGE cluster is likely to be relatively static, using bit maps
2. Invocations on a mobile object made by an invoker collocated with that mobile object
are not local, but remote call and are therefore marshaled and traverse TCP/IP stack
over the loopback device. Each MAGE host could maintain an id → proxy map. Then,
when a mobile object arrives, MAGE could use the arriving object’s id to set a direct
reference to itself in each of its local proxies. Thereafter, calls on these proxies would
be local. When id departs, MAGE would null the direct reference in each of id’s
proxies.
3. Verify the design decision to use a listener to manage results, by empirically comparing
the two result management protocols. The fact that the listener allows MAGE to
Definition 6.2.1. An RMI remote object is an instance of RemoteObject that can receive
Service Map
RMI registry name → proxy
invocation server id → RemoteObject
DGC server id → LeaseInfo
activation server id → RemoteObject
Definition 6.2.2. An RMI proxy or stub is created for a specific remote object. It stores its
remote object’s host, or server. It marshals an invocation, sends the marshaled invocation
RMI adds two primitives to Java — remote objects and proxies to remote objects.
A remote object receives and executes calls that an invoker sends to it via a proxy. To
realize this functionality, RMI runs an invocation server, a registry, a distributed garbage
collector, and an activation server3 . Table 6.1 lists these servers and the mappings they
maintain. Chapter 2 gives an extended example of an RMI application that illustrates RMI’s
programming model.
RMI’s invocation server4 listens for invocation messages, looks up each invocation’s target
remote object, executes the invocation in the context of that remote object, and replies with
the result. An ObjID is a class whose instances are globally unique identifiers for remote
objects. The invocation server maintains a map of identifiers to remote objects. Proxies
embed their remote object’s identifier in each call they marshal. RMI’s invocation server
Definition 6.2.3. Exporting is the act of binding an identifier to a RMI remote object with
an invocation server so that it can receive and execute incoming, remote calls.
3
RMI’s activation server allows a server to export remote objects that hibernate (are stored on disk not in
memory) unless a client invokes them. MAGE does not support the hibernation of its mobile objects.
4
The invocation server is called the RMI server in the Java RMI documentation. For clarity, we use the
more precise name.
6.3. The MAGE Runtime System 120
When you couple a distributed programming model, like RMI, with a garbage collected
language, such as Java, you introduce the problem of remote references to locally dead
objects. A server’s garbage collector cannot simply collect remote objects when they are
locally dead, because some client may still be using them. Not collecting these remote
objects at all can lead to an object retention memory leak, because they may have no remote
clients. Java’s distributed garbage collector framework solves this problem by associating a
lease with each remote object. Each time a client unmarshals a proxy, it requests a lease
from the remote object’s server. Before that lease expires, the client must renew it, or the
6.2.3 Registry
that proxy from an RMI registry. The RMI registry (rmiregistry), which listens on the
To bootstrap an RMI application, the client and server must share an interface that
extends the Remote interface and defines a set of methods, and the client must statically
know the URL of a host that is running rmiregistry and has exported the named remote
MAGE modifies and extends the RMI runtime to handle mobile objects. In this section,
we motivate and explain each of the required changes. Table 6.2 summarizes the MAGE
services and the maps they maintain. The InetSocketAddress class wraps a IP address,
Service Map
MAGE registry id → InetSocketAddress
InetSocketAddress → MageRegistry
class server name → class-bytes
listener tag → result
VM port host → port
resource manager String → Object
The MAGE invocation server’s behavior is a superset of that of the RMI invocation server:
it must handle the movement of remote objects. Upon receipt of an invocation, the MAGE
invocation server must check whether the target mobile object is present, since another
invocation may have moved the mobile object after the current invocation was dispatched.
If the object has moved, the invocation server throws an exception, which restarts the find
phase at the invoker. Otherwise, it checks whether it is the invocation’s execution target.
If not, it unexports the mobile object from the invocation server, adds the mobile object
to the invocation, and forwards the invocation to the execution target. We describe the
Since RMI remote objects cannot move, the RMI DGC client need only renew each lease
with the DGC server that issued that lease. MAGE’s mobile objects introduce the problem
of notifying the DGC server of a mobile object’s current host. When a DGC client attempts
to renew the lease on a host that no longer hosts a mobile object, that host’s DGC server
informs the client that the object has moved. When so notified, MAGE DGC clients follow
their mobile object’s chain of forwarding pointers and update the DGC server to which they
will direct their next renewal attempt to their object’s current location.
6.3. The MAGE Runtime System 122
Sun’s Java tutorial gives the code for a class server, which listens for and responds to requests
for class definition, or class bytes [69]. Java’s marshaling, aka serialization, libraries can
annotate outbound objects with the URL of the codebase that contains class definitions
that do not exist at the unmarshaling host. The unmarshaler uses this URL to contact
the class server. In Java, such annotation is needed when a parameter passed to a remote
method is an instance of a class unknown at the unmarshaler. This occurs when a client
passes actuals that are instances of a local class that implements an interface or subclasses a
class in the target remote method’s signature, which the client and server necessarily share.
MAGE leverages these annotations to propagate the class definitions of mobile objects, as
map of ObjID identifiers to forwarding pointers. There is an entry in this map for each
mobile object that has either been invoked from or visited the machine on which the singleton
to remote MAGE registries in a map that binds an IP address and port pair to a proxy.
Upon startup, the MAGE registry reads an initial list of MAGE VMs into an in-
stance of HashSet<String>. This set tracks the universe of MAGE VMs. The com-
plement mobility attribute operator is defined in terms of this set, which it accesses via
a s t
(move o to T
, tag)
(o, tag)
ack
o at t
(i, tag)
r o executes i
The point of MAGE is to control object mobility. Often the mobile object o that is the
target of an invocation is found at s, not at the desired execution engine t ∈ T . The question
is how to move it to t. MAGE could either first explicitly move o to t or make the move
Figure 6.1 depicts a protocol that explicitly sends a move message. First, a sends an
explicit move message for o to s. The move message contains the T that a’s mobility
attribute calculated so that s can use it as an input in the application of o’s component
mobility attribute, if one is bound. It also contains a globally unique tag. To prevent a from
starving, the target t immobilizes o until it receives the invocation from a identified by the
tag. A component mobility attribute may select any t ∈ T or even override a’s T altogether,
so s must inform a which t was selected, with the message “o at t.” Then a makes an RPC
invocation on o at t, by sending the pair (i, tag) to t and awaiting the result r as shown.
The target t uses the tag to identify the invocation that frees o to move again. While o is
This solution requires a to block until it receives r and the addition of an explicit, distinct
move message to the invocation protocol, and six network messages. To prevent starvation,
it also requires that o be immobilized at t until a’s invocation arrives. Preventing starvation
6.3. The MAGE Runtime System 124
comes at a cost: what to do if the invocation never arrives? There are four responses:
1) allow starvation; 2) a could resend the invocation after a timeout if it does not receive
a result5 ; 3) free o after a timeout period; or 4) accept that o may simply be immobilized
indefinitely. MAGE’s current implementation uses response 4, because immobility does not
impact correctness and allows an application to progress, albeit at some performance cost.
Figure 6.2 depicts the protocol that results when the move is implicit to an invocation.
Here, we require a listener, as we do not wait to directly tell a which t was selected. First, a
acquires a globally unique tag and an associated future from its local listener l. A future
is an object that will hold the result of a future computation, here an invocation on o at
t [39, 60]. Then a sends its invocation together with the tag to s the host at which a found
o. The host s then marshals the mobile object o, builds the message (i, tag, o) and sends it
to t where i executes. The host t then sends the result r together with the tag to l. The
listener l uses the tag to put the result in the future identified by the tag.
A future is a mechanism that allows asynchronous RPC calls. When the caller invokes an
asynchronous RPC call that supports futures, the caller immediately receives a future rather
than blocking on the call. The caller is then free to perform other work in parallel to the
remote call. At any time, the caller can check the future to see if the result has arrived or
simply block on the future when the caller has exhausted the available concurrency [39, 60].
Thus, a future allows a to exploit the network latency of an RPC to perform other work
in parallel instead of simply blocking. If a has nothing else to do and wishes to make a
synchronous call, it simply immediately calls the future’s blocking method for acquiring that
result. The target execution engine forwards exceptions, if they occur through r. If, for
some reason, o never executes and nothing is ever returned, a will block indefinitely on its
future, just as the caller would do in a standard RPC call that never returned.
In addition to providing the parallelism of a future, this approach has other advantages.
The actor a’s interactions with l occur within an shared address space; they are memory
5
This approach is closely related to the general problem of RPC semantics in the face of failure, viz. the
choice among at-least-once, at-most-once, or exactly-once semantics.
6.3. The MAGE Runtime System 125
a l s t
tag?
tag
legend (i, tag)
(i, tag, o)
local call
message (r, tag) o executes i
reads and writes. Thus, although this approach requires the listener l, it requires fewer
network messages, three vs six; it does not require an explicit move message: nor must
it immobilize o while it waits for a’s invocation i, but instead can execute i immediately
upon o’s arrival. For these reasons, the current MAGE implementation uses a listener. The
By default, RMI’s invocation server listens at an ephemeral port assigned by the operating
system, to ease running multiple invocation servers on a single host. This causes no problems
for RMI since, by convention, an invoker bootstraps by downloading a proxy from the
rmiregistry running on that host. The rmiregistry binds to the well-known port
1099 and each proxy contains the port of its remote object’s invocation server.
When running multiple MAGE invocation servers on a single host, MAGE cannot simply
extract the invocation port from a proxy for the mobile object o, as RMI does, because of the
MAGE invocation protocol may require o’s current host to forward o to another invocation
server whose port is unknown to both o’s invoker and current host. To partially solve this
This discovery mechanism allows a client to specify a target location using only a host
6.3. The MAGE Runtime System 126
address and no port. When a MAGE invocation server receives an invocation whose target
is only a host address and it does not already know that host’s default port, it learns
the port at which that host’s invocation server is listening as follows: It contacts that
host’s rmiregistry to get a proxy to that host’s VM port server. That proxy supports
getPort() which returns the address of the default invocation server on the machine on
which the VM port server is running. This solution is partial because it designates one of
the n MAGE instances sharing a machine as the default invocation server, and does not
The MAGE resource manager is a subclass of Java’s Hashtable that implements Remote
and therefore allows remote queries and updates. The MAGE resource manager is loosely
typed: for maximum flexibility, it maps String to Object instances. A programmer nests
hash tables to store hierarchical data. Thus, a resource is anything that can represent itself
In Listing 6.1, looking up “CPU” returns a hash table that maps a host name to a
string containing that host’s load average. The application developer must have previously
Each JVM running MAGE publishes a resource manager. MAGE does not automatically
provide any resource information in its resource manager, instead leaving that task to the
API for communicating resource state or handle to a resource to a policy that a developer
6.4 Primitives
In this section, we first present the challenges in implementing MAGE’s mobile object and
proxy to the remote object, not the remote object itself. MAGE needs to support both
this behavior, when a mobile object is an actual, as well as marshal the mobile object
Static Fields In standard Java, a class and all of its instances share a single address space.
Thus, static fields, field defined on the class itself, not its instances, are a convenient
mechanism for sharing data across instances. Mobility complicates the story: the
instances of a class are no longer guaranteed to share an address space, and the class
definition itself must exist within every address space that contains an instance.
Direct References To move the mobile object o to t, MAGE marshals a clone of o, sends
that clone to t, unexports o, then updates the forwarding pointer for o to point to t,
thereby implicitly updating all local proxies for o. Local references to the instance of o
before it was cloned present a problem: any writes to this now dead clone are lost.
Initially, MAGE modified rmic, the RMI compiler, to produce MAGE proxies. In Java 5,
RMI deprecated rmic and replaced it with the dynamic generation of proxies that support
the signatures defined by an application’s remote interface, but delegate the bulk of their
reflection to make the remote call. This abstraction simplified the implementation of MAGE
In RMI, the Remote interface defines only a type recognized by rmic and now by the
dynamic proxy generator6 to signal the creation of a proxy. MageMobile defines the bind
methods that MAGE proxies must support. Ideally, MageMobile would obviate Remote
6
The class magesun.rmi.server.Util in MAGE.
6.4. Primitives 128
in a MAGE application, but that would require changing the dynamic proxy generator to
recognize MageMobile instead of, or perhaps in addition to, Remote. This work, and its
A language’s support for mobility ranges from strong to weak. Under strong mobility, both a
mobile component’s code and execution state moves; under weak, only a mobile component’s
code moves [16]. On this continuum, Java is fairly weak, since it does not move stack or
ment AppIface and inherit from Figure 6.3: MAGE Mobile Object Class Diagram
MageMobileObject, as shown in
programmer to lock the mobile object to a host as well as supporting the binding of
6.4. Primitives 129
mobility attributes directly to a component (Section 3.6); and 2) it defines a type and
a field that MAGE uses to control the marshaling of a MAGE mobile object. RMI uses
marshaling behavior. When a remote object is marshaled, its associated RMI proxy class
For a mobile object to move, it must be marshaled, not its proxy, so MAGE must override
this behavior. However, a MAGE mobile object potentially moves only when it is invoked,
not merely referenced. Thus, when a mobile object is a merely a parameter in a remote call,
MAGE must support RMI’s default behavior and marshal that mobile object’s proxy, not
the object itself. MAGE uses MageMobileObject and its move field to distinguish these
two cases. While a mobile object resides on a particular host, its move field is false. When
MAGE marshals a mobile object for a move, it sets its move to true. This field remains true
in the now-dead version of the mobile object left behind by the move. Threads in active
mobile objects use this fact to stop and release the object for garbage collection.
To complete the discussion of Figure 6.3, we note that RMI’s RemoteObject class im-
plements the java.lang.Object behavior for remote objects and RMI’s RemoteServer
class is the common superclass to server implementations. AppIface denotes the application
interface that defines the remote methods that instances of AppMobileClass can receive.
In Java, a static field is a field shared by all instances of a class in an address space.
Obviously, maintaining field sharing becomes costly when an object can move and instances
can move among address spaces. By default, RMI does not marshal static fields, thereby
punting this sharing problem to the programmer. If the programmer is sufficiently motivated,
she can write and exclusively use getters and setters that broadcast updates to VMs that
are hosting an instance of the class, write custom marshaling via Java’s readObject and
writeObject methods to track the set of VMs where instances exist, and roll her own
replication mechanism. MAGE follows RMI’s lead, and leaves the handling of static fields in
mobile objects to the programmer. By default, MAGE objects exist in only one namespace
at a time.
6.4. Primitives 130
Like an RMI remote object, a MAGE mobile object is kept alive by proxies held by its
clients, renewing their leases with the DGC server of the mobile object’s current host. When
a MAGE mobile object moves, it unexports itself, which unregisters it both from a VM’s
invocation and DGC servers on the VM it is leaving7 . On all systems, other than a mobile
object’s origin host, access to that mobile object is mediated by a proxy acquired from the
RMI registry, so this action removes all references to the discarded copy of the mobile object
on that VM, leaving it eligible for collection by the local VM’s garbage collector. A thread
running on a mobile object’s origin host could hold a reference to such a discarded clone,
and violate MAGE’s invariant that a mobile object exist in only one namespace at a time.
MAGE does not track and therefore cannot replace local references with proxies. Ideally, the
compiler would warning about a local reference to a mobile object. Currently, MAGE relies
on the programmer to respect the convention that they should eschew direct, non-proxy
references to mobile objects8 . To allow a mobile object’s clients time to catch up with a
mobile object after it has decamped to a new host, MAGE pins mobile objects, thereby
making them unreapable for one lease renewal period, which defaults to 10 minutes. This
The remote procedure call paradigm, of which RMI is an instance, relies on proxies, or stubs,
to marshal calls at the client for writing to the network. A proxy generator creates these
proxies automatically, either statically via the now deprecated rmic compiler prior to Java
5 or dynamically since Java 5. In both cases, remote proxies are generated for classes that
implement the Remote interface. Thus, RMI’s Remote interface defines remote methods;
it designates interfaces for which a proxy must be generated. Java remote methods must
Unlike an RMI proxy, a MAGE proxy, in addition to remote methods, defines local
methods that bind mobility attributes to the proxy. Since having these methods throw
7
To unexport itself, a mobile object must acquire its move lock.
8
More empirical investigation is needed to determine whether local references are a problem in practice.
6.4. Primitives 131
RemoteException does not make sense, MAGE defines them in the interface MageMobile
that does not extend Remote, as shown in Figure 6.4. MageMobile also defines a move
method, whose purpose is to provide a hook on which to bind mobility attributes to handle
system shutdowns. The idea is to make it easier for an application programmer to write
a facility that, upon receipt of a system shutdown alert, calls move on all affected mobile
objects.
In Figure 6.4, the shared application-defined interface AppIface allows client and server
Figure 6.4 shows where methods are declared, not necessarily defined or overridden. The
and invokeRemoteMethod. The former method defines some of the local method calls
declared by Object, like toString() and equals(); the latter method delegates the
remote call to UnicastRef.invoke() which marshals the call, sends it to the remote
return type is FutureMageCall or, when MageMobile declared the passed method, to
invoke invokeMageMethod, which implements bind, rebind, and unbind. The class
a MAGE call (Section 6.5.4) if a mobility attribute is bound to the proxy, or a standard
implement futures (Section 6.3.5). When the return type of an incoming call is a descendant
invokeFutureMethod method to handle the call. This method grabs a thread that makes
the call on behalf of the calling thread, which is free to immediately return. When the remote
call returns, the FutureCallHandler thread assigns the result, including exceptions, to
the future. The calling thread can check this future at any time to see if the call has returned,
or, when it has no further concurrent work to do, it can block on the future, as specified by
java.util.concurrent.Future<V> [70].
The cost of supporting futures in MAGE is the cost of invoking the isAssignableFrom
6.5 Operations
In this section, we discuss the implementation of each of the classes of operations that MAGE
introduces.
6.5.1 Find
Chapter 5 presents the design of MAGE’s directory service, which uses forwarding pointers.
MAGE caches a forwarding pointer to every mobile object that has ever been invoked from
or has visited a host in its MageRegistryImpl. An invoker must download a proxy for
a mobile object on which it wishes to invoke operations from that mobile object’s origin
server. When the proxy is unmarshaled, MAGE extracts the mobile object’s identifier and
adds an entry to the cache that points to the mobile object’s origin server. When a mobile
6.5. Operations 133
object arrives at a host and is locally exported to receive remote calls, MAGE either adds or
overwrites its entry with a self-loop, a forwarding pointer to the local host. When a mobile
object departs, MAGE overwrites the mobile object’s entry in MageRegistryImpl with a
The MageRegistryServer class, the local component of the MAGE registry (Sec-
tion 6.3), implements a find method that straightforwardly walks the chain of forward-
ing pointers. The MageRegistryServer first looks up the target mobile object’s last
known location in the local MageRegistryImpl cache, then contacts that location’s
forwarding pointer to the next MageRegistryImpl instance in the chain or signals that
the target component is collocated with it by replying with its own location.
6.5.2 Bind
Mobility attributes bind to proxies to allow different invokers to apply different migration
policies to a single mobile object. Mobility attributes also directly bind to mobile object
to impose a shared policy on all invokers. Bound attributes decide where invocations on a
client-side mobility attribute binding with a mobility attribute field and a accesser, mutator
pair. Component mobility attributes are similarly implemented, but by the base class of all
the programmer must first call unbind, then bind or use rebind.
Mobility attributes define two sets, a set of valid locations at which to receive an invocation
and a set of execution targets. Mobility attribute operators apply set operations, such as
union, to these sets. Mobility attribute operators augment the set operations with LEFT
6.5. Operations 134
and RIGHT binary operators that just return the named operand (Section 3.5 introduces
these operators).
contains fields to store operands and the S and T operators over those operands. As
method recurses into the operands. The targets method differs from the starts method
in Listing 6.2 only in that it passes opT to apply. The apply method performs the specified
operation. Essentially, apply is a switch statement over the set of operators. Complement
is defined against a universe. Thus, each MAGE server must maintain a set of all MAGE
servers, which apply uses to implement complement. Currently, this list statically defined
6.5.4 Invocation
1. It adds new messages, notably MageCall and the accompanying MAGE invocation;
and
We begin with the format of the network messages. We then turn to invocation sequence
diagram, which we use to frame the discussion of tasks assigned to the various classes that
generate and handle the messages used. On the client, the bulk of the implementation resides
In UnicastRef, the method mageInvoke loops over finding the mobile object, then
attempts to make the invocation. If either the find or the invocation fails, because the object
moves, mageInvoke restarts the loop, until a configurable starvation bound is exceeded.
in Transport. This method unmarshals the header of the incoming MAGE invocation,
unmarshals and exports the mobile object if it is in the invocation stream, then applies the
the invocation or unexports and forwards the mobile object to its execution target. We
close with a discussion of the algorithms to realize movement in the presence of concurrent
invocations. The listener portion of the protocol was previously discussed in Section 6.3.5.
1. Java objects cannot move without their classes, which may not be defined
2. Direct local calls on a mobile object are invisible to MAGE, so MAGE can
mediated operation on itself, are restricted to void methods that lack in-out
parameters.
6.5. Operations 136
Client Host
Client Port
Operation
Transport
Protocol
Version
Magic
Figure 6.5: JRMI Header
Parameters
Stub Type
Object ID
Operation
Call Data
Custom
Header
JRMI
(a) RMI Invocation
Parameters
Stub Type
Object ID
Operation
Result To
Call Data
Call Tag
Custom
Targets
Header
Object
Mobile
JRMI
(b) MAGE Invocation
Message Formats
Java’s RMI can run over various protocols, notably tunneled within HTTP and directly on
TCP/IP. Figure 6.5 depicts the format of RMI’s transport header9 . The Protocol field is
Call, DGCAck, or Ping. The latter two operations are used by Java’s distributed garbage
collection service. The bracketed fields — Client Host and Client Port — are not sent
when the protocol is SingleOp. MAGE uses Java’s JRMI header unchanged, but adds
Figure 6.6 presents the format of the invocation messages that RMI and MAGE use.
MAGE adds four fields to the RMI invocation message — Targets, Call Tag, Result To,
and Mobile Object. The targets field stores the client’s target set created when the client
applied its mobility attribute. Component mobility attributes (CMA), which bind mobility
attributes directly to the component, uses the targets field as an input to the application of
the component mobility attribute. The MAGE listener service requires the “Call Tag” and
“Result To” fields. After the call executes on a server, that server uses the “Result To” field
to determine where to route the result. The listener collocated with the invoker uses the
call tag to route the result to the invoking thread. Finally, the mobile object field stores a
Figure 6.6a and Figure 6.6b are separated into three parts according to which class
tcp.TCPTransport handles the JRMI header in both RMI and MAGE. Transport
handles the Object ID field which identifies the remote, or mobile, object on the receiving
server. When receiving a MAGE call, it also handles the additional MAGE fields. Finally,
UnicastServerRef determine which stub type to use, then use the operation field as a
RMI’s custom call data field allows an application to add custom call data to its
invocations. To add custom call data, the programmer must override UnicastRef’s
MAGE does not use this field because it is accessed too late in the processing of an invoca-
tion. In particular, the mobile object, if sent, must be instantiated and exported before it
can receive calls. The custom call data field is not processed until after the call has been
dispatched, at which point it is too late to export the target mobile object. It is also more
efficient to handle the MAGE fields as early as possible when processing a call.
All marshaled objects, in particular those in the parameter and mobile object fields, are
annotated with the URL of the invoker’s classserver. If a class is not defined locally,
6.5. Operations 138
Call Tag
Header
Header
Return
Return
Result
Result
JRMI
JRMI
Type
Type
(a) RMI Return (b) MAGE Return
Figure 6.7 depicts the formats of the RMI and MAGE invocation returns. A MAGE
listener uses the call tag field to either notify a sleeping invoker or to place the result where
Figure 6.8 contains the sequence diagram for the invocation phase of the FI, the MAGE
invocation protocol. From left to right in synopsis, the client a invokes its target mobile
object o found at the server s ∈ S, the set of valid starting locations. The server s then
unexports o, adds it to the invocation, and forwards both to the target server t ∈ T , the
set of target execution hosts. The server t unmarshals the mobile object and exports it,
before dispatching the call to it. The chain of local calls on t that eventually reaches
MageMobileObject, the ancestor of all mobile objects in MAGE, represents this sequence
of events.
From left to right in detail, the ApplicationClass contains the running code that invokes
a method on the mobile object o by invoking a method of the desired name on Proxy.
In JDK 1.5, the Proxy class is dynamically generated for classes that implement inter-
faces that are descendants of Remote. It delegates all calls to its InvocationHandler,
MageInvocationHandler
MageMobileObject
UnicastServerRef
ApplicationClass
TCPTransport
TCPTransport
UnicastRef
Transport
Transport
Proxy
Figure 6.6b
Figure 6.6b
legend
local call
message Figure 6.7b
2. Local MAGE method calls, such as bind, which sets the MageInvocationHandler’s
FutureMageCall; and
The local MAGE methods are documented in Section 6.5.2. Future calls, documented
in Section 6.4.2, simply use a thread pool to make synchronous MAGE remote calls.
6.5. Operations 140
method wraps its call to executeCall in a loop and a try-catch block that restarts the
call, subject to MAGE’s starvation constraint, in the event that the target mobile object
mobile object has not moved, and applies the mobility attribute ma by calling apply on
line 4. In Algorithm 6.2, the apply method first checks that s ∈ S, then generates T . If
the execution fails, Algorithm 6.1 follows the chain of forwarding pointers (the find phase of
FI) to locate the target mobile object o on line 7. Each time mageInvoke must find the
Algorithm 6.3, implemented in StreamRemoteCall, actually sends the call and waits
for a reply. It first acquires a call tag from its listener, then marshals the call, before
blocking on listener’s getReturn on line 5. When it receives an invocation return, the listener
6.5. Operations 141
unmarshals the result, then returns from getReturn to awaken the invoking thread. If the
updates its forwarding pointer, which is realized as a LiveRef instance that contains the
IP address and port of o’s new location, thus collapsing the invoker’s chain of forwarding
pointers.
the target mobile object o could move before the invocation reaches it. However, this race
is not actually a problem: if o moves, it will not be at the server s when the invocation
invoker. When mageInvoke catches either of these exceptions, it restarts the invocation
receives a message, it processes the JRMI header, and identifies the message as a MAGE
depicts serviceMageCall. On line 1, s extracts the named data from the invocation i.
not local, then either there was an error, or o moved before the i reached s and the invoker
calls applyCMA to apply o’s component mobility attribute, if one is bound, on line 11.
The call count of o tracks the number of threads executing in o. On line 12, s checks
whether there was a waiting mover and increment o’s call count on lines 26–30, before
We are considering the case in which s forwards o, which it accomplishes on lines 13–24.
6.5. Operations 143
The server s first checks whether o has been immobilized. Then it attempts to acquire o’s
move lock to prevent any new threads from entering o by causing attempts to increment
o’s call count to throw MovingException on line 28. After setting o.mlock, s waits for
the threads already in o to drain at line 21. There can only be one mover at time, so after
a thread has acquired a mobile object’s mlock, subsequent attempts to acquire it throw
MovingException on line 17. Note that the move lock is needed only for side-effects
confined to the mobile object itself, since other side-effects written by a thread running in
Server t’s TCPTransport instance also uses serviceMageCall to handle the incoming
invocation. This time the mobile object is in the invocation stream, so t exports o on line 9.
This export atomically sets o’s mlock to 0 and increments its call count to prevent the mover
from starving as could occur if another thread moved o before the client a could execute its
The method mageDispatch calls the method named by the invocation o via Java’s reflection
facility. It differs from it RMI progenitor in that it must handle both direct and indirect,
listener mediated returns. In Figure 6.8, the invocation is eventually dispatched on the
application’s mobile object, which MageMobileObject, the ancestor of all mobile object
classes, represents.
When more than one invocation for the same object arrives simultaneously, one of the
invocations will win the race to lock the object on line 13. Whichever does will unexport
the mobile object and move it. Each loser will report a NoSuchObjectException back
6.5. Operations 144
to its invoker.
A MAGE mobile object cannot move while it is has in-flight invocations that threads
executing within it sent. MAGE derives this limitation from Java’s weak mobility support:
Java does not support thread migration. If it did, the MAGE listener could forward the
results of in-flight invocations. So long as all calls made on a mobile object are proxy-
mediated remote calls, the object’s call count will be nonzero and will prevent that object
from moving until all in-flight invocations return and the call count goes to zero, as described
in Algorithm 6.4.
Section 6.4.1. The problem occurs because a thread can hold a direct reference to a mobile
object and thereby prevent the copy left behind after the object moves from being reaped.
These calls do not increment the object’s call count. Just as with the garbage collection
problem, MAGE relies on convention to mitigate this problem: programmers must avoid
A MAGE mobile object moves itself by calling one of its own methods via a proxy whose
mobility attribute picks a target set that does not include the current host. The invoking
thread makes its call as usual and blocks in the listener. The host to which the object moves
executes the call as usual, and forwards the result to the old host’s listener. The problem is
writes to fields in the dead clone. Any such writes must be forwarded to the mobile object’s
new host. When the method is void, side-effect free, and lacks in-out parameters, there is no
problem: the invoking thread does not write to fields in the dead clone. The invoking thread
can, of course, write to any other location in the application, such as a different mobile
object.
When a mobile object moves, MAGE sets its moved field to true to marshal the mobile
object itself and not a proxy to the mobile object, as occurs when the mobile object appears
in a parameter list. The invoking thread could check this field, realize that the mobile
object has moved and call a “fix-up” method on its proxy defined by MageMobileObject
to forward the result to the mobile object. Of course, the result may not change the mobile
object’s state, in which case it can be dropped, or it may simply return to the remote invoker
6.6. Limitations 145
that invoked the thread that caused the mobile object to move, in which case nothing special
need be done. At present, MAGE relies on the programmer to restrict herself to self-moves
6.6 Limitations
The current implementation of MAGE, like all implementations, is not ideal. Since MAGE
was implemented, Java added its JMX API for management services [68] that obviates the
MAGE resource manager. MAGE would better integrate with the Java ecosystem if it
MAGE’s class server runs on its own port, rather than sharing a port with a single
listener that multiplexes its messages with the other services. It should be merged with the
others. Currently, many of MAGE’s services run as RMI remote objects. MAGE’s efficiency
and scalability would be improved if they were directly integrated into MAGE framework.
mediated references to a mobile object and making direct, local calls on it. One possible
mobile objects. This mobile object factory would return proxies on the origin host. The
produced class private. This is not feasible for MAGE, since applications need to subclass
MageMobileObject. Instead, the MAGE mobile object factory could track those objects
that it creates and MAGE could refuse to move objects that it did not create.
Each MAGE server learns about other MAGE servers statically, via a configuration file.
A dynamic broadcast mechanism for announcing new and departing MAGE servers should
Currently the MAGE registry has two layers — the RMI registry and a RMI Remote
object that implements the MAGE registry extensions and must be downloaded from the
RMI registry. MAGE’s registry functionality should be merged into a single service.
When a mobile object moves before an invocation reaches it, Algorithm 6.1 catches the
6.7. Summary 146
resulting exception, restarts the invocation protocol, and wastefully re-marshals the call.
Further, its implementation abuses Java’s exception handling mechanism to signal re-starting
the invocation rather than an error [88]. A better solution would be to handle the problem
at a lower level via a return type, not an exception, and avoid the redundant work.
6.7 Summary
In this chapter, we have described the implementation of MAGE. We compared the MAGE
runtime to the RMI runtime, which MAGE extends. We described the implementation
of MAGE’s three primitives, followed by the operations that MAGE allows over those
primitives.
147
Chapter 7
Evaluation
True genius resides in the capacity for evaluation of uncertain, hazardous, and conflicting
information.
For mobility attributes to be at all practical, they must not impose too much overhead
upon their user. In this chapter, we present two sets of benchmarks that compare MAGE
against RMI:
must eat and exploit mobility to satisfy their hunger. We describe a MAGE-based solution to
this problem, which models philosophers as active mobile objects contending over chopsticks,
also modeled as mobile objects. Activity and chopstick contention make this application a
particularly demanding test of the robustness of the MAGE framework. We then describe
and evaluate various different migration policies that philosophers can use to acquire food.
consisting of three machines: 1. a dual-processor Intel 500 MHz Pentium III with 512MB of
7.1. Baseline Measurements 148
RAM, 2. a dual-processor Intel 2.80 GHz Pentium 4 with 1GB of RAM, and 3. an Intel Xeon
2.80 GHz with 2GB of RAM. Each machine runs Linux 2.6.20. We use Sun’s JDK 1.5.0 07.
The contributions of MAGE include a rich set of expressions for defining arbitrary mobile
object and invocation placement policies, isolating those policies, and composing those
policies (Section 1.3). The expressivity and separation of concerns MAGE offers is not free.
These measurements quantify the overhead of the MAGE programming model. We present
D’Agent [36], here because, unlike MAGE, they make no attempt to isolate layout decisions.
language: They are lower-level and thus impose less execution overhead at the cost of a
higher cognitive load on the programmer when writing and maintaining code.
No standard benchmarks or test suite exists for the programming models most closely
related to MAGE (Chapter 8). Indeed, the related work all concentrates on illustrating their
programming model using code snippets drawn from toy applications. Only SATIN [123]
reports any quantitative measurements at all — the SLOC and bytes of the SATIN
world!” application on two machines, and the time to send and deploy an Ogg Vorbis codec.
The SATIN authors offer no baseline against which to compare these numbers.
We begin with invocation micro-benchmarks because other costs will be either amortized
over the life of an application (i.e. class-loading) or are specific to a particular application
or environment, such as the cost of a policy that collocates an object with a resource like
a printer or a database. Thus, rather than try to measure the cost of all the functionality
MAGE can provide, we measure the overhead it imposes when it realizes RMC and the
7.1. Baseline Measurements 149
classic invocation paradigms — RPC, COD, and REV1 . Our goal is to demonstrate that
MAGE’s qualitative benefits do not come at too high a quantitative price. We include
Java RMI in the invocation benchmarks as a baseline for comparison because (1) Java RMI
is a well-known, standard mechanism; (2) the difference between Java RMI and MAGE
RPC illustrates MAGE’s overhead in the absence of mobility; and (3) other researchers
can multiply these MAGE micro-benchmark results against the ratio of the performance of
Java RMI in their environment to the Java RMI performance reported here to estimate how
The execution of a function call naturally divides into the overhead of invocation
mechanism and the work done by the call. The work a call does is application specific and
can take arbitrary time. Here, we seek to measure the overhead of the MAGE invocation
integer. As a result, they shed no light on the question of whether the overhead of the MAGE
return values is an easily duplicated and calibrated proxy for work. Thus, Section 7.1.2
uses marshaling of increasingly large return values to show that, while MAGE’s overhead
is not constant, it is a declining fraction of the total cost of an invocation as the work per
invocation increases.
MAGE adds three principal sources of overhead to a Java RMI invocation: the time needed
to
1. evaluate the mobility attributes bound to an invoker’s proxy and directly to the
2. marshal the fields MAGE has added to the invocation message; and
3. manage mobility — specifically, a) move a mobile object, b) handle the possibility that
1
These models were introduced and described in Chapter 3.
7.1. Baseline Measurements 150
the target mobile object has moved since the invocation was sent, c) collect garbage,
Item 1 — the time to evaluate a mobility attribute — can take arbitrary time, especially
when that mobility attribute interacts with its environment via the resource manager. Thus,
we employ the attributes tailored for each invocation paradigm. To minimize the cost of
mobility, we statically deploy the test class. Since we do not need to bind mobility attributes
directly to mobile object to model the above invocation paradigms, we do not bind mobility
attributes directly to mobile objects. To avoid the overhead associated with items 3b and
3c, we restrict ourselves to single-threaded benchmarks, and we do not run the experiments
Listing 7.1 contains the mobile test class, BallImpl. Because our focus is the cost the
MAGE invocation infrastructure, this class does almost no work: it has a single integer
Cold Warm
Invocation Invocation Invocation
Paradigm Time (ms) Time(ms)
JAVA RMI 2.03 1.28
MAGE RPC 12.69 3.33
COD 123.32 10.30
REV 124.27 12.37
RMC 150.45 13.35
For COD, an instance BallImpl migrates to the invoker’s host. Once a test object
arrives, the incr method is invoked and the results are returned to the invoker via the
listener. For REV, we do the reverse. A local instance of BallImpl migrates to the remote
host by instantiating a new clone at the remote host and discarding the old clone at the
local host. The result is sent back to the local host. RMC is similar to REV except that the
The measurements are contained in Table 7.1. We give cold and warm invocation times
in the second and third columns, respectively. The reported numbers for both are an average
of 10 runs. For cold, each run sets up a fresh server, downloads a fresh proxy, then times a
single invocation. Thus, the cold invocation times show the one-time startup cost of priming
the MAGE engine — loading the CPU and disk caches with relevant code and data as well
as the cost of starting a connection thread that unmarshals and dispatches the invocation
on the server. For the mobile paradigms, the startup cost to move the definition of the
BallImpl to the target execution JVM dominates the total mean time.
The warm benchmarks set up the server, download a proxy, and make an initial call
whose time-to-completion is ignored, before timing 10 consecutive calls. Dropping the first
call approximates amortizing its cost without requiring a large number of runs. Thus, the
warm times give a more accurate representation that MAGE applications will experience.
Further, it is much easier to gather statistically significant data from long running servers.
We can see from Table 7.1 that the time reported for MAGE’s implementation of
the well-known distributed models. COD, REV, and RMC all move BallImpl prior to
7.1. Baseline Measurements 152
executing incr. Thus, it is not surprising that their mean total time exceeds that of MAGE
RPC, the immobile case, by an order of magnitude. COD is the fastest because its return,
although listener-mediated, uses TCP/IP loopback and is entirely local2 . REV is faster
than RMC because the arriving object is registered with the target invocation server, incr
is immediately executed, and the return is directly back on the socket used to deliver the
invocation, unmediated by the MAGE invocation listener. RMC comes in last because it is
When comparing a Java RMI call against a MAGE RPC call, we see that MAGE imposes
overhead of 160% on a vanilla Java RMI call. To explain this delta, I ran the Java RMI and
MAGE RPC invocation benchmarks 100, 000 instead of 10 times each and ran the YourKit
Java Profiler [121] against the results. The cost of marshaling accounts for most of this
overhead. MAGE adds four fields to the Java RMI invocation header, of which three are
route the result as a String, and the mobile object itself. At the client, a MAGE invoker
spends a factor of 3 more time than an RMI invoker to marshal an invocation. The MAGE
server, however, spends still more time and is the bottleneck: the MAGE server spends a
factor of 4 more time waiting to unmarshal and unmarshaling the invocation than the RMI
1
server, slightly more than 2 its total time. MAGE RPC’s mean time-to-completion is 260%
3 1
that of Java RMI. Thus, 4 of 2 or 38 (260% = 13
5 ) = 39
40 = 97.5% is unmarshaling overhead
97.5%
at the server. As a fraction of total overhead, 160% = 61% accounts for the majority of
MAGE’s overhead. Evidently, MAGE’s implementation could benefit from the same sort
of optimizations that have been proposed for RMI, in particular marshaling libraries that
Of the remaining and 160% − 97.5% = 62.5% of MAGE’s overhead, profiling reveals
that MAGE pays, over and above Java RMI, for the cost of 1) string handling in the
application of mobility attributes, 2) ensuring that sockets acquired from the socket pool
are still alive by pinging the server-side, and 3) working around Java’s partitioning of the
2
MAGE could decrease this cost still further by optimizing for collocation as proposed at the close of
Section 6.1.
7.1. Baseline Measurements 153
table in which it stores server objects that remote clients can invoke (ObjectTable). For
1
item 2, MAGE clients spend 40 of the mean total time waiting for replies to their ping vs 0,
i.e. unmeasurable noise, under Java RMI. Prior to Java 5, the ObjectTable was global
within a JVM. With Java 5, Sun partitioned remote objects by invocation listener port, so
that the clients of one listener could not invoke operations on remote objects exported at
another listener within the same JVM. A mobile object may create a new invocation listener
when it arrives at a server whose port is unknown to the proxies of existing clients. To work
around this issue, MAGE searches the object table globally, at measurable cost.
Like almost all code, MAGE would obviously benefit from optimization. For instance,
the set of hosts is likely to change slowly and predictably enough to be represented with
bit strings. The current implementation focuses on being robust and maintainable. It has
been written with a eye to Knuth’s dictum — “We should forget about small efficiencies, say
about 97% of the time: premature optimization is the root of all evil.” [51] — perhaps with
Is the invocation overhead MAGE imposes independent of the work done by an invocation?
The next benchmark seeks to shed light on this question. Marshaling is a simple example of
generic work. Moreover, MAGE is built on top of Java RMI, so it uses the same marshaling
Figure 7.1 shows how MAGE’s overhead declines as the marshaling cost of a call increases.
In this experiment, we return an increasingly large ArrayList whose elements are instances
of a class that consists of four strings whose length is normally distributed about 40 characters,
If the MAGE overhead were independent of the work an invocation does, it would take
a fixed amount of time and thus be a fast decreasing fraction of the time-to-completion of
a MAGE invocation as the size of the returned ArrayList increases. Table 7.2 records
3
This benchmark was inspired by a similar benchmark posted at http://daniel.gredler.net/2008/
01/07/java-remoting-protocol-benchmarks/.
7.1. Baseline Measurements 154
400
Java RMI
MAGE RPC
300
average time−to−completion (ms)
200
100
0
µ(mage)−µ(rmi)
Elements µ(mage)
25 0.09098111
50 0.26457409
100 0.32884892
150 0.25898509
250 0.32108809
500 0.21121683
1000 0.15482159
2500 0.14406123
5000 0.12072428
Table 7.2: Mean MAGE Overhead Relative to RMI as Fraction of Total Time.
7.2. Peripatetic Dining Philosophers 155
the mean overhead of MAGE relative to RMI as a fraction of MAGE’s mean total time.
As Table 7.2 makes clear, the MAGE overhead is not fixed, so it is not independent of the
To exercise the MAGE framework and to illustrate the flexibility and concision of the
migration policies it can express, we define “peripatetic dining philosophers,” a novel variant
of the dining philosopher’s problem that requires mobility. We describe the implementation
of our solution, which requires active mobile objects. We then present and compare a variety
of migration policies, against both a fixed and changing backdrop of resource production.
Definition 7.2.1 (Dining Philosophers [25, 17]). Around a circular table, n philosophers
rest, eat, and think. Each philosopher needs 2 chopsticks to eat, but there are only n
chopsticks, one between each pair of philosophers. The dining philosophers problem is to
1. deterministic;
2. concurrent;
4. fair;
5. bounded; and
6. economical.
Remark. “Bounded” means that both the number and size of messages in transit is finite;
economical means that a philosopher sends a finite number of messages in each state —
We can capture the arrangement of philosophers and chopsticks in a ring. Figure 7.2
c0
p0 p1
c1
The dining philosophers problem models resource allocation in the presence of cycles in the
resource graph: its philosophers are agents that require forks, a set of shared resources, whose
cardinality is classically but not necessarily two. It does not model resource consumption.
What if philosophers actually needed to consume food in order to think? What if one
fork were a streaming data source, like traffic crossing a backbone router, the other fork
were an encrypted channel to the NSA, and the philosopher’s food was the CPU required
to forward a filtered version of the stream? In terms of the metaphor, we can replace the
table around which the philosophers are seated with a set of cafés. In this new problem,
philosophers may wish to move from one café to another, depending on food availability.
problem is to satisfy the constraints of the dining philosopher problem, then maximize work
3. Both philosophers and chopsticks can move from one café to another; and
Remark. In contrast with the Evolving Philosopher Problem [53], the ring in which philoso-
phers and chopsticks alternate does not change under peripatetic dining philosophers.
Maximizing work per unit time entails optimizing the layout of philosophers onto cafés,
A philosopher can only work (think), i.e. perform filtering for the NSA as described
above, when it has the requisite resources, viz. forks. Thus, we use the count of the number
of times a philosopher enters its think phase as a proxy for the work it does.
Time-to-completion t, work per unit time w, and total work are related as follows:
wt = W (7.1)
Thus, given a time budget t, maximizing w maximizes total work W ; given work to do
of code mobility. Philosophers can now differ in their appetites; that is, how much food
they consume when they are hungry. Cafés can produce food at different rates. When the
demand for food at a particular café is too great, a philosopher has a reason to move to
another café.
this family for each café; one contains food production rates, the other starting amounts of
food. Four vectors characterize each philosopher: one for consumption rates, starting café,
time required for thinking, and the number of servings needed to sate the philosopher. The
cost to move a chopstick and the cost to move a philosopher define two more dimensions.
Finally, another group of problems is formed by producing each of these vectors with a
In this chapter, we restrict ourselves to problem instances in which the vector of starting
amount of food at each café is all zero and the philosopher consumption rate, time-to-think,
Under peripatetic dining philosophers, the philosopher ring is mapped onto the set of
cafés. Those mappings differ in terms of the number of neighboring philosophers in the ring
that share a café. When two philosophers who share a chopstick in the ring share a café,
7.2. Peripatetic Dining Philosophers 158
their chopstick can remain at that café. When neighboring philosophers are at different
café’s, they must send their shared chopstick back and forth between the two cafés. Clearly,
chopstick acquisition is more expensive when the philosophers that share a chopstick are not
collocated. Thus, any philosopher migration policy should seek to collocate philosophers
Dining philosophers is a generic and abstract problem that elucidates problems that arise
when attempting to realize mutual exclusion. Systems composed of mobile objects also need
dining philosophers does appear to strain the metaphor — why would anyone send chopsticks
back and forth between two cafés? — until one asks why would anyone share chopsticks
in the dining philosopher problem? In future work, we intend to consider modifying the
minimize time-to-completion.
Example
Imagine that the two philosophers in Figure 7.2 have access to two cafés, A and B. Both
café’s start with 0 servings. A produces 1 serving/s, while B produces 2 servings/s. The
two philosophers must each think, and therefore eat, 10 times. Both eat 2 serving/s.
If the philosophers start and remain at A, they will complete their work in 20s and 40
servings will go to waste at B. If the philosophers start and remain at B, they will complete
their work in 10s and 10 servings will go to waste at A. Since the philosophers do not move,
In practice, the cost of chopstick and philosopher movement is greater than zero. As-
suming movement were free, however, the philosophers minimize their collective time-to-
completion when they dine at separate cafés. If one philosopher starts and remains at A
and the other at B, then the philosopher at B will finish in 5s, while the philosopher at A
finishes at 10s. Café B continued to produce food while the philosopher at A waited for
Collectively, the philosophers require 20 servings. The two café’s produce 21 servings in
7.2. Peripatetic Dining Philosophers 159
p0
c0
p5 p1
c1
1 meal/s
c5 c2
p4 p2
c3
c4 p3 2 meal/s 3 meal/s
7s, which bounds time-to-completion from below. After the philosopher at B completes its
work in 5 seconds, the philosopher at A still need to eat 5 servings. If it remains at A, sating
its hunger will take an addition 5s, as in the scenario above. If it moves to B, it can sate its
hunger in 3s. Under this migration strategy, the time-to-completion is 8s and 4 servings are
wasted.
Of course, when the production rate of the cafés is fixed, as in this example, mobility
reduces to optimal deployment, with some latency for discovering the café production rates.
Mobility and migration policies become essential when café production rates change over
time. Next, we use MAGE to empirically investigate the peripatetic dining philosophers
The peripatetic dining philosopher problem boils down the layout problem for which MAGE
was designed: an optimal layout of philosophers maximizes work per unit time.
The MAGE implementation runs six philosophers. Figure 7.3a depicts the standard
dining philosopher ring for six philosophers. The philosophers all request the chopstick to
their right, then left, except p5 who breaks the symmetry by requesting the chopstick to his
left, c0 , before c5 . Each philosopher must eat 1 meal each time they are hungry. Figure 7.3b
depicts the cafés, each labeled with their rate of food production. Note that each second,
7.2. Peripatetic Dining Philosophers 160
the cafés collectively produce enough food to sate all six philosophers, assuming the number
In Listing 7.2, rounds and count are integers; self is a MAGE proxy to an in-
attribute to eat(). When a philosophers calls its eat(), the mobility attribute bound to
it decides at which café that philosopher should eat. In Sections 7.2.3 and 7.2.4, we describe
and analyze the performance of various migration policies, realized as mobility attributes
With the exception of moved, Listing 7.2 is a standard realization of the state loop in
a classic formulation of dining philosophers. Here, the philosopher transitions between its
three states of hungry, thinking, and sleeping until the count of those transitions exceeds
rounds.
In MAGE, when the mobile object o moves from host s to host t, o is first cloned, then
the new clone is marshaled and sent to t. The new clone at t executes the call that triggered
7.2. Peripatetic Dining Philosophers 161
o to move and becomes the current version of o. MAGE discards the old clone that remains
old clone when the new clone of a mobile object is sent to another host. Thus, moved
distinguishes the old and new clones of a mobile object. In Listing 7.2, moved set to true
causes the thread running in an old clone to exit the state loop and terminate.
Philosophers are active objects that move themselves. As we have noted, Java does not
support strong mobility, so we need some way to restart a computation at the language level:
we need to define a continuation using only the heap. When an active object cycles through
a state machine encoded in a switch, we can store its current state in the heap. If each
case in the switch is side-effect free before a movement-triggering method is called, then
when we marshal, move, and unmarshal the object we can restore its state and start a new
thread that returns to the method call that triggered the active object’s movement. We must
perform bookkeeping whenever an active mobile object arrives at a new host, notably we
must start the mobile object’s thread. All movement-triggering methods must detect arrival
and perform such bookkeeping as necessary. We use these techniques to realize philosophers
self.eat() Legend
marshal →
moved = true invocation local call
s clone = readObject() message
l clone.justArrived()
e
e Thread().sta
rt()
p return
HUNGRY →
moved → die self.eat()
When a self-invocation causes a mobile object to move, the thread running in the old
clone sleeps in the MAGE listener, as shown in Figure 7.4. Execution in the new clone sends
a return to the listener and awakens the old clone’s thread. The old clone’s thread must be
side-effect free. For this reason, a method whose self-invocation causes movement must be
void. The old clone’s thread can, of course, write to the old clone, as that clone is simply
discarded.
eat() method. The variables first and second are fields that contain proxies to a
philosopher’s chopsticks. In their constructors, philosophers bind these fields to CODa. The
helpings field determines how much a philosopher eats when it is hungry. It defaults to
one in the evaluations that follow. This eat() differs from its classic formulation in dining
The eat() method’s if-else handles bookkeeping. When a philosopher moves and its new
clone arrives at host, readObject() in Listing 7.4 unmarshals in it and sets justArrived
eat() and chains to uponArrival() in Listing 7.5, which first clears justArrived,
performs the bookkeeping, then starts a new thread for the philosopher.
7.2. Peripatetic Dining Philosophers 163
The movement-triggering call then returns and awakens the old clone’s thread, which
sets the old clone’s state to THINKING before executing the loop conditional. Since the old
clone’s moved boolean is true, it dies and the fact that it changed the old clone’s state is
irrelevant. The new clone’s thread starts out with its state set to HUNGRY, so it immediately
executes eat(). This execution applies the philosopher’s mobility attribute which could
cause the philosopher to move again, repeating this process. To prevent starvation, all the
mobility attributes in this evaluation also have a justArrived field, and return the local
host when it is true, thus allowing the philosopher to execute eat() at least once after
every move. If there is no food, the philosopher blocks in a queue until the café produces
more food.
There are two ways to immobilize a mobile object in MAGE. The first is an internal
move lock. A mover holds this lock while it waits for inplace invocations currently executing
in a mobile object to complete before it moves the object. To prevent the starvation of
movers, this move lock prevents new inplace invocations. Only a single mover can hold this
lock at a time.
7.2. Peripatetic Dining Philosophers 164
realise this mechanism: programmers call immobilize to lock a mobile object to its current
host and mobilize to free it. In peripetatic dining philosophers, the chopsticks represent
mobile resources that the philosophers need in order to eat. We have defined need to mean
that the chopsticks must be local when a philosopher eats, thus the binding of cod to them.
In the absence of user-controlled immobilization, while a philosopher was waiting for its
second chopstick, its first chopstick could be moved away by the philosopher that shares
Listing 7.6 illustrates the use of these two methods. In MAGE, a mobile object moves
before the method triggering that movement executes. Thus, a philosopher does not check
whether its neighbor owns the chopstick until after the chopstick is collocated with it.
7.2. Peripatetic Dining Philosophers 165
Both philosophers could be collocated, so the method must be synchronized. The owner
immobilizes the chopstick so that both chopsticks are local when it eats.
the classical acquisition of a chopstick in both a for loop and a try-catch block. The
try-catch block handles the case where the chopstick has been immobilized. Rather than
spin, we first bind an instance of a current location evaluation mobility attribute so that we
awakens, it sends a return to the thread waiting in getChopstick(), which must rebind
cod, before again making the remote call to the chopstick’s get method. The latency of
this work and the fact that the philosopher that just freed the chopstick is local to the
chopstick means that philosopher that was waiting in waitUntilFree() often loses the
To support some of the mobility attribute we describe below, our implementation of peri-
patetic dining philosophers populates the MAGE resource manager with each café’s produc-
tion rate r, number of resident philosophers, and available food m. Realized as mobility
Cooperative, CooperativeLocal These two policies seek to cooperatively move the phi-
losophers to match the consumption rate of the philosophers at a café with that café’s
number of philosophers in excess of the café’s rate of production. These two attribute
differ in that Cooperative sends messages to discover a target café where r > n, while
Gourmand This policy ranks the cafés and causes a philosopher to move to its highest
Hermit This policy causes a philosopher to seek a café with the fewest other philosophers
on it.
MostFood This policy greedily moves a philosopher to the café with the most available
food.
HighestProduction This policy moves a philosopher to the café with the highest rate of
production.
Listings 7.8, 7.9, and 7.10 present the “MostFood” policy’s concrete implementation as a
mobility attribute.
provides in its ml package for use as the base class of all attributes that bind to a single
7.2. Peripatetic Dining Philosophers 167
method. MostX assumes that the MAGE resource manager is populated with keys, whose
format is host:resource, mapped to float values. The X in its name abstracts the
resource name. Its rm field is a handle to the local resource manager. As such, it is transient;
pher to attempt to eat after each move. Set in readObject, it is checked in the targets
7.2. Peripatetic Dining Philosophers 168
singleton set containing only the philosopher’s current host. Otherwise, it loops through
all keys whose suffix matches the resource field, returning the set of hosts that share a
In Listing 7.10, MostFood’s targets() is quite simple and compact. It simply checks
if sufficient time, as defined by the sampling interval (ms) passed into its constructor has
elapsed. If not, it returns the singleton set of the host on which it is executing. Otherwise,
David A. Wheeler’s ’SLOCCount’ tool [106] generated the data in Table 7.3 and Figure 7.5.
This tool strips comments and then counts the remaining, physical, not logical, source lines
of code (SLOC). Further, we have used this tool to count each attribute’s entire class file,
COCOMO is a widely used software cost estimation model [15]. We report it here
to translate the SLOC results into dollars, a more meaningful unit of measure. Realized
as mobility attribute under MAGE, migration policies are isolated and small: developers
working on distributed systems that employ mobility are likely to save money if they use
MAGE.
Figure 7.5 presents the SLOC of the application attributes — attributes written to
realize migration policies for the peripatetic dining philosophers application — not the
attributes that MAGE provides in its ml package. Like MostX, the FewestX and NoX
classes factor code used in subsets of the policies. In particular, Hermit extends FewestX
These metrics demonstrate the concision of the policies that MAGE can express: MAGE
allowed us to express a number of interesting policies, well-suited for exploring layout in the
In this section, we compare migration policies against each other and three immobile
layouts when the café’s food production is fixed as defined in Figure 7.3b. The immobile
80
60
SLOC
40
20
0
FewestX.java
RandomWaitJaunt.java
Cooperative.java
CooperativeLocal.java
MostFood.java
RandomJaunt.java
HighestProduction.java
MostX.java
NoX.java
Gourmand.java
Hermit.java
resource utilization that an application, here peripatetic dining philosophers, can realize by
on the café whose production is 2 meals/s, and 3 on the café whose production is 3
meals/s.
The best case layout requires extrinsic information, here the production rate of each
café. For our evaluation, the worst case layout, which places all philosophers at the slowest
7.2. Peripatetic Dining Philosophers 173
16 1
producing café, is unlikely, at 3 = 729 . We include it as a point of reference. The random
extrinsic information.
The collections of migration policies we evaluate in Figures 7.6–7.8 include all Coop-
erative, all CooperativeLocal, all Greedy with various sampling rates, all MaxProduction,
and all RandomWaitJaunt. MinimizeMoves minimizes philosopher moves using the same
extrinsic information that underlies the static best layout to bind an instance of the Hermit,
two instances of Gourmand, and three instances MaxProduction attributes to the six
philosophers. RandomPolicy binds a policy from the above policies to each philosopher
uniformly at random.
We compare these migration policies and static layouts along four axis — time to
Each bar chart in this section reports the average of 10 runs. The philosophers make 150
transitions from HUNGRY to THINKING to SLEEPING in their three state state machine,
so they call their eat method 50 times. There are six philosophers, who each eat 1 meal
when they are hungry and three cafés that, in aggregate, produce 6 meal/s. Thus, ignoring
network latency and execution time, the idealized minimum time-to-completion is 50s. When
evaluating the migration policies, we start the philosophers out at a café chosen uniformly
at random.
cooperative causes philosophers to move slightly more often, with its concomitant impact on
chopstick moves, as shown in Figures 7.9 and 7.10. The box plot in Figure 7.7 demonstrates
mobility. Random policy conservatively models the effect of mobility when one lacks extrinsic
information about either the application’s behavior or resource distribution and production.
The random policy dramatically demonstrates the utility of mobility — a random collection
7.2. Peripatetic Dining Philosophers 174
300
250
time−to−completion (s)
200
150
100
50
0
RandomWaitJaunt
MinimizeMoves
RandomPolicy
Cooperative
CooperativeLocal
ImmobileWorstCase
Greedy
GreedyEager
GreedyLazy
ImmobileBestCase
ImmobileRandom
of migration policies finishes in 57% of the time and 30% of the waste when compared to
the random, immobile layout. Even though RandomWaitJaunt’s decisions are all random,
since it distributes the philosophers more evenly across the cafés temporally than immobile
random.
The three greedy policies differ in the rate at which they sample the resource manager
for each café’s available food. The eager version’s interval is 50ms; greedy’s is 200ms; and
the lazy version’s is 500ms. Note that café’s update their food every 50ms, so sampling
Figure 7.6 demonstrates that the three greedy policies are very fast: they are the three
fastest policies, finishing very close to the optimal time of 50s. The greedy policies also
7.2. Peripatetic Dining Philosophers 175
300 ●
●
250
time−to−completion (s)
200
150
100 ●
●
50
RandomWaitJaunt
MinimizeMoves
RandomPolicy
Cooperative
CooperativeLocal
ImmobileWorstCase
Greedy
GreedyEager
GreedyLazy
ImmobileBestCase
ImmobileRandom
minimize food wastage, as shown in Figure 7.8. In particular, the three greedy policies
perform better than the best case layout of immobile philosophers. At first, this seems
remarkable. However, the three cafés’ production of meals is not synchronized. The last
greedy philosopher to finish does so as soon as the last food he needs is produced anywhere.
The last immobile philosopher must wait until his café produces his final meal.
To achieve these numbers, the greedy policies move the philosophers around frequently,
as Figure 7.9 makes clear. Under the greedy policies, moreover, the philosophers all move
en masse from their current café to the café with the most available food, dragging their
chopstick along with them. This is the key to why the greedy policy performs so well — most
time, the average time to acquire a chopstick under the cooperative policy was 2.5s, while
that of greedy was 1.3s. Thus, the greedy policy’s chopstick acquisition time is 0.53% or
1
slightly great than 2 the acquisition time of the cooperative policy.
philosopher moves wasted meals
Cooperative Cooperative
CooperativeLocal CooperativeLocal
Greedy Greedy
7.2. Peripatetic Dining Philosophers
GreedyEager GreedyEager
GreedyLazy GreedyLazy
ImmobileBestCase ImmobileBestCase
ImmobileRandom ImmobileRandom
ImmobileWorstCase ImmobileWorstCase
MaxProduction MaxProduction
MinimizeMoves MinimizeMoves
RandomPolicy RandomPolicy
RandomWaitJaunt RandomWaitJaunt
Figure 7.8: Fixed Cooks: Average Number of Uneaten Meals
200
150
chopstick moves
100
50
0
RandomWaitJaunt
MinimizeMoves
RandomPolicy
Cooperative
CooperativeLocal
ImmobileWorstCase
Greedy
GreedyEager
GreedyLazy
ImmobileBestCase
ImmobileRandom
MaxProduction
Figure 7.10: Fixed Cooks: Average Number of Chopstick Moves
When the distribution of resources is fixed albeit unknown, mobility serves only to allow an
application to recover from a poor initial deployment of its components. When resources
are themselves mobile and changing, an application composed of mobile objects can adapt
as the distribution of resources changes. In this section, we evaluate policies in the context
of changing resources. Specifically, each café’s rate of food production starts out randomly
We change runs from 150 to 1500 so that there are more opportunities for the application
to react to changes in food production at the cafés. 1500 transitions means that each
philosopher needs to eat 500 meals. Since there are 6 philosophers, the earliest the experiment
can end is when the cafés produce 3000 meals. To ease the comparison of runs, we maintain
the invariant that the cafés always produce 6 meals/s so that requisite food is produced in
very nearly the same amount of time. Given this constraint, the optimal time-to-completion
is 3000meal/6meals/s = 500s = 8.3̄m. Each café changes cooks, i.e. its meal production
rate, every minute, for a grand total of 8 times during each run.
7.2. Peripatetic Dining Philosophers 178
1000
800
time−to−completion (s)
600
400
200
0
ImmRandomLayout
Cooperative
Greedy
MaxProduction
Figure 7.11: Changing Cooks: Average Time-to-Completion
The policies we evaluate are Cooperative, Greedy, Immobile Random Layout, and
Maximum Production. When production is changing, immobile best case and worst case
random layout are not well-defined as a layout could change from best case to worst case as
In Figure 7.11, Greedy finishes first, followed by MaxProduction. The cost advantage of
Figure 7.12 demonstrates Greedy’s excellence in quickly using all available food. Figure 7.13
depicts what the Greedy policy expends to achieve its time-to-completion and wasted meals
the café that currently has the highest production, so it moves the philosopher, dragging
their chopsticks with them, only 9 times. Greedy is high in spite of the fact that it also
concentrates the philosophers at a single café, because, as already noted, it frequently moves
7.2. Peripatetic Dining Philosophers 179
2500
2000
1500
wasted meals
1000
500
0
ImmRandomLayout
Cooperative
Greedy
MaxProduction
Figure 7.12: Changing Cooks: Average Number of Uneaten Meals
Our evaluation of the proposed migration policies has been descriptive. Game theory provides
tools that can answer prescriptive questions such as “which collection of policies should
one use?” We can model philosopher layout, and more generally mobile object layout, as
a game. We could define the payoff function that describes different outcomes in terms
migration policy would then be the strategy that a philosopher follows. We could then
apply game theoretic solution concepts, such as Nash or dominant strategy equilibria, to
find the corresponding set of strategies. Further criteria from economics, such as welfare
In the above evaluation, the cost of philosopher migration is fixed and small. An
7.2. Peripatetic Dining Philosophers 180
1000
800
philosopher moves
600
400
200
0
ImmRandomLayout
Cooperative
Greedy
MaxProduction
Figure 7.13: Changing Cooks: Average Number of Philosopher Moves
interesting evaluation would vary this cost to determine, for instance, the point at which
Two philosophers share each chopstick. Chopstick acquisition is more expensive when the
philosophers that share a chopstick are not collocated. Let philosophers be numbered [1..6].
Consider the partition {1}, {3, 5}, {2, 4, 6}, each assigned to a different café. This particular
layout maximizes the number of edges in the dining philosopher ring that cross the partitions.
It would be interesting to study policies that are aware of the philosopher ring and seek to
minimize these crossings. When chopsticks are fungible resources, such minimization might
be achieved by dynamically changing the dining philosopher ring, i.e. by exchanging a pair
not been previously studied: the authors of the evolving philosopher problem considered
only the birth and death of a philosopher and the merging of two communities (rings) of
philosophers [53].
7.3. Summary 181
1500
1000
chopstick moves
500
0
ImmRandomLayout
Cooperative
Greedy
MaxProduction
Figure 7.14: Changing Cooks: Average Number of Chopstick Moves
programming problem.
7.3 Summary
In this chapter, we have quantified MAGE’s invocation and marshaling overhead using bench-
designed for a mobile context. Featuring both mobility of philosophers and chopsticks, this
various migration policies and showed how concisely MAGE can express these policies.
182
Chapter 8
Related Work
Computing environments change. Machines fail and new ones are added. Gigabit
switches are installed and printers decommissioned. New applications and operating systems
are installed. Mobile devices, like cellphones, change location and can access a different
set of resources than they could in their previous location. Network and CPU load varies.
Often, administrators must handle these changes. The challenge is to build systems and
This challenge is seminal. Researchers have worked on it since the dawn of the computer
age. We take some of this work for granted, like adaptive locks or the fact that file systems
test blocks and, once they identify a bad block, they recover the data and avoid that bad
block in the future. In this vast space of work, Figure 8.1 focuses on two overlapping subsets,
systems that, in response to their environment, change their behavior or change their layout,
the mapping of their subcomponents onto execution engines. To differentiate behavioral and
Consider a client-server multimedia system that streams data from the server to the client
for playback. This system can encode the stream in two ways: 1) a bandwidth expensive
183
Reconfigurable Systems
Behavioral Layout
but high-fidelity encoding or 2) a light-weight but lossy encoding. If this system switches
between these two encodings depending on network load, the system exhibits behavioral
adaptation [28, §3.1]. A cluster whose scheduler moves running components around to
binding between the software components of the application and their physical location within
and layout adaptation converge. REV’s motivating example illustrates this convergence: a
mail server performs custom filtering using filters sent by its clients1 .
above. Difficulties include handling the reappearance of systems that did not receive an
1
Chapter 4 opens with this example.
184
update because they were unavailable, and correctly transitioning threads running the old
behavior to the new behavior [64, 4, 107, 28]. As these systems are not closely related to
subsumes static, as a dynamic system can reconfigure itself at startup, thus simulating static
adaptation. We use shading to denote adaptation time offered by a project in Figure 8.1.
Hollow circles denote systems that adapt statically. Solid circles denotes systems that adapt
dynamically.
adapts itself autonomously [45]. Given a recipe that selects algorithms (behavior) and layout
based on resource distribution and availability, SCS queries its environment to generate
a site-specific configuration. Because it adapts both behavior and layout, SCS is in the
intersection.
Classically, layout has been manual and static, restricted to deployment. For instance,
RPC-based systems have assumed static distribution of components and their definitions.
Java’s RMI [66], CORBA [92], and COM/DCOM [27] exemplify such RPC-based distributed
system infrastructures.
The idea of supporting dynamic layout, i.e. program mobility, is not new and has
appeared in various forms in distributed operating system [7, 26, 61] and programming
language [48, 37] research. Broadly, this research has explored systems that offer ever greater
degrees of mobility, progressing from the data migration inherent to RPC [13] to the explosion
of interest in MA [99] that began in 1995. The vast majority of mobile agent systems support
mobility through explicit calls to a move command. As a result, the programmer must
intermingle the application’s layout, or per component migration policies, with the code that
Not least for this reason, mobile programs are more complex to write and debug than
distributed programs that rely on a static layout of their components. As a result, a number
of programming models that abstract dynamic layout have been proposed. MAGE is one
such programming model. In the rest of the chapter, we compare and contrast MAGE with
8.1. Classic Agent 185
Examples of early work on mobility of programs (and objects) through a language’s runtime
system are Emerald [48], Hermes [14], DOWL [2], and COOL [37]. In particular, Emerald
introduced the ability to “locate an object, move an object to another node, and fix an object
at a particular node.” By moving objects, these early systems achieved a weak, heap-based
form of mobility. In the 1990s, a second wave of mobile code languages burst onto the scene,
including Telescript [108], AgentTCL [52], Aglet [58], Mole [96], Ara [79], Ajanta [101] and
Sumatra [85]. We can classify [50] these systems into those that move execution state as
well as program code (strong mobility), and those that move only code (weak mobility).
Examples of systems that support both are Sumatra and Telescript. The latter impose
Since it is expensive to access and move a thread’s stack safely and the JVM does
not provide access to the CPU’s register file, MAGE currently implements a form of weak
mobility: In general, it waits for all threads to drain from a mobile object before moving it.
MAGE can move active objects, as in the peripatetic dining philosopher case, but only if
the active object cooperates by providing its own bus stops, execution points in which the
These languages provide some form of a move command that programmers can use
to change the location of a program’s components. They stand in the same relation to
programming models like MAGE and its siblings in the same way that assembly language
constructs in the same way that synchronization primitives can be reduced to semaphores.
Listing 8.1 depicts the code an invoking thread would need to execute to realize COD in
a classic agent language. The invoker must discover its own location, collocate a with itself,
8.2 FarGo
The FarGo programming model [42, 44, 43, 1] calls its components complets and defines them
to be the transitive closure of the heap references of an object. It is unclear how a complet
differs from Java’s serial representation of an object, which is also the transitive closure of
heap references [67]. FarGo provides programmers three ways to control component mobility.
The first is an explicit call to move. FarGo supports two implicit mobility mechanisms —
Inter-complet references are essentially stubs in RMI terms. FarGo supports five default
relocation policies in a set of complet reference classes — Link, Pull, Duplicate, Stamp, and
then when A moves, B follows it. The A component could have been explicitly moved, moved
FarGo programmer can use these links cause groups of components to move in unison.
FarGo allows programmers and administers to write complet migration policies using
complet references, a Java event API, an Event-Action scripting language, and a graphical
layout tool. The graphical tool relies on the Java event API and script mechanisms, so we
will not discuss it further. Both the Java event API and script mechanisms allow FarGo
programmer supplied migration policy executes. The Java event API intermingles component
migration policy with application code; the scripting language separates the two. Events and
complet references allow programmers to express migration policies in two different ways that
8.2. FarGo 187
can interact: the migration of a component caused by an event can trigger the migration of
other components due to complet references and vice versa. FarGo programmers must take
Unlike FarGo, MAGE offers a single mechanism, the mobility attribute, for implicitly
controlling component mobility and expressing migration policies. Mobility attributes and
FarGo’s inter-complet references are both first class entities in the sense that they can be
passed into functions and modified within Java, their implementation language. Both FarGo
and MAGE allow the dynamic adaptation of migration policies through the binding and
rebinding of their complet links and mobility attributes to components at runtime. FarGo’s
event-action scripts, while not first class, can also be dynamically bound to complets in FarGo.
MAGE allows programmers to define their own policies by subclassing a default mobility
attribute. FarGo’s complet link classes are not intended to be extended by programmers.
MAGE’s mobility attributes can be composed (Section 3.5); FarGo makes no provision for
FarGo’s complet reference mobility allows programmers to ensure that tightly coupled
complets migrate and thus remain together. In other words, FarGo can move components
important when moving components to and from hosts that are frequently disconnected, such
as laptops [80]. Components can form transitory working sets in the course of a program’s
computation. In general, these working sets are difficult to statically discover. MAGE’s
invocation based mechanism lets a program’s execution determine how the program’s
components move based on messages actually sent, rather than a programmer’s static,
offers a natural way for a distributed application to react to the a machine going offline for
maintenance, since it has only to post the event. In MAGE, the components would move off
the host only as they were invoked, so a programmer would have to manually invoke each
8.3 StratOSphere
the StratOSphere project [118, 120, 119] maps these scenarios to computation paradigms,
which it represents as messages. StratOSphere calls those scenarios that move only data
message to fetch code from a remote system, before calling dispatch on the return message.
a remote server that unmarshals the message and calls its dispatch method.
The StratOSphere authors noted that many scenarios could not be represented by their
CS, COD and REV messages and proposed a new paradigm, which they called Remote Code
that, from the point of view of the invoker, requires components from the local execution
environment and other execution environments remote to the target execution environment.
that conveys the local components to the remote target execution environment, and then
gathers the remaining components from the nontarget remote execution environments before
StratOSphere makes these messages, and thus the computation paradigms they represent,
available to programmers through a class hierarchy. Because its messages are passive,
StratOSphere introduces a separate set of classes to represent the mobile code paradigm.
These classes allow the programmer to instantiate active objects that import components to
execute, then aggregate and carry the results of the executions of these components as they
Through its messages, StratOSphere allows one to use different mobility models to
write distributed programs. Each message must be statically created by the programmer,
an application’s core logic are not separate. StratOSphere programmers may be able to
achieve some runtime flexibility in the expression of their migration policies by using the
for a given network configuration, such as instantiating a COD message upon one pass
through a code block and a CS message upon another, while using a message abstract base
In StratOSphere, a computation may require more than one component. This is crucial
to the definition of RCE above, which makes sense only if the computation requires compo-
nents from different locations. Programmers using StratOSphere map the components to
computations by fetching these components, by name, from a repository into their message.
The StratOSphere literature does not address how the programmer specifies the order of
to the invoker/sender. Presumably, the programmer must dispatch the resulting message
in the case of COD and manually return the results of an REV execution. The fact that
dispatch and a return value is inherent to the CS message, but not the COD and REV
component to control where it executes, and thus which computation paradigm, COD or
MAGE programmer would first send a component that invokes the other components in the
RCE set. This component would bind a COD attribute to each of its references to the other
components. As it invokes operations on the other components, MAGE would then lazily
collocate them.
8.4. SATIN 190
8.4 SATIN
middleware must support dynamic reconfiguration of both behavior and layout. SATIN
defines logical mobility, as distinct from the physical mobility of a cellphone, as “the migration
of a partial or complete application or process from one host to another” [123, §1]. SATIN’s
unit of mobility is a logical mobility unit (LMU), which contains an arbitrary number of
logical mobility entities (LME). In terms of MAGE, an LMU is a component, while a set
of LME is analogous to the heap closure of the fields of a component. SATIN associates a
set of attributes called properties with each LMU. These properties list the hardware and
software dependencies of the LMU. For instance, they might specify that the LMU can only
Table 8.1, from [122, §1.3.3], shows how SATIN maps COD onto a sequence of actions:
A and B are nodes, represented by a and b in the code. It is unclear whether Table 8.1
not code, its naı̈ve realization as a programming model would be very low-level, even more
so than classic agent, and with the attendant lack of isolating the mobility concern.
8.5 Columba
Columba discusses mobility in terms of binding [10]. Columba associates a shadow proxy
each mobile device. A shadow proxy is mobile code, implemented using the Java-based
Secure and Open Mobile Agent platform. A binder manager manages all of a shadow proxy’s
external references (bindings) and can dynamically and transparently adjusts those bindings,
under the control of the policy manager. XML metadata describe each resource, such as
whether the resource can move, its dependencies, and what operations it exports. Policies,
written in the declarative Ponder language, use the metadata to determine how to change
bindings. Columba allows administrators to add new or change existing policies at runtime.
Columba realizes COD when an event triggers the binder manager to execute a “co-locality
policy” which collocates two resources, which may be shadow proxies, then rewrites their
Columba offers two interesting features that MAGE does not: it 1) allows programmers,
via its use of XML metadata, to write resource aware policies with less effort than MAGE’s
current implementation requires; and 2) supports injecting new policies into a running system.
For the latter, MAGE assumes the set of policies (attributes) that a programmer can choose
from is statically fixed. In contrast, MAGE 1) reports and analyzes its overhead, while
Columba does not; 2) supports the composition of policies; and 3) uses a single language,
Java, to express both application logic and migration policies. The fact that Columba
separates the application logic and policy specification into two languages, Java and Ponder,
hinders debugging (how can a programmer step through a shadow proxy when the binder
8.6. Aspect Oriented Programming 192
manager can rewrite its bindings?) and increases the cognitive scope of the programmer’s
cutting concerns, those concerns that cannot be easily modularized because they overarch or
frame different concerns. Logging and mobility, our particular concern, are two examples.
AOP calls these cross-cutting concerns aspects and defines joinpoints as those points in
the execution of a program where different concerns can be woven together. Pointcuts are
named subsets of joinpoints; an example pointcut is the set of all method invocations in a
In AOP terms, MAGE dynamically weaves the mobility aspect into a distributed program
at the method call pointcut and applies its attributes like before advice. AOP treats aspects
as self-contained and focuses on their composition with the target code and with each other.
Since the unit of composition in AOP is an aspect, an AOP programmer would be forced to
represent each different migration policy as a separate aspect [103]. MAGE uses a single
language, Java, for both the application logic and the mobility concern in the implementation
of its attributes. The binding of attributes directly appears in the application logic, and
is not expressed indirectly as a pointcut. Relative to AOP, this fact reduces the cognitive
scope of MAGE, easing debugging and maintenance. MAGE focuses solely on the mobility
concern. Freed of the need to support very general cross-cutting concern, MAGE is able to
D2 AL [9] is a AOP model that focuses on the component mobility aspect of distributed
which components should be co-located and whether that co-location should be realized by
movement or replication. D2 AL’s proposed weaver works at compile time so D2 AL does not
express runtime component migration policies; rather, it focuses on static program layout.
8.7. P2PMobileAgents 193
RoleEP [103] encapsulates component mobility in roles, and thereby addresses AOP’s
problem of how to separate migration policies without assigning them to different aspects.
These roles dynamically bind to a component and extend that component with new methods
that govern both how their migration policy and how other components can interact with
the component. In RoleEP, a migration policy must be expressed separately from a role as a
series of calls to the migration methods provided by that role. Mobility attributes in MAGE
do not extend the interface of components to which they are bound; rather, they implicitly
encapsulate a migration policy that the MAGE RTS applies upon each method invocation.
8.7 P2PMobileAgents
Like Columba, P2PMobileAgents [38] extends the explicit migration of traditional mobile
agent programming models with metadata about the resources needed and provided by the
agents and execution environment in the system and a declarative domain specific language
for migration policies that selects an execution environment, given an agent’s resource needs
and the current network configuration. P2PMobileAgents uses XML to implement both of
The authors do not address how to bind migration policies to agents, nor whether or
not these policies can be composed. However, an example they give implies that, prior to
an explicit migrate call, P2PMobileAgents executes the migration policy as a P2P query
broadcast to the overlay network. Since queries must be built statically, it appears that,
unlike MAGE, P2PMobileAgents’ programming model is static, in the sense that it does not
8.8 Summary
Table 8.2 lists whether and how the programming models discussed in this chapter isolate
the mobility concern from the application logic. The difficulty associated with attempting
8.8. Summary 194
to achieve this isolation strongly differentiates those that do not from MAGE, so we drop
Although the remaining programming models all support explicit mobility through a
move command, separating the mobility concern implies that a component’s migration
policy is not always manual. Table 8.3 summarizes to what the remaining programming
Table 8.4 characterizes the properties of the migration policies in each programming
8.8. Summary 195
model. By first class, we mean an entity that can be passed to method calls and modified
system that tracks the resource needs of components and the availability of resources in the
system [85].
196
Chapter 9
Conclusion
MAGE’s raison d’être is that computation and resources must be dynamically co-located
as resources appear and disappear and move around on a network. To realize this ambition,
MAGE defines a programming model whose bedrock is the mobility attribute abstraction.
This model defines expressions over mobile object, proxy, and its mobility attribute types.
Objects move when the application of which they are a part decides to move either the
computation or the data that they represent from one namespace to another, usually for
performance and efficiency reasons. In MAGE, an application makes its distribution wishes
known via mobility attributes. Since, as we have shown, mobility attributes can encompass
any distributed programming model and dynamically bind to program components, they
allow the programmer who uses them to build flexible and adaptable distributed programs
The principal contribution of this thesis is the MAGE programming model and its
realization. A programmer would choose MAGE for projects that require dynamic layout
adaptation because MAGE (1) separates the migration concern into attributes; (2) facilitates
policy reuse via attribute composition; and (3) offers powerful, flexible, and elegant control
9.1. Future Work 197
We believe that MAGE will provide the community a valuable framework for thinking
about computation mobility. MAGE provides a high level of abstraction that unites the
distributed programming models currently in widespread use, separates core application code
from computation placement policies, and facilities the construction of complex migration
albeit over the TCP/IP loopback stack, even when two mobile objects are collocated,
of invocations made by collocated mobile objects from RPC to local procedure calls is
demonstrates the utility of attribute operators should be formulated and built. Finally,
MAGE can move components to and from a compute farm in response to the cost of
CPU cycles. For a long-running scientific application, such a migration policy could
and investigate its utility in mobile device applications, such as mobile TCP/IP. I am
to formulate a problem that researchers could use to evaluate the performance and
[1] Miki Abu and Israel Ben-Shaul. A multi-threaded model for distributed mobile objects
[3] William Adjie-Winoto, Elliot Schwartz, Hari Balakrishnan, and Jeremy Lilley. The
17th ACM Symposium on Operating Systems Principles (SOSP), pages 186–201, New
[4] Sameer Ajmani, Barbara Liskov, and Liuba Shrira. Modular software upgrades for
[5] Sara Alouf, Fabrice Huet, and Philippe Nain. Forwarders vs. centralized server: an
49(1-4):299–319, 2002.
[6] K. Arnold and J. Gosling. The Java Programming Language Third Edition. Addison
Wesley, 2000.
[7] Y. Artsy and R. Finkel. Designing a process migration facility: the Charlotte experience.
199
REFERENCES 200
[8] Earl Barr, Raju Pandey, and Michael Haungs. MAGE: A distributed programming
[9] U. Becker. D2 AL: A design-based aspect language for distribution control. In Position
[10] Paolo Bellavista, Antonio Corradi, Rebecca Montanari, and Cesare Stefanelli. Dynamic
7(2):34–42, 2003.
[12] Yves Bertot and Pierre Castéran. Interactive Theorem Proving and Program De-
[13] A. Birrell and B. Nelson. Implementing remote procedure calls. ACM Transactions
[14] Andrew P. Black and Y. Artsy. Implementing location independent invocation. IEEE
[15] Barry W. Boehm, Ellis Horowitz, Ray Madachy, Donald Reifer, Bradford K. Clark, Bert
Steece, Winsor A. Brown, Sunita Chulani, and Chris Abts. Software Cost Estimation
with Cocomo II. Prentice Hall PTR, Upper Saddle River, NJ, USA, January 2000.
[16] A. Carzaniga, P. Pietro, and G. Vigna. Designing distributed applications with mobile
[17] K.M. Chandy and J. Misra. The drinking philosophers problem. ACM Transactions
[18] Chin-Chen Chang and Iuon-Chang Lin. The strategy of reducing the location update
traffic using forwarding pointers in virtual layer architecture. Computer Standards and
[19] Seon G. Chang and Chae Y. Lee. A selective pointer forwarding strategy for location
344–351, 2000.
[20] A. Chervenak, I. Foster, C. Kesselman, C. Salisbury, and S. Tuecke. The data grid:
Towards an architecture for the distributed management and analysis of large scientific
datasets, 2001.
[21] D. Chess, C. Harrison, and A. Kershenbaum. Mobile agents: Are they a good idea?
[22] Michael J. Demmer and Maurice Herlihy. The Arrow distributed directory protocol.
[23] P. J. Denning. Thrashing: Its causes and prevention. In Proceedings AFIPS Joint
[24] Peter J. Denning. The locality principle. Communications of the ACM, 48(7):19–24,
2005.
[26] F. Douglis and J. Ousterhout. Transparent process migration: Design alternatives and
[27] G. Eddon and H. Eddon. Inside Distributed COM. Microsoft Press, 1998.
REFERENCES 202
[28] Brian Ensink and Vikram Adve. Coordinating adaptations in distributed systems. In
[30] Robert Joseph Fowler. The complexity of using forwarding addresses for decentralized
Distributed Computing (PODC), pages 108–120, New York, NY, USA, 1986. ACM.
[31] Munehiro Fukuda, Lubomir F. Bic, Michael B. Dillencourt, and Fehmina Merchant.
[32] Erich Gamma, Richard Helm, Ralph Johnson, and John Vlissides. Design Patterns:
63361-2.
[33] Michael R. Garey and David S. Johnson. Computers and Intractability; A Guide to
the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA, 1990.
[35] Richard Goering. Keynote: How multicore will reshape computing. EETimes, March
2007.
[36] Robert S. Gray, George Cybenko, David Kotz, Ronald A. Peterson, and Daniela Rus.
[37] Sabine Habert and Laurence Mosseri. COOL: kernel support for object-oriented
[38] Klaus Haller and Heiko Schuldt. Using predicates for specifying targets of migration
[39] Robert H. Halstead, Jr. Multilisp: A language for concurrent symbolic computa-
[40] Miguel Helft. For start-ups, web success on the cheap. The New York Times, November
8th 2006.
[41] Carl Hewitt, Peter Bishop, and Richard Steiger. A universal modular actor formalism
[42] Ophir Holder, Israel Ben-Shaul, and Hovav Gazit. Dynamic layout of distributed
[43] Ophir Holder, Israel Ben-Shaul, and Hovav Gazit. System support for dynamic layout
[44] Ophir Holder and Hovav Gazit. FarGo programming guide. Technical Report EE Pub
[45] An-Cheng Huang and Peter Steenkiste. Building self-configuring services using service-
[46] Galen C. Hunt and Michael L. Scott. The Coign automatic distributed partition-
and Implementation (OSDI), pages 187–200, Berkeley, CA, USA, 1999. USENIX
Association.
[47] Ravi Jain and Yi-Bing Lin. An auxiliary user location strategy employing forwarding
[48] Eric Jul, Henry Levy, Norman Hutchinson, and Andrew Black. Fine-grained mobility in
1988.
[49] Gregor Kiczales, Erik Hilsdale, Jim Hugunin, Mik Kersten, Jeffrey Palm, and William G.
[50] J. Kiniry and D. Zimmerman. A hands-on look at Java mobile agents. IEEE Internet,
[52] David Kotz, Robert Gray, Saurab Nog, Daniela Rus, Sumit Chawla, and George
Cybenko. Agent TCL: Targeting the needs of mobile computers. IEEE Internet
[53] Jeff Kramer and Jeff Magee. The evolving philosophers problem: Dynamic change
[54] P. Krishna. Performance Issues in Mobile Wireless Networks. PhD thesis, Texas A&M
George Riley, Brad Topol, and Mustaque Ahamad. Efficient implementation of Java
Oriented Technologies and Systems (COOTS), Santa Fe, New Mexico, April 1998.
[56] Leslie Lamport. Time, clocks, and the ordering of events in a distributed system.
[57] Leslie Lamport. Specifying Systems: The TLA+ Language and Tools for Hardware
[58] D.B. Lange, M. Oshima, G. Karjoth, and K. Kosaka. Aglets: Programming mobile
agents in Java. In Proceedings of the Worldwide Computing and Its Applications, pages
253–266, 1997.
[59] Yi-Bing Lin and Wen-Nung Tsai. Location tracking with distributed HLR’s [sic]
February 1998.
[60] Barbara L. Liskov and L. Shrira. Promises: Linguistic support for efficient asynchronous
1988.
[62] Steve Lohr. A software maker goes up against Microsoft. The New York Times,
[63] W. Lugmayr. Gypsy: A component-oriented mobile agent system. PhD thesis, Technical
[64] Scott Malabarba, Raju Pandey, Jeffrey Gragg, Earl Barr, and J. Fritz Barnes. Runtime
support for type-safe dynamic Java classes. In Proceedings of the 14th European
[65] John Markoff. Intel prototype may herald a new age of processing. The New York
products/jdk/rmi/index.
REFERENCES 206
//java.sun.com/products/jdk/1.2/docs/guide/serialization/spec/
serialTOC.doc.html.
sun.com/javase/technologies/core/mntr-mgmt/javamanagement/,
September 2007.
[72] Luc Moreau. Distributed directory service and message router for mobile agents.
[73] Luc Moreau. A fault-tolerant directory service for mobile agents based on forwarding
Agents, Interactions, Mobility and Systems, pages 93–100, Madrid, Spain, March 2002.
[74] Christian Nester, Michael Philippsen, and Bernhard Haumacher. A more efficient RMI
for Java. In Proceedings of the ACM 1999 Conference on Java Grande, 1999.
22–30, 1982.
[76] Athanasios Papoulis. Probability, Random Variables, and Stochastic Processes. McGraw
[77] David Patterson, Arvind, Krste Asanovic, Derek Chiou, James C. Hoe, Christoforos
Kozyrakis, Shih-Lien Lu, Mark Oskin, Jan Rabaey, and John Wawrzynek. RAMP:
Research accelerator for multiple processors. In Proceedings of the 18th Hot Chips
[78] Renaud Pawlak, Lionel Seinturier, Laurence Duchien, and Gérard Florin. JAC: A
[79] H. Peine and T. Stoplmann. The architecture of the Ara platform for mobile agents.
[80] Gian Pietro Picco. µCode: A lightweight and flexible mobile code toolkit. In K. Rother-
mel and F. Hohl, editors, Mobile Agents, Proceedings of the 2nd International Workshop
on Mobile Agents (MA), volume 1477, pages 160–171, Stuttgart (German), September
1998. Springer.
[81] José M. Piquer. Indirect distributed garbage collection: handling object migration.
September 1981.
[83] Michael L. Powell and Barton P. Miller. Process migration in DEMOS/MP. SIGOPS
[84] Dongyu Qiu and R. Srikant. Modeling and performance analysis of BitTorrent-like peer-
[87] V. Ryan, S. Seligman, and R. Lee. Schema for representing JavaTM objects in an
[88] Jürgen Schwille. Use and abuse of exceptions - 12 guidelines for proper exception
[89] George Semeczko and Stanley Y. W. Su. Supporting object migration in distributed
[90] Marc Shapiro, Peter Dickman, and David Plainfossé. Robust, distributed references and
of Distributed Computing (PODC), pages 135–146, New York, NY, USA, 1992. ACM.
[91] Marc Shapiro, Peter Dickman, and David Plainfossé. SSP chains: Robust, distributed
references supporting acyclic garbage collection. Technical Report 1799, INRIA, 1992.
[93] J.W. Stamos and D.K. Gifford. Remote evaluation. In ACM Transactions on Pro-
gramming Languages and Systems, volume 12, pages 537–565, October 1990.
[94] Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, and Hari Balakrishnan.
[96] M. Strasser, J. Baumann, and F. Hohl. Mole: A Java based mobile agent system. In
[97] Andrew Tanenbaum. Computer Networks. Prentice Hall, 3rd edition, 1996.
[98] The Coq Development Team. The Coq proof assistant reference manual. Technical
[99] T. Thorn. Programming languages for mobile code. ACM Computing Surveys,
[101] Anand Tripathi, Neeran Karnik, Manish Vora, Tanvir Ahmed, and Ram Singh. Mo-
[102] Anand R. Tripathi, Neeran M. Karnik, Tanvir Ahmed, Ram D. Singh, Arvind Prakash,
Vineet Kakani, Manish K. Vora, and Mukta Pathak. Design of the Ajanta system for
2002.
[103] Naoyasu Ubayashi and Tetsuo Tamai. Separation of concerns in mobile agent applica-
tions. In Proceedings of the 3rd International Conference Reflection 2001, LNCS 2192,
[104] Peter Wayner. Cloud versus cloud: A guided tour of Amazon, Google, AppNexus, and
[106] David A. Wheeler. Linux kernel 2.6: It’s worth more! http://groklaw.net,
October 2004.
[108] Jim E. White. Telescript technology: The foundation for the electronic marketplace.
[109] Jim E. White. Mobile agents. General Magic Inc. White Paper, 1996. http:
//www.magic.com.
2007.
2007.
September 2008.
[118] Daniel Wu, Divyakant Agrawal, and Amr El Abbadi. StratOSphere: Mobile processing
[119] Daniel Wu, Divyakant Agrawal, and Amr El Abbadi. Mobility and extensibility in the
[120] Daniel Wu, Divyakant Agrawal, and Amr El Abbadi. StratOSphere: Unification of
[122] Stefanos Zachariadis, Manish Lad, Cecilia Mascolo, and Wolfgang Emmerich. Building
2007.
[123] Stefanos Zachariadis, Cecilia Mascolo, and Wolfgang Emmerich. The SATIN component