Tous les exposés (et les repas) auront lieu au Labri (salle
178).

Quelques renseignements
pratiques

Le texte de la proposition d'Alpage est ici

14h 14h30: Pierre Fraigniaud (LIAFA): Checking the validity of the augmented graph model

14h30 15h30: Laurent Viennot (LIAFA): The Inframetric Model for the Internet

Travail commun avec E. Lebhar et P. Fraigniaud

A large amount of algorithms has recently been designed for the

Internet under the assumption that the distance defined by the

round-trip delay (RTT) is a metric. Moreover, many of these

algorithms (\eg overlay network construction, routing scheme

design, sparse spanner construction) rely on the assumption that

the metric has bounded ball growth or bounded doubling dimension.

This paper analyzes the validity of these assumptions and proposes

a tractable model matching experimental observations.

15h30-15h45: pause

15h45-16h15 Cyril Gavoille (travail joint avec A. Labourel):
Distributed
Relationship Schemes for Trees

Nous présenterons une structure de données distribuées pour les arbres
supportant des requêtes entre sommets proches (à distance bornée). Alstrup,
Bille et Rauhe (SODA'03) ont proposé schéma de construction, et ont montré
l'intérêt de ces représentations pour les moteurs de recherche dans les bases de
données XML. Nous apporterons ici une amélioration à leur schéma.

16h15-16h45: Anne Benoit
(ENS Lyon): Scheduling
pipeline workflows to optimize throughput, latency and reliability

Mapping workflow applications onto parallel platforms is a challenging

problem, even for simple application patterns such as pipeline graphs.

Several antagonist criteria should be optimized, such as throughput,

latency, reliability (or a combination). Typical applications include

digital image processing, where images are processed in steady-state

mode. In this talk, we study the complexity of various multi-criteria

mapping problems for pipeline graphs. For some NP-hard instances of

the problem, polynomial bi-criteria heuristics are presented and their

relative performance is evaluated through extensive simulations.

16h45-17h: pause

17h-17h30 Olivier Beaumont Nicolas
Bonichon Lionel Eyraud-Dubois(LaBRI):
Scheduling Divisible Tasks under Bounded
Multi-Port Model

In this paper, we discuss complexity issues for scheduling

divisible workloads on heterogeneous systems under the bounded multi-port model.
To our best knowledge, this paper is the first attempt to consider divisible
load scheduling

under a realistic communication model, where the master node can communicate
simultaneously to several slaves, provided that bandwidth constraints are not
exceeded. In this paper,

we concentrate on one round distribution schemes, where a given node starts its
processing only once all data has been received. Our main contributions

are (i) the proof that processors start working immediately after receiving
their work (ii) the study of the optimal schedule in the case of 2 processors
and (iii) the

proof that scheduling divisible load under the bounded multi-port model is
NP-complete. This last result strongly differs from divisible load literature
and represents the first

NP-completeness result when latencies are not taken into account.

17h30-18h: Ruslan Sadykov (LIX): Scheduling Malleable Jobs on 2 machines

Abstract : "Malleable jobs is a special type of the parallel jobs which

can be executed on more than one processor at the same time. A

particularity of the malleable jobs is that the number of processors a

job is executed on may change during the execution. With the emergence

of new production, communication and parallel computing system, the

usual scheduling requirement that a job is executed only on one

processor has become, in many cases, obsolete and unfounded. Therefore,

parallel jobs scheduling is becoming more and more widespread.

In the talk, we concentrate on the problem of scheduling malleable jobs

to minimize mean flow time. An algorithm for the 2-machine case and a

dominance property for the general case will be presented."

9h00-10h00: Bruno Gaujal (LIG): Routage dans les grilles de calcul

10h00-10h30: Anne Benoit, Loris Marchal, Jean-François Pineau, Yves Robert, Frédéric Vivien (ENS Lyon): Offline and online master-worker scheduling of concurrent bags-of-tasks on heterogeneous platforms

Scheduling problems are
already difficult on traditional parallel

machines. They become extremely challenging on heterogeneous clusters,

even when embarrassingly parallel applications are considered. In this paper we
deal

with the problem of scheduling multiple applications, made of collections of
independent

and identical tasks, on a heterogeneous

master-worker platform. The applications are submitted online, which

means that there is no a priori (static) knowledge of the workload

distribution at the beginning of the execution.

The objective is to minimize the maximum stretch,

i.e. the maximum ratio between the actual time an application has

spent in the system and the time this application would have spent if

executed alone.

On the theoretical side, we design an optimal algorithm for the offline

version of the problem (when all release

dates and application characteristics are known beforehand).

We also introduce several heuristics for the general case of online
applications.

On the practical side, we have conducted extensive simulations and MPI

experiments, showing that we are able to deal with very large problem

instances in a few seconds. Also, the solution that we compute

totally outperforms classical heuristics from the literature,

thereby fully assessing the usefulness of our approach.

10h30-11h: pause

11h-11h30: Hubert Larchevêque:
Construction
distribuée de groupes pour le calcul à grande échelle:

11h30-12h: François Bonnet (IRISA), avec
Roberto Baldoni, Alessia Milani, et Michel Raynal:
Anonymous Graph Exploration without Collision by Mobile Robots

Abstract: Considering a synchronous model for autonomous mobile robots moving on
a finite anonymous graph, this talk focuses on the Constrained Perpetual Graph
Exploration problem (CPGE). That problem requires each robot to perpetually
visits all the vertices of the graph, in such a way that no vertex hosts more
than one robot at a time, and each edge is traversed by at most one robot at a
time. I will present an upper bound k on the number of robots that can be placed
in the graph while keeping CPGE solvability. Interestingly, this upper bound is
related to the topology of the graph.

13h30-14h30: Raymond Namyst (LaBRI):
Ordonnancement sur machines hiérarchiques

14h30:14h45: Pause

14h45-15h15 Gilles Tredan (IRISA): Estimation dynamique du nombre de processus crashés dans un système asynchrone

It is well-known that, in an asynchronous system where

processes are prone to crash, it is impossible to design a

protocol that provides each process with the set of processes

that are currently alive. Basically, this comes from the fact

that it is impossible to distinguish a crashed process from a

process that is very slow or with which communications are

very slow. Nevertheless, designing protocols that provide

the processes with good approximations of the set of processes

that are currently alive remains a real challenge in

fault-tolerant distributed computing. This paper proposes

such a protocol. To that end, it considers a realistic computation

model where the processes are provided with nonsynchronized

local clocks and a function alpha(). That function

takes a local duration as a parameter, and returns an integer

that is an estimate of the number of processes that

can crash during that duration. A simulation-based experimental

evaluation of the protocol is also presented. The

experiments show that the protocol is practically relevant.

15h15-15h45: Tobias Moemke (ETH
Zürich): Reoptimization Problems: Hardness and Algorithms

The talk provides an overview of the concept of reoptimization. To this end
recent development in reoptimizing the travelling salesman problem and the
Steiner tree problem are discussed - including hardness results and
approximation algorithms.