supercomp11/supercomp11.tex

   1
   2 \documentclass[smallextended]{svjour3}
   3 \usepackage{graphicx}
   4
   5 \begin{document}
   6
   7 \title{Best effort strategy and virtual load for asynchronous iterative load balancing}
   8
   9 \author{Raphaël Couturier \and
  10         Arnaud Giersch \and
  11         Abderrahmane Sider
  12 }
  13
  14 \institute{F. Author \at
  15               first address \\
  16               Tel.: +123-45-678910\\
  17               Fax: +123-45-678910\\
  18               \email{fauthor@example.com}           %  \\
  19 %             \emph{Present address:} of F. Author  %  if needed
  20            \and
  21            S. Author \at
  22               second address
  23 }
  24
  25 \maketitle
  26
  27
  28 \begin{abstract}
  29
  30 Most of the  time, asynchronous load balancing algorithms  have extensively been
  31 studied in  a theoretical point of  view. The Bertsekas'  algorithm is certainly
  32 the most well  known algorithm for which the convergence proof  is given. From a
  33 practical point of view, when a node wants to balance a part of its load to some
  34 of its  neighbors, the strategy is not  described.  In this paper,  we propose a
  35 strategy called \texttt{best  effort} which tries to balance the  load of a node
  36 to all its less loaded neighbors  while ensuring that all the nodes concerned by
  37 the load balancing  phase have the same amount  of load.  Moreover, asynchronous
  38 iterative  algorithms  in which  an  asynchronous  load  balancing algorithm  is
  39 implemented most of  the time can dissociate messages  concerning load transfers
  40 and message concerning load information.  In order to increase the converge of a
  41 load balancing  algorithm, we propose a simple  heuristic called \texttt{virtual
  42   load}  which  allows a  node  that receives  an  load  information message  to
  43 integrate  the load  that it  will receive  latter in  its load  (virtually) and
  44 consequently sends a (real) part of its  load to some of its neighbors. In order
  45 to validate our  approaches, we have defined a simulator  based on SimGrid which
  46 allowed us to conduct many experiments.
  47
  48
  49 \end{abstract}
  50
  51
  52
  53
  54 qsdqsd
  55
  56
  57
  58
  59 \end{document}