Exposés à venir

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

Pour s'inscrire à la liste de diffusion, envoyer un courrier électronique à sympa@diff.u-bordeaux.fr avec comme sujet "subscribe labri.algodist-gt votre_nom votre_prénom". Pour se désabonner, il suffit d'envoyer à sympa@diff.u-bordeaux.fr un message dont le sujet est "unsubscribe labri.algodist-gt"

Lundi 5 novembre 2018 : TBA Patrick Lambein, LIX
Résumé :

Lundi 8 octobre 2018 : Mutual Exclusion - New Twists on an Old Tale Danny Hendler, Ben-Gurion University
Résumé :

Lundi 25 juin 2018 : TBA Sébastien Tixeuil, UPMC
Résumé :

Lundi 4 juin 2018 : A Journey through Dynamic Networks (with Excursions) Arnaud Casteigts
Résumé : Soutenance d'habilitation à diriger des recherches (14h, amphi du LaBRI).

Lundi 14 mai 2018 : ' Distributed Spanning Tree Computation, Distributed Topology Computation and... Coverings ' Yves Métivier
Résumé : We present a characterisation of graphs which enable the distributed computation of their topology or the distributed computation of a spanning tree in terms of coverings. (Travail avec Arnaud Casteigts et John Michael Robson)

Lundi 23 avril 2018 : Whac-A-Mole: Smart node positioning in clone attack in wireless sensor networks Akka Zemmari
Résumé : Wireless sensor networks are often deployed in unattended environments and, thus, an adversary can physically capture some of the sensors, build clones with the same identity as the captured sensors, and place these clones at strategic positions in the network for further malicious activities. Such attacks, called clone attacks, are a very serious threat against the usefulness of wireless networks. Researchers proposed different techniques to detect such attacks. The most promising detection techniques are the distributed ones that scale for large networks and distribute the task of detecting the presence of clones among all sensors, thus, making it hard for a smart attacker to position the clones in such a way as to disrupt the detection process. However, even when the distributed algorithms work normally, their ability to discover an attack may vary greatly with the position of the clones. We believe this aspect has been greatly underestimated in the literature. In this paper, we present a thorough and novel study of the relation between the position of clones and the probability that the clones are detected. To the best of our knowledge, this is the first such study. In particular, we consider four algorithms that are re- presentatives of the distributed approach. We evaluate for them whether their capability of detecting clone attacks is influenced by the positions of the clones. Since wireless sensor networks may be deployed in different situations, our study considers several possible scenarios: a uniform scenario in which the sensors are deployed uniformly, and also not uniform scenarios, in which there are one or more large areas with no sensor (we call such areas “holes”) that force communications to flow around these areas. We show that the different scenarios greatly influence the performance of the algorithms. For instance, we show that, when holes are present, there are some clone positions that make the attacks much harder to be detected. We believe that our work is key to better understand the actual security risk of the clone attack in the presence of a smart adversary and also with respect to different deployment scenarios. Moreover, our work suggests, for the different scenarios, effective clone detection solutions even when a smart adversary is part of the game.

Lundi 9 avril 2018 : (Méta)-noyaux constructifs et linéaires dans les graphes peu denses Valentin Garnero
Résumé : Dans cet exposé je vous présenterai les résultats obtenus au cours de ma thèse, laquelle traite de noyaux et de complexité paramétrée. La complexité paramétrée est une branche de l'algorithmie qui analyse la complexité d'un problème en fonction de la taille des données n et d'un paramètre k (arbitraire). L'objectif est de pouvoir attaquer des problèmes difficiles (NPc) et de montrer que l’exposition combinatoire n'est fonction que du paramètre (et pas de la taille des données), cad, trouver des algorithmes en f(k)+p(n). L'extraction de noyau est une méthode qui permet d'obtenir des algorithmes avec un telle complexité. Il s'agit d'un pré-calcul (une réduction polynomiale) qui réduit la taille des données en temps polynomial, tout en garantissant que la taille du noyau (l'instance réduite) est bornée par une fonction du paramètre g(k). Il suffit de résoudre le problème dans le noyau, de n'importe quelle façon, pour obtenir un algorithme en f(g(k)) + p(n).

La méthode de décomposition en régions [Alber, Fellows, Niedermeier] est un résultat majeur dans le domaine des noyaux. Elle a permis de construire de nombreux noyaux linaires pour des variantes de la Domination dans les graphes planaires. J'illustrerai cette méthode avec le cas de la Domination Rouge Bleu, qui consiste à trouver, dans un graphe bicoloré, un ensemble de sommets bleus tel que tous les sommets rouges sont à distance au plus 1 de la solution.

Cette méthode a ensuite été généralisée par des méta-résultats [ex: Bodlaender, Fomin, Lokshtanov, Penninkx, Saurabh, Thilikos], qui prouve l'existence de noyaux (dans des graphes peu denses) pour tout problème vérifiant certaines conditions génériques. Je présenterai un de ses méta-résultats, qui se base sur la programmation dynamique et sur la décomposition en protrusion, et qui a le mérite d’être constructif.

Lundi 26 mars 2018 : Distributed coloring in sparse graphs with fewer colors Marthe Bonamy
Résumé : We are concerned with efficiently coloring sparse graphs in the distributed setting with as few colors as possible. According to the celebrated Four Color Theorem, planar graphs can be colored with at most 4 colors, and the proof gives a (sequential) quadratic algorithm finding such a coloring. A natural problem is to improve this complexity in the distributed setting. Using the fact that planar graphs contain linearly many vertices of degree at most 6, Goldberg, Plotkin, and Shannon obtained a deterministic distributed algorithm coloring n-vertex planar graphs with 7 colors in O(logn) rounds. Here, we show how to color planar graphs with 6 colors in polylog(n) rounds. Our algorithm indeed works more generally in the list-coloring setting and for sparse graphs (for such graphs we improve by at least one the number of colors resulting from an efficient algorithm of Barenboim and Elkin, at the expense of a slightly worst complexity). Our bounds on the number of colors turn out to be quite sharp in general. Among other results, we show that no distributed algorithm can color every n-vertex planar graph with 4 colors in o(n) rounds. This is joint work with Pierre Aboulker, Nicolas Bousquet and Louis Esperet.

Lundi 19 mars 2018 : Simple Consensus Protocols Frederik Mallmann-Trenn, MIT
Résumé : We study consensus processes on the complete graph of n nodes. Initially, each node supports one from up to n different opinions. Nodes randomly and in parallel sample the opinions of constant many nodes. Based on these samples, they use an update rule to change their own opinion. The goal is to reach consensus, a configuration where all nodes support the same opinion. In particular, we consider the Voter process, 3-Majority, and 2-Choices.

Lundi 12 mars 2018 : TBA Akka Zemmari REPORTÉ
Résumé :

Lundi 5 mars 2018 : ' PADEC: A Framework for Certified Self-Stabilization ' Karine Altisen, Verimag
Résumé : Joint work with Pierre Corbineau and Stéphane Devismes

Self-stabilization is a property that allows distributed algorithms to withstand transient faults and recover a correct behavior within finite time. It has been introduced by Dijkstra in 1974. Over the last decades, progress in self-stabilization has led to consider more and more adversarial environments. This make the design, proof for correctness and complexity analysis of self-stabilizing solutions more and more intricate.

However, those proofs are commonly written by hand, based on informal reasoning. In this work, we propose instead to use a proof assistant, a tool which allows to develop certified proofs interactively and check them mechanically. We present the PADEC framework, a Coq library dedicated to building certified proofs of self-stabilizing algorithms.

We first define in Coq the computational model which is the most commonly used in the self-stabilizing area, and its semantics. We propose several tools for proving convergence of algorithms and for counting elements. We illustrate the use of our framework by: - certifying a non-trivial part of an existing self-stabilizing algorithm; - certifying a commonly-used composition operation for self-stabilizing algorithms.

Lundi 26 février 2018 : TBA Nicolas Hanusse REPORTÉ

Lundi 12 février 2018 : Distributed Recoloring: the addition of colors Mikaël Rabie, Aalto University

Résumé : Given two colorings of a graph, we consider the following question: can we re-color the graph from one coloring to the other through a series of elementary changes? Here, an elementary change, or step, consists in selecting an independent set and changing the color of each vertex to another also compatible with the colors of its neighbors. The answer is not always positive, and it is in fact a PSPACE-complete decision problem. In this talk, we try to quantify how considering a stable set at each step instead of a single vertex impacts the number of steps necessary for a re-coloring, and how much communication is needed in the LOCAL model (at each round, a vertex can only communicate with its neighbors, with no limitation as to the size of the messages nor the computation power of the vertex) to compute the re-coloring or decide there is none. We also consider the question of how many extra colors are needed to make the problem always feasible, and beyond that, how the number of necessary steps decreases with the addition of colors. The case of trees is of special interest. I will provide a collection of both positive and negative results around those questions. This a joint work with Marthe Bonamy, Paul Ouvrard, Jukka Suomela and Jara Uitto.

Lundi 5 février 2018 : Refinement-Based Composition for Computing Snapshots in Distributed Anonymous Networks Maha Boussabbeh

Résumé : Recording a global state of a distributed computation is one of the most important paradigm that finds applications in several aspects of a distributed system design. Algorithms recording such global states are called snapshot algorithms. Most of them assume that the network is not anonymous or there exists a distinguished process. We explore the correct-by-construction process to formalize snapshot computations in an anonymous network. Based on recent studies, we investigate existing algorithms to highlight how they can be composed and specified in a top/down approach in order to obtain a global view anonymously. This approach is supported by an incremental process controlled by model refinements.

Lundi 22 janvier 2018 : On the simplification of temporal cliques Arnaud Casteigts
Résumé : In the context of this talk, a temporal clique is a complete graph with a unique integer label on every edge. This number can be thought of as the only date at which both endpoints interact. In a recent article, Akrida, Gasieniek, Mertzios, and Spirakis show that n/4 well chosen edges can be removed in such a graph without breaking temporal connectivity (i.e. maintaining increasing paths (journeys) between every pair of nodes, in both directions). In this talk, I will present a three-steps proof which gradually improves upon this result. The first step shows that (n^2)/8 edges (i.e. one quarter of the edges) can be removed; the second step, building upon the first, shows that half of the edges can actually be removed; then the third step, building upon the other two, shows that all edges but O(n) can actually be removed. This is obviously tight (up to a constant factor). Characterizing the exact factor that our proof yields is still work in progress. On the other hand, we give a conjecture as to the exact number of edges which can be removed (à un près), supported by extensive simulations.

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:

  • 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

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

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

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)


Français English





edit SideBar

Blix theme adapted by David Gilbert, powered by PmWiki