Résumés


Mardi 13 apres midi


Pierre Fraigniaud (LRI) : Tables de Hachages Distribuées

Cet exposé aura pour principal objectif la présentation de certains
aspects fondamentaux des réseaux distribués, dont en particulier
les réseaux logiques pour systèmes pair-à-pair et les réseaux
sociaux. Dans le cadre des systèmes pair-à-pair, l'exposé décrira
la mise en oeuvre de tables de hachage distribuées et leur analyse.
Dans le cadre des réseaux sociaux, et si le temps le permet,
l'exposé se penchera plus particulièrement sur les propriétés
"petits monde". Dans un troisième temps l'exposé se donnera comme
objectif de faire le pont entre ces deux notions.



Nicolas Hanusse (LaBRI): "vers l'émergence des petit-mondes "



Lionel Eyraud (ID-IMAG) : Ordonnancement de tâches dans OAR, de la théorie à la pratique


The objective of this work is to study and analyze the path from
theoretical models and algorithms to their implementation on an actual
environment on a real platform. We outline in details the divergences
between classical models and a real batch scheduling system, and
propose solutions to adapt a theoretically well-founded algorithm to
such a system. Experimental results show that this implementation
perform about as well as FCFS with backfilling, and much better in the
difficult instances. We hope that further usage of this algorithm in a
live system will show that interaction between theory and practice can
be fruitful.



Mathilde Hurand (LIX) : Finding total unimodularity in optimization problems solved by linear programs

A popular approach in combinatorial optimization is to model problems as integer linear programs. Ideally, the relaxed linear program would have only integer solutions, which happens for instance when the constraint matrix is totally unimodular. Still, sometimes it is possible to build an integer solution with same cost from the fractional solution. Examples are two scheduling problems \cite{Baptiste.Schieber:A-Note-on-Scheduling,BruckerKravchenko:Time-Windows}  and the single disk prefetching/caching problem \cite{Albers.Garg.Leonardi:Minimizing-stall}.
We show that problems such as the three previously mentioned can be separated into two subproblems: (1) finding an optimal feasible set of slots, and (2) assigning the jobs or pages to the slots. It is straigthforward to show that the latter can be solved greedily. We are able to solve the former with a totally unimodular linear program, which provides simpler (and sometimes combinatorial) algorithms with better worst case running times.

joint work with Christoph Dürr



Jean Francois Pineau (ENS Lyon): Influence de l'hétérogénéité sur une plate-forme maître esclave

Nous étudions ici le problème d'ordonnancement de tâches identiques et
indépendantes avec dates d'arrivées sur une plate-forme maître-esclave,
communiquant à l'aide d'un modèle un-port. Alors que ce problème est
résoluble en temps polynomial sur une plate-forme homogène, il n'existe pas
d'algorithme optimal déterministe dès l'ajout d'une source d'hétérogénéité,
que cela soit au niveau des calculs ou des communications. Nous présenterons
ainsi des bornes inférieures de compétitivités pour plus de 3 fonctions
objectives, et ce sur des plate-formes ayant différentes sources
d'hétérogénéité. Nous présenterons également des solutions efficaces pour les
problèmes hors-ligne. Des résultats expérimentaux illustreront ce problème.


Mercredi 14 matin


Cyril Gavoille (LaBRI): Structures de donnees compactes


Il s'agit de donner un aperçu général sur le domaine des structures
de données dans le cadre du calcul distribué, mais pas seulement. En
insistant sur les motivations, un large panel de résultats très
récents sera présenté. Cet exposé s'adresse à tous. Quelques mots-clés
: calcul de distances, plus proche ancêtre commun et les fichiers XML,
représentation implicite et codage des graphes.



Corinne Touati (Univ. Tsukuba): Théorie des jeux et Ordonnancement

Nous etudions la mise en concurence de plusieurs ordonnanceurs sur une
plateforme maitre-esclaves. Nous supposons que la plateforme est
heterogene et que chaque application se compose d'un grand nombre de
taches independantes ayant des besoins en terme de bande passante et
de puissance de calcul connues.
Nous supposons qu'une equite instantanee est assuree au niveau du
systeme, mais que chaque ordonnanceur essaye de maximiser son propre
debit (comportement dit "non-cooperatif").
Nous presentons quelques concepts de base de la theorie des jeux puis
explicitons les equilibres obtenus par ce type de concurence. Nous
montrons alors que les performances des applications peuvent etre
arbitrairement mauvaises pour les mesures de performance classiques.




Martin Quinson: Découverte de Plates-Formes



Loris Marchal (ENS Lyon): Comparaison des stratégies centralisées et distribuées pour l'ordonnancement d'applications concurrentes sur plate-forme maître-esclave hétérogène

Lorsqu'on exécute plusieurs applications simultanément sur une plate-forme de calcul hétérogène, celles-ci doivent se partager les ressources de calcul (processeurs) et de communication (bande-passante des liens réseau). Dans ce travail nous nous intéressons à l'ordonnancement efficace et équitable de ces applications sur une plate-forme maître-esclave où les communications sont faites le long d'un arbre inclus dans le réseau.
Nous montrons qu'il est possible de calculer un ordonnancement périodique asymptotiquement optimal en utilisant la programmation linéaire. Pour les topologies en étoile (arbre de profondeur 1), nous montrons comment calculer la solution optimale de façon analytique. Pour des plates-formes de grande taille, rassembler l'information globale nécessaire au programme linéaire en un ordonnanceur centralisé peut sembler irréaliste. Une solution est d'adapter l'algorithme des flux concurrents d'Awerbuch et Leighton, mais celui nécessite tout de même quelques informations globales. Nous nous intéressons donc également aux heuristiques n'utilisant que des informations locales, et testons leurs performances par simulation. La meilleure de ces heuristiques atteint les performances optimales dans environ les deux tiers de nos essais, mais peut en être très éloigné dans quelques cas.


Mercredi 14 apres-midi




Etienne Rivière (IRISA): Voronet

Cet exposé introduit VoroNet, un réseau d'objets
pair-à-pair reposant sur une décomposition de Voronoi de l'espace de
nommage. VoroNet se distingue
des autres réseaux pair-à-pair par le fait que dans VoroNet, les pairs
sont les objets de l'application eux-mêmes et ont des identificateurs
liés à la sémantique de l'application, au lieu de dépendre d'une
fonction de hachage. Cela permet un support extensible pour une
recherche efficace dans une grande collection de données. Dans VoroNet,
les objets sont organisés dans l'espace de leurs attributs selon un
diagramme de Voronoi. VoroNet est inspiré du modèle petit-monde de
Kleinberg dans lequel chaque pair est connecté à des voisins proches
ainsi qu'à un nœud distant. VoroNet améliore le modèle initial de
Kleinberg car il gère des topologies quelconques et ainsi peut faire
face à des distributions de données hétérogènes. Nous montrons que
VoroNet peut être construit et maintenu de façon totalement
décentralisée et tolérante aux approximations de calculs.
L'analyse théorique du système montre que le routage
dans VoroNet peut être effectué avec un nombre de sauts
poly-logarithmique en la taille du système. Cette analyse est confirmée
par l'évaluation expérimentale, menée sous forme de simulations.

Alfredo Navarra (LaBRI): Minimizing Energy Consumption for Broadcast in Wireless Ad-Hoc Networks

The talk presents latest results mainly on the performance of the
Minimum Spanning Tree (MST) heuristic for the Minimum Energy
Broadcast Routing (MEBR) problem. The MEBR basically consists in
throwing n wireless devices on a d-dimensional Euclidean space while
setting one of them as the root. A node x transmitting with power
energy P_x can reach a node y at distance |x,y| whenever P_x >= Beta
|x,y|^alpha for suitable constants Beta and alpha. The goal is to
perform the broadcast pattern of communication from the root while
minimizing the total consumed energy. One of the most famous
heuristic studied in the literature is definitely the MST one.
The problem will be discussed from both experimental and theoretical
point of views.



Ralf Klasing (LaBRI): Dominating Sets in Web graphs

In this talk we study the size of generalised dominating
sets in two recently proposed models of the web graph. On the one
hand, we show that web graphs have fairly large dominating sets (i.e.
linear in the size of the graph). On the other hand, we present
on-line strategies to construct reasonable dominating sets. The proof
of the algorithmic bounds is based on an adaptation of the
differential equation method to the on-line setting, and may be of
independent interest.
Joint work with Colin Cooper (King's College London) and Michele Zito
(University of Liverpool)]