Réunion Alpage des 31 janvier et 1er février à Bordeaux

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

Jeudi 31 janvier après midi

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."

Vendredi 1er matin

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.

Vendredi 1er après-midi

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.