From Algorithmique Distribuée

Main: Coming talks

Talks are scheduled on Mondays from 2 to 3PM, in room 178.


Lundi 15 janvier 2018 : The Firing Squad Problem Revisited Bernadette Charron-Bost, LIX

Résumé : In the classical firing squad problem, an unknown number of nodes represented by identical finite states machines is arranged on a line and in each time unit each node may change its state according to its neighbors' states. Initially all nodes are passive, except one specific node located at an end of the line, which issues a fire command. This command needs to be propagated to all other nodes, so that eventually all nodes simultaneously enter some designated “firing" state.

A natural extension of the firing squad problem, introduced in this paper, allows each node to postpone its participation in the squad for an arbitrary time, possibly forever, and firing is allowed only after all nodes decided to participate. This variant is highly relevant in the context of decentralized distributed computing, where processes have to coordinate for initiating various tasks simultaneously.

The main goal of this paper is to study the above variant of the firing squad problem under the assumptions that the nodes are infinite state machines, have full computational capabilities, and that the inter-node communication links can be changed arbitrarily in each time unit, i.e., are defined by a dynamic graph. In this setting, we study the following fundamental question: what connectivity requirements enable a solution to the firing squad problem?

Our main result is an exact characterization of the dynamic graphs for which the firing squad problem can be solved. When restricted to static directed graphs, this characterization implies that the problem can be solved if and only if the graph is strongly connected. We also discuss how information on the number of nodes or on the diameter of the network, and the use of randomization, can improve the solutions to the problem.

Joint work with Shlomo Moran (Technion)


Lundi 18 décembre 2017 : fête du LaBRI

Résumé : moment qui se veut convivial et festif


Lundi 11 décembre 2017 : Présentation de l'activité du thème

Résumé : Présentation informelle de l'activité du thème. Chacun est invité à présenter en quelques slides ou directement au tableau ses préoccupations actuelles au sens large (travail en cours, problème ouvert, problème intéressant, ou collaborations, projets, etc.)


Lundi 4 décembre 2017 : Error-sensitive proof-labeling schemes Laurent Feuilloley, IRIF.

Résumé : Proof-labeling schemes are known mechanisms providing nodes of networks with certificates that can be verified locally by distributed algorithms. Given a boolean predicate on network states, such schemes enable to check whether the predicate is satisfied by the actual state of the network, by having nodes interacting with their neighbors only. Proof-labeling schemes are typically designed for enforcing fault-tolerance, by making sure that if the current state of the network is illegal with respect to some given predicate, then at least one node will detect it. Such a node can raise an alarm, or launch a recovery procedure enabling the system to return to a legal state. In this paper, we introduce error-sensitive proof-labeling schemes. These are proof-labeling schemes which guarantee that the number of nodes detecting illegal states is linearly proportional to the edit-distance between the current state and the set of legal states. By using error-sensitive proof-labeling schemes, states which are far from satisfying the predicate will be detected by many nodes, enabling fast return to legality. We provide a structural characterization of the set of boolean predicates on network states for which there exist error-sensitive proof-labeling schemes. This characterization allows us to show that classical predicates such as, e.g., acyclicity, and leader admit error-sensitive proof-labeling schemes, while others like regular subgraphs don't. We also focus on compact error-sensitive proof-labeling schemes. In particular, we show that the known proof-labeling schemes for spanning tree and minimum spanning tree, using certificates on O(logn) bits, and on O(log2n) bits, respectively, are error-sensitive, as long as the trees are locally represented by adjacency lists, and not just by parent pointers.


Lundi 27 novembre 2017 : Pas de GT

Résumé : On pourra par contre aller voir une soutenance de thèse.


Lundi 20 novembre 2017 : Proving lower bounds in the LOCAL model Juho Hirvonen, IRIF.

Résumé : Locality of distributed computing is the study of how far information has to propagate in distributed systems. In the last few years, we have seen the emergence of a complexity theory of locality for a large class of natural problems, the locally checkable labelings. I will present some of the new lower bound techniques that have contributed to this theory. These techniques are based on simulation, providing elegant and simple proofs.

The sinkless orientation problem has played a key role a key role in this new theory. We gave a randomized lower bound of Ω(log log n) for this problem (Brandt et al., STOC 2016), establishing it as the first problem with provably "intermediate" complexity. Our lower bound was later lifted to an Ω(log n) deterministic lower bound by Chang et al. (FOCS 2016). This, along with the matching algorithms of Ghaffari and Su (SODA 2017), show that this problem exhibits an exponential separation between deterministic and randomized complexities.

I will show a simpler lower bound proof for this problem, using elements from different proofs. I will try to highlight the effectiveness of simulation as a proof technique, and try to showcase how complexity theoretic results can be used as black boxes in order to aid these proofs.


Lundi 13 novembre 2017 : Model Equivalences through Simulations Damien Imbs, LIF, U. Marseille.

Résumé : Simulations are powerful tools in the study of the computability power of a distributed system. A simulation takes as input an algorithm that solves an instance of a given class of problems in a given model and produces as output another algorithm that executes correctly in another model.

This talk will first present the BG simulation, that shows that in a crash-prone asynchronous shared memory model, the important parameter regarding computability is the number of possible crashes, not the total number of processes. It will then present a more recent simulation that shows that, under certain conditions, Byzantine failure-prone systems can solve the same class of problems as crash-prone ones.


Lundi 6 novembre 2017 : Fast Asymptotic and Approximate Consensus in Highly Dynamic Networks. Matthias Fuegger, LSV.

Résumé : Reaching consensus on a common value in a distributed system is a well-studied central problem in distributed computing. Unfortunately, even modest network dynamics prohibit solvability. For many problems, such as, distributed control, clock synchronization, etc., it is however sufficient to asymptotically converge to the same value, or decide on values not too far from each other. We study solvability of these consensus variants in highly dynamic networks, provide time complexity results, and present fast algorithms. The talk finishes with an outlook on current research in biology.

The talk is on previous and current research with Bernadette Charron-Bost (LIX) and Thomas Nowak (LRI).


16-20 octobre 2017 : DISC

Résumé : 31ème édition, à Vienne.


Lundi 9 octobre 2017 : Relationships between various communication models of shared memory paradigm for fault-tolerant distributed computing Colette Johnen.

Résumé : There is a proliferation of communication models for distributed computing, in shared memory paradigm. Since subtle changes in the communication model can result in significant changes to the solvability/unsolvability or to the complexity of various problems, it becomes imperative to understand the relationships between the many models The situation becomes even more complicated when additional requirements such as fault-tolerance are added to the mix. This motivates us to study under what circumstances a program designed for one model and delivering some set of additional guarantees can be converted into an ``equivalent'' programs for a different model while delivering comparable guarantees.


Du 2 au 4 octobre 2017 : Réunion ANR Descartes

Résumé : Dans un château pas loin de Poitiers


Lundi 25 septembre 2017 : Message-Passing Algorithms for the Verification of Distributed Protocols Loïg Jézéquel, IRCCyN, Université de Nantes.

Résumé : Message-passing algorithms (MPAs) are an algorithmic paradigm for the following generic problem: given a system consisting of several interacting components, compute a new version of each component representing its behaviour inside the system. MPAs avoid computing the full state space by propagating messages along the edges of the system interaction graph. We present an MPA for verifying local properties of distributed protocols with a tree communication structure. We report on an implementation, and validate it by means of two case studies, including an analysis of the PGM protocol.


Du 11 au 13 septembre 2017 : Conférence "Fundamentals of Computation Theory" (Amphi du LaBRI)

Les exposés "distribués" ont été planifiés le mercredi. Vous pouvez trouver le programme sur https://fct2017.labri.fr


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:


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:


Récupéré sur http://algodist.labri.fr/index.php/Main/GT
Page mise à jour le 30 novembre 2017 à 09h54