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)]