\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}}
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}
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}
