--- /dev/null
+\documentclass[a4paper]{article}
+\usepackage{amsfonts,amssymb}
+\usepackage{amsmath}
+\usepackage{fullpage}
+\usepackage[francais]{babel}
+\usepackage[utf8]{inputenc}
+\usepackage{pifont}
+\usepackage{graphicx}
+\usepackage{ifthen}
+
+\title{Questions/Remarques sur l'équilibrage asynchrone}
+\author{Sylvain Contassot-Vivier et Jacques Bahi}
+
+\begin{document}
+\maketitle
+
+Remarques/questions sur l'équilibrage asynchrone :
+
+\begin{itemize}
+\item Page 1 :
+
+ \begin{itemize}
+ \item Est-ce que l'on considère des connections full-duplex ?\\ OUI
+ C'est-à-dire que si $j$ est connecté à $i$ à l'instant $t$, alors la
+ réciproque est vraie (symétrie des communications)
+
+ \item Qu'entend-t-on exactement par connexion entre deux procs ?\\ Sont-ce les
+ instants où les deux procs échangent des informations ? (a priori OUI)\\
+ Ou les instants où ils échangent de la charge ? (a priori NON)
+
+ \item La condition de somme sur les $\alpha_{ij}$ me paraît très
+ contraignante, voire même problématique. Prenons par exemple le cas simple
+ où le proc $i$ est connecté à un seul proc $j$ ayant une charge inférieure à
+ celle de $i$. On voit logiquement que $i$ doit transférer la moitié de la
+ différence de charge vers $j$ ce qui implique $\alpha_{ij}=1/2$. Et comme il
+ n'y a que $j$ comme voisin de $i$ à $t$ alors la somme des $\alpha_{ij}$ est
+ inférieure à 1.\\$\rightarrow$ cette condition est-elle nécessaire dans la
+ démo ??
+
+ \item Dans la définition de $r_{ij}(t)$, les deux conditions entre parenthèses
+ sont fausses car la 1ère impliquerait le contraire de la remarque précédente
+ (transferts de charges en mode connecté) et la seconde n'a pas lieu d'être
+ (plutôt le contraire) notamment à l'instant $t$ puisque l'envoi de ce qui
+ est reçu à $t$ a obligatoirement été effectué \emph{avant} $t$.
+ \end{itemize}
+
+\item Page 2 :
+
+ \begin{itemize}
+ \item Dans l'équation (2), il faut faire la somme des $v_{ij}(t)$ sur
+ $\overline{N_i}(t)$ et non $N_i(t)$.
+
+ \item Dans l'hypothèse 1, donner les bornes de l'union de $t-B+1$ à $t$ pour
+ être cohérent avec ce qui précède (ne change pas le concept).
+ \end{itemize}
+
+\item Page 3 :
+
+ \begin{itemize}
+ \item L'hypothèse 2 est problématique car elle implique un envoi non nul de
+ charge à tous les processeurs connectés à $i$ à l'instant $t$ et qui ont une
+ charge inférieure à celui-ci. Or, cela n'est pas optimal car il peut
+ arriver (souvent) que certains procs ont une charge inférieure à $i$ mais
+ supérieure à la répartition équilibrée localement. Autrement dit, certains
+ procs reçoivent une charge dont ils n'ont pas besoin.\\
+ $\rightarrow$ Je pense qu'il faut relâcher cette contrainte en changeant le
+ $\forall j$ en $\exists j$. Cela indique bien qu'il y a au moins un
+ transfert de charge lorsque le proc $i$ est connecté à des procs moins
+ chargés.
+
+ \item L'hypothèse 3 est incomplète car il manque la condition de sélection des
+ $j$ dans l'équation (3). Nous avions convenu que cela devait être $\forall
+ j\in N_i(t)$ mais j'en doute fortement maintenant car cela impliquerait que
+ la charge d'un processeur ne peut descendre au-dessous de celle de n'importe
+ lequel de ses voisins à l'instant $t$. Or, cela est une contrainte bloquante
+ pour le transfert de charge (et donc aussi sans doute la convergence) car si
+ le proc $i$ a plusieurs voisins connectés à l'instant $t$ dont un qui a la
+ même charge que lui, alors il ne devra pas envoyer de charge à aucun autre
+ de ses voisins pour respecter cette contrainte. Cela peut donc générer un
+ inter-blocage indéfiniment long si les deux procs en question sont toujours
+ connectés ensemble (il n'y a pas d'hypothèse empêchant cela).\\
+ $\rightarrow$ Je pense que la bonne condition de sélection devrait être
+ $\forall j, s_{ij}(t)>0$ mais cela est à approfondir (notamment avec le
+ choix des $\alpha_{ij}$).
+ \end{itemize}
+
+\item Page 4 :
+
+ \begin{itemize}
+ \item Correction dans l'équation (4) et juste avant ($j\ne j*\in N_i(t)$) : il
+ faut remplacer les $j$ en haut de la fraction par $k$ et inverser les
+ indices/exposants de $x^._.(t)$.
+
+ \item J'ai initialement pensé que le paramètre $\beta$ ne pouvait être égal à
+ 1 sinon cela impliquait un $\alpha_{ij*}$ potentiellement nul. Or, dans la
+ modélisation actuelle, cet alpha peut effectivement être nul si $x^i_{j*}\ge
+ x_i$.
+ On peut donc laisser comme c'était mais on peut aussi distinguer
+ explicitement deux cas : aucun transfert de charge et au moins un transfert
+ avec un voisin. Est-ce que cela apporterait un gain en clarté ??
+
+ \item En ce qui concerne le choix des $\alpha_{ij}$, il me semble qu'il faut
+ prendre en compte la distribution finale sur l'ensemble des procs dans
+ $\{i\}\cup N_i(t)$. Ainsi, on calcule les $\alpha_{ij}$ de façon à avoir une
+ répartition équitable de la charge des procs $i$ et $j$ dans $N_i(t)$ de la
+ façon suivante :
+ \begin{equation*}
+ x_i-\sum_{j\ne i\in N_i(t)} \alpha_{ij}(x_i(t)-x^i_j(t))=\frac{x_i(t)+\sum_{j\in
+ D_i(t)}x^i_j(t)}{|D_i(t)| + 1}
+ \end{equation*}
+ où $D_i(t)$ est l'ensemble des procs $j\in N_i(t)$ qui vérifient :
+ \begin{equation*}
+ \forall j\in D_i(t), x^i_j(t)<\frac{x_i(t) + \sum_{j\in D_i(t)} x^i_j(t)}{|D_i(t)| +
+ 1}
+ \end{equation*}
+
+ Quelques autres cas de politiques de transfert intéressantes :
+
+ \begin{enumerate}
+ \item Envoyer une unité de charge de $i$ vers $j*$ fonctionne mais donne une
+ convergence lente.
+ \item Une version plus rapide est d'envoyer de $i$ vers $j*$ la moitié de
+ leur différence de charge.
+ \item La version donnée dans la thèse d'Abdallah utilise des $\alpha_{ij}$
+ identiques, égaux à $\frac{1}{|N_i(t)|+1}$ pour les procs $j$ dans l'ordre
+ croissant des charges et tant qu'il reste assez de charge sur $i$.
+ D'après mes expés, elle aurait tendance à être moins efficace que 1.
+ \end{enumerate}
+
+ On pourrait peut-être voir également pour anticiper les charges que le proc
+ $i$ va recevoir après l'instant t. On peut éventuellement déduire qu'il va
+ recevoir quelque chose lorsqu'à l'instant $t$ il est connecté avec un proc
+ qui a une charge supérieure à la sienne. On peut borner supérieurement
+ cette apport potentiel par $\frac{1}{2}(x^i_j-x_i)$, mais le problème est
+ que la borne inférieure est nulle. Il paraît donc difficile d'en tirer
+ quelque chose... Voir ce que ça donne en estimant le transfert max... On
+ peut étudier des variantes si l'on a des infos supplémentaires telles que le
+ degré max des noeuds.
+ \end{itemize}
+
+\item Page 5 :
+
+ \begin{itemize}
+ \item Le théorème 3 ne prend pas en compte l'aspect discret des charges en
+ pratique.
+ \end{itemize}
+\end{itemize}
+\end{document}
+
+%%% Local Variables:
+%%% mode: latex
+%%% TeX-master: t
+%%% End:
