Fix fonts, inputenc, and fontenc.

[loba-papers.git] / supercomp11 / supercomp11.tex

diff --git a/supercomp11/supercomp11.tex b/supercomp11/supercomp11.tex
index 7daaa52bed489911e6845de60a1e20e27e21105b..29208fc51bea56b8d5db5ade12095783ab40245d 100644 (file)
--- a/supercomp11/supercomp11.tex
+++ b/supercomp11/supercomp11.tex
@@ -1,5 +1,8 @@
-

 \documentclass[smallextended]{svjour3}
 \documentclass[smallextended]{svjour3}

+\usepackage[utf8]{inputenc}
+\usepackage[T1]{fontenc}
+\usepackage{mathptmx}
+\usepackage{courier}

 \usepackage{graphicx}
 
 \begin{document}
 \usepackage{graphicx}
 
 \begin{document}


@@ -28,31 +31,45 @@
 \begin{abstract}
 
 Most of the  time, asynchronous load balancing algorithms  have extensively been
 \begin{abstract}
 
 Most of the  time, asynchronous load balancing algorithms  have extensively been

-studied in  a theoretical point of  view. The Bertsekas'  algorithm 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 \texttt{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 \texttt{virtual
-  load}  which  allows a  node  that receives  an  load  information message  to
-integrate  the load  that it  will receive  latter 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.
+studied in a theoretical point  of view. The Bertsekas and Tsitsiklis' algorithm
+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 \texttt{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 \texttt{virtual load} which allows a node that receives an load
+information message  to integrate the  load that it  will receive latter  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}
 
 
 

-
-qsdqsd
-
+Load  balancing algorithms  are  extensively used  in  parallel and  distributed
+applications in  order to  reduce the  execution times. They  can be  applied in
+different scientific  fields from high  performance computation to  micro sensor
+networks.   They are  iterative by  nature.  In  literature many  kinds  of load
+balancing  algorithms  have been  studied.   They  can  be classified  according
+different  criteria:   centralized  or  decentralized,  in   static  or  dynamic
+environment,  with  homogeneous  or  heterogeneous load,  using  synchronous  or
+asynchronous iterations, with  a static topology or a  dynamic one which evolves
+during time.  In  this work, we focus on  asynchronous load balancing algorithms
+where computer nodes  are considered homogeneous and with  homogeneous load with
+no external  load. In  this context, Bertsekas  and Tsitsiklis have  proposed an
+algorithm which is definitively a reference  for many works. In their work, they
+proved that under classical  hypotheses of asynchronous iterative algorithms and
+a  special  constraint   avoiding  \texttt{ping-pong}  effect,  an  asynchronous
+iterative algorithm  converge to  the uniform load  distribution. This  work has
+been extended by many authors. For example, DASUD propose a version working with
+integer load.