Exposés passés
Les exposés ont lieu le Lundi de 14h à 15h, en salle 178.
2015/2016
Lundi 20 juin : Gabriel Triangulations and Angle-Monotone Graphs: Local Routing and Recognition Nicolas Bonichon - (Université de Bordeaux)
Abstract: A geometric graph is \emph{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 angle\hyp 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 \emph{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.
Lundi 30 mai : Randomized Distributed MIS and Colouring Algorithms for Rings with Oriented Edges in O(\sqrt{log n}) bit rounds Akka Zemmari - (Université de Bordeaux)
Abstract: 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
Lundi 23 mai : Relâche
Abstract: On peut éventuellement aller à Algotel qui débute le lendemain https://algotel2016.labri.fr/
Lundi 16 mai : Relâche
Abstract: Lundi de Pentecôte
Lundi 9 mai : Majority population protocols Leszek Gasieniec (University of Liverpool)
Abstract: 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.
Lundi 2 mai : A General Framework for Reusing Proofs of Termination Detection by Refinement-Based Compositions Maha Boussabbeh - (Université de Bordeaux)
Abstract: 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.
Lundi 25 avril : A Faster Counting Protocol for Anonymous Dynamic Networks Alessia Milani - (Université de Bordeaux)
Abstract: 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,
Lundi 18 avril : Relâche
Abstract:
C'est les vaacaaaannnnces
Lundi 11 avril : Jeux sur les graphes Clément Charpentier - (Université de Lyon)
Abstract: 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.
Candidat MCF
Lundi 4 avril : 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) Philippe Duchon - (Université de Bordeaux)
Abstract:
La suite de l'exposé de l'exposé du 29 février
Lundi 28 mars : Relâche
Abstract:
C'est pââââââques
Lundi 21 mars : Deterministic Leader Election in O(D+ log n) Rounds with Messages of size O(1) Yves Métivier - (Bordeaux INP)
Abstract: 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 substantially improves upon the best known algorithm whose bit complexity is O(D log n). In fact, using the lower bound by Kutten et al. and a result of Dinitz and Solomon, we show that the bit complexity is optimal (up to a multiplicative constant). Furthermore, this algorithm requires no knowledge on the graph, such as n or D.
(Travail réalisé avec : A. Casteigts, J.M. Robson, and A. Zemmari)
Lundi 14 mars : Time and Homonyms Considerations over Community Protocols Mikaël Rabie - (LAMSADE, U. Paris Dauphine)
Abstract: 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(n\log 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.
Lundi 7 mars : Time vs. Information Tradeoffs for Leader Election in Anonymous Trees Christian Glacet - (CNR - IEIIT, Torino, Italy)
Abstract:
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.
Lundi 29 février : Le point de vue théorie de l'information et aléatoire sur l'élection de leader (d'après Beauquier, Blanchard, Burman et Guerraoui) Philippe Duchon - (Université de Bordeaux)
Abstract:
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.
Lundi 22 février : Relâche
Abstract:
C'est les vaaaaaaacaaaaances
Lundi 15 février : k-Set Agreement with n − k + 1 Atomic Read/Write Registers Zohir Bouzid - (Université de Bordeaux)
Abstract: 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
Lundi 8 février : Impact de la réplication pour les bases de données distribuées Noël Gillet - (Université Bordeaux )
Abstract: 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
Lundi 1 février : Incentives in distributed systems Paolo Penna - (ETH Zurich)
Abstract: 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.
Lundi 25 janvier : Pré-calcul distribué pour la visualisation interactive de densité pour de grands nuages de points Alexandre Perrot - (LaBRI, MaBIOVIS, Université de Bordeaux)
Abstract:
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.
Lundi 18 janvier : The read/write protocol complex is collapsible Fernando Benavides - (Instituto de Matematicas, UNAM)
Abstract:
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.
Lundi 14 décembre : Beachcombing on Strips and Islands David Ilcinkas - (LaBRI, Université de Bordeaux)
Abstract:
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.
Lundi 7 décembre : Rendezvous of Heterogeneous Mobile Agents in Edge-weighted Networks. Ralf Klasing - (LaBRI, Université de Bordeaux)
Abstract: 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).
Lundi 30 novembre : Machine Learning Approach for Android Apps Analysis Akka Zemmari - (LaBRI, Université de Bordeaux)
Abstract: 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.
Mardi 24 novembre (après-midi): Soutenance de thèse de David Bonnin
Abstract: 14h dans amphi du LaBRI.
Lundi 23 novembre et Mardi 24 novembre (matin): Journées du GT CoA
Abstract: Programme et inscription ici http://5.135.166.57/COA/index.php/welcome/pagePresentation
Lundi 16 novembre : Réunion du thème
Abstract:
Réunion du thème Algo Dist
Lundi 9 novembre : Classification automatique de graphes dynamique Yessin Neggaz - (LaBRI, Université de Bordeaux) /!\ SALLE 75 /!\
Abstract:
É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.
Lundi 2 novembre : On the Uncontended Complexity of Anonymous Consensus Claire Capdevielle - (LaBRI, Université de Bordeaux)
Abstract: 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.
Lundi 26 octobre : Pas d'exposé
On pourra cependant assister le matin à la soutenace de thèse de Vincent Autefage dans l' amphi du LaBRI à 10h dont le titre et le résumé suivent :
''Découverte de services et collaboration au sein d’une flotte hétérogène et hautement dynamique d’objets mobiles communicants autonomes', Vincent Autefage
Résumé:
Les systèmes autonomes sont des objets mobiles communicants capables de réaliser un
certain nombre de tâches sans intervention humaine. Le coût (e.g. argent, poids, éner-
gie) de la charge utile requise pour effectuer certaines missions est parfois trop important
pour permettre aux engins d’embarquer la totalité des capacités nécessaires (i.e. capteurs
et actionneurs). Répartir ces capacités sur plusieurs entités est une solution naturelle à
ce problème. Un tel groupe d’entités constitue une flotte à laquelle devient nécessaire de
fournir un mécanisme de découverte permettant aux différents engins de partager leurs
capacités respectives afin de résoudre une mission globale de façon collaborative. Ce mé-
canisme, outre l’affectation des tâches, doit gérer les conflits et les pannes potentielles qui
peuvent survenir à tout moment sur tout engin de la flotte. Fort de ces constations, nous
proposons un nouveau mécanisme collaboratif nommé AMiRALE qui apporte une solution
aux problèmes ci-dessus pour les flottes hétérogènes d’engins mobiles autonomes. Notre
système est entièrement distribué et repose uniquement sur des communications asyn-
chrones. Nous proposons également un nouvel outil nommé NEmu permettant de créer
des réseaux virtuels mobiles avec un contrôle important sur les propriétés de la topologie
du réseau ainsi que sur la configuration des nœuds et des inter-connexions. Cet outil per-
met la réalisation d’expérimentations réalistes sur des prototypes d’applications réseaux.
Enfin, nous proposons une évaluation de notre système collaboratif AMiRALE au travers
d’un scénario de nettoyage de parc utilisant une flotte autonome de drones et de robots
terrestres spécialisés.
Lundi 19 octobre : Algorithmes auto-stabilisants pour des paramètres de décomposition et de domination dans les graphes Mohammed Haddad - (Université de Lyon 1)
Abstract: 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.
Lundi 12 octobre : On Distinguishing Views in Symmetric Networks. Dominik Pająk - (University of Cambridge)
Abstract:
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
Lundi 5 octobre : Silent Self-stabilizing BFS Tree Algorithms Revised Colette Johnen - (LaBRI, Université de Bordeaux)
Abstract:
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)
Lundi 28 septembre : JBotSim: a tool for fast prototyping distributed algorithms in dynamic networks. Part 2 Arnaud Casteigts - (LaBRI, Université de Bordeaux)
Abstract: La suite de l'exposé du 18 mai. 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.
Lundi 21 septembre : Bridging the Gap between Performance and Bounds of Cholesky Factorization on Heterogeneous Platforms / Planar graphs and power domination + réunion de rentrée du thème Suraj Kumar/Claire Pennarun - (LaBRI, Université de Bordeaux)
Abstract: Nous écouterons Claire et Suraj nous exposer brièvement leur sujet de thèse et leur premiers résultats. Les exposés seront suivi de la réunion de rentrée du thème.
Suraj Kumar: Bridging the Gap between Performance and Bounds of Cholesky Factorization on Heterogeneous Platforms
Abstract: We consider the scheduling problem of Cholesky factorization on heterogeneous system. In this context we investigate how to adding static information based on an offline analysis to the scheduler improve their performance. We are comparing simulated performance with different theoretical bounds which we introduce.
Claire Pennarun: Planar graphs and power domination
2014/2015
Lundi 29 juin 2015 : Spreading Influence in Social Networks with Time Constraints Joseph Peters - (Simon Fraser University)
Abstract: 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.
Lundi 22 juin 2015 : Upper and Lower Bounds for Online Routing on Delaunay Triangulations Nicolas Bonichon - (LaBRI, Université de Bordeaux)
Abstract: 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.
Lundi 15 juin 2015 : Station Assignment with Reallocation Miguel Mosteiro - (Kean University, NJ, USA)
Abstract: 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.
Lundi 8 juin 2015 : Proving correctness of distributed algorithms in a dynamic context. Faten Fakhfakh - (LaBRI, Université de Bordeaux)
Abstract:
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.
Lundi 1er juin 2015 : An overview of computational models for wireless sensor networks Nesrine Ouled Abdallah - (LaBRI, Université de Bordeaux)
Abstract: 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.
Lundi 25 mai 2015 : Pas d'exposé -
Abstract: Pentecôte
Lundi 18 mai 2015 : JBotSim: a tool for fast prototyping distributed algorithms in dynamic networks. Arnaud Casteigts - (LaBRI, Université de Bordeaux)
Abstract: 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.
Lundi 11 mai 2015 : Calculer les distances dans un graphe en temps constant avec des étiquettes de 0.793n bits. Cyril Gavoille - (LaBRI, Université de Bordeaux)
Abstract: 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.
Lundi 4 mai 2015 : Pas d'exposé
On pourra par contre assister au séminaire de Tahiry Razafindralambo qui est candidat prof, même heure, amphi du LaBRI.
Titre : Controlled Mobility in Wireless Networks
Resumé : Mobility is the character or property of an object that has the capacity or the ability to move or be moved. It characterizes all things that can rapidly change shape, appearance or is unstable, variable or fluctuate in time and space. The introduction of mobility in networks is a milestone in the description and implementation of communication systems that must take into account the mobility of one or more entities that comprise this system.
In the early 2000, the research shows that mobility is not all a drawback by pointing out that mobility can increase the capacity, security and covered areas. These results raise two important points: (i) The contribution of mobility described in these articles are considered at application-level if we refer to the OSI model and (ii) mobility is undergone by the users or network entities.
The two points raised above will be addressed from different point of view. Regarding the first point the results I show here consider two aspects. The first issue focuses on the benefits of mobility at the application level and more specifically for coverage in wireless sensor networks. The second aspect considers the use of mobility as a network primitive and uses it to increase the performance of the protocol stack.
Lundi 27 avril 2015 : Pas d'exposé
Abstract: c'est les vacances
Lundi 20 avril 2015 : Extension du domaine algorithmique : les algorithmes de la nature - Ivan Lavallée
Abstract: 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.
Lundi 13 avril 2015 : Verifying parametrized asynchronous systems Anca Muscholl
Abstract: The talk should be a (gentle) introduction to verification problems
for concurrent, asynchronous systems. I will focuss 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
Lundi 6 avril 2015 : Pas d'exposé
Abstract: c'est pââââââques
Lundi 30 mars 2015 : An introduction to Software Transactional Memory - Alessia Milani (Labri, Université de Bordeaux)
Abstract: 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.
Lundi 23 mars 2015 : Algorithmes d'allocation pour le Cloud sous contrainte de fiabilité - Lionel Eyraud-Dubois (LaBRI, INRIA)
Abstract: 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.
Lundi 16 mars : On Distributed Computing with Beeps, la suite Akka Zemmari (LaBRI, Université de Bordeaux)
Abstract: La suite de l'exposé du 2 mars !
Lundi 9 mars 2015: On structural and Chromatic Properties of 1-planar Graphs. - Tomas Madaras (Pavol Jozef Šafárik University)
Abstract:The planar graphs have been, within decades of graph theory research, well explored yielding numerous results on their structural and chromatic properties. Along with this research, analogue problems were investigated for graphs which generalize - in various directions - the planar graphs. A particularly interesting generalization concerns the graph drawings in the plane which allow at most one crossing per edge, rising to the family of so called 1-planar graphs. These graphs, although introduced in late sixties of 20th century, were studied in a deeper detail only in the last decade. We survey known results on the global and local structure and chromaticity of 1-planar graphs with emphasis on similarities and fundamental differences when comparing with planar graphs, and several future research directions on an analogue of Steinberg conjecture for 1-planar graphs.
Remarque: Créneau emprunté par le GT Graphes et Applications
Lundi 2 mars 2015 : On Distributed Computing with Beeps Akka Zemmari (LaBRI, Université de Bordeaux)
Abstract: 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
Lundi 23 février 2015: : Relâche
Abstract: c'est les
Lundi 16 février 2015: Self-Stabilizing Leader Election in Polynomial Steps Stéphane Devismes (Université Joseph Fourier, Grenoble I)
Abstract: 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.
P.S. : Il s'agit d'un exposé CPU.
Lundi 9 février 2015 : 'A Distributed Enumeration Algorithm and Applications to All Pairs
Shortest Paths, Diameter...' Yves Métivier (LaBRI, Université de Bordeaux)
Abstract: 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
Lundi 2 février 2015 : Pas d'exposé
Allez voir les exposés des 'Journées GDR IM' qui se tiennent au LaBRI les 2 et 3 février. Le programme est ici : http://gdrim2015.labri.fr
Lundi 26 janvier 2015 : Periodic Data Retrieval in asynchronous rings with a malicious host - Evangelos Bampas (LaBRI, Université de Bordeaux)
Abstract:
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)
Lundi 19 janvier 2015 : " Équilibrage de charge dans des systèmes distribués" - Noel Gillet (LaBRI, Université de Bordeaux)
Abstract:
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.
(Travail en cours avec Nicolas Hanusse)
Lundi 12 janvier 2015 : "Distributedly Testing Cycle-Freeness" - David Ilcinkas (LaBRI, CNRS and Université de Bordeaux)
Abstract: We tackle 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.
Lundi 15 décembre 2014 : "Splitting and renaming with a majority of faulty processes" - David Bonnin (LaBRI, Université de Bordeaux)
Abstract: 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.
Lundi 08 décembre 2014 : "Maintaining a Spanning Forest in Highly Dynamic Networks: The Synchronous Case" - Yessin Neggaz et Matthieu Barjon, (LaBRI, Université de Bordeaux)
Lundi 01 décembre 2014 : "Towards a General Framework for Searching on a Line and Searching
on m Rays" - Jean-Lou De Carufel (Carleton University)
Abstract: 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).
Lundi 24 novembre 2014 : "ON THE POWER OF ONE BIT: HOW TO EXPLORE A GRAPH WHEN YOU CANNOT BACKTRACK?" - Dominik Pajak, (University of Cambridge)
Abstract: 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.
Lundi 17 novembre 2014 : "Group Search on the Line" - Leszek Gasieniec (University of Liverpool)
Lundi 10 novembre 2014 : "Patrolling by unreliable mobile robots" - Jurek Czyzowicz (Université du Québec en Outaouais)
Abstract: 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.
Lundi 03 novembre 2014 : "Coloration d'un cycle en temps log*(n): borne sup et borne inf" - Cyril Gavoille, (LaBRI, Université de Bordeaux)
Lundi 20 octobre 2014 : "Routage compact en pratique. Peut-on router avec des tables de routage de taille 6 ?" - Nicolas Hanusse , (LaBRI, Université de Bordeaux)
Abstract: 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.
Lundi 03 octobre 2014 : "k-Partitionnement auto-stabilisant " - Yvan Rivierre, (LaBRI, Université de Bordeaux)
Abstract: 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.
Lundi 22 septembre 2014 : Soutenance de thèse de Pierre Halftermeyer : "Connexité dans les Réseaux et Schémas d’Étiquetage Compact d’Urgence " - Amphi du LaBRI, 14h30
Abstract:
On cherche à attribuer à tout sommet x d’un graphe G (à n sommets) une étiquette L(x), idéalement de taille O(log n), permettant de répondre à des requêtes de connexité avec panne Conn(u,v,X).
C’est-à-dire qu’on veut, après un pré-traitement en temps O(|X|) des étiquettes des sommets de l’ensemble «en panne» X, répondre à partir des seules étiquettes L(u) et L(v), en un temps optimal O(log log n), à la question : u et v sont-ils connectés dans G\X ?
On tâchera de traiter ce problème dans les graphes de genre borné ainsi que dans les graphes excluant un mineur fixé.
2014/2013
Lundi 07 juillet 2014 : "Solo-fast Universal Constructions for Deterministic Abortable Objects" - Claire Capdevielle, (LaBRI, Université de Bordeaux)
Abstract: 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 constructionWe 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.
Lundi 30 juin 2014 : "Rendez-vous d'agents mobiles tolérant aux pannes" - Arnaud Labourel, (LIF, Université Aix-Marseille)
'Abstract: 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.
Lundi 23 juin 2014 : "Maintenance d'arbres et détection de déconnexion" - Christian Glacet, (LaBRI, Université de Bordeaux)
Abstract: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.
Lundi 16 juin 2014 : Allyx Fontaine soutient sa thèse "Analyse et preuves formelles d’algorithmes distribués probabilistes" - Amphi du LaBRI
Abstract:
Lundi 05 mai 2014 : "Le codage de réseau aléatoire : une introduction " - Christine Bachoc, (IMB, Université de Bordeaux)
Abstract:
Lundi 05 mai 2014 : "Data Structures for Emergency Planning" - Cyril Gavoille (LaBRI)
Abstract: 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.
Lundi 14 avril 2014 : "Some recent results for labeling schemes" - Stephen Alstrup (University of Copenhagen, DK)
Abstract: We describe methods to assign to each node in a graph a label, such that given the labels of two nodes it is possible to decide (alone from the labels) if they are adjacent in the graph. This is a labeling scheme. The objective is to minimize the maximum number of bits needed to represent a label associated to a node. We will also relate this to induced universal and universal graphs.
We will look at various graphs, and in addition to adjacency, we will also look at distance functions and nearest common ancestor computation in trees. The presentation will cover some recent progress including results from SODA’14.
Lundi 31 mars 2014 : "Algebraic Removal Lemma" - Oriol Serra ( Barcelona, Spain)
Abstract: 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.
Lundi 24 mars 2014 : "Exploration and Diffusion in Graphs using Deterministic Walks " - Adrian Kosowski (LaBRI)
Abstract: 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).
Lundi 03 mars 2014 : "Algorithmes de mise à jour locale pour des graphes aléatoires" - Romaric Duvignau (LaBRI)
Abstract: 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.
Lundi 24 février 2014 : "Distributed anonymous discrete function computation" - Julien Hendrickx(Univ. Louvain)
Abstract: We propose a model for deterministic distributed function computation by a network of identical and anonymous nodes:.
In this model, each node has bounded computation and storage capabilities that do not grow with the network size. Furthermore, each node only knows its neighbors, not the entire graph. Our goal is to characterize the class of functions that can be computed within this model. We provide a necessary condition for computability which we show to be nearly sufficient, in the sense that every function that violates this condition can at least be approximated. The problem of computing (suitably rounded) averages in a distributed manner plays a central role in our development; we provide an algorithm that solves it in time that grows quadratically with the size of the network.
Lundi 17 février 2014 : "The interplay between multidimensional skylines and functional dependencies " - Sofian Maabout (LaBRI)
Abstract: We show how functional dependencies, which are agnostoc to the orders defined over the dimensions domains, can help to optimize skyline queries which, by opposition are based on orders. We present some theoretical and experimental results.
Lundi 10 février 2014 : "Algorithmes auto-stabilisants barvards" - Lélia Blin (LIP6 - Université Pierre et Marie Curie)
Abstract: Dans le contexte des réseaux à grande échelle, la prise en compte des pannes est une nécessité évidente. Ce séminaire traite de l’auto-stabilisation, une méthode qui vise à concevoir des algorithmes distribués se « réparant d’eux-même » en cas de pannes transitoires pouvant impliquer toute modification arbitraire de l’état des processus. Plusieurs paramètres peuvent être pris en compte pour mesurer l’efficacité d’un algorithme auto-stabilisant, dont en particulier le temps de convergence et la complexité mémoire. L’importance du temps de convergence vient de la nécessité évidente pour un système de retrouver le plus rapidement possible un état valide après une panne. La nécessité de minimiser la mémoire vient, d’une part, de l’importance grandissante de réseaux offrant des espaces mémoires restreints, comme par exemple certains réseaux de capteurs, et, d’autre part, de l’intérêt de minimiser à la fois l’échange et le stockage d’information afin de limiter les potentialités de corruption de cette information. Lors de ce séminaire, nous traiterons de la minimisation de la mémoire au travers d'un exemple, à savoir le problème de l’élection d’un leader. Une borne inférieure de Ω(log n) bits de mémoire par noeud a été établie par Dolev, Gouda et Schneider (1999) pour ce problème fondamental. Cette borne n'est toutefois valable que pour des algorithmes silencieux, c'est-à-dire des algorithmes dont les registres ne sont plus modifiés lorsque le système a rejoint un état légitime. Nous verrons que, si l'on autorise l’algorithme à rester bavard (non-silencieux) même après avoir rejoint un état légitime, alors l’espace mémoire peut être amélioré d’un facteur au moins exponentiel.
Lundi 6 Janvier 2014 : "Self-stabilizing k-independent dominating set construction" - Colette Johnen(LaBRI)
Abstract: A k-independent dominating set is a k-independent set and a k-dominating set. A set of nodes, I, is k-independent if the distance between any pair of nodes in I is at least k+1. A set of nodes, D, is a k-dominating if every node is within distance k of a node of D.
I propose two self-self-stabilizing algorithm building k-independent dominating sets. The both algorithm (SID and FID) are silent, and they converge under the unfair distributed scheduler (the weakest scheduling assumption).
The algorithm FID reaches a terminal (also legitimate) configuration in at most 4n+k rounds, where n is the network size. The algorithm FID requires (k+1)log(n+1) bits per node.
The protocol SID is memory efficient : it requires only 2log((k+1)n+1)+1 bits per node. The computation of the convergence time of the protocol SID is opened question.
Lundi 16 Décembre 2013 : "Large-scale Data Stream Analysis" - Yann Busnel (LINA - Université de Nantes)
Abstract: L'objectif de cet exposé est de dresser un court état de l'art autour de l'analyse des flux de données à grande échelle, lesquels sont souvent utilisés pour du monitoring et de la sécurité, à la fois dans les réseaux et les systèmes distribués jusqu'à l'internet des objets. La problématique de ce champs de recherche consiste à extraire de l'information pertinente d'un flux de données en une passe unique (en raison de la taille du flux et de sa rapidité), et ne nécessitant qu'une quantité mémoire très faible et une puissance de calcul très limitée. Je présenterai ensuite les dernières applications utilisant nos résultats récents, lesquels vont de la détection d'intrusion, la détection de DDoS, l'échantillonnage, etc.
Lundi 9 Décembre 2013 : "Simulating weak shared memory" - David Bonnin (LaBRI)
Abstract: It is well known that in an asynchronous message-passing system with crash faults, one can emulate an atomic register providing that more than half of the processes are non-faulty. By contrast, when a majority of the processes may fail, simulating atomic register is not possible.
I will talk about weak variants of atomic registers that can be simulated tolerating a majority of processes failures.
Specifically, I will introduce a new class of registers, called $\alpha$-registers. We found a lower bound of $\alpha = M+1$ with $M=2f-n+2$ for these registers, and an explicit algorithm can emulate them with $\alpha = 2M-1$.
I will also probably talk about other approaches on weak shared memory : $M$-colored registers, and $k$-splitters.
This is a joint work with C. Travers.
Lundi 2 Décembre 2013 : "Spanners planaires de degré borné" - Nicolas Bonichon (LaBRI)
Abstract: This talk considers the question: « What is the smallest maximum degree that can be achieved for a plane spanner of a complete Euclidean graph? » Without the planarity constraint, it is known that the answer is 3 which is also the best known lower bound on the degree of any plane spanner. With the planarity requirement, the best known upper bound on the maximum degree is 6, the last in a long sequence of results improving the upper bound. In this talk we show that the complete Euclidean graph always contains a plane spanner of maximum degree 4.
Lundi 25 Novembre 2013 : "Optimal Bit Complexity Randomised Distributed MIS and Maximal Matching Algorithms for Anonymous Rings" - Allyx Fontaine (LaBRI)
Abstract: We present and analyse Las Vegas distributed algorithms which compute a MIS or a maximal matching for anonymous rings. Their bit complexity and time complexity are $O(\sqrt{\log n})$ with high probability. These algorithms are optimal modulo a multiplicative constant. Beyond the complexity results, the interest of this work stands in the description and the analysis of these algorithms which may be easily generalised. Furthermore, these results show a separation between the complexity of the MIS problem (and of the maximal matching problem) on the one hand and the colouring problem on the other. Colouring can be computed only in $\Omega(\log n)$ rounds on rings with high probability, while MIS is shown to have a faster algorithm. This is in contrast to other models, in which MIS is at least as hard as colouring.
This is joint work with Y. Métivier, J.M. Robson and A. Zemmari
Lundi 4 Novembre 2013 : "Palindrome Recognition In The Streaming Model" - Frederik Mallmann-Trenn, (Simon Fraser University)
----
Lundi 28 Octobre 2013 : "The Case for Reliable Software Transactional Networking" - Petr Kuznetsov (Paristech)
Abstract: Software-defined networking (SDN) is a novel paradigm that out-sources the control of packet-forwarding switches to a set of software controllers. The most fundamental task of these controllers is the correct implementation of the network policy, i.e., the intended network behavior. In essence, such a policy specifies the rules by which packets must be forwarded across the network. We initiate the study of the SDN control plane as a distributed system.
We introduce a formal model describing the interaction between the data plane and a distributed control plane (consisting of a collection of fault-prone controllers). Then we formulate the problem of consistentcomposition of concurrent network policy updates. The composition is enabled via a transactional interface with all-or-nothing semantics, which allows us to reason about possibilities and impossibilities in controller synchronization.
Lundi 14 Octobre 2013 : "The philosopher diner revisited : a new algebraic approach for an old modeling problem ?" - David Janin, (LaBRI)
Abstract: In the field of distributed algorithm, the philosopher diner is a typical algorithmical and modeling problem. How to model distributed states ? Local transitions ?
Their combinations ? Resulting global transitions ? Correctness criterion ? There are many already many modeling proposal. In this talk, we will provide yet another one.
We will show how inverse semigroup theory -- a mathematical theory developed since the 50's yet quite unknown in computer science -- and the associated language theory provide robust concepts and tools for that modeling. This is a joint (exploratory) work with Anne Dicky to be presented at MSR 2013.
Lundi 23 Septembre 2013 : "Computing Connected Components, Distributed DisasterDisclosure, and Event Extent Estimation" - Miroslaw Korzeniowski
Abstract: Decentralized monitoring and alarming systems can be an attractive
alternative to centralized architectures. Distributed sensor nodes
(e.g., in the smart grid's distribution network) are closer to an
observed event than a global and remote observer or controller. This
improves the visibility and response time of the system. Moreover, in
a distributed system, local problems may also be
handled locally and without overloading the communication network.
This article initiates the study of alarming from a distributed computing perspective and under two fundamentally different scenarios: \emph{on-duty} and \emph{off-duty}. We model the alarming system as a sensor network consisting of a set of distributed nodes performing local measurements to sense events. In order to avoid false alarms, the sensor nodes cooperate and only escalate an event (i.e., raise an alarm) if the number of sensor nodes sensing an event exceeds a certain threshold. In the on-duty scenario, nodes not affected by the event can actively help in the communication process, while in the off-duty scenario non-event nodes are inactive.
This article presents and analyzes algorithms that minimize the reaction time of the monitoring system while avoiding unnecessary message transmissions. Moreover, lower bounds are derived that shed light on the limitations of distributed alarming systems.
Lundi 16 Septembre 2013 : "A General Technique for Non-blocking Trees" - Faith Ellen, (University of Toronto)
Abstract: We describe a general method for obtaining non-blocking implementations of a large class of tree structures where pointers are directed
from parents to children. Our construction uses LLX and SCX operations, which are multi-word generalizations of the standard LL (load-link) and SC (store-conditional) operations. These operations are, in turn, implemented from single-word CAS instructions. A non-blocking implementation of a chromatic tree will be described as an example. Its height is guaranteed to be O(log n + c), where n is the number of keys stored in the tree and c is the number of incomplete update operations.
This is joint work with Trevor Brown and Eric Ruppert.
2012/2013
Lundi 8 Juillet 2013 : "Dynamic Resource Allocation in Cloud Computing platforms" - Lionel Eyraud-Dubois (Labri)
Abstract: 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.
Lundi 10 Juin 2013 : " The Heard-Of model: computing in distributed systems with benign failures" - Bernadette Charron-Bost (CNRS, Ecole polytechnique, Paris)
Abstract: 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
Lundi 3 Juin 2013 : "Introduction to renaming" - Corentin Travers (Labri)
Abstract: 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.
Lundi 27 Mai 2013 : " Exploration des graphes dynamiques T-intervalle-connexes : le cas de l'anneau" - Wade Ahmed (Labri)
Abstract: 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.
Keywords : Graphe dynamique, exploration, T-intervalle-connexité, agent mobile
Lundi 13 Mai 2013 : " Calcul Distribué et Fouille de Données" - Nicolas Hanusse (Labri)
Abstract: 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.
Lundi 22 Avril 2013 : " A peer-to-peer-based virtual environment system" - Eliya Buyukkaya (ENSSAT-Université de Rennes I)
Abstract: 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.
Lundi 15 Avril 2013 : " Algorithms for the Vertex Cover Problem on Large Graphs with Low Memory Capacities" - Romain Campigotto (LIP6-Paris)
Abstract: 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).
Lundi 8 Avril 2013 : "Implémentation d'algorithmes distribués à l'aide de Visidia" - Mohamed Mosbah (Labri)
Abstract: 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).
Lundi 25 Mars 2013 : "Simultaneous Consensus vs Set Agreement." - Zohir Bouzid (LIP6-Paris)
Abstract: 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.
Lundi 18 Mars 2013 : "Vers une classification des réseaux dynamiques en fonction des problèmes qu'on peut y résoudre." - Arnaud Casteigts (Labri)
Abstract: 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.
Lundi 25 Février 2013 : "Sur les 1001 modèles en algorithmique distribuée." - Yves Metivier (Labri)
Abstract: 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.
Lundi 18 Février 2013 : "Distributed Calculation of Graph Diameter" - Mike Robson (Labri)
Abstract: 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.
This is joint work with Yves Métivier and Akka Zemmari.
Lundi 11 Février 2013 : "Bounds for Communication in Wireless Grids" - Joseph Peters (Simon Fraser University)
Abstract: 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.
Lundi 04 Février 2013 : "Distributed Detection of Clone Attacks in Wireless Sensor Networks" - Mauro Conti (University of Padua, Italy)
Abstract: 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.
Lundi 28 Janvier 2013 : "Distributed Exclusive Graph Searching in Trees" - Janna Burman (LRI-Université Paris-Sud)
Abstract: 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.
Lundi 21 Janvier 2013 : "Présentation de Keep Alert, une solution pour la surveillance de marques sur Internet" - Anthony Don (Keep Alert)
Abstract: 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.
Lundi 14 Janvier 2013 : "Two Monte-Carlo Election Algorithms for Anonymous Graphs without any Initial Knowledge" - Akka Zemmari (Labri)
Abstract: 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 $c\geq 1$. The size of messages is $O\left((\log n)(\log^* n)^2 \right)$ with probability $1-o(n^{-c})$ for any $c\geq 1$; their expected size is $O\left((\log n)(\log^* n) \right)$.
This is a joint work with Y. Métivier and J. M. Robson
Lundi 10 Décembre 2012 : pas de seminaire. Soutenance de thèse-Florent Foucaud.
Lundi 3 Décembre 2012 : "Progress and Challenges for Labeling Schemes" - Cyril Gavoille (Labri)
Abstract: 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.
Lundi 26 Novembre 2012: "Competitive Routing on a Variant of the Delaunay Triangulation" - Prosenjit Bose (Carleton University)
Abstract: A subgraph H of a weighted graph G is a t-spanner of G provided that for every edge xy in G, the weight of the shortest path between x and y in H is at most t times the weight of xy. It is known that the Delaunay triangulation of a point set P (where the empty region is an equilateral triangle) is a 2-spanner of the complete Euclidean graph. We present a new and simple proof of this spanning ratio that allows us to route competitively on this graph. Specifically, we present a deterministic local routing scheme that is guaranteed to find a short path between any pair of vertices in this Delaunay triangulation. We guarantee that the length of the path is at most 5/sqrt(3) times the Euclidean distance between the pair of vertices. Moreover, we show that no local routing scheme can achieve a better competitive spanning ratio thereby implying that our routing scheme is optimal. This is somewhat surprising since the spanning ratio is 2. Finally, we showed how this routing scheme can be extended to route on some bounded degree subgraphs of this Delaunay triangulation.
Lundi 19 Novembre 2012: " Reliable Service Allocation in Clouds"- Lionel Eyraud-Dubois, Olivier Beaumont (Labri)
Abstract: We consider several reliability problems that arise when allocating applications to processing resources in a Cloud computing platform. More specifically, we assume on the one hand that each computing resource is associated to a capacity constraint and to a probability of failure. On the other hand, we assume that each service runs as a set of independent instances of identical Virtual Machines, and that the Service Level Agreement between the Cloud provider and the client states that a minimal number of instances of the service should run with a given probability. In this context, given the capacity and failure probabilities of the machines, and the capacity and reliability demands of the services, the question for the cloud provider is to find an allocation of the instances of the services (possibly using replication) onto machines satisfying all types of constraints. In this paper, our goal is to assess the impact of the reliability constraint on the complexity of resource allocation problems. We consider several variants this problem, depending on the number of services (one or many) and if their reliability demand is individual or global. We prove several fundamental complexity results ($\#$P and NP-completeness results) and we provide several optimal and approximation algorithms. In particular, we prove that a basic randomized allocation algorithm, that is easy to implement, provides optimal or quasi-optimal results in several contexts, and we show through simulations that it also achieves very good results in more general settings.
Lundi 12 Novembre 2012 : "MAXIMUM MATCHING IN MULTI-INTERFACE NETWORK"- Dominik Pająk (LaBRI)
Abstract: In heterogeneous networks, devices can communicate by means of multiple wireless interfaces. By choosing which interfaces to switch on at each device, several connections might be established. That is, the devices at the endpoints of each connection share at least one active interface. In this paper, we consider the standard matching problem in the context of multi-interface wireless networks. The aim is to maximize the number of parallel connections without incurring in interferences.
Lundi 5 Novembre 2012 : pas de séminaire
Lundi 22 Octobre 2012 : Christian Glacet (LaBRI)
Lundi 15 Octobre: " NETWORK VERIFICATION VIA ROUTING TABLE QUERIES" - Ralf Klasing (LaBRI)
Abstract: 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(logn)-approximation algorithm to verify a network of diameter 2, and we give exact polynomial-time algorithms for paths, trees, and cycles of even length.
Lundi 8 Octobre 2012 : pas de séminaire
Lundi 1er Octobre 2012 : Réunion de rentrée du thème - Nicolas Hanusse (LaBRI)
Abstract: L'ordre du jour:
- projets: thèse, région, ingénieur, conférence
- organisation du groupe de travail: exposé à venir (projets à long terme, discussion sur les modèles, logiciels, ...), vitrine
- mise-à-jour site web
- enseignement: état des lieux des enseignements locaux
- stages X, ENS, ...
Lundi 21 Juin : "ABOUT RANDOMISED DISTRIBUTED GRAPH COLOURING AND GRAPH PARTITION ALGORITHMS" - Akka Zemmari (LaBRI)
Abstract: We present and analyse a very simple randomised distributed vertex
colouring algorithm for arbitrary graphs of size $n$ that halts in time
$O(log n)$ with probability $1-o(n^{-1}).$ Each message
containing $1$ bit, its bit complexity per channel is $O(log n)$.
From this algorithm, we deduce and analyse a randomised distributed
vertex colouring algorithm for arbitrary graphs of maximum degree
$Delta$ and size $n$ that uses $Delta+1$ colours and halts in time
$O(log n)$ with probability $1-o(n^{-1}).$
We also obtain a partition algorithm for arbitrary graphs of size $n$
that builds a spanning forest in time $O(log n)$ with probability
$1-o(n^{-1})$. We study some parameters such as the number, the size
or the radius of trees of the spanning forest.
We assume that graphs are anonymous; we only assume that each vertex
distinguishes between its neighbours by locally known channel
names. Furthermore we do not assume that the size (or an upper bound
on the size) of graphs is known.
Joint work with Y. Métivier, N. Saheb and J.M. Robson
Lundi 14 Juin : Almost optimal asynchronous rendezvous in infinite multidimensional grids - Arnaud Labourel (LaBRI)
Abstract: Dans cet exposé, je montrerais comment deux agents mobiles peuvent se rencontrer dans une grille infinie de dimension supérieure à 2. On considère le modèle asynchrone. C'est-à-dire que la durée de traversée de chaque sommet par un agent est déterminée par un adversaire omniscient qui essaye d'empêcher le rendez-vous. On supposera que chaque agent connait sa position dans la grille mais pas celle de l'autre agent. Cette connaissance permet d'avoir un algorithme de rendez-vous ayant un coût, mesuré en terme de distance parcourue par les agents, quasiment optimal.