Liste des événements uniques du groupe Algorithmique Distribuée


2018-10-08The mutual exclusion problem: new twists on an old tale
14:00-15:00
178
Mutual exclusion, introduced by Dijkstra more than 50 years ago, is one of the most fundamental problems in distributed computing. In this talk, I will describe a few key results in classic shared-memory mutual exclusion research. Time permitting, I will also present novel variants of mutual exclusion whose goal is to model existing computer systems more realistically, as well as to model emerging new types of systems. The talk will be self-contained and no prior knowledge of shared-memory mutual exclusion is assumed.
 Plus d'infos  


2018-06-25Multihop Byzantine Reliable Broadcast
14:00-15:00
178
Communiquer via un réseau lorsqu’on est pas directement connectés requiert la participation d'intermédiaires dont la fiabilité peut être remise en question. Cet exposé passe en revue plusieurs algorithmes distribués pour le problème de la diffusion d’informations dans un réseau multisauts en dépit de tiers malveillants, et discute leurs avantages et inconvénients respectifs.
 Plus d'infos  


2018-05-14Distributed Spanning Tree Computation, Distributed Topology Computation and... Coverings
14:00-15:00
178
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)

 Plus d'infos  


2018-04-23Whac-A-Mole: Smart node positioning in clone attack in wireless sensor networks
14:00-15:00
178
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.
 Plus d'infos  


2018-04-09(Méta)-noyaux constructifs et linéaires dans les graphes peu denses
14:00-15:00
178
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.
 Plus d'infos  


2018-03-26Distributed coloring in sparse graphs with fewer colors
14:00-15:00
178
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.
 Plus d'infos  


2018-03-19 Simple Consensus Protocols
14:00-15:00
178
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.
 Plus d'infos  


2018-03-05PADEC: A Framework for Certified Self-Stabilization
14:00-15:00
178
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.
 Plus d'infos  


2018-02-12Distributed Recoloring: the addition of colors
14:00-15:00
178
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.
 Plus d'infos  


2018-02-05 Refinement-Based Composition for Computing Snapshots in Distributed Anonymous Networks
14:00-15:00
178
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.
 Plus d'infos  


2018-01-22On the simplification of temporal cliques
14:00-15:00
178
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.
 Plus d'infos  


2018-01-15The Firing Squad Problem Revisited
14:00-15:00
178
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)
 Plus d'infos  


2017-12-11Présentation de l'activité du thème
14:00-15:00
178
Présentation de l'activité du thème. Chacun est invité à présenter en quelques slides ou au tableau ses préoccupations actuelles au sens large (travail en cours, problème ouvert, problème intéressant, ou collaborations, projets, etc.)
 Plus d'infos  


2017-12-04Error-sensitive proof-labeling schemes
14:00-15:00
178
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.

 Plus d'infos  


2017-11-20Proving lower bounds in the LOCAL model
14:00-15:00
178
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.
 Plus d'infos  


2017-11-13Model Equivalences through Simulations
14:00-15:00
178
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.
 Plus d'infos  


2017-11-06 Fast Asymptotic and Approximate Consensus in Highly Dynamic Networks
14:00-15:00
178
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).
 Plus d'infos  


2017-10-09Relationships between various communication models of shared memory paradigm for fault-tolerant distributed computing
14:00-15:00
178
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.
 Plus d'infos  


2017-09-25Message-Passing Algorithms for the Verification of Distributed Protocols
14:00-15:00
178
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.
 Plus d'infos  


2017-06-26 Exploration de graphes par des robots amnésiques
14:00-15:00
178
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.
 Plus d'infos  


2017-06-19Jointure en Map-Reduce
14:00-15:00
178
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.
 Plus d'infos  


2017-06-13Orientation de graphes dans un environnement asynchrone et avec pannes
14:00-15:00
178
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
 Plus d'infos  


2017-05-22Jointure en Map-Reduce
14:00-15:00
178
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.
 Plus d'infos  


2017-04-10Robustness in Highly Dynamic Networks
14:00-15:00
178
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.
 Plus d'infos  


2017-04-03Modelling Distributed Computing Task Computability with Dynamic Epistemic Logic
14:00-15:00
178
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.
 Plus d'infos  


2017-03-27 Bamboo Garden Trimming Problem
14:00-15:00
178
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.
 Plus d'infos  


2017-03-20Self-Stabilizing Disconnected Components Detection and Rooted Shortest-Path Tree Maintenance in Polynomial Steps
14:00-15:00
178
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
max^3 n), where
maxi is the maximum weight of an edge,
max 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
max+D, where D is the hop-diameter of V_r.
 Plus d'infos  


2017-03-13On the Space Complexity of Conflict Detector Objects and Related Objects
14:00-15:00
178
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
 Plus d'infos  


2017-03-06L’agrégation de données dans les graphes dynamiques
14:00-15:00
178
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.
 Plus d'infos  


2017-02-27Stratégies d’assignation basées sur des couplages pour améliorer la localité dans les opérations de type Map/Reduce
14:00-15:00
178
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.
 Plus d'infos  


2017-02-13Calculer les plus court chemins, toujours et encore
14:00-15:00
178
Je ferai une brève présentation de techniques utilisées actuellement pour calculer les plus courts chemins dans les réseaux routiers de grande taille de plusieurs millions d'arêtes. Je propose ensuite de discuter des opportunités de collaboration avec Mappy.
 Plus d'infos  


2017-02-06Petite école du distribué : Analyse des algorithmes distribués probabilistes 3
14:00-15:00
178
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).
 Plus d'infos  


2017-01-30: Petite école du distribué : Analyse des algorithmes distribués probabilistes 2
14:00-15:00
178
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).
 Plus d'infos  


2017-01-23Petite école du distribué : Analyse des algorithmes distribués probabilistes 1
14:00-15:00
178
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).
 Plus d'infos  


2016-11-21Le modèle LOCAL et la coloration de graphes (suite et fin)
14:00-15:00
178
Cours dans le cadre d'une petite école du distribué. Suite de la Seconde partie.

Plan :
- Coloration rapide des cycles
- Borne inférieure en log* sur la coloration des cycles
- Etat de l'art
 Plus d'infos  


2016-11-14Le modèle LOCAL et la coloration de graphes (2/2)
14:00-15:00
178
Cours dans le cadre d'une petite école du distribué. Seconde partie.

Plan :
- Coloration rapide des cycles
- Borne inférieure en log* sur la coloration des cycles
- Etat de l'art
 Plus d'infos  


2016-11-07Le modèle LOCAL et la coloration de graphes (1/2)
14:00-15:00
178
Cours dans le cadre d'une petite école du distribué.

Plan:
- 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
 Plus d'infos  


2016-10-17Anonymity-Preserving Failure Detectors
14:00-15:00
178
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 in-
cremented, and (2) if two or more processes are non-faulty, it eventually
stabilizes.

Joint work with Zohir Bouzid
 Plus d'infos  


2016-10-10Calcul de chemins dans les réseaux multicouches : une approche par la théorie des langages
14:00-15:00
178
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.
 Plus d'infos  


2016-10-03An overview of discharging methods
14:00-15:00
178
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.
 Plus d'infos  


2016-06-20 Gabriel Triangulations and Angle-Monotone Graphs: Local Routing and Recognition
14:00-15:00
178
A geometric graph is angle-monotone if every pair of vertices has a path between them that---after some rotation---is x- and y-monotone.
Angle-monotone graphs are $sqrt 2$-spanners and they are increasing hyp chord graphs.
Dehkordi, Frati, and Gudmundsson introduced angle-monotone graphs in 2014 and proved that Gabriel triangulations are anglehyp monotone graphs.
We give a polynomial time algorithm to recognize angle-monotone geometric graphs.
We prove that every point set has a plane geometric graph that is generalized angle-monotone --specifically, we prove that the hts is generalized angle-monotone.
We give a local routing algorithm for Gabriel triangulations that finds a path from any vertex s to any vertex t whose length is within $1 + sqrt 2$ times the Euclidean distance from s to t.
Finally, we prove some lower bounds and limits on local routing algorithms on Gabriel triangulations.
 Plus d'infos  


2016-05-30Randomized Distributed MIS and Colouring Algorithms for Rings with Oriented Edges in O(sqrt{log n}) bit rounds
14:00-15:00
178
We present and analyse Las Vegas distributed algorithms which compute a MIS or a colouring for anonymous rings with an arbitrary orientation of the edges; their bit complexity and time complexity are O(sqrt{log n}) with high probability. These algorithms are optimal modulo a multiplicative constant.

Joint work with Yves Métivier and Mike Robson
 Plus d'infos  


2016-05-09Majority population protocols
14:00-15:00
178
We start with the review of literature on majority population protocols. In the considered problem a large group of simple asynchronous entities, each associated with one of the two basic colours, is asked to decide which colour is attributed to the majority. Later we present some extensions of such protocols to different models and tasks. We also show how to amend majority protocols to report equality if neither of the original colours dominates the other in the population. Finally we consider populations with elevated diversity (with larger number of colours) and provide space efficient solutions to the absolute and relative majority problems.
 Plus d'infos  


2016-05-02A General Framework for Reusing Proofs of Termination Detection by Refinement-Based Compositions
14:00-15:00
178
We propose a formal framework enhancing the termination detection property of distributed algorithms and reusing their specifications as well as their proofs. By relying on refinement and composition, we show that an algorithm specified with local termination detection, can be reused in order to compute the same algorithm with global termination detection. The main idea relies upon the development of distributed algorithms following a top/down approach and the integration of additional computation steps developed in a pre-defined module. This module is specified in a generic and scalable way in order to be composed with particular developments. Once the composition link is proven, the global termination emerges automatically. This work is done within the DAMPAS project.
 Plus d'infos  


2016-04-25A Faster Counting Protocol for Anonymous Dynamic Networks
14:00-15:00
178
We study the problem of counting the number of nodes in a slotted-time communication network, under the challenging assumption that nodes do not have identifiers and the network topology changes frequently. That is, for each time slot links among nodes can change arbitrarily provided that the network is always connected. This network model has been motivated by the ongoing development of new communication technologies that en- able the deployment of a massive number of devices with highly dynamic connectivity patterns. Tolerating dynamic topologies is clearly crucial in face of mobility and unreliable communication. Current communication networks do have node identifiers though. Nevertheless, even if identifiers may be still available in future massive networks, it might be convenient to ignore them if neighboring nodes change all the time. Consequently, knowing what is the cost of anonymity is of paramount importance to understand what is feasible or not for future generations of Dynamic Networks.

Counting is a fundamental task in distributed computing since knowing the size of the system often facilitates the desing of solutions for more complex problems. Also, the size of the system is usually used to decide termination in distributed algorithms. Currently, the best upper bound proved on the running time to compute the exact network size is double-exponential. However, only linear complexity lower bounds are known, leaving open the question of whether efficient Counting protocols for Anonymous Dynamic Networks exist or not.

In this paper we make a significant step towards answering this question by presenting a distributed Counting protocol for Anonymous Dynamic Networks which has exponential time complexity. Our algorithm ensures that eventually every node knows the exact size of the system and stops executing the algorithm. Previous Counting protocols have either double-exponential time complexity, or they are exponential but do not terminate, or terminate but do not provide running-time guarantees, or guarantee only an exponential upper bound on the network size. Other protocols are heuristic and do not guarantee the correct count.

Joint work with Miguel Mosteiro,
 Plus d'infos  


2016-04-11Jeux sur les graphes
14:00-15:00
178
Nous présentons deux jeux sur les graphes, le jeu de coloration et le jeu de poursuite, ainsi que les principales stratégies utilisées pour l'étude de ces jeux. Le premier est une version à deux joueurs du problème de coloration de graphes, l'autre est un jeu de type "gendarmes et voleur" sur les sommets d'un graphe. Nous discutons enfin des variantes distribuées de ces jeux et des possibilités d'étude qu'elles offrent.
 Plus d'infos  


2016-04-04Le point de vue ... II
14:00-15:00
178
Le point de vue théorie de l'information et aléatoire sur l'élection de leader -- seconde partie (d'après Beauquier, Blanchard, Burman et Guerraoui)

Dans un papier récent, Beauquier et al. décrivent des conditions sur l'ordonnancement d'un système distribué (totalement asynchrone), de type théorie de l'information et aléa algorithmique ("algorithmic randomness"), qui permettent d'assurer que tel ou tel problème peut être résolu pour *tout* ordonnancement respectant ces conditions. Les conditions sont du type "la séquence d'actions est T-aléatoire", ce qui signifie qu'un programme générant un n-préfixe de la séquence doit être de taille au moins T.n (le cas T=1 correspond à une séquence aléatoire au sens de Kolmogorov). En particulier, ils montrent que lorsque T=1 est suffisant pour résoudre un problème, il n'est jamais nécessaire - il existe toujours une constante T'<1 qui suffit.

Je n'ai aucun résultat original sur le sujet; je me contenterai de présenter ce que j'en ai compris.

Il s'agit de la suite de l'exposé du 29 février.
 Plus d'infos  


2016-03-21Deterministic Leader Election in O(D+log n) Rounds with Messages of size O(1)
14:00-15:00
178
We present a distributed algorithm for electing deterministically
a leader in a general network where each processor has a unique
identifier of size O(log n) (n is the number of nodes in the
network). It elects a leader in O(D+log n) rounds (D is the
diameter of the network) with messages of size O(1), thus it has
a bit complexity of O(D+log n). This improves the best known
algorithm whose bit complexity is O(Dlog n).
In fact, using a lower bound by Kutten et al. and a result of
Dinitz and Solomon, we show that the bit complexity of our algorithm
is optimal (up to a multiplicative constant). Furthermore, this
algorithm requires no knowledge on the graph, such as n or D.

(Travail en collaboration avec A. Casteigts, J. M. Robson et A. Zemmari)
 Plus d'infos  


2016-03-14Time and Homonyms Considerations over Community Protocols
14:00-15:00
178
Guerraoui and Ruppert introduced the model of Community Protocols. This Distributed System works with agents having a finite memory and unique identifiers (the set of identifiers being ordered). Each agent can store a finite number of identifiers they heard about. The interactions are asynchronous and pairwise, following a fair scheduler. The computation power of this model is fully characterized: it corresponds exactly to what non deterministic Turing Machines can compute on a space O(nlog n). In this talk, I will focus on two restrictions of the model: The first is what happens when agents may share identifiers, the population admitting homonyms. I will introduce a hierarchy, with characterizations depending on the rate of unique identifiers present in the population. The main result is that with log n identifiers, a Turing Machine with a polylogarithmic space can be simulated. The second consider the following time restriction: what can be computed in a polylogarithmic number of parallel interactions. This version is not yet characterized, but I will provide some impossibility results, some computable protocols, and I will give the tighter bound we found.
 Plus d'infos  


2016-03-07Time vs. Information Tradeoffs for Leader Election in Anonymous Trees
14:00-15:00
178
Dans cette présentation je donnerai des résultats concernant l'élection de leader dans des arbres anonymes.

Dans le modèle utilisé, l'ensemble des nœuds doivent produire en sortie un chemin simple vers l'un d'entre eux, ce dernier sera alors qualifié de leader. Le cas particulier étudié est celui de l'élection lorsque le temps alloué est inférieur au diamètre de l'arbre considéré.

Si aucune information supplémentaire n'est accessible, les nœuds ne pouvant pas avoir une vision complète du réseau, l'élection est impossible et ce quel que soit l'algorithme utilisé. L'étude proposée concerne donc le compromis entre la quantité d'information initialement requise par les nœuds et le temps leur étant alloué pour réaliser l'élection. Le modèle utilisé est celui des algorithmes avec conseil dans lequel un oracle ayant une connaissance complète du réseau, fournit un conseil unique sous forme d'une chaîne binaire, à l'ensemble des nœuds avant que ceux-ci n'initient leurs calculs.

Pour la majorité des valeurs de temps nos bornes inférieures et supérieures sont proches à un facteur multiplicatif près, ou diffèrent seulement d'un facteur logarithmique. Je présenterai le détail des résultats ainsi que les outils utilisés pour l'établissement de deux bornes me paraissant représentatives de cette étude.
 Plus d'infos  


2016-02-29Le point de vue
14:00-15:00
178
Dans un papier récent, Beauquier et al. décrivent des conditions sur l'ordonnancement d'un système distribué (totalement asynchrone), de type théorie de l'information et aléa algorithmique ("algorithmic randomness"), qui permettent d'assurer que tel ou tel problème peut être résolu pour *tout* ordonnancement respectant ces conditions. Les conditions sont du type "la séquence d'actions est T-aléatoire", ce qui signifie qu'un programme générant un n-préfixe de la séquence doit être de taille au moins T.n (le cas T=1 correspond à une séquence aléatoire au sens de Kolmogorov). En particulier, ils montrent que lorsque T=1 est suffisant pour résoudre un problème, il n'est jamais nécessaire - il existe toujours une constante T'<1 qui suffit.

Je n'ai aucun résultat original sur le sujet; je me contenterai de présenter ce que j'en ai compris.
 Plus d'infos  


2016-02-15k-Set Agreement with n ? k + 1 Atomic Read/Write Registers
14:00-15:00
178
The k-set agreement problem is a generalization of the consensus problem. Namely, assuming that each process proposes a value, every non-faulty process should decide one of the proposed values, and no more than k different values should be decided. This is a hard problem in the sense that we cannot solve it in an asynchronous system, as soon as k or more processes may crash. One way to sidestep this impossibility result consists in weakening the termination property, requiring that a process must decide a value only if it executes alone during a long enough period of time.

This is the well-known obstruction-freedom progress condition.

Consider a system of n anonymous asynchronous processes that communicate through atomic read/write registers, and such that any number of them may crash. In this paper, we address and solve the challenging open problem of designing an obstruction-free k-set agreement algorithm using only (n ? k + 1) atomic registers. From a shared memory cost point of view, our algorithm is the best algorithm known so far, thereby establishing a new upper bound on the number of registers needed to solve the problem, and in comparison to the previous upper bound, its gain is (n?k) registers.

Joint work with M. Raynal and P. Sutra
 Plus d'infos  


2016-02-08Impact de la réplication pour les bases de données distribuées
14:00-15:00
178
Les bases de données distribuées, massivement utilisées dans le contexte actuel du Big Data, doivent traiter de très grande quantité de requêtes sur les données qu'elles stockent. Une des problématique majeure est donc de minimiser le temps de traitement de ces requêtes. La réplication de données est classiquement utilisée à des fins de robustesse mais rarement pour la performance. Nous proposons un algorithme de gestion de copies qui va adapter le nombre de répliquas de chaque donnée afin de mieux répartir la charge des requêtes entre les différents noeuds stockant ces copies. Nous présentons une évaluation expérimentale de notre algorithme pour la base de données distribuée Apache Cassandra. Nous comparons notamment différents algorithmes d'affectation de requêtes et montrons le gain réel sur le temps de complétion grâce à notre gestion de copies.

Travail en commun avec Nicolas Hanusse et Frédéric Lalanne
 Plus d'infos  


2016-02-01Incentives in distributed systems
14:00-15:00
178
In this talk I will give an overview of the role of "incentives" in distributed systems, and how game-theoretic considerations can be used for the analysis of a (distributed) protocol. Roughly speaking, the "participants" of the protocol may deviate from the prescribed "actions" whenever this is convenient for themselves (possibly creating trouble to the overall system).

I will present several applications and examples showing how much incentives can affect the "system performance" and how to cope with that. Along the way, I will discuss how certain "classical" approaches and methods in game theory underly some assumption on distributed system (e.g., synchronization, use of randomness, etc.) and highlight some open questions in this field.
 Plus d'infos  


2016-01-25 Pré-calcul distribué pour la visualisation interactive de densité pour de grands nuages de points
14:00-15:00
178
Arriver à naviguer en temps réel dans des cartes représentant des milliards de points nécessite de faire des pré-calcul de structures de données distribués. Nous montrerons dans cet exposé un algorithme de calcul distribué d'aggrégation de valeurs ainsi que son implémentation dans un environnement Hadoop dans le cadre d'un système de visualisation pour l'exploration de cartes de chaleur.
 Plus d'infos  


2016-01-18The read/write protocol complex is collapsible
14:00-15:00
178
The celebrated asynchronous computability theorem provides a characterization of the class of decision tasks that can be solved in a wait-free manner by asynchronous processes that communicate by writing and taking atomic snapshots of a shared memory. Several variations of the model have been proposed (immediate snapshots and iterated immediate snapshots), all equivalent for wait-free solution of decision tasks, in spite of the fact that the protocol complexes that arise from the different models are structurally distinct. The topological and combinatorial properties of these snapshot protocol complexes have been studied in detail, providing explanations for why the asynchronous computability theorem holds in all the models.

In reality concurrent systems do not provide processes with snapshot operations. Instead, snapshots are implemented (by a wait-free protocol) using operations that write and read individual shared memory locations.

Thus, read/write protocols are also computationally equivalent to snapshot protocols. However, the structure of the read/write protocol complex has not been studied. In this paper we show that the read/write iterated protocol complex is collapsible (and hence contractible). Furthermore, we show that a distributed protocol that wait-free implements atomic snapshots in effect is performing the collapses.

This is a joint work with Sergio Rajsbaum.
 Plus d'infos  


2015-12-14 Beachcombing on Strips and Islands
14:00-15:00
178
A group of mobile robots (beachcombers) have to search collectively every point of a given domain. At any given moment, each robot can be in walking mode or in searching mode. It is assumed that each robot's maximum allowed searching speed is strictly smaller than its maximum allowed walking speed. A point of the domain is searched if at least one of the robots visits it in searching mode. The Beachcombers' Problem consists in developing efficient schedules (algorithms) for the robots which collectively search all the points of the given domain as fast as possible. In this talk, I will present recent results on this topic.
 Plus d'infos  


2015-12-07Rendezvous of Heterogeneous Mobile Agents in Edge-weighted Networks.
14:00-15:00
178
We introduce a variant of the deterministic rendezvous problem for a pair of
heterogeneous agents operating in an undirected graph, which differ in the time
they require to traverse particular edges of the graph. Each agent knows the
complete topology of the graph and the initial positions of both agents. The
agent also knows its own traversal times for all of the edges of the graph, but is
unaware of the corresponding traversal times for the other agent. The goal of the
agents is to meet on an edge or a node of the graph. In this scenario, we study the
time required by the agents to meet, compared to the meeting time T_OPT in the
offline scenario in which the agents have complete knowledge about each others
speed characteristics. When no additional assumptions are made, we show that
rendezvous in our model can be achieved after time O(n T_OPT) in a n-node graph,
and that such time is essentially in some cases the best possible. However, we
prove that the rendezvous time can be reduced to ?(T_OPT) when the agents
are allowed to exchange ?(n) bits of information at the start of the rendezvous
process. We then show that under some natural assumption about the traversal
times of edges, the hardness of the heterogeneous rendezvous problem can be
substantially decreased, both in terms of time required for rendezvous without
communication, and the communication complexity of achieving rendezvous in
time ?(T_OPT).
 Plus d'infos  


2015-11-30 Machine Learning Approach for Android Apps Analysis
14:00-15:00
salle 178
Android being the most popular open source mobile operating system, attracts a plethora of app developers. Millions of applications are developed for Android platform with a great extent of behavioral diversities and are available on Play Store as well as on many third party app stores. Due to its open nature, Android Platform has been targeted by many malware writers. The conventional way of signature-based detection methods for detecting malware on a device are no longer promising due to an exponential increase in the number of variants of the same application with different signatures. In this talk, we present a machine learning approach for malware detection in Android Apps.
 Plus d'infos  


2015-11-09 Classification automatique de graphes dynamique
14:00-15:00
75
Étant donné un graphe dynamique, donné sous la forme d’une séquence de graphes statiques ou bien comme une succession d’évènements topologiques (apparitions/disparitions de liens de communication), on s’intéresse à tester automatiquement certaines propriétés temporelles sur le graphe. Les propriétés qui nous intéressent correspondent à des conditions nécessaires et/ou suffisantes pour la réalisation de tâches distribuées classiques (élection, diffusion, comptage, etc.) Nous avons répertorié à ce jour une vingtaine de propriétés. Par exemple, le réseau est-il temporellement connexe ? (existence d’un trajet, i.e. d’une succession d’arêtes dont les dates d’existence sont temporellement croissantes, depuis chaque sommet vers chaque autre sommet) ; certaines arêtes réapparaissent-elles dans un temps borné ou de manière périodique ? Leur ensemble vérifie-t-il certaines propriétés ? Être capable de vérifier ce type de propriété automatiquement nous permettrait de déterminer dans un contexte de mobilité donné (p. ex. drones, robots, voitures, dont on peut obtenir ou générer des traces de connexité), les tâches réalisables par l’ensemble des entités
 Plus d'infos  


2015-11-02On the Uncontended Complexity of Anonymous Consensus
14:00-15:00
178
We study on uncontended complexity of anonymous algorithms, counting the number of distinct memory accesses in operations that encounter no contention. We assume that contention-free operations on a concurrent object perform “fast” reads and writes, and resort to more expensive synchronization primitives, such as CAS, only when contention is detected. We call such concurrent implementations interval-solo-fast and derive tight lower bounds on time and space complexity of anonymous interval-solo-fast consensus.
 Plus d'infos  


2015-10-19Algorithmes auto-stabilisants pour des paramètres de décomposition et de domination dans les graphes
14:00-15:00
178
Un système distribué est dit auto-stabilisant s’il peut reprendre un comportement correct en un temps fini après l’occurrence de fautes et ce sans intervention extérieure. De ce fait, l’auto-stabilisation est une approche optimiste pour la tolérance aux fautes dans le sens où elle protège le système des fautes transitoires. Un algorithme auto-stabilisant peut être défini selon différents modèles de communication ainsi que différents modèles de calcul. En effet, prouver la convergence d'un algorithme auto-stabilisant se doit dêtre faite selon un démon/scheduler qui peut être centralisé ou distribué, équitable ou non. De de plus, la complexité de ces algorithmes peut se calculer selon différentes mesures : moves, steps ou rounds, chacune d'entre elles apportant une connaissance propre sur l'algorithme proposé. Cependant, réussir à borner l'ensemble de ces mesures n'est pas toujours trivial, en particulier pour les cas les plus généraux de démons. La littérature des algorithmes auto-stabilisants est très riches. Cependant, nous allons nous intéresser dans cet exposé aux algorithmes auto-stabilisants pour quelques paramètres de théorie des graphes. En particulier, nous nous focaliserons dans un premier temps sur des décompositions particulières des graphes : en triangles et en étoiles uniformes ainsi que des paramètres de domination. Nous nous attarderons par la suite sur les techniques de preuve de convergence utilisées pour ces algorithmes.
 Plus d'infos  


2015-10-12On Distinguishing Views in Symmetric Networks.
14:00-15:00
178
The view of a node in a port-labeled network is an infinite tree encoding all walks in the network originating from this node. It is an important concept in the context of symmetry breaking in distributed systems. For example a deterministic rendezvous is infeasible if the agents start from positions with the same views. We want to decide if two views are identical but we would like to compare the infinite trees truncated to certain depth d. We are looking for such d that if the views truncated to depth d are equal then the whole infinite trees are also equal and there are some nodes whose views differ only at depth d. It turns out that truncating to depth Theta(D*log(n/D)) (where D is the diameter and n is the number of nodes) is always sufficient and sometimes necessary to distinguish the views.

The talk will be based on two papers:

Views in a graph: to which depth must equality be checked?
Julien M. Hendrickx

Distinguishing Views in Symmetric Networks: A Tight Lower Bound
Dariusz Dereniowski, Adrian Kosowski, Dominik Paj?k
 Plus d'infos  


2015-10-05 Silent Self-stabilizing BFS Tree Algorithms Revised
14:00-15:00
Amphi
Analysis of two fundamental results of the self-stabilizing literature about silent BFS spanning tree constructions: the Dolev et al algorithm and the Huang and Chen's algorithm. More precisely, we propose in the composite atomicity model three straightforward adaptations inspired from those algorithms. We then present a deep study of these three algorithms. Our results are related to both correctness (convergence and closure, assuming a distributed unfair daemon) and complexity (analysis of the stabilization time in terms of rounds and steps).
(joint work with with Stéphane Devismes - VERIMAG)

Exceptionnellement, l'exposé aura lieu dans l'amphi du LaBRIelement, l'exposé aura lieu dans l'amphi du LaBRI
 Plus d'infos  


2015-09-28 JBotSim: a tool for fast prototyping distributed algorithms in dynamic networks. Part
14:00-15:00
178
JBotSim is a java library that offers basic primitives for prototyping, running, and visualizing distributed algorithms in dynamic networks. With JBotSim, one can implement an idea in minutes and interact with it (e.g., add, move, or delete nodes) while it is running. JBotSim is well suited to prepare live demonstrations of your algorithms to colleagues or students; it can also be used to evaluate performance at the algorithmic level, i.e. in terms of the number of messages, number of rounds. Unlike most tools (OMnet, The One, Visidia), JBotSim is not an integrated environment. It is a lightweight *library* to be used in your program. In this talk, I will give an overview of its distinctive features and architecture, as well as many examples of algorithms and scenarios. This talk will also be the occasion to discuss recent hot topics in distributed computing, which are swarm algorithms and intelligence.

Suite de l'exposé du 18 mai. Il y aura des rappels pour ceux qui n'ont pas assisté à la première partie.
 Plus d'infos  


2015-06-29Spreading Influence in Social Networks with Time Constraints
14:00-15:00
178
In a social network, agents change their behaviours and opinions on the basis of information collected from their neighbours. Generally, recent information is more influential than older information, and information that is received in a short period of time is more influential than information received during a long period of time. An example of this phenomenon is consumer reviews on websites such as Amazon. Another example is viral marketing which attempts to influence consumer adoption of products. A third example is recent communication strategies of politicians.

In this talk, I will present a graph-based model of the spread of influence in networks that generalizes previous research by including temporal information. The goal is to identify a small set of nodes that eventually influences all nodes in the graph with the restriction that influence only lasts for a bounded time interval. The problem for general graphs is computationally difficult even for approximate solutions. The talk will focus on efficient algorithms for restricted families of graphs: paths, rings, trees, and complete graphs.
 Plus d'infos  


2015-06-22Upper and Lower Bounds for Online Routing on Delaunay Triangulations
14:00-15:00
178
Consider a weighted graph G whose vertices are points in the plane and edges are line segments between pairs of points. The weight of each edge is the Euclidean distance between its two endpoints. A routing algorithm on G has a routing ratio of c if the length of the path produced by the algorithm from any vertex s to any vertex t is at most c|[st]|. The routing algorithm is online if it makes forwarding decisions based on 1) the k-neighborhood in G (for some integer constant k > 0) of the current position of the message and 2) limited information stored in the message header.

We present an online routing algorithm on the Delaunay triangulation with routing ratio less than 5.90. This improves upon the algorithm with best known routing ratio of 15.48. We also show that the routing ratios of any deterministic k-local algorithm is at least 1.70 for the Delaunay triangulation.
 Plus d'infos  


2015-06-15 Station Assignment with Reallocation
14:00-15:00
178
In this work, we studied a dynamic allocation problem that arises in various scenarios where mobile clients joining and leaving the system have to communicate with static stations via radio transmissions. Restrictions are a maximum delay, or laxity, between consecutive client transmissions and a maximum bandwidth that a station can share among its clients. We studied the problem of assigning clients to stations so that every client transmits to some station, satisfying those restrictions. We considered reallocation algorithms, where clients are revealed at its arrival time, the departure time is unknown until they leave, and clients may be reallocated to another station, but at a cost proportional to the reciprocal of the client’s laxity. I will present positive and negative results as well as the results of our simulations showing that our protocols behave even better than our theoretical guarantees.

This is joint work with Yulia Rossikova and Prudence W. H. Wong, and will be presented at SEA 2015.
 Plus d'infos  


2015-06-08Proving correctness of distributed algorithms in a dynamic context
14:00-15:00
178
Proving the correctness of distributed algorithms is a hard task due to the lack of global state knowledge and the non-determinism in the processes execution. In dynamic networks, this task becomes more difficult because of dynamic behavior and time complexity. In this talk, we propose a reuse based approach for specifying and proving distributed algorithms in dynamic networks. It consists in developing a formal pattern using Event-B method, based on refinement technique. Our pattern allows to handle topological events in dynamic networks and to characterize the concept of time. The proposed solution relies on evolving graphs, as a powerful model to record the evolution of a network topology. To illustrate it, we investigate an example of a distributed algorithm encoded by local computations models.
 Plus d'infos  


2015-06-01 An overview of computational models for wireless sensor networks
14:00-15:00
178
In this talk, we will give an overview of some computational models designed for networks of tiny artifacts with sensing capabilities and with limited resources.
We will focus on the population protocols (PP) model of Angluin et al. which is based on pairwise interactions between anonymous passively mobile finite state agents. We will consider, among other examples, the PP that stably computes the OR predicate and that we applied to the broadcast problem.
We will also consider works that extend the PP model such as the mediated population protocols.
In all these models, the interacting pairs are supposed to be chosen by a fair scheduler. In this talk, we will present a new fair one based on the rendezvous algorithm.
 Plus d'infos  


2015-05-18JBotSim: a tool for fast prototyping distributed algorithms in dynamic networks
14:00-15:00
178
JBotSim is a java library that offers basic primitives for prototyping, running, and visualizing distributed algorithms in dynamic networks. With JBotSim, one can implement an idea in minutes and interact with it (e.g., add, move, or delete nodes) while it is running. JBotSim is well suited to prepare live demonstrations of your algorithms to colleagues or students; it can also be used to evaluate performance at the algorithmic level, i.e. in terms of the number of messages, number of rounds. Unlike most tools (OMnet, The One, Visidia), JBotSim is not an integrated environment. It is a lightweight *library* to be used in your program. In this talk, I will give an overview of its distinctive features and architecture, as well as many examples of algorithms and scenarios. This talk will also be the occasion to discuss recent hot topics in distributed computing, which are swarm algorithms and intelligence.
 Plus d'infos  


2015-05-11Calculer les distances dans un graphe en temps constant avec des étiquettes de 0.793n bits
14:00-15:00
178
Dans cet exposé je présenterai une structure de données compacte permettant de calculer en temps constant la distance entre n'importe quelle paire de sommets d'un graphe arbitraire à n sommets. Cette structure de données se présente sous forme d'étiquette associée à chacun des sommets, la distance entre les u et v étant décodée à partir d'un calcul impliquant seulement les étiquettes de u et de v. La solution triviale, à l'aide d'un vecteur de distances de taille n, produit des étiquettes de nlogn bits. En fait, aucune technique utilisant o(nlogn) bits et décodant en temps constant n'est connue. Cependant, si on relâche la contrainte du décodage en temps constant, des solutions avec O(n) bits existent. Une des meilleures d'entres elles utilisent 11n bits pour un décodage O(logn). Notre solution réduit la taille des étiquettes à 0.793n bits avec un décodage constant et s'étend naturellement aux graphes valués.
 Plus d'infos  


2015-04-20 Extension du domaine algorithmique : les algorithmes de la nature
14:00-15:00
178
Suite aux travaux de A.M.Turing, les algorithmes ont été vus comme l’abstraction à partir de laquelle on pouvait écrire des programmes pour des ordinateurs dont le principe était lui-même issu du concept théorique de machine de Turing.

Nous partons ici du constat que les les algorithmes de la nature, massivement parallèles, autoadaptatifs et auto reproductibles, dont on ne sait pas comment ils fonctionnent réellement, ni pourquoi, ne sont pas aisément spécifiés par le modèle théorique actuel de Machine de Turing Universelle, ou de Calculateur Universel ; en particulier les aspects de communications, de règles évolutives, d’événements aléatoires, à l’image du code génétique, ne sont pris en compte que par ajout d’artifices à la théorie. Nous nous proposons ici de montrer comment aborder ces problèmes en repensant le modèle théorique. Nous proposerons un modèle d’algorithme, appelé ici machine-? qui contient et généralise les modèles existants.
 Plus d'infos  


2015-04-13Verifying parametrized asynchronous systems
14:00-15:00
178
The talk should be a (gentle) introduction to verification problems for concurrent, asynchronous systems. I will focus on two models (among a large number!), one with shared memory and another one with asynchronous calls. The talk is based on the following papers:
- Parameterized Verification of Asynchronous Shared-Memory Systems Javier Esparza, Pierre Ganty, and Rupak Majumdar CAV 2013
- Safety of parametrized asynchronous shared-memory systems is almost always decidable S. La Torre, A. Muscholl, I. Walukiewicz 2015
- Algorithmic Verification of Asynchronous Programs Pierre Ganty, and Rupak Majumdar ACM Transactions on Programming Languages and Systems 2012
 Plus d'infos  


2015-03-30 An introduction to Software Transactional Memory
14:00-15:00
178
Software Transactional memory (or STM for short) is a promising programming paradigm that aims at simplifying concurrent programming by using the notion of a transaction. A transaction executes a piece of code containing accesses to data items which are shared by several processes in a concurrent setting. By using transactions, the programmer needs only enhance its sequential code with invocations of special operations to read or write data items. It is guaranteed that if any operation of a transaction takes place, they all do, and that if they do, they appear to other threads to do so atomically, as one indivisible operation.

In this talk, I will present the STM paradigm and the main algorithmic techniques to implement it.
 Plus d'infos  


2015-03-23 Algorithmes d'allocation pour le Cloud sous contrainte de fiabilité
14:00-15:00
178
Pour les services qui s'exécutent sur une plate-forme de Cloud Computing, la fiabilité et la disponibilité sont des problématiques clés : avec l'augmentation de la taille de ces plates-formes, les pannes de machines sont de plus en plus fréquentes et doivent être prises en compte en amont. À travers une analyse de traces d'un cluster de Google, cet exposé présente une formalisation du problème d'allocation des services sur une plate-forme de façon à pouvoir résister aux pannes, ainsi qu'un algorithme de résolution basée sur deux techniques : approximation binomiale et génération de colonnes. Travail en commun avec Olivier Beaumont, Paul Renaud-Goud, et Juan-Angel Lorenzo.
 Plus d'infos  


2015-03-16On Distributed Computing with Beeps , Part II
14:00-15:00
178
We consider networks of processes which interact with beeps. Various beeping models are used. The basic one, defined by Cornejo and Khun assumes that a process can choose either to beep or to listen. If it listens it can distinguish between silence or the presence of at least one beep. The aim of this paper is the study of the resolution of paradigms such as collision detection, computation of the degree of a vertex, of a MIS or a colouring in the framework of beeping models. Join work with Yves Métivier and Mike Robson

Suite de l'exposé du 2 mars.
 Plus d'infos  


2015-03-02On Distributed Computing with Beeps
14:00-15:00
178
We consider networks of processes which interact with beeps. Various beeping models are used. The basic one, defined by Cornejo and Khun assumes that a process can choose either to beep or to listen. If it listens it can distinguish between silence or the presence of at least one beep. The aim of this paper is the study of the resolution of paradigms such as collision detection, computation of the degree of a vertex, of a MIS or a colouring in the framework of beeping models.

Join work with Yves Métivier and Mike Robson
 Plus d'infos  


2015-02-16Self-Stabilizing Leader Election in Polynomial Steps
14:00-15:00
178
We present a silent self-stabilizing leader election algorithm for bidirectional connected identified networks of arbitrary topology. This algorithm is written in the locally shared memory model. It assumes the distributed unfair daemon, the most general scheduling hypothesis of the model. Our algorithm requires no global knowledge on the network (such as an upper bound on the diameter or the number of processes, for example).

We show that its stabilization time is in Theta(n^3) steps in the worst case, where n is the number of processes. Its memory requirement is asymptotically optimal, i.e., Theta(log n) bits per processes. Its round complexity is of the same order of magnitude (i.e., Theta(n) rounds), as the best existing algorithm (proposed by Datta et al) designed with similar settings,i.e., it does not use global knowledge and is proven under the unfair daemon).

To the best of our knowledge, this is the first asynchronous self-stabilizing leader election algorithm for arbitrary identified networks that is proven to achieve a stabilization time polynomial in steps. By contrast, we show that the previous best existing algorithm designed with similar settings stabilizes in a non polynomial number of steps in the worst case.

This talk and Stephane's visit is supported by CPU.
 Plus d'infos  


2015-02-09A Distributed Enumeration Algorithm and Applications to All Pairs Shortest Paths, Diameter...
14:00-15:00
178
We consider the standard message passing model; we assume the system is fully synchronous: all processes start at the same time and time proceeds in synchronised rounds. In each round each vertex can transmit a different message of size $O(1)$ to each of its neighbours. This paper proposes and analyses a distributed enumeration algorithm of vertices of a graph having a distinguished vertex which satisfies that two vertices with consecutive numbers are at distance at most $3$. We prove that its time complexity is $O(n)$ where $n$ is the number of vertices of the graph. Furthermore, the size of each message is $O(1)$ thus its bit complexity is also $O(n).$ We provide some links between this enumeration and Hamiltonian graphs from which we deduce that this enumeration is optimal in the sense that there does not exist an enumeration which satisfies that two vertices with consecutive numbers are at distance at most $2$.

We deduce from this enumeration algorithms which compute all pairs shortest paths and the diameter with a time complexity and a bit complexity equal to $O(n)$. This improves the best known distributed algorithms (under the same hypotheses) for computing all pairs shortest paths or the diameter presented in cite{PRT12,HW12} having a time complexity equal to $O(n)$ and which use messages of size $O(log n)$ bits.

Join work with Mike Robson and Akka Zemmari
 Plus d'infos  


2015-01-26Periodic Data Retrieval in asynchronous rings with a malicious host
14:00-15:00
178
The notion of "black hole" has been used extensively in the mobile agent literature to model a crashed node which kills incoming agents without leaving any trace of them. I will consider more powerful models of faulty (or malicious) hosts in the context of the Periodic Data Retrieval problem in asynchronous ring networks. The problem is to collect infinite streams of data generated at the nodes of the network and report them infinitely often to a prescribed safe node (the homebase). I will discuss lower and upper bounds on the optimal number of agents required to perform the task in the presence of a unique malicious host.

(joint work with Nikos Leonardos, Euripides Markou, Aris Pagourtzis, and Matoula Petrolia)
 Plus d'infos  


2015-01-19 Équilibrage de charge dans des systèmes distribués
14:00-15:00
178
L'expansion, au cours des deux dernières décennies des réseaux, et notamment d'Internet, a engendré une création importante de données, massives de par leur nombre et leur taille. De ce fait, des systèmes de stockages distribués (comme Cassandra par exemple) sont utilisés en pratique afin de stocker ces données.

Deux problématiques se posent alors : (1) comment répartir les données? (2) comment optimiser le traitement des requêtes sur ces données?

Nous nous intéressons ici à l'équilibrage des requêtes entre les différents noeuds d'un système distribué. Notre approche consiste à utiliser la réplication d'objet et nous proposons différents algorithmes d'affectation des requêtes en cherchant à optimiser le temps de complétion (temps de traitement) des requêtes.
 Plus d'infos  


2015-01-12 Distributedly Testing Cycle-Freeness
14:00-15:00
178
We tackle emph{local distributed testing} of graph properties. This framework is well suited to contexts in which data dispersed among the nodes of a network can be collected by some central authority (like in, e.g., sensor networks). In local distributed testing, each node can provide the central authority with just a few information about what it perceives from its neighboring environment, and, based on the collected information, the central authority is aiming at deciding whether or not the network satisfies some property.
We analyze in depth the prominent example of checking emph{cycle-freeness}, and establish tight bounds on the amount of information to be transferred by each node to the central authority for deciding cycle-freeness. In particular, we show that distributedly testing cycle-freeness requires at least $ceil{log d}-1$ bits of information per node in graphs with maximum degree~$d$, even for connected graphs.
Our proof is based on a novel version of the seminal result by Naor and Stockmeyer (1995) enabling to reduce the study of certain kinds of algorithms to order-invariant algorithms, and on an appropriate use of the known fact that every free group can be linearly ordered.
 Plus d'infos  


2014-12-15Splitting and renaming with a majority of faulty processes
14:00-15:00
178
The renaming problem has been introduced by Attiya et al. [1], and consists on the following : Each process start with a unique name in a large namespace (such as an IP address), and each process tries to acquire a new name such as, at the end of the algorithm, each process has a new unique name in a much smaller namespace. This problem was first solved in asynchronous message-passing systems with a strict minority of processes that might crash, and later largely studied in wait-free shared memory systems, which can themselves be simulated in the former model (as explained in [2]). Splitters are basic shared memory objects that were introduced in [3] in order to build a fast renaming algorithm, and extending the renaming to a ``long-lived'' version. A splitter is an object that can be accessed through one operation Split(), and returns a direction in {right, down, stop}, with the property that not all processes return right, not all return down, and at most 1 process may return stop.
In asynchronous message-passing systems with a majority of faulty processes, the renaming problem cannot be solved, and splitters cannot be implemented. But we extended these notions to k-renaming and k-splitters, both for one-shot and long-lived versions. Instead of having unique name for each process, each new name (in a small namespace) may be acquired by at most k processes, and at most k processes accessing a k-splitter may return stop. We developed an optimal algorithm for implementing k-splitters, i.e. the algorithm implements them with k = floor(n/(n-f)), where n in the number of processes and f the maximal number of faulty processes among them, and it is not possible to implement k'-splitters with k' < floor(n/(n-f)). Although the namespace is not optimal, especially in the long-lived version, k-renaming based on these k-splitters is optimal for the same reason that k=floor(n/(n-f)) is both a lower bound, and a reached upper bound.
[1] H. Attiya, A. Bar-Noy, D. Dolev, D. Peleg, and R. Reischuk. Renaming in an asynchronous environment. J. ACM, 37(3):524–548, July 1990. [2] H. Attiya, A. Bar-Noy, and D. Dolev. Sharing memory robustly in message-passing systems. J. ACM, 42(1):124–142, 1995. [3] M. Moir and J. H. Anderson. Wait-free algorithms for fast, long-lived renaming. Science of Computer Programming, 25(1):1 – 39, 1995.
 Plus d'infos  


2014-12-08Maintaining a Spanning Forest in Highly Dynamic Networks: The Synchronous Case
14:00-15:00
178
Highly dynamic networks are characterized by frequent changes in the availability of communication links. Many of these networks are in general partitioned into several components that keep splitting and merging continuously and unpredictably. We present an algorithm that strives to maintain a forest of spanning trees in such networks, without any kind of assumption on the rate of changes. Our algorithm is the adaptation of a coarse-grain interaction algorithm (Casteigts et al., 2013) to the synchronous message passing model (for dynamic networks). While the high-level principles of the coarse-grain variant are preserved, the new algorithm turns out to be significantly more complex. In particular,
it involves a new technique that consists of maintaining a distributed permutation of the set of all nodes IDs throughout the execution. The algorithm also inherits the properties of its original variant: It relies on purely localized decisions, for which no global information is ever collected at the nodes, and yet it maintains a number of critical properties whatever the frequency and scale of the changes. In particular, the network remains always covered by a spanning forest in which 1) no cycle can ever appear, 2) every node belongs to a tree, and 3) after an arbitrary number of edge disappearance, all maximal subtrees immediately restore exactly one token (at their root). These properties are ensured whatever the dynamics, even if it keeps going for an arbitrary long period of time. Optimality is not the focus here, however the number of tree per components – the metric of interest here – eventually converges to one if the network stops changing (which is never expected to happen, though). The algorithm correctness is proven and its behavior is tested through experimentation.
 Plus d'infos  


2014-12-01Towards a General Framework for Searching on a Line and Searching on m Rays
14:00-15:00
178
We revisit the problem of searching for a target at an unknown location on a line when given upper and lower bounds on the distance D that separates the initial position of the searcher from the target. We present tight bounds on the exact optimal competitive ratio achievable, parameterized in terms of the given range for D, along with an optimal search strategy that achieves this competitive ratio.
We present an optimal search strategy for the case where a fixed turn cost t is charged every time the searcher changes direction. Moreover, we generalize our results to the framework where the cost of moving distance x away from the origin is a x + b and the cost of moving distance y towards the origin is c y + d for constants a, b, c and d.
This is joint work with Prosenjit Bose (Carleton U.) and Stephane Durocher (U. of Manitoba).
 Plus d'infos  


2014-11-24On the power of one bit: How to explore a graph when you cannot backtrack?
14:00-15:00
178
We study the problem of exploration of an anonymous undirected graph with n vertices, m edges and diameter D by a single mobile agent. The agent does not know the incoming port when entering to a vertex thus it cannot backtrack its moves. Each vertex of the graph is endowed with a whiteboard on which the agent can store information.

In this talk we will study tradeoffs between the exploration time and the existence of the internal memory available to the agent. We will first show an algorithm for an agent with 1 bit of memory completing exploration of any graph with stop in time O(m) using whiteboards of size O(log Delta) on each vertex with degree Delta.

An oblivious agent (with no internal memory) can explore any graph in time O(m D) using whiteboards of size O(log Delta) by applying the rotor-router mechanism. We will show that, even with unbounded whiteboards, there is no algorithm for oblivious agents that is better than the rotor-router in the worst case by showing a Omega(n3) lower bound for a specific class of graphs. We will also observe that any oblivious agent cannot stop after completing the task. This shows separation between oblivious and non-oblivious agents in terms of the exploration time and the stop property.
 Plus d'infos  


2014-11-10Patrolling by unreliable mobile robots
14:00-15:00
178
Mobile robots collaborate in order to solve efficiently the central problems in algorithmics of distributed computing like searching/exploration, rendez-vous or pattern formation. Patrolling is a perpetual traversal of an environment by a collection of mobile robots. The standard measure of efficiency of a patrolling algorithm is defined by its idleness – the minimal time interval during which every point of the environment is always visited by at least one robot. Boundary patrolling and fence patrolling were fundamental problems investigated by the robotics community in the last decade.

We sketch briefly previous results concerning the algorithms for the boundary and fence-patrolling problem. When some (unknown) robots of the collection cannot perform their duties, the fence patrolling algorithms become surprisingly unnatural. In more details we discuss a new algorithm for patrolling by unreliable robots. We show that the presented algorithm achieves the idleness, which is the best possible.
 Plus d'infos  


2014-11-03Coloration d'un cycle en temps log*(n): borne sup et borne inf
14:00-15:00
178
 Plus d'infos  


2014-10-20Routage compact en pratique. Peut-on router avec des tables de routage de taille 6 ?
14:00-15:00
178
Le projet européen EULER portant sur des propositions de nouveaux schéma de routage vient de se terminer. Je ferai une petite présentation de nos contributions sur des algorithmes de routage compact pour lesquels nous obtenons des garanties sur l'étirement, la taille des tables ou le cout de construction. Des simulations sur des cartes des systèmes autonomes d'Internet montrent que nous pouvons obtenir des tables de petite taille ...

Ce travail a été fait avec Cyril Gavoille, Christian Glacet et David Ilcinkas.
 Plus d'infos  


2014-10-06k-Partitionnement auto-stabilisant
14:00-15:00
75
Le k-partitionnement organise un réseau comme suit : ses nœuds sous répartis en sous-ensembles disjoints appelés grappes et pour chaque grappe, un nœud appelé tête est distingué, de sorte que chaque nœud d'une grappe est au plus à k sauts de la tête de grappe. Une application possible est de faire du routage hiérarchique en suivant des chemins entre les têtes de grappe pour l'acheminement de messages à travers le réseau. Ceci est particulièrement intéressant dans les réseaux à large échelle où la probabilité de panne est élevée. Les fautes transitoires sont des pannes non-définitives qui n'affectent que le contenu du réseau et non son code ou sa structure. Un algorithme est auto-stabilisant s'il garantit au système, une fois que les fautes transitoires cessent, de récupérer un fonctionnement normal, en temps fini et sans intervention extérieure.
Dans cet exposé, nous considérerons le problème du k-partitionnement auto-stabilisant. Il faut noter que construire un k-partitionnement de taille minimum est un problème NP-difficile. Nous proposerons un algorithme auto-stabilisant de k-partitionnement et étudierons ses propriétés dans l'arbre, dans un graphe connexe et dans un graphe de disques unitaires. Cette dernière topologie est généralement utilisée pour modéliser des réseaux de capteurs sans fil.
 Plus d'infos  


2014-09-29k-Partitionnement auto-stabilisant
14:00-15:00
75
*****Attention Changement de salle 75 au lieu de 178 *****

Le k-partitionnement organise un réseau comme suit : ses nœuds sous répartis en sous-ensembles disjoints appelés grappes et pour chaque grappe, un nœud appelé tête est distingué, de sorte que chaque nœud d'une grappe est au plus à k sauts de la tête de grappe. Une application possible est de faire du routage hiérarchique en suivant des chemins entre les têtes de grappe pour l'acheminement de messages à travers le réseau. Ceci est particulièrement intéressant dans les réseaux à large échelle où la probabilité de panne est élevée. Les fautes transitoires sont des pannes non-définitives qui n'affectent que le contenu du réseau et non son code ou sa structure. Un algorithme est auto-stabilisant s'il garantit au système, une fois que les fautes transitoires cessent, de récupérer un fonctionnement normal, en temps fini et sans intervention extérieure.
Dans cet exposé, nous considérerons le problème du k-partitionnement auto-stabilisant. Il faut noter que construire un k-partitionnement de taille minimum est un problème NP-difficile. Nous proposerons un algorithme auto-stabilisant de k-partitionnement et étudierons ses propriétés dans l'arbre, dans un graphe connexe et dans un graphe de disques unitaires. Cette dernière topologie est généralement utilisée pour modéliser des réseaux de capteurs sans fil.

*****Attention Changement de salle 75 au lieu de 178 *****
 Plus d'infos  


2014-07-07Solo-fast Universal Constructions for Deterministic Abortable Objects
14:00-15:00
178
In the context of shared memory model, we present our study on efficient implementations for deterministic abortable objects. Deterministic abortable objects behave like ordinary objects when accessed sequentially, but they may return a special response abort to indicate that the operation failed (and did not take effect) when there is contention.
It is impossible to implement deterministic abortable objects only with read/write registers. Thus, we study solo-fast implementations. These implementations use stronger synchronization primitives, e.g., CAS, only when there is contention. We consider interval contention.
We present a non-trivial solo-fast universal construction for deterministic abortable objects. A universal construction is a method for obtaining a concurrent implementation of any object from its sequential code. The construction is non-trivial since in the resulting implementation a failed process can cause only a finite number of operations to abort. Our construction guarantees that operations that do not modify the object always return a legal response and do not use CAS. Moreover in case of contention, at least one writing operation succeeds. We prove that our construction has asymptotically optimal space complexity for objects whose size is constant.
 Plus d'infos  


2014-06-30Rendez-vous d'agents mobiles tolérant aux pannes
14:00-15:00
178
Les systèmes d’agents mobiles sont des environnements distribués dans lequel les nœuds du réseau sont passifs et ce sont des agents mobiles qui s’occupent de l’exécution de l’algorithme. Le réseau est représenté par un graphe et les agents peuvent se déplacer d’un nœud à l’autre du graphe le long de ses arêtes. Dans cet exposé, on va chercher à trouver des algorithmes permettant à deux agents mobiles initialement dispersé dans le graphe de se rencontrer sur un nœud du graphe. Plus particulièrement, on s'intéressera à ce problème pour un modèle synchrone dans lequel une panne peut se produire lors de chaque tentative de déplacement des agents. On considérera trois types de pannes possibles : probabiliste (probabilité constante de panne), adversaire non borné ou borné (un adversaire peut empêcher un agent de bouger pendant un nombre de rondes fini ou bien borné par une constante). Je donnerai des bornes inférieures et supérieures sur le coût du rendez-vous (nombre de déplacements des agents avant le rendez-vous dans le pire des cas) ainsi que des résultats d'impossibilité pour ces trois types de pannes.
 Plus d'infos  


2014-06-23Maintenance d'arbres et détection de déconnexion
14:00-15:00
178
Dans ce travail, nous proposons un algorithme auto-stabilisant de maintenance d'arbres de plus de courts chemins tout en gérant la déconnexion de graphes dynamiques ... ce qui résoud le problème du comptage à l'infini sans connaissance sur le graphe. Ce travail a été fait avec Colette Johnen, David Ilcinkas et Nicolas Hanusse.
 Plus d'infos  


2014-05-26Le codage de réseau aléatoire : une introduction
14:00-15:00
178
 Plus d'infos  


2014-05-05Data Structures for Emergency Planning
14:00-15:00
178
We present in this talk different techniques for quickly answer graph problems where some of the nodes may be turn off. Typical graph problems are such as connectivity or distances between pair of nodes but not only. Emergency planning for such problems is achieved by pre-processing the graphs and by virtually preventing all possible subsequent node removals. To obtain efficient data structures, the idea is to attach very little and localized information to nodes of the input graph so that queries can be solved using solely on these information. Contexts and solutions for several problems will be surveyed.
 Plus d'infos  


2014-03-31Algebraic Removal Lemma
14:00-15:00
178
The removal lemma is a combinatorial result which, in its simpler form,
says that a graph with n vertices and o(n^3) triangles can be made
triangle free by deleting o(n^2) edges. It was used by Ruzsa and Szemerédi
to provide a simple proof of Roth's theorem on 3-term arithmetic
progressions in dense sets of integers. An analogous algebraic statement
was formulated by Green in terms of solutions of linear equations in
abelian groups. In the talk I will report on some contributions made
jointly with Dan Král' and Lluís Vena to this algebraic version for
linear systems in abelian groups and some consequences in arithmetic
Ramsey theory. The latter include a version of Szemerédi theorem on
arithmetic progressions in dense sets of finite abelian groups.

P.S. : Il s'agit d'un exposé CPU.
 Plus d'infos  


2014-03-24Exploration and Diffusion in Graphs using Deterministic Walks
14:00-15:00
178
In a continuous diffusive process, a certain amount of a resource, known as "load", is initially placed on the nodes of the graph, possibly in an unfair manner. In successive time steps, each node shares its load evenly among all its neighbors, until the load on the nodes of the graph eventually converges to its limit distribution (e.g., becomes uniform in the case of regular graphs). However, continuous diffusion cannot be applied to "granular load" which is not arbitrarily divisible, i.e., represented by unsplittable unit-load tokens (chips), which are placed on nodes and may be passed around the graph. In such a scenario, one natural way of simulating the continuous diffusion process is to require that each chip follows an independent random walk on the graph.

In this talk, we will instead focus on chip diffusion processes following rules which are both locally fair and deterministic. These rules include the so-called "rotor walk", in which chips are propagated by each node to its neighbors in round-robin fashion and, more broadly, rules in which each node attempts to send out roughly the same number of tokens through each of its outgoing arcs.

We will start by providing a description of the evolution and limit behavior of the rotor walk on the n-node ring with K << n chips. For general graphs, we will show bounds on the "cover time" of a rotor walk system with K chips, proving that in a graph with m edges and diameter D, all nodes will have been visited at least once by some chip during the first O(mD / log K) steps of the process. Finally, we will relate the "blanket time" (the time until all nodes of the graph have been visited by chips a similar number of times) and the "diffusion time" (the time until all nodes all host a similar number of chips, for K >> n) of fair deterministic walks to analogous parameters of the random walk. The latter results allow us to design surprisingly simple and efficient deterministic algorithms for load balancing in the diffusive model.

This talk includes an overview of results presented at PODC'13, STACS'14, and some current work in progress (joint work with: P. Berenbrink, D. Dereniowski, R. Klasing, F. Mallmann-Trent, D. Pajak, T. Sauerwald, P. Uznanski).
 Plus d'infos  


2014-03-03Algorithmes de mise à jour locale pour des graphes aléatoires
14:00-15:00
178
Afin de modéliser l'évolution de réseaux logiques dynamiques, nous proposons de maintenir exactement une distribution donnée de graphes aléatoires lors d'une séquence arbitraire d'insertions et de suppressions de sommets. Nous nous plaçons dans un modèle local où nous n'avons pas accès à l'ensemble des sommets, mais supposons à la place l'accès à une primitive globale renvoyant un sommet aléatoire uniforme du graphe. Dans cet exposé, nous nous intéressons à maintenir la distribution uniforme dans les graphes k-sortants (graphes dirigés où tous les sommets ont degré sortant k). Nous présenterons plusieurs algorithmes d'insertion et de suppression pour le problème de maintenance, dont les plus efficaces sont asymptotiquement optimaux.
 Plus d'infos  


2014-01-27Présentation de quelques expériences de calcul distribué sur données massives
14:00-15:00
178
Cet exposé décrira un problème basique de comptage d'éléments distincts et des expériences réalisées sur une plate-forme de calcul distribué dans PlaFRIM et à l'intérieur du LaBRI
 Plus d'infos  


2013-07-08Dynamic Resource Allocation in Cloud Computing platforms
14:00-15:00
Salle 178
Je présente un problème d'allocation de ressources dans le contexte du Cloud Computing, où un ensemble de machines virtuelles (VM) doivent être allouées sur un ensemble de machines physiques (PMs). La particularité de ce problème vient du fait que la quantité de ressources dont chaque VM a besoin change au cours du temps, et qu'il est possible pour le fournisseur d'accès de changer l'allocation d'une VM par une opération de migration. Ce problème peut se modéliser sous la forme d'un problème de bin packing complètement dynamique, et je présente un algorithme d'approximation pour minimiser le nombre de PMs utilisées, tout en garantissant un petit nombre de migrations. Les propriétés de cet algorithme permettent également d'envisager une version distribuée.
 Plus d'infos  


2013-06-17Sur les algorithmes distribués probabilistes du type Monte-Carlo ou ``Que peut faire le hasard quand on est dans le brouillard?'
14:00-15:00
Salle 178
Cet exposé présente tout d'abord quelques résultats de non
existence d'algorithmes distribués probabilistes pour des réseaux
anonymes sur lesquels on n'a aucune information. Il se poursuit par la
description et l'analyse de procédures distribuées de
fractionnement et de nommage. Enfin on applique ces procédures
aux problèmes suivants : calcul d'un arbre recouvrant, comptage
du nombre de sommets d'un anneau et élection.
(Travail en collaboration avec John Michael Robson et Akka Zemmari.
 Plus d'infos  


2013-06-10The Heard-Of model: computing in distributed systems with benign failures
14:00-15:00
Salle 178
Problems in fault-tolerant distributed computing have been studied in a va- riety of system models. These models are all based on the principle that it is usefull and even necessary to specify why and by whom errors occur. In this talk, we question this principle, and present a general computational model, called the Heard-Of model, suitable for describing any type of system, be it message passing, shared memory, synchronous, or asynchronous.
In this model, computations evolve in rounds, and communication missed at a round is definitely lost. Only information transmission is represented: for each round r and each process p, our model specifies the set of processes that p “hears of” at round r (heard-of set) namely the processes from which p receives some message at round r. The features of a specific system are thus captured as a whole, just by a predicate over the collection of heard-of sets. Thus the Heard-Of model allows us to handle all types of benign failures, static or dynamic, permanent or transient, in a unified framework. Moreover, it unifies the most seemingly unrelated notions in distributing computing, namely synchrony and asynchrony.
We further demonstrate how this unifying framework leads to new results and insights in fault-tolerant distributed computing. In particular, we show that some fundamental results for asynchronous systems can be advantageously transferred to synchronous systems. We also examine Consensus algorithms in the Heard-Of model: we show how our approach allows us to devise new solutions and to give simple correctness proofs of existing algorithms like Paxos.

Joint work with André Schiper (EPFL)
 Plus d'infos  


2013-06-03Introduction to renaming
14:00-15:00
Salle 178
Renaming is a fundamental coordination problem in distributed computing. It consists in assigning new names taken from a small name space to processes in such a way that no two processes obtain the same name. The talk will survey renaming algorithms suited for different models of distributed computing, including the wait-free shared memory and the synchronous crash-prone message-passing models.
 Plus d'infos  


2013-05-27Exploration des graphes dynamiques T-intervalle-connexes : le cas de l'anneau
14:00-15:00
Salle 178
Dans cet exposé, je vais parler de l'étude des graphes dynamiques T-intervalle-connexes du point de vue du temps nécessaire à leur exploration par une entité mobile (agent). Un graphe dynamique est T-intervalle-connexe (T geq 1) si pour chaque fenêtre de T unités de temps, il existe un sous-graphe couvrant connexe stable. Cette propriété de stabilité de connexion au cours du temps a été introduite par Kuhn, Lynch et Oshman~cite{KLO10} (STOC 2010). Nous nous concentrons sur le cas où le graphe sous-jacent est un anneau de taille n et nous montrons que la complexité en temps en pire cas est de 2n-T-Theta(1) unités de temps si l'agent connaît la dynamique du graphe, et n+ frac{n}{max{1,T-1}} (delta-1) pm Theta(delta) unités de temps sinon, où delta est le temps maximum entre deux apparitions successives d'une arête.
 Plus d'infos  


2013-05-13Calcul Distribué et Fouille de Données
14:00-15:00
salle 178
L'avènement de la production massive de données et la volonté de les exploiter sont limités par les systèmes de gestion de bases de données relationnelles classiques. Cet exposé consiste en une discussion sur les enjeux et problèmes algorithmiques engendrés par le calcul distribué et parallèle. Le calcul de corrélations servira d'illustration. C'est un travail en cours avec Sofian Maabout et Eve Garnaud.
 Plus d'infos  


2013-04-22A peer-to-peer-based virtual environment system
14:00-15:00
Salle 178
Virtual environments (VEs) are 3-D virtual worlds in which a huge number of participants play roles and interact with their surroundings through virtual representations called avatars. VEs are traditionally supported by a client/server architecture. However, centralized architectures can lead to bottleneck on the server due to high communication and computation overhead during peak loads. Thus, P2P overlay networks are emerging as a promising architecture for VEs. However, exploiting P2P schemes in VEs is not straightforward, and several challenging issues related to data distribution and state consistency should be considered.

One of the key aspects of P2P-based VEs is the logical platform consisting of connectivity, communication and data architectures, on which the VE is based. The connectivity architecture is the overlay topology structure, which defines how peers are connected to each other. The communication architecture is the routing protocol defining how peers can exchange messages, while the data architecture defines how data are distributed over the logical overlay. The design of these architectures has significant influence on the performance and scalability of VEs.

First, we propose a scalable connectivity architecture based on a new triangulation algorithm reducing maintenance cost of the system. Second, we construct a communication architecture built on top of the connectivity architecture ensuring that each message reaches its intended destination. Finally, we propose a data architecture ensuring the management of data with different characteristics in terms of mobility in the VE, while providing a fair data distribution and low data transfer between peers in the VE.
 Plus d'infos  


2013-04-15Algorithms for the Vertex Cover Problem on Large Graphs with Low Memory Capacities
14:00-15:00
Salle 178
Most of the known optimization algorithms need to explore, mark, modify, etc. the instance given as input before producing their results. To do that, the instance is entirely loaded into the memory of the computer and is manipulated by the algorithm. Often, "extra" data structures are also necessary to memorize parameters useful all along the computation or to update the current solution that will be returned as the final product of the program. However, this classical model is no more adapted for many new computing applications. Indeed, nowadays, many fields such as biology, meteorology, finance, etc. produce very large amount of data.

In our works, we have focused on the Vertex Cover problem on huge graphs: in the intrinsic NP-completeness is added the difficulty to manipulate graphs with severe constraints (mainly related to the low memory capacities). We defined a treatment model combining some properties of several existing models in the literature: streaming, online, I/O-efficient, etc. We initially considered three approximation algorithms, which are memory-efficient (they use a memory space in O(log n) bits). We analyzed their performance in terms of solution quality and complexity, in mean and worst cases. We then focused on algorithms that use memory space of n bits. We showed that it could be very worst with strictly less than n bits memory space. Subsequently, we conducted experiments on very large graphs (in the order of billions of vertices and edges). This study showed that in practice, memory-efficient algorithms are better suited to handle large graphs.

This is joint work with Eric Angel (IBISC, Univ. Évry) and Christian Laforest (LIMOS, ISIMA, Clermont-Ferrand).
 Plus d'infos  


2013-04-08Implémentation d'algorithmes distribués à l'aide de Visidia
14:00-15:00
Salle 178
Dans le cadre du projet visidia, une plate-forme logicielle est développée pour l'implantation et la visualisation d'algorithmes distribués. Après une introduction et quelques rappels, l'exposé consistera en une présentation de la plate-forme et de son utilisation pour programmer des exemples d'algorithmes. L'interface et l'API permettent de visualiser l'exécution d'algorithmes, d'implanter de nouveaux algorithmes, ou d'effectuer des statistiques. Les algorithmes peuvent être exprimés selon plusieurs modèles (calculs locaux, passage de messages, agents mobiles).
 Plus d'infos  


2013-03-25Simultaneous Consensus vs Set Agreement
14:00-15:00
Salle 178
In the traditional consensus task, processes are required to agree on a common value chosen among the initial values of the participants. It is well known that consensus cannot be solved in crashed-prone, asynchronous distributed systems. Two generalizations of the consensus problem have been introduced: k-set agreement and k-simultaneous consensus. The k-set agreement task has the same requirements as consensus except that processes are allowed to decide up to k distinct values. In the k-simultaneous consensus task, each process participates simultaneously in k instances of consensus and is required to decide in at least one of them; any two processes deciding in the same instance must decide the same value. In this talk, we compare the computability of these problems in two central models in distributed computing: shared memory and message passing. We show that even though the two problems are equivalent in shared memory, k-simultaneous consensus is strictly harder than k-set agreement in the message passing model. This result will serve as a basis for a discussion about different models of computation and their respective power.
 Plus d'infos  


2013-03-18Vers une classification des réseaux dynamiques en fonction des problèmes qu'on peut y résoudre.
14:00-15:00
salle 178
Derrière les notions de "graphe dynamique" ou de "réseau dynamique" se cache une très grande diversité de scénarios et d'hypothèses, allant de réseaux semi-statiques où la connexité est toujours assurée à des réseaux complètement mobiles, où la connexité ne s'établit qu'à travers le temps et l'espace (e.g. DTNs). Dans cet exposé, résolument transversal, je présenterai l'état d'avancement de nos recherches autour de la question suivante : quel lien existe-t-il entre la "faisabilité" de tâches distribuées et la dynamique du réseau. Les hypothèses résultantes sur la dynamique peuvent être vues comme autant de classes de graphes (ou alternativement, comme autant de puissances possibles pour un adversaire qui contrôlerait la topologie). Nous avons à ce jour caractérisé et/ou recensé une petite vingtaine de classes de ce type.

Certains de ces travaux ont été menés en collaboration avec Serge Chaumette et Afonso Ferreira. D'autres avec Paola Flocchini et Nicola Santoro.
 Plus d'infos  


2013-02-25Sur les 1001 modèles en algorithmique distribuée
14:00-15:00
salle 178
Le but de cet "exposé-discussion" est de présenter quelques modèles en algorithmique distribuée et d'échanger sur leurs liens et leurs mérites.
 Plus d'infos  


2013-02-18Distributed Calculation of Graph Diameter
14:00-15:00
Salle 178
We consider the problem of calculating the diameter of a graph given that there is a single vertex "Leader" and neighbouring vertices can exchange
messages of a single bit at each round. We show that this can be achieved in the same O(n) time complexity as well known algorithms without this bound on
message length.
The techniques used can be applied to a number of other graph computations. We consider briefly how the algorithm behaves if applied in a situation where more than one vertex considers itself the Leader.

Joint work with Yves Métivier and Akka Zemmari
 Plus d'infos  


2013-02-11Bounds for Communication in Wireless Grids
14:00-15:00
Salle 178
In a wireless network, a transmission can be received by a node if it is
close enough to the sender. However, transmissions can interfere with
each other and the interference distance is typically greater than the
reception distance. Efficient communication protocols in these networks
minimize the time to move information without interference.

In this talk, I will describe optimal protocols for the problem of collecting
information into a central node of a two-dimensional square or hexagonal
grid graph. The optimality of the protocols is proved using a new lower
bound technique that is an adaptation to a discrete environment of a
method based on linear programming duality for continuous flows.

This is joint work with Jean-Claude Bermond, CNRS-INRIA-University of Nice.
 Plus d'infos  


2013-02-04Distributed Detection of Clone Attacks in Wireless Sensor Networks
14:00-15:00
Salle 178
Wireless Sensor Networks (WSNs) are often deployed in hostile environments where an adversary can physically capture some of the nodes, first can reprogram, and then, can replicate them in a large number of clones, easily taking control over the network. A few distributed solutions to address this fundamental problem have been recently proposed. However, these solutions are not satisfactory. First, they are energy and memory demanding: A serious drawback for any protocol to be used in the WSN-resource-constrained environment. Further, they are vulnerable to the specific adversary models that we introduced. The contributions of our work are threefold. First, we analyze the desirable properties of a distributed mechanism for the detection of node replication attacks. Second, we show that the known solutions for this problem do not completely meet our requirements. Third, we propose a new self-healing, Randomized, Efficient, and Distributed (RED) protocol for the detection of node replication attacks, and we show that it satisfies the introduced requirements. Finally, extensive simulations show that our protocol is highly efficient in communication, memory, and computation; is much more effective than competing solutions in the literature; and is resistant to the new kind of attacks introduced in our work, while other solutions are not.
 Plus d'infos  


2013-01-28Distributed Exclusive Graph Searching in Trees
14:00-15:00
Salle 178
We consider a version of the well known graph searching problem, where a team of robots aims at clearing the contaminated edges of a graph. We study graph searching in the model of mobile computing where autonomous deterministic robots move between the graph nodes when operating in asynchronous cycles of Look-Compute-Move. Moreover, motivated by physical constraints, following some recent works, we consider the exclusivity property, stating that no two or more robots can occupy a same node at the same time. In addition, we assume that all the graph elements and the robots are anonymous. Robots are oblivious and have no sense of direction. Our objective is to characterize for a graph $G$, the set of integers $k$ such that graph searching can be achieved by a team of $k$ robots starting from any $k$ distinct nodes in $G$. Our main result consists in a full characterization for any asymmetric tree. Towards providing a characterization in the general case, including trees with non-trivial automorphisms, we provide a set of positive and negative results, including a full characterization for any line. All our positive results are based on the design of algorithms enabling perpetual graph searching to be achieved with the desired number of robots. We prove that, in addition to the distributed nature of our setting, the exclusivity property has a significant impact on the nature of the graph searching problem. Hence, the design of the algorithms requires to invent new methods.
 Plus d'infos  


2013-01-21Présentation de Keep Alert, une solution pour la surveillance de marques sur Internet
14:00-15:00
Salle 178
A destination des cabinets de propriété industrielle et des services juridiques, Keep Alert propose des surveillances de marque parmi les noms de domaine, les régies publicitaires et les réseaux sociaux.
Anthony DON, directeur technique chez Keep Alert, présentera au groupe de travail, le fonctionnement global de la plateforme, puis abordera les problématiques actuelles et les perspectives de développement relatives à l'algorithmique distribuée.
 Plus d'infos  


2013-01-14Two Monte-Carlo Election Algorithms for Anonymous Graphs without any Initial Knowledge
14:00-15:00
Salla 178
The paper proposes and analyses two Monte Carlo election algorithms for anonymous graphs without any initial knowledge. Both have a time complexity equal to $O(D)$, where $D$ is the diameter of the graph. The first is correct with probability $1-o(n^{-1})$ (where $n$ is the size of the graph). The size of messages is $O(log n)$ with probability $1-o(n^{-1})$ and the expected value of the size of messages is also $O(log n)$. The second is correct with probability $1-o(n^{-c})$ for any $cgeq 1$. The size of messages is $Oleft((log n)(log^* n)^2
ight)$ with probability $1-o(n^{-c})$ for any $cgeq 1$; their expected size is $Oleft((log n)(log^* n)
ight)$.

This is a joint work with Y. Métivier and J. M. Robson
 Plus d'infos  


2012-12-03Progress and Challenges for Labeling Schemes
14:00-15:00
Salle 178
A fundamental question in Distributed Computing is to understand how localized and how much information are required to solve a task on a network. Typically, if the distance between any pair x,y of nodes in a network is asked, we would like to know which minimal information about x and y in the network are needed. The goal in labeling schemes is precisely to understand how much information must be attached to the nodes (formalized as labels) to solve a graph problem assuming the answer can be determined solely on the basis of the labels of the nodes invoked in the query. In this talk, I give a survey on labeling schemes, present some recent results with their techniques, and highlight new challenges.
 Plus d'infos  


2012-10-22Toward a compact distributed routing scheme
14:00-15:00
s. 178
Current routing scheme used for inter-domain routing has
scaling issues (linear routing tables size).
In this GT, I'll present an distributed alternative to this classical
shortest path routing, compact routing.
A routing scheme is said to be compact if routing tables used have
sub-linear size.
 Plus d'infos  


2012-10-15Network Verification via Routing Table Queries
14:00-15:00
s. 178
We address the problem of verifying the accuracy of a map of a network by making as few measurements as possible on its nodes. This task can be formalized as an optimization problem that, given a graph G=(V,E), and a query model specifying the information returned by a query at a node, asks for finding a minimum-size subset of nodes of G to be queried so as to univocally identify G. This problem has been faced w.r.t. a couple of query models assuming that a node had some global knowledge about the network. Here, we propose a new query model based on the local knowledge a node instead usually has. Quite naturally, we assume that a query at a given node returns the associated routing table, i.e., a set of entries which provides, for each destination node, a corresponding (set of) first-hop node(s) along an underlying shortest path. First, we show that any network of n nodes needs Omega(log log n) queries to be verified. Then, we prove that there is no o(log n)-approximation algorithm for the problem, unless P=NP, even for networks of diameter 2. On the positive side, we provide an O(log n)-approximation algorithm to verify a network of diameter 2, and we give exact polynomial-time algorithms for paths, trees, and cycles of even length.

This is joint work with Evangelos Bampas, Davide Bilo, Guido Drovandi, Luciano Guala and Guido Proietti.

Intervenant: Ralf Klasing
 Plus d'infos  


2012-07-16From self-stabilizing to self-stabilizing with service guarantee weight-based clustering
14:00-15:00
s. 076
I will present a generic scheme to transform a silent self-stabilizing 1-hop weight-based clustering protocol, called original protocol P, to a self-stabilizing with service guarantee protocol, called the transformed protocol TP. TP requires only 2 bits more than P. Moreover, starting from an arbitrary configuration, TP reaches a safe con guration in at most 3 rounds, where the following useful minimal service is provided: "each node belongs to a 1-hop cluster having an e ffectual leader". Afterwards, TP reaches a terminal configuration in at most 4*SP rounds where SP is the stabilization time of P protocol. During stabilization of TP protocol, the minimal service is preserved, so the clustering structure is available throughout the entire network.

Intervenant: Fouzi Mekhaldi
 Plus d'infos  


2012-07-03Some algorithms for replica placement with distance constraints in tree networks
14:00-15:00
s. 076
The problem of replica placement in tree networks subject to server capacity and distance constraints is considered. The client requests are known beforehand, while the number and location of the servers are to be determined. The Single policy enforces that all requests of a client are served by a single server in the tree, while in the Multiple policy, the requests of a given client can be processed by multiple servers, thus distributing the processing of requests over the platform. For the Single policy, we prove that all instances of the problem are NP-hard, and we propose approximation algorithms. The problem with the Multiple policy was known to be NP-hard with distance constraints, but we provide a polynomial time optimal algorithm to solve the problem in the particular case of binary trees when no request exceeds the server capacity.

Intervenant: Hubert Larchevêque
 Plus d'infos  


2012-06-25Evolutionary Dynamics on Undirected Networks
14:00-15:00
s. 178
Evolutionary dynamics have been traditionally studied in the contect of homogeneous populations, mainly described by the Moran Process. Recently, this approach has been generalized by Lieberman, Hauert and Nowak [Nature, 2005], by arranging individuals on the nodes of a connected directed network. Our work focuses on evolutionary models for undirected networks which seem to have a smoother behaviour.
We present the first class of undirected graphs which act as suppressors of selection (i.e. have smaller fixation probability than the clique). We also show how to compute fixation probabilities in any undirected graph via a fully polynomial randomized approximation scheme. In addition we present a new alternative evolutionary model in which all individuals act simultaneously and the result is a compromise between aggressive and non-aggressive individuals. So, we consider also aggregation as opposed to "all or nothing" strategy implied by the generalized Moran process.

This is recent joint work with (a)G. Mertzios, S. Nikoletseas and Ch. Raptopoulos [WINE 2011] and (b) with J. Diaz, L.A. Goldberg, G. Mertzios, D. Richerby and M. Serna [SODA 2012].

Intervenant: George B. Mertzios
 Plus d'infos  


2012-06-18Convergecast by Power-Aware Mobile Agents
14:00-15:00
s. 076
A set of identical, mobile agents is deployed in a network. Every network edge has a weight representing the distance between its endpoints. Each agent possesses a battery - a power source allowing to move along the network edges. Agents’ movement uses its battery proportionally to the distance travelled. The agent may stop at any point of network edge. Agents have a simple sensing device permitting to detect other agents - present at the same time at the same point of the network. At the beginning each agent has its initial information. The agents may exchange their information when they meet. The agents collaborate in order to achieve a common goal, which is convergecast, i.e., the initial information of all agents must be eventually concentrated at one agent. We investigate what is the minimal value of power, initially available to all agents, so that convergecast may be achieved. We study the problem in the centralized setting, when the problem must be solved by a centralized authority knowing the network and the initial positions of all agents in the network, and in the distributed setting, when each agent has to perform an algorithm being unaware of its initial position and the presence of other agents.

Intervenant: Jurek Czyzowicz
 Plus d'infos  


2012-06-11Leader Election for Anonymous Asynchronous Agents in Arbitrary Networks
14:00-15:00
s. 076
We consider the problem of leader election among mobile agents
operating in an arbitrary network modeled as an undirected graph.
Nodes of the network are unlabeled and all agents are identical. Hence the
only way to elect a leader among agents is by exploiting asymmetries
in their initial positions in the graph. Agents do not know the graph or
their positions in it, hence they must gain this knowledge
by navigating in the graph and share it with other agents to accomplish
leader election. This can be done using meetings of agents, which is
difficult because of their asynchronous nature:
an adversary has total control over the speed of agents. When can a leader
be elected in this adversarial scenario and how to do it?
We give a complete answer to this question by characterizing all initial
configurations for which leader election is possible and by constructing
an algorithm that accomplishes leader election for all configurations for
which this can be done.

This is joint work with Andrzej Pelc.

Intervenant: Dariusz Dereniowski
 Plus d'infos  


2012-06-04Calcul distribué de requêtes type ``horizon'' (Skyline)
14:00-15:00
s. 076
L'exposé discutera des résultats présentés à EDBT'11 dans:
"Efficient Execution Plans for Distributed Skyline Query Processing
João B. Rocha-Junior, Akrivi Vlachou, Christos Doulkeridis, and Kjetil Nørvåg"

Etant donné un ensemble O d'objets décrits chacun par n attributs
et étant donné un ordre total "<_i" sur chaque attribut, o1 "domine" o2 ssi
pour chaque attribut i, o1[i] $leq_i$ o2[i] ET il y a un j tel
que o1[j] <_j o2[j]. L'horizon de O (c'est aussi appelé 'enveloppe de Pareto')
est l'ensemble de ses éléments qui ne sont pas dominés. Le papier présente
une technique d'ordonnancement permettant de réduire la quantité de données
transférées sur le réseau pour optimiser la requête.

Intervenant: Sofian Maabout
 Plus d'infos  


2012-05-14Modélisation cérébrale systémique: approches en algorithmique distribuée
14:00-15:00
s. 076
Je présenterai les activités de l'équipe Mnemosyne, dans le domaine de la modélisation multi-échelle du cerveau. Cette équipe, immergée à l'Institut des Maladies Neurodégénératives, est une équipe d'informatique et de mathématique appliquée. Elle s'appuie sur des connaissances, des expérimentations et des interactions avec biologistes et médecins pour développer des modèles pouvant avoir des impacts dans les Sciences du Vivant et en médecine, mais elle développe aussi une démarche à part entière dans le domaine des STIC et particulièrement en algorithmique distribuée que je présenterai ici.

Intervenant: Frederic ALEXANDRE
 Plus d'infos  


2012-04-02Spanner planaire pour le Unit Disk Graph
14:00-15:00
s. 076
Nous nous intéressons à la recherche d'un spanner (un sous-graphe approximant les distances) planaire pour les graphes de disques unitaires (UDG) qui modélise les réseaux ad hoc sans fils. De nombreux résultats existent pour les spanners en terme de distance Euclidienne de UDG, nous présentons ici un algorithme qui construit un spanner planaire avec un facteur d'étirement constant en terme de distance de graphe pour UDG. Par rapport aux constructions précédemment proposées pour ce problème, nous assurons un facteur d'étirement significativement plus petit ainsi que la planarité totale du graphe. Cet algorithme utilise uniquement des propriétés locales et peut donc être implémenté de manière distribuée.

Intervenant: Nicolas Catusse
 Plus d'infos  


2012-03-26Distributed Online and Stochastic Queuing on a Multiple Access Channel
14:00-15:00
s. 076
We consider the problems of online and stochastic packet queuing in a
distributed system of n nodes with queues, where the communication
between the nodes is done via a multiple access channel. In each
round, an arbitrary number of packets can be injected into the system,
each to an arbitrary node's queue. Two measures of performance are
considered: the total number of packets in the system, called the
total load, and the maximum queue size, called the maximum load. In
the online setting, we develop a deterministic algorithm that is
asymptotically optimal with respect to both complexity measures, in a
competitive way; more precisely, the total load of our algorithm is
bigger then the total load of any other algorithm, including
centralized onine solutions, by only O(n^2), while the maximum queue
size of our algorithm is at most O(n) plus the value which is at most
n times bigger than the maximum queue size of any other algorithm. The
optimality for both measures is justifi ed by proving the
corresponding lower bounds. Next, we show that our algorithm is
stochastically optimal for any expected injection rate smaller or
equal to 1. To the best of our knowledge, this is the fi rst solution
to the stochastic queuing problem on a multiple access channel that
achieves such optimality for the (highest possible) rate equal to 1.

This is joint work with Marcin Bienkowski, Tomasz Jurdzinski, and Dariusz Kowalski.

Intervenant: Miroslaw Korzeniowski
 Plus d'infos  


2012-03-12On the lambda-alert problem in radio networks
14:00-15:00
s. 076
In this talk we will consider the λ-alert problem in a single hop radio network. Some subset of stations of the network is activated. The aim of the protocol is to say if the number of activated stations is at least λ. The problem is a generalization of the alert problem and is similar to the classical k-Selection problem. We will consider deterministic, randomized, oblivious and adaptive algorithms for λ-alert in models with and without collision detection.

Orateur: Dominik Pajak
 Plus d'infos  


2012-03-05On Snapshots and Stable Properties Detection in Anonymous Fully Distributed Systems
14:00-15:00
s. 076
Most known snapshot algorithms assume that vertices of network have unique
identifier and/or there is exactly one initiator. This talk concerns snapshot computation
in an anonymous network and more generally what stable properties of a distributed
system can be computed anonymously with local snapshots with multiple initiators
when knowing an upper bound on the diameter of the network.

Orateur: Thomas Morsellino
 Plus d'infos  


2012-02-13Preuves formelles d'algorithmes distribués probabilistes
14:00-15:00
s. 076
Afin de prouver des propriétés d'algorithmes distribués probabilistes à l'aide d'un assistant de preuve tel Coq, il faut un modèle permettant de raisonner à la fois sur l'aspect distribué et sur le probabiliste. Une nouvelle méthode a été introduite dans la bibliothèque Alea concernant l'aspect probabiliste. Elle est basée sur l'interprétation monadique des programmes probabilistes vus en tant que distributions probabilistes.

Nous présentons en premier lieu comment l'interprétation des algorithmes probabilistes comme des distributions a permis de constituer la bibliothéque Alea de preuves formelles de propriétés de ces programmes. Nous verrons ensuite les choix faits pour modéliser les algorithmes distribués. Nous appliquerons enfin ces théories dans les cas de la brisure de symétrie, du handshake et du maximal matching.
 Plus d'infos  


2012-02-06Tolerating Transient, Permanent, and Intermittent Failures
14:00-15:00
s. 076
When the size of a distributed system gets larger or when it is deployed in hazardous environments, the possibility that some elements of the system are subject to faults (failure, memory corruption, hacking, ...) become impossible to elude. Faults can be classified according to duration, span, or nature. In this talk, we focus on distributed systems that simultaneously tolerate several kinds of faults using three classical problems as case studies. We present first a distributed protocol simulating a single-writer multi-reader atomic register in the presence of transient faults and of permanent crash faults. This protocol relies on two re-usable tools: a communication primitive and a bounded timestamp scheme. Then, we study logical clock weak synchronization in the presence of transient faults and of intermittent Byzantine faults. We prove several impossibility results and provide a protocol that is optimal both with respect to impossibility result and with respect to recovery time. Finally, we define three new fault tolerance schemes in distributed systems that are subject to transient faults and to intermittent Byzantine faults. We design a protocol constructing a wide class of spanning trees that is optimal with respect to fault tolerance metrics defined for these three schemes.

Orateur: Swan Dubois (LIP6)
 Plus d'infos  


2012-01-23Scheduling Associative Reductions with Overlapping Transfers and Computation
14:00-15:00
s. 076
Increasing the performance of HPC and cloud environments involves to optimize the reduction phase, which is present in many applications. This optimization problem arises in at least two contexts: the MPI_Reduce collective function that allows to combine several arrays by performing a pairwise reduction operation on every arrays; and, the Reduce part of MapReduce applications, where a single result is generated from several inputs. By assuming the associativity of the reduction operation, it is possible to determine a spanning tree that schedules data transfers and reduction operations. Two algorithms are proposed for the cases where the number of reducers or the number of concurrent transfers is bounded. When there is no limitation, two specific optimal spanning trees are also characterized for specific transfer and computation costs.

Orateur: Louis-Claude Canon
 Plus d'infos  


2012-01-16The Impact of Edge Deletions on the Number of Errors in Networks.
14:00-15:00
s. 076
In this talk we deal with an error model in distributed networks. For a target t, every node is assumed to give an advice, ie. to point to a neighbour that take closer to the destination. Any node giving a bad advice is called a liar. Starting from a situation without any liar, we study the impact of topology changes on the number of liars.
More precisely, we establish a relationship between the number of liars and the number of distance changes after one edge deletion. Whenever l deleted edges are chosen uniformly at random, for any graph with n nodes, m edges and diameter D, we prove that the expected number of liars and distance changes is O(l^2 D n / m) in the resulting graph. The result is tight for l = 1. For some specific topologies, we give more precise bounds.


This is joint work with Nicolas Hanusse and David Ilcinkas.

Orateur: Christian Glacet
 Plus d'infos  


2012-01-09Overlay Addressing and Routing System Based on Hyperbolic Geometry
14:00-15:00
s. 076
Local knowledge routing schemes based on virtual coordinates taken from the hyperbolic plane have attracted considerable interest in recent years. In this work, we propose a new approach for seizing the power of the hyperbolic geometry.
We aim at building a scalable and reliable system for creating and managing overlay networks over the Internet.
The system is implemented as a peer-to-peer infrastructure based on the transport layer connections between the peers.

Orateur: Cyril Cassagnes
 Plus d'infos  


2011-12-12Tight Bounds for Anonymous Conflict Detectors
14:00-15:00
s. 076
Most known distributed algorithms for randomized consensus from multi-writer registers proceed in rounds, each of which performs two tasks. The first is to ensure agreement with some nonzero probability. The second is to detect whether agreement has been reached.

We give matching upper and lower bounds of min{log m / log log m, n}, to within constant factors, for the individual step complexity of a wait-free m-valued conflict detector for n anonymous processes implemented from multi-writer registers. The upper bound is deterministic, but the lower bound also holds for randomized implementations.

It follows that the same lower bound holds on the individual step complexity of m-valued wait-free anonymous consensus, even for randomized algorithms with global coins against an oblivious adversary. The upper bound can also be used to slightly improve a previous upper bound on the cost of randomized consensus.

This work is joint with James Aspnes and appeared at SPAA 2011.

Orateur: Faith Ellen
 Plus d'infos  


2011-12-07Bounded-Distance Network Creation Games
14:00-15:00
s. 178
A network creation game simulates a decentralized and non-cooperative building of a communication network. Informally, there are n players sitting on the network nodes, which attempt to establish a reciprocal communication by activating, incurring a certain cost, any of their incident links. The goal of each player is to have all the other nodes as close as possible in the resulting network, while buying as few links as possible. According to this intuition, any model of the game must then appropriately address a balance between these two conflicting objectives. Motivated by the fact that a player might have a strong requirement about its centrality in the network, in this paper we introduce a new setting in which if a player maintains its (either maximum or average) distance to the other nodes within a given associated bound, then its cost is simply equal to the number of activated edges, otherwise its cost is unbounded. We study the problem of understanding the structure of associated pure Nash equilibria of the resulting games, that we call MaxBD and SumBD, respectively.
 Plus d'infos  


2011-12-05On the Power of Waiting when Exploring Public Transportation Systems
14:00-15:00
s. 076
We study the problem of exploration by a mobile entity (agent) of a class of dynamic networks, namely the periodically-varying graphs (the PV-graphs, modeling public transportation systems, among others). These are defined by a set of carriers following infinitely their prescribed route along the stations of the network. Flocchini, Mans, and Santoro (ISAAC 2009) studied this problem in the case when the agent must always travel on the carriers and thus cannot wait on a station. They described the necessary and sufficient conditions for the problem to be solvable and proved that the optimal number of steps (and thus of moves) to explore a $n$-node PV-graph of $k$ carriers and maximal period $p$ is in $Theta(kcdot p^2)$ in the general case.

In this talk, we study the impact of the ability to wait at the stations. We exhibit the necessary and sufficient conditions for the problem to be solvable in this context, and we prove that waiting at the stations allows the agent to reduce the worst-case optimal number of moves by a multiplicative factor of at least $Theta(p)$, while the time complexity is reduced to $Theta(ncdot p)$. (In any connected PV-graph, we have $n leq kcdot p$.) We also show some complementary optimal results in specific cases (same period for all carriers, highly connected PV-graphs). Finally this new ability allows the agent to completely map the PV-graph, in addition to just explore it.

This is joint work with David Ilcinkas.

Orateur: Ahmed Wade
 Plus d'infos  


2011-11-28In search of lost time
14:00-15:00
s. 076
In their seminal papers Dwork, Lynch, and Stockmeyer (JACM, 1988) and Lamport (TOCS, 1998) showed that, in order to solve Consensus in a distributed system, it is sufficient that the system behaves well during a finite period of time. In sharp contrast, Chandra, Hadzilacos, and Toueg (JACM, 1996) proved that a failure detector that, from some time on, provides "good" information forever is necessary. We explain that this apparent paradox is due to the two-layered structure of the failure detector model. This structure also has impact on comparison relations between failure detectors. In particular, we make explicit why the classic relation is neither reflexive nor extends the natural history-wise inclusion. Our point is to help understanding of existing models and to study how they model real distributed systems in an accurate way.

Orateur: Bernadette Charron-Bost
 Plus d'infos  


2011-11-21The Complexity of Picking a Name
14:00-15:00
s. 076
Renaming is a fundamental problem in distributed computing,
in which a set of processes need to pick new names from a small
namespace.
In this talk, we present a new connection between renaming and the
classic mutual exclusion problem. We exploit this connection to get
new linear time complexity lower bounds for deterministic renaming,
queue, stack, and fetch-and-increment implementations. On the other
hand, we use it to obtain fast mutual exclusion algorithms based on
sorting networks.

Joint work with James Aspnes, Seth Gilbert, and Rachid Guerraoui.
A full version of these results appeared in the Proceedings of FOCS
2011, and is available at http://people.epfl.ch/dan.alistarh

Orateur: Dan Alistarh
 Plus d'infos  


2011-11-14Asynchronous Exclusive Perpetual Grid Exploration without Sense of Direction
14:00-15:00
s. 076
We investigate the exclusive perpetual exploration of grid shaped networks
using anonymous, oblivious and fully asynchronous robots. Our results hold for robots without sense
of direction (i.e. they do not agree on a common North, nor do they agree on a common left and right ;
furthermore, the "North" and "left" of each robot is decided by an adversary that schedules robots for
execution, and may change between invocations of particular robots). We focus on the minimal number
of robots that are necessary and sufficient to solve the problem in general grids.

This is joint work with Alessia Milani, Maria Gradinariu Potop-Butucaru and Sébastien Tixeuil (to appear in Proc. OPODIS'11).

Orateur: François Bonnet
 Plus d'infos  


2011-10-24Convergence de chaines de Markov controlees par un adversaire
14:00-15:00
s. 076
En algorithmique distribuée, il n'est pas rare de modéliser le
non-déterminisme d'un système en donnant à un adversaire le choix de
l'action à exécuter. Pour peu que les actions soient randomisées, le
système devient alors un automate probabiliste, dont le comportement, si
on sélectionne aléatoirement les actions à effectuer, devient celui
d'une chaîne de Markov.

L'objectif du présent travail est d'explorer dans quelles conditions les
resultats classiques de convergence sur les chaînes de Markov persistent
dans ce genre de situation moins confortable. L'idée est de pouvoir les
appliquer pour pouvoir affirmer, sous des hypothèses minimales, la
convergence de ces systèmes non déterministes vers des distributions
bien définies.

Orateur: Philippe Duchon
 Plus d'infos  


2011-10-17Using the Last-mile Model as a Distributed Scheme for Available Bandwidth Prediction
14:00-15:00
s. 076
Several Network Coordinate Systems have been proposed to predict
unknown network distances between a large number of Internet nodes by
using only a small number of measurements, mostly focused on
predicting latency. But end-to-end path available bandwidth is an
important metric for the performance optimisation in many high
throughput distributed applications, such as video streaming and file
sharing networks.

In this talk, we show how to perform available
bandwidth prediction with the last-mile model, in which each node is
characterised by its incoming and outgoing capacities. This model has
been used in several theoretical works for distributed
applications. We design decentralised heuristics to compute the
capacities of each node so as to minimise the prediction error. We
show that our algorithms can achieve a competitive accuracy even with
asymmetric and erroneous end-to-end measurement datasets, and even
when using a very small number of measurements.

Orateur: Lionel Eyraud-Dubois
 Plus d'infos  


2011-10-10Boundary Patrolling by Mobile Agents with Distinct Maximal Speeds
14:00-15:00
s. 076
A set of k mobile agents are placed on the boundary of a simply connected planar object represented by a cycle of unit length. Each agent has its own predefined maximal speed, and is capable of moving around this boundary with a velocity not exceeding its maximal speed. The agents are required to protect the boundary from an intruder which attempts to penetrate to the interior of the object through a point of the boundary, unknown to the agents. The intruder needs some time interval of length au to accomplish the intrusion. Will the intruder be able to penetrate into the object, or is there an algorithm allowing the agents to move perpetually along the boundary, so that no point of the boundary remains unprotected for a time period of au?

Such a problem may be solved by designing an algorithm which defines the motion of agents so as to minimize the idle time I, i.e., the longest time interval during which any fixed boundary point remains unvisited by some agent, with the obvious goal of achieving I <  au.

Depending on the type of the environment, this problem is known as either "boundary patrolling" or "fence patrolling" in the robotics literature. The most common heuristics adopted in the past include the cyclic strategy, where agents move in one direction around the cycle covering the environment, and the partition strategy, in which the environment is partitioned
into sections patrolled separately by individual agents. This paper is, to our knowledge, the first study of the fundamental problem of boundary patrolling by agents with distinct maximal speeds. In this scenario, we give special attention to the performance of the cyclic strategy and the partition strategy. We propose general bounds and methods for analyzing these strategies, obtaining exact results for cases with 2, 3, and 4 agents. We show that there are cases when the cyclic strategy is optimal, cases when the partition strategy is optimal and, perhaps more surprisingly, cases when novel, alternative methods have to be used to achieve optimality.

This is joint work with Jurek Czyzowicz, Leszek Gasieniec and Evangelos Kranakis.
 Plus d'infos  


2011-09-12Multi-Interface Networks - a survey
14:00-15:00
amphithéâtre du LaBRI (050)
Multi-Interface networks refer to a recent model which considers heterogeneous devices in communication networks. A device can establish several connections by means of different communication interfaces like Bluetooth, IrDA, LAN, WiFi, GSM. A connection is established if both the devices at its endpoints activate at least one common interface. The possibility for the devices to establish different connections introduces new challenging problems on the basis of the available interfaces, the deployment, the bandwidth constraints and other parameters. We survey on recent results where minimum spanning tree, shortest paths, flow and other basic problems have been re-visited within the multi-interface model.
 Plus d'infos  


2011-07-18Approximating Graphic TSP by Matchings
14:00-15:00
s. 178
We present a framework for approximating the metric TSP based on a
novel use of matchings. Traditionally, matchings have been used to
add edges in order to make a given graph Eulerian, whereas our
approach also allows for the removal of certain edges leading to a
decreased cost.

For the TSP on graphic metrics (graph-TSP), the approach yields a
1.461-approximation algorithm with respect to the
Held-Karp lower bound. For graph-TSP restricted to a class of graphs that
contains degree three bounded and claw-free graphs, we show that the
integrality gap of the Held-Karp relaxation matches the conjectured
ratio 4/3. The framework allows for generalizations in a natural way and
also leads to a 1.586-approximation algorithm for the traveling salesman
path problem on graphic metrics where the start and end vertices are
prespecified.

This is joint work with Ola Svensson.
 Plus d'infos  


2011-07-11Dynamic Sharing of a Multiple Access Channel and its Online Analysis
14:00-15:00
s. 178
We consider the mutual exclusion problem on a multiple access channel.
Mutual exclusion is one of the fundamental problems in distributed
computing. In the classic version of this problem, n processes perform
a concurrent program which occasionally triggers some of them to use
shared resources, such as memory, communication channel, device, etc.
The goal is to design a distributed algorithm to control entries and
exits to/from the shared resource in such a way that in any time there
is at most one process accessing it. We consider both the classic and
a slightly weaker version of mutual exclusion, called
ε-mutual-exclusion, where for each period of a process staying in the
critical section the probability that there is some other process in
the critical section is at most ε. We show that there are channel
settings, where the classic mutual exclusion is not feasible even for
randomized algorithms, while ε-mutual-exclusion is. In more relaxed
channel settings, we prove an exponential gap between the makespan
complexity of the classic mutual exclusion problem and its weaker
ε-exclusion version. We also show how to guarantee fairness of mutual
exclusion algorithms, i.e., that each process that wants to enter the
critical section will eventually succeed. In the online/competitive
analysis we consider the problem of serving queues of nodes wanting to
send packets over a shared channel so that maximum queue length stays
within constant factors from maximum queue length of an optimal
centralized algorithm.

This is joint work with Marcin Bienkowski, Tomasz Jurdzinski, Marek Klonowski, and
Dariusz Kowalski.
 Plus d'infos  


2011-07-04Robot Networks with Homonyms: The Case of Patterns Formation
14:00-15:00
s. 178
In this paper, we consider the problem of formation of a series of geometric patterns by a network of oblivious mobile robots that communicate only through vision.
So far, the problem has been studied in models where robots are either assumed to have distinct identifiers or to be completely anonymous.
To generalize these results and to better understand how anonymity affects the computational power of robots, we study the problem in a new model, introduced recently in cite{Delporte2011}, in which n robots may share up to 1 <= l <= n different identifiers.
We present necessary and sufficient conditions, relating symmetricity and homonymy, that makes the problem solvable.
To present our algorithms, we use a function that computes the Weber point for many regular and symmetric configurations. This function is interesting in its own right, since the problem of finding Weber points has been solved up to now for only few other patterns.


Das2010:
S. Das, P. Flocchini, N. Santoro and M. Yamashita. On the computational power of oblivious robots: forming a series of geometric patterns. In PODC 2010.

Delporte2011:
C. Delporte-Gallet, H. Fauconnier, R. Guerraoui, T. Hung, A. Kermarrec, and E. Ruppert. Byzantine agreement with homonyms. In PODC 2011.

****

Zohir Bouzid is doing his PhD with Sébastien Tixeuil in Paris.
 Plus d'infos  


2011-06-14Speculating Seriously
14:00-15:00
amphithéâtre du LaBRI (050)
If we are ever to understand what computers can collectively do, we need a new theory of complexity. Recent evolutions, including the cloud and the multicore, are turning computing ubiquitously distributed, rendering the classical complexity theory of centralized computing at best insufficient. A complexity theory for distributed computing has emerged in the last decades, measuring complexity for each specific model of the networked environment, represented by an adversary that may provoke asynchrony, failures, contention, etc. This one adversary - one result approach led to an exponential proliferation of seemingly unrelated results, none of which captures current practices in the development of distributed applications. Instead, applications rely on speculative algorithms that perform well when the environment behaves nicely and gracefully degrades if the environment is more hostile, considering thereby several adversaries at the same time. With no underlying theory, the proposed speculative algorithms lack however rigor and there is anecdotal evidence of their fragility. It is moreover usually impossible to predict their behavior or determine whether their limitations are related to fundamental impossibilities or artifacts of specific infrastructures. The goal of this talk is to discuss a glimmer of a theory of speculative distributed computing.

****

Rachid Guerraoui is professor in computer science at EPFL. He is interested in distributed computing on which he wrote few books and more papers (http://lpdwww.epfl.ch/rachid/).

****

NOTE: Ce séminaire aura lieu le MARDI!
 Plus d'infos  


2011-06-06Broadcasting on Large Scale Heterogeneous Platforms with connectivity artifacts under the Bounded Multi-Port Model
14:00-15:00
s. 178
We consider the problem of broadcasting a large message in
a large-scale distributed platform. The message must be sent from a source
node, with the help of the receiving peers which may forward the
message to other peers. In this context, we are interested in
maximizing the throughput (i.e. the maximum streaming rate, once
steady state has been reached). The platform model does not assume
that the topology of the platform is known in advance: we consider an
Internet-like network, with complete potential connectivity.
Furthermore, the model associates to each node local properties
(incoming and outgoing bandwidth), and the goal is to build an overlay
which will be used to perform the broadcast operation. We model
contentions using the bounded multi-port model: a processor can be
involved simultaneously in several communications, provided that its
incoming and outgoing bandwidths are not exceeded. It is also
necessary to minimize the number of simultaneous connections that are
opened at a given node (i.e., its outdegree). We also block the possibility
of direct communication between some nodes to model NAT/firewall
restrictions.
 Plus d'infos  


2011-05-23Static Quantum Games Revisited
14:00-15:00
s. 178
The so called emph{quantum game theory} has recently been proclaimed as one of the new branches in the development of both quantum information theory and game theory. However, the notion of a quantum game itself has never been strictly defined, which has led to a lot of conceptual confusion among different authors. In this paper we introduce a new conceptual framework of a emph{scenario} and an emph{implementation} of a game. It is shown that the procedures of "quantization" of games proposed in the literature lead in fact to several different games which can be defined within the same scenario, but apart from this they may have nothing in common with the original game. Within the framework we put forward, a lot of conceptual misunderstandings that have arisen around "quantum games" can be stated clearly and resolved uniquely. In particular, the proclaimed essential role of entanglement in several static "quantum games", and their connection with Bell inequalities, is disproved.
 Plus d'infos  


2011-05-02Spanner, distance oracle, and compact routing for unweighted graphs
14:00-15:00
s. 178
It is known that every n-vertex unweighted graph G has a subgraph H of O(n^1.5) edges such that the distance in H between any two vertices is at most the distance in G plus 2. In other words, there is always a graph of size O(n^1.5) that well approximate all distances in G. It is however not known whether every graph has a data-structure (a distance oracle) of space O(n^1.5) supporting (d+2)-approximate distance query in constant time. In this direction, Patrascu and Roditty have recently showed in FOCS'11 that distance oracle of size O(n^1.66) and (2d+1)-approximate distance query in constant time do exists.

In this talk, I will show a distributed version of this oracle matching its space and distance approximation bounds, and a generalization of it. I will also present a compact routing scheme using tables of size O(n^0.75) and whose route lengths are at most twice the distance plus one.
 Plus d'infos  


2011-04-18Choosing the best among peers
14:00-15:00
s. 178
A group of n peers (e.g., computer scientists) has to choose the best (most
competent) among them. Each member of the group may vote for one other
member (self-voting is not allowed), or abstain. While opinions may be subjective,
resulting in various voting graphs (directed graphs in which an arc (u,v) means
that u votes for v), it is natural to assume that more competent peers are also,
in general, more competent in evaluating competence of others. We capture this
by proposing a voting system in which each member is assigned a positive integer
"value" satisfying the following "strict support monotonicity" property: the value
of x is larger than the value of y if and only if the sum of values of members voting
for x is larger than the sum of values of members voting for y. Then we choose
the member with the highest value, or if there are several such members, another
election mechanism (e.g., random) chooses one of them.

We show that for every voting graph there is a value function satisfying the strict
support monotonicity property and that such a function can be computed in
linear time. However, it turns out that this method of choosing the best among
peers is vulnerable to vote manipulation: even one voter of very low value
may change her vote so as to get the highest value. This is due to the possibility of
loops (directed cycles) in the voting graph. Hence we slightly modify voting graphs
by erasing all arcs that belong to some cycle. This modification results in
a "pruned voting graph" which is always a rooted forest.

We show that for all pruned voting graphs there are value functions giving
a guarantee against manipulation. More precisely, we show a value function
guaranteeing that no coalition of k members all of whose values are lower than
those of (1-1/(k+1))n other members can manipulate their votes so that one of
them gets the largest value. In particular, no single member from the lower half
of the group is able to manipulate his/her vote to become elected. We also show
that no better guarantee can be given for any value function satisfying
the strict support monotonicity property.

This is joint work with Jurek Czyzowicz and Andrzej Pelc.
 Plus d'infos  


2011-03-14Multipath spanning graphs
14:00-15:00
s. 178
This talk will be about graphs spanners. An (alpha,eta) spanner H of
a graph G is a covering subgraph such that for any pair of vertices u,v
the distance (defined as the length of a shortest path joining the
vertices) in the subgraph is at most alpha times the distance in G plus
eta. Generally spanner constructions are rated with the construction
time and the size of the spanner they yield.

Introduced by Peleg & Alii. spanners are fundamental objects related to
compact routing, distance oracles, distributed distance labelling and so on.

After a brief remainder of the classic constructions which yield
(2k-1,0) (for any positive integer k) and (1,2) spanners we will show it
is possible to extend the definition to account other metrics,
especially metrics which take in account multiple paths. Firstly we will
introduce an *edge*-disjoint multipath metric and show that the two
classic constructions can be extended in such a way to create
(c(2k-1),0) c-multipath spanners and (2,8) 2-multipath spanners on this
metric. Secondly we will show that the notion of spanners is also
sensible on *node*-disjoint multipaths by presenting a construction
which yields a multiplicative spanner on the metric defined by the
smallest *node*-disjoint cycle between two vertices.
 Plus d'infos  


2011-02-14About Lower Bounds on the Bit Complexity and the Execution Time of some Probabilistic Distributed Graph Algorithms
14:00-15:00
s. 178
We present a general framework for proving lower bounds for the bit complexity (and thus the execution time) of some probabilistic distributed graph algorithms and we apply it to the complexity of some problems such as colouring, maximal matching or maximal independent set. We also give impossibility results on the existence of Las Vegas distributed algorithms to break symmetries at distance k for k >= 3.

This is joint work with Y. Métivier, J.M. Robson and N. Saheb
 Plus d'infos  


2011-02-07SkewCCC+: A Heterogeneous Distributed Hash Table
14:00-15:00
s. 178
Distributed Hash Tables (DHTs) enable fully distributed Peer-to-Peer network construction and maintenance with name-driven routing. There exist very few DHT approaches that consider heterogeneity of nodes inside the construction process or properly serve data of different load. To our best knowledge, there is no construction which smoothly addresses both these issues. We propose a Peer-to-Peer construction that explicitly uses heterogeneity to simplify the routing and maintenance process even in the presence of an adaptive adversary. Using a hypercube and cube connected cycles networks as a backbone, we show how to cope with two types of heterogeneity: one for nodes and one for data.

This is joint work with Marcin Bienkowski, André Brinkmann, and Marek Klonowski.
 Plus d'infos  


2011-01-24Fault-tolerance Synchronous Handshake Algorithm for Local Computations
14:00-15:00
Salle 178
This work presents a new probabilistic, synchronization
algorithm to get a handshake between two neighboring nodes in the graph.
This algorithm is designed for an asynchronous distributed network of
anonymous processes which use the message exchange as a model for the
communication. In this work, we use the Event-B method for the
specification and for the proof of correctness. We present a comparative
study between our algorithm and the one proposed by Y. Metivier et al.
(*). We show that our proposal presents a considerable improvement of
the previous one in terms of the number of sent messages and fault
tolerance. We display the effectiveness of our algorithm by
highlighting the importance of its asynchronous aspect on the total
performances of the algorithm.

(*) Metivier, Y., Saheb, N., Zemmari, A.: Randomized rendezvous. In: In
Mathematics and computer science : Algorithms, trees, combinatorics and
probabilities, Trends in mathematics. pp. 183-194. Birkhäuser (2000)
 Plus d'infos  


2011-01-17Dissuasive Methods against Malicious Behaviors in Large Scale Distributed Systems
14:00-15:00
Salle 178
Users of large scale distributed systems deployed in the public domain
do misbehave: MMOG players cheat, file sharing system users free-ride,
and social network users create multiple identities or try to
impersonate people they know. Traditional techniques to deal with
malicious users consist in masking their misbehaviors (e.g., BFT) or
preventing them (e.g., using cryptography). This talk presents dissuasive
methods against malicious behaviors based on distributed verifications:
users check each others actions and report detected faults. We first
illustrate our approach by analyzing an epidemic high-bandwidth
dissemination protocol where the inherent randomness of gossip protocols
allows lightweight collusion-resilient tracking of free-riders. We then
present our work on secured distributed computations in social networks
where the real persons' reputation concern acts as an incentive not to
misbehave.
 Plus d'infos  


2011-01-10Log-space agents for solving anonymous rendezvous and other graph problems
14:00-15:00
Salle 178
In this talk we consider deterministic algorithms for some agent-based
tasks in graphs. Mobile agents are frequently employed to perform
decentralized information management processes, by persistently
traversing or crawling the web, collecting, updating and disseminating
information, and maintaining network integrity.

In the rendezvous problem, two identical (anonymous) mobile agents
start from arbitrary nodes in a graph and move from node to node with
the goal of meeting. A well-known recent result on exploration, due to
Reingold, states that exploration of arbitrary graphs can be performed
in log-space, i.e., using an agent equipped with $O(log n)$ bits of
memory, where $n$ is the size of the graph. Our main result establishes
the minimum size of the memory of anonymous agents that guarantees
deterministic rendezvous when it is feasible. We show that this minimum
size is $Theta(log n)$, where $n$ is the size of the graph, regardless
of the delay between the starting times of the agents.

We also mention some other problems related to map reconstruction, for
which an agent with $Theta(log n)$ bits of memory is sometimes
required and always sufficient.
 Plus d'infos  




Liste des événements répétitifs du groupe Algorithmique Distribuée




Retour
Retour à l'index