Exposés à venir

Les exposés ont lieu le Lundi de 14h à 15h, en salle 178.


Lundi 26 juin 2017 : Exploration de graphes par des robots amnésiques David Ilcinkas

Résumé : Je présenterai un panorama général des résultats et techniques habituelles concernant l'exploration de graphes par des robots amnésiques mais doués de vision globale.


Lundi 24 avril 22 mai 19 juin 2017 : Jointure en Map-Reduce Sofian Maabout

Résumé : Joindre deux tables revient à concaténer leurs enregistrements qui partagent la même valeur sur certains attributs. Nous passons en revue quelques techniques de mise en œuvre de cette opération dans le paradigme Map-Reduce avec étude de leurs complexités.


Lundi 12 juin 2017 : Orientation de graphes dans un environnement asynchrone et avec pannes Noël Gillet

Résumé : Dans cette présentation, nous nous intéressons à l'orientation de graphe de manière distribuée. Plus précisément, nous cherchons à calculer une orientation minimum, c'est-à-dire à minimiser le degré sortant maximum d'un nœud du graphe. Ce problème d'orientation est notamment une modélisation naturelle pour des problèmes d'allocation de ressources. Nous présentons l'algorithme AvgDegAsync qui fonctionne dans un environnement distribué où les communications sont asynchrones et où les nœuds peuvent être en panne. Notre algorithme garantit une $2(2+\epsilon)$-approximation de l'orientation optimale en utilisant un nombre logarithmique de rondes asynchrones. De plus, il ne nécessite pas de connaissance sur le graphe comme le nombre de nœuds ou encore sa densité.

Ce travail a été réalisé avec Nicolas Hanusse et une présentation a été donnée à AlgoTel 2017


Lundi 22 mai 2017 : Soutenance de la thèse de Nesrine Ouled Abdallah Attention ! Lieu : Amphi du LaBRI et horaire : 10h30.
Résumé : ' Dans cette thèse, nous nous intéressons aux modèles de calculs dans les réseaux d'objets à capacités restreintes, tels que les réseaux de capteurs sans fil. Nous nous focalisons sur les protocoles de population proposés par Angluin et al. Dans ce modèle, les objets sont représentés par des agents à états finis, passivement mobiles, communiquant entre paires et formant un réseau asynchrone et anonyme. Nous présentons deux études comparatives qui nous permettent par la suite de proposer une approche établissant le lien des protocoles de population avec deux autres modèles : le modèle des tâches avec les systèmes de réécritures de graphes, et le modèle asynchrone et anonyme d'échange de messages.

Nous passons ensuite au problème d'ordonnancement dans les protocoles de population. Nous proposons un nouvel ordonnanceur probabiliste, 1-central, basé sur les rendez-vous randomisés et appelé HS Scheduler. Contrairement aux autres ordonnanceurs, il est permet à plus d'une paire de communiquer à la fois. Nous prouvons qu'il est équitable avec probabilité 1. Nous analysons par la suite le temps de stabilisation de certains protocoles s'exécutant sous le Random Scheduler (proposé par Angluin et al.) ou le HS Scheduler et sur différentes topologies du graphe d'interaction. Nous prouvons que le HS Scheduler est équivalent en temps au Random Scheduler quand le graphe d'interaction est complet mais qu'il permet une stabilisation plus rapide quand le graphe est aléatoire. Par la suite, nous proposons un autre ordonnanceur qui prend en considération les états des agents et permet d'introduire la terminaison à certains protocoles : le Prorotol Aware HS Scheduler. Nous prouvons qu'il est équitable avec probabilité 1. Nous faisons l'analyse du temps de stabilisation de certains protocoles s'exécutant sous cet ordonnanceur en considérant différentes topologies du graphe d'interaction. Nous prouvons que cet ordonnanceur permet une stabilisation plus rapide pour ces protocoles. Finalement, nous implémentons et simulons sur ViSiDiA l'ensemble des scénarios étudiés et validons les bornes théoriques que nous avons établies.


15 - 19 mai 2017 : EPIT

Abstract: Ecole de Printemps en Informatique Théorique à porquerolles. Le thème cette année est le calcul distribué. Venez nombreux ! http://epit2017.labri.fr/fr/


Lundi 1/8 mai 2017 : relâche

Abstract: jours fériés


Lundi 17 avril 2017 : relâche

Abstract: lundi de pââââââques


Lundi 10 avril 2017 : Robustness in Highly Dynamic Networks Arnaud Casteigts

Abstract: We investigate a special case of hereditary property that we refer to as {\em robustness}. A property is robust in a given graph if it is inherited by all connected spanning subgraphs of this graph. We motivate this definition in different contexts, showing that it plays a central role in highly dynamic networks, although the problem is defined in terms of classical (static) graph theory. In this paper, we focus on the robustness of {\em maximal independent sets} (MIS). Following the above definition, a MIS is said to be robust (RMIS) if it remains a valid MIS in all connected spanning subgraphs of the original graph. We characterize the class of graphs in which all possible MISs are robust. We show that, in these particular graphs, the problem of finding a robust MIS is local; that is, we present an RMIS algorithm using only a sublogarithmic number of rounds (in the number of nodes n) in the LOCAL model. On the negative side, we show that, in general graphs, the problem is not local. Precisely, we prove a $\Omega(n)$ lower bound on the number of rounds required for the nodes to decide consistently in some graphs. This result implies a separation between the RMIS problem and the MIS problem in general graphs. It also implies that any strategy in this case is asymptotically (in order) as bad as collecting all the network information at one node and solving the problem in a centralized manner. Motivated by this observation, we present a centralized algorithm that computes a robust MIS in a given graph, if one exists, and rejects otherwise. Significantly, this algorithm requires only a polynomial amount of local computation time, despite the fact that exponentially many MISs and exponentially many connected spanning subgraphs may exist.


Lundi 3 avril 2017 : Modelling Distributed Computing Task Computability with Dynamic Epistemic Logic Sergio Rajsbaum (UNAM, Mexico)

Abstract: The usual epistemic S5 model for multi-agent systems is a Kripke graph, whose edges are labeled with the agents that do not distinguish between two states. We propose to uncover the higher dimensional information implicit in the Kripke graph, by using as a model its dual, a chromatic simplicial complex. For each state of the Kripke model there is a facet in the complex, with one vertex per agent. If an edge (u,v) is labeled with a set of agents S, the facets corresponding to u and v intersect in a simplex consisting of one vertex for each agent of S. Then we use dynamic epistemic logic to study how the simplicial complex epistemic model changes after the agents communicate with each other. There are topological invariants preserved from the initial epistemic complex to the epistemic complex after an action model is applied, that depend on how reliable the communication is. In turn these topological properties determine the knowledge that the agents may gain after the communication happens, to solve a given distributed task, also modelled using dynamic epistemic logic.


Lundi 27 mars 2017 : Bamboo Garden Trimming Problem (Perpetual maintenance of machines with different attendance urgency factors) Ralf Klasing

Abstract: A garden G is populated by n > 1 bamboos b_1, b_2, ..., b_n with the respective daily growth rates h_1, h_2, ... h_n. It is assumed that the initial heights of bamboos are zero. The robotic gardener or simply a robot maintaining the bamboo garden is attending bamboos and trimming them to height zero according to some schedule.

The Bamboo Garden Trimming Problem, or simply BGT, is to design a perpetual schedule of cuts to maintain the elevation of bamboo garden as low as possible. The bamboo garden is a metaphor for a collection of machines which have to be serviced with different frequencies, by a robot which can service only one machine during a visit. The objective is to design a perpetual schedule of servicing the machines which minimizes the maximum (weighted) waiting time for servicing. We consider two variants of BGT.

In discrete BGT the robot is allowed to trim only one bamboo at the end of each day. In continuous BGT the bamboos can be cut at any time, however, the robot needs time to move from one bamboo to the next one and this time is defined by a weighted network of connections.

For discrete BGT, we show a simple 4-approximation algorithm and, by exploiting relationship between BGT and the classical Pinwheel Scheduling Problem, we obtain also a 2-approximation and even a closer approximation for more balanced growth rates. For continuous BGT, we propose approximation algorithms which achieve approximation ratios O(log(h_1/h_n)) and O(log n).

This is a joint work with L. Gasieniec, Ch. Levcopoulos, A. Lingas, J. Min, and T. Radzik.


Lundi 20 mars 2017 : Self-Stabilizing Disconnected Components Detection and Rooted Shortest-Path Tree Maintenance in Polynomial Steps David Ilcinkas

Abstract: We deal with the problem of maintaining a shortest-path tree rooted at some process r in a network that may be disconnected after topological changes. The goal is then to maintain a shortest-path tree rooted at r in its connected component, V_r, and make all processes of other components detecting that r is not part of their connected component. We propose, in the composite atomicity model, a silent self-stabilizing algorithm for this problem working in semi-anonymous networks under the distributed unfair daemon (the most general daemon) without requiring any a priori knowledge about global parameters of the network. This is the first algorithm for this problem that is proven to achieve a polynomial stabilization time in steps. Namely, we exhibit a bound in O(\maxi \nmax^3 n), where \maxi is the maximum weight of an edge, \nmax is the maximum number of non-root processes in a connected component, and n is the number of processes. The stabilization time in rounds is at most 3\nmax+D, where D is the hop-diameter of V_r.


Lundi 13 mars 2017 : On the Space Complexity of Conflict Detector Objects and Related Objects Colette Johnen

Abstract: We study 3 objects in shared-memory model: conflict detector, adopt-commit and value splitter. We design for each of these objects an implementation that is wait-free, anonymous, input-oblivious and only uses two register primitive operations: read and write. Each of these implementations requires $O(\sqrt(n))$ atomic registers where $n$ is the number of processes. We conclude, by establishing a lower bound for each of these implementations matching the upper bounds derived from the proposed implementations.

Joint work with Claire Capdevielle and Alessia Milani


Lundi 6 mars 2017 : L’agrégation de données dans les graphes dynamiques Quentin Bramas

Résumé : Les graphes dynamiques, aussi appelés graphes évolutifs, graphes temporels ou graphes variant dans le temps, ont gagné en popularité car il permettent de modéliser un grand nombre de phénomènes, et plus particulièrement les interactions dans les réseaux dont la topologie évolue rapidement, comme les réseaux de capteurs sans fil, les protocoles de population, ou bien les réseaux sociaux. Dans un graphe dynamique, les noeuds et les arrêtes apparaissent et disparaissent au fil du temps, et ces changements ne sont pas vus comme des fautes mais bien comme une caractéristique à part entière du graphe. Dans cette présentation, je vais montrer plusieurs manières de définir les graphes dynamiques et quelles sont leurs propriétés. Enfin, je présenterai à titre d’exemple mes contributions sur le problème de l’agrégation de données dans les graphes dynamiques, d’un point de vue centralisé ou distribué, avec connaissance du futur ou non.


Lundi 27 février 2017 : Stratégies d’assignation basées sur des couplages pour améliorer la localité dans les opérations de type Map/Reduce Thomas Lambert

Abstract: Map/Reduce est un paradigme d'algorithme parallèle qui cherche à séparer une tâche en plusieurs sous-tâches de tailles plus réduites afin de les traiter indépendamment et d'agréger ensuite les résultats. Dans cet exposé nous nous intéresserons à la première phase, la phase dite de "Map", c'est à dire le placement de plusieurs tâches indépendantes sur un ensemble de machines. Lors de cette phase, les fichiers d'entrées sont répliqués et pré-placés sur plusieurs processeurs de manière aléatoire afin d'augmenter le nombre de machines susceptible d'exécuter une tâche. Nous voulons ici essayer d'utiliser au mieux cette distribution initiale des fichiers afin de finir l'ensemble des tâches au plus vite (minimisation du makespan). Pour cela nous nous restreignons au cas des tâches homogènes et proposons une modélisation basée sur les graphes bipartis (les arêtes représentent les placement initiaux des fichiers d'entrées). Grâce à un algorithme inspiré des algorithmes de couplage nous montrerons qu'il est possible d’obtenir la solution optimale du problème en temps polynomial. Nous analyserons ensuite la qualité de cette solution en montrons qu'avec forte probabilité elle est au moins quasi-parfaite, c'est à dire égale à l'optimal théorique plus un. Enfin nous conclurons l'exposé sur différents résultats de simulations permettant une analyse du cas où l'on autorise le déplacement des fichiers d'entrées et où l'on cherche à minimiser ces déplacements.


Lundi 20 février 2017 : relâche

Abstract: vacaaaaances


Lundi 13 février 2017 : TBA Nicolas Hanusse

Abstract: Un exposé pas très long


Lundi 6 février 2017 : Petite école du distribué : Analyse des algorithmes distribués probabilistes 3/2 Akka Zemmari

Résumé : Le but de ce cours est de présenter quelques inégalités de concentration utilisées en analyse d’algorithmes distribuées probabilistes. Après quelques rappels et quelques définitions, nous verrons les inégalités utiles et comment les utiliser pour prouver des bornes (supérieures) sur la complexité des algorithmes. Ces bornes étant vraie avec forte probabilité. Nous illustrerons toutes ces méthodes au travers d’un exemple classique en algorithmique distribuée : le calcul d’un ensemble indépendant maximal (MIS).

Remarque : il y a bien deux exposé ce lundi 6 février !


Lundi 6 février 2017 : Calcul de routes et Projets en cours chez Mappy 11h Amphi du Labri Yvan Montalieu - (Mappy)

Abstract: Ce séminaire de présentation des projets en cours chez mappy, entreprise spécialiste du calcul d’itinéraires et des services de cartographie.

Il est ouvert à tous (étudiants master inclus) et devrait intéresser principalement les chercheurs en:

  • algorithmique de "grands" graphes
  • analyse d'image et apprentissage

Lundi 30 janvier 2017 : Petite école du distribué : Analyse des algorithmes distribués probabilistes 2/2 Akka Zemmari

Résumé : Le but de ce cours est de présenter quelques inégalités de concentration utilisées en analyse d’algorithmes distribuées probabilistes. Après quelques rappels et quelques définitions, nous verrons les inégalités utiles et comment les utiliser pour prouver des bornes (supérieures) sur la complexité des algorithmes. Ces bornes étant vraie avec forte probabilité. Nous illustrerons toutes ces méthodes au travers d’un exemple classique en algorithmique distribuée : le calcul d’un ensemble indépendant maximal (MIS).


Lundi 23 janvier 2017 : Petite école du distribué : Analyse des algorithmes distribués probabilistes 1/2 Akka Zemmari

Résumé : Le but de ce cours est de présenter quelques inégalités de concentration utilisées en analyse d’algorithmes distribuées probabilistes. Après quelques rappels et quelques définitions, nous verrons les inégalités utiles et comment les utiliser pour prouver des bornes (supérieures) sur la complexité des algorithmes. Ces bornes étant vraie avec forte probabilité. Nous illustrerons toutes ces méthodes au travers d’un exemple classique en algorithmique distribuée : le calcul d’un ensemble indépendant maximal (MIS).


28-29 novembre 2016 : GDR CoA
Abstract: Programme à venir par ici https://www.irif.univ-paris-diderot.fr/~nschaban/GT-COA/


21 novembre : Petite école du distribué (3/2) Le model LOCAL et la coloration de graphes, Cyril Gavoille
Abstract: - La fin de la borne inférieure sur la coloration des cycles (Linial) - Preuve alternative fondé sur le théorème de Ramsey


14 novembre : Petite école du distribué (2/2) Le model LOCAL et la coloration de graphes, Cyril Gavoille
Abstract: - Coloration rapide des cycles - Borne inférieure en log* sur la coloration des cycles - Etat de l'art


7 novembre : Petite école du distribué (1/2) Le model LOCAL et la coloration de graphes, Cyril Gavoille
Abstract: Le modèle LOCAL - Le problème de la coloration - Coloration des 1-orientations en 6 couleurs - De 6 à 3 couleurs - Cas des graphes arbitraires


3 novembre : Soutenance de thèse de Claire Capdevielle
Abstract:


lundi 31 octobre : relâche
Abstract: C'est les vacances


Lundi 24 octobre : Soutenance de thèse de Yessin M. Neggaz - (Université de Bordeaux)
Abstract:


Lundi 17 octobre : Anonymity Preserving Failure Detector Corentin Travers - (Université de Bordeaux)

Abstract: The consensus problem in anonymous, failures prone and asynchronous shared memory systems is investigated. A new class of failure detectors, called anonymity-preserving failure detectors suited to anonymous systems is introduced. As its name indicates, a failure detector in this class cannot be relied upon to break anonymity. For example, the anonymous perfect detector AP , which gives at each process an estimation of the number of processes that have failed belongs to this class. The weakest failure detector among this class for consensus is then determined. This failure detector, called C, may be seen as a loose failures counter: (1) after a failure occurs, the counter is eventually incremented, and (2) if two or more processes are non-faulty, it eventually stabilizes.


Lundi 10 octobre : Calcul de chemins dans les réseaux multicouches : une approche par la théorie des langages Lamine Lamali - (Université de Bordeaux)

Abstract: Les réseaux multicouches sont des réseaux où plusieurs protocoles coexistent sur différentes couches. Néanmoins, plusieurs architectures réseaux définissent des fonctions de conversion, encapsulation et désencapsulation de protocoles pour pallier cette hétérogénéité. Les algorithmes classiques de calcul de chemins dans les graphes ne peuvent être appliqués dans ce contexte car ils ne prennent pas en compte ces (dés)encapsulations. De plus, les plus courts chemins dans ce type de réseaux ont des caractéristiques non triviales : ils peuvent comporter des boucles et n’ont pas de sous-structure optimale.

Après avoir constaté que les séquences de protocoles associées à un chemin dans un réseau multicouche forment un langage à contexte libre, nous proposons un nouveau modèle de réseau basé sur les automates à pile, ainsi que des algorithmes issus de la théorie des langages pour calculer le(s) plus court(s) chemin(s) dans ce type de réseaux. Nous montrons également que sous contrainte de bande passante, le calcul de chemins devient NP-complet, même dans un réseau symétrique et avec seulement deux protocoles."


Lundi 3 octobre : An overview of discharging methods Marthe Bonamy- (Université de Bordeaux)
Abstract: Discharging methods are used in order to obtain structural lemmas in graph theory. In general, the point is to prove by contradiction that a graph with some properties (planarity, bounded density...) must contain an element of a given list as a subgraph. The idea of this proof technique is as follows: (1) weights are assigned to some elements of the graph (vertices, edges, faces...), (2) a discharging phase allows to redistribute the weights over the graph, (3) using the hypothesis that some subgraphs do not appear in the graph, a weight assessment shows that the total weight is in contradiction with the density/planarity assumptions. In short, it is a counting argument that takes strong advantage of the graph structure. Though the proofs are easier to handle as such for humans, they can be straightforwardly translated into linear programs for the sake of computers.

The existence of a subgraph from this given list can then be used for example for coloring purpose. In particular, this proof technique is decisive for the Four Colour Theorem. During step (2), the weight redistribution is typically local (the weight travels to close elements only). In 2005, Borodin made this technique evolve by introducing global discharging rules (the weight can travel arbitrarily far away). To this day, global discharging methods are still under-developed, but look promising. This talk is meant as an overview of different discharging techniques, through coloring problems they helped answer to. We will also mention their algorithmic appeal, as efficient coloring algorithms as well as tools toward more refined bounds of Fixed Parameter Tractability kernels.


Lundi : '' titre à définir' orateur - (affiliation)

Abstract:


Français English

Emplois

Groupe

GT

Opportunités

edit SideBar

Blix theme adapted by David Gilbert, powered by PmWiki