% File:    mthreads.tex
% Author:  Bernd Mathiske, Florian Matthes
% Date:    02-MAY-1995
% Purpose: NGITS 95 Israel, Paper for Proceedings

\documentstyle[twocolumn,xple_sl,epsf,a4]{article}
\pagestyle{empty}
\setlength {\textheight} {24cm}
\setlength {\columnsep} {2.0pc}
\setlength {\textwidth} {17cm}
\setlength {\footheight} {0.0in}
\setlength {\topmargin} {0.25in}
\setlength {\headheight} {0.0in}
\setlength {\headsep} {0.0in}
% \setlength {\oddsidemargin} {-.19in}                                        
                                        
\newcommand{\sep}{\noindent\rule{\textwidth}{0.5pt}}
\newcommand{\e}[1]{{\em #1\/}}
\newcommand{\p}[1]{{\sl{}#1}}
\newcommand{\k}[1]{{\bf{}#1}}
\newcommand{\R}{$\Rightarrow$}
\newcommand{\r}{$\rightarrow$}
\newcommand{\comment}[1]{{\it #1}}
\renewcommand{\labelitemi}{$\triangleright$}

%avoid excessive space between enumeration items
\newcommand{\FM}{
\setlength{\topsep}{0pt}
\setlength{\parskip}{0pt}
\setlength{\itemsep}{0pt plus 0.5ex}
%\setlength{\parsep}{0pt}
\setlength{\partopsep}{0pt}}

\FM

\title{On Migrating Threads}

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

\begin{document}
\maketitle

\begin{abstract} 

\noindent Based on the notion of persistent threads in 
Tycoon\footnote{Tycoon $=$ Typed Communicating Objects in Open Environments 
\cite{MaSc92a,MMS94}} \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.

\thispagestyle {empty}   

\end{abstract}


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

Most of the work on migrating threads described in this paper 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 in this 
paper 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 
paper reports on our ongoing 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 the paper 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. 

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

\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.

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{figure*}
\begin{center}
\begin{tabular}{|l|ll|}
\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}
\end{center}
\caption{Thread-based implementations of cooperative activities}
\label{matrix}
\end{figure*}

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

\begin{itemize} \item The lifetime of a thread is limited by its enclosing 
operating system process.

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

As described in \cite{MaSc94}, a generalization towards \e{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=8.2cm
\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 
\e{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.  (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, \ldots) 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 the 
paper 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}, \ldots) 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 \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.


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

\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 sugar'' to hide the underlying infrastructure from 
high-level workflow script programmers.

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

\begin{xple}\small
\k{interface} Thread \k{export}
  error, abortion :\k{Exception}
  T(R $<$:\k{Ok}) $<$:\k{Ok}
  State $<$:\k{Ok}
  runningState, blockingState, suspendedState, 
  terminatedState, exceptionState :State
  state(R $<$:\k{Ok}  thread :T(R)) :State
  new, fork(R $<$:\k{Ok}  f(self :T(R)) :R) :T(R)
  suspend, run, abort, kill(R $<$:\k{Ok}  thread :T(R)) :\k{Ok}
  join(R $<$:\k{Ok}  thread :T(R)) :R
  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}
  atomic(R $<$:\k{Ok}  action() :R) :R
  \ldots
\k{end}
\end{xple}

In Tycoon, threads are \e{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} (\p{new, fork, suspend, \ldots}), as 
well as user-defined functions that depend on a specific thread result type.

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}), the \p{thread} module exports further synchronization 
primitives (semaphores, mutexes and condition variables) not shown here.

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=8.2cm
\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.\footnote{In addition \p{groupManagerSite.execute} passes a local binding  (\p{projectBudgetDB}) as a parameter to \p{step3}.}
In this approach iteration has to be expressed by recursion.
\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}
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.

\begin{figure}
\begin{center}\leavevmode
\epsfxsize=8.2cm
\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 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 a mere 
syntactic sugar realized by Tycoon's extensible syntax \cite{CMA94} for 
Tycoon library calls which 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 \e{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 Fig~\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 \e{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 
(that 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=8.2cm
\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} and SOS \cite{SGM89,Shap93}).

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, \ldots\ 
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{Concluding Remarks}

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}.

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}.

\small
\bibliographystyle{alpha}
\bibliography{/users/dbis1/matthes/txt/bib/florian-macros,/users/dbis1/matthes/txt/bib/florian}

\end{document}
