\section{Preliminaries}\label{sec:back}

Various systems and models have been described in the past for coordinating components in distributed settings. This section starts by presenting a simple abstract model of lookup, and then relating that model to a set of predating approaches.

\subsection{Lookup Model}

Components are described towards the outside world by respective \emph{specifications} (see Figure~\ref{fig:Crit}). Lookup services basically provide components, on one hand, a means to construct and advertise such specifications, and on the other hand, a mechanism to query components based on (specification) \emph{templates}. The composition and nature of these specifications and templates, as well as the \emph{matching} between them, vary between approaches. 

\vspace{-2mm}
\begin{figure}
\begin{center}
\includegraphics[scale=0.2]{projections_working}
\end{center}
\caption{Component and lookup model}\label{fig:Crit}
\end{figure}
\vspace{-5mm}



\paragraph{Internal vs. external specification.}

When viewing specifications as being based on different properties, one can in a first step distinguish 
between \emph{internal} and \emph{external} properties. Internal properties are based on the nature of components themselves, i.e., they reflect properties of a given component. %, whether these are more static/immutable properties, or dynamic/varying %ones. 
%On the other hand, 
External criteria reflect properties %, again static or dynamic, 
which pertain to the surroundings of the component, such as its context or (runtime) environment.


\paragraph{Implicit vs. explicit specification.}

In a second step, one can distinguish between \emph{implicit} and \emph{explicit} properties. The former kind of criteria 
reflect intrinsic properties \emph{of the services provided} by a given component; they are not influenced by the nature and set of targeted clients for that component, or the means by which the component is made available to such consumers. Explicit criteria in contrast, manifest in the way the component's very design is influenced by the perspective of making it ultimately available to the outside world. %, or the way it is ``published''. 


\paragraph{Static vs. dynamic evaluation.}

Furthermore, the evaluation of the matching can be 
\emph{static}, i.e., based on attributes of component specifications which are evaluated once and for all when the component is loaded, or \emph{dynamic}, in which case
 the matching becomes a continuous process (see Section~\ref{subsec:p2pimpl}). 

%\paragraph{Templates.}
%
%Components which are seeking components to interact with, query these based on specification templates. The matching performed by the lookup service between these and real specifications depends on the nature of both of these. Templates may, but do not have to, take into account all properties of specifications. 



%This can be illustrated by web servers that have two specifications: current number of clients versus maximum number of %simultaneous clients.
%While there is a clear relationship between those two values, it is not possible to deduce one from the other.
%Most lookup infrastructures are actually statics-based, requiring the components to remove their descriptions and resubmit the %new ones if the values change.


\subsection{Examples}

We illustrate the above model through a set of well-known lookup services, and overviewing derivatives for each. 
%We restrict our discussions to the basics of the respective approaches whenever a more thorough presentation would not change the resulting classification. 
Results are summarized in Table~\ref{tab:coarse} (due to the sparse occurrence of dynamic criteria in common lookup services the distinction static/dynamic is however omitted).
%Concrete applications of model will be presented in Section~\ref{sec:xamples}.

\paragraph{Domain Name System (DNS).} %explicit internal
DNS is very likely to be the most frequently used, static, name-based lookup system. 
%value-based, statics-based lookup system. 
Components are IP addresses, the specifications are (internal) host names, the templates are host names as well, and the matching tries to find the component that registers with a given host name (explicitly) and returns it's IP if possible.

\paragraph{Network Information Service (NIS).} %implicit external
NIS is one of the oldest type-based, static lookup systems.
Components are the entries of the maps (external), the specifications are map names (implicit), the templates are either map names or nicknames (e.g., $passwd$ for $passwd.byname$), and the matching is the result of the \texttt{ypcat} command. 

\paragraph{CORBA.}

The Common Object Request Broker Architecture (CORBA)~\cite{CORBA3} defines both a Naming Service and Trading Object Service for name-based and type-based lookup of objects respectively. The Naming Service represents the original means of looking up objects based on a \emph{hierarchical} naming scheme, where an object is registered (explicit) and made available by attaching it (external) a unique name  $N_1.\cdot\cdot\cdot.N_{n}$ of which each component $N_i$ is a name/kind-pair. In this case, specifications and templates are both defined as sets of such pairs. Names for the Java RMI registry, or regular expressions, are similar in that sense, with $n=1$.

The Trading Object Service offers rich combinations of means of defining the service type of a component. The most preferred way of attaching a type specification to a component consists in attaching it a name/value-pair. This definition of a component is external and explicit as well: the ``type'' describes actual properties of the component itself, but is not implicit like the actual classification of a component according to the type system of the considered language/environment.

Note that the OMG has more recently specified the Interoperable Name Service, defining URL-format object references that can be typed into a program to reach services at a remote location, including the Naming Service. 
%A second URL format actually invokes the remote Naming Service using the name that
%the user appends to the URL, and retrieves the IOR of the named object.
%It seems thus that despite the richness of CORBA`s two predating specifications for 
%lookup, and well-engineered implementations, the ideal solution has not been found 
%yet. A more abstract view of components and their lookup, such as proposed in this 
%paper, might represent a way out of this odyssey.

\paragraph{RM-ODP.}

 
The Reference Model for Open Distributed Processing (RM-ODP)~\cite{BS97} defines, similarly to CORBA, both a ``white pages'' (name-based) and ``yellow pages'' (type-based) lookup service (both explicit and external), going by the names of relocator and trader respectively. The latter service describes two roles which interacting components may take: \emph{exporters} of services, and \emph{importers}. A \emph{service description} is an interface (type) and a set of properties attached to it, and a \emph{service offer} binds a service description to a concrete component, which can be a CORBA object or another object.
Properties are thus used to describe specifications and templates, the latter ones being more precisely combinations of properties; rules are expressed based on properties and operators (these are called matching criteria).

A novelty of the trader specification is the description of delegation and collaboration among individual trader units, which however does not seem to impact the model ultimately perceived by an application programmer, as, expressed in our terminology, specifications are simply cascaded.


\paragraph{UDDI.}\label{par:uddi}

The \emph{universal description, discovery and integration} (UDDI)~\cite{829340} specification defines a lookup service for Web Services. Such a \emph{registry} is centered around a \emph{public cloud}, a set of replica nodes storing white pages (abstract services by "name"), yellow pages (by "type"), and green pages (by "description" and "location"). Targeting at Web Services, UDDI encompasses a set of XML messages for SOAP-based interaction with registries.
Each party is described through a \emph{business entity}, several of which can be linked through \emph{publisher assertion}s. A \emph{business service} is a particular Web Service offered by a business entity. Such a service is described by one or more \emph{binding templates}, which optionally contain textual service descriptions, and URLs for the respective services. Finally, \emph{binding templates} refer to one or more \emph{tModel}s, which contain the pointers to actual descriptions of the services offered, and delineate the interaction protocols with the respective services.
All the above-mentioned entities describe a refined pattern for specifications in the sense of our model introduced before-hand. The enforcing of authentication is covered in our model by external explicit criteria (see Section~\ref{subsec:secure}).  The load distribution among nodes forming the public cloud is achieved in our implementation in an efficient manner by distributing the matching, greatly transparently, over a peer-to-peer overlay network (see Section~\ref{subsec:p2pimpl}).
 
Note that UDDI is a rare example of dynamic lookup, where components can be notified of changes in specifications of other components. Further examples are given by load balancing, or reuse frequency~\cite{BayPauls05}.

\paragraph{Service Groups.}

Sadou et al. \cite{SAKOMI01} introduce a notion of \emph{service group} to mediate between client and server components. These are motivated by the desire for type evolution, e.g., the possibility of adding parameters to methods. Just like in RM-OPD, the approach introduces both a notion of \emph{type} which reflects provided services (i.e., the server side) in the terminology introduced by the authors, and a notion of \emph{role} which represents the needs of customers (i.e., the client side).

At a first glance, one could hence be brought to viewing the types of \cite{SAKOMI01} as specifications in our case, roles as templates, and service groups as defining the matching, respectively. However, the emphasis of \cite{SAKOMI01} consists in making services of a given type available to clients expecting a slightly different type. Service groups are thus a form of glue aiming at expressing \emph{how to pass from a given type to a given role}. They consist in stubs for respective server objects, which transform invocations based on a given role (the expected type) such as to fit the effective type. In our model, this represents explicit, internal component registration, and the specifications are made up of the stubs. 
%The matching reported in Figure~\ref{fig:Crit} consists in defining, based on 
%specifications --- in this case to be seen as service groups --- \emph{whether a given 
%type matches a given role}.

In a sense, HydroJ~\cite{949324} and LuckyJ~\cite{os2004iee}, can be seen as similar approaches to service groups, as these are also based on some notion of type. Borrow/Lend~\cite{EB05}, a derivative of the Type-based Publish/Subscribe (TPS) abstraction~\cite{EG04}, as suggested by the name of the latter paradigm, in contrast, is primarily based on type-based matching of inherent Java object types (implicit, internal). The types are augmented by (dynamic) predicate evaluation, and with keys (explicit, external).

\paragraph{Coordination Spaces.}

The Borrow/Lend abstraction can in fact be seen as a variant of the Linda Tuple Space~\cite{Carriero85} with callback functionalities. The original Tuple Space is a means of exchanging information among distributed components, based on tuples of place holders (types) and values, i.e., a mixture of value-based and type-based matching, where values can also be character strings. This demonstrates how thin the border between types and values is. 

Just like Borrow/Lend, Tagged Sets~\cite{Oriol:05:TSASTCM} are a variant of Tuple Spaces, where tuple items can also be predicates (leading to a dynamic evaluation), or keys (symmetric or asymmetric). Similarly, SecOS~\cite{BOV99}, supports the use of keys, with a partial matching. Clearly, any such criterion is explicit and external.

\vspace{-2mm}
%% TODO reference table somewhere...
\begin{table}
\begin{tabular}{|p{1.5cm}||p{5.2cm}|p{5.2cm}|}
\hline
Criteria & Explicit & Implicit \\
\hline \hline
External 
& UDDI, CORBA Naming, Trading, Java RMI, Linda, Regular Expressions, Tagged Sets, Borrow/Lend, SecOS & Reuse Frequency, Load Balancing, NIS\\ 
\hline 
Internal & HydroJ, LuckyJ, Service Groups, DNS & Method Dispatch, Borrow/Lend\\
%&  & \\
\hline
\end{tabular}
\caption{Coarse classification of lookup services}\label{tab:coarse}
\end{table}
\vspace{-8mm}


\subsection{A Note on Values and Types}\label{sec:valsVsTypes}

A distinction that is often made when discussing component lookup is the one between \emph{values} and \emph{types}. This is nicely illustrated by the metaphors of ``white pages'' and ``yellow pages'' respectively. 
%An example of a white page-like lookup is the CORBA Naming Service, where a name %is attached to each registered component, and is used to find that component. An often %cited example of a yellow page-like lookup is the CORBA Trading Service, where a service description is attached to every component. 
%Another example for a yellow page service which is complementary to the above-%
%mentioned is the Borrow/Lend abstraction~\cite{EB05}, where a component can
% express interest in components which implement a given type in the programming
% language sense (and satisfy predicates).

However, component lookup in a distributed heterogeneous environment is basically untyped. Matching components for their ``type'' boils down to matching such components for the \emph{name of their type}, an internal property of these components. The possibility of registering several objects under a same given name, as supported by many systems, illustrates this seamless transition; by doing so, such a name becomes more a type description than a unique identifier. The issue of matching in such a setting becomes essentially a question of \emph{depth}, in a way similar to the issue of object copying/cloning~\cite{GS00}. Any categorical distinction between values and types at this level seems unnatural. This is captured by our abstract notions of specifications and templates, which will become clearer through the matching model presented in Section~\ref{sec:model}, and illustrations thereof in Section~\ref{sec:xamples}.

