]> AND Private Git Repository - loba-papers.git/blobdiff - loba-besteffort/loba-besteffort.tex
Logo AND Algorithmique Numérique Distribuée

Private GIT Repository
Embed fonts in pdf file.
[loba-papers.git] / loba-besteffort / loba-besteffort.tex
index fd628570de2cd1549a1073d77618b2395f066d16..b53ffec9d55c835ce200c1710d3266c37f11200f 100644 (file)
@@ -1,72 +1,82 @@
-\documentclass[smallextended]{svjour3}
+\documentclass[preprint]{elsarticle}
+
 \usepackage[utf8]{inputenc}
 \usepackage[T1]{fontenc}
 \usepackage[utf8]{inputenc}
 \usepackage[T1]{fontenc}
-\usepackage{mathptmx}
+
+\usepackage{newtxtext}
+\usepackage[cmintegrals]{newtxmath}
+%\usepackage{mathptmx,helvet,courier}
+
 \usepackage{amsmath}
 \usepackage{amsmath}
-\usepackage{courier}
 \usepackage{graphicx}
 \usepackage{url}
 \usepackage[ruled,lined]{algorithm2e}
 
 \usepackage{graphicx}
 \usepackage{url}
 \usepackage[ruled,lined]{algorithm2e}
 
-\newcommand{\abs}[1]{\lvert#1\rvert} % \abs{x} -> |x|
-
-\newenvironment{algodata}{%
-  \begin{tabular}[t]{@{}l@{:~}l@{}}}{%
-  \end{tabular}}
-
+%%% Remove this before submission
 \newcommand{\FIXMEmargin}[1]{%
   \marginpar{\textbf{[FIXME]} {\footnotesize #1}}}
 \newcommand{\FIXME}[2][]{%
   \ifx #2\relax\relax \FIXMEmargin{#1}%
   \else \textbf{$\triangleright$\FIXMEmargin{#1}~#2}\fi}
 
 \newcommand{\FIXMEmargin}[1]{%
   \marginpar{\textbf{[FIXME]} {\footnotesize #1}}}
 \newcommand{\FIXME}[2][]{%
   \ifx #2\relax\relax \FIXMEmargin{#1}%
   \else \textbf{$\triangleright$\FIXMEmargin{#1}~#2}\fi}
 
+\newcommand{\abs}[1]{\lvert#1\rvert} % \abs{x} -> |x|
+
+\newenvironment{algodata}{%
+  \begin{tabular}[t]{@{}l@{:~}l@{}}}{%
+  \end{tabular}}
+
 \newcommand{\VAR}[1]{\textit{#1}}
 
 \begin{document}
 
 \newcommand{\VAR}[1]{\textit{#1}}
 
 \begin{document}
 
-\title{Best effort strategy and virtual load
-  for asynchronous iterative load balancing}
+\begin{frontmatter}
 
 
-\author{Raphaël Couturier \and
-        Arnaud Giersch
-}
+\journal{Parallel Computing}
 
 
-\institute{R. Couturier \and A. Giersch \at
-              FEMTO-ST, University of Franche-Comté, Belfort, France \\
-              % Tel.: +123-45-678910\\
-              % Fax: +123-45-678910\\
-              \email{%
-                raphael.couturier@femto-st.fr,
-                arnaud.giersch@femto-st.fr}
-}
+\title{Best effort strategy and virtual load for\\
+  asynchronous iterative load balancing}
 
 
-\maketitle
+\author{Raphaël Couturier}
+\ead{raphael.couturier@femto-st.fr}
 
 
+\author{Arnaud Giersch\corref{cor}}
+\ead{arnaud.giersch@femto-st.fr}
 
 
-\begin{abstract}
-
-Most of the  time, asynchronous load balancing algorithms  have extensively been
-studied in a theoretical point  of view. The Bertsekas and Tsitsiklis'
-algorithm~\cite[section~7.4]{bertsekas+tsitsiklis.1997.parallel}
-is certainly  the most well known  algorithm for which the  convergence proof is
-given. From a  practical point of view, when  a node wants to balance  a part of
-its  load to some  of its  neighbors, the  strategy is  not described.   In this
-paper, we propose a strategy  called \emph{best effort} which tries to balance
-the load of a node to all  its less loaded neighbors while ensuring that all the
-nodes  concerned by  the load  balancing  phase have  the same  amount of  load.
-Moreover,  asynchronous  iterative  algorithms  in which  an  asynchronous  load
-balancing  algorithm is  implemented most  of the  time can  dissociate messages
-concerning load transfers and message  concerning load information.  In order to
-increase  the  converge of  a  load balancing  algorithm,  we  propose a  simple
-heuristic called \emph{virtual load} which allows a node that receives a load
-information message  to integrate the  load that it  will receive later  in its
-load (virtually) and consequently sends a (real) part of its load to some of its
-neighbors.  In order to  validate our  approaches, we  have defined  a simulator
-based on SimGrid which allowed us to conduct many experiments.
+\address{FEMTO-ST, University of Franche-Comté\\
+ 19 avenue de Maréchal Juin, BP 527, 90016 Belfort cedex , France\\
+  % Tel.: +123-45-678910\\
+  % Fax: +123-45-678910\\
+}
 
 
+\cortext[cor]{Corresponding author.}
 
 
+\begin{abstract}
+  Most of the time, asynchronous load balancing algorithms have extensively been
+  studied in a theoretical point of view. The Bertsekas and Tsitsiklis'
+  algorithm~\cite[section~7.4]{bertsekas+tsitsiklis.1997.parallel} is certainly
+  the most well known algorithm for which the convergence proof is given. From a
+  practical point of view, when a node wants to balance a part of its load to
+  some of its neighbors, the strategy is not described.  In this paper, we
+  propose a strategy called \emph{best effort} which tries to balance the load
+  of a node to all its less loaded neighbors while ensuring that all the nodes
+  concerned by the load balancing phase have the same amount of load.  Moreover,
+  asynchronous iterative algorithms in which an asynchronous load balancing
+  algorithm is implemented most of the time can dissociate messages concerning
+  load transfers and message concerning load information.  In order to increase
+  the converge of a load balancing algorithm, we propose a simple heuristic
+  called \emph{virtual load} which allows a node that receives a load
+  information message to integrate the load that it will receive later in its
+  load (virtually) and consequently sends a (real) part of its load to some of
+  its neighbors.  In order to validate our approaches, we have defined a
+  simulator based on SimGrid which allowed us to conduct many experiments.
 \end{abstract}
 
 \end{abstract}
 
+% \begin{keywords}
+%   %% keywords here, in the form: keyword \sep keyword
+% \end{keywords}
+
+\end{frontmatter}
+
 \section{Introduction}
 
 Load  balancing algorithms  are  extensively used  in  parallel and  distributed
 \section{Introduction}
 
 Load  balancing algorithms  are  extensively used  in  parallel and  distributed
@@ -299,7 +309,7 @@ neighbor.
 \section{Virtual load}
 \label{Virtual load}
 
 \section{Virtual load}
 \label{Virtual load}
 
-In this section,  we present the concept of \texttt{virtual  load}.  In order to
+In this section,  we present the concept of \emph{virtual load}.  In order to
 use this concept, load balancing messages must be sent using two different kinds
 of  messages:  load information  messages  and  load  balancing messages.   More
 precisely, a node  wanting to send a part  of its load to one  of its neighbors,
 use this concept, load balancing messages must be sent using two different kinds
 of  messages:  load information  messages  and  load  balancing messages.   More
 precisely, a node  wanting to send a part  of its load to one  of its neighbors,
@@ -309,7 +319,7 @@ Load information  message are really  short, consequently they will  be received
 very quickly.  In opposition, load  balancing messages are often bigger and thus
 require more time to be transferred.
 
 very quickly.  In opposition, load  balancing messages are often bigger and thus
 require more time to be transferred.
 
-The  concept  of  \texttt{virtual load}  allows  a  node  that received  a  load
+The  concept  of  \emph{virtual load}  allows  a  node  that received  a  load
 information message to integrate the load that it will receive later in its load
 (virtually)  and consequently send  a (real)  part of  its load  to some  of its
 neighbors. In fact,  a node that receives a load  information message knows that
 information message to integrate the load that it will receive later in its load
 (virtually)  and consequently send  a (real)  part of  its load  to some  of its
 neighbors. In fact,  a node that receives a load  information message knows that
@@ -785,14 +795,14 @@ On constate quoi (vérifier avec les chiffres)?
 
 \FIXME{conclude!}
 
 
 \FIXME{conclude!}
 
-\begin{acknowledgements}
-  Computations have been performed on the supercomputer facilities of
-  the Mésocentre de calcul de Franche-Comté.
-\end{acknowledgements}
+\section*{Acknowledgements}
 
 
-\FIXME{find and add more references}
-\bibliographystyle{spmpsci}
+Computations have been performed on the supercomputer facilities of the
+Mésocentre de calcul de Franche-Comté.
+
+\bibliographystyle{elsarticle-num}
 \bibliography{biblio}
 \bibliography{biblio}
+\FIXME{find and add more references}
 
 \end{document}
 
 
 \end{document}