\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{mathptmx}
+\usepackage{amsmath}
\usepackage{courier}
\usepackage{graphicx}
+\newcommand{\abs}[1]{\lvert#1\rvert} % \abs{x} -> |x|
+
\begin{document}
\title{Best effort strategy and virtual load
\section{Best effort strategy}
\label{Best-effort}
-\textbf{À traduire} Ordonne les voisins du moins chargé au plus chargé.
-Trouve ensuite, en les prenant dans ce ordre, le nombre maximal de
-voisins tels que tous ont une charge inférieure à la moyenne des
-charges des voisins sélectionnés, et de soi-même.
-
-Les transferts de charge sont ensuite fait en visant cette moyenne pour
-tous les voisins sélectionnés. On envoie une quantité de charge égale
-à (moyenne - charge\_du\_voisin).
-
-~\\\textbf{Question} faut-il décrire les stratégies makhoul et simple ?
+We will describe here a new load-balancing strategy that we called
+\emph{best effort}. The general idea behind this strategy is, for a
+processor, to send some load to the most of its neighbors, doing its
+best to reach the equilibrium between those neighbors and himself.
+
+More precisely, when a processors $i$ is in its load-balancing phase,
+he proceeds as following.
+\begin{enumerate}
+\item First, the neighbors are sorted in non-decreasing order of their
+ known loads $x^i_j(t)$.
+
+\item Then, this sorted list is traversed in order to find its largest
+ prefix such as the load of each selected neighbor is lesser than:
+ \begin{itemize}
+ \item the processor's own load, and
+ \item the mean of the loads of the selected neighbors and of the
+ processor's load.
+ \end{itemize}
+ Let's call $S_i(t)$ the set of the selected neighbors, and
+ $\bar{x}(t)$ the mean of the loads of the selected neighbors and of
+ the processor load:
+ \begin{equation*}
+ \bar{x}(t) = \frac{1}{\abs{S_i(t)} + 1}
+ \left( x_i(t) + \sum_{j\in S_i(t)} x^i_j(t) \right)
+ \end{equation*}
+ The following properties hold:
+ \begin{equation*}
+ \begin{cases}
+ S_i(t) \subset V(i) \\
+ x^i_j(t) < x_i(t) & \forall j \in S_i(t) \\
+ x^i_j(t) < \bar{x} & \forall j \in S_i(t) \\
+ x^i_j(t) \leq x^i_k(t) & \forall j \in S_i(t), \forall k \in V(i) \setminus S_i(t) \\
+ \bar{x} \leq x_i(t)
+ \end{cases}
+ \end{equation*}
+
+\item Once this selection is completed, processor $i$ sends to each of
+ the selected neighbor $j\in S_i(t)$ an amount of load $s_{ij}(t) =
+ \bar{x} - x^i_j(t)$.
+
+ From the above equations, and notably from the definition of
+ $\bar{x}$, it can easily be verified that:
+ \begin{equation*}
+ \begin{cases}
+ x_i(t) - \sum_{j\in S_i(t)} s_{ij}(t) = \bar{x} \\
+ x^i_j(t) + s_{ij}(t) = \bar{x} & \forall j \in S_i(t)
+ \end{cases}
+ \end{equation*}
+\end{enumerate}
+
+\section{Other strategies}
+\label{Other}
+
+\textbf{Question} faut-il décrire les stratégies makhoul et simple ?
\paragraph{simple} Tentative de respecter simplement les conditions de Bertsekas.
Parmi les voisins moins chargés que soi, on sélectionne :
