% File: mt.tex
% Author: Bernd Mathiske, Florian Matthes
% Date: 07.11.1996, revised by FM based on Amihai Motro's suggestions
% Purpose: JIIS article
%

%% Kluwer Small Journal Article Template File
%% Current version: January 24, 1994

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Prepared by Amy Hendrickson, TeXnology Inc.                          %%
%% (617) 738-8029                                                       %%
%%                                                                      %%
%% Inquiries to Suzanne M. Rumsey, net address: prod@world.std.com      %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


% Use one of these two commands: 
\documentstyle[xple,epsf]{smjrnl} % For Computer Modern Fonts, or,
%\documentstyle[xple,epsf,smjfonts]{smjrnl} % for PostScript fonts
\newcommand{\e}[1]{{\em #1\/}}
\newcommand{\p}[1]{{\sl{}#1}}
\newcommand{\k}[1]{{\bf{}#1}}
\newcommand{\st}{$<$:}

\begin{document}
\begin{article}


%%%%% To be entered at Kluwers: =====>>
\journame{}
\volnumber{}
\issuenumber{}
\issuemonth{}
\volyear{}

%% Do not delete either of the following two commands.
%% Please supply facing curly brackets for the part you
%% are not using for this article.
\received{}\revised{}

\authorrunninghead{}
\titlerunninghead{}

%\setcounter{page}{275} %% Optional, uncomment to set page number.
%%%%  <<==== End of commands to be entered at Kluwers 


%%  Authors, start here ====>>

\title{On Migrating Threads
\thanks{This work was supported in part by the Commission of the 
European Communities under grant number ISC-CAN-080 CIS, 
\em{Activity Modelling and Object Technology for 
Cooperative Information Systems}.}}

\author{Bernd Mathiske}
\email{mathiske@fb.sony.de} 
\author{Florian Matthes}
\email{matthes@informatik.uni-hamburg.de} 
\author{Joachim~W.~Schmidt}
\email{J\_Schmidt@informatik.uni-hamburg.de} 
\affil{Fachbereich Informatik,
       Universit\"at Hamburg, \\
       Vogt-K\"olln Stra{\ss}e 30,
       D-22527 Hamburg, Germany}

%% Article editor
\editor{Amihai Motro}

%% Abstract
\abstract{
Based on the notion of persistent threads in 
Tycoon \cite{MaSc94}, we investigate thread migration 
as a programming construct for building activity-oriented distributed 
applications.  We first show how a straight-forward extension of a 
higher-order persistent language can be used to define activities that span 
multiple (semi-) autonomous nodes in heterogeneous networks.  In 
particular, we discuss the intricate binding issues that arise in systems 
where threads are first-class language citizens that may access local and 
remote, mobile and immobile resources. \\ \\
We also describe how our system model can be understood as a promising 
generalization of the more static architecture of first-order and 
higher-order distributed object systems.  Finally, we give some insight 
into the implementation of persistent and migrating threads and we explain 
how to represent bindings to ubiquitous resources present at each node 
visited by a migrating thread on the network to avoid excessive 
communication or storage costs.
}

%% Keywords
\keywords{distribution threads migration agents workflows persistence
          higher-order languages bindings dynamic linking}

\section{Introduction and Rationale}
\label{Intro}

Most of the work on migrating threads described in this article has been 
carried out in the context of the European ESPRIT basic research project 
FIDE (fully integrated data environments).  The rationale behind the FIDE 
project is to improve significantly the productivity in the process of 
building integrated, data-intensive applications.  The overall goal of FIDE 
is to develop a consistent and small set of orthogonal language and system 
concepts to eliminate the historical mismatches and overlaps between 
independently developed component technologies.

While the initial contribution of FIDE has been the development of persistence
and type system technology to overcome the mismatches between programming
language and database technology, the work described here addresses the
overlaps and mismatches between distributed programming, transaction management
and workflow management.

More specifically, we propose to generalize the well-understood programming
concept of threads \cite{POSIX} to also cover persistent and migrating threads
which can be used as primitive building blocks to implement long-term and
distributed cooperative activities.  In a recent paper \cite{MaSc94}, we
describe the notion of persistent threads while this article reports on our
work to migrate such persistent threads between heterogeneous nodes in local or
wide area networks.

The analogy with the concept of remote procedure calls may help to clarify 
the rationale behind our work.  Remote procedure calls and migrating 
threads both demonstrate how to reduce successfully the complexity of 
distributed systems by a generalization of a well-established 
non-distributed programming concept:

\begin{itemize}
\item Programmers do not need to learn a new programming abstraction.

\item Local software architectures and libraries can be scaled easily to 
distributed software architectures.

\item Tools can be provided to optimize the mapping from high-level 
language abstractions to low-level communication mechanisms.

\item The generalized programming abstraction interacts well with other 
programming language concepts like static typing, modularization and 
parameterization.

\end{itemize}

Our work on migrating threads reveals a strong synergy between 
concepts, language constructs and technologies which support persistence 
through time with their counterparts to support distribution through space. 
This synergy will become obvious in the rest of this article which is 
organized as follows. 

First, we present migrating persistent threads as a generalization of
conventional thread concepts and motivate them as a valuable programming
abstraction for the implementation of long-term distributed activities. We then
introduce a terminology for data, code and thread bindings
(Section~\ref{Bindings}) and basic thread operations as well as related typing
aspects (Section~\ref{Operations}). This is the basis for a comparison of
alternative models for distributed programming in Section~\ref{Models}. These
range from a client-server oriented programming style via higher-order
languages and object migration approaches to migrating threads.  In
Section~\ref{Resources} we discuss the difficult binding issues arising in the
context of thread migration. Based on our classification of thread resources we
describe how to achieve adequate binding support for standard programming
situations. In Section~\ref{Implementation} we give some insight in our
implementation of migrating threads available uniformly on Unix, Windows and
MacOS platforms.

%------------A-------------------------------------------------------------------

\section{Thread Persistence and \mbox{Mobility}}
\label{Mobility}

A thread describes a single sequential flow of control in a program.  Having
multiple threads in a program means that at any instant the program has
multiple points of execution, one in each of its threads.  Unlike operating
system processes, multiple threads execute within a common address space,
permitting multiple threads to access shared resources (see
Figure~\ref{evalcont}).  Threads are also known as {\em lightweight processes}
\cite{Sun88,Nels91,Kepp93} as they require significantly fewer resources
(mostly time and storage space) than operating system processes.  This concerns
in particular creation and context switches.

\begin{figure}
\begin{center}\leavevmode
\epsfxsize=0.8\textwidth 
\epsfbox{evalcont.ps}
\end{center}
\caption{Evaluation state and resources of a local volatile thread}
\label{evalcont}
\end{figure}

Today, threads are a well-established and standardized \cite{POSIX} programming
abstraction suitable for short-lived and non-distributed applications.  For
example, loosely coupled high-level activities like text editing,
spell checking, typesetting, and screen refreshing can be mapped to separate
concurrent threads that execute different code against shared data.  Moreover,
there is a rich repertoire of explicit and implicit synchronization mechanisms
for thread coordination and communication (semaphores, mutexes, condition
variables, channels, message queues, rendezvous', transactions).

\begin{table}
\begin{tabular}{lll}
\hline
{\bf Cooperation Mode}   & same time              & different time      \\
                         & (single session)       & (multiple sessions)  \\
\hline
same location            & local volatile threads & local persistent threads \\
(single address space)   &                        & \\
\hline
different location       & migrating threads      & migrating persistent threads \\
(multiple address spaces)&                        & \\
\hline
\end{tabular}
\caption{Thread-based implementations of cooperative activities}
\label{matrix}
\end{table}

However, the traditional thread concept exhibits severe limitations 
for cooperative work as required by data-intensive applications, as it 
covers only one segment of the space vs. time matrix depicted in 
Figure~\ref{matrix}:

\begin{itemize} \item The lifetime of a thread is limited by its enclosing 
operating system process (i.e., a thread is a \e{volatile} and 
not a persistent value).

\item The location of a thread is limited by a single address space.
\end{itemize}

As described in \cite{MaSc94}, a generalization towards {\em persistent 
threads} makes it possible to map also long-term activities (business 
processes or workflows) to threads.  For example, the handling of a 
customer request by a clerk in a service department can be modeled by a 
thread that runs for several days or even weeks, thereby outlasting 
multiple activations of the same program.  In a type-complete persistent 
language, persistent threads can be stored, for example, as attributes of 
database tables and they can be manipulated by user-defined queries.

\begin{figure}
\begin{center}\leavevmode
\epsfxsize=\textwidth
\epsfbox{migratingThread.epsf}
\end{center}
\caption{Implementing a distributed activity by thread migration}
\label{migratingThread}
\end{figure}

If one adopts an activity-oriented view of distributed applications, it is 
desirable to be able to express distributed workflows directly by 
{\em migrating threads} that span multiple network nodes and independent 
databases.  For example, Figure~\ref{migratingThread} and the associated 
Tycoon script in Figure~\ref{migratingThreadScript} describe an expense 
report activity in a company by means of a single thread.  This 
thread migrates through different departments (sites) and carries around 
information about its past history.  Being invoked by an employee, it is 
equipped with various bindings to mobile resources like the attributes of 
the expense report and immobile resources like a project budget databases 
maintained by the group manager.  Passing through the secretary's and the 
group manager's site, it eventually reaches the finance department where a 
money transfer is initiated.

In a conventional system, activity persistence is implemented by writing 
the full thread state to a file or a database.  To continue an activity 
after a process restart, its stored state has to be reloaded and a new 
thread has to be created in order to resume code execution at the last 
instruction executed in the previous session.
Similar techniques have to be applied for activity migration.
This ``manual'' approach to thread 
persistence and migration fails for non-trivial long-term and distributed 
activities due to the following technical difficulties:
\begin{itemize}

\item Bindings between variable names in the code (e.g., \p{expenseReport, 
projectBudgetDB} in Figure~\ref{migratingThreadScript}) and their 
associated entities have to be reestablished.  Such thread bindings are 
discussed in more detail in Section~\ref{Bindings}.

\item Depending on the power of the language at hand (loops, function 
calls, recursion, exception handling, etc.) it may be very difficult to 
recreate a thread that is in the correct execution state (program counter, 
evaluation stack, exception handler). 

\item It is often necessary to transmit the state and code information of a 
thread separately and to apply ad-hoc dynamic code binding mechanisms at 
the receiver side prior to thread restart.

\end{itemize}

In our Tycoon system and language, persistence and mobility is the default 
for all data, code and thread entities.  Only immobile and volatile 
resources require special treatment by the programmer (see 
Section~\ref{Resources}).  This relieves the programmer from low-level thread 
implementation details and turns threads into a suitable programming 
primitive for distributed, data-intensive applications.

\begin{figure}
\begin{xple}\small
 \k{migrate to} Employee \k{do}
   \k{repeat}
      \k{let} data = getExpenseDataFromUser()
      \k{migrate to} Secretary \k{do}
         \k{let} expenseReport=compileReport(data) 
      \k{end}
   \k{until} valid(expenseReport) 
 \k{end}
 \k{migrate to} GroupManager \k{with remote}
    projectBudgetDB :ProjectBudgetDB 
 \k{do}    
    update(projectBudgetDB, expenseReport.total)
 \k{end}
 \k{migrate to} FinanceDepartment \k{do}
    transferMoney(expenseReport.total)
 \k{end}
\end{xple}
\caption{Tycoon script for a migrating thread (expense report)}
\label{migratingThreadScript}
\end{figure}


%-------------------------------------------------------------------------------

\section{Thread Bindings}
\label{Bindings}

In this section we introduce a terminology for the description of data, code
and thread bindings (c.f.~\cite{MaSc94}) that we use in the rest of this
article to describe the Tycoon thread semantics, to discuss selected thread
implementation aspects and to compare different models for distributed
programming.

A binding is an association between a name and a computational entity from 
a specific semantic domain \cite{Stra67,MABD88}.  We also say that a name 
is bound to a computational entity.  An environment is a (possibly ordered) 
collection of bindings.  Names are used to identify entities in an 
environment.  Different names can be bound to the same entity (sharing, 
aliasing).

Entities can be atomic (like integers or booleans) or structured (like
records, objects or functions).  Structured entities typically consist
of environments.  For example, the fields of a record lead to bindings
from field names to other entities.  Therefore, bindings can be used to
model (recursive) relationships between entities.

Entities can be flat (like records) or nested (like functions in
Algol-like languages).  In a nested entity, names bound in a global
outer environment are automatically visible in a local inner
environment.

The binding of names to structured entities naturally leads to the concept 
of a transitive closure of bindings that underlies many persistence and 
migration models: any entity reachable through a chain of bindings from a 
persistent (mobile) entity becomes persistent (mobile), too.  This approach 
which is also adopted in Tycoon decouples the lifetime and mobility of an 
entity from its type (orthogonal persistence \cite{AtBu86}, orthogonal 
mobility) and should be seen in contrast to systems and languages where the 
programmer has to tag persistent and mobile objects explicitly at 
creation-time.  The latter systems provide a weaker notion of referential 
integrity since bindings from persistent (mobile) to volatile (immobile) 
objects are replaced at transaction-commit (migration-time) by bindings to 
a distinguished NIL entity or they may even become undefined.

We distinguish three categories of structured entities:

{\bf Data} describes the persistent state of an information system by a 
collection of computational entities related through bindings.  The 
structure (types) of the entities and their bindings are described by 
types.  For example, the database schema of the \p{projectBudgetDB} at site 
\p{GroupManager} describes the signatures of the local persistent bindings 
between project and account entities stored at that site.

{\bf Code} is a description of operation sequences that query and update 
volatile or persistent entities and bindings.  Code can be expressed by 
means of imperative or declarative, high-level or low-level programs and 
scripts.  For example, the imperative script in 
Figure~\ref{migratingThreadScript} is written at a rather high level of 
abstraction and involves static bindings to further code entities 
(\p{getExpenseDataFromUser}, \p{compileReport}) but also to mobile 
(\p{data}, \p{expenseReport}) and immobile (\p{projectBudgetDB}) data 
entities.

{\bf Threads} are representations of code in the process of being executed. 
 A thread is created by submitting a (non-parameterized) code fragment like 
the expense report script in Figure~\ref{migratingThreadScript} and 
(persistent) data to an evaluator.  Multiple threads executing the same 
code typically have different local bindings (\p{expenseReport}) but shared 
global bindings (\p{projectBudgetDB}).

The semantics of the thread evaluator can be defined inductively by rules that
map thread states to thread states and that perform side-effects on data as
described in more detail in \cite{MaSc94}.  A thread state subsumes bindings to
the code fragments currently being executed and a dynamic environment that
records the current bindings from names occurring in the code to local and
global entities.  In most imperative programming and query language
implementations, thread states are represented as records that reference stacks
of so-called ``activation records'', one for each function or query invocation
(cf. Figure~\ref{evalcont}).


%-------------------------------------------------------------------------------

\section{Thread Operations and \mbox{Typing}}
\label{Operations}
Following Tycoon's add-on approach to data modeling \cite{MaSc91b,MaSc92a}, 
the \k{migrate to} construct utilized in Figure~\ref{migratingThreadScript} 
is not built into the core Tycoon system.  Instead of this, migrating 
threads are provided by a hierarchy of library abstractions and Tycoon's 
extensible grammar \cite{CMA94} is exploited to provide the 
necessary syntactic layer to hide the underlying infrastructure from 
high-level workflow script programmers.

Tycoon's core thread functionality is provided by a library module that 
exports exactly the following exceptions, types and functions:

\begin{xple}\small
\k{interface} Thread \k{export}
(* --- Types: *)
  T(R $<$:\k{Ok}) $<$:\k{Ok}
  State $<$:\k{Ok}
(* --- Constants: *)  
  error, abortion :\k{Exception}
  runningState, blockingState, suspendedState, 
  terminatedState, exceptionState :State
(* --- Queries: *)
  main() :T(Int)
  self() :T(\k{Ok})
  running() :Array(T(\k{Ok}))
  state(R $<$:\k{Ok}  thread :T(R)) :State
(* --- Thread management: *)
  new, fork, launch(R $<$:\k{Ok}  f(self :T(R)) :R) :\k{Ok}
  duplicate(R $<$:\k{Ok}  thread :T(R)) :T(R)
  suspend, run, abort, kill(R $<$:\k{Ok}  thread :T(R)) :\k{Ok}
  join(R $<$:\k{Ok}  thread :T(R)) :R
(* --- Termination by exception: *)  
  throw(R $<$:\k{Ok}  thread :T(R)  exc():\k{Ok}) :\k{Ok}
  catch(R$<$:\k{Ok} thread :T(R)  handler(exc():\k{Ok}):\k{Ok}):\k{Ok}
  joinCatch(R $<$:Ok  thread :T(R)) :R
(* --- Synchronization primitives: *)  
  atomic(R $<$:\k{Ok}  action() :R) :R
  sleep(timeout :Real) :\k{Ok}
\k{end}
\end{xple}

In Tycoon, threads are {\em typed} first-class values that can be stored in 
variables, passed as parameters, embedded into (persistent) data structures 
and transmitted between network sites.  For example, a variable of type 
\p{thread.T(Person)} can only hold a thread that evaluates code which 
returns a value of type \p{Person}.  Tycoon's polymorphic typing makes it 
possible to define both, generic functions that work uniformly on threads 
with an arbitrary result type \p{R} (like \p{new, fork} or \p{suspend}), as 
well as user-defined functions that depend on a specific thread result type.

A Tycoon thread executes a function which is specified as an argument of the
respective thread creation operation. For example, the following program
fragment creates a new thread \p{t} which immediately start the execution of
the function \p{f} that returns an integer value. It is required that a
``thread script'' function like \p{f} expects a thread parameter of the
appropriate type, \p{T(Int)} in this case. At runtime, the \p{thread.fork}
operation passes the newly created thread as an actual argument to the function
to support type-safe reflexive thread operations.
\begin{xple}
  \k{let} f\/(self :thread.T(Int)) :Int =   {\small(* Thread-Skript *)}
    \k{begin} \dots
      thread.kill(self)   {\small(* a reflexive operation on the current thread *)}
      \dots
      4711
    \k{end}
  \k{let} t = thread.fork(f)   {\small(* Creation of a new thread that executes \p{f}. *)}
\end{xple}
More precisely, the abstract data type \p{thread.T} is a type operator 
parametrized by the result type \p{R} of the thread function.  
\begin{xple}
  T(R {\st}\k{Ok}) {\st}\k{Ok}
\end{xple}
By virtue of Tycoon's polymorphic type system, a thread result can be
obtained in a type-safe way. For example, \p{t} is a value of type
\p{thread.T(Int)} which implies that the result of the \p{thread.join} function
applied to \p{t} returns an integer value.
\begin{xple}
  \k{let} x :Int = thread.join(t)
\end{xple}
At runtime, this statement blocks the execution of the current thread
(\p{thread.self}) until the evaluation result of the function \p{f}
is available. Thereupon execution of the waiting thread is resumed and the
result of \p{t} is bound to the variable \p{x}.  Mismatches between
the type (here \p{Int}) required by the given expression context and
the thread result type are detected by the Tycoon compiler at compile-time

Without going into details, the functions \p{throw} and \p{catch} exploit the
presence of higher-order functions in Tycoon to unify asynchronous signal
handling with exception handling.  For example, the function call
\p{thread.abort(otherThread)} raises the exception \p{thread.abortion} in
\p{otherThread}. In addition to critical sections (\p{thread.atomic}), several
related modules export further synchronization primitives (semaphores, mutexes
and condition variables) not shown here but discussed in detail in
\cite{Piel96}.

Building on these thread primitives, other Tycoon library modules add 
mechanisms to create a portable linear byte stream representation of a 
thread value, to establish a stream connection between network sites, to 
address network sites based on roles and logical identifiers, to atomically 
migrate running threads between network sites, etc.  All these modules are 
loosely coupled and (by virtue of polymorphic typing and structural dynamic 
type checking across sites) strongly typed.  This makes it possible to 
modify selected modules, for example, to experiment with different 
addressing and coordination protocols between migrating threads while 
ensuring a certain degree of overall system consistency.

%-------------------------------------------------------------------------------

\section{Models for Distributed Activity-Oriented Systems}
\label{Models}

In this section we compare migrating threads with other programming models for
distributed applications like remote procedure calls and (higher-order)
distributed object management.  We argue that in particular for
activity-oriented tasks like workflow management it is desirable to add threads
as mobile resources to these more traditional models.  Our comparison is based
on the uniform view of data, code and thread bindings introduced in
Section~\ref{Bindings}.

In the following we restrict ourselves to distribution models that scale to
heterogeneous, federated and widely distributed environments.  Therefore, we do
not discuss concurrent or database languages based on the notion of a single
(persistent) address space, like distributed databases, distributed virtual
memory or distributed persistent heaps, some of which already provide
multi-threading capabilities.  As argued in more detail in \cite{MMS95b}, we
believe that the autonomy and heterogeneity requirements of larger-scale
distributed systems are not addressed by these models.

\subsection{Remote Procedure Call}
\label{RPC}

Already in the introduction we quoted remote procedure calls as an example 
how to successfully generalize a well-established local programming concept 
to a distributed scenario.  From a binding perspective, the core concept of 
RPCs are bindings from local to remote code entities which can be 
maintained for the duration of a session.

Typically, an activity is implemented by one thread of control at a single 
client side invoking subactivities at several server sites.  A remote 
invocation either uses a single thread at the server side which implicitly 
serializes requests from multiple clients or it creates a fresh volatile 
thread for each incoming client request (multi-threaded server).

The plain RPC model has the crucial disadvantage for activity-oriented 
programming, that the code describing a long-term activity has to be 
fragmented, distributed and installed statically at the relevant sites.  
Furthermore, with conventional RPC mechanisms \cite{Corb91,DCE93}
it is very circumstantial to transmit recursive data structures.


\subsection{Distributed Object Systems and Remote References}
\label{DistObj}
Distributed object management is viewed as a promising approach to build 
scalable distributed systems that are also capable of integrating legacy 
(database) systems by means of a unified object paradigm \cite{Mano92}.  
There are numerous proposals for specific object models like DSOM of IBM 
\cite{IBM94}, DOM of GTE \cite{Mano92}, Network Objects of Modula-3 
\cite{BNOW93} and future versions of Microsoft's OLE \cite{Micr94}
and there are several related standardization efforts like CORBA of the OMG 
\cite{CORBA91} and the OSF DCE/DME \cite{DCE93}.  For a detailed 
feature analysis of these models see \cite{NWM93,Mano93c}.

From a binding perspective, distributed object models provide bindings to 
local and remote objects which aggregate data and code.  Compared with the 
RPC model, the argument bindings for remote method invocation are generalized,
since it is not only possible to transmit values but also 
references to other (local or remote) objects.

However, like in the RPC model there is no migration of behavior and object 
types have to be installed statically.
As sketched in Figure~\ref{clientServer} it 
is necessary to split activities into separate scripts stored as object 
methods at different sites.  Moreover, long-term and recoverable activities are 
difficult to implement in today's distributed object models.

Figure~\ref{clientServer} shows how the expense report activity described 
in Section~\ref{Mobility} can be implemented by communicating distributed 
objects.  Separate server objects describe the services 
available through the secretary, the project manager and the finance 
department.  Activity control is centralized at the client (employee) site 
which is also responsible for exception handling at all stages of script 
execution.

\begin{figure}
\begin{center}\leavevmode
\epsfxsize=\textwidth
\epsfbox{clientServer.epsf}
\end{center}
\caption{Implementing a distributed activity by communicating objects}
\label{clientServer}
\end{figure}

The availability of remote references minimizes the data transfer 
during activity migration since each binding to a local entity at the 
originator site is replaced transparently on transmission by a remote 
reference.  A remote reference identifies the originating address space 
and an entity local to it \cite{JLHB88,BNOW93,Card94}.
Subsequent read, write or execute access to the entity at the remote site 
transparently invokes a network communication with the originating site.

Conversion to remote references has clear, simple semantics since it 
preserves the original sharing.  On the other hand it causes data 
fragmentation across address spaces, in particular it decreases the 
autonomy of migrating threads.  Its usefulness depends on high site 
availability and low network latency.

\subsection{Higher-Order Languages}
\label{Higher}
Higher-order languages do not make a distinction between code and data 
bindings.  In distributed higher-order languages like Obliq \cite{Card94} 
it is therefore possible to transmit code and data uniformly between 
network sites.  For example, by passing a function as an argument in an 
RPC, programmers can implement migration of behavior directly, as required 
by activity-oriented applications.

Moreover, since function abstraction dynamically aggregates state bindings,
function migration already exhibits a limited mechanism to transmit partial
evaluation states of activities across networks.  For example, the Tycoon code
in Figure~\ref{higherOrderFunctionScript} utilizes four functions (\p{step1}
through \p{step4}) to encode the four evaluation states of the expense report
script as valid at migration time.  As expected, activity migrations are
implemented by passing (the closures of) the above functions to higher-order
RPCs \cite{MMS95b} that simply execute their argument at the respective remote
site. Such a \e{remote execution engine} can also establish bindings to
resources available only at the receiver side by passing them as actual
arguments to the function. For example, \p{groupManagerSite.execute} will
execute \p{step3} with the \p{projectBudgetDB} as a local argument.

\begin{figure}
\begin{xple}\small
\k{let rec} step1 = \k{fun}() \k{begin}
  \k{let} data = getExpenseDataFromUser()
  \k{let} step2 = \k{fun}() \k{begin}
    \k{let} expenseReport=compileReport(data)
    \k{if} valid(expenseReport) \k{then}
      \k{let} step3=\k{fun}(projectBudgetDB :ProjectBudgetDB) 
      \k{begin}
        update(projectBudgetDB expenseReport.total)
        \k{let} step4 = \k{fun}() \k{begin}
          transferMoney(expenseReport.total)
        \k{end}
        financeDepartmentSite.execute(step4)
      \k{end}
      groupManagerSite.execute(step3)
    \k{else}
      employeeSite.execute(step1)
    \k{end}
  \k{end}
  secretarySite.execute(step2)
\k{end}
employeeSite.execute(step1)
\end{xple}
\caption{Encoding thread states with higher-order functions}
\label{higherOrderFunctionScript}
\end{figure}
Note that in this approach iteration has to be expressed by recursion.

As illustrated by Figure~\ref{procedures}, the resulting scenario is very close
to our thread migration approach (see Figure~\ref{migratingThread}).
However, additional local thread functionality is required to implement 
concurrent activities and activities can only be transmitted in an 
execution state captured by an explicit function abstraction which destroys the
block structure of imperative programs.

\begin{figure}
\begin{center}\leavevmode
\epsfxsize=\textwidth
\epsfbox{procedures.epsf}
\end{center}
\caption{Emulating thread migration in a higher-order distributed language}
\label{procedures}
\end{figure}


\subsection{Migrating Objects}
\label{ObjMig}

While entities in many distributed object models are immobile (they never leave
their creation address space), some systems also support explicit object
migration (Emerald \cite{Jul88,JLHB88}, SOS \cite{SGM89}).  If an object leaves
an address space, some local references are converted transparently into remote
references.  Conversely, if an object enters an address space, some remote
references may be converted back into local references.

In addition to technical advantages (load balancing, reduced communication 
traffic, simplified system reconfiguration) object mobility provides 
migration of behavior and encapsulation of state as required for activity 
migration.

On the other hand, the state of a long-term activity represented by a 
migrating object has to be encoded explicitly as a (structured) object 
attribute.  In particular, conditional, iterative and recursive state 
transitions lead to complicated state encodings.  This explicit encoding 
should be seen in contrast to persistent threads where the runtime support 
implicitly and efficiently maintains the state of the long-term activity.


\subsection{Migrating Threads and Network Agents}

If one is interested in building systems where a large number of loosely
coupled activities roams the network and makes heavy use of network resources,
it is desirable to avoid a cumbersome encoding of activities and to have
persistent and migrating first-class threads for straight-forward activity
programming.

Such a complete unification of data, code and thread binding is achieved in
Emerald \cite{Jul88,Jul89,JLHB88} and in Tycoon.  Emerald makes heavy use of
reference semantics for these bindings.  In particular, object state attributes
and thread stack frames tend to be fragmented across multiple network nodes.
Therefore, the main focus of Emerald is on applications in local area networks
with high site availability and low network latency.  As discussed in
Section~\ref{Resources}, Tycoon provides a spectrum of binding mechanisms to
handle also other distribution scenarios, like autonomous network agents on
global electronic marketplaces, a vision sketched in \cite{Whit94,Wayn94}.

Clearly, migrating threads are not a replacement for todays established
distributed programming mechanisms, but they constitute a valuable programming
abstraction that can be integrated smoothly into many distribution models.

%--------------------------------------------------------------------------------

\section{Binding Techniques for Thread Resources}
\label{Resources}

In this section we discuss the central issue in thread migration, namely how to
transmit a thread state which represents a set of transitive bindings to data,
code and other threads between address spaces.  After a classification of
thread resources we present tailored binding mechanisms provided in Tycoon for
local and remote as well as for mobile and immobile resources.

\subsection{Classification of Thread Resources}
\label{Classify}

In order to determine appropriate binding mechanisms for resources that are 
involved in the migration of a thread, we first classify these resources 
based on their implementation technology:

\begin{description}

\item [Tycoon] resources are all language entities (data, code, threads) 
which are defined entirely in Tycoon libraries or application code and 
which are therefore managed by the Tycoon runtime system.
  
\item [External] resources are conceptually pre-existing resources that are 
not under direct control of the Tycoon runtime system.  These resources 
include files, communication channels, input or output devices, graphical 
elements (windows, buttons, menus) or programs (mail tool, word processor). 
 External resources are created by external library code written in C or 
C++ which is available to Tycoon programmers via typed language gateways.  
In Section~\ref{Volatile} we sketch a method that allows volatile external 
resources to ``accompany'' persistent and migrating threads through time 
and space.

\end{description} 

In general, every atomic and structured Tycoon entity is persistent and 
{\bf mobile}.  If a component binding of a structured Tycoon entity (tuple, 
array, function, thread, \dots) refers to an external resource, its 
persistence and mobility has to be ensured by explicit Tycoon code (see 
Section~\ref{Volatile}).

Some resources like platform-dependent software components or hardware 
devices are inherently {\bf immobile}.  In addition it may be necessary to 
regard some resources (for example, a huge database or a licensed piece of 
software) as immobile.

A further classification is based on the scope of resource definitions:

\begin{description}

\item [Local] resources are defined in the inner lexical scope of a thread 
code definition and they are allocated dynamically for each thread (e.g., 
\p{data} and \p{expenseReport} in Figure~\ref{migratingThread}).

\item [Global] resources are defined in the outer lexical scope of a thread 
code definition and they are potentially shared by multiple threads (e.g., 
the procedure definitions in Figure~\ref{migratingThread}).

\end{description}

The following important cases of distributed resources require special 
binding methods:

\begin{description}

\item [Remote] resources are available at a remote site only.  For example, 
\p{projectBudgetDB} in Figure~\ref{migratingThread} is available 
exclusively at the group manager's site and requires a dynamic binding on 
thread migration from the secretary's site to the group manager's site.

\item [Ubiquitous] resources are available at all sites visited by a 
thread.  Standard examples are the thread migration software itself (module 
\p{thread} in Section~\ref{Operations}), operating system functions and program 
libraries that serve rather general purposes like GUI and network 
programming.  Ubiquitous resources are usually stateless but an 
application-specific notion of resource equivalence frequently leads to a 
more general interpretation of ubiquity.
   
\end{description}

\subsection{Shipping Mobile Resources}\label{Mobile}

We explain the shipping of mobile resources using the following \k{migrate 
to} statement taken from Figure~\ref{migratingThreadScript}:
\begin{xple}
\k{let} data = \ldots
\k{migrate to} Secretary \k{do}
  \k{let} expenseReport = compileReport(data)
\k{end}
\end{xple}
Assuming that the \k{migrate to} command is executed by a thread \p{t} 
running at site \p{Employee}, the migration of \p{t} is performed as 
follows.  First, \p{t} is suspended at site \p{Employee}.  Then, \p{t} is 
shipped to site \p{Secretary}.  Finally, \p{t} is resumed at site 
\p{Secretary}.  The notation \k{migrate to \ldots\ do} is 
realized by Tycoon's extensible syntax \cite{CMA94} which translates 
directly into Tycoon library calls to perform these elementary thread manipulation 
and data communication steps.

As explained in Section~\ref{Bindings}, the thread \p{t} contains a 
continuation binding to the code still to be executed.  This code fragment 
(\p{\k{let} expenseReport = compileReport(data)}) in turn is represented as 
a function closure with bindings to all its free variables 
(\p{compileReport} and \p{data}).  The free variables in the example above 
constitute a local thread resource (\p{data}, a data entity) and a global 
thread resource (\p{compileReport}, a code entity).

The basic semantics of thread shipping in Tycoon is a {\em deep copy} 
operation between address spaces.  Therefore, the thread \p{t} at site 
\p{Secretary} contains direct local bindings to all mobile resources 
transitively reachable from \p{t}.

User-defined bulk data structures like lists, trees, database tables, etc., 
and also nested entities referring to code and threads are handled 
correctly by the Tycoon system.  Programmers have to be aware that deep 
copying does not preserve sharing of mutable locations and may lead to high 
storage and communication costs.

In order to minimize the transitive referential closure of an entity, its 
representation must not include (indirect) references to entities which are 
irrelevant for its further use.  A counterexample is a linked-list 
representation of function closures as found, for example, in Napier88 
\cite{NapierRep} where nested functions can unattendedly capture indirect 
references to bulk structures, as for instance the persistent root of the 
object store.  This virtually prevents code and thread transmission and is 
also a severe obstacle to garbage collections.  To avoid these problems, 
Tycoon uses flat function closures of minimal size determined by a static 
binding analysis during code generation.



\subsection{Working with Immobile Resources}
\label{Immobile}

There are two alternatives to handle immobile resources like the database 
\p{projectBudgetDB} in Figure~\ref{migratingThreadScript}.

\begin{itemize}

\item Thread migration to the remote site (see 
Figure~\ref{migratingThread});

\item Explicit communication with the remote site where the immobile 
resource is located.

\end{itemize}

In Tycoon the latter can be achieved by a remote procedure call (RPC) 
facility which is portable across different middleware architectures.  As 
described in \cite{MMS95b}, there are two Tycoon RPC implementations based 
on ONC-RPC (also known as Sun-RPC) and BSD sockets respectively. A third 
implementation which utilizes DCE as its communication 
medium is in preparation.


\subsection{Dynamic Binding to Remote \mbox{Resources}}
\label{Remote}

In a thread script, only the static bindings to local resources can be 
checked at compile time against the local database schema.  In a loosely 
coupled system where remote sites can perform schema updates between 
thread script compilation time and thread migration time, it is necessary 
to perform {\em dynamic} bindings to remote resources (e.g. 
\p{projectBudgetDB} in Figure~\ref{migratingThreadScript}).  In order to
locate a remote resource within the 
destination address space, an ubiquitous {\em name service} like the
network object import mechanism in Modula-3 \cite{BNOW93} or Obliq 
\cite{Card94} can be used to identify resources based on a 
string value.  This requires a dynamic type check between the actual
resource type and the types used in script programming and bears the risk
that a type error is detected after migration only.

As an alternative, the types of the remote resources can be attached already to
the type specification of a remote {\em migration engine}.  A migration engine
is an RPC server that accepts a thread, binds it dynamically to local site
resources and then resumes the thread.  In Tycoon, a remote migration engine is
typed based on the signatures of its resources.  Therefore, mismatches between
remote types and the types used in thread scripts are detected already at
server binding time. Thus type errors are limited to the departure site and can
only happen once per connection.

Syntactically, the name and the type of each remote resource is listed in 
the \k{with remote} clause of a migrate statement. The scope of these 
identifiers is restricted to the block enclosed by the keywords 
\k{do} and \k{end} (see also Figure~\ref{migratingThreadScript}):

\begin{xple}
\k{migrate to} GroupManager \k{with remote}
  projectBudgetDB :ProjectBudgetDB
\k{do}     
   update(projectBudgetDB, expenseReport.total)
\k{end}
\end{xple}

To summarize, Tycoon thread scripts are fully statically type checked at 
their originating site.  Whenever two sites establish a network connection 
(which may lead to a large number of thread migrations or RPC calls), the 
resource type definitions of the two sites are verified to be
(structurally) compatible.

\subsection{Access to Ubiquitous Resources}
\label{Ubiquitous}

Experience with non-trivial activity-oriented applications shows that in 
order to avoid excessive communication or storage costs on thread 
migration, system support is needed to handle bindings to ubiquitous 
resources present at each node visited by a migrating thread on the 
network.

From the programmer's viewpoint, it suffices to mark ubiquitous resources 
with a call to the function \p{register} of the module \p{ubiquitous}.
\begin{xple}
ubiquitous.register(windowManager)
ubiquitous.register(list)
ubiquitous.register(database)
\end{xple}

\begin{figure}
\begin{center}\leavevmode
\epsfxsize=9cm
\epsfbox{rebind.epsf}
\end{center}
\caption{Rebinding ubiquitous resources by means of dynamic linking}
\label{rebind}
\end{figure}

In the example above, the Tycoon modules \p{windowManager}, \p{list} 
(polymorphic lists) and an application-specific module \p{database} are 
tagged as ubiquitous resources.  The argument of the \p{register} function 
can be an arbitrary Tycoon entity; it is not constrained to coarse-grained 
module values. This is a generalization of the limited dynamic linking capabilities of other distributed programming systems (see e.g., Emerald \cite{Jul88}, SOS \cite{SGM89,Shap93}, FACILE \cite{Knab95} and Java \cite{GMcG95}).

On transmission between address spaces, bindings to entities explicitly 
marked as ubiquitous are replaced by symbolic references.  At the receiver 
site, these symbolic references are replaced by corresponding local bindings. 
 In principle, a dynamic type check has to be performed during this {\em 
dynamic linking} to ensure that the type of the remote resource matches the 
type of the resource at the originator site.  In the Tycoon implementation, 
this expensive repeated operation can be avoided by global identification 
mechanisms (for details, see \cite{MMS95b}).

The dynamic linking of ubiquitous resources is most useful for immutable 
values (code, literals, external bindings) replicated over the network.  
However, there are also some situations where a migrating thread has to 
bind to mutable repositories at multiple network sites.  For example, a 
migrating thread might operate on multiple databases, file systems or ftp 
servers or produce side-effects on multiple screens, fax machines, etc.
while roaming the network.

The following Tycoon code shows the definition of the function 
\p{info} in the module \p{statistics} which is bound to the 
ubiquitous modules \p{database} and \p{print}. 
\begin{xple}
\k{module} statistic \k{import} database print
\k{export} \k{let} info() = print.int(database.count())
\k{end};
\end{xple}
The left hand side of Figure~\ref{rebind} illustrates the bindings 
within the address space \p{A} that contains the module \p{statistics}.  If 
a thread that uses solely the function \p{info} is transferred to another 
address space \p{B}, the deep copy operation stops at the ubiquitous 
resources \p{database} and \p{print}.


\subsection{Recreation of Volatile Resources}
\label{Volatile}

Volatile resources like window handles and bindings to C data structures 
outside of the Tycoon persistent store can be registered with the module 
\p{volatile} in order to make them pseudo-persistent.  Such volatiles are 
recreated automatically following a system restart or a migration 
operation and they are destructed automatically preceding shutdown, 
rollback or migration operations.

The order in which volatiles are registered is significant, because typically 
there exist bindings from ``younger'' to ``older'' volatiles.  If 
programmers register volatiles in creation order, the automatic recreation 
operations follow the original creation sequence and destruction happens in 
reverse order. A similar mechanism is embodied in the SOS system,
where resource dependencies are defined by naming {\em pre-requisite objects}
\cite{SGM89} which have to be recreated before their dependent objects.

Each Tycoon address space contains a global data structure referencing all 
volatiles under the control of the module \p{volatile}.  The elements of 
this data structure never migrate;
instead they are recreated automatically at the receiver site.
Volatiles interact with the Tycoon garbage collector 
through ``weak references'' \cite{HKMN93}.  

%--------------------------------------------------------------------------------

\section{Implementing Migrating Persistent Threads}
\label{Implementation}

The previous sections described migrating threads from an application
programmer's point of view. We now turn to implementation aspects of thread
migration, namely storage and data representation (Section~\ref{thread-representation}),
communication protocols (Section~\ref{migration-gates}) and transaction
management (Section~\ref{transactions}).

\subsection{A Mobile and Persistent Thread State Representation}
\label{thread-representation}

Figure~\ref{evalcont} shows the most important constituents of the execution
(evaluation) state of a local, volatile thread. Such a thread is represented by a
data structure that captures the states of all relevant registers of the CPU. These registers, in particular the stack pointer and the program counter,
constitute transitive references to all further components of the evaluation
state. Occasionally, the transitive referential closures of several threads
overlap. In this simple way, local volatile threads can share program resources
of all kinds like code, variables, files and communication channels.

\begin{figure}
\begin{center}\leavevmode
\epsfxsize=0.6\textwidth 
\epsfbox{ptstruct.ps}
\end{center}
\caption{Object store representation of a persistent and mobile Tycoon thread}
\label{ptstruct}
\end{figure}

From the programmer's point of view, Tycoon threads behave just like normal
volatile threads in other programming languages.  However, Tycoon thread
representations are integrated with the global transaction and persistence
mechanisms of Tycoon.  Figure~\ref{ptstruct} illustrates the concrete
representation of a Tycoon thread by persistent store objects. The object in
the upper left corner constitutes the actual thread value (a handle).  It
contains the thread state, a reference to the thread stack and the
result. Whereas the former is a persistent entry, the latter are valid only in
certain thread states. In the following, the set of possible thread states
\p{state} and the respective transitions are explained (see
Figure~\ref{tstates}.

\begin{figure}
\begin{center}\leavevmode
\epsfxsize=0.6\textwidth 
\epsfbox{tstates.ps}
\end{center}
\caption{Persistent thread states}
\label{tstates}
\end{figure}

\begin{description}
\item [running:] Expression evaluation takes place in this state.  Each
executing thread has its own persistent stack object referenced by the field
\p{stack}. The first slots of the stack object contain the abstract machine's
register values (\p{IP} \dots \p{CF}) and some extra administrative data. By storing
these and the stack contents in a single object, allocation and release of registers
and stacks is simplified.

\item [suspended:] \begin{sloppypar} In this state a thread has been
stopped explicitly by a call to \p{thread.suspend}. This does not
change its storage structure which also applies to the state
\p{blocked}. \end{sloppypar}

\item [blocking:] A thread that waits for the result of another thread
(due to a call to \p{thread.join}) is blocked until the required value
becomes available. A blocking thread can also be suspended.

\item [terminated:] When a thread has completed the evaluation of its
function, the function result is stored in the field \p{result} and propagated
to all threads that have a pending \p{thread.join} on this thread. Then
the reference to the \p{stack} is removed. Thus, a terminated
thread occupies only very little storage space, but still provides its
result to other threads that still have a reference to this thread and may
execute \p{thread.join} at a later point in time.

\item [exception:] This state is reached when a dynamic exception is raised
during evaluation that propagates through all active function frames of a thread
and that is not handled by a matching exception handler installed by a \k{try
end} block. The exception package is stored in the
field \p{result} and is propagated to all threads that execute 
\p{thread.join} on this thread. The field \p{stack} is treated as described for
the state \p{terminated}.
\end{description}

The evaluation of a Tycoon thread does not use the persistent representation of its
registers directly to avoid expensive persistent store accesses in the virtual
machine. Instead of this, there is also a volatile representation for all
frequently used thread components such as registers and thread stacks which are
mapped to main memory by a special object store operation
\p{tsp\_openReadWriteLock} \cite{MMS95c}. Volatile and persistent thread
representations are synchronized prior to the following events: thread state
transition, global garbage collection, transaction commit and transaction
restart.

In case of a global transaction commit, all threads in a \p{running}
state are captured in a global list which constitutes the root of the
persistent object store. This design decision leads to a simple
and clean storage management strategy:
\begin{itemize}
\item All objects (in particular passive threads) that are
transitively reachable by an active thread are recognized by the
garbage collection as being ``alive'' and are stored persistently.

\item All other objects are garbage collected since there is no further
activity that can access them directly or indirectly.

\end{itemize}
We have designed the thread representation carefully to reduce references
between threads to a minimum.  This is not only necessary to avoid 
persistent storage leaks, but also to preserve the autonomy of threads
which is important for their mobility.


\subsection{Typed Thread Migration Gates}
\label{migration-gates}

In this section we describe how we implement migration of threads using local
thread manipulation operations and on top of a standard RPC communication
layer.

A simple ``passive'' thread migration takes place when a thread is passed as a
direct or indirect RPC-argument by another active thread. Workflows and agents
typically require an ''active'' thread migration since they initiate their
migration themselves. This requires some non-trivial implementation steps,
because the transmission of a migrating thread cannot be controlled completely
by itself since it is necessary to distinguish two evaluation states: the state
of the thread to be shipped and resumed at the receiver site as well as the
state of the thread that controls the communication steps. Moreover type-safe
bindings to local resources at the receiver site require special arrangements.

The module \p{gate} implements active thread migration. Since this module is
implemented completely in Tycoon, is is possible to describe active thread
migration in the remainder of this subsection at a high level of abstraction by
explaining the Tycoon source code, line by line. The module \p{gate} is based
on Tycoon's type-safe and type-complete RPC-mechanism which is described in
\cite{MMS95b} and \cite{Math96}.

First of all, the module \p{gate} defines a type operator \p{Parameter(Data)} which is
parametrized by the type \p{Data} of resources which will be bound dynamically
at the receiver site. 
\begin{xple}
  \k{Let} Parameter(Data {\st}Ok) = \k{Tuple}
    \k{var} data :optional.T(Data)
    agent :thread.T(Ok)
  \k{end}
\end{xple}
The implementation of this type operator is a tuple that aggregates the
migrating thread with a placeholder for the resources that will be supplied in
the target store.

The main type of the module (called \p{gate.T}) are remote {\em gates} to which
threads can migrate in order to enter remote object stores: 
\begin{xple}
  \k{Let} T(Data {\st}Ok) {\st}Service = \k{Tuple}
    transfer(parameter :Parameter(Data)) :Ok
  \k{end}
\end{xple}
A value of type \p{gate.T(Data)} is an RPC service which provides a single
function.  This function (\p{transfer}) is invoked by \p{gate.migrateTo} to
transmit packages of the matching type \p{Parameter(Data)}.

A typical application of \p{gate.migrateTo} looks as follows:
\begin{xple}
  \k{let} groupManagerSite = client.bind(\ldots  :T(ProjectBudgetDB))
  \dots 
  \k{let} projectBudgetDB = gate.migrateTo(groupManagerSite)
  \dots 
\end{xple}
First, the remote gate \p{groupManagerSite} is made accessible to the current
thread by means of an RPC client binding. When the thread ``passes'' this gate
with the \p{migrateTo} operation, a value that is determined by the respective
RPC service is returned and enters the scope of the thread function which is
now being executed at the remote site.

The type-safe implementation of \p{gate.migrateTo} looks as follows:
\begin{xple}
  \k{let} migrateTo(Data {\st}\k{Ok}  gate :T(Data)) :Data =
    \k{begin}
      \k{let} parameter = \k{tuple}
        \k{let} \k{var} data = optional.nil(:Data)
        \k{let} agent = thread.self\/()
      \k{end}
      thread.launch(\k{fun}(self :thread.T(\k{Ok}))
        \k{begin}
          gate.transfer(parameter)
          thread.kill(parameter.agent)
        \k{end})
      optional.value(parameter.data)
    \k{end}
\end{xple}
First, a package is created which aggregates the current thread and a null
value (placeholder) of type \p{Data} which will be updated by another function
at the receiver site. Second, a fresh thread is launched that carries out the
migration operations on the now ''passive'' thread
\p{parameter.agent}. Finally, the value stored in the field \p{parameter.date}
is returned to the caller (which is now being executed at the remote site).

The transmission of the package \p{parameter} is executed by a short-lived
local helper thread which is created (and started) by the thread primitive
\p{thread.launch}. The latter acts like \p{thread.fork}, but atomically also
suspends the calling thread. The local helper thread executes the anonymous
function that begins with the keyword \k{fun}. First, it calls the RPC
\p{gate.transfer} which transmits the package. Then it kills the local
representation of the already migrated thread. After this, the helper thread
terminates and as there are no references to it, the garbage collection will
release its resources.

The statement \p{optional.value(parameter.data)} which yields the
function result of \p{migrateTo} is executed by a copy of the migrated
thread on the recipient site. This results from the implementation of
the RPC service which constitutes the migration gate.

At the server site, the function \p{gate.new} creates a migration gate and
registers it dynamically as an RPC service. 
\begin{xple}
\k{let} new(dispatcher :server.T  \ldots   data() :Data) :sid.T(T(Data)) =
  \k{begin}
    \k{let} gate = \k{tuple}
      \k{let} transfer(parameter :Parameter(Data)) =
        \k{begin}
          parameter.data := optional.new(data())
          thread.run(parameter.agent)
        \k{end}
    \k{end}
    server.register(dispatcher  \ldots  gate)
  \k{end}
\end{xple}
The parameter \p{dispatcher} and further parameters not shown here are simply
passed on to the function \p{server.register} which registers a service
\p{gate} at the \p{dispatcher}. The type \p{Data} indirectly determines
the type (\p{T(Data)}) of the RPC service \p{gate} which is
constructed dynamically by the first binding in the function.  The function
\p{transfer} offered by the RPC service \p{gate} takes a parameter
of type \p{Parameter(Data)} that matches the packets generated by the
\p{migrateTo} function described above.

Note that access to the function \p{data} stems from a dynamic binding,
i.e. parameter passing. This dynamic binding and the assignment to
\p{parameter.data} implement the transfer of a local value into the scope of a
migrating thread in a type-safe way.  Moreover, it should be noted that
Tycoon provides higher-order functions such that the parameterless function
\p{data} can provide arbitrary objects from within the whole object store.

The examples in this subsection also demonstrate that Tycoon's polymorphic
type system is sufficiently expressive to describe the migration of 
threads with strongly-typed bindings to remote resources without resorting to
low-level, type-unsafe language primitives.


\subsection{Transactional Thread Migrations}
\label{transactions}

The preferred application domain for migrating threads is a loosely coupled
environment with highly autonomous subsystems. In such an environment,
consistency maintenance is limited to local data stores only.  If integrity
constraints do not span multiple systems, there is no need for large spheres of
control \cite{GrRe93} which have to protect concurrent distributed activities
against unwanted interference.

Migrating activities that are implemented by threads should refrain, as far as
possible, from complicating these simple conditions.  Therefore we advocate
binding techniques that support the autonomy of migrating threads and in
consequence the autonomy of visited sites.  The problematic nature of
distributed transactions is avoided wherever possible.

On the other hand, a thread migration itself may lead to concurrency-control
and recovery problems. In particular, the departure and the destination site
should establish a consistent view of the outcome of each migration
step. Otherwise, a thread instance could be duplicated or be lost. As a
consequence, a migration should be performed as a distributed transaction.  For
this purpose, the well-known two-phase commit technique
\cite{Gray78,LSG*79,Lamp81,ISOCCR90} is sufficient.

During migration, the client of a gate takes the role of a transaction
coordinator and of a transaction participant. The gate server acts as a
participant only.

It is important to suspend the reactivation of the migrating thread
until the transaction is completed. Otherwise, it could happen that some
actions must be undone in case of a transaction failure.

Besides the departure and the destination site of a migrating thread there can
be more sites that are indirectly affected by the transaction, because the
migration itself might be an application-relevant information. For example, it
might be interesting for a manager to know at which site a certain workflow is
situated or a user might want to know how far in physical terms an agent has
already traveled. As Tycoon does neither restrict distributed programming to
agent style (like Telescript \cite{GM95b}) nor to a pure client/server style,
there may also be ``tethered agents'' that are more or less under remote
control by a third-party site while they are roaming the network. It is
straight-forward to extend the simple migration transaction scheme by a set of
further 2PC participants to suit such scenarios.

\section{Conclusion}

We propose to enrich today's distributed programming models with 
higher-order concepts like first-class persistent and migrating threads and 
functions to provide better support for long-lived distributed activities 
like process modeling \cite{CKO92}, workflow management and network agent 
programming \cite{Whit94,Wayn94,TLKC95}.

At the system level, thread migration can be supported uniformly by 
techniques that are well-established in the persistent programming language 
world: stream representations of tagged object-graphs, portable code 
formats, function closures and polymorphic structural type checking.  
However, our experience with non-trivial activity-oriented applications 
shows that in order to avoid excessive communication or storage costs, 
additional system and language support has to be provided to support 
bindings to remote and ubiquitous resources.


More work is required to scale thread synchronization and coordination to a 
distributed, persistent scenario and to investigate the relationship 
between threads and transactions \cite{BDSSW93}.

\bibliographystyle{plain}
\bibliography{/users/dbis1/matthes/Referenzen/florian-macros,/users/dbis1/matthes/Referenzen/florian}

%% Do not delete this! ===>>>
\end{article}
\end{document}

