Add algorithm makhoul2.

[loba.git] / ALGORITHMS

diff --git a/ALGORITHMS b/ALGORITHMS
index 69a25455b0dc3793f4e84071b23f17645aa677a7..11e70999d94b00d001bee22e63375c941b90989c 100644 (file)
--- a/ALGORITHMS
+++ b/ALGORITHMS
@@ -1,15 +1,17 @@
-DESCRIPTIONS DES ALGORITHMES
+DESCRIPTIONS DES ALGORITHMES D'ÉQUILIBRAGE
 
 fairstrategy
 ============
-Tant qu'il reste un voisin moins chargé[*] que soi-même, envoyer une
-certaine quantité de charge (delta = 0.001 dans le code) à tous les
-voisins moins chargés que soi-même.
+Ordonne les voisins du plus chargé au moins chargé.
+Ensuite, tant qu'il reste un voisin moins chargé[*] que soi-même,
+envoyer une certaine quantité de charge (delta = 0.001 dans le code) à
+tous les voisins moins chargés que soi-même.
 [*] en réalité, un voisin moins chargé à qui on peut envoyer delta de
     charge sans devenir moins chargé que lui.
 
 Q: à quoi sert le tri du départ ?
 
+
 makhoul
 =======
 Ordonne les voisins du moins chargé au plus chargé puis calcule les
@@ -19,10 +21,29 @@ 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.
 
+Références:
+    - Algorithm 2 dans
+      http://portal.acm.org/citation.cfm?id=1459693.1459708
+      http://info.iut-bm.univ-fcomte.fr/staff/giersch/biblio.html#bahi_giersch_makhoul.2008.scalable
+ou bien
+    - Algorithme 6 (p.111) dans la thèse de Abdallah Makhoul.
+
+
+makhoul2
+========
+Comme makhoul, mais la différence est calculée avec la charge courante
+(intégrant donc les envois déjà faits).
+
+Références:
+    - le code source :-(
+      cf. makhoul.txt
+
+
 none
 ====
 Aucun équilibrage.  Peut-être utile pour tester/déboguer le code.
 
+
 simple
 ======
 Tentative de respecter simplement les conditions de Bertsekas.