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