 |
 |
|
Liste des événements uniques du groupe Algorithmique Distribuée
| 2013-06-10 | The Heard-Of model: computing in distributed systems with benign failures |
14:00-15:00 Salle 178 |
Problems in fault-tolerant distributed computing have been studied in a va- riety of system models. These models are all based on the principle that it is usefull and even necessary to specify why and by whom errors occur. In this talk, we question this principle, and present a general computational model, called the Heard-Of model, suitable for describing any type of system, be it message passing, shared memory, synchronous, or asynchronous.
In this model, computations evolve in rounds, and communication missed at a round is definitely lost. Only information transmission is represented: for each round r and each process p, our model specifies the set of processes that p “hears of” at round r (heard-of set) namely the processes from which p receives some message at round r. The features of a specific system are thus captured as a whole, just by a predicate over the collection of heard-of sets. Thus the Heard-Of model allows us to handle all types of benign failures, static or dynamic, permanent or transient, in a unified framework. Moreover, it unifies the most seemingly unrelated notions in distributing computing, namely synchrony and asynchrony.
We further demonstrate how this unifying framework leads to new results and insights in fault-tolerant distributed computing. In particular, we show that some fundamental results for asynchronous systems can be advantageously transferred to synchronous systems. We also examine Consensus algorithms in the Heard-Of model: we show how our approach allows us to devise new solutions and to give simple correctness proofs of existing algorithms like Paxos.
Joint work with André Schiper (EPFL) |
| | Plus d'infos |
|
| 2013-05-27 | Exploration des graphes dynamiques T-intervalle-connexes : le cas de l'anneau |
14:00-15:00 Salle 178 |
Dans cet exposé, je vais parler de l'étude des graphes dynamiques T-intervalle-connexes du point de vue du temps nécessaire à leur exploration par une entité mobile (agent). Un graphe dynamique est T-intervalle-connexe (T geq 1) si pour chaque fenêtre de T unités de temps, il existe un sous-graphe couvrant connexe stable. Cette propriété de stabilité de connexion au cours du temps a été introduite par Kuhn, Lynch et Oshman~cite{KLO10} (STOC 2010). Nous nous concentrons sur le cas où le graphe sous-jacent est un anneau de taille n et nous montrons que la complexité en temps en pire cas est de 2n-T-Theta(1) unités de temps si l'agent connaît la dynamique du graphe, et n+ frac{n}{max{1,T-1}} (delta-1) pm Theta(delta) unités de temps sinon, où delta est le temps maximum entre deux apparitions successives d'une arête. |
| | Plus d'infos |
|
| 2013-05-13 | Calcul Distribué et Fouille de Données |
14:00-15:00 salle 178 |
L'avènement de la production massive de données et la volonté de les exploiter sont limités par les systèmes de gestion de bases de données relationnelles classiques. Cet exposé consiste en une discussion sur les enjeux et problèmes algorithmiques engendrés par le calcul distribué et parallèle. Le calcul de corrélations servira d'illustration. C'est un travail en cours avec Sofian Maabout et Eve Garnaud.
|
| | Plus d'infos |
|
| 2013-04-22 | A peer-to-peer-based virtual environment system |
14:00-15:00 Salle 178 |
Virtual environments (VEs) are 3-D virtual worlds in which a huge number of participants play roles and interact with their surroundings through virtual representations called avatars. VEs are traditionally supported by a client/server architecture. However, centralized architectures can lead to bottleneck on the server due to high communication and computation overhead during peak loads. Thus, P2P overlay networks are emerging as a promising architecture for VEs. However, exploiting P2P schemes in VEs is not straightforward, and several challenging issues related to data distribution and state consistency should be considered.
One of the key aspects of P2P-based VEs is the logical platform consisting of connectivity, communication and data architectures, on which the VE is based. The connectivity architecture is the overlay topology structure, which defines how peers are connected to each other. The communication architecture is the routing protocol defining how peers can exchange messages, while the data architecture defines how data are distributed over the logical overlay. The design of these architectures has significant influence on the performance and scalability of VEs.
First, we propose a scalable connectivity architecture based on a new triangulation algorithm reducing maintenance cost of the system. Second, we construct a communication architecture built on top of the connectivity architecture ensuring that each message reaches its intended destination. Finally, we propose a data architecture ensuring the management of data with different characteristics in terms of mobility in the VE, while providing a fair data distribution and low data transfer between peers in the VE. |
| | Plus d'infos |
|
| 2013-04-15 | Algorithms for the Vertex Cover Problem on Large Graphs with Low Memory Capacities |
14:00-15:00 Salle 178 |
Most of the known optimization algorithms need to explore, mark, modify, etc. the instance given as input before producing their results. To do that, the instance is entirely loaded into the memory of the computer and is manipulated by the algorithm. Often, "extra" data structures are also necessary to memorize parameters useful all along the computation or to update the current solution that will be returned as the final product of the program. However, this classical model is no more adapted for many new computing applications. Indeed, nowadays, many fields such as biology, meteorology, finance, etc. produce very large amount of data.
In our works, we have focused on the Vertex Cover problem on huge graphs: in the intrinsic NP-completeness is added the difficulty to manipulate graphs with severe constraints (mainly related to the low memory capacities). We defined a treatment model combining some properties of several existing models in the literature: streaming, online, I/O-efficient, etc. We initially considered three approximation algorithms, which are memory-efficient (they use a memory space in O(log n) bits). We analyzed their performance in terms of solution quality and complexity, in mean and worst cases. We then focused on algorithms that use memory space of n bits. We showed that it could be very worst with strictly less than n bits memory space. Subsequently, we conducted experiments on very large graphs (in the order of billions of vertices and edges). This study showed that in practice, memory-efficient algorithms are better suited to handle large graphs.
This is joint work with Eric Angel (IBISC, Univ. Évry) and Christian Laforest (LIMOS, ISIMA, Clermont-Ferrand). |
| | Plus d'infos |
|
| 2013-04-08 | Implémentation d'algorithmes distribués à l'aide de Visidia |
14:00-15:00 Salle 178 |
Dans le cadre du projet visidia, une plate-forme logicielle est développée pour l'implantation et la visualisation d'algorithmes distribués. Après une introduction et quelques rappels, l'exposé consistera en une présentation de la plate-forme et de son utilisation pour programmer des exemples d'algorithmes. L'interface et l'API permettent de visualiser l'exécution d'algorithmes, d'implanter de nouveaux algorithmes, ou d'effectuer des statistiques. Les algorithmes peuvent être exprimés selon plusieurs modèles (calculs locaux, passage de messages, agents mobiles). |
| | Plus d'infos |
|
| 2013-03-25 | Simultaneous Consensus vs Set Agreement |
14:00-15:00 Salle 178 |
In the traditional consensus task, processes are required to agree on a common value chosen among the initial values of the participants. It is well known that consensus cannot be solved in crashed-prone, asynchronous distributed systems. Two generalizations of the consensus problem have been introduced: k-set agreement and k-simultaneous consensus. The k-set agreement task has the same requirements as consensus except that processes are allowed to decide up to k distinct values. In the k-simultaneous consensus task, each process participates simultaneously in k instances of consensus and is required to decide in at least one of them; any two processes deciding in the same instance must decide the same value. In this talk, we compare the computability of these problems in two central models in distributed computing: shared memory and message passing. We show that even though the two problems are equivalent in shared memory, k-simultaneous consensus is strictly harder than k-set agreement in the message passing model. This result will serve as a basis for a discussion about different models of computation and their respective power. |
| | Plus d'infos |
|
| 2013-03-18 | Vers une classification des réseaux dynamiques en fonction des problèmes qu'on peut y résoudre. |
14:00-15:00 salle 178 |
Derrière les notions de "graphe dynamique" ou de "réseau dynamique" se cache une très grande diversité de scénarios et d'hypothèses, allant de réseaux semi-statiques où la connexité est toujours assurée à des réseaux complètement mobiles, où la connexité ne s'établit qu'à travers le temps et l'espace (e.g. DTNs). Dans cet exposé, résolument transversal, je présenterai l'état d'avancement de nos recherches autour de la question suivante : quel lien existe-t-il entre la "faisabilité" de tâches distribuées et la dynamique du réseau. Les hypothèses résultantes sur la dynamique peuvent être vues comme autant de classes de graphes (ou alternativement, comme autant de puissances possibles pour un adversaire qui contrôlerait la topologie). Nous avons à ce jour caractérisé et/ou recensé une petite vingtaine de classes de ce type.
Certains de ces travaux ont été menés en collaboration avec Serge Chaumette et Afonso Ferreira. D'autres avec Paola Flocchini et Nicola Santoro. |
| | Plus d'infos |
|
| 2013-02-25 | Sur les 1001 modèles en algorithmique distribuée |
14:00-15:00 salle 178 |
Le but de cet "exposé-discussion" est de présenter quelques modèles en algorithmique distribuée et d'échanger sur leurs liens et leurs mérites. |
| | Plus d'infos |
|
| 2013-02-18 | Distributed Calculation of Graph Diameter |
14:00-15:00 Salle 178 |
We consider the problem of calculating the diameter of a graph given that there is a single vertex "Leader" and neighbouring vertices can exchange
messages of a single bit at each round. We show that this can be achieved in the same O(n) time complexity as well known algorithms without this bound on
message length.
The techniques used can be applied to a number of other graph computations. We consider briefly how the algorithm behaves if applied in a situation where more than one vertex considers itself the Leader.
Joint work with Yves Métivier and Akka Zemmari |
| | Plus d'infos |
|
| 2013-02-11 | Bounds for Communication in Wireless Grids |
14:00-15:00 Salle 178 |
In a wireless network, a transmission can be received by a node if it is
close enough to the sender. However, transmissions can interfere with
each other and the interference distance is typically greater than the
reception distance. Efficient communication protocols in these networks
minimize the time to move information without interference.
In this talk, I will describe optimal protocols for the problem of collecting
information into a central node of a two-dimensional square or hexagonal
grid graph. The optimality of the protocols is proved using a new lower
bound technique that is an adaptation to a discrete environment of a
method based on linear programming duality for continuous flows.
This is joint work with Jean-Claude Bermond, CNRS-INRIA-University of Nice. |
| | Plus d'infos |
|
| 2013-02-04 | Distributed Detection of Clone Attacks in Wireless Sensor Networks |
14:00-15:00 Salle 178 |
Wireless Sensor Networks (WSNs) are often deployed in hostile environments where an adversary can physically capture some of the nodes, first can reprogram, and then, can replicate them in a large number of clones, easily taking control over the network. A few distributed solutions to address this fundamental problem have been recently proposed. However, these solutions are not satisfactory. First, they are energy and memory demanding: A serious drawback for any protocol to be used in the WSN-resource-constrained environment. Further, they are vulnerable to the specific adversary models that we introduced. The contributions of our work are threefold. First, we analyze the desirable properties of a distributed mechanism for the detection of node replication attacks. Second, we show that the known solutions for this problem do not completely meet our requirements. Third, we propose a new self-healing, Randomized, Efficient, and Distributed (RED) protocol for the detection of node replication attacks, and we show that it satisfies the introduced requirements. Finally, extensive simulations show that our protocol is highly efficient in communication, memory, and computation; is much more effective than competing solutions in the literature; and is resistant to the new kind of attacks introduced in our work, while other solutions are not.
|
| | Plus d'infos |
|
| 2013-01-28 | Distributed Exclusive Graph Searching in Trees |
14:00-15:00 Salle 178 |
We consider a version of the well known graph searching problem, where a team of robots aims at clearing the contaminated edges of a graph. We study graph searching in the model of mobile computing where autonomous deterministic robots move between the graph nodes when operating in asynchronous cycles of Look-Compute-Move. Moreover, motivated by physical constraints, following some recent works, we consider the exclusivity property, stating that no two or more robots can occupy a same node at the same time. In addition, we assume that all the graph elements and the robots are anonymous. Robots are oblivious and have no sense of direction. Our objective is to characterize for a graph $G$, the set of integers $k$ such that graph searching can be achieved by a team of $k$ robots starting from any $k$ distinct nodes in $G$. Our main result consists in a full characterization for any asymmetric tree. Towards providing a characterization in the general case, including trees with non-trivial automorphisms, we provide a set of positive and negative results, including a full characterization for any line. All our positive results are based on the design of algorithms enabling perpetual graph searching to be achieved with the desired number of robots. We prove that, in addition to the distributed nature of our setting, the exclusivity property has a significant impact on the nature of the graph searching problem. Hence, the design of the algorithms requires to invent new methods. |
| | Plus d'infos |
|
| 2013-01-21 | Présentation de Keep Alert, une solution pour la surveillance de marques sur Internet |
14:00-15:00 Salle 178 |
A destination des cabinets de propriété industrielle et des services juridiques, Keep Alert propose des surveillances de marque parmi les noms de domaine, les régies publicitaires et les réseaux sociaux.
Anthony DON, directeur technique chez Keep Alert, présentera au groupe de travail, le fonctionnement global de la plateforme, puis abordera les problématiques actuelles et les perspectives de développement relatives à l'algorithmique distribuée. |
| | Plus d'infos |
|
| 2013-01-14 | Two Monte-Carlo Election Algorithms for Anonymous Graphs without any Initial Knowledge |
14:00-15:00 Salla 178 |
The paper proposes and analyses two Monte Carlo election algorithms for anonymous graphs without any initial knowledge. Both have a time complexity equal to $O(D)$, where $D$ is the diameter of the graph. The first is correct with probability $1-o(n^{-1})$ (where $n$ is the size of the graph). The size of messages is $O(log n)$ with probability $1-o(n^{-1})$ and the expected value of the size of messages is also $O(log n)$. The second is correct with probability $1-o(n^{-c})$ for any $cgeq 1$. The size of messages is $Oleft((log n)(log^* n)^2
ight)$ with probability $1-o(n^{-c})$ for any $cgeq 1$; their expected size is $Oleft((log n)(log^* n)
ight)$.
This is a joint work with Y. Métivier and J. M. Robson |
| | Plus d'infos |
|
| 2012-12-03 | Progress and Challenges for Labeling Schemes |
14:00-15:00 Salle 178 |
A fundamental question in Distributed Computing is to understand how localized and how much information are required to solve a task on a network. Typically, if the distance between any pair x,y of nodes in a network is asked, we would like to know which minimal information about x and y in the network are needed. The goal in labeling schemes is precisely to understand how much information must be attached to the nodes (formalized as labels) to solve a graph problem assuming the answer can be determined solely on the basis of the labels of the nodes invoked in the query. In this talk, I give a survey on labeling schemes, present some recent results with their techniques, and highlight new challenges. |
| | Plus d'infos |
|
| 2012-10-22 | Toward a compact distributed routing scheme |
14:00-15:00 s. 178 |
Current routing scheme used for inter-domain routing has
scaling issues (linear routing tables size).
In this GT, I'll present an distributed alternative to this classical
shortest path routing, compact routing.
A routing scheme is said to be compact if routing tables used have
sub-linear size.
|
| | Plus d'infos |
|
| 2012-10-15 | Network Verification via Routing Table Queries |
14:00-15:00 s. 178 |
We address the problem of verifying the accuracy of a map of a network by making as few measurements as possible on its nodes. This task can be formalized as an optimization problem that, given a graph G=(V,E), and a query model specifying the information returned by a query at a node, asks for finding a minimum-size subset of nodes of G to be queried so as to univocally identify G. This problem has been faced w.r.t. a couple of query models assuming that a node had some global knowledge about the network. Here, we propose a new query model based on the local knowledge a node instead usually has. Quite naturally, we assume that a query at a given node returns the associated routing table, i.e., a set of entries which provides, for each destination node, a corresponding (set of) first-hop node(s) along an underlying shortest path. First, we show that any network of n nodes needs Omega(log log n) queries to be verified. Then, we prove that there is no o(log n)-approximation algorithm for the problem, unless P=NP, even for networks of diameter 2. On the positive side, we provide an O(log n)-approximation algorithm to verify a network of diameter 2, and we give exact polynomial-time algorithms for paths, trees, and cycles of even length.
This is joint work with Evangelos Bampas, Davide Bilo, Guido Drovandi, Luciano Guala and Guido Proietti.
Intervenant: Ralf Klasing |
| | Plus d'infos |
|
| 2012-07-16 | From self-stabilizing to self-stabilizing with service guarantee weight-based clustering |
14:00-15:00 s. 076 |
I will present a generic scheme to transform a silent self-stabilizing 1-hop weight-based clustering protocol, called original protocol P, to a self-stabilizing with service guarantee protocol, called the transformed protocol TP. TP requires only 2 bits more than P. Moreover, starting from an arbitrary configuration, TP reaches a safe conguration in at most 3 rounds, where the following useful minimal service is provided: "each node belongs to a 1-hop cluster having an effectual leader". Afterwards, TP reaches a terminal configuration in at most 4*SP rounds where SP is the stabilization time of P protocol. During stabilization of TP protocol, the minimal service is preserved, so the clustering structure is available throughout the entire network.
Intervenant: Fouzi Mekhaldi |
| | Plus d'infos |
|
| 2012-07-03 | Some algorithms for replica placement with distance constraints in tree networks |
14:00-15:00 s. 076 |
The problem of replica placement in tree networks subject to server capacity and distance constraints is considered. The client requests are known beforehand, while the number and location of the servers are to be determined. The Single policy enforces that all requests of a client are served by a single server in the tree, while in the Multiple policy, the requests of a given client can be processed by multiple servers, thus distributing the processing of requests over the platform. For the Single policy, we prove that all instances of the problem are NP-hard, and we propose approximation algorithms. The problem with the Multiple policy was known to be NP-hard with distance constraints, but we provide a polynomial time optimal algorithm to solve the problem in the particular case of binary trees when no request exceeds the server capacity.
Intervenant: Hubert Larchevêque |
| | Plus d'infos |
|
| 2012-06-25 | Evolutionary Dynamics on Undirected Networks |
14:00-15:00 s. 178 |
Evolutionary dynamics have been traditionally studied in the contect of homogeneous populations, mainly described by the Moran Process. Recently, this approach has been generalized by Lieberman, Hauert and Nowak [Nature, 2005], by arranging individuals on the nodes of a connected directed network. Our work focuses on evolutionary models for undirected networks which seem to have a smoother behaviour.
We present the first class of undirected graphs which act as suppressors of selection (i.e. have smaller fixation probability than the clique). We also show how to compute fixation probabilities in any undirected graph via a fully polynomial randomized approximation scheme. In addition we present a new alternative evolutionary model in which all individuals act simultaneously and the result is a compromise between aggressive and non-aggressive individuals. So, we consider also aggregation as opposed to "all or nothing" strategy implied by the generalized Moran process.
This is recent joint work with (a)G. Mertzios, S. Nikoletseas and Ch. Raptopoulos [WINE 2011] and (b) with J. Diaz, L.A. Goldberg, G. Mertzios, D. Richerby and M. Serna [SODA 2012].
Intervenant: George B. Mertzios |
| | Plus d'infos |
|
| 2012-06-18 | Convergecast by Power-Aware Mobile Agents |
14:00-15:00 s. 076 |
A set of identical, mobile agents is deployed in a network. Every network edge has a weight representing the distance between its endpoints. Each agent possesses a battery - a power source allowing to move along the network edges. Agents’ movement uses its battery proportionally to the distance travelled. The agent may stop at any point of network edge. Agents have a simple sensing device permitting to detect other agents - present at the same time at the same point of the network. At the beginning each agent has its initial information. The agents may exchange their information when they meet. The agents collaborate in order to achieve a common goal, which is convergecast, i.e., the initial information of all agents must be eventually concentrated at one agent. We investigate what is the minimal value of power, initially available to all agents, so that convergecast may be achieved. We study the problem in the centralized setting, when the problem must be solved by a centralized authority knowing the network and the initial positions of all agents in the network, and in the distributed setting, when each agent has to perform an algorithm being unaware of its initial position and the presence of other agents.
Intervenant: Jurek Czyzowicz |
| | Plus d'infos |
|
| 2012-06-11 | Leader Election for Anonymous Asynchronous Agents in Arbitrary Networks |
14:00-15:00 s. 076 |
We consider the problem of leader election among mobile agents
operating in an arbitrary network modeled as an undirected graph.
Nodes of the network are unlabeled and all agents are identical. Hence the
only way to elect a leader among agents is by exploiting asymmetries
in their initial positions in the graph. Agents do not know the graph or
their positions in it, hence they must gain this knowledge
by navigating in the graph and share it with other agents to accomplish
leader election. This can be done using meetings of agents, which is
difficult because of their asynchronous nature:
an adversary has total control over the speed of agents. When can a leader
be elected in this adversarial scenario and how to do it?
We give a complete answer to this question by characterizing all initial
configurations for which leader election is possible and by constructing
an algorithm that accomplishes leader election for all configurations for
which this can be done.
This is joint work with Andrzej Pelc.
Intervenant: Dariusz Dereniowski |
| | Plus d'infos |
|
| 2012-06-04 | Calcul distribué de requêtes type ``horizon'' (Skyline) |
14:00-15:00 s. 076 |
L'exposé discutera des résultats présentés à EDBT'11 dans:
"Efficient Execution Plans for Distributed Skyline Query Processing
João B. Rocha-Junior, Akrivi Vlachou, Christos Doulkeridis, and Kjetil Nørvåg"
Etant donné un ensemble O d'objets décrits chacun par n attributs
et étant donné un ordre total "<_i" sur chaque attribut, o1 "domine" o2 ssi
pour chaque attribut i, o1[i] $leq_i$ o2[i] ET il y a un j tel
que o1[j] <_j o2[j]. L'horizon de O (c'est aussi appelé 'enveloppe de Pareto')
est l'ensemble de ses éléments qui ne sont pas dominés. Le papier présente
une technique d'ordonnancement permettant de réduire la quantité de données
transférées sur le réseau pour optimiser la requête.
Intervenant: Sofian Maabout |
| | Plus d'infos |
|
| 2012-05-14 | Modélisation cérébrale systémique: approches en algorithmique distribuée |
14:00-15:00 s. 076 |
Je présenterai les activités de l'équipe Mnemosyne, dans le domaine de la modélisation multi-échelle du cerveau. Cette équipe, immergée à l'Institut des Maladies Neurodégénératives, est une équipe d'informatique et de mathématique appliquée. Elle s'appuie sur des connaissances, des expérimentations et des interactions avec biologistes et médecins pour développer des modèles pouvant avoir des impacts dans les Sciences du Vivant et en médecine, mais elle développe aussi une démarche à part entière dans le domaine des STIC et particulièrement en algorithmique distribuée que je présenterai ici.
Intervenant: Frederic ALEXANDRE
|
| | Plus d'infos |
|
| 2012-04-02 | Spanner planaire pour le Unit Disk Graph |
14:00-15:00 s. 076 |
Nous nous intéressons à la recherche d'un spanner (un sous-graphe approximant les distances) planaire pour les graphes de disques unitaires (UDG) qui modélise les réseaux ad hoc sans fils. De nombreux résultats existent pour les spanners en terme de distance Euclidienne de UDG, nous présentons ici un algorithme qui construit un spanner planaire avec un facteur d'étirement constant en terme de distance de graphe pour UDG. Par rapport aux constructions précédemment proposées pour ce problème, nous assurons un facteur d'étirement significativement plus petit ainsi que la planarité totale du graphe. Cet algorithme utilise uniquement des propriétés locales et peut donc être implémenté de manière distribuée.
Intervenant: Nicolas Catusse |
| | Plus d'infos |
|
| 2012-03-26 | Distributed Online and Stochastic Queuing on a Multiple Access Channel |
14:00-15:00 s. 076 |
We consider the problems of online and stochastic packet queuing in a
distributed system of n nodes with queues, where the communication
between the nodes is done via a multiple access channel. In each
round, an arbitrary number of packets can be injected into the system,
each to an arbitrary node's queue. Two measures of performance are
considered: the total number of packets in the system, called the
total load, and the maximum queue size, called the maximum load. In
the online setting, we develop a deterministic algorithm that is
asymptotically optimal with respect to both complexity measures, in a
competitive way; more precisely, the total load of our algorithm is
bigger then the total load of any other algorithm, including
centralized onine solutions, by only O(n^2), while the maximum queue
size of our algorithm is at most O(n) plus the value which is at most
n times bigger than the maximum queue size of any other algorithm. The
optimality for both measures is justified by proving the
corresponding lower bounds. Next, we show that our algorithm is
stochastically optimal for any expected injection rate smaller or
equal to 1. To the best of our knowledge, this is the first solution
to the stochastic queuing problem on a multiple access channel that
achieves such optimality for the (highest possible) rate equal to 1.
This is joint work with Marcin Bienkowski, Tomasz Jurdzinski, and Dariusz Kowalski.
Intervenant: Miroslaw Korzeniowski |
| | Plus d'infos |
|
| 2012-03-12 | On the lambda-alert problem in radio networks |
14:00-15:00 s. 076 |
In this talk we will consider the λ-alert problem in a single hop radio network. Some subset of stations of the network is activated. The aim of the protocol is to say if the number of activated stations is at least λ. The problem is a generalization of the alert problem and is similar to the classical k-Selection problem. We will consider deterministic, randomized, oblivious and adaptive algorithms for λ-alert in models with and without collision detection.
Orateur: Dominik Pajak |
| | Plus d'infos |
|
| 2012-03-05 | On Snapshots and Stable Properties Detection in Anonymous Fully Distributed Systems |
14:00-15:00 s. 076 |
Most known snapshot algorithms assume that vertices of network have unique
identifier and/or there is exactly one initiator. This talk concerns snapshot computation
in an anonymous network and more generally what stable properties of a distributed
system can be computed anonymously with local snapshots with multiple initiators
when knowing an upper bound on the diameter of the network.
Orateur: Thomas Morsellino |
| | Plus d'infos |
|
| 2012-02-13 | Preuves formelles d'algorithmes distribués probabilistes |
14:00-15:00 s. 076 |
Afin de prouver des propriétés d'algorithmes distribués probabilistes à l'aide d'un assistant de preuve tel Coq, il faut un modèle permettant de raisonner à la fois sur l'aspect distribué et sur le probabiliste. Une nouvelle méthode a été introduite dans la bibliothèque Alea concernant l'aspect probabiliste. Elle est basée sur l'interprétation monadique des programmes probabilistes vus en tant que distributions probabilistes.
Nous présentons en premier lieu comment l'interprétation des algorithmes probabilistes comme des distributions a permis de constituer la bibliothéque Alea de preuves formelles de propriétés de ces programmes. Nous verrons ensuite les choix faits pour modéliser les algorithmes distribués. Nous appliquerons enfin ces théories dans les cas de la brisure de symétrie, du handshake et du maximal matching.
|
| | Plus d'infos |
|
| 2012-02-06 | Tolerating Transient, Permanent, and Intermittent Failures |
14:00-15:00 s. 076 |
When the size of a distributed system gets larger or when it is deployed in hazardous environments, the possibility that some elements of the system are subject to faults (failure, memory corruption, hacking, ...) become impossible to elude. Faults can be classified according to duration, span, or nature. In this talk, we focus on distributed systems that simultaneously tolerate several kinds of faults using three classical problems as case studies. We present first a distributed protocol simulating a single-writer multi-reader atomic register in the presence of transient faults and of permanent crash faults. This protocol relies on two re-usable tools: a communication primitive and a bounded timestamp scheme. Then, we study logical clock weak synchronization in the presence of transient faults and of intermittent Byzantine faults. We prove several impossibility results and provide a protocol that is optimal both with respect to impossibility result and with respect to recovery time. Finally, we define three new fault tolerance schemes in distributed systems that are subject to transient faults and to intermittent Byzantine faults. We design a protocol constructing a wide class of spanning trees that is optimal with respect to fault tolerance metrics defined for these three schemes.
Orateur: Swan Dubois (LIP6) |
| | Plus d'infos |
|
| 2012-01-23 | Scheduling Associative Reductions with Overlapping Transfers and Computation |
14:00-15:00 s. 076 |
Increasing the performance of HPC and cloud environments involves to optimize the reduction phase, which is present in many applications. This optimization problem arises in at least two contexts: the MPI_Reduce collective function that allows to combine several arrays by performing a pairwise reduction operation on every arrays; and, the Reduce part of MapReduce applications, where a single result is generated from several inputs. By assuming the associativity of the reduction operation, it is possible to determine a spanning tree that schedules data transfers and reduction operations. Two algorithms are proposed for the cases where the number of reducers or the number of concurrent transfers is bounded. When there is no limitation, two specific optimal spanning trees are also characterized for specific transfer and computation costs.
Orateur: Louis-Claude Canon |
| | Plus d'infos |
|
| 2012-01-16 | The Impact of Edge Deletions on the Number of Errors in Networks. |
14:00-15:00 s. 076 |
In this talk we deal with an error model in distributed networks. For a target t, every node is assumed to give an advice, ie. to point to a neighbour that take closer to the destination. Any node giving a bad advice is called a liar. Starting from a situation without any liar, we study the impact of topology changes on the number of liars.
More precisely, we establish a relationship between the number of liars and the number of distance changes after one edge deletion. Whenever l deleted edges are chosen uniformly at random, for any graph with n nodes, m edges and diameter D, we prove that the expected number of liars and distance changes is O(l^2 D n / m) in the resulting graph. The result is tight for l = 1. For some specific topologies, we give more precise bounds.
This is joint work with Nicolas Hanusse and David Ilcinkas.
Orateur: Christian Glacet |
| | Plus d'infos |
|
| 2012-01-09 | Overlay Addressing and Routing System Based on Hyperbolic Geometry |
14:00-15:00 s. 076 |
Local knowledge routing schemes based on virtual coordinates taken from the hyperbolic plane have attracted considerable interest in recent years. In this work, we propose a new approach for seizing the power of the hyperbolic geometry.
We aim at building a scalable and reliable system for creating and managing overlay networks over the Internet.
The system is implemented as a peer-to-peer infrastructure based on the transport layer connections between the peers.
Orateur: Cyril Cassagnes |
| | Plus d'infos |
|
| 2011-12-12 | Tight Bounds for Anonymous Conflict Detectors |
14:00-15:00 s. 076 |
Most known distributed algorithms for randomized consensus from multi-writer registers proceed in rounds, each of which performs two tasks. The first is to ensure agreement with some nonzero probability. The second is to detect whether agreement has been reached.
We give matching upper and lower bounds of min{log m / log log m, n}, to within constant factors, for the individual step complexity of a wait-free m-valued conflict detector for n anonymous processes implemented from multi-writer registers. The upper bound is deterministic, but the lower bound also holds for randomized implementations.
It follows that the same lower bound holds on the individual step complexity of m-valued wait-free anonymous consensus, even for randomized algorithms with global coins against an oblivious adversary. The upper bound can also be used to slightly improve a previous upper bound on the cost of randomized consensus.
This work is joint with James Aspnes and appeared at SPAA 2011.
Orateur: Faith Ellen |
| | Plus d'infos |
|
| 2011-12-07 | Bounded-Distance Network Creation Games |
14:00-15:00 s. 178 |
A network creation game simulates a decentralized and non-cooperative building of a communication network. Informally, there are n players sitting on the network nodes, which attempt to establish a reciprocal communication by activating, incurring a certain cost, any of their incident links. The goal of each player is to have all the other nodes as close as possible in the resulting network, while buying as few links as possible. According to this intuition, any model of the game must then appropriately address a balance between these two conflicting objectives. Motivated by the fact that a player might have a strong requirement about its centrality in the network, in this paper we introduce a new setting in which if a player maintains its (either maximum or average) distance to the other nodes within a given associated bound, then its cost is simply equal to the number of activated edges, otherwise its cost is unbounded. We study the problem of understanding the structure of associated pure Nash equilibria of the resulting games, that we call MaxBD and SumBD, respectively.
|
| | Plus d'infos |
|
| 2011-12-05 | On the Power of Waiting when Exploring Public Transportation Systems |
14:00-15:00 s. 076 |
We study the problem of exploration by a mobile entity (agent) of a class of dynamic networks, namely the periodically-varying graphs (the PV-graphs, modeling public transportation systems, among others). These are defined by a set of carriers following infinitely their prescribed route along the stations of the network. Flocchini, Mans, and Santoro (ISAAC 2009) studied this problem in the case when the agent must always travel on the carriers and thus cannot wait on a station. They described the necessary and sufficient conditions for the problem to be solvable and proved that the optimal number of steps (and thus of moves) to explore a $n$-node PV-graph of $k$ carriers and maximal period $p$ is in $Theta(kcdot p^2)$ in the general case.
In this talk, we study the impact of the ability to wait at the stations. We exhibit the necessary and sufficient conditions for the problem to be solvable in this context, and we prove that waiting at the stations allows the agent to reduce the worst-case optimal number of moves by a multiplicative factor of at least $Theta(p)$, while the time complexity is reduced to $Theta(ncdot p)$. (In any connected PV-graph, we have $n leq kcdot p$.) We also show some complementary optimal results in specific cases (same period for all carriers, highly connected PV-graphs). Finally this new ability allows the agent to completely map the PV-graph, in addition to just explore it.
This is joint work with David Ilcinkas.
Orateur: Ahmed Wade |
| | Plus d'infos |
|
| 2011-11-28 | In search of lost time |
14:00-15:00 s. 076 |
In their seminal papers Dwork, Lynch, and Stockmeyer (JACM, 1988) and Lamport (TOCS, 1998) showed that, in order to solve Consensus in a distributed system, it is sufficient that the system behaves well during a finite period of time. In sharp contrast, Chandra, Hadzilacos, and Toueg (JACM, 1996) proved that a failure detector that, from some time on, provides "good" information forever is necessary. We explain that this apparent paradox is due to the two-layered structure of the failure detector model. This structure also has impact on comparison relations between failure detectors. In particular, we make explicit why the classic relation is neither reflexive nor extends the natural history-wise inclusion. Our point is to help understanding of existing models and to study how they model real distributed systems in an accurate way.
Orateur: Bernadette Charron-Bost |
| | Plus d'infos |
|
| 2011-11-21 | The Complexity of Picking a Name |
14:00-15:00 s. 076 |
Renaming is a fundamental problem in distributed computing,
in which a set of processes need to pick new names from a small
namespace.
In this talk, we present a new connection between renaming and the
classic mutual exclusion problem. We exploit this connection to get
new linear time complexity lower bounds for deterministic renaming,
queue, stack, and fetch-and-increment implementations. On the other
hand, we use it to obtain fast mutual exclusion algorithms based on
sorting networks.
Joint work with James Aspnes, Seth Gilbert, and Rachid Guerraoui.
A full version of these results appeared in the Proceedings of FOCS
2011, and is available at http://people.epfl.ch/dan.alistarh
Orateur: Dan Alistarh |
| | Plus d'infos |
|
| 2011-11-14 | Asynchronous Exclusive Perpetual Grid Exploration without Sense of Direction |
14:00-15:00 s. 076 |
We investigate the exclusive perpetual exploration of grid shaped networks
using anonymous, oblivious and fully asynchronous robots. Our results hold for robots without sense
of direction (i.e. they do not agree on a common North, nor do they agree on a common left and right ;
furthermore, the "North" and "left" of each robot is decided by an adversary that schedules robots for
execution, and may change between invocations of particular robots). We focus on the minimal number
of robots that are necessary and sufficient to solve the problem in general grids.
This is joint work with Alessia Milani, Maria Gradinariu Potop-Butucaru and Sébastien Tixeuil (to appear in Proc. OPODIS'11).
Orateur: François Bonnet |
| | Plus d'infos |
|
| 2011-10-24 | Convergence de chaines de Markov controlees par un adversaire |
14:00-15:00 s. 076 |
En algorithmique distribuée, il n'est pas rare de modéliser le
non-déterminisme d'un système en donnant à un adversaire le choix de
l'action à exécuter. Pour peu que les actions soient randomisées, le
système devient alors un automate probabiliste, dont le comportement, si
on sélectionne aléatoirement les actions à effectuer, devient celui
d'une chaîne de Markov.
L'objectif du présent travail est d'explorer dans quelles conditions les
resultats classiques de convergence sur les chaînes de Markov persistent
dans ce genre de situation moins confortable. L'idée est de pouvoir les
appliquer pour pouvoir affirmer, sous des hypothèses minimales, la
convergence de ces systèmes non déterministes vers des distributions
bien définies.
Orateur: Philippe Duchon |
| | Plus d'infos |
|
| 2011-10-17 | Using the Last-mile Model as a Distributed Scheme for Available Bandwidth Prediction |
14:00-15:00 s. 076 |
Several Network Coordinate Systems have been proposed to predict
unknown network distances between a large number of Internet nodes by
using only a small number of measurements, mostly focused on
predicting latency. But end-to-end path available bandwidth is an
important metric for the performance optimisation in many high
throughput distributed applications, such as video streaming and file
sharing networks.
In this talk, we show how to perform available
bandwidth prediction with the last-mile model, in which each node is
characterised by its incoming and outgoing capacities. This model has
been used in several theoretical works for distributed
applications. We design decentralised heuristics to compute the
capacities of each node so as to minimise the prediction error. We
show that our algorithms can achieve a competitive accuracy even with
asymmetric and erroneous end-to-end measurement datasets, and even
when using a very small number of measurements.
Orateur: Lionel Eyraud-Dubois |
| | Plus d'infos |
|
| 2011-10-10 | Boundary Patrolling by Mobile Agents with Distinct Maximal Speeds |
14:00-15:00 s. 076 |
A set of k mobile agents are placed on the boundary of a simply connected planar object represented by a cycle of unit length. Each agent has its own predefined maximal speed, and is capable of moving around this boundary with a velocity not exceeding its maximal speed. The agents are required to protect the boundary from an intruder which attempts to penetrate to the interior of the object through a point of the boundary, unknown to the agents. The intruder needs some time interval of length au to accomplish the intrusion. Will the intruder be able to penetrate into the object, or is there an algorithm allowing the agents to move perpetually along the boundary, so that no point of the boundary remains unprotected for a time period of au?
Such a problem may be solved by designing an algorithm which defines the motion of agents so as to minimize the idle time I, i.e., the longest time interval during which any fixed boundary point remains unvisited by some agent, with the obvious goal of achieving I < au.
Depending on the type of the environment, this problem is known as either "boundary patrolling" or "fence patrolling" in the robotics literature. The most common heuristics adopted in the past include the cyclic strategy, where agents move in one direction around the cycle covering the environment, and the partition strategy, in which the environment is partitioned
into sections patrolled separately by individual agents. This paper is, to our knowledge, the first study of the fundamental problem of boundary patrolling by agents with distinct maximal speeds. In this scenario, we give special attention to the performance of the cyclic strategy and the partition strategy. We propose general bounds and methods for analyzing these strategies, obtaining exact results for cases with 2, 3, and 4 agents. We show that there are cases when the cyclic strategy is optimal, cases when the partition strategy is optimal and, perhaps more surprisingly, cases when novel, alternative methods have to be used to achieve optimality.
This is joint work with Jurek Czyzowicz, Leszek Gasieniec and Evangelos Kranakis. |
| | Plus d'infos |
|
| 2011-09-12 | Multi-Interface Networks - a survey |
14:00-15:00 amphithéâtre du LaBRI (050) |
Multi-Interface networks refer to a recent model which considers heterogeneous devices in communication networks. A device can establish several connections by means of different communication interfaces like Bluetooth, IrDA, LAN, WiFi, GSM. A connection is established if both the devices at its endpoints activate at least one common interface. The possibility for the devices to establish different connections introduces new challenging problems on the basis of the available interfaces, the deployment, the bandwidth constraints and other parameters. We survey on recent results where minimum spanning tree, shortest paths, flow and other basic problems have been re-visited within the multi-interface model. |
| | Plus d'infos |
|
| 2011-07-18 | Approximating Graphic TSP by Matchings |
14:00-15:00 s. 178 |
We present a framework for approximating the metric TSP based on a
novel use of matchings. Traditionally, matchings have been used to
add edges in order to make a given graph Eulerian, whereas our
approach also allows for the removal of certain edges leading to a
decreased cost.
For the TSP on graphic metrics (graph-TSP), the approach yields a
1.461-approximation algorithm with respect to the
Held-Karp lower bound. For graph-TSP restricted to a class of graphs that
contains degree three bounded and claw-free graphs, we show that the
integrality gap of the Held-Karp relaxation matches the conjectured
ratio 4/3. The framework allows for generalizations in a natural way and
also leads to a 1.586-approximation algorithm for the traveling salesman
path problem on graphic metrics where the start and end vertices are
prespecified.
This is joint work with Ola Svensson. |
| | Plus d'infos |
|
| 2011-07-11 | Dynamic Sharing of a Multiple Access Channel and its Online Analysis |
14:00-15:00 s. 178 |
We consider the mutual exclusion problem on a multiple access channel.
Mutual exclusion is one of the fundamental problems in distributed
computing. In the classic version of this problem, n processes perform
a concurrent program which occasionally triggers some of them to use
shared resources, such as memory, communication channel, device, etc.
The goal is to design a distributed algorithm to control entries and
exits to/from the shared resource in such a way that in any time there
is at most one process accessing it. We consider both the classic and
a slightly weaker version of mutual exclusion, called
ε-mutual-exclusion, where for each period of a process staying in the
critical section the probability that there is some other process in
the critical section is at most ε. We show that there are channel
settings, where the classic mutual exclusion is not feasible even for
randomized algorithms, while ε-mutual-exclusion is. In more relaxed
channel settings, we prove an exponential gap between the makespan
complexity of the classic mutual exclusion problem and its weaker
ε-exclusion version. We also show how to guarantee fairness of mutual
exclusion algorithms, i.e., that each process that wants to enter the
critical section will eventually succeed. In the online/competitive
analysis we consider the problem of serving queues of nodes wanting to
send packets over a shared channel so that maximum queue length stays
within constant factors from maximum queue length of an optimal
centralized algorithm.
This is joint work with Marcin Bienkowski, Tomasz Jurdzinski, Marek Klonowski, and
Dariusz Kowalski.
|
| | Plus d'infos |
|
| 2011-07-04 | Robot Networks with Homonyms: The Case of Patterns Formation |
14:00-15:00 s. 178 |
In this paper, we consider the problem of formation of a series of geometric patterns by a network of oblivious mobile robots that communicate only through vision.
So far, the problem has been studied in models where robots are either assumed to have distinct identifiers or to be completely anonymous.
To generalize these results and to better understand how anonymity affects the computational power of robots, we study the problem in a new model, introduced recently in cite{Delporte2011}, in which n robots may share up to 1 <= l <= n different identifiers.
We present necessary and sufficient conditions, relating symmetricity and homonymy, that makes the problem solvable.
To present our algorithms, we use a function that computes the Weber point for many regular and symmetric configurations. This function is interesting in its own right, since the problem of finding Weber points has been solved up to now for only few other patterns.
Das2010:
S. Das, P. Flocchini, N. Santoro and M. Yamashita. On the computational power of oblivious robots: forming a series of geometric patterns. In PODC 2010.
Delporte2011:
C. Delporte-Gallet, H. Fauconnier, R. Guerraoui, T. Hung, A. Kermarrec, and E. Ruppert. Byzantine agreement with homonyms. In PODC 2011.
****
Zohir Bouzid is doing his PhD with Sébastien Tixeuil in Paris. |
| | Plus d'infos |
|
| 2011-06-14 | Speculating Seriously |
14:00-15:00 amphithéâtre du LaBRI (050) |
If we are ever to understand what computers can collectively do, we need a new theory of complexity. Recent evolutions, including the cloud and the multicore, are turning computing ubiquitously distributed, rendering the classical complexity theory of centralized computing at best insufficient. A complexity theory for distributed computing has emerged in the last decades, measuring complexity for each specific model of the networked environment, represented by an adversary that may provoke asynchrony, failures, contention, etc. This one adversary - one result approach led to an exponential proliferation of seemingly unrelated results, none of which captures current practices in the development of distributed applications. Instead, applications rely on speculative algorithms that perform well when the environment behaves nicely and gracefully degrades if the environment is more hostile, considering thereby several adversaries at the same time. With no underlying theory, the proposed speculative algorithms lack however rigor and there is anecdotal evidence of their fragility. It is moreover usually impossible to predict their behavior or determine whether their limitations are related to fundamental impossibilities or artifacts of specific infrastructures. The goal of this talk is to discuss a glimmer of a theory of speculative distributed computing.
****
Rachid Guerraoui is professor in computer science at EPFL. He is interested in distributed computing on which he wrote few books and more papers (http://lpdwww.epfl.ch/rachid/).
****
NOTE: Ce séminaire aura lieu le MARDI!
|
| | Plus d'infos |
|
| 2011-06-06 | Broadcasting on Large Scale Heterogeneous Platforms with connectivity artifacts under the Bounded Multi-Port Model |
14:00-15:00 s. 178 |
We consider the problem of broadcasting a large message in
a large-scale distributed platform. The message must be sent from a source
node, with the help of the receiving peers which may forward the
message to other peers. In this context, we are interested in
maximizing the throughput (i.e. the maximum streaming rate, once
steady state has been reached). The platform model does not assume
that the topology of the platform is known in advance: we consider an
Internet-like network, with complete potential connectivity.
Furthermore, the model associates to each node local properties
(incoming and outgoing bandwidth), and the goal is to build an overlay
which will be used to perform the broadcast operation. We model
contentions using the bounded multi-port model: a processor can be
involved simultaneously in several communications, provided that its
incoming and outgoing bandwidths are not exceeded. It is also
necessary to minimize the number of simultaneous connections that are
opened at a given node (i.e., its outdegree). We also block the possibility
of direct communication between some nodes to model NAT/firewall
restrictions.
|
| | Plus d'infos |
|
| 2011-05-23 | Static Quantum Games Revisited |
14:00-15:00 s. 178 |
The so called emph{quantum game theory} has recently been proclaimed as one of the new branches in the development of both quantum information theory and game theory. However, the notion of a quantum game itself has never been strictly defined, which has led to a lot of conceptual confusion among different authors. In this paper we introduce a new conceptual framework of a emph{scenario} and an emph{implementation} of a game. It is shown that the procedures of "quantization" of games proposed in the literature lead in fact to several different games which can be defined within the same scenario, but apart from this they may have nothing in common with the original game. Within the framework we put forward, a lot of conceptual misunderstandings that have arisen around "quantum games" can be stated clearly and resolved uniquely. In particular, the proclaimed essential role of entanglement in several static "quantum games", and their connection with Bell inequalities, is disproved. |
| | Plus d'infos |
|
| 2011-05-02 | Spanner, distance oracle, and compact routing for unweighted graphs |
14:00-15:00 s. 178 |
It is known that every n-vertex unweighted graph G has a subgraph H of O(n^1.5) edges such that the distance in H between any two vertices is at most the distance in G plus 2. In other words, there is always a graph of size O(n^1.5) that well approximate all distances in G. It is however not known whether every graph has a data-structure (a distance oracle) of space O(n^1.5) supporting (d+2)-approximate distance query in constant time. In this direction, Patrascu and Roditty have recently showed in FOCS'11 that distance oracle of size O(n^1.66) and (2d+1)-approximate distance query in constant time do exists.
In this talk, I will show a distributed version of this oracle matching its space and distance approximation bounds, and a generalization of it. I will also present a compact routing scheme using tables of size O(n^0.75) and whose route lengths are at most twice the distance plus one.
|
| | Plus d'infos |
|
| 2011-04-18 | Choosing the best among peers |
14:00-15:00 s. 178 |
A group of n peers (e.g., computer scientists) has to choose the best (most
competent) among them. Each member of the group may vote for one other
member (self-voting is not allowed), or abstain. While opinions may be subjective,
resulting in various voting graphs (directed graphs in which an arc (u,v) means
that u votes for v), it is natural to assume that more competent peers are also,
in general, more competent in evaluating competence of others. We capture this
by proposing a voting system in which each member is assigned a positive integer
"value" satisfying the following "strict support monotonicity" property: the value
of x is larger than the value of y if and only if the sum of values of members voting
for x is larger than the sum of values of members voting for y. Then we choose
the member with the highest value, or if there are several such members, another
election mechanism (e.g., random) chooses one of them.
We show that for every voting graph there is a value function satisfying the strict
support monotonicity property and that such a function can be computed in
linear time. However, it turns out that this method of choosing the best among
peers is vulnerable to vote manipulation: even one voter of very low value
may change her vote so as to get the highest value. This is due to the possibility of
loops (directed cycles) in the voting graph. Hence we slightly modify voting graphs
by erasing all arcs that belong to some cycle. This modification results in
a "pruned voting graph" which is always a rooted forest.
We show that for all pruned voting graphs there are value functions giving
a guarantee against manipulation. More precisely, we show a value function
guaranteeing that no coalition of k members all of whose values are lower than
those of (1-1/(k+1))n other members can manipulate their votes so that one of
them gets the largest value. In particular, no single member from the lower half
of the group is able to manipulate his/her vote to become elected. We also show
that no better guarantee can be given for any value function satisfying
the strict support monotonicity property.
This is joint work with Jurek Czyzowicz and Andrzej Pelc. |
| | Plus d'infos |
|
| 2011-03-14 | Multipath spanning graphs |
14:00-15:00 s. 178 |
This talk will be about graphs spanners. An (alpha,eta) spanner H of
a graph G is a covering subgraph such that for any pair of vertices u,v
the distance (defined as the length of a shortest path joining the
vertices) in the subgraph is at most alpha times the distance in G plus
eta. Generally spanner constructions are rated with the construction
time and the size of the spanner they yield.
Introduced by Peleg & Alii. spanners are fundamental objects related to
compact routing, distance oracles, distributed distance labelling and so on.
After a brief remainder of the classic constructions which yield
(2k-1,0) (for any positive integer k) and (1,2) spanners we will show it
is possible to extend the definition to account other metrics,
especially metrics which take in account multiple paths. Firstly we will
introduce an *edge*-disjoint multipath metric and show that the two
classic constructions can be extended in such a way to create
(c(2k-1),0) c-multipath spanners and (2,8) 2-multipath spanners on this
metric. Secondly we will show that the notion of spanners is also
sensible on *node*-disjoint multipaths by presenting a construction
which yields a multiplicative spanner on the metric defined by the
smallest *node*-disjoint cycle between two vertices.
|
| | Plus d'infos |
|
| 2011-02-14 | About Lower Bounds on the Bit Complexity and the Execution Time of some Probabilistic Distributed Graph Algorithms |
14:00-15:00 s. 178 |
We present a general framework for proving lower bounds for the bit complexity (and thus the execution time) of some probabilistic distributed graph algorithms and we apply it to the complexity of some problems such as colouring, maximal matching or maximal independent set. We also give impossibility results on the existence of Las Vegas distributed algorithms to break symmetries at distance k for k >= 3.
This is joint work with Y. Métivier, J.M. Robson and N. Saheb
|
| | Plus d'infos |
|
| 2011-02-07 | SkewCCC+: A Heterogeneous Distributed Hash Table |
14:00-15:00 s. 178 |
Distributed Hash Tables (DHTs) enable fully distributed Peer-to-Peer network construction and maintenance with name-driven routing. There exist very few DHT approaches that consider heterogeneity of nodes inside the construction process or properly serve data of different load. To our best knowledge, there is no construction which smoothly addresses both these issues. We propose a Peer-to-Peer construction that explicitly uses heterogeneity to simplify the routing and maintenance process even in the presence of an adaptive adversary. Using a hypercube and cube connected cycles networks as a backbone, we show how to cope with two types of heterogeneity: one for nodes and one for data.
This is joint work with Marcin Bienkowski, André Brinkmann, and Marek Klonowski. |
| | Plus d'infos |
|
| 2011-01-24 | Fault-tolerance Synchronous Handshake Algorithm for Local Computations |
14:00-15:00 Salle 178 |
This work presents a new probabilistic, synchronization
algorithm to get a handshake between two neighboring nodes in the graph.
This algorithm is designed for an asynchronous distributed network of
anonymous processes which use the message exchange as a model for the
communication. In this work, we use the Event-B method for the
specification and for the proof of correctness. We present a comparative
study between our algorithm and the one proposed by Y. Metivier et al.
(*). We show that our proposal presents a considerable improvement of
the previous one in terms of the number of sent messages and fault
tolerance. We display the effectiveness of our algorithm by
highlighting the importance of its asynchronous aspect on the total
performances of the algorithm.
(*) Metivier, Y., Saheb, N., Zemmari, A.: Randomized rendezvous. In: In
Mathematics and computer science : Algorithms, trees, combinatorics and
probabilities, Trends in mathematics. pp. 183-194. Birkhäuser (2000)
|
| | Plus d'infos |
|
| 2011-01-17 | Dissuasive Methods against Malicious Behaviors in Large Scale Distributed Systems |
14:00-15:00 Salle 178 |
Users of large scale distributed systems deployed in the public domain
do misbehave: MMOG players cheat, file sharing system users free-ride,
and social network users create multiple identities or try to
impersonate people they know. Traditional techniques to deal with
malicious users consist in masking their misbehaviors (e.g., BFT) or
preventing them (e.g., using cryptography). This talk presents dissuasive
methods against malicious behaviors based on distributed verifications:
users check each others actions and report detected faults. We first
illustrate our approach by analyzing an epidemic high-bandwidth
dissemination protocol where the inherent randomness of gossip protocols
allows lightweight collusion-resilient tracking of free-riders. We then
present our work on secured distributed computations in social networks
where the real persons' reputation concern acts as an incentive not to
misbehave.
|
| | Plus d'infos |
|
| 2011-01-10 | Log-space agents for solving anonymous rendezvous and other graph problems |
14:00-15:00 Salle 178 |
In this talk we consider deterministic algorithms for some agent-based
tasks in graphs. Mobile agents are frequently employed to perform
decentralized information management processes, by persistently
traversing or crawling the web, collecting, updating and disseminating
information, and maintaining network integrity.
In the rendezvous problem, two identical (anonymous) mobile agents
start from arbitrary nodes in a graph and move from node to node with
the goal of meeting. A well-known recent result on exploration, due to
Reingold, states that exploration of arbitrary graphs can be performed
in log-space, i.e., using an agent equipped with $O(log n)$ bits of
memory, where $n$ is the size of the graph. Our main result establishes
the minimum size of the memory of anonymous agents that guarantees
deterministic rendezvous when it is feasible. We show that this minimum
size is $Theta(log n)$, where $n$ is the size of the graph, regardless
of the delay between the starting times of the agents.
We also mention some other problems related to map reconstruction, for
which an agent with $Theta(log n)$ bits of memory is sometimes
required and always sufficient.
|
| | Plus d'infos |
|
| 2010-12-13 | Un algorithme distribué de recherche dans un réseau non-fiable ou comment battre la marche aléatoire avec une montre |
14:00-15:00 Salle 076 |
Dans les réseaux dynamiques, il est nécessaire de considérer que
les informations stockées aux noeuds ne sont pas fiables. Comment
effectuer une recherche ou un routage lorsque un ensemble de noeuds non
nécessairement détectables "mentent" ? Je présenterai un algorithme
distribué générique, la marche lunatique, qui s'exécutent rapidement
pour des topologies différentes telles que le chemin ou les graphes de
grande expansion (graphes aléatoires réguliers).
Ce travail a été réalisé avec Adrian Kosowski, David Ilcinkas et Nicolas
Nisse et a été présenté lors de PODC 2010.
|
| | Plus d'infos |
|
| 2010-12-06 | SimGrid : Logiciel pour la simulation d'applications distribuées |
14:00-15:00 Salle 178 |
Il existe de nombreux logiciels pour l'étude et la simulation d'algorithmes distribués. Le but de SimGrid est de fournir un environnement commun pour la comparaison expérimentale des performances d'algorithmes dans des environnements distribués hétérogènes. L'accent est mis sur le passage à l'échelle, tout en restant aussi réaliste que possible.
J'exposerai les motivations et les principes généraux de SimGrid, son fonctionnement sur un exemple simple, et quelques résultats de validation du modèle de communication contenu dans le simulateur. |
| | Plus d'infos |
|
| 2010-11-29 | About the Power of Anonymous Radio Networks |
14:00-15:00 Salle 178 |
We address the enumeration and the leader election problems over multi-hop radio networks. We
consider an asynchronous radio communication model where each process emits a message and all
its neighbours hear this message after arbitrary and unpredictable time. This amount of time
depends on the processing time taken by the network layer to ensure message delivery.
In this talk, we characterize graphs in which we can solve these problems and we present an
enumeration algorithm and a leader election algorithm. For both problems, we highlight the
importance of the initial knowledge. For the enumeration problem, each process only knows the
size of the graph and, contrary to related works, the number of its neighbouring processes is
unknown. Whereas for the election problem, we show that this knowledge is not sufficient; our
algorithm supposes that each process initially knows a map of the network. Given a graph of
maximum degree ∆ with n nodes and m edges, our algorithms both yield O(mn^2) emitted messages
of size O(∆ log n) bits.
Joint work with Jérémie Chalopin (LIF) and Yves Métivier (LaBRI).
|
| | Plus d'infos |
|
| 2010-11-22 | On the correctness and efficiency of a distributed directory service |
14:00-15:00 Salle 178 |
Many distributed systems support some concept of mobile objects, i.e. objects (e.g., a file) that can be transmitted over a network from one node to another. A directory service allows nodes to keep track of mobile objects : if a user requests the object and it is not on the local node, the directory protocol locates the object and moves it on the local node.
To implement a directory service a fundamental synchronization problem has to be solved : multiple concurrent requests should be totally ordered. This can be also seen as a distributed queuing problem.
Through few well-known algorithms, the talk will discuss issues related to the correctness and the efficiency of implementing a distributed directory service. Some open problems will be presented. |
| | Plus d'infos |
|
| 2010-11-15 | Gestion auto-stabilisante avec garantie de service de la connaissance des clusters voisins |
14:00-15:00 Salle 178 |
Les algorithmes auto-stabilisants permettent au système des retrouver, en un temps fini, sa cohérence de lui-même sans intervention extérieure, ni ré-initialisation globale. Néanmoins, ces algorithmes ignorent complètement le comportement du système pendant la phase de stabilisation. Notre travail porte sur l'amélioration du service offert par les algorithmes auto-stabilisants pendant leurs convergence, et donc, de concevoir des algorithmes auto-stabilisants garantissant un service minimum pendant la phase de stabilisation.
Le partitionnement en clusters est proposé dans les réseaux mobiles sans infrastructure pour améliorer leurs performances. Vu que les protocoles de partitionnement sont adaptatifs aux changements topologiques, la structure hiérarchique produite sera dynamique : des clusters peuvent apparaître et disparaître au cours du temps. Par conséquent, tous les protocoles hiérarchiques doivent être également adaptatifs à ces changements.
Nous proposons un protocole de connaissance des clusters voisins, baptisé CNK. CNK permet à chaque leader de cluster de connaître tous ses clusters voisins : l'identité de leurs leaders, les chemins menant à eux, ainsi que la liste de leurs membres. CNK est auto-stabilisant. De plus, il possède une propriété intéressante, à savoir la garantie de service pendant la stabilisation. CNK offre rapidement un service minimum utile, à savoir : chaque leader connaît l'identité de tous les leaders des clusters voisins, ainsi que des chemins menant à eux. Ce service minimum est préservé en dépit des changements de la structure hiérarchique, tel que : la création et destruction de clusters, ainsi que le changement de composition des clusters. La connaissance des clusters voisins est donc hautement disponible, ce qui assure la continuité de fonctionnement des protocoles de couches supérieures, comme le routage hiérarchique.
Mots-clés : auto-stabilisation, garantie de service, partitionnement, voisinage d'un cluster. |
| | Plus d'infos |
|
| 2010-11-08 | Randomized Rumor Spreading and Vertex Expansion |
14:00-15:00 Salle 178 |
We study the relation between the vertex expansion of a graph and the performance of randomized rumor spreading (push model). We prove that randomized rumor spreading takes O( (1/alpha) * poylog(n) ) time on any regular n-vertex graph with vertex expansion alpha.
This bound basically extends previously known upper bounds by replacing conductance by vertex expansion.
Our result is almost tight in the sense that the dependency on 1/alpha is optimal (up to logarithmic factors) and that on non-regular graphs with constant vertex expansion, the runtime can be polynomial in n. Our upper bound also implies that randomized rumor spreading is ``fast'' on every vertex-transitive graph and yields a new upper bound on the cover time of random walks.
(joint work with Alexandre Stauffer) |
| | Plus d'infos |
|
| 2010-10-18 | On Bounded Degree Strong Plane Geometric Spanners |
14:00-15:00 Salle 178 |
Given a set P of n points in the plane, we show how to compute in O(n log n) time
a spanning subgraph of their Delaunay triangulation that has maximum degree 7 and
is a strong plane t-spanner of P with t = (1+sqrt{2})^2 ∗ δ, where δ is the spanning ratio of
the Delaunay triangulation. Furthermore, the maximum degree bound can be reduced
slightly to 6 while remaining a strong plane constant spanner at the cost of an increase
in the spanning ratio and no longer being a subgraph of the Delaunay triangulation.
|
| | Plus d'infos |
|
| 2010-10-11 | Wait-free coordination |
14:00-15:00 Salle 178 |
In a distributed system, several entities (nodes, processors,
sensors, etc.) have to cooperate in order to solve some tasks.
Unfortunately, the very fact that processing entities are
distributed often makes difficult or even impossible to solve even
simple tasks. In particular, message transfers may experience
unpredictable delays due to network asynchrony and nodes may fail.
An important question is to understand what can be computed in a
distributed system prone to a given level of uncertainty. Uncertainty
being characterized by the kind of failure nodes may suffer and the
timing assumptions of the underlying communication network.
This talk will focus on the wait-free case in which any number of
processes may crash and the network is totally asynchronous. The first
part will give a brief overview of the deep connection between
algebraic/combinatorial topology and distributed computing.
Topological methods have yielded a variety of lower bounds for
distributed computing . One of the most celebrated result is a
characterization of wait-free computability. If time permits, the
second part will try to demonstrate that the wait-free case is central:
the computability question in other models with different
timing/failures assumptions can often be reduced to the wait-free
case. More, this can be done by appropriate algorithmic construction. |
| | Plus d'infos |
|
| 2010-06-21 | About Randomised Distributed Graph Colouring and Graph Partition Algorithms |
14:00-15:00 Salle 178 |
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 |
| | Plus d'infos |
|
| 2010-06-14 | Almost optimal asynchronous rendezvous in infinite multidimensional grids |
14:00-15:00 Salle 178 |
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. |
| | Plus d'infos |
|
| 2010-06-07 | Using neighborhood exploration to speed up random walks |
14:00-15:00 salle 3, bat. A29 |
We consider strategies that can be used to speed-up the cover time of a random walk on
undirected connected graphs. The price of this speed up is normally some extra work that
can be performed locally by the walk or by the vertices of the graph. Typical assumptions
about what is allowed include: Biased walk transitions, Use of previous history, Local
exploration of the graph.
Methods of local exploration include the neighbour marking process RW-MARK and lookahead
RW-LOOK (searching to fixed depth).
The marking process, RW-MARK, made by a random walk on an undirected graph G is
as follows. Upon arrival at a vertex v, the walk marks v if unmarked and otherwise it marks
a randomly chosen unmarked neighbor of v.
Depending on the degree and the expansion of the graph, we prove several upper bounds
on the time required by the process RW-MARK to mark all vertices of G. If, for instance
G is the hypercube on n vertices the processes marks all vertices in time O(n), with high
probability. This significantly reduces the n log_e n cover time of the hypercube using a
standard random walk.
The process RW-MARK can be compared to the marking process CC-MARK where a
vertex v is chosen uniformly at random (coupon collecting) at each step. For the hypercube
CC-MARK also has a marking time of O(n).
In the related look-ahead process RW-LOOK, the walk marks all neighbours of the visited
vertex to some depth k. For the hypercube, for example, the performance of the processes
RW-LOOK-1, and CC-LOOK-1 is asymptotic to (log_e 2)n with high probability.
This research is joint work with Petra Berenbrink, Robert Elsässer, Tomasz Radzik and
Thomas Sauerwald. |
| | Plus d'infos |
|
| 2010-05-17 | Graphes de recouvrement multichemins |
14:00-15:00 amphi C - Bat. A29 |
Cet exposé parlera de graphes de recouvrement (nommés spanners en
anglais) qui approximent des plus courts chemin entre des paires de
sommets. Habituellement un spanneur $H$ d'étirement $s$ pour un graphe
$G$ est un sous-graphe couvrant tel que la distance dans $H$ entre deux
sommets quelconques est au plus $s$ fois la distance dans $G$. Nous
montrerons dans cet exposé qu'il est possible de définir une notion de
spanneur pour une métrique multichemins, notamment des spanneurs qui
approximent des plus courts cycles passant par deux sommets quelconques.
Après avoir introduit la métrique multichmins, il sera montré qu'il est
possible de construire pour tout graphe et tout entier $k$ des
$p(2k-1)$-spanneurs $p$-multichemins possédant $O(n^{1+1/k})$ arêtes, où
$n$ est le nombre de sommets du graphe. En se restreingnant à deux
chemins, il sera montré que la construction précedente permet d'obtenir
un $3$-spanneur $2$-multichemins. Enfin, il sera montré comment obtenir
un spanneur $2$-multichemins dont le facteur d'étirement est de $2$ au
prix d'une constante additive sur la longueur des chemins. |
| | Plus d'infos |
|
| 2010-05-10 | Quelques éléments analytiques dans les réseaux hautement dynamiques |
14:00-15:00 Salle 178 |
Les réseaux dynamiques ont fait l'objet de nombreux travaux ces
dernières années car ils posent un ensemble de problèmes inédits.
Toutefois, la grande majorité des études dans le domaine se sont
attachées à concevoir et évaluer des solutions appliquées pour des
contextes technologiques donnés. Ces travaux ont rendu possible de
nombreuses tâches, mais ont finalement abouti à peu de compréhension sur
la nature réelle de ces réseaux ainsi que leurs limitations intrinsèques.
Nous pensons que ce déficit est essentiellement lié à l'invalidité des
propriétés habituellement exploitables d'un point de vue algorithmique.
En effet, que signifient des notions telles que la connexité d'un
graphe, la longueur d'un chemin, ou encore le degré d'un sommet en
contexte dynamique ? Que dire également d'hypothèses usuelles sur la
structure du réseau (arbre, anneau, etc.) ou sur l'absence de symmétries
(p.ex. recouvrements) ?
L'objectif de cet exposé sera de montrer qu'en redéfinissant certains de
ces concepts de base dans le cadre dynamique, on ouvre la porte à de
nouveaux travaux analytiques. Je développerai l'exemple du broadcast
avec détection de la terminaison, où l'on cherche aussi bien à optimiser
les distances topologiques que temporelles, en faisant des hypothèses
propres au cas dynamique (travail en commun avec Paola Flocchini,
Bernard Mans, et Nicola Santoro). Les résultats de cette analyse
alimenteront ensuite une discussion sur l'utilité de l'approche
elle-même et déboucheront sur la présentation de quelques nouveaux
problèmes.
|
| | Plus d'infos |
|
| 2010-05-03 | Exploration optimale de terrains avec obstacles |
14:00-15:00 Salle 178 |
A mobile robot represented by a point moving in the plane has to
explore an unknown terrain with obstacles. Both the terrain and the
obstacles are modeled as arbitrary polygons. We focus on the limited
vision scenario, when the robot situated at a point p of the terrain
explores (sees) all points q of the terrain for which the segment pq
belongs to the terrain and the distance between p and q be at most 1.
All points of the terrain (except obstacles) have to be explored and
the performance of an exploration algorithm is measured by the length
of the trajectory of the robot.
We show exploration algorithms with complexity $O(P+A+sqrt{Ak})$,
where P is the total perimeter of the terrain (including perimeters of
obstacles), A is the area of the terrain (excluding obstacles), and k
is the number of obstacles. Our algorithms work for arbitrary
terrains, if one of the parameters A or k is known. We also prove a
matching lower bound $Omega(P+A+sqrt{Ak})$, even if the terrain is
known to the robot. |
| | Plus d'infos |
|
| 2010-04-12 | Au delà de l'évaluation en pire cas : comparaison et évaluation en moyenne de processus d'optimisation pour le problème du vertex cover et des arbres de connexion de groupes dynamiques |
14:00-15:00 Salle 178 |
La théorie de la complexité distingue les problèmes que l’on sait résoudre en un temps polynomial en la taille des données (que l'on peut qualifier de raisonnable), des problèmes NP-complets, qui nécessitent (en l'état actuel des connaissances) un temps de résolution exponentiel en la taille des données (que l'on peut qualifier de déraisonnable).
C’est pour cette raison que la communauté scientifique s’est tournée vers les algorithmes (polynomiaux) d’approximation dont la mesure de qualité se fait le plus souvent grâce au rapport d'approximation en pire cas (pour un problème de minimisation de taille, un algorithme possède un rapport d’approximation de k si la taille de toute solution pouvant être retournée par l’algorithme est inférieure ou égale à k fois la taille de la solution optimale).
Dans la littérature, on en vient à considérer qu'un algorithme est plus performant qu'un autre lorsqu'il possède un plus petit rapport d'approximation en pire cas. Cependant, il faut être conscient que cette mesure, désormais "classique", ne prend pas en compte la réalité de toutes les exécutions possibles d'un algorithme (elle ne considère que les exécutions menant à la plus mauvaise solution).
Mes travaux ont pour objet de mieux "capturer" le comportement des algorithmes d’approximation en allant plus loin que le simple rapport d’approximation en pire cas, et ce sur deux problèmes distincts :
I. Le problème du Vertex Cover
En montrant que les performances moyennes d’un algorithme peuvent être décorélées des performances en pire cas. Par exemple, nous avons montré que dans la classe des graphes spécialement conçus pour le piéger en pire cas, l'algorithme glouton "Maximum Degree Greedy" retourne, en moyenne, des solutions dont la taille tend vers l'optimum lorsque n tend vers l'infini.
En évaluant les performances moyennes d’un algorithme. Nous avons prouvé que l'algorithme online présenté par Demange et Paschos en 2005 (dont le rapport d'approximation en pire cas est égal au degré maximum du graphe) est au plus 2-approché en moyenne dans n'importe quel graphe. Ce résultat, combiné à d'autres, montre que cet algorithme est "en pratique" meilleur que la plupart des algorithmes 2-approchés connus, malgré un mauvais rapport d'approximation en pire cas.
En comparant les performances de différents algorithmes (analytiquement et expérimentalement). Nous avons proposé un algorithme de liste et nous avons prouvé analytiquement qu'il retourne toujours une meilleure solution que celle construite par un autre algorithme de liste récent [ORL 2006] quand ils traitent la même liste de sommets (dans certains graphes particuliers, la différence de taille peut être arbitrairement grande).
Nous avons également comparé analytiquement (en utilisant des outils comme les séries génératrices) les performances moyennes de six algorithmes sur les chemins. Nous les avons ensuite expérimentées sur un grand nombre de graphes de diverses familles bien choisies.
On constate dans ces études que les algorithmes 2-approchés étudiés sont ceux qui obtiennent les plus mauvaises performances en moyenne et que ceux qui ont les meilleurs comportements moyens ont de mauvais rapports d'approximation (fonction du degré max. du graphe).
Tous ces résultats montrent que le rapport d'approximation en pire cas n'est pas toujours suffisant pour caractériser l'intégralité de la qualité d'un algorithme et que d'autres analyses (en moyenne notamment) doivent être effectuées pour en faire le tour.
II. Le problème de la connexion de groupes dynamiques dans les réseaux
Nous avons analysé un processus de mise-à-jour d'un arbre connectant dans un réseau un groupe que les membres peuvent rejoindre ou quitter à tout moment. Notre processus possède de bonnes propriétés : il est simple à implémenter et il garantit, après chaque opération d'ajout ou de retrait, que le diamètre de l'arbre est au plus 2 fois l'optimal. Cependant, pour obtenir cette garantie, nous devons autoriser la reconstruction totale de l'arbre lorsque le membre identifié comme sa racine quitte le groupe. Ces étapes de reconstruction sont très coûteuses et nous cherchons donc à en évaluer le nombre.
Des travaux précédents montraient que dans le pire cas, il faut reconstruire (quasiment) à chaque étape pour conserver la garantie sur le diamètre. Nous montrons dans ces travaux (en utilisant les marches aléatoires, etc.) que, en fonction de certains paramètres du problèmes (comme les probabilités associées aux opérations d'ajout et de retrait), l'espérance du nombre de reconstructions est soit logarithmique en le nombre d'évènements (ajout ou retrait), soit constant. Ce résultat montre que le comportement moyen est très bon (malgré un pire cas très défavorable) et que notre processus de mise-à-jour peut être une solution viable en pratique. |
| | Plus d'infos |
|
| 2010-03-29 | Construction auto-stabilisante d'arbres pour des métriques non-locales |
14:00-15:00 Salle 178 |
Dans ma thèse, je me suis intéressé aux problèmes liés à la construction d'arbres couvrants dans des systèmes distribués auto-stabilisants. Les systèmes auto-stabilisants tolèrent les fautes et assurent qu'à la suite d'une perturbation temporaire du réseau, le système retrouve automatiquement sans intervention extérieure un comportement correcte, au bout d'un temps fini.
La structure d'arbre couvrant est couramment utilisée pour le routage dans les réseaux. Le problème est de savoir quel arbre couvrant choisir, car il en existe potentiellement une multitude. On détermine donc l'arbre couvrant que l'on souhaite construire par rapport à un critère que l'on désire optimiser. La plupart des travaux auto-stabilisants de construction d'arbre couvrant s'intéressent à des métriques basées sur les distances (DFS, BFS, arbre de plus courts chemins ...). L'optimisation de ces métriques se base uniquement sur les connaissances locales de chaque noeud (autrement dit le voisinage direct). Durant ce séminaire, je m'intéresserai à des métriques dont l'optimisation nécessite une information plus globale.
Tout d'abord, je présenterai un algorithme auto-stabilisant résolvant le problème de l'arbre couvrant de degré minimum qui permet de limiter l'engorgement des communications. Ce problème est NP-difficile à résoudre et nous avons proposé le premier algorithme auto-stabilisant résolvant ce problème et atteignant la meilleure approximation possible en temps polynomial.
Ensuite, je présenterai un autre algorithme auto-stabilisant pour construire un arbre couvrant de poids minimum. Notre approche améliore les solutions existantes de plusieurs façons. Elle ne nécessite aucune connaissance sur le réseau, elle améliore la taille mémoire utilisée et enfin elle garantie la propriété loop-free. Cette dernière amélioration assure que lors de la phase de convergence une structure d'arbre couvrant est préservée à tout moment si un arbre couvrant (quelconque) est construit, jusqu'à atteindre une configuration légitime.
|
| | Plus d'infos |
|
| 2010-03-22 | On the Performance of Transactional Memory: a theoretical Insight |
14:00-15:00 Salle 178 |
With the advent of multicore computing, many more programmers will need to develop concurrent programs in order to exploit advances in technology. Traditional lock-based concurrent programming makes difficult to achieve both correctness and performance: granularity tradeoffs, deadlock avoidance, lack of composability etc.
Transactional memory (TM) is a novel programming paradigm expected to simplify the design and verification of concurrent programs, while exploiting the maximum concurrency supported by the underlying multicore architecture. TM synchronizes threads via in-memory transactions. Transactions encapsulate sequences of operations on shared data items, and it is guaranteed that if any operation takes place, they all do, and that if they do, they appear to other threads to do so atomically. Performance of TMS is still a major challenge to address.
The talk will provide an introduction to the TM paradigm, will give some theoretical insight on the performance of TM implementations and will discuss some research directions.
|
| | Plus d'infos |
|
| 2010-03-08 | Des algorithmes auto-stabilisants - suite - |
14:00-15:00 Salle 178 |
Petit cours sur les algorithmes auto-stabilisants. Les concepts
basiques des algorithmes auto-stabilisants seront présentés et illustrés
par une étude de cas : la construction auto-stabilisante d’un arbre
couvrant. |
| | Plus d'infos |
|
| 2010-02-15 | Des algorithmes auto-stabilisants |
14:00-15:00 Amphi du LaBRI |
Petit cours sur les algorithmes auto-stabilisants. Les concepts
basiques des algorithmes auto-stabilisants seront présentés et illustrés
par une étude de cas : la construction auto-stabilisante d’un arbre
couvrant.
|
| | Plus d'infos |
|
| 2010-02-08 | Scheduling strategies for efficient interruptible algorithms |
14:00-15:00 Salle 178 |
In many AI applications, such as medical diagnostic systems and motion
planning under kinetic constraints, the available computation time is
uncertain. Interruptible algorithms are extremely useful in precisely
such environments: these algorithms have the property that they can be
interrupted at any point during their execution, at which point they must
be able to report some satisfactory solution. On the other hand, a contract
algorithm is an algorithm whose computation time is provided as part of its
input. Such algorithms may very well fail to return any meaningful solution,
if interrupted prior to their allotted execution time.
In this talk I will discuss black-box techniques for generating interruptible
versions of contract algorithms in a variety of settings. Our techniques
involve scheduling multiple executions of contract algorithms in identical
parallel processors, and in many cases optimal schedules can be obtained.
The presentation will survey some of the recent results and the future
challenges in related areas.
|
| | Plus d'infos |
|
| 2010-02-01 | The round complexity of agreement in partially synchronous systems |
14:00-15:00 Salle 178 |
Agreement or consensus is a fundamental problem in distributed
computing in which processes collectively choose a common value
from a large set of proposals. k-Set-agreement is a generalization of the
consensus problem in which processes have are allowed to collectively
choose k values from the set of proposals. The impossibility of
fault-tolerant set agreement in asynchronous networks
is one of the seminal results in distributed computing. In synchronous
networks, set-agreement is possible. The complexity of set agreement
has been a significant research challenge that has now been resolved.
However, real networks are neither purely synchronous nor purely
asynchronous. Rather, they tend to alternate between periods of
synchrony and periods of asynchrony. Nothing specific was known about
the complexity of set agreement in such a “partially synchronous”
setting. This talk presents the (asymptotically) tight bounds on the
complexity of set agreement in such systems. While doing so, we
highlight close connections between the basic models of distributed
computation: synchronous, partially synchronous, and asynchronous. We
introduce a technique for simulating, in a fault-prone asynchronous
shared memory, executions of an asynchronous and failure-prone
message-passing system in which some fragments appear synchronous to
some processes. We use this simulation technique to derive a lower
bound on the round complexity of set agreement in a partially
synchronous system by a reduction from asynchronous set agreement. Our
simulation technique is of independent interest. In particular, it
allows us to re-derive and extend existing lower bounds on the complexity of
synchronous early-deciding set agreement. |
| | Plus d'infos |
|
| 2010-01-25 | Caractérisation des hypothèses topologiques associées à des algorithmes distribués dans les réseaux dynamiques |
14:00-15:00 Salle 178 |
(joint work with Arnaud Casteigts and Afonso Ferreira)
Besides the complexity in time or in number of messages, a common
approach for analyzing distributed algorithms is to look at their
assumptions on the underlying network. This talk focuses on such
assumptions in dynamic networks, where the connectivity is expected
to change, predictably or not, during the execution.
The contribution of this work is a theoretical framework dedicated to
such analysis. By combining several existing components (local computations,
graph relabellings, and evolving graphs), this framework allows to express
detailed properties on the network dynamics and to prove that a given
property is necessary, or sufficient, for the success of an algorithm.
Consequences of this work include (i) the possibility to compare distributed
algorithms on the basis of their topological requirements, (ii) the elaboration
of a formal classification of dynamic networks with respect to these properties,
and (iii) the possibility to check automatically whether a network trace
belongs to one of the classes, and consequently to know which algorithm
should run on it.
|
| | Plus d'infos |
|
| 2010-01-18 | Job replication on multiserver systems |
14:00-15:00 Salle 178 |
Parallel processing is a way to use resources efficiently by processing
several jobs simultaneously on different servers. In a well controlled environment
where the status of the servers and the jobs are well known, everything is nearly
deterministic and replicating jobs on different servers is wasteful.
However, in a poorly controlled environment where the servers are
unreliable and/or their capacity is highly variable, it is desirable to
design a system that is robust in the sense that it is not affected by the poorly
performing servers. By replicating jobs and assigning them to several
different servers simultaneously, we not only achieve robustness but can
also make the system more efficient under certain conditions so that the
jobs are processed at a faster rate overall. We consider
the option of replicating jobs and study how the performance of different
“degrees” of replication, ranging from no replication to full
replication, affects the performance of a system of parallel servers.
|
| | Plus d'infos |
|
| 2010-01-11 | Optimalité et Competitivité de l'exploration de polygones par des robots mobiles |
14:00-15:00 Salle 178 |
Dans cet exposé, je montrerais comment un robot mobile peut explorer
efficacement un polygone. On considère des robots ayant une vision
limitée, c'est-à-dire qu'il ne voient que leur environnement se trouvant
soit dans un disque de rayon un (champ de vision circulaire) ou dans un
carré de coté deux (champ de vision carré) centré sur le robot. Notre
principal résultat est que l'exploration du bord d'un polygone
rectilinéaire (polygone dont chaque coté est soit vertical, soit
horizontal) peut se faire de manière optimale par un robot au champ de
vision carré qui part du bord du polygone. Dans tous les autres cas :
exploration totale du polygone, départ depuis l'intérieur du polygone ou
champ de vision circulaire, on montre que l'exploration optimale du
polygone est impossible.
|
| | Plus d'infos |
|
| 2010-01-04 | Overlay networks maximizing streaming throughput |
14:00-15:00 Salle 178 |
We consider the problem of broadcasting a large message in a large scale
distributed platform. The message must be sent from a source node, with
the help of the receiving peers which may forward the message to other
peers. In this context, we are interested in maximizing the throughput
(i.e. the maximum broadcast rate, once steady state has been reached).
The platform model does not assume that the topology of the platform is
known in advance, but rather associates to each node local properties
(incoming and outgoing bandwidth), and the goal is to build an overlay
which will be used to perform the broadcast operation. We model
contentions using the bounded multi-port model: a processor can be
involved simultaneously in several communications, provided that its
incoming and outgoing bandwidths are not exceeded. For the sake of
realism, it is also necessary to bound the number of simultaneous
connections that can be opened at a given node (i.e. its outdegree).
We prove that unfortunately, this additional constraint makes the
problem of maximizing the overall throughput NP-Complete. On the other
hand, we also propose a polynomial time algorithm based on a slight
resource augmentation to solve this problem.
|
| | Plus d'infos |
|
| 2009-12-18 | Comment se rencontrer de manière asynchrone dans un graphe quelconque |
14:00-15:00 Salle 178 |
Dans cet exposé, je montrerais comment deux agents mobiles peuvent se rencontrer dans un graphe quelconque et possiblement infini. Le graphe est inconnu des agents et ses sommets sont anonymes. À chaque étape, l'agent doit choisir un numéro de port correspondant à une des arêtes incidentes du sommet courant et traverser cette arête. Les deux agents se rencontrent s'ils sont sur un même sommet ou s'ils se croisent sur une arête. On considère le modèle asynchrone. C'est-à-dire que la durée de chaque étape d'un agent est déterminée par un adversaire omniscient qui essaye d'empêcher le rendez-vous. Les agents ont des identifiants uniques afin de permettre le rendez-vous de manière déterministe. En effet, sans identifiants, deux agents déterministes auraient le même comportement et ne se rencontreraient jamais dans un cycle. Je montrerais que le rendez-vous est toujours possible dans les graphes sous ces conditions et comment étendre ce résultat au rendez-vous d'agents mobiles dans le plan. |
| | Plus d'infos |
|
| 2009-12-14 | Optimisation des réseaux radio maillés et Routage dynamique |
14:00-15:00 Salle 178 |
Nous nous intéressons dans un premier temps aux problématiques
d'optimisation de la capacité des réseaux radio maillés. Nous
définissons la capacité d'un réseau comme la quantité de flot que peut
répartir équitablement une topologie aux utilisateurs qu'elle sert. Nous
étudions plus précisément le problème joint du routage et de
l'ordonnancement relié au Round Weighting Problem. Nous dérivons une
formulation qui élimine le routage pour se concentrer sur la capacité de
transport disponible sur les coupes du réseau. L'équivalence des
solutions optimales avec les formulations existantes est démontrée, et
le processus de résolution combine une génération de lignes et de
colonnes. Ces études mettent en évidence la présence d'une zone de
contention autour de chaque point d'accès qui contraint la capacité du
réseau.
Dans un second temps, nous présentons une étude de la stabilité d'un
protocole de routage depuis des sources vers des puits indifférenciés
dans un réseau à file d'attente modélisé par un multigraphe, dans lequel
le trafic est injecté de manière arbitraire au cours du temps. Nous
étudions le comportement d'un algorithme distribué et local de
transmission de paquets de proche en proche dans le réseau. A chaque
étape, un noeud transmet les paquets qu'il a en transit vers ses voisins
de manière à optimiser un gradient local. Nous montrons que ce protocole
est optimal dans le sens où le nombre de paquets en transit dans le
réseau reste borné tant que les sources injectent un flot qu'une autre
méthode saurait écouler.
|
| | Plus d'infos |
|
| 2009-12-14 | A rule-based language for distributed programming |
11:00-12:00 Salle 178 |
I will present a rule-based language, Netlog, to express distributed
applications such as communication protocols or P2P applications in a
declarative manner.
The language extends Datalog with communication primitives,
as well as aggregation and non-deterministic constructs, standard in
network applications.
Netlog admits a sound distributed fixpoint semantics, which takes
explicitly into account the in-node behavior as well as the
communication between nodes, and solves semantic problems raised in
declarative networking.
Our objective is to design languages which are easy to program,
portable over heterogeneous environments, as well as efficient to
execute. I will present hints in the efficiency we can expect from the
declarative programs, as well as how to make them easier to program.
The language has been implemented and runs over a virtual machine,
Netquest, which relies on a DBMS.
|
| | Plus d'infos |
|
| 2009-12-07 | Robustness of the rotor-router mechanism |
14:00-15:00 Salle 076 |
We consider the model of exploration of an undirected graph
G by a single agent which is called the rotor-router mechanism or
the Propp machine (among other names).
Let $pi_v$ indicate the edge adjacent to a node v which
the agent took on its last exit from v.
The next time when the agent enters node v,
first a "rotor" at node v advances pointer $pi_v$ to
the edge $next(pi_v)$ which is next after the edge $pi_v$ in a fixed cyclic
order of the edges adjacent to v.
Then the agent is directed onto edge $pi_v$ to move to the next node.
It was shown before that after initial O(mD) steps,
the agent periodically follows one established Eulerian cycle, that is,
in each period of 2m consecutive steps the agent traverses
each edge exactly twice, once in each direction.
The parameters m and D are the number of edges in G and the diameter of G.
We investigate the robustness of such exploration
in presence of faults in the pointers $pi_v$ or dynamic changes in the
graph.
We show that after the exploration establishes an Eulerian cycle,
(i) if at some step the values of
k pointers $pi_v$ are arbitrarily changed, then a new Eulerian
cycle is established
within O(km) steps;
(ii) if at some step k edges are added to the graph,
then a new Eulerian cycle is established
within O(km) steps;
(iii) if at some step an edge is deleted from the graph, then
a new Eulerian cycle is established
within $O(gamma m)$ steps, where $gamma$ is the smallest number of edges
in a cycle in graph G containing the deleted edge.
Our proofs are based on the relation between Eulerian cycles and
spanning trees known as the "BEST" Theorem (after de Bruijn, van
Aardenne-Ehrenfest, Smith and Tutte).
|
| | Plus d'infos |
|
| 2009-12-04 | Spanner géométrique planaire de degré au plus 6 |
14:00-15:00 Salle 178 |
We consider the problem of constructing planar spanners of Euclidean
graphs with the smallest maximum degree. We present a 6-spanner of
degree bound by 6. The best previous bound on the degree of planar
spanner was 14 with a stretch of $approx 3.53$. The spanner we proposed
can be easily computed the Triangular Distance Delaunay triangulation
introduced by Chew in 1989, that is known to have a stretch factor of 2
but its degree may not be bounded. (Travail réalisé en collaboration
avec Cyril Gavoille, Nicolas Hanusse et Ljubomir Perković.)
|
| | Plus d'infos |
|
| 2009-11-30 | Simulations de protocoles de routage compact : étude et simulation du protocole |
14:00-15:00 Salle 178 |
Due à l'extension de l'Internet, le protocole de routage BGP montre ses
limites notamment en terme de gestion du nombre d'entrées dans les
tables de routage. De nouveaux protocoles de routage permettant un
meilleur passage à l'échelle sont ainsi étudiés. Parmi ces protocoles,
les protocoles de routage dit compact sont prometteurs car ils
permettent de réduire de manière significative la taille des tables de
routage. Les performances de ces protocoles ne peuvent cependant pas
être facilement évaluées lors de tests grandeur nature. Il est ainsi
nécessaire de les simuler.
Nous nous proposons d'utiliser le protocole "Abraham" comme cas
d'étude. Ce protocole est un protocole de routage compact optimal : en
effet, quelque soit le graphe, il présente un étirement maximum de
3 pour des tables (locales) de routage en O(sqrt(n)*log(n)^0(1)).
Après avoir introduit brièvement le simulateur DRMSim, je présenterai le
protocole "Abraham", son implémentation dans DRMSim, quelques premiers
résultats obtenus. Finalement, deux challenges à relever seront
exposés : gestion de la dynamicité du réseau et gestion des
politiques de routage.
|
| | Plus d'infos |
|
| 2009-11-26 | Navigation dans les grands graphes |
14:00-16:00 Amphi du LaBRI |
(Soutenance HDR) |
| | Plus d'infos |
|
| 2009-11-23 | Preuves Formelles de Systèmes de Calculs Locaux, II |
14:00-15:00 Salle 178 |
Les calculs locaux sur les graphes, et en particulier les systèmes
de réétiquetage de graphes, constituent un outil pour le codage d'algorithmes
distribués, leur preuve de correction et l'analyse de leur pouvoir d'expression.
Un système de réétiquetage de graphes est un ensemble de
règles dont les membres gauche et droit sont des étiquetages définis sur
un même graphe connexe. Chaque règle décrit des modifications locales de
l'état d'un réseau et non de sa structure.
Dans le cadre du projet Visidia, nous nous intéressons à la preuve formelle
d'algorithmes et plus généralement de propriétés de ce modèle.
Les exposés seront autocontenus et comprendront une succinte présentation de
Coq, ainsi que des tactiques et stratégies de démonstration adaptées au domaine
décrit.
Les preuves complètes en Coq des résultats que nous montrons sont disponibles
sur la page du projet : http://www.labri.fr/~casteran/Loco.
|
| | Plus d'infos |
|
| 2009-11-16 | Algorithmic Methods for Large Communication Networks |
10:00-11:30 Amphi du LaBRI |
(Soutenance HDR) |
| | Plus d'infos |
|
| 2009-11-09 | Preuves Formelles de Systèmes de Calculs Locaux, I |
14:00-15:00 Salle 178 |
Les calculs locaux sur les graphes, et en particulier les systèmes
de réétiquetage de graphes, constituent un outil pour le codage d'algorithmes
distribués, leur preuve de correction et l'analyse de leur pouvoir d'expression.
Un système de réétiquetage de graphes est un ensemble de
règles dont les membres gauche et droit sont des étiquetages définis sur
un même graphe connexe. Chaque règle décrit des modifications locales de
l'état d'un réseau et non de sa structure.
Dans le cadre du projet Visidia, nous nous intéressons à la preuve formelle
d'algorithmes et plus généralement de propriétés de ce modèle.
Les exposés seront autocontenus et comprendront une succinte présentation de
Coq, ainsi que des tactiques et stratégies de démonstration adaptées au domaine
décrit.
Les preuves complètes en Coq des résultats que nous montrons sont disponibles
sur la page du projet : http://www.labri.fr/~casteran/Loco.
|
| | Plus d'infos |
|
| 2009-10-26 | IC-Scheduling Theory: A New Scheduling Paradigm for Internet-Based Computing |
14:00-15:00 Salle 178 |
Technological and economic developments have made the Internet a viable platform for a new
modality of Internet-based computing (IC). Within this modality, the owner of a large, typically
compute-intensive, computation enlists remote clients to “collaborate” in performing
the computation. When the computation comprises only independent tasks, the temporal unpredictability
of IC—communication is over the Internet; computing is by clients who arrive
unpredictably and are typically not dedicated to the computation—is at worst an annoying
source of slowdown. But, when the computation’s tasks have interdependencies that prioritize
their execution, then temporal unpredictability can confute attempts to benefit from “parallel”
execution of tasks and even cause a computation to stall for lack of unallocated eligible tasks.
In a series of papers, we have proposed a new scheduling paradigm that aims to respond to
the new challenges of IC. Faced with the impossibility (due to temporal unpredictability) of
scheduling to accommodate “critical paths” in a computation, we seek to schedule in a way that
always renders as many tasks as possible eligible for allocation to clients. This goal: maximizes
the utilization of available clients and minimizes the likelihood of stalling. We have formalized
this scheduling problem and, under idealized assumptions, have developed the beginnings of an
algorithmic theory for scheduling complex computations for IC.
We describe the concepts underlying the new theory and the algorithms that emerge from
them, illustrated via several familiar computations and computational paradigms. We describe
simulation experiments whose results suggest that the theory’s schedules have a measurable
benign effect on “real” Internet-based computing. |
| | Plus d'infos |
|
| 2009-10-19 | Presentation et analyse de quelques algorithmes distribues probabilistes |
10:00-12:00 Amphi du LaBRI |
(Soutenance HDR) |
| | Plus d'infos |
|
| 2009-10-16 | Euler tour lock-in problem in the rotor-router model |
14:00-15:00 Salle 178 |
(joint work with E. Bampas, L. Gasieniec, N. Hanusse, R. Klasing, and A. Kosowski) The rotor-router model, also called the Propp machine, was first considered as a deterministic alternative to the random walk. It is known that the route in an undirected graph G=(V,E), where |V|=n and |E|=m, adopted by an agent controlled by the rotor-router mechanism forms eventually an Euler tour based on arcs obtained via replacing each edge in G by two arcs with opposite direction. The process of ushering the agent to an Euler tour is referred to as the lock-in problem. In a recent work, Yanovski et al. proved that independently of the initial configuration of the rotor-router mechanism in G the agent locks-in in time bounded by 2m diam, where diam is the diameter of G.
In this paper we examine the dependence of the lock-in time on the initial configuration of the rotor-router mechanism. The case study is performed in the form of a game between a player intending to lock-in the agent in an Euler tour as quickly as possible and its adversary with the counter objective. |
| | Plus d'infos |
|
| 2009-09-14 | Quelques résultats sur les protocoles de population |
14:00-15:00 Salle 178 |
Les réseaux de capteurs mobiles font leur apparition en informatique
depuis plusieurs années. Les applications de ces réseaux sont nombreuses:
environnementales, militaires, économiques, écologiques... Certaines
caractéristiques de ces réseaux sont nouvelles et posent ainsi un défi
pour les concepteurs d'algorithmes que nous sommes.
Le modèle des protocoles de population [AAD+04] a été conçu pour
représenter formellement les réseaux de capteurs constitués d'agents
mobiles dont la mémoire est très limitée, sans aucun contrôle sur leur
propre mouvement. Nous étendrons ce modèle en un modèle plus hétérogène
dans lequel nous étudierons deux problèmes particuliers.
Dans cet exposé je présenterai en effet mes résultats sur deux types
d'algorithme, ceux de comptage, permettant de compter le nombre d'agents
présents dans le système, et ceux de rassemblement, permettant de
collecter les données mesurées par les différents agents du réseau.
|
| | Plus d'infos |
|
| 2009-06-29 | Computing Geometric Spanners Locally |
14:00-15:00 Salle 178 |
In this talk, I will discuss a project to develop efficient local distributed algorithms for
wireless communication by exploiting the geometry of wireless systems. A wireless
system is often modeled as a graph in the Euclidean space -- such as the Unit
Disk Graph (UDG) -- and geometric techniques are used to obtain insights about
the structure of such graphs. So far, we obtained insights that have led us to the
development of the currently most efficient local algorithms to construct:
1) a bounded-degree plane spanner of a UDG (useful for unicasting) and
2) a bounded-degree *lightweight* plane spanner of a UDG (useful for
unicasting and broadcasting).
I will describe the insights and techniques we developed.
There are still questions left open. It is not clear, for example, that the geometry
has been fully exploited. Lower bound arguments have also not been made.
Finally, we have not dealt with the issue of interference -- critical for battery
powered mobile devices. I will finish the talk by bringing up those questions.
|
| | Plus d'infos |
|
| 2009-05-25 | Vers une modélisation robuste des protocoles de routage pour VANET |
14:00-15:00 Salle 178 |
Un réseau de véhicules est un réseau ad hoc mobile constitué de noeuds
mobiles (les véhicules) qui communiquent via des liaisons sans-fil de
type WiFi. Les objectifs d'un tel réseau sont de contribuer à des
routes plus sûres et plus efficaces à l'avenir en fournissant des
informations opportunes aux conducteurs et aux autorités intéressées,
et de proposer des services ludiques aux passagers des véhicules
(chat, jeux, échange de fichiers multimedia...).
Un réseau de véhicules n'a ni infrastructure prédéterminée ni gestion
centralisée. Dans un tel réseau, chaque noeud assure les fonctions
d'un routeur et retransmet, si nécessaire, les paquets à ses voisins.
Un des principal défis des réseaux ad hoc est la conception de
protocoles de routage à la fois robustes (tolérant aux pannes, à la
mobilité des noeuds) et permettant le passage à l'échelle en terme de
distances et de nombre de noeuds. Les changements fréquents de
topologie impliquent une surcharge (overhead) importante de
l'utilisation du réseau dù aux messages de signalisation nécessaires
au fonctionnement du routage. Dans ce cadre, le choix d'un protocole
de routage limitant l'overhead augmente significativement les
performances globales du réseau d'un point de vu des utilisateurs. De
nombreuses études évaluent et comparent les protocoles de routage dans
les réseaux ad hoc par des simulations. Malheureusement, les résultats
dépendent souvent du choix du simulateur et de l'implémentation des
protocoles. Pour avoir des résultats plus pertinents, nous proposons
une méthode d'évaluation basée sur une analyse à la fois quantitatif
et stochastique. Son application nous permet de comparer de manière
détaillée les principaux types de protocole de routage dans les
réseaux de véhicules (réactifs, géographiques).
|
| | Plus d'infos |
|
| 2009-05-18 | Mobilité forte des applications distribuées communicantes |
14:00-15:00 Salle 178 |
La mobilité forte des processus est un mécanisme fréquemment utilisé dans les applications distribuées, déployées à la large échelle, comme support pour équilibrer la charge et réparer des pannes. La mobilité forte permet de transférer un processus d’un site source vers un site distant, et de poursuivre son exécution à partir du point d’interruption sur le site source. Le séminaire portera sur les problèmes de la mobilité forte dans les applications distribuées communicantes. Il présente une approche générique pour la mobilité des processus communicants basée sur la sérialisation des processus par la transformation de leurs codes sources, générant ainsi, des processus mobiles. Cette approche a été appliquée pour les architectures client/serveur et les celles orientées service. En particulier, les règles de transformation de code ont été appliquées pour les threads et les objets Java, les services web (WSRF), et les processus BEPL. Les expérimentations réalisées sur les différentes implantations montrent que le temps ajouté (overhead) par la transformation de code est négligeable. |
| | Plus d'infos |
|
| 2009-05-11 | Selfish wavelength assignment in multifiber optical networks |
14:00-15:00 Salle 178 |
We study path coloring games that describe situations in which
selfish entities possess communication requests in a multifiber
all-optical network. Each player is charged according to the maximum fiber
multiplicity that her color (wavelength) choice incurs and the social cost
is the maximum player cost. We investigate the price of anarchy of such
games and provide two different upper bounds for general graphs---namely
the number of wavelengths and the minimum length of a path of maximum
disutility, over all worst-case Nash Equilibria---as well as matching
lower bounds which hold even for trees. We also prove constant bounds for
the price of anarchy in chains and rings in which the number of
wavelengths is relatively small compared to the load of the network; in
the opposite case we show that the price of anarchy can be unbounded.
This is joint work with Aris Pagourtzis, George Pierrakos, and Katerina Potika. |
| | Plus d'infos |
|
| 2009-05-04 | What Can be Observed Locally? Round-based Models for Quantum Distributed Computing |
14:00-15:00 Salle 178 |
It is a well-established fact that, by resorting to quantum processing in
addition to manipulating classical information, it is possible to reduce
the time complexity of some centralized algorithms, and also to decrease
the bit size of messages exchanged in tasks requiring communication among
several agents.
This talk focuses on the impact of quantum information on ``locality'' in
distributed computing. Specifically, the object of the study is the
round-complexity of quantum distributed algorithms, when no bounds are
imposed on local computational power or on the message size. We consider
Linial's LOCAL model of a distributed system, augmented through two types
of quantum extensions: (1) initialization of the system in a quantum
entangled state, and/or (2) application of quantum communication channels.
For both types of extensions, we put forward valid proof-of-concept
examples of distributed problems whose round complexity is in fact reduced
through genuinely quantum effects, in contexts which do not depend on the
anonymity of nodes or the appearance of faults.
Finally, we show that even the quantum variants of the LOCAL model have
non-trivial limitations, captured by a very simple (purely probabilistic)
notion which we call ``physical locality''. While this is strictly weaker
than the ``computational locality'' of the classical LOCAL model, it
nevertheless implies that for many distributed combinatorial optimization
problems, such as Maximal Independent Set, the best currently known lower
time bounds cannot be broken by applying quantum processing, in any
conceivable way.
This is joint work with Cyril Gavoille. |
| | Plus d'infos |
|
| 2009-04-20 | Représentations de graphes pour l'algorithmique et la modélisation |
14:00-15:00 Salle 178 |
L'exposé abordera trois problématiques de représentation des graphes.
La première concerne les graphes d'intervalles et le maintien dynamique
d'un modèle d'intersection lorsque le graphe subit des modifications
d'arête ou de sommets. La solution proposée repose sur l'utilisation des
PQ-arbres et de la décomposition modulaire, dont nous montrons
l'équivalence pour les graphes d'intervalles, et débouche sur un
algorithme traitant les quatre opérations élémentaires (ajout et retrait
d'arête ou de sommet) en temps O(n).
La seconde partie de l'exposé sera consacrée à un problème de
modélisation des graphes de terrain, qui sont des graphes de taille très
importante rencontrés dans divers contextes pratiques. Récemment, il a
été proposé de modéliser ces graphes par le biparti d'incidence des
cliques maximales et des sommets. Cela a permis de générer aléatoirement
des graphes dont on contrôle à la fois la distribution des degrés et le
coefficient d'agglomération, ce qui n'avait jamais été réalisé jusqu'à
lors. L'approche souffre néanmoins d'un inconvénient majeur que nous
essaierons de corriger par l'introduction d'un modèle multiparti basé
sur la factorisation récursive des intersections de voisinages dans le
biparti. Nous aborderons la question de la convergence de ce procédé et
montrerons des liens forts avec une structure combinatoire bien connue,
l'ordre d'inclusion des intersections de cliques maximales.
Enfin, nous nous intéresserons à la possibilité de représenter les
voisinages dans un graphe de permutation de manière compacte. Le modèle
d'intersection de ces graphes requiert un espace O(n) et répond aux
requêtes d'adjacence entre deux sommets en temps constant. Qu'en est-il
des requêtes de voisinages? Nous construirons une structure de taille
O(n) qui permet de lister le voisinage d'un sommet de degrés d en temps
O(d). Nous donnerons un algorithme de parcours en largeur d'un graphe de
permutation qui fonctionne en temps O(n), améliorant ainsi la complexité
du problème des plus courts chemins, à origine unique et entre toutes
les paires, sur cette classe de graphes.
|
| | Plus d'infos |
|
| 2009-04-06 | Memory efficient anonymous graph exploration |
14:00-15:00 Salle 178 |
Efficient exploration of unknown or unmapped environments has become one
of the fundamental problem domains in algorithm design. Its applications
range from robot navigation in hazardous environments to rigorous
searching, indexing and analysing digital data available on the
Internet. A large number of exploration algorithms has been proposed
under various assumptions about the capability of mobile (exploring)
entities and various characteristics of the environment which are to be
explored. Here we consider the "graph model", where the environment is
represented by a graph of connections in which discrete moves are
permitted only along its edges. Designing efficient exploration
algorithms in this model has been extensively studied under a diverse
set of assumptions, e.g., directed vs undirected graphs, anonymous nodes
vs nodes with distinct identities, deterministic vs probabilistic
solutions, single vs multiple agent exploration, as well as in the
context of different complexity measures including the time complexity,
the memory consumption, and the use of other computational resources
such as tokens and messages. In this talk the emphasis is on memory
efficient exploration of anonymous graphs. We discuss in greater detail
three approaches: "random walk", "Propp machine" and "basic walk",
reviewing major relevant results, presenting recent developments, and
commenting on directions for further research.
|
| | Plus d'infos |
|
| 2009-03-23 | Construction auto-stabilisante et robuste de clusters de taille bornée |
14:00-15:00 Salle 178 |
Le procédé de clustering permet de regrouper les n½uds d’un réseau en groupes appelés clusters, où chaque cluster sera dirigé par un chef (clusterhead).
Une telle solution offre une organisation hiérarchique au réseau, ce qui facilite la tache de communication, et apporte plus de scalabilité au système. Cependant, pour plus d’efficacité, cette hiérarchie doit être établie le plus rapidement possible, et doit être maintenue dans le temps.
Les algorithmes auto-stabilisants permettent au système des retrouver, en un temps fini, sa cohérence de lui-même sans intervention extérieure, ni réinitialisation globale. Néanmoins, ces algorithmes ignorent complètement le comportement du système pendant la phase de stabilisation.
Notre travail porte sur l’amélioration du service offert par les algorithmes auto-stabilisants pendant leurs convergence, et donc, de concevoir des algorithmes auto-stabilisants garantissant un service minimum pendant la phase de stabilisation.
Nous proposons alors un algorithme de clustering à la fois auto-stabilisant et robuste, construisant des clusters respectant certaines propriétés. Nous montrerons que notre algorithme atteint, à partir de n’importe quel état initial, un état sûre en un nombre constant de rounds. Dans un état sûre, le réseau est partitionné en clusters de taille bornée, mais ces clusters ne vérifient pas forcément toutes les propriétés souhaitées. Pendant que le système évolue pour la construction des clusters finaux, l’algorithme garantie que le réseau reste partitionné (c.à.d. la hiérarchie reste toujours présente). |
| | Plus d'infos |
|
| 2009-02-02 | An Optimal Bit Complexity Randomised Distributed MIS Algorithm |
14:00-15:00 Salle 178 |
Joint work with Y. Métivier, J.M. Robson, N. Saheb-Djahromi.
We present a randomised distributed maximal independent set (MIS)
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:
thus its bit complexity per channel is $O(log n)$ (the bit complexity
is the number of bits we need to solve a distributed task, it measures
the communication complexity).
We assume that the graph is anonymous: unique identities are not
available to distinguish the processes; 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 the graph is known.
This algorithm is optimal (modulo a multiplicative constant) for the
bit complexity and improves the best previous randomised distributed
MIS algorithms (deduced from the randomised PRAM algorithm due to
Luby cite{Luby}) for general graphs which is $O(log^2 n)$ per
channel (it halts in time $O(log n)$ and the size of each message is
$log n$). This result is based on a powerful and general technique
for converting unrealistic exchanges of messages containing real
numbers drawn at random on each vertex of a network into
exchanges of bits. Then we consider a natural question:
what is the impact of a vertex inclusion in the MIS on distant
vertices? We prove that this impact vanishes rapidly as the distance
grows for bounded-degree vertices. We provide a counter-example that
shows this result does not hold in general. We prove also that these
results remain valid for Luby's algorithm presented by Lynch
cite{Lynch} and by Wattenhofer cite{Watten}. This question remains
open for the variant given by Peleg cite{Peleg}.
|
| | Plus d'infos |
|
| 2009-01-26 | Un algorithme distribué pour du clustering de ressources dans les plateformes à grande échelle |
14:00-15:00 Salle 178 |
Nous nous intéressons à un problème de clustering distribué dans des
plateformes à grande échelle. Pour cela nous avons recours à l'étude
d'un problème NP-Complet classique, le Bin
Covering (qui admet un PTAAS). En effet nous considérons que chaque hôte
de la plateforme possède une certaine puissance dans une caractéristique
particulière (disons sa capacité de stockage), modélisée par un poids.
Notre but est de former des groupes d'hôtes possédant une puissance
agrégée suffisante dans cette caractéristique pour satisfaire les
besoins des tâches à traiter. Nous ajoutons une contrainte sur les
latences séparant les éléments d'un même groupe de travail : deux hôtes
dans un même groupe ne doivent pas se trouver à plus d'une certaine
distance (fixée au départ) l'un de l'autre.
Nous présenterons alors un algorithme distribué permettant d'approcher
l'optimal à un facteur 1/3 en utilisant une augmentation de ressources
de 4, i.e. les groupes formés pourront avoir un diamètre de 4dmax. Cette
solution, presentée dans le cas où les hôtes sont dans Q^D pour une
petite valeur de D, utilise O(4^Dnlog n) messages et nécessite
O((4^D)log2 n) rounds dans un modèle synchrone. |
| | Plus d'infos |
|
| 2009-01-19 | Routage dans les réseaux (k,r)-cellulaires |
14:00-15:00 Salle 178 |
Fraigniaud et al. [FG01a] et indépendamment Thorup
et al. [TZ01] ont montré que tout arbre à $n$ noeuds
possède un schéma de routage de plus courts chemins utilisant des
adresses,
des en-têtes et des tables de routage de O(log n) bits. Il est toujours
ouvert de savoir si ce résultat optimal peut être étendu ne serait-ce
qu'aux réseaux de largeur arborescente deux dont la meilleure borne
connue, due à Peleg [Peleg00a] est O(log^2n) bits.
Dans cet article, nous étendons ce résultat optimal aux réseaux dits
$(k,r)$-cellulaires, c'est-à-dire aux réseaux ne contenant pas
$K_{2,r}$ comme mineur et dont les composantes 2-connexes peuvent être
rendues planaire-extérieures par la suppression de $k$ sommets. Par exemple,
les réseaux (2,4)-cellulaires contiennent les arbres, les graphes
planaire-extérieurs et plus généralement tous les graphes sans mineur
$K_{2,4}$.
keywords: routage compact, graphe sans mineur, graphe planaire, graphe
planaire-extérieur.
|
| | Plus d'infos |
|
| 2008-12-15 | Le mot circulant à déplacement aléatoire : un outil pour la conception d'algorithmes répartis |
14:00-15:00 Salle 178 |
L'écriture d'algorithmes répartis capables de gérer à la fois la
dynamicité des systèmes et l'occurrence de fautes, est un « exercice »
difficile. Afin de simplifier l'écriture de tels algorithmes, nous
avons conçu un outil élémentaire, une « brique de base » : le mot
circulant à déplacement aléatoire. Cet outil permet la découverte
d'un réseau, mais aussi peut être exploité comme élément de
structuration et de contrôle. Dans un premier temps, nous
présenterons précisément les mots circulants à déplacement
aléatoire, puis nous en montrerons les capacités de structuration.
Enfin, nous proposerons deux applications spécifiques : la découverte
de ressources dans un réseau, puis l'exclusion mutuelle.
|
| | Plus d'infos |
|
| 2008-12-08 | Fault-tolerant implementations of regular register by safe register |
14:00-15:00 Salle 178 |
Lamport defined three classes of communication registers: safe, regular.
and atomic, in his seminal paper ("On Interprocess Communication", dc,
1986).
The class of a register R depends on the returned values by a read
operation of R overlapped by write operations on R.
Register R is safe if a read operation that does overlap write
operation returns any value.
Register R is regular if any read operation that overlaps a write
returns the value of either the latest write that happens-before it, or
the value of some overlapping write.
In any register R, a read operation that does not overlap any write,
returns the value of the latest write on R that happens-before it.
Lamports gives a wait-free implementation of a
single-writer/single-reader regular binary register
from only one single-writer/single-reader binary safe register.
One extension to the research initiated by Lamport arises from asking
whether wait-free and self-stabilizing constructions of regular
registers from weak one can be made.
Wait-freedom, captures tolerance of stopping failures of components of
the network; and self-stabilization, captures recovery of the network
from transient errors of its components.
Lamport transformation is not self-stabilizing. In fact, as established
by Hoepman, Papatrianfafiou and Tsigas ("Self-stabilization of wait-free
shared memory objects",jpdc, 2002) there is no wait-free and
self-stabilizing
implementation of a single-writer/single-reader regular binary register
with only one single-writer/single-reader safe binary register.
In this talk we present a wait-free and self-stabilizing implementation
of a single-writer/single-reader regular register by several
single-writer/single-reader safe registers.
This is joint work with Lisa Higham.
|
| | Plus d'infos |
|
| 2008-12-01 | Connectivity in Multi-Interface Networks |
14:00-15:00 Salle 178 |
A multi-interface network is modeled by a graph whose nodes correspond to
a set of wireless devices communicating by means of multiple radio
interfaces, according to the proximity and common interfaces. A connection
is covered (activated) when the endpoints of the corresponding edge share
at least one active interface. In this context, we study centralized and
distributed algorithms for the problem of covering a spanning subgraph, and
also look at two other important networking problems: covering all the
connections, and covering a specified communication path. The applied
optimization criterion is motivated by issues of energy consumption
minimization. |
| | Plus d'infos |
|
| 2008-11-24 | Allocation of Clients to Multiple Servers on Large Scale Heterogeneous Platforms |
14:00-15:00 Salle 178 |
Joint work with Olivier Beaumont, Lionel Eyraud-Dubois and Hejer Rejeb.
In this presentation, we consider the problem of allocating a large
number of independent, equal-sized tasks to a heterogeneous large
scale computing platforms, such as BOINC or Folding@home. We model the
platform using a set of servers (masters) that initially hold (or
generate) the tasks to be processed by a set of clients (slaves). All
resources have different speeds of communication and computation and
we model contentions using the bounded multi-port model. Under this
model, a processor can be involved simultaneously in several
communications, provided that its incoming and outgoing bandwidths are
not exceeded. This model corresponds well to modern networking
technologies, but for the sake of realism, another parameter needs to
be introduced in order to bound the number of simultaneous connexions
that can be opened at a server node. We prove that unfortunately, this
additional parameter makes the problem of maximizing the overall
throughput (i.e. the fractional number of tasks that can be processed
within one time-unit) NP-Complete. This result is closely related to
results on bin packing with splittable items and cardinality
constraints. On the other hand, we also propose a sophisticated
polynomial time algorithm, based on a slight resource augmentation to
solve this problem. More specifically, we prove that, if dj denotes
the maximal number of connexions that can be opened at node Sj , then
the throughput achieved using this algorithm and dj + 1 is at least
the same as the optimal one with dj . We also provide a dual algorithm
for minimizing the maximal number of connexions that need to be opened
in order to achieve a given throughput. Finally, we also propose
extensive simulations to assess the performance of proposed algorithm.
|
| | Plus d'infos |
|
| 2008-10-20 | Présentation de la plateforme visidia |
14:30-15:30 Salle 178 |
Dans le cadre de la fête du LaBRI, M. Mosbah présente la plateforme
visidia au groupe de travail algorithmique distribuée (ouvert aux
autres membres du labo) le lundi 20 octobre à 14h30 - salle 178
L'exposé aura deux parties: Présentation de visidia et démonstration
Visidia est un logiciel qui permet d'implanter, de visualiser et
d'animer un algorithme distribué. Cet outil offre une interface
graphique permettant de construire un graphe, représentant le réseau, à
l'aide de la souris, et de programmer un algorithme distribué en
utilisant une bibliothèque de primitives de base. Plusieurs algorithmes
(arbre recouvrant, élection) sont déjà implémentés et peuvent être
visualisés directement par l'utilisateur. A chaque noeud du graphe, le
logiciel visidia associe automatiquement un processus léger (thread) et
une copie de l'algorithme à exécuter. La visualisation consiste à animer
les évènements (de haut niveau) lors de l'exécution d'un algorithme
(envoi de message, changement d'état, progression du calcul). Visidia
est utilisé pour l'enseignement d'algorithmes distribués et pour la mise
au point ou l'analyse d'algorithmes.
Des extensions de visidia aux agents mobiles et aux réseaux de capteurs
seront également présentées.
|
| | Plus d'infos |
|
| 2008-10-13 | Construction locale de sous-graphes couvrants épars |
14:00-15:00 Salle 178 |
La construction de "squelette" d'un graphe, c'est-à-dire de
sous-graphe couvrant peu denses approximant les distances, est à la
base de nombreuses solutions algorithmiques pour résoudre des
problèmes de calcul de distance, de routage, de voyageur de commerce,
de synchronisation de calculs distribués, etc.
Nous présenterons un nouvel algorithme permettant de réaliser un
compromis optimal entre le facteur d'approximation des distances et le
nombre d'arêtes du squelette. Une caractéristique importante de notre
algorithme est qu'il est "local": tout sommet peut décider des arêtes
incidentes à garder dans le squelette final en fonction de son
voisinage à distance borné.
(avec B. Derbel, D. Peleg, L. Viennot) |
| | Plus d'infos |
|
| 2008-09-15 | Rendezvous of Mobile Agents in Anonymous Graphs |
14:00-15:00 Salle 178 |
A typical and well-studied problem in mobile distributed computing is the
Rendezvous problem defined as follows. There are k mobile agents
dispersed among the nodes of an undirected connected graph
(of size n) and the objective is to gather the agents in a single node
of the graph. The agents are allowed to move along the edges of the
graph and they communicate with each-other by writing messages on public
whiteboards present at each node. Since the nodes of the graph are
initially unlabelled (and thus indistinguishable except for their
degree), it is difficult for the agents to decide on a common meeting
point. We present several solutions for the Rendezvous problem under
different conditions on the initial knowledge available to the agents.
|
| | Plus d'infos |
|
| 2008-06-30 | Analysis of two randomized algorithms for maximal matching |
14:00-15:00 Salle 178 |
We introduce and study two versions of a randomized algorithm
based on dynamic timetable handshake. Each process of the network
generates a random time in the real interval [0,1]. This number is
supposed to be a possible time for a handshake, if both processes are
available at that time. Whenever the clock reaches the smallest
generated item, there will be a handshake between the process that
proposes the item and the requested one and they cancel all other data
from their timetable, informing their other neighboring processes. The
algorithm continues in the remaining processes with the updated
timetable (for the first version of the algorithm) or with a new
generated timetable (for the second one) until a maximal matching is
obtained.
We analyze the efficiency of the first algorithm in terms of the size of
the matching and the complexity of the second one in terms of its phase
number.
|
| | Plus d'infos |
|
| 2008-06-23 | Routing without Ordering |
14:00-15:00 Salle 178 |
We analyze the correctness and the complexity of two well-known routing
algorithms, introduced by Gafni and Bertsekas (1981): By reversing the
directions of some edges, these algorithms transform a directed acyclic
input graph into a graph in a way such that there exists at least one
route from each node to a special destination node (while maintaining
acyclicity). The resulting graph can thus be used to route messages in
a loop-free manner.
Gafni and Bertsekas translate these routing algorithms into ordering
algorithms in which each node of the graph maintains an unbounded
"height" in some total order, which indicate the directions of its incident
edges. In this work, we present a novel formalization for these algorithms
based only on directed graphs with binary labels for edges. Using this
formalization, we define a general class of distributed algorithms for
establishing routes in acyclic graphs, and we derive requirements
on the input graph for correctness of the algorithms. Moreover, this
simple formalization allows us to give an exact analysis of their complexity.
In particular, we provide expressions for the exact number of steps taken
during an execution of the algorithm, and prove that this complexity
measure only depends on the input graph.
Joint work of: Bernadette Charron-Bost, Antoine Gaillard, Jennifer
L. Welch, and Josef Widder
|
| | Plus d'infos |
|
| 2008-06-16 | Recherche optimale de trou noir avec cailloux |
14:00-15:00 Salle 178 |
Un trou noir est un n{oe}ud d'un réseau qui détruit tout agent (ou
robot) y entrant sans laisser de trace détectable. L'emplacement du
trou noir doit être déterminé par une une équipe d'agents mobiles
identiques déployée à partir d'un emplacement sain. Pratiquement
tous les résultats existants pour des agents asynchrones supposent
la présence à chaque n{oe}ud d'une mémoire partagée (tableau
blanc), de taille logarithmique, sur laquelle les agents peuvent
lire et écrire. Un méchanisme moins puissant et moins exigeant
consiste en l'utilisation de cailloux identiques (qui peuvent être
déposés sur les n{oe}uds, repris, et transportés par les agents),
traditionnellement employés pour l'exploration de graphes sains
({em i.e.} sans trou noir). Deux résultats récents montrent qu'il
est possible d'utiliser des cailloux comme moyen de communication
pour la recherche de trou noir. Ces résultats autorisent cependant
les cailloux à être placés non seulement sur les n{oe}uds mais
aussi sur les liens. Ils supposent également que les liens sont
FIFO.
Dans ce papier, nous considérons le modèle des cailloux idéaux,
c'est-à-dire le modèle où un caillou ne peut être placé que sur les
n{oe}uds, et pas plus d'un caillou ne peut être placé sur un
n{oe}ud donné. Nous prouvons que pour les réseaux de topologie
connue il est possible d'obtenir exactement les mêmes bornes
optimales en utilisant des cailloux idéaux qu'en utilisant des
tableaux blancs, et ce même si les liens ne sont pas FIFO. Plus
précisément, nous prouvons qu'une équipe de {em deux} agents
asynchrones, chacun équipé d'un seul caillou indistinguable (qui ne
peut être placé que sur les n{oe}uds, avec au plus un caillou par
n{oe}ud), peut localiser le trou noir. Ce résultat est obtenu en
utilisant le nombre optimal de mouvements $Theta(n log n)$, où $n$
est le nombre de n{oe}uds.
Pour résumer, nous fournissons la première preuve que, pour la
recherche de trou noir, le modèle des cailloux idéaux est aussi
puissant que le modèle des tableaux blancs.
|
| | Plus d'infos |
|
| 2008-06-09 | Skew-CCC - degree 3 suffices to build an overlay network in a distributed way |
14:00-15:00 Salle 178 |
We present a dynamic version of the Cube Connected Cycles network.
Nodes are allowed to join and leave the network and if a node joins
the network we assume it knows one node that is already a participant.
We assume that each pair of nodes can potentially become neighbors but
also that degree of nodes has to be bounded by 3. In our structure
nodes have indeed degree of at most 3 and time of all basic operations
(join, search, leave, routing) is logarithmic in the current number of
nodes (even though the latter is not known).
Basic two ideas behind the construction: the dimension of the network
is not defined globally - it might differ in different parts of the
network. Another concept: if one throws n log n balls into n bins,
each bin contains order log n balls. We form such bins in a virtual /
distributed way (as corners of a hypercube) and nodes in a bin form a
cycle of logarithmic size.
(This is joint work with Andre Brinkmann and Marcin Bienkowski.) |
| | Plus d'infos |
|
| 2008-06-02 | Élection probabiliste dans les arbres |
14:00-15:00 Salle 076 |
Dans cet exposé, on s'intéresse au problème de l'élection dans un
arbre. Les algorithmes que nous présentons sont basés sur une suite
d'effeuillages de l'arbre jusqu'à ce qu'il soit réduit à un seul
sommet : le sommet élu.
Le schéma d'effeuillage est facile à comprendre, cependant son (ses)
implémentation et son analyse soulèvent des questions intéressantes :
comment l'implémenter de manière distribuée ? quel est le sommet qui
a la plus forte probabilité d'être élu ? est-il possible d'influencer
la probabilité d'élection d'un sommet ? ...
Je présenterai des réponses à ces questions et en particulier, une
implémentation permettant d'obtenir une élection parfaitement
équitable : tous les sommet ont la même probabilité d'être élu.
|
| | Plus d'infos |
|
| 2008-05-26 | Locating and repairing faults in a network with mobile agents |
14:00-15:00 Salle 178 |
We consider a fixed, undirected, known network and a number of mobile
agents which can traverse the network in synchronized steps. Some
nodes in the network may be faulty and the agents are to find the
faults and repair them. The agents could be software agents, if the
underlying network represents a computer network, or robots, if the
underlying network represents some potentially hazardous physical
terrain. We consider the case where one agent can repair only one
faulty node. After repairing the fault, the agent dies. This model
can be viewed as a variant of the "black hole search" model. We show
that a simple deterministic algorithm for this problem terminates
within O(n/k + D log f/ loglog f) steps, where n is the number of
nodes in the network, D is the diameter of the network, k is the
number of agents, and f = min{n/k, n/D}; assuming that the number of
faulty nodes is at most k/2. We also prove the matching lower bound.
This is joint work with Colin Cooper and Ralf Klasing.
|
| | Plus d'infos |
|
| 2008-05-19 | Rendez-vous d'agents mobiles dans des réseaux non-fiables |
14:00-15:00 Salle 178 |
Dans cet exposé, on considère un ensemble d'agents mobiles dispersé sur
un réseau (modélisé par un graphe) et on veut que tous les agents se
regroupent sur un seul noeud du réseau (c'est le problème du
rendez-vous). On suppose que le réseau et les agents sont anonymes (les
sommets et les agents n'ont pas d'identifiants).
On suppose par ailleurs que des noeuds du réseau ou des liens de
communication sont défaillants. Tout agent entrant dans un de ces
sommets ou traversant un de ces liens est détruit.
L'objectif est de minimiser le nombre d'agents détruits et de rassembler
les agents restants. On caractérise les réseaux dans lesquels on peut
résoudre le rendez-vous. On étudie aussi quelles sont les connaissances
initiales nécessaires et/ou suffisantes à propos du réseau pour pouvoir
résoudre le problème.
(Travail réalisé avec Shantanu Das et Nicola Santoro)
|
| | Plus d'infos |
|
| 2008-05-05 | Multiple random walks on random regular graphs |
14:00-15:00 Salle 178 |
In this talk we study problems arising from multiple random walks under
various assumption of interaction between the particles. Results include,
cover time, time to broadcast and time coalesce to a single walk.
To make the results precise, we make the analysis on random regular graphs,
although this is mainly for convenience.
It was shown (by Cooper and Frieze), that for $rge 3$ the cover time $C_G$
of a random $r$-regular graph $G_r$ by a single random walk is asymptotic
to $ heta_r n ln n$, where $ heta_r=({r-1})/({r-2})$, is a parameter
which occurs throughout the results given below. This result holds whp
(with probability tending to one as the number of vertices $n$ tends to
infinity).
For $k$ random walks we establish the following (whp) results.
(i) The time for $k$ independent walks to cover $G_r$ is asymptotic to $ C_G/k$.
i.e. the speed up in search time is linear in $k$ the number of agents.
(ii) For most starting positions, the expected number of steps before any of
the walks meet is $ heta_r n/{kchoose 2}$.
(iii) If the walks can communicate on meeting at a vertex, we show that
(for most starting positions) the expected time for $k$ walks to broadcast
a single piece of information is asymptotic to $((2 ln k)/k) heta_r n$, as
$k,n$ tend to infinity.
(iv) We also consider properties of walks where particles interact when
they meet at a vertex by coalescing, or by exploding and destroying each
other. As an example, the expected extinction time of $k$ explosive particles
($k$ even) tends to $(2ln 2) heta_r n $ as $k$ tends to infinity.
(v) If the particles coalesce on meeting, then if one particle stars at each
vertex, the expected time to coalesce to a single walk is $2 heta_r n$.
By a time reversal argument, this is the expected time for the completion
of the voter problem, which is defined as follows: Initially each vertex
has a distinct opinion. At each time step each vertex $i$ contacts a random
neighbour $j$ and adopts the opinion of $j$. Thus $2 heta_r n$ is the
expected time until a single opinion emerges.
|
| | Plus d'infos |
|
| 2008-04-21 | Performance of Scheduling Policies and Networks in Generalized
Adversarial Queueing Models |
14:00-15:00 Salle 178 |
In this talk we will see the presentation of the thesis "Performance
of Scheduling Policies and Networks in Generalized Adversarial
Queueing Models". This thesis was presented on March 15, under a
supervision of Universidad de Chile and Universidad Rey Juan Carlos
(Spain). The framework of this work is called Adversarial Queueing
Theory (AQT), it was presented by Borodin et al in 2001. The goal of
the AQT model is the study queueing systems under a worst case
analyzes. The main contribution of this thesis is the definition of
three generalizations of the AQT model. Each one is specially well
adjusted to analyze different kinds of network problems. Mainly,
these generalizations attempt to represent real communication and
production networks, and more precisely attempt to capture issues
concerning the queues generated in them.
|
| | Plus d'infos |
|
| 2008-04-14 | De l'espace mémoire nécessaire aux algorithmes auto-stabilisants |
14:00-15:00 Salle 178 |
La notion d'auto-stabilisation a été introduite par Edsger
Dijkstra en 1974 : Quel que soit son état initial, un système
auto-stabilisant est certain d'atteindre un état cohérent en un nombre
fini d'étapes. Une telle propriété est hautement souhaitable, car après
une perturbation inattendue de l'état des mémoires des processus, un
système auto-stabilisant retourne finalement à un état correct sans aucune
intervention extérieure.
Les deux principaux problèmes "étalons" de l'algorithmique distribuée sont
l'élection de leader et l'exclusion mutuelle. Je me suis intéressée à
concevoir des solutions auto-stabilisantes à ces problèmes dans le cadre
d'anneaux anonymes. Dans la plus part des cas, il n'existe pas
d'algorithme déterministe et auto-stabilisant d'élection de leader, ni
d'exclusion mutuelle. J'ai donc proposé des algorithmes probabilistes. Je
me suis particulièrement attachée, à concevoir des solutions optimales en
terme d'espace mémoire.
|
| | Plus d'infos |
|
| 2008-04-07 | Tolérance aux pannes des réseaux multiniveaux : modélisation par
des graphes colorés |
14:00-15:00 Salle 178 |
Pour des raisons historiques, les réseaux de télécommunication sont
composés d'un empilement de niveaux technologiques assurant chacun des
fonctions spécifiques rendant la gestion du réseau très complexe. Les
technologies récentes permettent de simplifier cet empilement et de
converger vers un modèle IP/WDM dans lequel l'architecture MPLS (Multi
Protocol Label Switching), ou son extension GMPLS (Generalized-MPLS),
est de plus en plus employée. C'est ce modèle restreint à deux niveaux
que nous considérons. Ces réseaux multiniveaux comportent donc un
niveau physique et un seul niveau virtuel dont les liens sont des routes
pré-établies du niveau physique et sur lequel est routé un ensemble de
requêtes provenant des utilisateurs du réseau.
Cet empilement implique que lorsqu'une panne survient au niveau
physique, elle se traduit par un ensemble de pannes simultanées au
niveau virtuel. Cet ensemble de ressources virtuelles soumises aux mêmes
pannes est un groupe de risque. Les graphes colorés permettent de
modéliser les réseaux multiniveaux en associant à chaque arête du niveau
virtuel des couleurs symbolisant les risques de pannes auxquels elle est
soumise.
Dans les graphes colorés nous étudions des problèmes fondamentaux liés
à la connexité (existence d'ensembles de
chemins particuliers, arbre) du réseau représenté ainsi qu'à sa
vulnérabilité aux pannes (coupes). La mesure n'est plus le nombre
d'arêtes utilisées comme dans les graphes classiques, mais le nombre de
couleurs. Avec cette nouvelle mesure, nous verrons que tout se complique.
|
| | Plus d'infos |
|
| 2008-03-31 | Snap-stabilization in Message-Passing Systems |
14:00-15:00 Salle 178 |
In this presentation, we tackle the open problem of snap-stabilization in
message-passing systems.
Snap-stabilization is a nice approach to design protocols that withstand
transient faults. Compared to the well-known self-stabilization approach,
snap-stabilization guarantees that the effect of faults is contained
immediately after faults cease to occur.
Our contribution is twofold:
- First, we show that snap-stabilization is impossible for a wide class of
problems if we consider networks with finite yet unbounded link capacity.
- Second, we show that snap-stabilization becomes possible in the same
setting if we assume bounded-capacity links. We propose three
snap-stabilizing protocols working in fully-connected networks.
Our work opens exciting new research perspectives, as it enables the
snap-stabilizing paradigm to be implemented in actual networks.
|
| | Plus d'infos |
|
| 2008-02-11 | Reoptimization Problems: Hardness and Algorithms |
14:00-15:00 Salle 178 |
Given an instance of an optimization problem together with an optimal
solution, our goal is to find a high-quality solution for a locally
modified instance. The talk will provides a survey of this kind of
problems. In order to partially answer how useful the additional
information is, recent hardness results and approximation algorithms for
reoptimizing the travelling salesman problem and the Steiner tree
problem are presented.
|
| | Plus d'infos |
|
| 2008-02-04 | An Efficient Message Passing Election Algorithm based on Mazurkiewicz's Algorithm |
14:00-15:00 Salle 178 |
We study the election and the naming problems in the asynchronous
message passing model. We present a necessary condition based on
Angluin's lifting lemma that must be satisfied by any network
that admits a naming (or an election) algorithm. We then show that
this necessary condition is also sufficient: we present an election
and naming algorithm based on Mazurkiewicz's algorithm.
The algorithm we obtained is totally asynchronous and it
needs a polynomial number of messages of polynomial size, whereas
previous election algorithms in this model are pseudo-synchronous and
use messages of exponential size.
(travail réalisé avec Jérémie Chalopin)
|
| | Plus d'infos |
|
| 2008-01-28 | L'algorithme d'élection de Mazurkiewicz dans les étoiles |
14:00-15:00 Salle 178 |
Présentation de l'algorithme de Mazurkiewicz avec sa preuve
dans le modèle des calculs locaux où en un pas de calcul
un sommet consulte et modifie son état ainsi que les
états de ses voisins. |
| | Plus d'infos |
|
| 2007-12-12 | Energy and Time Efficient Broadcasting in Known Topology Radio Networks |
14:00-15:00 Salle 178 |
We consider broadcasting protocols in radio networks with known topology that are efficient in both time and energy. The radio network is modeled as an undirected graph G=(V,E) where |V|=n. It is assumed that during execution of the communication task every node in V is allowed to transmit at most once. Under this assumption it is shown that any radio broadcast protocol requires D+Omega(sqrt{n-D}) transmission rounds, where D is the diameter of G. This lower bound is complemented with an efficient construction of a deterministic protocol that accomplishes broadcasting in D+O(sqrt{n}log n) rounds. Moreover, if we allow each node to transmit at most k times, the lower bound D+Omega((n-D)^{1/(2k)}) on the number of transmission rounds holds. We also provide a randomized protocol that accomplishes broadcasting in D+O(kn^{1/(k-2)}log2 n) rounds. We conclude with a discussion of several other strategies for energy efficient radio broadcasting and a number of open problems in the area.
(joint work with Erez Kantor, Dariusz R. Kowalski, David Peleg, and Chang Su) |
| | Plus d'infos |
|
| 2007-12-12 | Gathering few fat robots |
15:00-16:00 Salle 178 |
Autonomous identical robots represented by unit discs move deterministically in the plane. They do not have any common coordinate system, do not communicate, do not have memory of the past and are totally asynchronous. Gathering such robots means forming a configuration for which the union of all discs representing them is connected. We solve the gathering problem for at most four robots. This is the first algorithmic result on gathering robots represented by two-dimensional figures rather than points in the plain: we call such robots {em fat}.
|
| | Plus d'infos |
|
| 2007-12-03 | Bin covering distribué avec contrainte de distance pour les plates
formes à grande échelle - Pistes pour une version multidimensionnelle |
14:00-15:00 Salle 178 |
Les plates formes à grande échelle s'intéressent aux ressources non
utilisés chez des utilisateurs reliées entre elles par Internet en vue de
les exploiter pour des problèmes parallélisables. L'objectif est
d'étendre ce système au travail de manière distribuée sur des
problèmes de taille importante, parallélisables et tels que chaque tâche
indépendante soit assez importante pour devoir être traitée par de
petits groupes de ressources. La formation de groupes de travail se ramène
à du bin covering distribué, et, comme il ne doit pas y avoir
d'éléments trop loin les uns des autres au sein d'un même groupe, une
contrainte de distance apparait. Le bin covering consiste, étant donnée
une liste d'éléments pondérés, à les assembler en groupes de poids
total supérieur à une certaine valeur, en essayant de maximiser le nombre
de groupes formés. Nous obtenons plusieurs résultats intéressants sur la
constuction de groupes de manière distribuée, sans contrainte de distance
tout d'abord, puis en incluant la contrainte de distance en dimension 1.
Seront enfin évoquées les pistes de travail pour des solutions en
dimensions supérieures, notamment l'utilisation d'une relaxation de la
contrainte de distance.
|
| | Plus d'infos |
|
| 2007-11-26 | Calculs locaux sur les arêtes (suite) |
14:00-15:00 Salle 178 |
Cet exposé présente différents modèles de systèmes distribués.
Ces modèles correspondent à différents niveaux d'abstraction et à
différents niveaux de synchronisation entre les processus. Ces modèles
sont étudiés à travers le problème de l'élection qui met en évidence
les bons objets combinatoires pour les comprendre et comparer leur
puissance. Cette étude permet d'obtenir une caractérisation des réseaux
asynchrones qui communiquent par échange de messages en mode synchrone
et admettant un algorithme d'élection (idem pour les réseaux fonctionnant
suivant le modèle d'Angluin).
Cette étude permet également d'obtenir une caractérisation des réseaux
asynchrones qui communiquent par échange de messages en mode asynchrone
et admettant un algorithme d'élection. Cet algorithme nécessite un nombre
polynomial de messages de taille polynomiale alors que le précédent
algorithme, du à Yamashita et Kameda, nécessite un nombre polynomial de
messages de taille exponentielle.
(Ce travail a été effectué en collaboration avec Jérémie Chalopin,
CNRS-LIF-Marseille).
|
| | Plus d'infos |
|
| 2007-11-19 | Calculs locaux sur les arêtes |
14:00-15:00 Salle 178 |
Cet exposé présente différents modèles de systèmes distribués.
Ces modèles correspondent à différents niveaux d'abstraction et à
différents niveaux de synchronisation entre les processus. Ces modèles
sont étudiés à travers le problème de l'élection qui met en évidence
les bons objets combinatoires pour les comprendre et comparer leur
puissance. Cette étude permet d'obtenir une caractérisation des réseaux
asynchrones qui communiquent par échange de messages en mode synchrone
et admettant un algorithme d'élection (idem pour les réseaux fonctionnant
suivant le modèle d'Angluin).
Cette étude permet également d'obtenir une caractérisation des réseaux
asynchrones qui communiquent par échange de messages en mode asynchrone
et admettant un algorithme d'élection. Cet algorithme nécessite un nombre
polynomial de messages de taille polynomiale alors que le précédent
algorithme, du à Yamashita et Kameda, nécessite un nombre polynomial de
messages de taille exponentielle.
(Ce travail a été effectué en collaboration avec Jérémie Chalopin,
CNRS-LIF-Marseille).
|
| | Plus d'infos |
|
| 2007-10-01 | Efficient Randomised Broadcasting in Random Regular Graphs and Peer-to-Peer Systems |
14:00-15:00 Salle 178 |
We consider two simple modifications of the so-called random phone
call model in order to broadcast a message in optimal time and with
minimal number of message transmissions in overlays for peer-to-peer
systems modelled by random regular graphs. In the original random
phone call model of Karp et al. (FOCS'00) it is assumed that in each
time step every node of a (complete) graph calls a neighbor, chosen
uniformly at random, and establishes a communication channel with this
neighbor. Any node $u$ is then allowed to send/receive messages to/from
all nodes which have established communication channels with $u$ in the
current time step. An important objective one might ask for is to
determine the number of steps and message transmissions needed in this
model to spread a message to all nodes of the graph. We know that
address-oblivious algorithms (to which the random phone call model
belongs) require $Omega(n log n/log d)$ transmissions, if a message
is intended to be spread in $O(log n)$ steps to all nodes of a
$d$-regular random graph of size $n$. In this paper we show that if we
allow every node to choose {em four distinct neighbours} instead of
one, or to avoid in each step the neighbours chosen in the {em most
recent three steps}, then the average number of message transmissions
produced by an arbitrary node decreases exponentially. The algorithms
presented in this paper can efficiently handle limited communication
failures, only require rough estimates of the number of nodes, and are
robust against limited changes in the size of the network.
Joint work with Petra Berenbrink and Tom Friedetzky
|
| | Plus d'infos |
|
| 2007-06-26 | Data management in networks |
14:00-15:00 Salle 075 |
The area of data management (DM) concentrates on storing shared objects in the network, so that arbitrary sequences of accesses coming from network nodes can be served efficiently. In order to achieve this goal, a DM algorithm has to migrate/replicate/delete copies, so that the nodes can find them "nearby" in the network.
It is a widely explored problem, with many variants. In my talk I will present two simple extensions to DM framework:
* k-resource, which tries to model popularity of shared items, and
* a dynamic model which tries to capture network mobility / network dynamics.
---------
No prior knowledge of data management is assumed, general knowledge of online algorithms is useful.
Relevant papers can be found on the page http://www.ii.uni.wroc.pl/~mbi/publications.html |
| | Plus d'infos |
|
| 2007-06-18 | Dating service - a tool to cope with heterogeneity in distributed systems |
14:00-15:00 Salle 178 |
We propose a simple scheme to organize resource allocation in a distributed system in which nodes submit various demands and supplies for some resource. In each round our system connects demand-supply pairs (creates dates) in a distributed and random fashion and we prove that even a distributed system (for example based on a Distributed Hash Table) produces the number of dates within a constant factor from a centralized one. We apply our scheme to two basic problems. In both nodes submit their incoming and outgoing bandwidths and we use our dating service to organize communication. In the first case we show how to do rumor spreading in a heterogenous network and in the second we show how to construct a random multigraph in polylogarithmic time.
(joint work with Olivier Beaumont, Philippe Duchon, Robert Elsaesser, Ralf Klasing, Hejer Rejeb) |
| | Plus d'infos |
|
| 2007-06-11 | Schéma d'adjacence pour les graphes planaires |
14:00-15:00 Salle 178 |
Un schéma d'adjacence d'un graphe est un codage du graphe distribué sur ses sommets. Le principe est d'associer à chaque sommet du graphe de l'information sous la forme d'une étiquette binaire de façon à ce que l'on puisse déterminer l'adjacence entre deux sommets en examinant seulement leurs étiquettes. Je vous présenterais un tel schéma pour les graphes planaires de n sommets avec des étiquettes de (2+o(1))log n bits. L'idée du schéma est d'utiliser un nouveau schéma avec de étiquettes de (1+o(1))log n bits pour les planaires extérieurs et la décomposition des graphes planaires en deux graphes planaires extérieurs. De la méme manière, on étend ce résultat aux graphes excluant un mineur fixé en utilisant un nouveau schéma pour les graphes d'arboricité borné. |
| | Plus d'infos |
|
| 2007-05-02 | Preuve automatique par récurrence sur des structures de données complexes |
11:00-12:00 Salle 075 |
Nous proposons avec Adel Bouhoula une nouvelle approche pour l'automatisation de la récurrence sur des structures de données complexes (telles que listes ordonnées, arbres, powerlists...) spécifiées é l'aide d'équations avec conditions et contraintes. Notre procédure est basée sur l'utilisation d'une grammaires d'arbres à contraintes qui décrit exactement le modèle initial de la spécification donnée. Cette grammaire sert à la fois de schéma de récurrence, pour la génération de sous-buts, et pour des vérifications de cohérence durant les étapes de récurrence.
La procédure proposée est montrée correcte et réfutationellement complète même en présence d'axiomes contraints entre termes constructeurs, et fournit des preuves très naturelles sur un certains nombre d'exemples.
|
| | Plus d'infos |
|
| 2007-04-23 | Marches alétoires en algorithmique distribuée, un paradigme de conception de solutions algorithmiques pour les environnements dynamiques. |
14:00-15:00 Salle 178 |
La conception de solutions algorithmiques tolérantes aux pannes pour des systèmes dynamiques est rendue difficile par le caractère imprévisible des reconfigurations topologiques. Nous avons donc proposé dans nos travaux de concevoir des algorithmes distribués fondés sur l'utilisation de marches alétoires. Une marche alétoire peut se voir en algorithmique distribuée comme le déplacement alétoire d'un message à travers le réseau. Nos travaux se sont d'abord orientés vers les performances qu'offrent les algorithmes fondés sur des marches alétoires. Nous nous sommes ensuite intéressés à la conception d'un protocole auto-stabilisant de circulation de jeton. Ce protocole peut être utilisé pour mener à bien de nombreuses tâches telles l'allocation de ressources, l'élection, ou encore la construction de structures de contrôle. Nous avons ensuite dérivé cette circulation de jeton pour la découverte de ressources dans le cadre des grilles de calcul volatiles et pour l'allocation de ressources dans les réseaux ad-hoc.
----
Pour amples informations cliquez ici :
http://www.labri.fr/perso/hibaoui/GT-Algo-Dist/actualites.htm
|
| | Plus d'infos |
|
| 2007-04-02 | Distributed Calculations by Random Mobile Agents. |
14:00-15:00 Salle 178 |
We describe a distributed algorithm for computing spanning trees in
dynamic networks by using mobile agents. Each agent uses a random walk
to move in the network and to construct a spanning subtree for the
nodes visited for the first time. Spanning subtrees are merged when
agents enter in an already discovered area of the network. In this
case, we clone the agent having higher color to capture and to annex
the adjacent subtree. We discuss in this paper this operation of
agent cloning and show that it is useful to construct an efficient
distributed algorithm for computing a spanning tree. The correction
and the termination detection are also investigated.
In the second part, we also investigate the following problem: k
mobile agents are placed in a network. The agents initially move in
the network using random walks. When the agents meet in a node of the
underlying graph,they merge in a single agent. The parameter of interest
is the exected time for all the agents to merge in a single agent. We
obtain efficient results for particular classes of graphs; such as star
graphs, complete graphs and hypercube when two or more agents meet in
a network.
----
Pour amples informations cliquez ici :
http://www.labri.fr/perso/hibaoui/GT-Algo-Dist/actualites.htm
|
| | Plus d'infos |
|
| 2007-03-26 | Fast Periodic Graph Exploration with Constant Memory. |
14:00-15:00 salle 178 |
The talk considers the problem of periodic exploration of all nodes in
undirected anonymous graphs by using a finite state automaton (or robot).
The nodes in the graph are neither labelled nor colored. However, while
visiting a node v the robot can distinguish between edges incident
to it. The edges are ordered and labelled by consecutive integers
1,...,d(v) called port numbers, where d(v) is the degree of v.
Periodic graph exploration requires that the automaton has to visit
every node infinitely many times in a periodic manner.
In this work, we are interested in minimisation of the length of
the exploration period. In other words, we want to minimise the
maximum number of edge traversals performed by the robot between two
consecutive visits of a generic node, in the same state and entering
the node by the same port.
The talk presents an efficient deterministic algorithm arranging the
port numbers, and a robot equipped with a constant number
of bits able to complete the traversal period in at most 3.75n-2 steps
hence disproving a previous conjecture by which 4n-O(1) steps are
required.
|
| | Plus d'infos |
|
| 2007-03-19 | The Power of Memory in Randomized Broadcasting. |
14:00-15:00 Salle 178 |
In this talk we analyze the runtime and number of message transmissions
generated by simple randomized broadcasting algorithms in random-like
networks, and show that an apparently minor change in the ability of the
nodes implies an almost exponential decrease in the average communication
overhead produced by an arbitrary node.
In a recent paper, we showed that in a random graph $G_{n,p}$ with $p >
log^2 n/n$ any address oblivious broadcasting algorithm requires
$Omega(log n)$ time steps and produces $Omega(n (log log n + log n /
log (pn)))$ message transmissions, w.h.p. In this talk we show that if
the nodes are provided with a little memory, i.e., they are able to
remember the addresses of the nodes chosen in the most recent three steps,
then the communication overhead decreases to $O(n log log n), with high
probability, for any $p > log^2 n/n$. To achieve this result, we analyze
the structure of random graphs, and state a ``power of two choices'' type
theorem for randomized broadcasting.
The algorithms presented in this paper can efficiently handle restricted
communication failures, only require rough estimates of the number of
nodes, and are robust against slight changes in the size of the network.
In addition, our methods and results can be extended to the generalized
random graph model of Chung and Lu. |
| | Plus d'infos |
|
| 2007-03-12 | Mobile Agent Algorithms versus Message Passing Algorithms. |
14:00-15:00 Salle 178 |
In this work, we are interested in the computational power of a
mobile agent system and, more particularly, in the comparison with a
message passing system. First we give formal definitions. Then we
explain how a mobile agent algorithm can be simulated by a message
passing algorithm. We also prove that any message passing algorithm
can be implemented by a mobile agent algorithm.
As a consequence of this result, known characterisations of solvable
tasks by message passing algorithms can be translated into
characterisations of solvable tasks by mobile agent algorithms.
We illustrate this result with the election problem and the rendezvous
problem.
(Joint work with Jérémie Chalopin, Emmanuel Godard and Rodrigue Ossamy
presented at OPODIS'06).
|
| | Plus d'infos |
|
| 2007-03-05 | Searching for black-hole faults in a network using multiple agents. |
14:00-15:00 Salle 178 |
We consider a fixed communication network where (software) agents can move freely from node to node along the edges. A "black hole" is a faulty or malicious node in the network such that if an agent enters this node, then it immediately "dies". We are interested in designing an efficient communication algorithm for the agents to identify all black holes. We assume that we have k agents starting from the same node s and knowing the topology of the whole network. The agents move through the network in synchronous steps and can communicate only when they meet in a node. At the end of the exploration of the network, at least one agent must survive and must know the exact locations of the black holes. If the network has n nodes and b black holes, then any exploration algorithm needs $Omega(n/k + D_b)$ steps in the worst-case, where $D_b$ is the worst case diameter of the network with at most b nodes deleted. We give a general algorithm which completes exploration in $O((n/k)log n/loglog n + b D_b)$ steps for arbitrary networks, if b <= k/2. In the case when b <= k/2, $bD_b=O(sqrt{n})$ and $k = O(sqrt{n})$, we give a refined algorithm which completes exploration in asymptotically optimal O(n/k) steps.
(joint work with Colin Cooper and Tomasz Radzik)
|
| | Plus d'infos |
|
| 2007-02-12 | Distributed implementation of greedy graph coloring algorithms |
14:00-15:00 Salle 178 |
The talk concerns distributed graph coloring algorithms, which determine a coloring of the system graph having analogous properties to those obtained by well known sequential heuristics. Complexity analysis is performed in the Linial model, for a system of n nodes and maximum degree Delta. For the largest-first (LF) approach, a simple randomized distributed algorithm will color the graph in an expected time of O(Delta log n log Delta) rounds, but any distributed LF-coloring algorithm requires at least Omega(Delta) rounds. The complexity of distributed implementation is also considereed for some other sequential graph coloring approaches, such as smallest-last (SL), dynamic-saturation (SLF/DSatur), or simple greedy (S). |
| | Plus d'infos |
|
| 2007-01-08 | Complexité en espace de l'exploration de graphes |
14:00-15:00 Salle 178 |
Le problème de l'exploration de graphes trouve ses motivations en informatique fondamentale, notamment en logique et en théorie de la complexité. Il possède également de nombreuses applications en robotique. Quel que soit le cadre, la quantité de mémoire utilisée par l'entité mobile (robot, automate fini, etc.) effectuant l'exploration est un des paramètres importants à considérer. Dans cet exposé, je présenterai quelques résultats concernant la complexité en espace de l'exploration de graphes.
|
| | Plus d'infos |
|
| 2006-12-06 | Distributed Coordination Algorithms for Mobile Robot Swarms: New Directions and Challenges. |
14:00-15:00 Salle 076 |
The talk will concern systems of multiple autonomous mobile robots (often referred to as robot swarms). Recently there have been a number of efforts to study issues related to coordination and control algorithms for such systems from the point of view of distributed computing. The talk will review the literature in this area and discuss open problems and future research directions.
|
| | Plus d'infos |
|
| 2006-11-27 | Bornes inférieures pour le routage |
14:00-15:00 Salle 178 |
Après un tour d'horizon sur le routage compact à propos du compromis entre la taille des tables de routage et le facteur d'étirement, je présenterai un résultat d'impossibilité (ou d'incompressibilité). Je détaillerai une technique qui permet d'établir ce genre de résultat pour lesquels la difficulté principale est de formaliser en calcul distribué des arguments très intuitifs du type : "si je connais pas telle information, alors je me trompe et ne peux résoudre mon problème de départ".
Je vous rappelle que toutes les infos du groupe de travail sont disponibles sur
http://www.labri.fr/perso/hibaoui/GT-Algo-Dist/index.html |
| | Plus d'infos |
|
| 2006-11-20 | |
14:00-15:00 Salle 178 |
Depuis quelques années, les recherches sur la modélisation des "réseaux réels" (réseaux sociaux, graphe du Web...) se multiplient, et de nombreux modèles ont été proposés pour rendre compte de propriétés observées dans ces réseaux. Certains se focalisent sur les propriétés structurelles (répartition des degrés, densité locale, faible diamètre), d'autres sur des propriétés plus algorithmique (non seulement faible diamètre, mais surtout existence d'algorithmes décentralisés permettant de trouver des chemins courts entre sommets arbitraires).
Dans certains de ces modèles (Barabasi et Albert, Cooper et Frieze), les sommets arrivent un par un et sont alors reliés aux précédents avec une loi de probabilité qui favorise les sommets ayant déjà un haut degré ("attachement préférentiel"); il a été démontré que ce comportement donne naissance à des graphes "sans échelle" (scale-free), dans lesquels les degrés se répartissent selon une loi de puissance (la proportion de sommets de degré au moins k est en gros proportionnelle à une puissance négative de k), propriété fréquemment observée dans les réseaux que l'on souhaite modéliser. Le diamètre de tels graphes est également faible (logarithmique).
Nous nous focalisons, sur ces modèles, sur la navigabilité, pour démontrer un résultat négatif: bien que le diamètre soit faible, aucun algorithme décentralisé, se basant uniquement sur des connaissances locales, ne peut espérer trouver de chemin entre deux sommets typiques en explorant moins d'un nombre polynomial de sommets. La preuve utilise une idée intuitivement naturelle, mais un peu technique à formaliser, qui veut que, dans ces graphes, de nombreux sommets soient très difficiles à distinguer, ce qui rend virtuellement impossible de choisir le "bon" dans une recherche de chemin.
Travail en commun avec Nicole Eggemann et Nicolas Hanusse.
Je vous rappelle que toutes les infos du groupe de travail sont disponibles sur
http://www.labri.fr/perso/hibaoui/GT-Algo-Dist/index.html
|
| | Plus d'infos |
|
| 2006-10-23 | Dynamic Load Balancing in Distributed Hash Tables. |
14:00-15:00 Salle 178 |
I consider Distributed Hash Tables (DHTs) based on a [0,1) ring. The
whole ring is partitioned among the peers so, that each peer is responsible for an interval and that each point in [0,1) is attributed to a peer. When a piece of information is to be published or found, a global hash function is computed on its name, yielding a point in [0,1). The peer responsible for the interval containing this point is also responsible for the considered piece of information. Network construction and routing, based on a hypercube and/or a de Bruijn graph, enable to find the sought-after point in logarithmic time (in the number of present peers).
I present distributed algorithms which assure that the intervals, for which peers are responsible, are of equal lengths, up to constant factors. The main difficulty in this problem is that the dynamics of the system are unpredictable. Therefore, I present two schemes. The first one is able to balance any system in logarithmic time but has unbounded communication cost. The second one has communication cost only by a logarithmic factor larger than any scheme keeping the system connected, but balances the system with some delay.
Je vous rappelle que toutes les infos du groupe de travail sont disponibles sur
http://www.labri.fr/perso/hibaoui/GT-Algo-Dist/index.html
à toute! |
| | Plus d'infos |
|
| 2006-10-09 | Détection de la terminaison dans les systèmes distribués asynchrones à base de messages. |
14:00-15:00 Salle 178 |
Non fourni |
| | Plus d'infos |
|
| 2006-06-26 | Maintenance d'arbres recouvrants dans le modèle des calculs locaux |
14:00-15:00 Salle 076 |
In this work we deal with the problem of spanning tree maintenance in the presence of crash failures in a distributed environment. First, we study 2-connected graphs. We present a protocol to maintain a spanning tree of such graphs in the presence of one failure. The time requirement of such an algorithm is bounded by c1 * Delta * N + c2 and the space complexity requirement is bounded by c1 * Delta + c2 for some constants c1,c2, where Delta is the degree and N the number of nodes of the graph to be examined. Second, we extend such a protcol to deal with any graph topology using a pre-processing task. The result of such a task is used as an initial configuration for the maintenance protocol. This protocol is a small generalization of the first one to maintain a forest of spanning trees for the not 2-connected graphs. |
| | Plus d'infos |
|
| 2006-06-19 | Test distribué de la 2-connexité de graphe dans le modèle des calculs locaux |
14:00-15:00 Salle 076 |
The vertex connectivity of a graph is the smallest number of vertices whose deletion separates the graph or makes it trivial. This work is devoted to the problem of vertex connectivity of graphs in a distributed environment. Using a spanning tree of the considered graph, we present a protocol to test whether a given graph is 2-connected using only local computations. The time requirement of such an algorithm is bounded by c1 * Delta * N2 + c2 and the space complexity requirement is bounded by c1 * Delta + c2 for some constants c1 and c2, where Delta is the degree and N the number of nodes of the graph to be examined. Moreover, we investigate some applications that can use our protocol as a preprocessing task for initial configurations. |
| | Plus d'infos |
|
| 2006-05-22 | Random graph models of large networks |
14:00-15:00 76 |
We consider random graph models for constructing networks as discrete processes. In the first type of model we have some knowledge of the network structure, such as vertex degree at any step, and construct networks exhibiting power law properties. In the second the network is produced in a distributed manner with little knowledge of overall structure. Such constructions may be useful in P2P networks. |
| | Plus d'infos |
|
| 2006-05-15 | Network algorithms with an oracle |
14:00-15:00 Salle 076 |
We study the problem of the amount of information about a network that must be known in order to efficiently accomplish an exploration or communication task. While previous results about exploration and communication in networks assumed particular partial information, such as the knowledge of the neighborhood, the knowledge of the network topology within some radius, or a partial map of the network, our approach is quantitative: we investigate the minimum total number of bits of information (minimum oracle size) that has to be known in order to perform efficient exploration or communication.
We present the approach by oracles on the examples of two problems. The first is exploration, a fundamental problem in mobile computing: a mobile agent has to traverse all edges of a network. The second is information dissemination, one of the basic communication primitives: a message held in one node of the network, called the source, has to be transmitted to all other nodes. If no restrictions are imposed, information dissemination is called broadcast. If only nodes that already got the source message can transmit, it is called wakeup.
For the exploration task we establish the minimum oracle size permitting exploration with competitive ratio below 2. For communication we show that the minimum oracle size to perform wakeup with a linear number of messages in an $n$-node network, is $Theta (n log n)$, while the broadcast with a linear number of messages can be achieved with an oracle of size $O(n)$. Thus an efficient wakeup requires strictly more information about the network than an efficient broadcast.
This is joint work with Pierre Fraigniaud and David Ilcinkas. |
| | Plus d'infos |
|
| 2006-04-24 | |
14:00-15:00 Salle 076 |
Les automates cellulaires sont une classe de systèmes dynamiques discrets qui sont fréquemment utilisés pour modéliser des systèmes complexes massivment parallèles. Dans leur acception classique, les automates cellulaires sont simulés sur une grille régulière et avec un synchronisme parfait des transitions. Néanmoins, ces deux hypothèses ont peu de chances d'êtres valides pour de nombreux systèmes. On cherche donc à déterminer dans quelle mesure les automates cellulaires peuvent garder leur comportement constant lorsqu'ils sont soumis à de petites pertubrations de synchronisme ou de topologie.
Mon travail s'articule en trois parties : j'expose tout d'abord comment on peut aborder
ce problème par des techniques de simulation numérique. Ensuite, je developpe des
outils probabilistes (couplages, chaînes de Markov et martingales) qui permettent de
traiter le problème dans certains cas particuliers. Dans un troisème temps, je me
concentre sur les études "à la physicienne" dans laquelle je cherche à comprendre des
phénomènes particuliers. Enfin, je conclus sur l'intérêt de ce travail dans le cadre
plus général de la modélisation.
http://www.labri.fr/perso/hibaoui/GT-Algo-Dist/actualites.htm |
| | Plus d'infos |
|
| 2006-04-10 | "Autour des grands réseaux d'interactions." |
14:00-15:00 Salle 076 |
Les grands réseaux d'interactions, nom générique pour les graphes rencontrés dans des contextes réels, sont depuis quelques années au centre de nombreuses recherches de par la variété des contextes et des disciplines dans lesquels ils apparaissent. Je ferai au cours de cet exposé un point sur quelques problématiques liées à cette thématique : métrologie de graphes et application au cas de l'Internet, modélisation des réseaux et des phénomènes à l'oeuvre sur ces réseaux (diffusion et robustesse). Je présenterai aussi quelques cas particuliers, notamment les réseaux pair-à-pair qui sont parmi les réseaux les plus étudiés actuellement.
|
| | Plus d'infos |
|
| 2006-04-03 | "Le problème de synthèse distribuée." |
14:00-15:00 Salle 076 |
Le problème de synthèse consiste, étant donnés un système ouvert et une propriété de ce système, à calculer un contrôleur pouvant inhiber certaines actions du système et qui, synchronisé avec lui, permet d'assurer la propriété donnée.
Cet exposé présente les difficultés rencontrées pour ce problème dans le cadre distribué, où la plupart des résultats connus mènent à l'indécidabilité, tant en sémantique synchrone qu'asynchrone. On montrera comment affaiblir les exigences sur les contrôleurs, ou sur l'entrée du problème, pour obtenir des résultats de positifs.
Travail commun avec Paul Gastin, Benjamin Lerman, Nathalie Sznajder.
|
| | Plus d'infos |
|
| 2006-03-20 | "Some Ideas about Modeling with Distributed Algorithms" |
14:00-15:00 Salle 076 |
"This will be a rather informal talk in which I want
to expose some rather simple ideas to public criticism
and discussion; yet I do not have any conclusive results. Two hopefully interesting scenarios will be considered:
(A) Modelling of Drifting Nodes in a Mobile Communication
Network, and (B) Modelling of Digital Image Processing by
means of Cellular Automata. Both topics belong to the wider field of Distributed
Graph Relabeling studied at LABRI by Mohamed Mosbah,
Yves Metivier and their colleagues.
The presentation language is, unfortunately, English.
Everybody is cordially invited."
http://www.labri.fr/perso/hibaoui/GT-Algo-Dist/index.html |
| | Plus d'infos |
|
| 2006-03-13 | "Observer la stabilisation" |
14:00-15:00 Salle 076 |
Les systèmes auto-stabilisants sont des systèmes répartis naturellement tolérants aux
défaillances. Un système auto-stabilisant est un système qui, quelque soit son
initialisation et donc après une défaillance, finit par se comporter correctement. Un inconvénient souvent cité de l'auto-stabilisation est que la stabilisation ne peut
être détectée par le protocole lui-même. En effet, si la détection se fait par un prédicat sur un ensemble de variables, la corruption de ces variables peut donner une
fausse indication. Par contre, rien n'empêche un observateur extérieur de procéder à
cette détection. Dans un article de PODC 98, Lin et Simon proposent un observateur réparti et montrent à l'aide d'exemples que la détection peut être plus courte que la
stabilisation. L'observateur réparti utilise, en chaque site, une mémoire supposée
incorruptible. Cette hypothèse, si elle est valide pour des réseaux locaux de petite
taille, ne passe absolument pas à l'échelle.
Nous proposons un nouveau modèle, fondé sur des observateurs locaux, utilisant
beaucoup moins de ressources. En particulier, un tel observateur est placé sur un seul
site du système et permet de conclure, sous certaines conditions, à la stabilisation.
Dans ce modèle, nous prouvons qu'il est possible de construire un observateur déterministe pour n'importe quelle tâche spécifiée sous un démon synchrone et pour une
topologie distinguée, dès lors que cette tâche admet une solution auto-stabilisante.
Nous introduisons également la notion d'observateur probabiliste et nous prouvons que
de tels observateurs permettent d'observer une plus grande classe de systèmes
auto-stabilisants que les observateurs déterministes.
|
| | Plus d'infos |
|
| 2006-03-06 | |
14:00-15:00 Salle |
Par Cyril Gavoille
Je donnerai un théorème de décomposition des graphes excluant
un mineur fixé (par exemple K_5 ou K_{3,3}), permettant de résoudre un
problème de routage dans une classe de graphes ainsi bien plus grande
que celle des graphes planaires.
|
| | Plus d'infos |
|
| 2006-02-06 | |
14:00-15:00 Salle 076 |
Un système distribué est souvent modélisé par un graphe où les noeuds
représentent les machines (unité de calculs) et les arêtes
ou arcs représentent les liens de communications. L'un des paradigmes
des calculs distribués est la tolérance aux pannes. Différents modèles
autour des pannes et leurs classifications sont données dans la
littérature. Dans cet exposé on va considérer des pannes transitoires,
dans un premier temps pouvant affecté l'état des machines, ensuite
l'état des liens de communication et à la fin le code (programme) des
machines.
Les algorithmes distribués sont codés dans les modèles des calculs
locaux et celui à passage de messages.
Une idée de plan serait:
- Tolérance aux pannes dans les calculs distribués - La stabilisation
globale
- La stabilisation locale
- La stabilisation instantanée
- Stabilisation des liens de communication
- Stabilisation du code |
| | Plus d'infos |
|
| 2006-01-30 | Election et nommage dans les réseaux anonymes. |
14:00-15:00 Salle 076 |
Dans ce travail, on s'intéresse aux problèmes d'élection et de nommage
dans un réseau anonyme. Le modèle considéré est un modèle où les
processus peuvent communiquer en émettant et en recevant des
messages. Le but d'un algorithme de nommage est d'attribuer de manière
distribuée des identifiants uniques à tous les processus du réseau. Le
but d'un algorithme d'élection est de distinguer un des sommets du
réseau.
Je commencerai par expliquer les résultats de Yamashita et Kameda dans
le modèle considéré : ils sont les premiers à avoir caractérisé quels
étaient les réseaux où ces problèmes pouvaient être résolus.
Je présenterai ensuite une adaptation de l'algorithme de Mazurkiewicz
dans ce modèle et j'expliquerai les différences entre cette approche
et celle de Yamashita et Kameda. En particulier, on verra quel est le
gain obtenu au point de vue de la complexité.
Pour finir, si on a le temps, on présentera une implémentation de
l'algorithme dans ViSiDiA. |
| | Plus d'infos |
|
| 2006-01-23 | |
14:00-15:00 Salle 178 |
(Résumé non fourni)
|
| | Plus d'infos |
|
| 2006-01-09 | Construction d'algorithmes distribués à l'aide de visidia. |
14:00-15:00 Salle 076 |
L'exposé sera organisé en deux parties. Dans la première partie, un
apercu sur les méthodes logiques de construction d'algorithmes de
graphes sera donné. La deuxième partie de l'exposé sera consacrée au
projet visidia (présentation de l'environnement de codage d'algorithmes
distribués, et du langage Lidia). |
| | Plus d'infos |
|
| 2005-12-12 | Algorithmique distribuée et graphes petit-mondes |
14:00-15:00 Salle 076 |
Un réseau est navigable si un algorithme de routage glouton peut être
utilisé pour router dans le réseau. Il se peut que le diamêtre d'un tel
réseau soit trés grand impliquant un grand nombre de sauts dans le
routage. Nous nous intéressons à une opération, la petite-mondisation,
qui consiste à rajouter un nouveau lien par sommet. Le réseau augmenté,
appelé petit-monde, assure que le routage glouton pour toute destination
se fait en un nombre polylogarithmique de sauts.
|
| | Plus d'infos |
|
| 2005-11-28 | Un modèle formel pour les agents mobiles |
14:00-15:00 Salle 076 |
Un modèle formel pour les agents mobiles
mots clés: agents mobiles, coopération, langage Z.
|
| | Plus d'infos |
|
| 2005-11-07 | "Bringing internet into villages using wireless communication." (Hardness and approximation of Gathering in static radio networks.) |
14:00-15:00 Salle 076 |
In this talk, we address the problem of gathering information in a
central node of a radio network, where interference constraints are
present. We take into account the fact that, when a node transmits,
it produces interference in an area bigger than the area in which
its message can actually be received. The network is modeled by a
graph; a node is able to transmit one unit of information to the set
of vertices at distance at most $dt$ in the graph, but when doing
so it generates interference that does not allow nodes at distance
up to $di$ ($di ge dt$) to listen to other transmissions. We
give a general lower bound on the number of rounds required to
gather on any graph, and present an algorithm working on any graph,
with an approximation factor of 4. We also show that the problem of
finding an optimal strategy for gathering (one that uses a minimum
number of time-steps) does not admit a Fully Polynomial Time
Approximation Scheme if $di > dt$, unless extsc{P=NP}, and in
the case $di=dt$ the problem is extsc{NP-hard}.
|
| | Plus d'infos |
|
| 2005-10-17 | Structures de données distribuées: un survol |
14:00-15:00 Salle 076 |
Il s'agit de donner un apercu général sur le domaine des structures de données dans le cadre du calcul distribué.
En insistant sur les motivations, un large panel de résultats très récents sera présenté.
Quelques mots-clés: calcul de distances, plus proche ancêtre commun, représentation implicte.
|
| | Plus d'infos |
|
| 2005-10-03 | Mise en place du groupe de travail + Exposé sur |
14:00-15:00 Salle 076 |
Cette première séance sera consacrée à la mise en place du groupe de travail, et à un premier exposé de type petite école sur "les calculs locaux" qui sera donné par Y. Métivier. |
| | Plus d'infos |
|
Liste des événements répétitifs du groupe Algorithmique Distribuée
RetourRetour à l'index
| |