From ed88631cce8e6737ba146dd0a98914baa97ee29c Mon Sep 17 00:00:00 2001
From: Arnaud Giersch <arnaud.giersch@iut-bm.univ-fcomte.fr>
Date: Wed, 20 Apr 2011 16:08:27 +0200
Subject: [PATCH 1/1] ajout de trucs

---
 supercomp11/biblio.bib      | 16 +++++++
 supercomp11/supercomp11.tex | 90 +++++++++++++++++++++++++++++++++++++
 2 files changed, 106 insertions(+)

diff --git a/supercomp11/biblio.bib b/supercomp11/biblio.bib
index 219485a..164500d 100644
--- a/supercomp11/biblio.bib
+++ b/supercomp11/biblio.bib
@@ -1,3 +1,19 @@
+@InProceedings{bahi+giersch+makhoul.2008.scalable,
+  author =       {Jacques M. Bahi and Arnaud Giersch and Abdallah
+                  Makhoul},
+  title =        {A Scalable Fault Tolerant Diffusion Scheme for Data
+                  Fusion in Sensor Networks},
+  pages =        {10 (5 pages)},
+  booktitle =    {Infoscale 2008, The Third International {ICST}
+                  Conference on Scalable Information Systems},
+  address =      {Vico Equense, Italy},
+  x-publisher =    {ICST (Institute for Computer Sciences,
+                  Social-Informatics and Telecommunications
+                  Engineering)},
+  year =         2008,
+  month =        jun,
+}
+
 @Book{bertsekas+tsitsiklis.1997.parallel,
   author =       {Bertsekas, Dimitri P. and Tsitsiklis, John N.},
   title =        {Parallel and Distributed Computation: Numerical
diff --git a/supercomp11/supercomp11.tex b/supercomp11/supercomp11.tex
index 0479906..a566b8a 100644
--- a/supercomp11/supercomp11.tex
+++ b/supercomp11/supercomp11.tex
@@ -178,7 +178,40 @@ condition or with a weaker condition.
 \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 ?
+
+\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}
@@ -195,6 +228,63 @@ results of the simulations are presented in section~\ref{Results}.
 \subsection{Simulation model}
 \label{Sim model}
 
+\begin{verbatim}
+Communications
+==============
+
+There are two receiving channels per host: control for information
+messages, and data for load transfers.
+
+Process model
+=============
+
+Each process is made of 3 threads: a receiver thread, a computing
+thread, and a load-balancer thread.
+
+* Receiver thread
+  ---------------
+
+    Loop
+    | wait for a message to come, either on data channel, or on ctrl channel
+    | push received message in a buffer of received messages
+    | -> ctrl messages on the one side
+    | -> data messages on the other side
+    +-
+
+   The loop terminates when a "finalize" message is received on each
+   channel.
+
+* Computing thread
+  ----------------
+
+    Loop
+    | if we received some real load, get it (data messages)
+    | if there is some real load to send, send it
+    | if we own some load, simulate some computing on it
+    | sleep a bit if we are looping too fast
+    +-
+    send CLOSE on data for all neighbors
+    wait for CLOSE on data from all neighbors
+
+  The loop terminates when process::still_running() returns false.
+  (read the source for full details...)
+
+* Load-balancing thread
+  ---------------------
+
+    Loop
+    | call load-balancing algorithm
+    | send ctrl messages
+    | sleep (min_lb_iter_duration)
+    | receive ctrl messages
+    +-
+    send CLOSE on ctrl for all neighbors
+    wait for CLOSE on ctrl from all neighbors
+
+  The loop terminates when process::still_running() returns false.
+  (read the source for full details...)
+\end{verbatim}
+
 \subsection{Validation of our approaches}
 \label{Results}
 
-- 
2.39.5