From a2921953b585b36d55e5d8819a99f4da8f842a13 Mon Sep 17 00:00:00 2001
From: Arnaud Giersch <arnaud.giersch@iut-bm.univ-fcomte.fr>
Date: Tue, 12 Feb 2013 00:03:27 +0100
Subject: [PATCH] Describe Makhoul's algorithm in English.

---
 supercomp11/supercomp11.tex | 54 +++++++++++++++++--------------------
 1 file changed, 24 insertions(+), 30 deletions(-)

diff --git a/supercomp11/supercomp11.tex b/supercomp11/supercomp11.tex
index 2f2dd31..741aa26 100644
--- a/supercomp11/supercomp11.tex
+++ b/supercomp11/supercomp11.tex
@@ -14,8 +14,11 @@
   \begin{tabular}[t]{@{}l@{:~}l@{}}}{%
   \end{tabular}}
 
-\newcommand{\FIXME}[1]{%
-  \textbf{$\triangleright$\marginpar{\textbf{[FIXME]}}~#1}}
+\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{\VAR}[1]{\textit{#1}}
 
@@ -260,45 +263,35 @@ several of its neighbors, and then is temporary going off the equilibrium state.
 This is particularly true with strongly connected applications.
 
 In order to reduce this effect, we add the ability to level the amount to send.
-The idea, here, is to make smaller steps toward the equilibrium, such as a
+The idea, here, is to make smaller steps toward the equilibrium, such that a
 potentially wrong decision has a lower impact.
 
 Concretely, once $s_{ij}$ has been evaluated as before, it is simply divided by
 some configurable factor.  That's what we named the ``parameter $k$'' in
 Section~\ref{Results}.  The amount of data to send is then $s_{ij}(t) = (\bar{x}
 - x^i_j(t))/k$.
-\FIXME{check the name ($k$)}
+\FIXME[check that it's still named $k$ in Sec.~\ref{Results}]{}
 
 \section{Other strategies}
 \label{Other}
 
-\FIXME{Réécrire en anglais.}
+Another load balancing strategy, working under the same conditions, was
+previously developed by Bahi, Giersch, and Makhoul in
+\cite{bahi+giersch+makhoul.2008.scalable}.  In order to assess the performances
+of the new \emph{best effort}, we naturally chose to compare it to this anterior
+work.  More precisely, we will use the algorithm~2 from
+\cite{bahi+giersch+makhoul.2008.scalable} and, in the following, we will
+reference it under the name of Makhoul's.
 
-% \FIXME{faut-il décrire les stratégies makhoul et simple ?}
+Here is an outline of the Makhoul's algorithm.  When a given node needs to take
+a load balancing decision, it starts by sorting its neighbors by increasing
+order of their load.  Then, it computes the difference between its own load, and
+the load of each of its neighbors.  Finally, taking the neighbors following the
+order defined before, the amount of load to send $s_{ij}$ is computed as
+$1/(N+1)$ of the load difference, with $N$ being the number of neighbors.  This
+process continues as long as the node is more loaded than the considered
+neighbor.
 
-% \paragraph{simple} Tentative de respecter simplement les conditions de Bertsekas.
-% Parmi les voisins moins chargés que soi, on sélectionne :
-% \begin{itemize}
-% \item un des moins chargés (vmin) ;
-% \item un des plus chargés (vmax),
-% \end{itemize}
-% puis on équilibre avec vmin en s'assurant que notre charge reste
-% toujours supérieure à celle de vmin et à celle de vmax.
-
-% On envoie donc (avec "self" pour soi-même) :
-% \[
-%     \min\left(\frac{load(self) - load(vmin)}{2}, load(self) - load(vmax)\right)
-% \]
-
-\paragraph{makhoul} Ordonne les voisins du moins chargé au plus chargé
-puis calcule les différences de charge entre soi-même et chacun des
-voisins.
-
-Ensuite, pour chaque voisin, dans l'ordre, et tant qu'on reste plus
-chargé que le voisin en question, on lui envoie 1/(N+1) de la
-différence calculée au départ, avec N le nombre de voisins.
-
-C'est l'algorithme~2 dans~\cite{bahi+giersch+makhoul.2008.scalable}.
 
 \section{Virtual load}
 \label{Virtual load}
@@ -520,7 +513,8 @@ number of computing iterations (2000 in our case).
 Note that this convergence detection was implemented in a centralized manner.
 This is easy to do within the simulator, but it's obviously not realistic.  In a
 real application we would have chosen a decentralized convergence detection
-algorithm, like the one described in \cite{10.1109/TPDS.2005.2}.
+algorithm, like the one described by Bahi, Contassot-Vivier, Couturier, and
+Vernier in \cite{10.1109/TPDS.2005.2}.
 
 \paragraph{Platforms}
 
-- 
2.39.5