--- /dev/null
+\documentclass[10pt,conference]{llncs}
+
+\usepackage[T1]{fontenc}
+\usepackage{ucs}
+\usepackage[utf8x]{inputenc}
+\usepackage{lmodern}
+\usepackage{color}
+\usepackage{amsmath}
+\usepackage{amsfonts}
+\usepackage[english]{babel}
+\usepackage[pdftex,final]{graphicx}
+\usepackage[ruled,vlined]{algorithm2e}
+\usepackage[pdftex]{graphicx}
+\usepackage{multirow}
+\DeclareGraphicsExtensions{.pdf,.jpeg,.png}
+
+
+\title{MAHEVE: An Efficient Reliable Mapping of Asynchronous Iterative
+ Applications on Volatile and Heterogeneous Environments \thanks{This
+ work was supported by the European Interreg IV From-P2P
+ project.}}
+
+
+\author{Raphaël Couturier, David Laiymani and Sébastien Miquée}
+ \authorrunning{R. Couturier, D. Laiymani and S. Miquée}
+ \institute{\vspace{-0.2cm}
+ University of Franche-Comté \qquad LIFC laboratory\\%[1mm]
+ IUT Belfort-Montb\'eliard, 2 Rue Engel Gros \\ BP 27 90016 Belfort,
+ France\\\{{\tt
+ raphael.couturier,david.laiymani,sebastien.miquee}\}{\tt
+ @univ-fcomte.fr} }
+
+
+\date{}
+\begin{document}
+
+
+\maketitle
+
+\vspace{-0.2cm}
+
+\begin{abstract}
+ With the emergence of massive distributed computing resources, such
+ as grids and distributed clusters architectures, parallel
+ programming is used to benefit from them and execute problems of
+ larger sizes. The asynchronous iteration model, called AIAC, has
+ been proven to be an efficient solution for heterogeneous and
+ distributed architectures. An efficient mapping of applications'
+ tasks is essential to reduce their execution time. In this paper we
+ present a new mapping algorithm, called MAHEVE (Mapping Algorithm
+ for HEterogeneous and Volatile Environments) which is efficient on
+ such architectures and integrates a fault tolerance mechanism to
+ resist computing nodes failures. Our experiments show gains on a
+ typical AIAC application execution time of about $55\%$, executed
+ on distributed clusters architectures containing more than 400
+ computing cores with the JaceP2P-V2 environment.
+\end{abstract}
+
+\section{Introduction}
+\label{sec:intro}
+
+Nowadays, scientific applications require a great computation power to
+solve large problems. Though personal computers are becoming more
+powerful, in many cases they are not sufficient. One well adapted
+solution is to use computers clusters in order to combine the power of
+many machines. Distributed clusters form such an architecture,
+providing a great computing power, by aggregating the computation
+power of multiple clusters spread over multiple sites. Such an
+architecture brings users heterogeneity in computing machines as well
+as network latency. In order to use such an architecture, parallel
+programming is required. In the parallel computing area, in order to
+execute very large applications on heterogeneous architectures,
+iterative methods are well adapted\cite{book_raph,bcvc06:ij}.
+
+
+These methods repeat the same instructions block until a convergence
+state and a desired approximation of the solution are reached. They
+constitute the only known approach to solving some kinds of problems
+and are relatively easy to parallelize. The Jacobi or the Conjugate
+Gradient\cite{cg} methods are examples of such methods. To parallelize
+them, one of the most used methods is the message passing paradigm
+which provides efficient mechanisms to exchange data between tasks. As
+such a method, we focus here on the asynchronous parallel iterative
+model, called AIAC\cite{book_raph} (for \textit{Asynchronous
+ Iterations -- Asynchronous Communications}).
+
+\begin{figure}[h!]
+ \vspace{-0.4cm}
+ \centering
+ \includegraphics[width=7.4cm]{images/AIAC}
+ \caption{Two processors computing in the Asynchronous Iterations -- Asynchronous Communications (AIAC) model}
+ \label{fig:AIAC}
+ \vspace{-0.90cm}
+\end{figure}
+
+
+In this model, as can be seen on Figure \ref{fig:AIAC}, after each
+iteration, a task sends its results to its neighbors and immediately
+starts the next iteration with the last received data. The receiving
+and sending mechanisms are asynchronous and tasks do not have to wait
+for the reception of dependency messages from their
+neighbors. Consequently, there is no idle time between two
+iterations. Furthermore, this model is tolerant to messages loss and
+even if a task is stopped the remaining tasks continue the
+computation, with the last available data. Several
+experiments\cite{bcvc06:ij} show the relevance of the AIAC algorithms
+in the context of distributed clusters with high latency between
+clusters. These works underline the good adaptability of AIAC
+algorithms to network and processor heterogeneity.
+
+
+In a previous study\cite{pdsec10} we proposed the implementation of
+two static mapping algorithms of tasks to processors dedicated to the
+AIAC model on heterogeneous distributed clusters. Both these two
+algorithms, AIAC-QM (for \textit{AIAC Quick-quality Map}) and F-EC
+(for \textit{Farhat Edges-Cuts}) showed an important performances
+improvement by significantly reducing the application execution
+time. These experiments were performed by using the fully fault
+tolerant JaceP2P-V2 environment, described in next section.
+%This Java based platform is an executing and developing
+%environment dedicated to the AIAC model. By implementing a distributed
+%backup/restore mechanism it is also fully fault
+%tolerant\cite{jaceP2P-v2}.
+In our previous experiments we did not introduce computing nodes
+failures during the computation. As architecture heterogeneity
+continually evolves according to computing nodes volatility, we have
+to take care more precisely about the heterogeneity of the target
+platform. Thus in this paper our main contribution is to propose a new
+mapping algorithm called MAHEVE (\textit{Mapping Algorithm for
+ HEterogeneous and Volatile Environments}). This algorithm
+explicitly tackles the heterogeneity issue and introduces a level of
+dynamism in order to adapt itself to the fault tolerance
+mechanisms. Our experiments show gains up to $65\%$ on application
+execution time, with faults during executions, which is about 10
+points better than AIAC-QM and about 25 points better than F-EC, and
+MAHEVE also outperforms them in experiments with no fault during executions.
+
+
+The rest of this paper is organized as
+follows. Section~\ref{sec:jacep2p} presents the JaceP2P-V2 middleware
+by describing its architecture and briefly presenting its fault
+tolerance mechanisms. Section~\ref{sec:pb} formalizes our mapping and
+fault tolerance problems and quotes existing issues to address
+them. Section~\ref{sec:maheve} describes the new mapping strategy we
+propose, MAHEVE. In Section~\ref{sec:expe} we present the experiments
+we conducted on the Grid'5000 testbed with more than 400 computing
+cores. Finally, we give some concluding remarks and plan our future
+work in Section~\ref{sec:conclu}.
+
+
+\section{JaceP2P-V2}
+\label{sec:jacep2p}
+
+JaceP2P-V2\cite{jaceP2P-v2} is a distributed platform implemented in
+Java, dedicated to developing and executing parallel iterative
+asynchronous applications. It is fully fault tolerant allowing it to
+execute parallel applications over volatile environments. To our
+knowledge this is the only platform dedicated to designing and
+executing AIAC algorithms in such volatile environments.
+
+
+The JaceP2P-V2 platform part, which is based on the daemons and
+supervisors paradigm, is composed of three main entities:
+\begin{itemize}
+\item The ``super-nodes'', which are in charge of supervising free
+ computing nodes connected to the platform;
+
+\item The ``spawner'', which is launched by a user wanting to execute
+ a parallel application. It is in charge of a group of computing
+ nodes and monitors them. If one of them fails, it requires a
+ replacing one to a super-node;
+
+\item The ``daemon'', first connects to a super-node and
+ waits for a task to execute. Each daemon can communicate directly
+ with its computing neighbors.
+\end{itemize}
+
+
+To be able to execute AIAC applications, JaceP2P-V2 has an
+asynchronous messaging mechanism, and to resist daemons failures, it
+implements a checkpoint/restart mechanism by using a distributed
+backup mechanism called the \textit{uncoordinated distributed
+ checkpointing}\cite{uncoord_cp}. This decentralized procedure
+allows the platform to be very scalable, with no weak points and does
+not require a secure nor a stable station for backups. When a daemon
+dies, it is replaced by another one, as we suppose that there are
+enough available free nodes. Moreover, to resist supervisors failures
+and for scalability, some extra nodes are reserved. For more details
+on the JaceP2P-V2 platform, interested readers can refer to
+\cite{jaceP2P-v2}.
+
+
+\section{Mapping and fault tolerance problems}
+\label{sec:pb}
+
+\subsection{Model formalization}
+\label{sec:pbmodel}
+
+\subsubsection{Application modeling}
+\label{sec:pbmodelapp}
+
+
+%With the AIAC model, all tasks compute in parallel at the same time,
+%without precedence nor synchronization. During an iteration, each task
+%computes its job and sends its results to its neighbors, and
+%immediately starts the next iteration.
+The TIG\cite{tig1} (\textit{Task Interaction Graph}) model is the most
+appropriate to our problem, as it only models relationships between
+tasks. In this model, all the tasks are considered simultaneously
+executable and communications can take place at any time during the
+computation, with no precedence nor synchronization. As a reminder,
+during an iteration in the AIAC model, each task computes its job and
+sends its results to its neighbors, and immediately starts the next
+iteration.
+
+
+In the TIG model, a parallel application is represented by a graph
+$GT(V,E)$, where \mbox{$V = \{V_1,V_2,\dots V_v\}$} is the set of
+$|V|$ vertices and \mbox{$E \subset V \times V$} is the set of
+undirectional edges. The vertices represent tasks and the edges
+represent the mutual communication among tasks. A function \mbox{$EC :
+ V \rightarrow \mathbb{R}^+$} gives the computation cost of tasks and
+\mbox{$CC : E \rightarrow \mathbb{R}^+$} gives the communication cost
+for message passing on edges. We define \mbox{$|V| = v$, $EC(V_i) =
+ e_i$} and \mbox{$CC(V_i,V_j) = c_{ij}$}. Another function
+\mbox{$D : V \rightarrow \mathbb{N}^+$} gives the amount of
+dependencies of a task, and we define \mbox{$D(V_i) = d_i$}.
+
+
+\subsubsection{Architecture modeling}
+\label{sec:pbmodelarchi}
+
+
+A distributed clusters architecture can be modeled by a
+three-level-graph. The levels are \textit{architecture} (a) (here the
+Grid'5000 grid), \textit{cluster} (c), and \textit{computing node} (n)
+levels. Let $GG(N,L)$ be a graph representing a distributed clusters
+architecture, where \mbox{$N = \{N_1,N_2,\dots N_n\}$} is the set of
+$|N|$ vertices and $L$ is the set of $|L|$ undirectional edges. The
+vertices represent the computing nodes and the edges represent the
+links between them. An edge \mbox{$L_i \in L$} is an unordered pair
+\mbox{$(N_x,N_y) \in N$}, representing a communication link between
+nodes $N_x$ and $N_y$. A function \mbox{$WN : N \rightarrow
+ \mathbb{R}^+$} gives the computational power of nodes and another
+function \mbox{$WL : L \rightarrow \mathbb{R}^+$} gives the
+communication latency of links. We define \mbox{$WN(N_i) = wn_i$} and
+\mbox{$WL(L_i,L_j) = wl_{ij}$}. Let be $|C|$ the number of clusters
+contained in the architecture. A function \mbox{$CN : C \rightarrow
+ \mathbb{N}^+$} gives the amount of computing nodes contained in a
+cluster, and another function \mbox{$CF : C \rightarrow \mathbb{N}^+$}
+gives the amount of available computing nodes (not involved in
+computation) of a cluster. We define \mbox{$CN(C_i) = C_{Ni}$} and
+\mbox{$CF(C_i) = C_{Fi}$}. We also define
+%\mbox{$C_{Pi}
+% = \sum_{j=1}^{C_{Ni}}{wn_j}$} as the whole computation power of
+%cluster $C_i$, \mbox{$C_{\overline{P}i} = \frac{C_{Pi}}{C_{Ni}}$}
+%as the average computation power of cluster $C_i$, and
+$C_{\overline{P}fi}$ as the average power of available resources of
+cluster $C_i$.
+
+We evaluate the \textit{heterogeneity degree} of the architecture,
+noted $hd$, by using the \textit{relative standard deviation} method,
+with $hd = \frac{\sigma_{PN}}{avg_{PN}}$ where $avg_{PN}$ is the
+average computing power of nodes and $\sigma_{PN}$ represents the
+standard deviation of computing nodes power. This measure provides us
+the coefficient of variation of the platform in percentage -- we only
+consider \mbox{$0 \leq hd \leq 1$} as considering values of \mbox{$hd
+ > 1$} is not relevant, as \mbox{$hd = 1$} denotes a fully
+heterogeneous platform.
+
+\vspace{-0.1cm}
+\subsubsection{Mapping functions}
+\label{sec:pbmodelmapping}
+
+
+When a parallel application $App$, represented by a graph $GT$, is
+mapped on a distributed clusters architecture, represented by a graph
+$GG$, the execution time of the application, $ET(App)$, can be defined
+as the execution time of the slowest task. Indeed, an application ends
+when all the tasks have detected convergence and reached the desired
+approximation of the solution. We define $ET(App) = \max_{i=1 \dots
+ v} ( ET(V_i) )$, where the execution time of each task $i$
+\mbox{($i=1 \dots v$)}, $ET(V_i)$, is given by $ET(V_i) =
+\frac{e_i}{wn_i} + \sum_{j \in J} c_{ij} \times wl_{ij}$ where $e_i$
+is the computational cost of $V_i$, $wn_i$ is the computational power
+of the node $N_i$ on which $V_i$ is mapped, $J$ represents the
+neighbors set of $V_i$, $c_{ij}$ is the amount of communications
+between $V_i$ and $V_j$, and $wl_{ij}$ is the link latency between the
+computing nodes on which $V_i$ and $V_j$ are mapped. As described in
+this formula, the execution time of a task depends on the task weight
+and on the communications which may occur between this task and its
+neighbors. We underline here that in the AIAC model, it is impossible
+to predict the number of iterations of a task. So it is difficult to
+evaluate a priori its cost $e_i$.
+
+
+This tasks mapping problem is similar to the classical graph
+partitioning and task assignment problem, and is thus NP-complete.
+
+
+\subsection{Fault tolerance}
+\label{sec:pbft}
+
+In volatile environments, computing nodes can disconnect at any time
+during the computation, and have thus to be efficiently replaced.
+The replacing nodes should be the best ones at the fault time,
+%according to the chosen mapping algorithm,
+by searching them in
+available nodes. As executing environments can regularly evolve, due
+to computing nodes volatility, a mapping algorithm has to keep a
+correct overview of the architecture, in real time. Thus, criteria to
+assign tasks to nodes should evolve too.
+
+
+Another problem appears after multiple crashes: some tasks may have
+migrated over multiple computing nodes and clusters, and the initial
+mapping may be totally changed. So, after having suffered some nodes
+failures the tasks mapping could not always satisfy the mapping
+criteria (not on the more powerful available machine, too far away
+from its neighbors\dots{}). A good fault tolerance policy has to
+evolve dynamically with the executing
+environment.
+
+
+\subsection{Specificities of the AIAC mapping problem}
+\label{sec:specAIACmapping}
+
+An important point to take into consideration is that we do not allow
+the execution of multiple tasks on the same computing node, as this
+provides a fall of performances when this one fails. Indeed we should
+redeploy all of the tasks from this node to another one, using last
+saves, which can be spread on multiple computing nodes. This may
+result in large communication overheads and in a waste of computation
+time. Nevertheless, to benefit from multi-cores processors, we use a
+task level parallelism by multi-threaded sequential solvers for
+example.
+
+
+Another important point in the AIAC model is that as the JaceP2P-V2
+environment is fault tolerant and tasks save checkpoints on their
+neighbors, it is more efficient to save on near nodes than on far ones
+in order to reduce the communication overhead during this operation,
+and to restart a task faster.
+
+
+\subsection{Related work}
+\label{sec:pbrw}
+
+In the literature of the TIG mapping many algorithms exist, which can
+be broadly classified into two categories. The first one is the
+\textit{Edge-cuts optimization} class, which minimizes the use of the
+penalizing links between clusters. As tasks are depending on
+neighbors, which are called dependencies, the goal is to choose nodes
+where distance, in term of network, is small to improve communications
+between tasks. Here we can cite the Farhat's algorithm\cite{fec}, and
+Metis\cite{metis} and Chaco\cite{chaco} which are libraries containing
+such kind of algorithms. The second category is the \textit{Execution
+ time optimization} class, which aims at minimizing the whole
+application execution time. These algorithms look for nodes which can
+provide the smallest execution time of tasks using their computational
+power. Here we can cite QM\cite{qm_these}, FastMap\cite{fastmap}, and
+MiniMax\cite{minimax} as such kind of algorithms.
+
+
+Both classes of algorithms may fit with our goals as in our model we
+have both the computational power of nodes and communication costs
+which may influence the applications performances.
+
+
+All mentioned algorithms do not tackle the computing nodes failures
+issue, or only basically by applying the same policy. As explained in
+Section \ref{sec:pbft}, a more efficient and dedicated replacement
+function is needed. Nevertheless, to the best of our knowledge, no
+tasks mapping algorithm, addressing explicitly both the executing
+platform heterogeneity and the computing nodes failures issues,
+exists.
+
+
+\vspace{-0.25cm}
+\section{MAHEVE}
+\label{sec:maheve}
+
+Here we present our new tasks mapping strategy, called MAHEVE (for
+\textit{Mapping Algorithm for HEterogeneous and Volatile
+ Environments}). This algorithm aims at taking the best part of each
+category mentioned in Section \ref{sec:pbrw}, the edge-cuts
+minimization and the application execution time optimization
+algorithms.
+
+
+This new algorithm can be divided into two parts. The first part aims
+at performing the initial mapping, and the second part is devoted to
+search replacing nodes when computing nodes failures occur.
+
+
+\vspace{-0.20cm}
+\subsection{Initial mapping}
+\label{sec:maheve_init}
+
+In this section we will study the main mechanisms of the
+\textit{static mapping} done by MAHEVE, which is composed of three
+phases: sort of clusters, sort of tasks, and the effective mapping,
+which maps tasks (in their sort order) on nodes of clusters (also in
+their sort order) with a reservation of some nodes in each cluster.
+
+
+%\begin{algorithm}[H]
+% \SetLine
+% \KwIn{GT (app. graph), CL (clusters), hd (heterogeneity degree)}
+% \KwOut{Mp (the mapping done)}
+%
+% \BlankLine
+%
+% nodes $\leftarrow$ sortingClusters(GG, hd)\;
+%% nodes $\leftarrow$ searchNodes(lt, nbTasks)\;
+%
+%% \BlankLine
+%
+% tasks $\leftarrow$ sortingTasks(GT, hd)\;
+%% tasks $\leftarrow$ orderTasks(st, hd)\;
+%
+%% \BlankLine
+%
+% \For{$i = 0$ \KwTo $size(tasks)$}
+% {
+% Mp.add(tasks($i$), nodes($i$))\;
+% }
+%
+%% \KwRet(Mp)
+%
+% \caption{General algorithm simplified}
+%\end{algorithm}
+
+
+\vspace{-0.15cm}
+\subsubsection{Sorting clusters}
+\label{sec:maheve_sort_clusters}
+
+The first step of the initial mapping is to sort clusters according to
+the executing platform heterogeneity degree $hd$. The main principles
+are that a cluster obtains a better mark when $hd < 0.5$ and it
+contains more computing nodes than other clusters ($C_{Fi}$, the
+number of available free nodes, is privileged), and when $hd \ge 0.5$
+and it contains more powerful computing nodes ($C_{\overline{P}fi}$,
+the average free computation power, is privileged). These choices come
+from several experiments with the AIAC model, which show that in such
+environments it is more efficient to privilege the computation power
+or the number of nodes. As the number of nodes, $C_{Fi}$, and the
+average free computing power, $C_{\overline{P}fi}$, are not in the
+same order of magnitude, we normalize them with two functions, $normN$
+and $normP$.
+%They are defined with \mbox{$normN\left(C_{Fi}\right) =
+% C_{Fi} \times 100 \div \sum_{j=1}^{|C|}C_{Fj}$}, which is the rate
+%of computing nodes, and \mbox{$normP(C_{\overline{P}fi}) =
+% C_{\overline{P}fi} \times 100 \div \sum_{j=1}^{|C|}
+% C_{\overline{P}fj}$}, which is the rate of the average power, both
+%representing the cluster in the architecture.
+We note $normN\left( C_{Fi} \right) = NC_{Fi}$ and
+$normP(C_{\overline{P}fi}) =NC_{\overline{P}fi}$.
+
+
+The formula used to give a mark, $M_i$, to a cluster is
+\begin{equation}
+ \label{eq:cluster}
+ M_i = {NC_{\overline{P}fi}}^{hd} + {NC_{Fi}}^{1 - hd}.
+\end{equation}
+
+
+This compromise function allows us to privilege clusters following our
+criteria, as explained previously, according to the heterogeneity
+degree. If we study its limits for the $hd$'s extremities, $hd = 0$
+and $hd = 1$, we obtain $\lim_{hd \rightarrow 0} M_i = NC_{Fi} + 1$ and
+$\lim_{hd \rightarrow 1} M_i = NC_{\overline{P}fi} + 1$, which fit with
+our objectives.
+
+Clusters are so sorted and placed in a list containing them, starting
+from the cluster which receives the better mark to the one which
+receives the lower mark.
+
+
+\subsubsection{Sorting tasks}
+\label{sec:maheve_sort_tasks}
+
+Like clusters, tasks are also sorted according to the heterogeneity
+degree of the executing platform. This sorting is done in the same way as
+previously, as when $hd < 0.5$ tasks with higher dependencies will be
+privileged, and when $hd \ge 0.5$ tasks with higher computing cost are
+privileged.
+%, in order to be executed on the highest powered computing nodes.
+
+
+The main function used to classified tasks is
+\begin{equation}
+ \label{eq:tasks}
+ Q_i = {e_i}^{hd} \times {d_i}^{1 - hd}
+\end{equation}
+
+where $Q_i$ is the evaluation of the task $i$ according to the
+heterogeneity degree $hd$ and $d_i$, the amount of dependencies of
+task $i$.
+
+
+Tasks are taken in the order of the first sort, determined with
+equation (\ref{eq:tasks}), and each task is placed in a new list (the
+final one) and some of its dependencies are added. We note $Nb_i =
+{d_i}^{1 - hd}$ this amount of dependencies as the lower the
+heterogeneity degree is the higher this number will be. This final
+operation allows to control the necessary locality of tasks according
+to $hd$. %the heterogeneity degree of the platform.
+
+
+\subsubsection{Mapping method}
+\label{sec:maheve_mapping_method}
+
+The third step of the initial mapping is to allocate tasks to
+nodes. As clusters and tasks have been sorted accordingly to the
+executing platform heterogeneity degree, ordered from the highest mark
+to the lowest, this function maps tasks on almost all available
+computing nodes of clusters, in their respective order in lists (for
+example a task classified first in the tasks list is mapped on an
+available node of the cluster classified first in the clusters list).
+The idea here is not to fulfill each cluster, but to preserve some
+computing nodes in each cluster. These conserved nodes will be used to
+replace failed nodes.
+
+
+Here we can mentioned that the whole mapping process (the three steps)
+has a complexity of $O( |V| log(|V|) )$, where |V| is the number of tasks.
+
+
+\subsection{Replacing function}
+\label{sec:maheve_rep}
+
+%This function is essential in a volatile environment, as an efficient
+%replacement should reduce the overhead on the application execution
+%time due to the loss of computing steps and data.
+
+As shown in the previous section, during the initial mapping some
+computing nodes in each cluster have been preserved. When a node fails
+this function replace it by a free node of the same cluster. If none
+is available this function sorts again clusters, to take into
+consideration platform modifications, and replace the failed node by
+one available in the new sorted clusters list. This mechanism allows
+to keep tasks locality and a real time overview of the executing
+platform.
+
+
+\section{Experimentation}
+\label{sec:expe}
+
+\subsection{A typical AIAC application and the execution platform}
+\label{sec:cond}
+
+We used the ``Kernel CG'' application of the NAS Parallel Benchmarks
+(NPB) \cite{nas} to evaluate the performances of our new mapping
+algorithm. This benchmark is designed to be used on large
+architectures, as it stresses communications%over latency networks
+, by processing unstructured matrix vector multiplication with a
+Conjugate Gradient method. As this method cannot be executed with the
+asynchronous iteration model we have replaced it by another method
+called the multisplitting method, which supports the asynchronous
+iterative model. More details about this method can be found in
+\cite{book_raph}. The chosen problem used a matrix of size $5,000,000$
+with a low bandwidth, fixed to $35,000$. This bandwidth size
+generates, according to the problem size, between 8 and 20 neighbors
+per tasks. This application was executed on 64 nodes.
+
+
+The platform used for our tests, called Grid’5000\cite{g5k}, is a
+French nationwide experimental set of clusters which provides us with
+distributed clusters architectures (28 heterogeneous clusters spread
+over 9 sites). We used three distributed clusters architectures, each
+having a different heterogeneity degree. The first one was composed of
+four clusters spread over four sites, with a total of 106 computing
+nodes representing 424 computing cores with \mbox{$hd = 0.08$}; the
+second one was composed of four clusters spread over three sites, with
+a total of 110 computing nodes representing 440 computing cores with
+\mbox{$hd = 0.50$}; and finally the third one was composed of five
+clusters spread over four sites with 115 computing nodes representing
+620 computing cores with \mbox{$hd = 0.72$}.
+
+
+All computing nodes of these clusters have at least 4 computing cores
+(in the last used architecture, with \mbox{$hd = 0.72$}, two clusters
+are composed of 8 computing cores machines) with a minimum of 4GB of
+memory (in order to execute the application with a big problem
+size). All computing nodes can communicate with each other through an
+efficient network. Nevertheless, this latter is shared with many other
+users so high latencies appear during executions.
+
+
+\subsection{Experiments}
+\label{sec:experiments}
+
+During executions, we introduced two failures in computing nodes
+involved in the computation every 20 seconds to simulate a volatile
+environment. Unfortunately, we did not have the opportunity to realize
+experiments with more computing nodes over more sites with problems of
+larger sizes, but we plan to extend our experiments in the future.
+
+
+Here we present the results of the evaluation of the MAHEVE algorithm,
+compared with FT-AIAC-QM (for \textit{Fault Tolerant AIAC-QM}) and
+FT-FEC (for \textit{Fault Tolerant F-EC}) which are respectively the
+fault tolerant versions of the AIAC-QM and F-EC mapping algorithms
+presented in \cite{pdsec10}. Table \ref{tab:results} shows the
+execution times of each mapping algorithm compared to the default
+mapping strategy of the JaceP2P-V2 platform, with the corresponding
+gains on application execution time, given in brackets. It presents
+both the executions with faults (WF) and the fault free (FF)
+executions.
+
+\vspace{-0.25cm}
+
+\renewcommand{\arraystretch}{1.6}
+\begin{table}[h!]
+ \centering
+ \begin{tabular}{|c|c|c|c|c|c|c|c|c|}
+ \hline
+ \multirow{2}{*}{ ~$hd$~ }&\multicolumn{2}{c|}{ ~Default~ }&\multicolumn{2}{c|}{ ~FT-AIAC-QM~ }&\multicolumn{2}{c|}{ ~FT-FEC~ }&\multicolumn{2}{c|}{ ~MAHEVE~ }\\
+ \cline{2-9}
+
+ & ~FF~ & ~WF~ & ~FF~ & ~WF~ & ~FF~ & ~WF~ & ~FF~ & ~WF~ \\
+ \hline
+ ~$0.08$~ & ~80~ & ~229~ & ~63 (21\%)~ & ~178 (22\%)~ & ~61 (23\%)~ & ~154
+ (33\%)~ & ~60 (25\%)~ & ~113 (50\%)~ \\
+
+ ~$0.50$~ & ~67~ & ~242~ & ~61 (9\%)~ & ~118 (51\%)~ & ~63 (6\%)~ & ~133
+ (45\%)~ & ~54 (20\%)~ & ~85 (65\%)~ \\
+
+ ~$0.72$~ & ~67~ & ~192~ & ~59 (12\%)~ & ~99 (45\%)~ & ~65 (3\%)~ & ~121
+ (33\%)~ & ~52 (22\%)~ & ~86 (53\%)~\\
+
+ \hline
+ \end{tabular}
+ \vspace{0.15cm}
+ \caption{Application execution time in seconds and corresponding gains on various
+ platforms using different mapping algorithms, with fault free (FF) executions
+ and with 2 node failures each 20 seconds (WF) executions.}
+ \label{tab:results}
+ \vspace{-0.7cm}
+\end{table}
+
+
+First of all, we can note that all mapping algorithms provide an
+enhancement of the application performances by considerably reducing
+its execution time, especially for executions with node failures, with
+an average gain of about $45\%$ in general in comparison to the
+default policy. If we focus on executions with node failures (WF),
+FT-FEC is efficient on architectures with a low heterogeneity degree
+(\mbox{$hd = 0.08$}) by providing gains of about $33\%$, and gains are
+roughly the same on heterogeneous architectures (\mbox{$hd =
+ 0.72$}). FT-AIAC-QM is efficient on architectures with a high
+heterogeneity degree (\mbox{$hd = 0.72$}) by providing gains of about
+$45\%$, whereas it is not so efficient on homogeneous architectures
+(\mbox{$hd = 0.08$}) by providing gains of about $22\%$. We can note
+here that on an architecture with a heterogeneity degree of $0.50$
+FT-AIAC-QM is more efficient than FT-FEC by providing gains up to
+$50\%$. Here we point out that in fault free executions (FF), both
+algorithms also provide gains on their respective favorite
+architectures, though gains are less great than in executions with
+faults (WF).
+
+
+Now if we focus on the performances of our new solution MAHEVE, we can
+see that it is all the time better than other algorithms. As can be
+seen in \mbox{Table \ref{tab:results}}, in executions with faults
+(WF), it reduces the application's execution time by about $50\%$ on
+homogeneous architectures (here of $0.08$ heterogeneity degree) which
+is more than 25 point better than FT-FEC and near 30 points better
+than FT-AIAC-QM. On heterogeneous architectures (here of $0.72$
+heterogeneity degree) it also outperforms other mapping algorithms by
+reducing the application execution time by about $53\%$ which is
+almost 10 points better than FT-AIAC-QM and 20 points better than
+FT-FEC. On middle heterogeneity degree architectures (here of $0.50$
+heterogeneity degree), MAHEVE is once again better than its two
+comparative mapping algorithms by reducing the application execution
+time by about $53\%$. These good performances come from the fact that
+it is designed to be efficient on both architectures, homogeneous and
+heterogeneous. Moreover, as it integrates a fault tolerance
+\textit{security} in the initial mapping, it is more efficient when
+computing nodes fail. Here we can point out that this algorithm allows
+in general gains on application execution time of about $55\%$. In fault free executions (FF), it outperforms once again
+the two other algorithms.
+
+\vspace{-0.15cm}
+\section{Conclusion and future works}
+\label{sec:conclu}
+
+In this paper we have presented a new mapping algorithm, called
+MAHEVE, to address the AIAC mapping issue on heterogeneous and
+volatile environments. It aims at doing an efficient mapping of tasks
+on distributed clusters architectures by taking the best part of the
+two known approaches, application execution time optimization and
+edge-cuts minimization. Experiments, though using a single
+application, show that it is the most efficient mapping algorithm on
+all kinds of architectures, as it takes into account their
+heterogeneity degree and adapt its sort methods to it. We have shown
+that it is all the time better than the two other comparative mapping
+algorithms, FT-AIAC-QM and FT-FEC. This can be explained by the fact
+that it not only takes care about computing nodes and clusters, but
+also about the tasks' properties, what refines the mapping solution.
+
+
+In our future works we plan to enhance the MAHEVE algorithm
+performances by modifying the notation of clusters, since their
+locality has not yet been taken into consideration. This would favor
+tasks locality, which would reduce communications delays and provide a
+much better convergence rate. We also have to validate the algorithm
+performance with other AIAC applications.
+
+
+%% Acknolegdement
+
+\section*{Acknowledgement}
+\label{ack}
+
+Experiments presented in this paper were carried out using the
+Grid'5000 experimental testbed\cite{g5k}, being developed under the
+INRIA ALADDIN development action with support from CNRS, RENATER and
+several Universities as well as other funding bodies.
+
+%%%
+
+
+\bibliographystyle{unsrt}
+
+\bibliography{biblio}
+
+
+\end{document}
+
--- /dev/null
+% LLNCS DOCUMENT CLASS -- version 2.16 (15-Apr-2010)\r
+% Springer Verlag LaTeX2e support for Lecture Notes in Computer Science\r
+%\r
+%%\r
+%% \CharacterTable\r
+%% {Upper-case \A\B\C\D\E\F\G\H\I\J\K\L\M\N\O\P\Q\R\S\T\U\V\W\X\Y\Z\r
+%% Lower-case \a\b\c\d\e\f\g\h\i\j\k\l\m\n\o\p\q\r\s\t\u\v\w\x\y\z\r
+%% Digits \0\1\2\3\4\5\6\7\8\9\r
+%% Exclamation \! Double quote \" Hash (number) \#\r
+%% Dollar \$ Percent \% Ampersand \&\r
+%% Acute accent \' Left paren \( Right paren \)\r
+%% Asterisk \* Plus \+ Comma \,\r
+%% Minus \- Point \. Solidus \/\r
+%% Colon \: Semicolon \; Less than \<\r
+%% Equals \= Greater than \> Question mark \?\r
+%% Commercial at \@ Left bracket \[ Backslash \\\r
+%% Right bracket \] Circumflex \^ Underscore \_\r
+%% Grave accent \` Left brace \{ Vertical bar \|\r
+%% Right brace \} Tilde \~}\r
+%%\r
+\NeedsTeXFormat{LaTeX2e}[1995/12/01]\r
+\ProvidesClass{llncs}[2010/04/15 v2.16\r
+^^J LaTeX document class for Lecture Notes in Computer Science]\r
+% Options\r
+\let\if@envcntreset\iffalse\r
+\DeclareOption{envcountreset}{\let\if@envcntreset\iftrue}\r
+\DeclareOption{citeauthoryear}{\let\citeauthoryear=Y}\r
+\DeclareOption{oribibl}{\let\oribibl=Y}\r
+\let\if@custvec\iftrue\r
+\DeclareOption{orivec}{\let\if@custvec\iffalse}\r
+\let\if@envcntsame\iffalse\r
+\DeclareOption{envcountsame}{\let\if@envcntsame\iftrue}\r
+\let\if@envcntsect\iffalse\r
+\DeclareOption{envcountsect}{\let\if@envcntsect\iftrue}\r
+\let\if@runhead\iffalse\r
+\DeclareOption{runningheads}{\let\if@runhead\iftrue}\r
+\r
+\let\if@openbib\iffalse\r
+\DeclareOption{openbib}{\let\if@openbib\iftrue}\r
+\r
+% languages\r
+\let\switcht@@therlang\relax\r
+\def\ds@deutsch{\def\switcht@@therlang{\switcht@deutsch}}\r
+\def\ds@francais{\def\switcht@@therlang{\switcht@francais}}\r
+\r
+\DeclareOption*{\PassOptionsToClass{\CurrentOption}{article}}\r
+\r
+\ProcessOptions\r
+\r
+\LoadClass[twoside]{article}\r
+\RequirePackage{multicol} % needed for the list of participants, index\r
+\RequirePackage{aliascnt}\r
+\r
+\setlength{\textwidth}{12.2cm}\r
+\setlength{\textheight}{19.3cm}\r
+\renewcommand\@pnumwidth{2em}\r
+\renewcommand\@tocrmarg{3.5em}\r
+%\r
+\def\@dottedtocline#1#2#3#4#5{%\r
+ \ifnum #1>\c@tocdepth \else\r
+ \vskip \z@ \@plus.2\p@\r
+ {\leftskip #2\relax \rightskip \@tocrmarg \advance\rightskip by 0pt plus 2cm\r
+ \parfillskip -\rightskip \pretolerance=10000\r
+ \parindent #2\relax\@afterindenttrue\r
+ \interlinepenalty\@M\r
+ \leavevmode\r
+ \@tempdima #3\relax\r
+ \advance\leftskip \@tempdima \null\nobreak\hskip -\leftskip\r
+ {#4}\nobreak\r
+ \leaders\hbox{$\m@th\r
+ \mkern \@dotsep mu\hbox{.}\mkern \@dotsep\r
+ mu$}\hfill\r
+ \nobreak\r
+ \hb@xt@\@pnumwidth{\hfil\normalfont \normalcolor #5}%\r
+ \par}%\r
+ \fi}\r
+%\r
+\def\switcht@albion{%\r
+\def\abstractname{Abstract.}\r
+\def\ackname{Acknowledgement.}\r
+\def\andname{and}\r
+\def\lastandname{\unskip, and}\r
+\def\appendixname{Appendix}\r
+\def\chaptername{Chapter}\r
+\def\claimname{Claim}\r
+\def\conjecturename{Conjecture}\r
+\def\contentsname{Table of Contents}\r
+\def\corollaryname{Corollary}\r
+\def\definitionname{Definition}\r
+\def\examplename{Example}\r
+\def\exercisename{Exercise}\r
+\def\figurename{Fig.}\r
+\def\keywordname{{\bf Keywords:}}\r
+\def\indexname{Index}\r
+\def\lemmaname{Lemma}\r
+\def\contriblistname{List of Contributors}\r
+\def\listfigurename{List of Figures}\r
+\def\listtablename{List of Tables}\r
+\def\mailname{{\it Correspondence to\/}:}\r
+\def\noteaddname{Note added in proof}\r
+\def\notename{Note}\r
+\def\partname{Part}\r
+\def\problemname{Problem}\r
+\def\proofname{Proof}\r
+\def\propertyname{Property}\r
+\def\propositionname{Proposition}\r
+\def\questionname{Question}\r
+\def\remarkname{Remark}\r
+\def\seename{see}\r
+\def\solutionname{Solution}\r
+\def\subclassname{{\it Subject Classifications\/}:}\r
+\def\tablename{Table}\r
+\def\theoremname{Theorem}}\r
+\switcht@albion\r
+% Names of theorem like environments are already defined\r
+% but must be translated if another language is chosen\r
+%\r
+% French section\r
+\def\switcht@francais{%\typeout{On parle francais.}%\r
+ \def\abstractname{R\'esum\'e.}%\r
+ \def\ackname{Remerciements.}%\r
+ \def\andname{et}%\r
+ \def\lastandname{ et}%\r
+ \def\appendixname{Appendice}\r
+ \def\chaptername{Chapitre}%\r
+ \def\claimname{Pr\'etention}%\r
+ \def\conjecturename{Hypoth\`ese}%\r
+ \def\contentsname{Table des mati\`eres}%\r
+ \def\corollaryname{Corollaire}%\r
+ \def\definitionname{D\'efinition}%\r
+ \def\examplename{Exemple}%\r
+ \def\exercisename{Exercice}%\r
+ \def\figurename{Fig.}%\r
+ \def\keywordname{{\bf Mots-cl\'e:}}\r
+ \def\indexname{Index}\r
+ \def\lemmaname{Lemme}%\r
+ \def\contriblistname{Liste des contributeurs}\r
+ \def\listfigurename{Liste des figures}%\r
+ \def\listtablename{Liste des tables}%\r
+ \def\mailname{{\it Correspondence to\/}:}\r
+ \def\noteaddname{Note ajout\'ee \`a l'\'epreuve}%\r
+ \def\notename{Remarque}%\r
+ \def\partname{Partie}%\r
+ \def\problemname{Probl\`eme}%\r
+ \def\proofname{Preuve}%\r
+ \def\propertyname{Caract\'eristique}%\r
+%\def\propositionname{Proposition}%\r
+ \def\questionname{Question}%\r
+ \def\remarkname{Remarque}%\r
+ \def\seename{voir}\r
+ \def\solutionname{Solution}%\r
+ \def\subclassname{{\it Subject Classifications\/}:}\r
+ \def\tablename{Tableau}%\r
+ \def\theoremname{Th\'eor\`eme}%\r
+}\r
+%\r
+% German section\r
+\def\switcht@deutsch{%\typeout{Man spricht deutsch.}%\r
+ \def\abstractname{Zusammenfassung.}%\r
+ \def\ackname{Danksagung.}%\r
+ \def\andname{und}%\r
+ \def\lastandname{ und}%\r
+ \def\appendixname{Anhang}%\r
+ \def\chaptername{Kapitel}%\r
+ \def\claimname{Behauptung}%\r
+ \def\conjecturename{Hypothese}%\r
+ \def\contentsname{Inhaltsverzeichnis}%\r
+ \def\corollaryname{Korollar}%\r
+%\def\definitionname{Definition}%\r
+ \def\examplename{Beispiel}%\r
+ \def\exercisename{\"Ubung}%\r
+ \def\figurename{Abb.}%\r
+ \def\keywordname{{\bf Schl\"usselw\"orter:}}\r
+ \def\indexname{Index}\r
+%\def\lemmaname{Lemma}%\r
+ \def\contriblistname{Mitarbeiter}\r
+ \def\listfigurename{Abbildungsverzeichnis}%\r
+ \def\listtablename{Tabellenverzeichnis}%\r
+ \def\mailname{{\it Correspondence to\/}:}\r
+ \def\noteaddname{Nachtrag}%\r
+ \def\notename{Anmerkung}%\r
+ \def\partname{Teil}%\r
+%\def\problemname{Problem}%\r
+ \def\proofname{Beweis}%\r
+ \def\propertyname{Eigenschaft}%\r
+%\def\propositionname{Proposition}%\r
+ \def\questionname{Frage}%\r
+ \def\remarkname{Anmerkung}%\r
+ \def\seename{siehe}\r
+ \def\solutionname{L\"osung}%\r
+ \def\subclassname{{\it Subject Classifications\/}:}\r
+ \def\tablename{Tabelle}%\r
+%\def\theoremname{Theorem}%\r
+}\r
+\r
+% Ragged bottom for the actual page\r
+\def\thisbottomragged{\def\@textbottom{\vskip\z@ plus.0001fil\r
+\global\let\@textbottom\relax}}\r
+\r
+\renewcommand\small{%\r
+ \@setfontsize\small\@ixpt{11}%\r
+ \abovedisplayskip 8.5\p@ \@plus3\p@ \@minus4\p@\r
+ \abovedisplayshortskip \z@ \@plus2\p@\r
+ \belowdisplayshortskip 4\p@ \@plus2\p@ \@minus2\p@\r
+ \def\@listi{\leftmargin\leftmargini\r
+ \parsep 0\p@ \@plus1\p@ \@minus\p@\r
+ \topsep 8\p@ \@plus2\p@ \@minus4\p@\r
+ \itemsep0\p@}%\r
+ \belowdisplayskip \abovedisplayskip\r
+}\r
+\r
+\frenchspacing\r
+\widowpenalty=10000\r
+\clubpenalty=10000\r
+\r
+\setlength\oddsidemargin {63\p@}\r
+\setlength\evensidemargin {63\p@}\r
+\setlength\marginparwidth {90\p@}\r
+\r
+\setlength\headsep {16\p@}\r
+\r
+\setlength\footnotesep{7.7\p@}\r
+\setlength\textfloatsep{8mm\@plus 2\p@ \@minus 4\p@}\r
+\setlength\intextsep {8mm\@plus 2\p@ \@minus 2\p@}\r
+\r
+\setcounter{secnumdepth}{2}\r
+\r
+\newcounter {chapter}\r
+\renewcommand\thechapter {\@arabic\c@chapter}\r
+\r
+\newif\if@mainmatter \@mainmattertrue\r
+\newcommand\frontmatter{\cleardoublepage\r
+ \@mainmatterfalse\pagenumbering{Roman}}\r
+\newcommand\mainmatter{\cleardoublepage\r
+ \@mainmattertrue\pagenumbering{arabic}}\r
+\newcommand\backmatter{\if@openright\cleardoublepage\else\clearpage\fi\r
+ \@mainmatterfalse}\r
+\r
+\renewcommand\part{\cleardoublepage\r
+ \thispagestyle{empty}%\r
+ \if@twocolumn\r
+ \onecolumn\r
+ \@tempswatrue\r
+ \else\r
+ \@tempswafalse\r
+ \fi\r
+ \null\vfil\r
+ \secdef\@part\@spart}\r
+\r
+\def\@part[#1]#2{%\r
+ \ifnum \c@secnumdepth >-2\relax\r
+ \refstepcounter{part}%\r
+ \addcontentsline{toc}{part}{\thepart\hspace{1em}#1}%\r
+ \else\r
+ \addcontentsline{toc}{part}{#1}%\r
+ \fi\r
+ \markboth{}{}%\r
+ {\centering\r
+ \interlinepenalty \@M\r
+ \normalfont\r
+ \ifnum \c@secnumdepth >-2\relax\r
+ \huge\bfseries \partname~\thepart\r
+ \par\r
+ \vskip 20\p@\r
+ \fi\r
+ \Huge \bfseries #2\par}%\r
+ \@endpart}\r
+\def\@spart#1{%\r
+ {\centering\r
+ \interlinepenalty \@M\r
+ \normalfont\r
+ \Huge \bfseries #1\par}%\r
+ \@endpart}\r
+\def\@endpart{\vfil\newpage\r
+ \if@twoside\r
+ \null\r
+ \thispagestyle{empty}%\r
+ \newpage\r
+ \fi\r
+ \if@tempswa\r
+ \twocolumn\r
+ \fi}\r
+\r
+\newcommand\chapter{\clearpage\r
+ \thispagestyle{empty}%\r
+ \global\@topnum\z@\r
+ \@afterindentfalse\r
+ \secdef\@chapter\@schapter}\r
+\def\@chapter[#1]#2{\ifnum \c@secnumdepth >\m@ne\r
+ \if@mainmatter\r
+ \refstepcounter{chapter}%\r
+ \typeout{\@chapapp\space\thechapter.}%\r
+ \addcontentsline{toc}{chapter}%\r
+ {\protect\numberline{\thechapter}#1}%\r
+ \else\r
+ \addcontentsline{toc}{chapter}{#1}%\r
+ \fi\r
+ \else\r
+ \addcontentsline{toc}{chapter}{#1}%\r
+ \fi\r
+ \chaptermark{#1}%\r
+ \addtocontents{lof}{\protect\addvspace{10\p@}}%\r
+ \addtocontents{lot}{\protect\addvspace{10\p@}}%\r
+ \if@twocolumn\r
+ \@topnewpage[\@makechapterhead{#2}]%\r
+ \else\r
+ \@makechapterhead{#2}%\r
+ \@afterheading\r
+ \fi}\r
+\def\@makechapterhead#1{%\r
+% \vspace*{50\p@}%\r
+ {\centering\r
+ \ifnum \c@secnumdepth >\m@ne\r
+ \if@mainmatter\r
+ \large\bfseries \@chapapp{} \thechapter\r
+ \par\nobreak\r
+ \vskip 20\p@\r
+ \fi\r
+ \fi\r
+ \interlinepenalty\@M\r
+ \Large \bfseries #1\par\nobreak\r
+ \vskip 40\p@\r
+ }}\r
+\def\@schapter#1{\if@twocolumn\r
+ \@topnewpage[\@makeschapterhead{#1}]%\r
+ \else\r
+ \@makeschapterhead{#1}%\r
+ \@afterheading\r
+ \fi}\r
+\def\@makeschapterhead#1{%\r
+% \vspace*{50\p@}%\r
+ {\centering\r
+ \normalfont\r
+ \interlinepenalty\@M\r
+ \Large \bfseries #1\par\nobreak\r
+ \vskip 40\p@\r
+ }}\r
+\r
+\renewcommand\section{\@startsection{section}{1}{\z@}%\r
+ {-18\p@ \@plus -4\p@ \@minus -4\p@}%\r
+ {12\p@ \@plus 4\p@ \@minus 4\p@}%\r
+ {\normalfont\large\bfseries\boldmath\r
+ \rightskip=\z@ \@plus 8em\pretolerance=10000 }}\r
+\renewcommand\subsection{\@startsection{subsection}{2}{\z@}%\r
+ {-18\p@ \@plus -4\p@ \@minus -4\p@}%\r
+ {8\p@ \@plus 4\p@ \@minus 4\p@}%\r
+ {\normalfont\normalsize\bfseries\boldmath\r
+ \rightskip=\z@ \@plus 8em\pretolerance=10000 }}\r
+\renewcommand\subsubsection{\@startsection{subsubsection}{3}{\z@}%\r
+ {-18\p@ \@plus -4\p@ \@minus -4\p@}%\r
+ {-0.5em \@plus -0.22em \@minus -0.1em}%\r
+ {\normalfont\normalsize\bfseries\boldmath}}\r
+\renewcommand\paragraph{\@startsection{paragraph}{4}{\z@}%\r
+ {-12\p@ \@plus -4\p@ \@minus -4\p@}%\r
+ {-0.5em \@plus -0.22em \@minus -0.1em}%\r
+ {\normalfont\normalsize\itshape}}\r
+\renewcommand\subparagraph[1]{\typeout{LLNCS warning: You should not use\r
+ \string\subparagraph\space with this class}\vskip0.5cm\r
+You should not use \verb|\subparagraph| with this class.\vskip0.5cm}\r
+\r
+\DeclareMathSymbol{\Gamma}{\mathalpha}{letters}{"00}\r
+\DeclareMathSymbol{\Delta}{\mathalpha}{letters}{"01}\r
+\DeclareMathSymbol{\Theta}{\mathalpha}{letters}{"02}\r
+\DeclareMathSymbol{\Lambda}{\mathalpha}{letters}{"03}\r
+\DeclareMathSymbol{\Xi}{\mathalpha}{letters}{"04}\r
+\DeclareMathSymbol{\Pi}{\mathalpha}{letters}{"05}\r
+\DeclareMathSymbol{\Sigma}{\mathalpha}{letters}{"06}\r
+\DeclareMathSymbol{\Upsilon}{\mathalpha}{letters}{"07}\r
+\DeclareMathSymbol{\Phi}{\mathalpha}{letters}{"08}\r
+\DeclareMathSymbol{\Psi}{\mathalpha}{letters}{"09}\r
+\DeclareMathSymbol{\Omega}{\mathalpha}{letters}{"0A}\r
+\r
+\let\footnotesize\small\r
+\r
+\if@custvec\r
+\def\vec#1{\mathchoice{\mbox{\boldmath$\displaystyle#1$}}\r
+{\mbox{\boldmath$\textstyle#1$}}\r
+{\mbox{\boldmath$\scriptstyle#1$}}\r
+{\mbox{\boldmath$\scriptscriptstyle#1$}}}\r
+\fi\r
+\r
+\def\squareforqed{\hbox{\rlap{$\sqcap$}$\sqcup$}}\r
+\def\qed{\ifmmode\squareforqed\else{\unskip\nobreak\hfil\r
+\penalty50\hskip1em\null\nobreak\hfil\squareforqed\r
+\parfillskip=0pt\finalhyphendemerits=0\endgraf}\fi}\r
+\r
+\def\getsto{\mathrel{\mathchoice {\vcenter{\offinterlineskip\r
+\halign{\hfil\r
+$\displaystyle##$\hfil\cr\gets\cr\to\cr}}}\r
+{\vcenter{\offinterlineskip\halign{\hfil$\textstyle##$\hfil\cr\gets\r
+\cr\to\cr}}}\r
+{\vcenter{\offinterlineskip\halign{\hfil$\scriptstyle##$\hfil\cr\gets\r
+\cr\to\cr}}}\r
+{\vcenter{\offinterlineskip\halign{\hfil$\scriptscriptstyle##$\hfil\cr\r
+\gets\cr\to\cr}}}}}\r
+\def\lid{\mathrel{\mathchoice {\vcenter{\offinterlineskip\halign{\hfil\r
+$\displaystyle##$\hfil\cr<\cr\noalign{\vskip1.2pt}=\cr}}}\r
+{\vcenter{\offinterlineskip\halign{\hfil$\textstyle##$\hfil\cr<\cr\r
+\noalign{\vskip1.2pt}=\cr}}}\r
+{\vcenter{\offinterlineskip\halign{\hfil$\scriptstyle##$\hfil\cr<\cr\r
+\noalign{\vskip1pt}=\cr}}}\r
+{\vcenter{\offinterlineskip\halign{\hfil$\scriptscriptstyle##$\hfil\cr\r
+<\cr\r
+\noalign{\vskip0.9pt}=\cr}}}}}\r
+\def\gid{\mathrel{\mathchoice {\vcenter{\offinterlineskip\halign{\hfil\r
+$\displaystyle##$\hfil\cr>\cr\noalign{\vskip1.2pt}=\cr}}}\r
+{\vcenter{\offinterlineskip\halign{\hfil$\textstyle##$\hfil\cr>\cr\r
+\noalign{\vskip1.2pt}=\cr}}}\r
+{\vcenter{\offinterlineskip\halign{\hfil$\scriptstyle##$\hfil\cr>\cr\r
+\noalign{\vskip1pt}=\cr}}}\r
+{\vcenter{\offinterlineskip\halign{\hfil$\scriptscriptstyle##$\hfil\cr\r
+>\cr\r
+\noalign{\vskip0.9pt}=\cr}}}}}\r
+\def\grole{\mathrel{\mathchoice {\vcenter{\offinterlineskip\r
+\halign{\hfil\r
+$\displaystyle##$\hfil\cr>\cr\noalign{\vskip-1pt}<\cr}}}\r
+{\vcenter{\offinterlineskip\halign{\hfil$\textstyle##$\hfil\cr\r
+>\cr\noalign{\vskip-1pt}<\cr}}}\r
+{\vcenter{\offinterlineskip\halign{\hfil$\scriptstyle##$\hfil\cr\r
+>\cr\noalign{\vskip-0.8pt}<\cr}}}\r
+{\vcenter{\offinterlineskip\halign{\hfil$\scriptscriptstyle##$\hfil\cr\r
+>\cr\noalign{\vskip-0.3pt}<\cr}}}}}\r
+\def\bbbr{{\rm I\!R}} %reelle Zahlen\r
+\def\bbbm{{\rm I\!M}}\r
+\def\bbbn{{\rm I\!N}} %natuerliche Zahlen\r
+\def\bbbf{{\rm I\!F}}\r
+\def\bbbh{{\rm I\!H}}\r
+\def\bbbk{{\rm I\!K}}\r
+\def\bbbp{{\rm I\!P}}\r
+\def\bbbone{{\mathchoice {\rm 1\mskip-4mu l} {\rm 1\mskip-4mu l}\r
+{\rm 1\mskip-4.5mu l} {\rm 1\mskip-5mu l}}}\r
+\def\bbbc{{\mathchoice {\setbox0=\hbox{$\displaystyle\rm C$}\hbox{\hbox\r
+to0pt{\kern0.4\wd0\vrule height0.9\ht0\hss}\box0}}\r
+{\setbox0=\hbox{$\textstyle\rm C$}\hbox{\hbox\r
+to0pt{\kern0.4\wd0\vrule height0.9\ht0\hss}\box0}}\r
+{\setbox0=\hbox{$\scriptstyle\rm C$}\hbox{\hbox\r
+to0pt{\kern0.4\wd0\vrule height0.9\ht0\hss}\box0}}\r
+{\setbox0=\hbox{$\scriptscriptstyle\rm C$}\hbox{\hbox\r
+to0pt{\kern0.4\wd0\vrule height0.9\ht0\hss}\box0}}}}\r
+\def\bbbq{{\mathchoice {\setbox0=\hbox{$\displaystyle\rm\r
+Q$}\hbox{\raise\r
+0.15\ht0\hbox to0pt{\kern0.4\wd0\vrule height0.8\ht0\hss}\box0}}\r
+{\setbox0=\hbox{$\textstyle\rm Q$}\hbox{\raise\r
+0.15\ht0\hbox to0pt{\kern0.4\wd0\vrule height0.8\ht0\hss}\box0}}\r
+{\setbox0=\hbox{$\scriptstyle\rm Q$}\hbox{\raise\r
+0.15\ht0\hbox to0pt{\kern0.4\wd0\vrule height0.7\ht0\hss}\box0}}\r
+{\setbox0=\hbox{$\scriptscriptstyle\rm Q$}\hbox{\raise\r
+0.15\ht0\hbox to0pt{\kern0.4\wd0\vrule height0.7\ht0\hss}\box0}}}}\r
+\def\bbbt{{\mathchoice {\setbox0=\hbox{$\displaystyle\rm\r
+T$}\hbox{\hbox to0pt{\kern0.3\wd0\vrule height0.9\ht0\hss}\box0}}\r
+{\setbox0=\hbox{$\textstyle\rm T$}\hbox{\hbox\r
+to0pt{\kern0.3\wd0\vrule height0.9\ht0\hss}\box0}}\r
+{\setbox0=\hbox{$\scriptstyle\rm T$}\hbox{\hbox\r
+to0pt{\kern0.3\wd0\vrule height0.9\ht0\hss}\box0}}\r
+{\setbox0=\hbox{$\scriptscriptstyle\rm T$}\hbox{\hbox\r
+to0pt{\kern0.3\wd0\vrule height0.9\ht0\hss}\box0}}}}\r
+\def\bbbs{{\mathchoice\r
+{\setbox0=\hbox{$\displaystyle \rm S$}\hbox{\raise0.5\ht0\hbox\r
+to0pt{\kern0.35\wd0\vrule height0.45\ht0\hss}\hbox\r
+to0pt{\kern0.55\wd0\vrule height0.5\ht0\hss}\box0}}\r
+{\setbox0=\hbox{$\textstyle \rm S$}\hbox{\raise0.5\ht0\hbox\r
+to0pt{\kern0.35\wd0\vrule height0.45\ht0\hss}\hbox\r
+to0pt{\kern0.55\wd0\vrule height0.5\ht0\hss}\box0}}\r
+{\setbox0=\hbox{$\scriptstyle \rm S$}\hbox{\raise0.5\ht0\hbox\r
+to0pt{\kern0.35\wd0\vrule height0.45\ht0\hss}\raise0.05\ht0\hbox\r
+to0pt{\kern0.5\wd0\vrule height0.45\ht0\hss}\box0}}\r
+{\setbox0=\hbox{$\scriptscriptstyle\rm S$}\hbox{\raise0.5\ht0\hbox\r
+to0pt{\kern0.4\wd0\vrule height0.45\ht0\hss}\raise0.05\ht0\hbox\r
+to0pt{\kern0.55\wd0\vrule height0.45\ht0\hss}\box0}}}}\r
+\def\bbbz{{\mathchoice {\hbox{$\mathsf\textstyle Z\kern-0.4em Z$}}\r
+{\hbox{$\mathsf\textstyle Z\kern-0.4em Z$}}\r
+{\hbox{$\mathsf\scriptstyle Z\kern-0.3em Z$}}\r
+{\hbox{$\mathsf\scriptscriptstyle Z\kern-0.2em Z$}}}}\r
+\r
+\let\ts\,\r
+\r
+\setlength\leftmargini {17\p@}\r
+\setlength\leftmargin {\leftmargini}\r
+\setlength\leftmarginii {\leftmargini}\r
+\setlength\leftmarginiii {\leftmargini}\r
+\setlength\leftmarginiv {\leftmargini}\r
+\setlength \labelsep {.5em}\r
+\setlength \labelwidth{\leftmargini}\r
+\addtolength\labelwidth{-\labelsep}\r
+\r
+\def\@listI{\leftmargin\leftmargini\r
+ \parsep 0\p@ \@plus1\p@ \@minus\p@\r
+ \topsep 8\p@ \@plus2\p@ \@minus4\p@\r
+ \itemsep0\p@}\r
+\let\@listi\@listI\r
+\@listi\r
+\def\@listii {\leftmargin\leftmarginii\r
+ \labelwidth\leftmarginii\r
+ \advance\labelwidth-\labelsep\r
+ \topsep 0\p@ \@plus2\p@ \@minus\p@}\r
+\def\@listiii{\leftmargin\leftmarginiii\r
+ \labelwidth\leftmarginiii\r
+ \advance\labelwidth-\labelsep\r
+ \topsep 0\p@ \@plus\p@\@minus\p@\r
+ \parsep \z@\r
+ \partopsep \p@ \@plus\z@ \@minus\p@}\r
+\r
+\renewcommand\labelitemi{\normalfont\bfseries --}\r
+\renewcommand\labelitemii{$\m@th\bullet$}\r
+\r
+\setlength\arraycolsep{1.4\p@}\r
+\setlength\tabcolsep{1.4\p@}\r
+\r
+\def\tableofcontents{\chapter*{\contentsname\@mkboth{{\contentsname}}%\r
+ {{\contentsname}}}\r
+ \def\authcount##1{\setcounter{auco}{##1}\setcounter{@auth}{1}}\r
+ \def\lastand{\ifnum\value{auco}=2\relax\r
+ \unskip{} \andname\\r
+ \else\r
+ \unskip \lastandname\\r
+ \fi}%\r
+ \def\and{\stepcounter{@auth}\relax\r
+ \ifnum\value{@auth}=\value{auco}%\r
+ \lastand\r
+ \else\r
+ \unskip,\r
+ \fi}%\r
+ \@starttoc{toc}\if@restonecol\twocolumn\fi}\r
+\r
+\def\l@part#1#2{\addpenalty{\@secpenalty}%\r
+ \addvspace{2em plus\p@}% % space above part line\r
+ \begingroup\r
+ \parindent \z@\r
+ \rightskip \z@ plus 5em\r
+ \hrule\vskip5pt\r
+ \large % same size as for a contribution heading\r
+ \bfseries\boldmath % set line in boldface\r
+ \leavevmode % TeX command to enter horizontal mode.\r
+ #1\par\r
+ \vskip5pt\r
+ \hrule\r
+ \vskip1pt\r
+ \nobreak % Never break after part entry\r
+ \endgroup}\r
+\r
+\def\@dotsep{2}\r
+\r
+\let\phantomsection=\relax\r
+\r
+\def\hyperhrefextend{\ifx\hyper@anchor\@undefined\else\r
+{}\fi}\r
+\r
+\def\addnumcontentsmark#1#2#3{%\r
+\addtocontents{#1}{\protect\contentsline{#2}{\protect\numberline\r
+ {\thechapter}#3}{\thepage}\hyperhrefextend}}%\r
+\def\addcontentsmark#1#2#3{%\r
+\addtocontents{#1}{\protect\contentsline{#2}{#3}{\thepage}\hyperhrefextend}}%\r
+\def\addcontentsmarkwop#1#2#3{%\r
+\addtocontents{#1}{\protect\contentsline{#2}{#3}{0}\hyperhrefextend}}%\r
+\r
+\def\@adcmk[#1]{\ifcase #1 \or\r
+\def\@gtempa{\addnumcontentsmark}%\r
+ \or \def\@gtempa{\addcontentsmark}%\r
+ \or \def\@gtempa{\addcontentsmarkwop}%\r
+ \fi\@gtempa{toc}{chapter}%\r
+}\r
+\def\addtocmark{%\r
+\phantomsection\r
+\@ifnextchar[{\@adcmk}{\@adcmk[3]}%\r
+}\r
+\r
+\def\l@chapter#1#2{\addpenalty{-\@highpenalty}\r
+ \vskip 1.0em plus 1pt \@tempdima 1.5em \begingroup\r
+ \parindent \z@ \rightskip \@tocrmarg\r
+ \advance\rightskip by 0pt plus 2cm\r
+ \parfillskip -\rightskip \pretolerance=10000\r
+ \leavevmode \advance\leftskip\@tempdima \hskip -\leftskip\r
+ {\large\bfseries\boldmath#1}\ifx0#2\hfil\null\r
+ \else\r
+ \nobreak\r
+ \leaders\hbox{$\m@th \mkern \@dotsep mu.\mkern\r
+ \@dotsep mu$}\hfill\r
+ \nobreak\hbox to\@pnumwidth{\hss #2}%\r
+ \fi\par\r
+ \penalty\@highpenalty \endgroup}\r
+\r
+\def\l@title#1#2{\addpenalty{-\@highpenalty}\r
+ \addvspace{8pt plus 1pt}\r
+ \@tempdima \z@\r
+ \begingroup\r
+ \parindent \z@ \rightskip \@tocrmarg\r
+ \advance\rightskip by 0pt plus 2cm\r
+ \parfillskip -\rightskip \pretolerance=10000\r
+ \leavevmode \advance\leftskip\@tempdima \hskip -\leftskip\r
+ #1\nobreak\r
+ \leaders\hbox{$\m@th \mkern \@dotsep mu.\mkern\r
+ \@dotsep mu$}\hfill\r
+ \nobreak\hbox to\@pnumwidth{\hss #2}\par\r
+ \penalty\@highpenalty \endgroup}\r
+\r
+\def\l@author#1#2{\addpenalty{\@highpenalty}\r
+ \@tempdima=15\p@ %\z@\r
+ \begingroup\r
+ \parindent \z@ \rightskip \@tocrmarg\r
+ \advance\rightskip by 0pt plus 2cm\r
+ \pretolerance=10000\r
+ \leavevmode \advance\leftskip\@tempdima %\hskip -\leftskip\r
+ \textit{#1}\par\r
+ \penalty\@highpenalty \endgroup}\r
+\r
+\setcounter{tocdepth}{0}\r
+\newdimen\tocchpnum\r
+\newdimen\tocsecnum\r
+\newdimen\tocsectotal\r
+\newdimen\tocsubsecnum\r
+\newdimen\tocsubsectotal\r
+\newdimen\tocsubsubsecnum\r
+\newdimen\tocsubsubsectotal\r
+\newdimen\tocparanum\r
+\newdimen\tocparatotal\r
+\newdimen\tocsubparanum\r
+\tocchpnum=\z@ % no chapter numbers\r
+\tocsecnum=15\p@ % section 88. plus 2.222pt\r
+\tocsubsecnum=23\p@ % subsection 88.8 plus 2.222pt\r
+\tocsubsubsecnum=27\p@ % subsubsection 88.8.8 plus 1.444pt\r
+\tocparanum=35\p@ % paragraph 88.8.8.8 plus 1.666pt\r
+\tocsubparanum=43\p@ % subparagraph 88.8.8.8.8 plus 1.888pt\r
+\def\calctocindent{%\r
+\tocsectotal=\tocchpnum\r
+\advance\tocsectotal by\tocsecnum\r
+\tocsubsectotal=\tocsectotal\r
+\advance\tocsubsectotal by\tocsubsecnum\r
+\tocsubsubsectotal=\tocsubsectotal\r
+\advance\tocsubsubsectotal by\tocsubsubsecnum\r
+\tocparatotal=\tocsubsubsectotal\r
+\advance\tocparatotal by\tocparanum}\r
+\calctocindent\r
+\r
+\def\l@section{\@dottedtocline{1}{\tocchpnum}{\tocsecnum}}\r
+\def\l@subsection{\@dottedtocline{2}{\tocsectotal}{\tocsubsecnum}}\r
+\def\l@subsubsection{\@dottedtocline{3}{\tocsubsectotal}{\tocsubsubsecnum}}\r
+\def\l@paragraph{\@dottedtocline{4}{\tocsubsubsectotal}{\tocparanum}}\r
+\def\l@subparagraph{\@dottedtocline{5}{\tocparatotal}{\tocsubparanum}}\r
+\r
+\def\listoffigures{\@restonecolfalse\if@twocolumn\@restonecoltrue\onecolumn\r
+ \fi\section*{\listfigurename\@mkboth{{\listfigurename}}{{\listfigurename}}}\r
+ \@starttoc{lof}\if@restonecol\twocolumn\fi}\r
+\def\l@figure{\@dottedtocline{1}{0em}{1.5em}}\r
+\r
+\def\listoftables{\@restonecolfalse\if@twocolumn\@restonecoltrue\onecolumn\r
+ \fi\section*{\listtablename\@mkboth{{\listtablename}}{{\listtablename}}}\r
+ \@starttoc{lot}\if@restonecol\twocolumn\fi}\r
+\let\l@table\l@figure\r
+\r
+\renewcommand\listoffigures{%\r
+ \section*{\listfigurename\r
+ \@mkboth{\listfigurename}{\listfigurename}}%\r
+ \@starttoc{lof}%\r
+ }\r
+\r
+\renewcommand\listoftables{%\r
+ \section*{\listtablename\r
+ \@mkboth{\listtablename}{\listtablename}}%\r
+ \@starttoc{lot}%\r
+ }\r
+\r
+\ifx\oribibl\undefined\r
+\ifx\citeauthoryear\undefined\r
+\renewenvironment{thebibliography}[1]\r
+ {\section*{\refname}\r
+ \def\@biblabel##1{##1.}\r
+ \small\r
+ \list{\@biblabel{\@arabic\c@enumiv}}%\r
+ {\settowidth\labelwidth{\@biblabel{#1}}%\r
+ \leftmargin\labelwidth\r
+ \advance\leftmargin\labelsep\r
+ \if@openbib\r
+ \advance\leftmargin\bibindent\r
+ \itemindent -\bibindent\r
+ \listparindent \itemindent\r
+ \parsep \z@\r
+ \fi\r
+ \usecounter{enumiv}%\r
+ \let\p@enumiv\@empty\r
+ \renewcommand\theenumiv{\@arabic\c@enumiv}}%\r
+ \if@openbib\r
+ \renewcommand\newblock{\par}%\r
+ \else\r
+ \renewcommand\newblock{\hskip .11em \@plus.33em \@minus.07em}%\r
+ \fi\r
+ \sloppy\clubpenalty4000\widowpenalty4000%\r
+ \sfcode`\.=\@m}\r
+ {\def\@noitemerr\r
+ {\@latex@warning{Empty `thebibliography' environment}}%\r
+ \endlist}\r
+\def\@lbibitem[#1]#2{\item[{[#1]}\hfill]\if@filesw\r
+ {\let\protect\noexpand\immediate\r
+ \write\@auxout{\string\bibcite{#2}{#1}}}\fi\ignorespaces}\r
+\newcount\@tempcntc\r
+\def\@citex[#1]#2{\if@filesw\immediate\write\@auxout{\string\citation{#2}}\fi\r
+ \@tempcnta\z@\@tempcntb\m@ne\def\@citea{}\@cite{\@for\@citeb:=#2\do\r
+ {\@ifundefined\r
+ {b@\@citeb}{\@citeo\@tempcntb\m@ne\@citea\def\@citea{,}{\bfseries\r
+ ?}\@warning\r
+ {Citation `\@citeb' on page \thepage \space undefined}}%\r
+ {\setbox\z@\hbox{\global\@tempcntc0\csname b@\@citeb\endcsname\relax}%\r
+ \ifnum\@tempcntc=\z@ \@citeo\@tempcntb\m@ne\r
+ \@citea\def\@citea{,}\hbox{\csname b@\@citeb\endcsname}%\r
+ \else\r
+ \advance\@tempcntb\@ne\r
+ \ifnum\@tempcntb=\@tempcntc\r
+ \else\advance\@tempcntb\m@ne\@citeo\r
+ \@tempcnta\@tempcntc\@tempcntb\@tempcntc\fi\fi}}\@citeo}{#1}}\r
+\def\@citeo{\ifnum\@tempcnta>\@tempcntb\else\r
+ \@citea\def\@citea{,\,\hskip\z@skip}%\r
+ \ifnum\@tempcnta=\@tempcntb\the\@tempcnta\else\r
+ {\advance\@tempcnta\@ne\ifnum\@tempcnta=\@tempcntb \else\r
+ \def\@citea{--}\fi\r
+ \advance\@tempcnta\m@ne\the\@tempcnta\@citea\the\@tempcntb}\fi\fi}\r
+\else\r
+\renewenvironment{thebibliography}[1]\r
+ {\section*{\refname}\r
+ \small\r
+ \list{}%\r
+ {\settowidth\labelwidth{}%\r
+ \leftmargin\parindent\r
+ \itemindent=-\parindent\r
+ \labelsep=\z@\r
+ \if@openbib\r
+ \advance\leftmargin\bibindent\r
+ \itemindent -\bibindent\r
+ \listparindent \itemindent\r
+ \parsep \z@\r
+ \fi\r
+ \usecounter{enumiv}%\r
+ \let\p@enumiv\@empty\r
+ \renewcommand\theenumiv{}}%\r
+ \if@openbib\r
+ \renewcommand\newblock{\par}%\r
+ \else\r
+ \renewcommand\newblock{\hskip .11em \@plus.33em \@minus.07em}%\r
+ \fi\r
+ \sloppy\clubpenalty4000\widowpenalty4000%\r
+ \sfcode`\.=\@m}\r
+ {\def\@noitemerr\r
+ {\@latex@warning{Empty `thebibliography' environment}}%\r
+ \endlist}\r
+ \def\@cite#1{#1}%\r
+ \def\@lbibitem[#1]#2{\item[]\if@filesw\r
+ {\def\protect##1{\string ##1\space}\immediate\r
+ \write\@auxout{\string\bibcite{#2}{#1}}}\fi\ignorespaces}\r
+ \fi\r
+\else\r
+\@cons\@openbib@code{\noexpand\small}\r
+\fi\r
+\r
+\def\idxquad{\hskip 10\p@}% space that divides entry from number\r
+\r
+\def\@idxitem{\par\hangindent 10\p@}\r
+\r
+\def\subitem{\par\setbox0=\hbox{--\enspace}% second order\r
+ \noindent\hangindent\wd0\box0}% index entry\r
+\r
+\def\subsubitem{\par\setbox0=\hbox{--\,--\enspace}% third\r
+ \noindent\hangindent\wd0\box0}% order index entry\r
+\r
+\def\indexspace{\par \vskip 10\p@ plus5\p@ minus3\p@\relax}\r
+\r
+\renewenvironment{theindex}\r
+ {\@mkboth{\indexname}{\indexname}%\r
+ \thispagestyle{empty}\parindent\z@\r
+ \parskip\z@ \@plus .3\p@\relax\r
+ \let\item\par\r
+ \def\,{\relax\ifmmode\mskip\thinmuskip\r
+ \else\hskip0.2em\ignorespaces\fi}%\r
+ \normalfont\small\r
+ \begin{multicols}{2}[\@makeschapterhead{\indexname}]%\r
+ }\r
+ {\end{multicols}}\r
+\r
+\renewcommand\footnoterule{%\r
+ \kern-3\p@\r
+ \hrule\@width 2truecm\r
+ \kern2.6\p@}\r
+ \newdimen\fnindent\r
+ \fnindent1em\r
+\long\def\@makefntext#1{%\r
+ \parindent \fnindent%\r
+ \leftskip \fnindent%\r
+ \noindent\r
+ \llap{\hb@xt@1em{\hss\@makefnmark\ }}\ignorespaces#1}\r
+\r
+\long\def\@makecaption#1#2{%\r
+ \small\r
+ \vskip\abovecaptionskip\r
+ \sbox\@tempboxa{{\bfseries #1.} #2}%\r
+ \ifdim \wd\@tempboxa >\hsize\r
+ {\bfseries #1.} #2\par\r
+ \else\r
+ \global \@minipagefalse\r
+ \hb@xt@\hsize{\hfil\box\@tempboxa\hfil}%\r
+ \fi\r
+ \vskip\belowcaptionskip}\r
+\r
+\def\fps@figure{htbp}\r
+\def\fnum@figure{\figurename\thinspace\thefigure}\r
+\def \@floatboxreset {%\r
+ \reset@font\r
+ \small\r
+ \@setnobreak\r
+ \@setminipage\r
+}\r
+\def\fps@table{htbp}\r
+\def\fnum@table{\tablename~\thetable}\r
+\renewenvironment{table}\r
+ {\setlength\abovecaptionskip{0\p@}%\r
+ \setlength\belowcaptionskip{10\p@}%\r
+ \@float{table}}\r
+ {\end@float}\r
+\renewenvironment{table*}\r
+ {\setlength\abovecaptionskip{0\p@}%\r
+ \setlength\belowcaptionskip{10\p@}%\r
+ \@dblfloat{table}}\r
+ {\end@dblfloat}\r
+\r
+\long\def\@caption#1[#2]#3{\par\addcontentsline{\csname\r
+ ext@#1\endcsname}{#1}{\protect\numberline{\csname\r
+ the#1\endcsname}{\ignorespaces #2}}\begingroup\r
+ \@parboxrestore\r
+ \@makecaption{\csname fnum@#1\endcsname}{\ignorespaces #3}\par\r
+ \endgroup}\r
+\r
+% LaTeX does not provide a command to enter the authors institute\r
+% addresses. The \institute command is defined here.\r
+\r
+\newcounter{@inst}\r
+\newcounter{@auth}\r
+\newcounter{auco}\r
+\newdimen\instindent\r
+\newbox\authrun\r
+\newtoks\authorrunning\r
+\newtoks\tocauthor\r
+\newbox\titrun\r
+\newtoks\titlerunning\r
+\newtoks\toctitle\r
+\r
+\def\clearheadinfo{\gdef\@author{No Author Given}%\r
+ \gdef\@title{No Title Given}%\r
+ \gdef\@subtitle{}%\r
+ \gdef\@institute{No Institute Given}%\r
+ \gdef\@thanks{}%\r
+ \global\titlerunning={}\global\authorrunning={}%\r
+ \global\toctitle={}\global\tocauthor={}}\r
+\r
+\def\institute#1{\gdef\@institute{#1}}\r
+\r
+\def\institutename{\par\r
+ \begingroup\r
+ \parskip=\z@\r
+ \parindent=\z@\r
+ \setcounter{@inst}{1}%\r
+ \def\and{\par\stepcounter{@inst}%\r
+ \noindent$^{\the@inst}$\enspace\ignorespaces}%\r
+ \setbox0=\vbox{\def\thanks##1{}\@institute}%\r
+ \ifnum\c@@inst=1\relax\r
+ \gdef\fnnstart{0}%\r
+ \else\r
+ \xdef\fnnstart{\c@@inst}%\r
+ \setcounter{@inst}{1}%\r
+ \noindent$^{\the@inst}$\enspace\r
+ \fi\r
+ \ignorespaces\r
+ \@institute\par\r
+ \endgroup}\r
+\r
+\def\@fnsymbol#1{\ensuremath{\ifcase#1\or\star\or{\star\star}\or\r
+ {\star\star\star}\or \dagger\or \ddagger\or\r
+ \mathchar "278\or \mathchar "27B\or \|\or **\or \dagger\dagger\r
+ \or \ddagger\ddagger \else\@ctrerr\fi}}\r
+\r
+\def\inst#1{\unskip$^{#1}$}\r
+\def\fnmsep{\unskip$^,$}\r
+\def\email#1{{\tt#1}}\r
+\AtBeginDocument{\@ifundefined{url}{\def\url#1{#1}}{}%\r
+\@ifpackageloaded{babel}{%\r
+\@ifundefined{extrasenglish}{}{\addto\extrasenglish{\switcht@albion}}%\r
+\@ifundefined{extrasfrenchb}{}{\addto\extrasfrenchb{\switcht@francais}}%\r
+\@ifundefined{extrasgerman}{}{\addto\extrasgerman{\switcht@deutsch}}%\r
+}{\switcht@@therlang}%\r
+\providecommand{\keywords}[1]{\par\addvspace\baselineskip\r
+\noindent\keywordname\enspace\ignorespaces#1}%\r
+}\r
+\def\homedir{\~{ }}\r
+\r
+\def\subtitle#1{\gdef\@subtitle{#1}}\r
+\clearheadinfo\r
+%\r
+%%% to avoid hyperref warnings\r
+\providecommand*{\toclevel@author}{999}\r
+%%% to make title-entry parent of section-entries\r
+\providecommand*{\toclevel@title}{0}\r
+%\r
+\renewcommand\maketitle{\newpage\r
+\phantomsection\r
+ \refstepcounter{chapter}%\r
+ \stepcounter{section}%\r
+ \setcounter{section}{0}%\r
+ \setcounter{subsection}{0}%\r
+ \setcounter{figure}{0}\r
+ \setcounter{table}{0}\r
+ \setcounter{equation}{0}\r
+ \setcounter{footnote}{0}%\r
+ \begingroup\r
+ \parindent=\z@\r
+ \renewcommand\thefootnote{\@fnsymbol\c@footnote}%\r
+ \if@twocolumn\r
+ \ifnum \col@number=\@ne\r
+ \@maketitle\r
+ \else\r
+ \twocolumn[\@maketitle]%\r
+ \fi\r
+ \else\r
+ \newpage\r
+ \global\@topnum\z@ % Prevents figures from going at top of page.\r
+ \@maketitle\r
+ \fi\r
+ \thispagestyle{empty}\@thanks\r
+%\r
+ \def\\{\unskip\ \ignorespaces}\def\inst##1{\unskip{}}%\r
+ \def\thanks##1{\unskip{}}\def\fnmsep{\unskip}%\r
+ \instindent=\hsize\r
+ \advance\instindent by-\headlineindent\r
+ \if!\the\toctitle!\addcontentsline{toc}{title}{\@title}\else\r
+ \addcontentsline{toc}{title}{\the\toctitle}\fi\r
+ \if@runhead\r
+ \if!\the\titlerunning!\else\r
+ \edef\@title{\the\titlerunning}%\r
+ \fi\r
+ \global\setbox\titrun=\hbox{\small\rm\unboldmath\ignorespaces\@title}%\r
+ \ifdim\wd\titrun>\instindent\r
+ \typeout{Title too long for running head. Please supply}%\r
+ \typeout{a shorter form with \string\titlerunning\space prior to\r
+ \string\maketitle}%\r
+ \global\setbox\titrun=\hbox{\small\rm\r
+ Title Suppressed Due to Excessive Length}%\r
+ \fi\r
+ \xdef\@title{\copy\titrun}%\r
+ \fi\r
+%\r
+ \if!\the\tocauthor!\relax\r
+ {\def\and{\noexpand\protect\noexpand\and}%\r
+ \protected@xdef\toc@uthor{\@author}}%\r
+ \else\r
+ \def\\{\noexpand\protect\noexpand\newline}%\r
+ \protected@xdef\scratch{\the\tocauthor}%\r
+ \protected@xdef\toc@uthor{\scratch}%\r
+ \fi\r
+ \addtocontents{toc}{\noexpand\protect\noexpand\authcount{\the\c@auco}}%\r
+ \addcontentsline{toc}{author}{\toc@uthor}%\r
+ \if@runhead\r
+ \if!\the\authorrunning!\r
+ \value{@inst}=\value{@auth}%\r
+ \setcounter{@auth}{1}%\r
+ \else\r
+ \edef\@author{\the\authorrunning}%\r
+ \fi\r
+ \global\setbox\authrun=\hbox{\small\unboldmath\@author\unskip}%\r
+ \ifdim\wd\authrun>\instindent\r
+ \typeout{Names of authors too long for running head. Please supply}%\r
+ \typeout{a shorter form with \string\authorrunning\space prior to\r
+ \string\maketitle}%\r
+ \global\setbox\authrun=\hbox{\small\rm\r
+ Authors Suppressed Due to Excessive Length}%\r
+ \fi\r
+ \xdef\@author{\copy\authrun}%\r
+ \markboth{\@author}{\@title}%\r
+ \fi\r
+ \endgroup\r
+ \setcounter{footnote}{\fnnstart}%\r
+ \clearheadinfo}\r
+%\r
+\def\@maketitle{\newpage\r
+ \markboth{}{}%\r
+ \def\lastand{\ifnum\value{@inst}=2\relax\r
+ \unskip{} \andname\\r
+ \else\r
+ \unskip \lastandname\\r
+ \fi}%\r
+ \def\and{\stepcounter{@auth}\relax\r
+ \ifnum\value{@auth}=\value{@inst}%\r
+ \lastand\r
+ \else\r
+ \unskip,\r
+ \fi}%\r
+ \begin{center}%\r
+ \let\newline\\\r
+ {\Large \bfseries\boldmath\r
+ \pretolerance=10000\r
+ \@title \par}\vskip .8cm\r
+\if!\@subtitle!\else {\large \bfseries\boldmath\r
+ \vskip -.65cm\r
+ \pretolerance=10000\r
+ \@subtitle \par}\vskip .8cm\fi\r
+ \setbox0=\vbox{\setcounter{@auth}{1}\def\and{\stepcounter{@auth}}%\r
+ \def\thanks##1{}\@author}%\r
+ \global\value{@inst}=\value{@auth}%\r
+ \global\value{auco}=\value{@auth}%\r
+ \setcounter{@auth}{1}%\r
+{\lineskip .5em\r
+\noindent\ignorespaces\r
+\@author\vskip.35cm}\r
+ {\small\institutename}\r
+ \end{center}%\r
+ }\r
+\r
+% definition of the "\spnewtheorem" command.\r
+%\r
+% Usage:\r
+%\r
+% \spnewtheorem{env_nam}{caption}[within]{cap_font}{body_font}\r
+% or \spnewtheorem{env_nam}[numbered_like]{caption}{cap_font}{body_font}\r
+% or \spnewtheorem*{env_nam}{caption}{cap_font}{body_font}\r
+%\r
+% New is "cap_font" and "body_font". It stands for\r
+% fontdefinition of the caption and the text itself.\r
+%\r
+% "\spnewtheorem*" gives a theorem without number.\r
+%\r
+% A defined spnewthoerem environment is used as described\r
+% by Lamport.\r
+%\r
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\r
+\r
+\def\@thmcountersep{}\r
+\def\@thmcounterend{.}\r
+\r
+\def\spnewtheorem{\@ifstar{\@sthm}{\@Sthm}}\r
+\r
+% definition of \spnewtheorem with number\r
+\r
+\def\@spnthm#1#2{%\r
+ \@ifnextchar[{\@spxnthm{#1}{#2}}{\@spynthm{#1}{#2}}}\r
+\def\@Sthm#1{\@ifnextchar[{\@spothm{#1}}{\@spnthm{#1}}}\r
+\r
+\def\@spxnthm#1#2[#3]#4#5{\expandafter\@ifdefinable\csname #1\endcsname\r
+ {\@definecounter{#1}\@addtoreset{#1}{#3}%\r
+ \expandafter\xdef\csname the#1\endcsname{\expandafter\noexpand\r
+ \csname the#3\endcsname \noexpand\@thmcountersep \@thmcounter{#1}}%\r
+ \expandafter\xdef\csname #1name\endcsname{#2}%\r
+ \global\@namedef{#1}{\@spthm{#1}{\csname #1name\endcsname}{#4}{#5}}%\r
+ \global\@namedef{end#1}{\@endtheorem}}}\r
+\r
+\def\@spynthm#1#2#3#4{\expandafter\@ifdefinable\csname #1\endcsname\r
+ {\@definecounter{#1}%\r
+ \expandafter\xdef\csname the#1\endcsname{\@thmcounter{#1}}%\r
+ \expandafter\xdef\csname #1name\endcsname{#2}%\r
+ \global\@namedef{#1}{\@spthm{#1}{\csname #1name\endcsname}{#3}{#4}}%\r
+ \global\@namedef{end#1}{\@endtheorem}}}\r
+\r
+\def\@spothm#1[#2]#3#4#5{%\r
+ \@ifundefined{c@#2}{\@latexerr{No theorem environment `#2' defined}\@eha}%\r
+ {\expandafter\@ifdefinable\csname #1\endcsname\r
+ {\newaliascnt{#1}{#2}%\r
+ \expandafter\xdef\csname #1name\endcsname{#3}%\r
+ \global\@namedef{#1}{\@spthm{#1}{\csname #1name\endcsname}{#4}{#5}}%\r
+ \global\@namedef{end#1}{\@endtheorem}}}}\r
+\r
+\def\@spthm#1#2#3#4{\topsep 7\p@ \@plus2\p@ \@minus4\p@\r
+\refstepcounter{#1}%\r
+\@ifnextchar[{\@spythm{#1}{#2}{#3}{#4}}{\@spxthm{#1}{#2}{#3}{#4}}}\r
+\r
+\def\@spxthm#1#2#3#4{\@spbegintheorem{#2}{\csname the#1\endcsname}{#3}{#4}%\r
+ \ignorespaces}\r
+\r
+\def\@spythm#1#2#3#4[#5]{\@spopargbegintheorem{#2}{\csname\r
+ the#1\endcsname}{#5}{#3}{#4}\ignorespaces}\r
+\r
+\def\@spbegintheorem#1#2#3#4{\trivlist\r
+ \item[\hskip\labelsep{#3#1\ #2\@thmcounterend}]#4}\r
+\r
+\def\@spopargbegintheorem#1#2#3#4#5{\trivlist\r
+ \item[\hskip\labelsep{#4#1\ #2}]{#4(#3)\@thmcounterend\ }#5}\r
+\r
+% definition of \spnewtheorem* without number\r
+\r
+\def\@sthm#1#2{\@Ynthm{#1}{#2}}\r
+\r
+\def\@Ynthm#1#2#3#4{\expandafter\@ifdefinable\csname #1\endcsname\r
+ {\global\@namedef{#1}{\@Thm{\csname #1name\endcsname}{#3}{#4}}%\r
+ \expandafter\xdef\csname #1name\endcsname{#2}%\r
+ \global\@namedef{end#1}{\@endtheorem}}}\r
+\r
+\def\@Thm#1#2#3{\topsep 7\p@ \@plus2\p@ \@minus4\p@\r
+\@ifnextchar[{\@Ythm{#1}{#2}{#3}}{\@Xthm{#1}{#2}{#3}}}\r
+\r
+\def\@Xthm#1#2#3{\@Begintheorem{#1}{#2}{#3}\ignorespaces}\r
+\r
+\def\@Ythm#1#2#3[#4]{\@Opargbegintheorem{#1}\r
+ {#4}{#2}{#3}\ignorespaces}\r
+\r
+\def\@Begintheorem#1#2#3{#3\trivlist\r
+ \item[\hskip\labelsep{#2#1\@thmcounterend}]}\r
+\r
+\def\@Opargbegintheorem#1#2#3#4{#4\trivlist\r
+ \item[\hskip\labelsep{#3#1}]{#3(#2)\@thmcounterend\ }}\r
+\r
+\if@envcntsect\r
+ \def\@thmcountersep{.}\r
+ \spnewtheorem{theorem}{Theorem}[section]{\bfseries}{\itshape}\r
+\else\r
+ \spnewtheorem{theorem}{Theorem}{\bfseries}{\itshape}\r
+ \if@envcntreset\r
+ \@addtoreset{theorem}{section}\r
+ \else\r
+ \@addtoreset{theorem}{chapter}\r
+ \fi\r
+\fi\r
+\r
+%definition of divers theorem environments\r
+\spnewtheorem*{claim}{Claim}{\itshape}{\rmfamily}\r
+\spnewtheorem*{proof}{Proof}{\itshape}{\rmfamily}\r
+\if@envcntsame % alle Umgebungen wie Theorem.\r
+ \def\spn@wtheorem#1#2#3#4{\@spothm{#1}[theorem]{#2}{#3}{#4}}\r
+\else % alle Umgebungen mit eigenem Zaehler\r
+ \if@envcntsect % mit section numeriert\r
+ \def\spn@wtheorem#1#2#3#4{\@spxnthm{#1}{#2}[section]{#3}{#4}}\r
+ \else % nicht mit section numeriert\r
+ \if@envcntreset\r
+ \def\spn@wtheorem#1#2#3#4{\@spynthm{#1}{#2}{#3}{#4}\r
+ \@addtoreset{#1}{section}}\r
+ \else\r
+ \def\spn@wtheorem#1#2#3#4{\@spynthm{#1}{#2}{#3}{#4}\r
+ \@addtoreset{#1}{chapter}}%\r
+ \fi\r
+ \fi\r
+\fi\r
+\spn@wtheorem{case}{Case}{\itshape}{\rmfamily}\r
+\spn@wtheorem{conjecture}{Conjecture}{\itshape}{\rmfamily}\r
+\spn@wtheorem{corollary}{Corollary}{\bfseries}{\itshape}\r
+\spn@wtheorem{definition}{Definition}{\bfseries}{\itshape}\r
+\spn@wtheorem{example}{Example}{\itshape}{\rmfamily}\r
+\spn@wtheorem{exercise}{Exercise}{\itshape}{\rmfamily}\r
+\spn@wtheorem{lemma}{Lemma}{\bfseries}{\itshape}\r
+\spn@wtheorem{note}{Note}{\itshape}{\rmfamily}\r
+\spn@wtheorem{problem}{Problem}{\itshape}{\rmfamily}\r
+\spn@wtheorem{property}{Property}{\itshape}{\rmfamily}\r
+\spn@wtheorem{proposition}{Proposition}{\bfseries}{\itshape}\r
+\spn@wtheorem{question}{Question}{\itshape}{\rmfamily}\r
+\spn@wtheorem{solution}{Solution}{\itshape}{\rmfamily}\r
+\spn@wtheorem{remark}{Remark}{\itshape}{\rmfamily}\r
+\r
+\def\@takefromreset#1#2{%\r
+ \def\@tempa{#1}%\r
+ \let\@tempd\@elt\r
+ \def\@elt##1{%\r
+ \def\@tempb{##1}%\r
+ \ifx\@tempa\@tempb\else\r
+ \@addtoreset{##1}{#2}%\r
+ \fi}%\r
+ \expandafter\expandafter\let\expandafter\@tempc\csname cl@#2\endcsname\r
+ \expandafter\def\csname cl@#2\endcsname{}%\r
+ \@tempc\r
+ \let\@elt\@tempd}\r
+\r
+\def\theopargself{\def\@spopargbegintheorem##1##2##3##4##5{\trivlist\r
+ \item[\hskip\labelsep{##4##1\ ##2}]{##4##3\@thmcounterend\ }##5}\r
+ \def\@Opargbegintheorem##1##2##3##4{##4\trivlist\r
+ \item[\hskip\labelsep{##3##1}]{##3##2\@thmcounterend\ }}\r
+ }\r
+\r
+\renewenvironment{abstract}{%\r
+ \list{}{\advance\topsep by0.35cm\relax\small\r
+ \leftmargin=1cm\r
+ \labelwidth=\z@\r
+ \listparindent=\z@\r
+ \itemindent\listparindent\r
+ \rightmargin\leftmargin}\item[\hskip\labelsep\r
+ \bfseries\abstractname]}\r
+ {\endlist}\r
+\r
+\newdimen\headlineindent % dimension for space between\r
+\headlineindent=1.166cm % number and text of headings.\r
+\r
+\def\ps@headings{\let\@mkboth\@gobbletwo\r
+ \let\@oddfoot\@empty\let\@evenfoot\@empty\r
+ \def\@evenhead{\normalfont\small\rlap{\thepage}\hspace{\headlineindent}%\r
+ \leftmark\hfil}\r
+ \def\@oddhead{\normalfont\small\hfil\rightmark\hspace{\headlineindent}%\r
+ \llap{\thepage}}\r
+ \def\chaptermark##1{}%\r
+ \def\sectionmark##1{}%\r
+ \def\subsectionmark##1{}}\r
+\r
+\def\ps@titlepage{\let\@mkboth\@gobbletwo\r
+ \let\@oddfoot\@empty\let\@evenfoot\@empty\r
+ \def\@evenhead{\normalfont\small\rlap{\thepage}\hspace{\headlineindent}%\r
+ \hfil}\r
+ \def\@oddhead{\normalfont\small\hfil\hspace{\headlineindent}%\r
+ \llap{\thepage}}\r
+ \def\chaptermark##1{}%\r
+ \def\sectionmark##1{}%\r
+ \def\subsectionmark##1{}}\r
+\r
+\if@runhead\ps@headings\else\r
+\ps@empty\fi\r
+\r
+\setlength\arraycolsep{1.4\p@}\r
+\setlength\tabcolsep{1.4\p@}\r
+\r
+\endinput\r
+%end of file llncs.cls\r
