Author: "Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest" - Searchworks@Jio Institute Digital Library Search Results

Your search keyword '"Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest"' showing total 400 results

Start Over Author "Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest"

400 results on '"Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest"'

1. Network verification via routing table queries

Author: Guido Proietti, Evangelos Bampas, Guido Drovandi, Luciano Gualà, Davide Bilò, Ralf Klasing, Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), University of Sassari, Consiglio Nazionale delle Ricerche [Roma] (CNR), Department of Physics, University of Rome Tor Vergata, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Dipartimento di Informatica [Italy] (DI), Università degli Studi dell'Aquila (UNIVAQ), Istituto di Analisi dei Sistemi ed Informatica 'Antonio Ruberti' (IASI), Modélisation, Information et Systèmes - UR UPJV 4290 (MIS), Université de Picardie Jules Verne (UPJV), Dipartimento di Ingegneria e Scienze dell'Informazione e Matematica [L'Aquila] (DISIM), Istituto di Analisi dei Sistemi ed Informatica 'Antonio Ruberti' [Roma] (IASI), ANR-11-BS02-0014,DISPLEXITY,Calculabilité et complexité en distribué(2011), Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Università degli Studi di Sassari = University of Sassari [Sassari] (UNISS), National Research Council of Italy | Consiglio Nazionale delle Ricerche (CNR), Università degli Studi di Roma Tor Vergata [Roma], Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Università degli Studi dell'Aquila = University of L'Aquila (UNIVAQ), and Department of Information Engineering, Computer Science and Mathematics = Dipartimento di Ingegneria e Scienze dell'Informazione e Matematica [L'Aquila] (DISIM)
Subjects: Theoretical computer science, Optimization problem, Graph/network topology, General Computer Science, Computational complexity theory, Computer Networks and Communications, Computer science, Routing table, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Vertex cover, 0102 computer and information sciences, 02 engineering and technology, Network topology, 01 natural sciences, Graph verification, Theoretical Computer Science, 0202 electrical engineering, electronic engineering, information engineering, ComputingMilieux_MISCELLANEOUS, Computer Science::Databases, Settore INF/01 - Informatica, Applied Mathematics, Approximation algorithm, 020206 networking & telecommunications, Approximation algorithms, Computational complexity, Computational Theory and Mathematics, 010201 computation theory & mathematics, Network verification, Shortest path problem, Graph (abstract data type), [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
Abstract: International audience; 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 Ω(loglogn) queries to be verified. Then, we prove that there is no o(logn)-approximation algorithm for the problem, unless \sf P=\sf NP , even for networks of diameter 2. On the positive side, we provide an O(logn)-approximation algorithm to verify a network of diameter 2, and we give exact polynomial-time algorithms for paths, trees, and cycles of even length.
Published: 2015

2. Collision-Free Network Exploration

Author: Dariusz Dereniowski, Dominik Pajak, Jurek Czyzowicz, Ralf Klasing, Leszek Gasieniec, Adrian Kosowski, Département d'Informatique et d'Ingénierie (DII), Université du Québec en Outaouais (UQO), Department of Algorithms and Systems Modelling [ETI GUT] (Gdansk University of Technology), Faculty of Electronics, Telecommunications and Informatics [GUT Gdańsk] (ETI), Gdańsk University of Technology (GUT)-Gdańsk University of Technology (GUT), Department of Computer Science [Liverpool], University of Liverpool, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Networks, Graphs and Algorithms (GANG), Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Department of Algorithms and System Modeling [Gdansk], Gdańsk University of Technology, Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université Sciences et Technologies - Bordeaux 1-Université Bordeaux Segalen - Bordeaux 2, Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Sciences et Technologies - Bordeaux 1, Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), ANR-11-BS02-0014,DISPLEXITY,Calculabilité et complexité en distribué(2011), Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), and Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest
Subjects: General Computer Science, Computer Networks and Communications, Computer science, Distributed computing, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Topology (electrical circuits), 0102 computer and information sciences, 01 natural sciences, Theoretical Computer Science, Set (abstract data type), Combinatorics, Collision free, Connection (algebraic framework), 0101 mathematics, ComputingMilieux_MISCELLANEOUS, Mathematics, Discrete mathematics, Spanning tree, Degree (graph theory), Applied Mathematics, Node (networking), 010102 general mathematics, Binary logarithm, Tree (graph theory), Network exploration, Computer Science::Multiagent Systems, Computational Theory and Mathematics, 010201 computation theory & mathematics, Tree network, Mobile agent, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
Abstract: International audience; A set of mobile agents is placed at different nodes of a $n$-node network. The agents synchronously move along the network edges in a {\em collision-free} way, i.e., in no round may two agents occupy the same node. In each round, an agent may choose to stay at its currently occupied node or to move to one of its neighbors. An agent has no knowledge of the number and initial positions of other agents. We are looking for the shortest possible time required to complete the collision-free {\em network exploration}, i.e., to reach a configuration in which each agent is guaranteed to have visited all network nodes and has returned to its starting location. We first consider the scenario when each mobile agent knows the map of the network, as well as its own initial position. We establish a connection between the number of rounds required for collision-free exploration and the degree of the minimum-degree spanning tree of the graph. We provide tight (up to a constant factor) lower and upper bounds on the collision-free exploration time in general graphs, and the exact value of this parameter for trees. For our second scenario, in which the network is unknown to the agents, we propose collision-free exploration strategies running in $O(n^2)$ rounds for tree networks and in $O(n^5\log n)$ rounds for general networks.
Published: 2017

3. Half-turn symmetric FPLs with rare couplings and tilings of hexagons

Author: Philippe Duchon, Jean-Christophe Aval, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), and Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest
Subjects: Coupling, General Computer Science, Substitution tiling, 010102 general mathematics, Plane partition, tilings of hexagons, 0102 computer and information sciences, Expression (computer science), 01 natural sciences, Bijective proof, Theoretical Computer Science, Combinatorics, Loop (topology), Fully packed loop configurations, 010201 computation theory & mathematics, alternating sign matrices, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], Turn (geometry), FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), 0101 mathematics, Symmetry (geometry), Mathematics
Abstract: 14 p.; International audience; In this work, we put to light a formula that relies the number of fully packed loop configurations (FPLs) associated to a given coupling pi to the number of half-turn symmetric FPLs (HTFPLs) of even size whose coupling is a punctured version of the coupling pi. When the coupling pi is the coupling with all arches parallel pi0 (the ''rarest'' one), this formula states the equality of the number of corresponding HTFPLs to the number of cyclically-symmetric plane partition of the same size. We provide a bijective proof of this fact. In the case of HTFPLs odd size, and although there is no similar expression, we study the number of HTFPLs whose coupling is a slit version of pi_0, and put to light new puzzling enumerative coincidence involving countings of tilings of hexagons and various symmetry classes of FPLs.
Published: 2013

4. Heterogeneous Resource Allocation under Degree Constraints

Author: Olivier Beaumont, H. Rejeb, Lionel Eyraud-Dubois, C. Thraves Caro, Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Laboratorio de Algoritmia Distribuida y Redes (LADyR), Universidad Rey Juan Carlos [Madrid] (URJC), ANR-05-MMSA-0006,ALPAGE,ALgorithmique des Plates-formes A Grande Echelle(2005), Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Department of telecommunication systems and computation, ANR-11-INFR-0013,SONGS,Simulation de systèmes de prochaine génération(2011), Eyraud-Dubois, Lionel, and Masse de données : Modélisation, Simulation, Applications - ALgorithmique des Plates-formes A Grande Echelle - - ALPAGE2005 - ANR-05-MMSA-0006 - MMSA - VALID
Subjects: Resource Augmentation, Computational complexity theory, Computer science, Distributed computing, Online Computation, Cloud computing, 02 engineering and technology, computer.software_genre, Scheduling (computing), Bin Packing, Server, [INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], 0202 electrical engineering, electronic engineering, information engineering, Resource management, Time complexity, business.industry, Bin packing problem, Approximation algorithm, 020206 networking & telecommunications, Cloud Computing, Approximation algorithms, Divisible Scheduling, Computational Theory and Mathematics, Hardware and Architecture, Virtual machine, Signal Processing, Resource allocation, 020201 artificial intelligence & image processing, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], business, Heuristics, computer
Abstract: International audience; In this paper, we consider the problem of assigning a set of clients with demands to a set of servers with capacities and degree constraints. The goal is to find an allocation such that the number of clients assigned to a server is smaller than the server's degree and their overall demand is smaller than the server's capacity, while maximizing the overall throughput. This problem has several natural applications in the context of independent tasks scheduling or virtual machines allocation. We consider both the \emph{offline} (when clients are known beforehand) and the \emph{online} (when clients can join and leave the system at any time) versions of the problem. We first show that the degree constraint on the maximal number of clients that a server can handle is realistic in many contexts. Then, our main contribution is to prove that even if it makes the allocation problem more difficult (NP-Complete), a very small additive resource augmentation on the servers degree is enough to find in polynomial time a solution that achieves at least the optimal throughput. After a set of theoretical results on the complexity of the offline and online versions of the problem, we propose several other greedy heuristics to solve the online problem and we compare the \emph{performance} (in terms of throughput) and the \emph{cost} (in terms of disconnections and reconnections) of all proposed algorithms through a set of extensive simulation results.
Published: 2013

5. Rendezvous of heterogeneous mobile agents in edge-weighted networks

Author: Ralf Klasing, Łukasz Kuszner, Dariusz Dereniowski, Adrian Kosowski, Department of Algorithms and Systems Modelling [ETI GUT] (Gdansk University of Technology), Faculty of Electronics, Telecommunications and Informatics [GUT Gdańsk] (ETI), Gdańsk University of Technology (GUT)-Gdańsk University of Technology (GUT), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Networks, Graphs and Algorithms (GANG), Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), ANR-11-BS02-0014,DISPLEXITY,Calculabilité et complexité en distribué(2011), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Sciences et Technologies - Bordeaux 1, Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, Klasing, Ralf, and BLANC - Calculabilité et complexité en distribué - - DISPLEXITY2011 - ANR-11-BS02-0014 - BLANC - VALID
Subjects: FOS: Computer and information sciences, Weight function, General Computer Science, Computer science, Distributed computing, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Theoretical Computer Science, Computer Science - Data Structures and Algorithms, 0202 electrical engineering, electronic engineering, information engineering, [INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Data Structures and Algorithms (cs.DS), Communication complexity, ComputingMilieux_MISCELLANEOUS, Discrete mathematics, Rendezvous, Graph, Computer Science::Multiagent Systems, Tree traversal, 010201 computation theory & mathematics, Distributed algorithm, [INFO.INFO-MA]Computer Science [cs]/Multiagent Systems [cs.MA], Graph (abstract data type), 020201 artificial intelligence & image processing, Mobile agent, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], mobile agents, Rendezvous problem, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract: We introduce a variant of the deterministic rendezvous problem for a pair of heterogeneous agents operating in an undirected graph, which differ in the time they require to traverse particular edges of the graph. Each agent knows the complete topology of the graph and the initial positions of both agents. The agent also knows its own traversal times for all of the edges of the graph, but is unaware of the corresponding traversal times for the other agent. The goal of the agents is to meet on an edge or a node of the graph. In this scenario, we study the time required by the agents to meet, compared to the meeting time $T_{\textup{OPT}}$ in the offline scenario in which the agents have complete knowledge about each others speed characteristics. When no additional assumptions are made, we show that rendezvous in our model can be achieved after time $O(n T_{\textup{OPT}})$ in a n-node graph, and that such time is essentially in some cases the best possible. However, we prove that the rendezvous time can be reduced to $\Theta (T_{\textup{OPT}})$ when the agents are allowed to exchange Θ(n) bits of information at the start of the rendezvous process. We then show that under some natural assumption about the traversal times of edges, the hardness of the heterogeneous rendezvous problem can be substantially decreased, both in terms of time required for rendezvous without communication, and the communication complexity of achieving rendezvous in time $\Theta (T_{\textup{OPT}})$.
Published: 2015

6. Deterministic Rendezvous of Asynchronous Bounded-Memory Agents in Polygonal Terrains

Author: Adrian Kosowski, Jurek Czyzowicz, Andrzej Pelc, Département d'Informatique et d'Ingénierie (DII), Université du Québec en Outaouais (UQO), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, and Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)
Subjects: Mathematical optimization, Finite-state machine, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Regular polygon, Rendezvous, Terrain, 0102 computer and information sciences, 01 natural sciences, Theoretical Computer Science, 010104 statistics & probability, Computational Theory and Mathematics, 010201 computation theory & mathematics, Bounded function, Polygon, Trajectory, 0101 mathematics, Rendezvous problem, Algorithm, ComputingMilieux_MISCELLANEOUS, Mathematics
Abstract: Two mobile agents, modeled as points starting at different locations of an unknown terrain, have to meet. The terrain is a polygon with polygonal holes. We consider two versions of this rendezvous problem: exact RV, when the points representing the agents have to coincide at some time, and ?-RV, when these points have to get at distance less than ? in the terrain. In any terrain, each agent chooses its trajectory, but the movements of the agent on this trajectory are controlled by an adversary that may, e.g., speed up or slow down the agent. Agents have bounded memory: their computational power is that of finite state machines. Our aim is to compare the feasibility of exact and of ?-RV when agents are anonymous vs. when they are labeled. We show classes of polygonal terrains which distinguish all the studied scenarios from the point of view of feasibility of rendezvous. The features which influence the feasibility of rendezvous include symmetries present in the terrains, boundedness of their diameter, and the number of vertices of polygons in the terrains.
Published: 2011

7. How many oblivious robots can explore a line

Author: Nicola Santoro, David Ilcinkas, Andrzej Pelc, Paola Flocchini, School of Information Technology and Engineering [Ottawa] (SITE), University of Ottawa [Ottawa], Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Département d'Informatique et d'Ingénierie (DII), Université du Québec en Outaouais (UQO), School of Computer Science [Ottawa], Carleton University, See paper for details., ANR-07-BLAN-0322,ALADDIN,Algorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks(2007), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), and Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest
Subjects: Theoretical computer science, Computer science, Distributed computing, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0211 other engineering and technologies, 0102 computer and information sciences, 02 engineering and technology, exploration, 01 natural sciences, Theoretical Computer Science, distributed computing, oblivious, mobile robots, Impossibility, asynchronous, 021103 operations research, Mobile robot, Computer Science Applications, 010201 computation theory & mathematics, Asynchronous communication, Signal Processing, Robot, line, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Line (text file), Information Systems
Abstract: International audience; We consider the problem of exploring an anonymous line by a team of k identical, oblivious, asynchronous deterministic mobile robots that can view the environment but cannot communicate. We completely characterize sizes of teams of robots capable of exploring a n-node line. For k= 5, or k=4 and n is odd. For all values of k for which exploration is possible, we give an exploration algorithm. For all others, we prove an impossibility result.
Published: 2011

8. Derandomizing random walks in undirected graphs using locally fair exploration strategies

Author: Ralf Klasing, Adrian Kosowski, Colin Cooper, David Ilcinkas, Department of Computer Science (DCS), King‘s College London, Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Combinatoire et Algorithmique, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), See paper for details., ANR-07-BLAN-0322,ALADDIN,Algorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks(2007), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Department of Algorithms and Systems Modelling [ETI GUT] (Gdansk University of Technology), Faculty of Electronics, Telecommunications and Informatics [GUT Gdańsk] (ETI), Gdańsk University of Technology (GUT)-Gdańsk University of Technology (GUT), ANR-05-MMSA-0006,ALPAGE,ALgorithmique des Plates-formes A Grande Echelle(2005), Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), and Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)
Subjects: Mathematical optimization, Computer Networks and Communications, Computer science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Comparability graph, Random walk, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, law.invention, Theoretical Computer Science, Combinatorics, Indifference graph, Graph exploration, law, Graph power, Line graph, Random regular graph, 0202 electrical engineering, electronic engineering, information engineering, Pancyclic graph, Mathematics, Discrete mathematics, Block graph, graph exploration : Propp machine, Directed graph, Feedback arc set, Computational Theory and Mathematics, 010201 computation theory & mathematics, Hardware and Architecture, Robbins' theorem, Graph (abstract data type), 020201 artificial intelligence & image processing, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], MathematicsofComputing_DISCRETEMATHEMATICS
Abstract: International audience; We consider the problem of exploring an anonymous undirected graph using an oblivious robot. The studied exploration strategies are designed so that the next edge in the robot's walk is chosen using only local information, and so that some local equity (fairness) criterion is satisfied for the adjacent undirected edges. Such strategies can be seen as an attempt to derandomize random walks, and are natural counterparts for undirected graphs of the rotor-router model for symmetric directed graphs. The first of the studied strategies, known as Oldest-First (OF), always chooses the neighboring edge for which the most time has elapsed since its last traversal. Unlike in the case of symmetric directed graphs, we show that such a strategy in some cases leads to exponential cover time. We then consider another strategy called Least-Used-First (LUF) which always uses adjacent edges which have been traversed the smallest number of times. We show that any Least-Used-First exploration covers a graph G=(V,E) of diameter diam within time O(diam|E|), and in the long run traverses all edges of G with the same frequency.
Published: 2011

9. Synchronous black hole search in directed graphs

Author: Cristina M. Pinotti, Adrian Kosowski, Alfredo Navarra, Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Dipartimento di Matematica e Informatica [Perugia] (DMI), Università degli Studi di Perugia (UNIPG), Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), and Università degli Studi di Perugia = University of Perugia (UNIPG)
Subjects: Synchronous scheduler, General Computer Science, Graph searching problem, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Upper and lower bounds, Graph algorithms, Mobile agents in graphs, Graph searching problem, Black hole search problem, Theoretical Computer Science, Computer Science::Robotics, Combinatorics, 0202 electrical engineering, electronic engineering, information engineering, Mobile agents in graphs, Black hole search problem, Graph algorithms, Communication complexity, Complement graph, Mathematics, Directed graph, Feedback arc set, 010201 computation theory & mathematics, Asynchronous communication, Distributed system, Graph (abstract data type), Robot, 020201 artificial intelligence & image processing, Computer Science(all)
Abstract: The paper considers a team of robots which has to explore a graph G, where some nodes can be harmful. Robots are initially located at the so-called home base node. The dangerous nodes are the so-called black hole nodes, and once a robot enters in one of them, it is destroyed. The goal is to find a strategy in order to explore G in such a way that minimum number of robots is wasted. The exploration ends if there is at least one surviving robot which knows all the edges leading to the black holes. As many variations of the problem have been considered so far, the solution and its measure heavily depend on the initial knowledge and the capabilities of the robots. In this paper, we assume that G is a directed graph, the robots are associated with unique identifiers, they know the number of nodes n of G (or at least an upper bound on n), and they know the number of edges @D leading to the black holes. Each node is associated with a whiteboard where robots can read and write information in a mutual exclusive way. A recently posed question [J. Czyzowicz, S. Dobrev, R. Kralovic, S. Miklik, D. Pardubska, Black hole search in directed graphs, in: Proc. of 16th International Colloquium on Structural Information and Communication Complexity, SIROCCO, LNCS, vol. 5869, 2009, pp. 182-194.] is whether some number of robots, expressed as a function of parameter @D only, is sufficient to detect black holes in directed graphs of arbitrarily large order n. We give a positive answer to this question for the synchronous case, i.e., when the robots share a common clock, showing that O(@D@?2^@D) robots are sufficient to solve the problem. This bound is nearly tight, since it is known that at least 2^@D robots are required for some instances. Quite surprisingly, we also show that unlike in the case of undirected graphs, for the directed version of the problem, synchronization can sometimes make a difference: for @D=2, in the synchronous case 4 robots are always sufficient, whereas in the asynchronous case at least 5 robots are sometimes required.
Published: 2011

10. Fast radio broadcasting with advice

Author: David Ilcinkas, Andrzej Pelc, Dariusz R. Kowalski, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Department of Computer Science [Liverpool], University of Liverpool, Département d'Informatique et d'Ingénierie (DII), Université du Québec en Outaouais (UQO), See paper for details., ANR-07-BLAN-0322,ALADDIN,Algorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks(2007), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, This work was done during the stay of David Ilcinkas at the Research Chair in Distributed Computing of the Université du Québec en Outaouais and at the University of Ottawa, as a postdoctoral fellow. Andrzej Pelc was partially supported by NSERC discovery grant and by the Research Chair in Distributed Computing at the Université du Québec en Outaouais., and Alexander A. Shvartsman, Pascal Felber
Subjects: Theoretical computer science, General Computer Science, Computer science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, 02 engineering and technology, Broadcasting, 01 natural sciences, Theoretical Computer Science, Broadcasting (networking), Computer Science::Networking and Internet Architecture, 0202 electrical engineering, electronic engineering, information engineering, Advice, Deterministic broadcasting, Computer Science::Information Theory, Distributed algorithm, business.industry, Radio network, Ask price, 010201 computation theory & mathematics, Order (business), Broadcast communication network, 020201 artificial intelligence & image processing, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], business, Constant (mathematics), Radio broadcasting, Algorithm, Advice (complexity), Computer Science(all), Computer network
Abstract: International audience; We study deterministic broadcasting in radio networks in the recently introduced framework of network algorithms with {\em advice}. We concentrate on the problem of trade-offs between the number of bits of information (size of advice) available to nodes and the time in which broadcasting can be accomplished. In particular, we ask what is the minimum number of bits of information that must be available to nodes of the network, in order to broadcast very fast. For networks in which constant time broadcast is possible under complete knowledge of the network we give a tight answer to the above question: $O(n)$ bits of advice are sufficient but $o(n)$ bits are not, in order to achieve constant broadcasting time in all these networks. This is in sharp contrast with geometric radio networks of constant broadcasting time: we show that in these networks a constant number of bits suffices to broadcast in constant time. For arbitrary radio networks we present a broadcasting algorithm whose time is inverse-proportional to the size of advice.
Published: 2010

11. Remembering without memory: Tree exploration by asynchronous oblivious robots

Author: Nicola Santoro, David Ilcinkas, Andrzej Pelc, Paola Flocchini, Distributed Computing Research Group [Ottawa], University of Ottawa [Ottawa], Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Département d'Informatique et d'Ingénierie (DII), Université du Québec en Outaouais (UQO), School of Computer Science [Ottawa], Carleton University, See paper for details., ANR-07-BLAN-0322,ALADDIN,Algorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks(2007), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Partially supported by NSERC Discovery grant. Andrzej Pelc is also partially supported by the Research Chair in Distributed Computing at the Université du Québec en Outaouais. This work was done during the stay of David Ilcinkas at the Research Chair in Distributed Computing of the Université du Québec en Outaouais and at the University of Ottawa, as a postdoctoral fellow., and Alexander A. Shvartsman, Pascal Felber
Subjects: Theoretical computer science, General Computer Science, Computer science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, 02 engineering and technology, exploration, 01 natural sciences, Constructive, Theoretical Computer Science, Combinatorics, Computer Science::Robotics, oblivious, mobile agent, 0202 electrical engineering, electronic engineering, information engineering, Mathematics, asynchronous, Discrete mathematics, Degree (graph theory), Swarm behaviour, robot, Mobile robot, Binary logarithm, tree, Asymptotically optimal algorithm, 010201 computation theory & mathematics, Asynchronous communication, Robot, Graph (abstract data type), 020201 artificial intelligence & image processing, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Computer Science(all)
Abstract: International audience; In the effort to understand the algorithmic limitations of computing by a swarm of robots, the research has focused on the minimal capabilities that allow a problem to be solved. The weakest of the commonly used models is {\sc Asynch} where the autonomous mobile robots, endowed with visibility sensors (but otherwise unable to communicate), operate in Look-Compute-Move cycles performed asynchronously for each robot. The robots are often assumed (or required to be) oblivious: they keep no memory of observations and computations made in previous cycles. We consider the setting when the robots are dispersed in an anonymous and unlabeled graph, and they must perform the very basic task of {\em exploration}: within finite time every node must be visited by at least one robot and the robots must enter a quiescent state. The complexity measure of a solution is the number of robots used to perform the task. We study the case when the graph is an arbitrary tree and establish some unexpected results. We first prove that, in general, exploration cannot be done efficiently. More precisely we prove that there are $n$-node trees where $\Omega(n)$ robots are necessary; this holds even if the maximum degree is $4$. On the other hand, we show that if the maximum degree is $3$, it is possible to explore with only $O(\frac{\log n} {\log\log n})$ robots. The proof of the result is constructive. We also prove that the size of the team used in our solution is asymptotically {\em optimal}: there are trees of degree $3$, whose exploration requires $\Omega(\frac{\log n}{\log\log n})$ robots. Our final result shows that the difficulty in tree exploration comes in fact from the symmetries of the tree. Indeed, we show that, in order to explore trees that do not have any non-trivial automorphisms, 4 robots are always sufficient and often necessary.
Published: 2010

12. Towards a Type-Theoretical Account of Lexical Semantics

Author: Bruno Mery, Christian Bassac, Christian Retoré, Centre de recherche en terminologie et traduction (CRTT), Université Lumière - Lyon 2 (UL2), Linguistic signs, grammar and meaning: computational logic for natural language (SIGNES), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), and Mery, Bruno
Subjects: Linguistics and Language, Lexical semantics, Computer science, Formal semantics (linguistics), Cognitive semantics, 0102 computer and information sciences, 0603 philosophy, ethics and religion, computer.software_genre, 01 natural sciences, [INFO.INFO-CL]Computer Science [cs]/Computation and Language [cs.CL], Lexical item, Type Theory, Computer Science (miscellaneous), business.industry, Lexicology, 06 humanities and the arts, Linguistics, Lexical Semantics, ACM: J.: Computer Applications/J.5: ARTS AND HUMANITIES/J.5.4: Linguistics, Philosophy, [INFO.INFO-CL] Computer Science [cs]/Computation and Language [cs.CL], 010201 computation theory & mathematics, Well-founded semantics, Computational semantics, 060302 philosophy, Artificial intelligence, Montague Semantics, business, computer, Generative lexicon, Natural language processing
Abstract: After a quick overview of the field of study known as "Lexical Semantics", where we advocate the need of accessing additional information besides syntax and Montague-style semantics at the lexical level in order to complete the full analysis of an utterance, we summarize the current formulations of a well-known theory of that field. We then propose and justify our own model of the Generative Lexicon Theory, based upon a variation of classical compositional semantics, and outline its formalization. Additionally, we discuss the theoretical place of informational, knowledge-related data supposed to exist within the lexicon as well as within discourse and other linguistic constructs. The formalization of the structure of natural language utterances around a surface form (phenogrammatics), a deep structure (tectogrammatics) and the meaning thereof as a logical form (semantics) has developed from the original theories of Curry and Montague to form coherent, type-driven models. Most of these new theories rely upon variations of the compositional analysis of the sentence: from pheno to tectogrammatics, and then to semantics. Our contribution to this work aims at giving such a model a means to overcome the problems posed by polysemous lexical units during the semantical analysis of the tectogrammatical form. Building upon an assumed "deep structure", we formalize parts of Pustejovsky's Generative Lexicon Theory, linguistically motivated in Pustejovsky (The generative lexicon, MIT Press, Cambridge, MA, 1995), in a pre-processing of the semantics of the sentence. The mechanisms of Lexical Semantics we propose are an additional layer of classical Montague compositional semantics, and, as such, integrate smoothly within such an analysis; we proceed by converting the lexical data to modifiers of the logical form. This treatment of Lexical Semantics furthermore induces us to think that some sort of non-evident background knowledge of the common use of words is necessary to perform a correct semantic analysis of an utterance. This "commonsense metaphysics" would therefore not be strictly confined to pragmatics, as is often assumed.
Published: 2009

13. TreeForm: Explaining and exploring grammar through syntax trees

Author: Donald Derrick, Daniel Archambault, University of British Columbia (UBC), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Graph Visualization and Interactive Exploration (GRAVITE), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), and Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest
Subjects: Linguistics and Language, Computer science, media_common.quotation_subject, 02 engineering and technology, computer.software_genre, Language and Linguistics, Domain (software engineering), Abstract syntax, 0202 electrical engineering, electronic engineering, information engineering, [INFO.INFO-HC]Computer Science [cs]/Human-Computer Interaction [cs.HC], ComputingMilieux_MISCELLANEOUS, media_common, Coreference, Grammar, business.industry, 020207 software engineering, Syntax, Linguistics, Feature (linguistics), Tree (data structure), 020201 artificial intelligence & image processing, Artificial intelligence, business, Abstract syntax tree, computer, Natural language processing, Information Systems
Abstract: Linguists studying grammar often describe their models using a syntax tree. Drawing a syntax tree involves the depiction of a rooted tree with additional syntactic features using specific domain conventions. TreeForm assists users in developing syntax trees, complete with movement lines, coreference, and feature association, in order to explore their syntactic theories and explain them to their colleagues. It is a drag-and-drop alternative to LaTeX and labelled bracket nota- tion tools already available, which many linguists find difficult to use. We com- pare the output of TreeForm to those existing tools and show that it is able to better respect the conventions of the domain. We assess how easily linguists learn to use TreeForm through a series of cognitive walkthroughs. Our reviews find that TreeForm is a viable alternative to existing tools.
Published: 2009

14. The cost of monotonicity in distributed graph searching

Author: Nicolas Nisse, David Soguet, David Ilcinkas, Département d'Informatique et d'Ingénierie (DII), Université du Québec en Outaouais (UQO), Laboratoire de Recherche en Informatique (LRI), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Additional supports from the project 'Fragile' of the ACI Sécurité Informatique, and from the project 'Grand Large' of INRIA., Eduardo Tovar, Philippas Tsigas, Hacène Fouchal, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), See paper for details., ANR-07-BLAN-0322,ALADDIN,Algorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks(2007), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)
Subjects: Monotonicity, Mathematical optimization, Theoretical computer science, Computer Networks and Communications, Computer science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 050801 communication & media studies, 0102 computer and information sciences, 02 engineering and technology, Strength of a graph, Biconnected graph, 01 natural sciences, Theoretical Computer Science, law.invention, 0508 media and communications, Graph power, law, Line graph, 0202 electrical engineering, electronic engineering, information engineering, Graph property, Complement graph, Graph searching, Distance-hereditary graph, Mobile agent, Discrete mathematics, 020203 distributed computing, 05 social sciences, Voltage graph, Directed graph, Butterfly graph, Competitive ratio, Graph bandwidth, Computational Theory and Mathematics, 010201 computation theory & mathematics, Hardware and Architecture, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Null graph, Graph factorization, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract: International audience; Blin {\it et al.} (2006) proposed a distributed protocol that enables the smallest number of searchers to clear any unknown asynchronous graph in a decentralized manner. {\it Unknown} means that the searchers are provided no {\it a priori} information about the graph. However, the strategy that is actually performed lacks of an important property, namely the monotonicity. That is, the clear part of the graph may decrease at some steps of the execution of the protocol. Actually, the protocol of Blin {\it et al.} is executed in exponential time. Nisse and Soguet (2007) proved that, in order to ensure the smallest number of searchers to clear any $n$-node graph in a monotone way, it is necessary and sufficient to provide $\Theta(n \log n)$ bits of information to the searchers by putting short labels on the nodes of the graph. This paper deals with the smallest number of searchers that are necessary and sufficient to monotoneously clear any graph in a decentralized manner, when the searchers have no a priori information about the graph. The distributed graph searching problem considers a team of searchers that is aiming at clearing any connected contaminated graph. The clearing of the graph is required to be {\it connected}, i.e., the clear part of the graph must remain permanently connected, and {\it monotone}, i.e., the clear part of the graph only grows. The {\it search number} $\mcs(G)$ of a graph $G$ is the smallest number of searchers necessary to clear $G$ in a monotone connected way in centralized settings. We prove that any distributed protocol aiming at clearing any unknown n-node graph in a monotone connected way, in decentralized settings, has {\it competitive ratio} $\Theta(\frac{n}{\log n})$. That is, we prove that, for any distributed protocol $\cal P$, there exists a constant $c$ such that for any sufficiently large $n$, there exists a $n$-node graph $G$ such that $\cal P$ requires at least $c\frac{n}{\log n}\, \mcs(G)$ searchers to clear $G$. Moreover, we propose a distributed protocol that allows $O(\frac{n}{\log n})\, \mcs(G)$ searchers to clear any unknown asynchronous $n$-node graph $G$ in a monotone connected way.
Published: 2009

15. On the Tree-Width of Planar Graphs

Author: Cyril Gavoille, Youssou Dieng, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Electronic Notes in Discrete Mathematics, ANR-06-BLAN-0148,GRAAL,Décompositions des graphes et algorithmes(2006), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), and Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest
Subjects: Block graph, Discrete mathematics, Book embedding, Planar straight-line graph, Applied Mathematics, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 010103 numerical & computational mathematics, 0102 computer and information sciences, 01 natural sciences, 1-planar graph, Planar graph, Combinatorics, symbols.namesake, tree-decomposition, 010201 computation theory & mathematics, Outerplanar graph, planar, symbols, Discrete Mathematics and Combinatorics, 0101 mathematics, ComputingMilieux_MISCELLANEOUS, MathematicsofComputing_DISCRETEMATHEMATICS, Forbidden graph characterization, Polyhedral graph, Mathematics
Abstract: We prove that every planar graph G of tree-length l has a tree-decomposition for which every bag is the union of at most 10 shortest paths of length O ( l ) . As a consequence, the tree-width of G is bounded by O ( l ) , generalizing the linear local tree-width result of planar graphs, since the tree-length of a graph does not exceed its diameter. Such a tree-decomposition can be computed in polynomial time without any prior decomposition of the input graph.
Published: 2009

16. Cost minimization in wireless networks with a bounded and unbounded number of interfaces

Author: Ralf Klasing, Adrian Kosowski, Alfredo Navarra, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Department of Algorithms and Systems Modelling [ETI GUT] (Gdansk University of Technology), Faculty of Electronics, Telecommunications and Informatics [GUT Gdańsk] (ETI), Gdańsk University of Technology (GUT)-Gdańsk University of Technology (GUT), Dipartimento di Matematica e Informatica [Perugia] (DMI), Università degli Studi di Perugia (UNIPG), ANR-05-MMSA-0006,ALPAGE,ALgorithmique des Plates-formes A Grande Echelle(2005), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, and Università degli Studi di Perugia = University of Perugia (UNIPG)
Subjects: 010201 computation theory & mathematics, Computer Networks and Communications, Hardware and Architecture, [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, ComputingMilieux_MISCELLANEOUS, Software, Information Systems
Abstract: International audience
Published: 2009

17. On the Size of Permutation Networks and Consequences for Efficient Simulation of Hypercube Algorithms on Bounded-Degree Networks

Author: PrzemysŁawa Kanarek, Walter Unger, Krzysztof Loryś, Hubert Wagener, Juraj Hromkovič, Ralf Klasing, Department of Computer Science [ETH Zürich] (D-INFK), Eidgenössische Technische Hochschule - Swiss Federal Institute of Technology [Zürich] (ETH Zürich), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Lehrstuhl für Informatik I (i1), Rheinisch-Westfälische Technische Hochschule Aachen University (RWTH), ANR-07-BLAN-0322,ALADDIN,Algorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks(2007), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, and Rheinisch-Westfälische Technische Hochschule Aachen (RWTH)
Subjects: 68M10, Vertex (graph theory), General Mathematics, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0211 other engineering and technologies, 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Combinatorics, Permutation, TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY, Permutation networks, Network design and communication, Permutation graph, Mathematics, Discrete mathematics, 90B18, 021103 operations research, Switching networks, Degree (graph theory), 94C15, Communication networks, Asymptotically optimal algorithm, 010201 computation theory & mathematics, Bounded function, Parallel algorithms AMS subject classifications. 68M07, Path (graph theory), Hypercube, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], MathematicsofComputing_DISCRETEMATHEMATICS
Abstract: International audience; The sizes of permutation networks and planar permutation networks for special sets of permutations are investigated. Several asymptotically optimal estimations for distinct subsets of the set of all permutations are established here. The two main results are: (i) an asymptotically optimal switching network of size O(N log log N) for shifts of power 2. (ii) an asymptotically optimal planar permutation network of size Θ(N 2 • (log log N/ log N) 2) for shifts of power 2. A consequence of our results is the construction of a 4-degree network which can simulate each communication step of any hypercube algorithm using edges from at most a constant number of different dimensions in one communication step in O(log log N) communication steps. An essential improvement of gossiping in vertex-disjoint path mode in bounded-degree networks follows.
Published: 2009

18. A randomized algorithm for the joining protocol in dynamic distributed networks

Author: Colin Cooper, Ralf Klasing, Tomasz Radzik, Department of Computer Science (DCS), King‘s College London, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), ANR-05-MMSA-0006,ALPAGE,ALgorithmique des Plates-formes A Grande Echelle(2005), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), and Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest
Subjects: Dynamic network analysis, General Computer Science, [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], Joining protocol, Peer to peer networks, Overlay network, Self repairing networks, 0102 computer and information sciences, 02 engineering and technology, Security token, 01 natural sciences, Theoretical Computer Science, Combinatorics, 0202 electrical engineering, electronic engineering, information engineering, ComputingMilieux_MISCELLANEOUS, Connectivity, Mathematics, Random graph, Randomized algorithm, Dynamic network, Random graph process, Neighbourhood (graph theory), 020206 networking & telecommunications, Vertex (geometry), 010201 computation theory & mathematics, Random walks, Computer Science(all), MathematicsofComputing_DISCRETEMATHEMATICS
Abstract: We describe a randomized algorithm for assigning neighbours to vertices joining a dynamic distributed network. The aim of the algorithm is to maintain connectivity, low diameter and constant vertex degree. On joining each vertex donates a constant number of tokens to the network. These tokens contain the address of the donor vertex. The tokens make independent random walks in the network. A token can be used by any vertex it is visiting to establish a connection to the donor vertex. This allows joining vertices to be allocated a random set of neighbours although the overall vertex membership of the network is unknown. The network we obtain in this way is robust under adversarial deletion of vertices and edges and actively reconnects itself.One model we consider is a network constructed in this fashion, in which vertices join but never leave. If t is the size of the network, then the diameter of the network is O(logt) for all t, with high probability. As an example of the robustness of this model, suppose an adversary deletes edges from the network leaving components of size at least t1/2+δ. With high probability the network reconnects itself by replacing lost edges using tokens from the token pool.
Published: 2008

19. Impact of memory size on graph exploration capability

Author: Andrzej Pelc, David Ilcinkas, Pierre Fraigniaud, Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Département d'Informatique et d'Ingénierie (DII), Université du Québec en Outaouais (UQO), This work was done while Pierre Fraigniaud and David Ilcinkas were with University Paris-Sud (LRI). Additional support by the project ``PairAPair' of the ACI Masses de Données, and by the project ``Grand Large' of INRIA. Supported in part by NSERC discovery grant and by the Research Chair in Distributed Computing of the Université du Québec en Outaouais., ANR-07-BLAN-0322,ALADDIN,Algorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks(2007), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), and Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest
Subjects: Theoretical computer science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Graph exploration, mobile agent, 0202 electrical engineering, electronic engineering, information engineering, memory size, Discrete Mathematics and Combinatorics, Mathematics, Finite-state machine, Memoria, Applied Mathematics, robot, Graph, Automaton, finite automaton, Graph Node, 010201 computation theory & mathematics, Robot, 020201 artificial intelligence & image processing, Regular graph, Mobile agent, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Algorithm
Abstract: International audience; A mobile agent (robot), modeled as a finite automaton, has to visit all nodes of a regular graph. How does the memory size of the agent (the number of states of the automaton) influence its exploration capability? In particular, does every increase of the memory size enable an agent to explore more graphs? We give a partial answer to this problem by showing that a strict gain of the exploration power can be obtained by a polynomial increase of the number of states. We also show that, for automata with few states, the increase of memory by even one state results in the capability of exploring more graphs.
Published: 2008
Full Text: View/download PDF

20. Position discovery for a system of bouncing robots

Author: Evangelos Kranakis, Adrian Kosowski, Oscar Morales-Ponce, Leszek Gąsieniec, Jurek Czyzowicz, Eduardo Pacheco, Département d'Informatique et d'Ingénierie (DII), Université du Québec en Outaouais (UQO), Department of Computer Science [Liverpool], University of Liverpool, Networks, Graphs and Algorithms (GANG), Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), School of Computer Science [Ottawa], Carleton University, Chalmers University of Technology [Göteborg], School of Computer Science (Carleton, Ottawa), ANR-11-BS02-0014,DISPLEXITY,Calculabilité et complexité en distribué(2011), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, and Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)
Subjects: 0209 industrial biotechnology, Computer science, Real-time computing, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, 02 engineering and technology, Topology, 01 natural sciences, Theoretical Computer Science, Task (project management), Computer Science::Robotics, Set (abstract data type), 020901 industrial engineering & automation, Line segment, Position (vector), Simulation, Mathematics, Ring (mathematics), Mobile robot, Computer Science Applications, Task (computing), Computational Theory and Mathematics, 010201 computation theory & mathematics, Robot, Unit (ring theory), Information Systems
Abstract: International audience; A collection of $n$ anonymous mobile robots is deployed on a unit-perimeter ring or a unit-length line segment. Every robot starts moving at constant speed, and bounces each time it meets any other robot or segment endpoint, changing its walk direction. We study the problem of {\em position discovery}, in which the task of each robot is to detect the presence and the initial positions of all other robots. The robots cannot communicate or perceive information about the environment in any way other than by bouncing. Each robot has a clock allowing it to observe the times of its bounces. The robots have no control on their walks, which are determined by their initial positions and the starting directions. Each robot executes the same \emph{position detection algorithm}, which receives input data in real-time about the times of the bounces, and terminates when the robot is assured about the existence and the positions of all the robots. Some initial configuration of robots are shown to be {\em infeasible} --- no position detection algorithm exists for them. We give complete characterizations of all infeasible initial configurations for both the ring and the segment, and we design optimal position detection algorithms for all feasible configurations. For the case of the ring, we show that all robot configurations in which not all the robots have the same initial direction are feasible. We give a position detection algorithm working for all feasible configurations. The cost of our algorithm depends on the number of robots starting their movement in each direction. If the less frequently used initial direction is given to $k \leq n/2$ robots, the time until completion of the algorithm by the last robot is $\frac{1}{2}\lceil \frac{n}{k} \rceil$. We prove that this time is optimal. By contrast to the case of the ring, for the unit segment we show that the family of infeasible configurations is exactly the set of so-called {\em symmetric configurations}. We give a position detection algorithm which works for all feasible configurations on the segment in time $2$, and this algorithm is also proven to be optimal.
Published: 2015

21. On the hardness of constructing minimal 2-connected spanning subgraphs in complete graphs with sharpened triangle inequality

Author: Ralf Klasing, Juraj Hromkovič, Guido Proietti, Dirk Bongartz, Sebastian Seibert, Hans-Joachim Böckenhauer, Walter Unger, Klasing, Ralf, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), and Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest
Subjects: General Computer Science, Spanning subgraph, Vertex connectivity, [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], 0102 computer and information sciences, 02 engineering and technology, Minimum-cost biconnected spanning subgraph, 01 natural sciences, Upper and lower bounds, Theoretical Computer Science, Combinatorics, 0202 electrical engineering, electronic engineering, information engineering, Graph algorithms, ComputingMilieux_MISCELLANEOUS, Minimum degree spanning tree, Mathematics, Discrete mathematics, Triangle inequality, Graph augmentation, Approximation algorithm, Approximation algorithms, Graph, Metric Graphs, [INFO.INFO-OH] Computer Science [cs]/Other [cs.OH], 010201 computation theory & mathematics, 020201 artificial intelligence & image processing, Graph factorization, Inapproximability, Computer Science(all)
Abstract: In this paper we investigate the problem of finding a 2-connected spanning subgraph of minimal cost in a complete and weighted graph G. This problem is known to be APX-hard, for both the edge and the vertex connectivity case. Here we prove that the APX-hardness still holds even if one restricts the edge costs to an interval [1, 1 + e], for an arbitrary small e > 0. This result implies the first explicit lower bound on the approximability of the general version (i.e., for arbitrary graphs) of the problem. On the other hand, if the input graph satisfies the sharpened β-triangle inequality, then a (2/3 + 1/3 ċ β/1-β)-approximation algorithm is designed. This ratio tends to 1 with β tending to ½, and it improves the previous known bound of 3/2, holding for graphs satisfying the triangle inequality, as soon as β < 5/7Furthermore, a generalized problem of increasing to 2 the edge-connectivity of any spanning subgraph of G by means of a set of edges of minimum cost is considered. This problem is known to admit a 2-approximation algorithm. Here we show that whenever the input graph satisfies the sharpened β-triangle inequality with β < 2/3, then this ratio can be improved to β/1-β.
Published: 2004
Full Text: View/download PDF

22. Analyzing Real Cluster Data for Formulating Allocation Algorithms in Cloud Platforms

Author: Olivier Beaumont, Juan-Angel Lorenzo-del-Castillo, Lionel Eyraud-Dubois, Reformulations based algorithms for Combinatorial Optimization (Realopt), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Institut de Mathématiques de Bordeaux (IMB), Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), ANR-11-INFR-0013,SONGS,Simulation de systèmes de prochaine génération(2011), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Institut de Mathématiques de Bordeaux (IMB), Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Inria Bordeaux - Sud-Ouest, Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), ANR-13-MONU-0007,SOLHAR,Solveurs pour architectures hétérogènes utilisant des supports d'exécution(2013), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, Beaumont, Olivier, Infrastructures matérielles et logicielles pour la société numérique - Simulation de systèmes de prochaine génération - - SONGS2011 - ANR-11-INFR-0013 - INFRA - VALID, and Modèles Numériques - Solveurs pour architectures hétérogènes utilisant des supports d'exécution - - SOLHAR2013 - ANR-13-MONU-0007 - MN - VALID
Subjects: Data Analysis, Computer Networks and Communications, Computer science, CPU time, Cloud computing, 02 engineering and technology, Dynamic priority scheduling, Usage data, Theoretical Computer Science, Resource (project management), Artificial Intelligence, Order (exchange), 0202 electrical engineering, electronic engineering, information engineering, [INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Parallel jobs, Resource management, Independence (probability theory), TRACE (psycholinguistics), 020203 distributed computing, business.industry, Scale (chemistry), 020206 networking & telecommunications, Cloud Computing, Computer Graphics and Computer-Aided Design, [INFO.INFO-MO]Computer Science [cs]/Modeling and Simulation, Hardware and Architecture, Resource allocation, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], business, Algorithm, Software
Abstract: We analyze a large cluster trace released by Google.We provide information about static and dynamic features of dominant jobs.We show that memory usage of tasks is independent of CPU usage for most jobs.We analyze the independence of machine failures.Based on this analysis, we propose several algorithmic formulations for allocation problems. A problem commonly faced in Computer Science research is the lack of real usage data that can be used for the validation of algorithms. This situation is particularly true and crucial in Cloud Computing. The privacy of data managed by commercial Cloud infrastructures, together with their massive scale, makes them very uncommon to be available to the research community. Due to their scale, when designing resource allocation algorithms for Cloud infrastructures, many assumptions must be made in order to make the problem tractable.This paper provides deep analysis of a cluster data trace recently released by Google and focuses on a number of questions which have not been addressed in previous studies. In particular, we describe the characteristics of job resource usage in terms of dynamics (how it varies with time), of correlation between jobs (identify daily and/or weekly patterns), and correlation inside jobs between the different resources (dependence of memory usage on CPU usage). From this analysis, we propose a way to formalize the allocation problem on such platforms, which encompasses most job features from the trace with a small set of parameters.
Published: 2014

23. Broadcasting on Large Scale Heterogeneous Platforms under the Bounded Multi-Port Model

Author: Olivier Beaumont, Nicolas Bonichon, Przemyslaw Uznanski, Lionel Eyraud-Dubois, Shailesh Kumar Agrawal, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Reformulations based algorithms for Combinatorial Optimization (Realopt), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Institut de Mathématiques de Bordeaux (IMB), Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'informatique Fondamentale de Marseille (LIF), Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS), Citibank, Singapore, ANR-11-INFR-0013,SONGS,Simulation de systèmes de prochaine génération(2011), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Institut de Mathématiques de Bordeaux (IMB), Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Inria Bordeaux - Sud-Ouest, Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, and Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU)
Subjects: 020203 distributed computing, business.industry, Computer science, Distributed computing, overlay networks, Overlay network, Approximation algorithm, 020206 networking & telecommunications, 02 engineering and technology, Broadcasting, transport protocols, Approximation methods, Scheduling (computing), Computational Theory and Mathematics, Hardware and Architecture, Bounded function, Models of communication, Signal Processing, 0202 electrical engineering, electronic engineering, information engineering, distributed processing, Peer-to-peer computing, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], business, Computer network
Abstract: International audience; We consider the classical problem of broadcasting a large message at an optimal rate in a large scale distributed network under the multi-port communication model. In this context, we are interested in both building an overlay network and providing an explicit algorithm for scheduling the communications. From an optimization point of view, we aim both at maximizing the throughput (ie the rate at which nodes receive the message) and minimizing the degree of the participating nodes, ie the number of TCP connections they must handle simultaneously. The main novelties of our approach are the introduction of this degree constraint and the classification of the set of participating nodes into two parts: open nodes that stay in the open-Internet and "guarded'' nodes that lie behind firewalls or NATs. Two guarded nodes cannot communicate directly, but rather need to use an open node as a gateway for transmitting a message. In the case without guarded nodes, we prove that it is possible to reach the optimal throughput, at the price of a quasi-optimal (up to a small additive increase) degree of the participating nodes. In presence of guarded nodes, our main contributions are a closed form formula for the optimal cyclic throughput and the proof that the optimal solution may require arbitrarily large degrees. In the acyclic case, we propose an algorithm that reaches the optimal throughput with low degree. Then, we prove a worst case ratio between the optimal acyclic and cyclic throughput and show through simulations that this ratio is on average very close to 1, what makes acyclic solutions efficient both in terms of throughput maximization and degree minimization.
Published: 2014

24. There are Plane Spanners of Maximum Degree 4 (extended abstract)

Author: Bonichon, Nicolas, Kanj, Iyad, Perkovic, Ljubomir, Xia, Ge, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), School of Computer Science, Telecommunications, and Information Systems [DePaul] (CTI), DePaul University [Chicago], School of Computing [DePaul] (SOC), Department of Computer Science - Lafayette College, Lafayette College [Easton], CPU, Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), and Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest
Subjects: [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], ComputingMilieux_MISCELLANEOUS
Abstract: International audience
Published: 2014

25. Impact de la dynamique sur la fiabilité d'informations de routage

Author: Glacet, Christian, Hanusse, Nicolas, Ilcinkas, David, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Combinatoire et Algorithmique, Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), and Glacet, Christian
Subjects: [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS]
Abstract: International audience; Pour permettre le routage dans un graphe, les nœuds doivent connaître des portions de route. La dynamique du graphe peut rendre les informations stockées erronées. Cet article s'intéresse à la caractérisation de la quantité d'informations erronées, ainsi qu'aux nombre de changements de distances dans le graphe suite à L suppressions d'arêtes et L' suppressions de nœuds. Nous considérons un graphe G de diamètre D possédant N nœuds et M arêtes. Nous montrons que l'espérance du nombre d'erreurs et de changement de distance est d'au plus D (LN/M + L').
Published: 2014

26. Time versus space trade-offs for rendezvous in trees

Author: Adrian Kosowski, Jurek Czyzowicz, Andrzej Pelc, Département d'Informatique et d'Ingénierie (DII), Université du Québec en Outaouais (UQO), Networks, Graphs and Algorithms (GANG), Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), ANR-11-BS02-0014,DISPLEXITY,Calculabilité et complexité en distribué(2011), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Inria Bordeaux - Sud-Ouest, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Sciences et Technologies - Bordeaux 1
Subjects: Logarithm, Computer Networks and Communications, Computer science, Node (networking), Distributed computing, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Rendezvous, Tree (graph theory), memory space, Theoretical Computer Science, Combinatorics, Task (computing), Computational Theory and Mathematics, Hardware and Architecture, anonymous agents, Theory of computation, Line (geometry), rendezvous, Constant (mathematics), time
Abstract: Two identical (anonymous) mobile agents start from arbitrary nodes of an unknown tree and have to meet at some node. Agents move in synchronous rounds: in each round an agent can either stay at the current node or move to one of its neighbors. We consider deterministic algorithms for this rendezvous task. The main result of this paper is a tight trade-off between the optimal time of completing rendezvous and the size of memory of the agents. For agents with $$k$$ memory bits, we show that optimal rendezvous time is $$\Theta (n+n^2/k)$$ in $$n$$ -node trees. More precisely, if $$k \ge c\log n$$ , for some constant $$c$$ , we design agents accomplishing rendezvous in arbitrary trees of size $$n$$ (unknown to the agents) in time $$O(n+n^2/k)$$ , starting with arbitrary delay. We also show that no pair of agents can accomplish rendezvous in time $$o(n+n^2/k)$$ , even in the class of lines of known length and even with simultaneous start. Finally, we prove that at least logarithmic memory is necessary for rendezvous, even for agents starting simultaneously in a $$n$$ -node line.
Published: 2014

27. Complexité de l'exploration par agent mobile des graphes dynamiques

Author: Wade, Ahmed, Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Combinatoire et Algorithmique, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Université de Bordeaux, Ralf Klasing(klasing@labri.fr), Wade, Ahmed Mouhamadou, Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, and Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)
Subjects: Mobile agent, [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], T-intervalle-connexité, [INFO.INFO-RB] Computer Science [cs]/Robotics [cs.RO], [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], graphe dynamique, agent mobile, PV-graphs, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], exploration, [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], [INFO.INFO-RB]Computer Science [cs]/Robotics [cs.RO], [INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC], PV-graphe, Dynamic graphs, T-interval-connected
Abstract: In this thesis, we study the complexity of the problem of exploration by a mobile agent in dynamic graphs. A mobile entity (called agent) moving in a dynamic graph has to traverse/visit each of its vertices at least once. This fundamental problem in computating by mobile agents has been well-studied in static graphs since the original paper of Claude Shannon. However, for highly dynamic graphs, only the case of periodic dynamic graphs has been studied. We study this problem in two families of dynamic graphs, periodically-varying graphs (PV-graphs) and T-interval-connected dynamic graphs. The obtained results improve the existing results and give optimal bounds on the studied problems. A PV-graph is defined by a set of carriers infinitely following their prescribed route along the network stations. In 2013, Flocchini, Mans and Santoro studied the problem in the case when the agent must always travel on the carriers and thus cannot wait at a station. Our work investigates the ability of an agent that can wait at the stations. We exhibit 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(n\cdot p)$, where $n$, $k$, and $p$ denote respectively the number of sites, the number of carriers, and the maximal period. (In any connected PV-graph, we have $n \leq k\cdot p$.) We also show some complementary optimal results in specific cases (same period for all carriers, highly connected PV-graphs). Finally this ability allows the agent to produce a complete map of the PV-graph, in addition to just explore it. In the second part of the thesis, we considered the same problem (exploration) in T-interval-connected dynamic graphs. A dynamic graph is T-interval-connected ($T \geq 1$) if for every consecutive $T$ rounds, there exists a stable connected spanning subgraph. We considered T-interval-connected dynamic graphs such that the underlying graph is a ring of size $n$. We show that in the worst case the complexity is $2n-T-2$ time units if the agent knows the dynamic of the graph, and $\frac{n-1}{T} \delta +n \pm \Theta(\delta) -1$ time units if the agent does not know the dynamics of the graph, where $\delta$ is the maximum time between two successive appearances of an edge. Furthermore, we generalize these results by considering another family of underlying graphs, cactus graphs. A cactus graph is a connected graph in which any two simple cycles have at most one vertex in common. We propose an algorithm that allows the agent to explore these dynamic graphs in at most $2^{O(\sqrt{log n})} n$ time units. We show that the lower bound of our algorithm is $2^{\Omega(\sqrt{log n})} n$ time units., Cette thèse porte sur l'étude de la complexité de l'exploration de graphes dynamiques par agent mobile. Une entité mobile (appelée agent) se déplaçant dans un graphe dynamique doit traverser/visiter au moins une fois chacun de ses sommets. (Le temps de traversée d'une arête est unitaire.) Ce problème fondamental en algorithmique par agents mobiles a été très étudié dans les graphes statiques depuis l'article originel de Claude Shannon. Concernant les graphes dynamiques, seul le cas des graphes dynamiques périodiques a été étudié. Nous étudions ce problème dans deux familles de graphes dynamiques, les graphes dynamiques périodiquement variables (PV-graphes) et les graphes dynamiques T-intervalle-connexes. Les résultats obtenus dans cette thèse améliorent des résultats existants et donnent des bornes optimales sur le problème étudié. Un PV-graphe est défini par un ensemble de transporteurs suivant infiniment leur route respective le long des stations du réseau. En 2013, Flocchini, Mans et Santoro ont étudié le problème de l'exploration des PV-graphes en considérant que l'agent doit toujours rester sur les transporteurs. Cette thèse montre l'impact de la capacité d'attendre sur les stations. Nous prouvons que l'attente sur les stations permet à l'agent d'atteindre de meilleures complexités en pire cas : le nombre de mouvements est réduit d'un facteur multiplicatif d'au moins $\Theta(p)$, et la complexité en temps passe de $\Theta(kp^2)$ à $\Theta(np)$, où $n$ est le nombre de stations, $k$ le nombre de transporteurs, et $p$ la période maximale ($n\leq kp$ dans tout PV-graphe connexe). Par ailleurs, l'algorithme que nous proposons pour prouver les bornes supérieures permet de réaliser la cartographie du PV-graphe, en plus de l'explorer. Dans la deuxième partie de cette thèse, nous considérons le même problème (l'exploration) dans les graphes dynamiques T-intervalle-connexes. 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. Nous considérons dans un premier temps les graphes dynamiques T-intervalle-connexes qui ont un anneau de taille $n$ comme graphe sous-jacent et nous montrons que la complexité en temps en pire cas de leurs exploration 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. Nous généralisons ensuite ces résultats en considérant une autre famille de graphes sous-jacents, les cactus à $n$ sommets. Un cactus est un graphe connexe dans lequel deux cycles ont au plus un sommet en commun. Nous donnons un algorithme qui permet d'explorer ces graphes dynamiques en au plus $2^{O(\sqrt{log n})} n$ unités de temps, et nous montrons que la borne inférieure de notre algorithme est $2^{\Omega(\sqrt{log n})} n$.
Published: 2014

28. Parallel scheduling of task trees with limited memory

Author: Eyraud-Dubois, Lionel, Marchal, Loris, Sinnen, Oliver, Vivien, Frédéric, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Optimisation des ressources : modèles, algorithmes et ordonnancement (ROMA), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon), Laboratoire de l'Informatique du Parallélisme (LIP), Department of Electrical and Computer Engineering [Auckland ] (ECE), University of Auckland [Auckland], INRIA, Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), and Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)
Subjects: memory usage, pebble-game, task graphs, multi-criteria optimization, scheduling, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Approximation algorithms
Abstract: This paper investigates the execution of tree-shaped task graphs using multiple processors. Each edge of such a tree represents some large data. A task can only be executed if all input and output data fit into memory, and a data can only be removed from memory after the completion of the task that uses it as an input data. Such trees arise, for instance, in the multifrontal method of sparse matrix factorization. The peak memory needed for the processing of the entire tree depends on the execution order of the tasks. With one processor the objective of the tree traversal is to minimize the required memory. This problem was well studied and optimal polynomial algorithms were proposed. Here, we extend the problem by considering multiple processors, which is of obvious interest in the application area of matrix factorization. With multiple processors comes the additional objective to minimize the time needed to traverse the tree, i.e., to minimize the makespan. Not surprisingly, this problem proves to be much harder than the sequential one. We study the computational complexity of this problem and provide inapproximability results even for unit weight trees. We design a series of practical heuristics achieving different trade-offs between the minimization of peak memory usage and makespan. Some of these heuristics are able to process a tree while keeping the memory usage under a given memory limit. The different heuristics are evaluated in an extensive experimental evaluation using realistic trees.; Dans ce rapport, nous nous intéressons au traitement d'arbres de tâches par plusieurs processeurs. Chaque arête d'un tel arbre représente un gros fichier d'entrée/sortie. Une tâche peut être traitée seulement si l'ensemble de ses fichiers d'entrée et de sortie peut résider en mémoire, et un fichier ne peut être retiré de la mémoire que lorsqu'il a été traité. De tels arbres surviennent, par exemple, lors de la factorisation de matrices creuses par des méthodes multifrontales. La quantité de mémoire nécessaire dépend de l'ordre de traitement des tâches. Avec un seul processeur, l'objectif est naturellement de minimiser la quantité de mémoire requise. Ce problème a déjà été étudié et des algorithmes polynomiaux ont été proposés. Nous étendons ce problème en considérant plusieurs processeurs, ce qui est d'un intérêt évident pour le problème de la factorisation de grandes matrices. Avec plusieurs processeurs se pose également le problème de la minimisation du temps nécessaire pour traiter l'arbre. Nous montrons que comme attendu, ce problème est bien plus compliqué que dans le cas séquentiel. Nous étudions la complexité de ce problème et nous fournissons des résultats d'inaproximabilité, même dans le cas de poids unitaires. Nous proposons plusieurs heuristiques qui obtiennent différents compromis entre mémoire et temps d'exécution. Certaines d'entre elles sont capables de traiter l'arbre tout en gardant la consommation mémoire inférieure à une limite donnée. Nous analysons les performances de toutes ces heuristiques par une large campagne de simulations utilisant des arbres réalistes.
Published: 2014

29. There are Plane Spanners of Maximum Degree 4

Author: Ljubomir Perkovic, Nicolas Bonichon, Iyad A. Kanj, Ge Xia, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), School of Computer Science, Telecommunications, and Information Systems [DePaul] (CTI), DePaul University [Chicago], School of Computing [DePaul] (SOC), Department of Computer Science - Lafayette College, Lafayette College [Easton], CPU, Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), and Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest
Subjects: Computational Geometry (cs.CG), FOS: Computer and information sciences, Degree (graph theory), Delaunay triangulation, Spanner, Computer Science::Computational Geometry, [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG], Upper and lower bounds, Planarity testing, Combinatorics, Stretch factor, Spatial network, Computer Science - Computational Geometry, Theta graph, Computer Science::Data Structures and Algorithms, Mathematics
Abstract: Let E be the complete Euclidean graph on a set of points embedded in the plane. Given a constant t >= 1, a spanning subgraph G of E is said to be a t-spanner, or simply a spanner, if for any pair of vertices u,v in E the distance between u and v in G is at most t times their distance in E. A spanner is plane if its edges do not cross. This paper considers the question: "What is the smallest maximum degree that can always be achieved for a plane spanner of E?" Without the planarity constraint, it is known that the answer is 3 which is thus the best known lower bound on the degree of any plane spanner. With the planarity requirement, the best known upper bound on the maximum degree is 6, the last in a long sequence of results improving the upper bound. In this paper we show that the complete Euclidean graph always contains a plane spanner of maximum degree at most 4 and make a big step toward closing the question. Our construction leads to an efficient algorithm for obtaining the spanner from Chew's L1-Delaunay triangulation.
Published: 2014
Full Text: View/download PDF

30. Extending ER models to capture database transformations to build data sets for data mining

Author: Carlos Ordonez, David Sergio Matusevich, Sofian Maabout, Wellington Cabrera, Department of computer Science [Houston], Rice University [Houston], Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), and Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest
Subjects: Physical data model, Information Systems and Management, [INFO.INFO-DB]Computer Science [cs]/Databases [cs.DB], Database, Relational database, Computer science, View, Data definition language, Database schema, InformationSystems_DATABASEMANAGEMENT, computer.software_genre, Database design, Database theory, Data mining, computer, computer.programming_language, Database model
Abstract: Mis en ligne le 19/12/2013; International audience; In a data mining project developed on a relational database, a significant effort is required to build a data set for analysis. The main reason is that, in general, the database has a collection of normalized tables that must be joined, aggregated and transformed in order to build the required data set. Such scenario results in many complex SQL queries that are written independently from each other, in a disorganized manner. Therefore, the database grows with many tables and views that are not present as entities in the ER model and similar SQL queries are written multiple times, creating problems in database evolution and software maintenance. In this paper, we classify potential database transformations, we extend an ER diagram with entities capturing database transformations and we introduce an algorithm which automates the creation of such extended ER model. We present a case study with a public database illustrating database transformations to build a data set to compute a typical data mining model.
Published: 2013

31. Approximation Algorithms for Energy Minimization in Cloud Service Allocation under Reliability Constraints

Author: Paul Renaud-Goud, Olivier Beaumont, Philippe Duchon, Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Renaud-Goud, Paul, Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, and Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)
Subjects: FOS: Computer and information sciences, Computer science, Distributed computing, Reliability (computer networking), Cloud computing, 02 engineering and technology, computer.software_genre, energy savings, Service-level agreement, 0202 electrical engineering, electronic engineering, information engineering, [INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Resource management, approximation, Service (business), 020203 distributed computing, reliability, business.industry, Context (computing), Approximation algorithm, Energy consumption, Replication (computing), Computer Science - Distributed, Parallel, and Cluster Computing, Virtual machine, Resource allocation, 020201 artificial intelligence & image processing, Distributed, Parallel, and Cluster Computing (cs.DC), [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], business, computer, Cloud
Abstract: We consider allocation problems that arise in the context of service allocation in Clouds. More specifically, we assume on the one part that each computing resource is associated to a capacity constraint, that can be chosen using Dynamic Voltage and Frequency Scaling (DVFS) method, and to a probability of failure. On the other hand, we assume that the service runs as a set of independent instances of identical Virtual Machines. Moreover, there exists a Service Level Agreement (SLA) between the Cloud provider and the client that can be expressed as follows: the client comes with a minimal number of service instances which must be alive at the end of the day, and the Cloud provider offers a list of pairs (price,compensation), this compensation being paid by the Cloud provider if it fails to keep alive the required number of services. On the Cloud provider side, each pair corresponds actually to a guaranteed success probability of fulfilling the constraint on the minimal number of instances. In this context, given a minimal number of instances and a probability of success, the question for the Cloud provider is to find the number of necessary resources, their clock frequency and an allocation of the instances (possibly using replication) onto machines. This solution should satisfy all types of constraints during a given time period while minimizing the energy consumption of used resources. We consider two energy consumption models based on DVFS techniques, where the clock frequency of physical resources can be changed. For each allocation problem and each energy model, we prove deterministic approximation ratios on the consumed energy for algorithms that provide guaranteed probability failures, as well as an efficient heuristic, whose energy ratio is not guaranteed., Nous considérons un problème d'allocation de services dans des \textit{Clouds}. Les resources de calcul sont caractérisées par une probabilité de panne, et une contrainte de capacité, qui peut être ajustée grâce à la technique dite de Dynamic Voltage and Frequency Scaling (DVFS). Il existe un contrat entre le fournisseur et le client, le fournisseur assurant au client qu'un certain nombre d'instances du service du client sera toujours en train de s'exécuter à la fin de la journée, avec une certaine probabilité. La question est donc de savoir à quelle vitesse devront tourner les processeurs, et à quel point les services devront être répliqués sur les machines. Nous exhibons des algorithmes d'approximation, prouvons leurs facteurs d'approximation sur l'énergie consommée, et décrivons des heuristiques performantes.
Published: 2013

32. Calcul parallèle de dépendances

Author: Garnaud, Eve, Hanusse, Nicolas, Maabout, Sofian, Novelli, Noël, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'informatique Fondamentale de Marseille - UMR 6166 (LIF), Université de la Méditerranée - Aix-Marseille 2-Université de Provence - Aix-Marseille 1-Centre National de la Recherche Scientifique (CNRS), Maabout, Sofian, Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), and Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest
Subjects: [INFO.INFO-DB]Computer Science [cs]/Databases [cs.DB], [INFO.INFO-DB] Computer Science [cs]/Databases [cs.DB]
Abstract: National audience; L'extraction de dépendances fonctionnelles (DFs) est un probléme classique qui continue de susciter de nouveaux travaux du fait des multiples exploitations possibles que cette information peut avoir. Dans cet article, nous présentons un algorithme paralléle paramétrable qui calcule les DFs exactes, DFs approchées, DFs conditionnelles (DFCs) ainsi que les clés minimales. Pour les cas des DFs exactes et des clés minimales, les tests de validité sont basés sur un calcul de nombre de valeurs distinctes. Nous étudions l'introduction des techniques d'approximation proposées á cet effet (nombre de valeurs distinctes), précisément la méthode Hyperloglog, permettant ainsi d'économiser l'espace mémoire et ouvrant la voie á une approche paralléle orientée données. Ceci est d'autant plus important quand les données sont massives. Bien que les résultats retournés dans ce dernier cas soient approximatifs, nous donnons des bornes théoriques sur les erreurs qu'on peut avoir. Une série d'expériences montrent l'efficacité de notre approche.
Published: 2013

33. On the Communication Complexity of Distributed Name-Independent Routing Schemes

Author: Nicolas Hanusse, Christian Glacet, David Ilcinkas, Cyril Gavoille, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Institut Universitaire de France (IUF), Ministère de l'Education nationale, de l’Enseignement supérieur et de la Recherche (M.E.N.E.S.R.), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), See paper for details., ANR-11-BS02-0014,DISPLEXITY,Calculabilité et complexité en distribué(2011), European Project: 258307,EC:FP7:ICT,FP7-ICT-2009-5,EULER(2010), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, Ilcinkas, David, BLANC - Calculabilité et complexité en distribué - - DISPLEXITY2011 - ANR-11-BS02-0014 - BLANC - VALID, and Experimental UpdateLess Evolutive Routing - EULER - - EC:FP7:ICT2010-10-01 - 2014-06-30 - 258307 - VALID
Subjects: TheoryofComputation_MISCELLANEOUS, distributed routing algorithm, compact routing, Routing table, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 020206 networking & telecommunications, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, 02 engineering and technology, bounded stretch, 01 natural sciences, Combinatorics, Asynchronous algorithms, 010201 computation theory & mathematics, TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY, Shortest path problem, 0202 electrical engineering, electronic engineering, information engineering, [INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Graph (abstract data type), [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Communication complexity, name-independent, Mathematics, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract: International audience; We present a distributed asynchronous algorithm that, for every undirected weighted $n$-node graph $G$, constructs name-independent routing tables for $G$. The size of each table is $\tO(\sqrt{n}\,)$, whereas the length of any route is stretched by a factor of at most~$7$ w.r.t. the shortest path. At any step, the memory space of each node is $\tO(\sqrt{n}\,)$. The algorithm terminates in time $O(D)$, where $D$ is the hop-diameter of $G$. In synchronous scenarios and with uniform weights, it consumes $\tO(m\sqrt{n} + n^{3/2}\min\set{D,\sqrt{n}\,})$ messages, where $m$ is the number of edges of $G$. In the realistic case of sparse networks of poly-logarithmic diameter, the communication complexity of our scheme, that is $\tO(n^{3/2})$, improves by a factor of $\sqrt{n}$ the communication complexity of \emph{any} shortest-path routing scheme on the same family of networks. This factor is provable thanks to a new lower bound of independent interest.
Published: 2013

34. Modélisation des communications sur plates-formes à grande echelles

Author: Uznanski, Przemyslaw, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Université Sciences et Technologies - Bordeaux I, Olivier Beaumont, Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), and Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest
Subjects: Power aware routing, [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], PlanetLab, Bandwidth sharing, Streaming, Requêtes découpables, Pare-feu, Network prediction, Diffusion, Système de prédiction réseau, Firewalls, Splittable requests, Routage efficace en énergie, Partage de bande passante, Broadcast, LastMile
Abstract: The increasing popularity of Internet bandwidth-intensive applications prompts us to consider followingproblem: How to compute efficient collective communication schemes on large-scale platform?The issue of designing a collective communication in the context of a large scale distributed networkis a difficult and a multi-level problem. A lot of solutions have been extensively studied andproposed. But a new, comprehensive and systematic approach is required, that combines networkmodels and algorithmic design of solutions.In this work we advocate the use of models that are able to capture real-life network behavior,but also are simple enough that a mathematical analysis of their properties and the design of optimalalgorithms is achievable.First, we consider the problem of the measuring available bandwidth for a given point-topointconnection. We discuss how to obtain reliable datasets of bandwidth measurements usingPlanetLab platform, and we provide our own datasets together with the distributed software usedto obtain it. While those datasets are not a part of our model per se, they are necessary whenevaluating the performance of various network algorithms. Such datasets are common for latencyrelatedproblems, but very rare when dealing with bandwidth-related ones.Then, we advocate for a model that tries to accurately capture the capabilities of a network,named LastMile model. This model assumes that essentially the congestion happens at the edgesconnecting machines to the wide Internet. It has a natural consequence in a bandwidth predictionalgorithm based on this model. Using datasets described earlier, we prove that this algorithm is ableto predict with an accuracy comparable to best known network prediction algorithm (DistributedMatrix Factorization) available bandwidth between two given nodes. While we were unable toimprove upon DMF algorithm in the field of point-to-point prediction, we show that our algorithmhas a clear advantage coming from its simplicity, i.e. it naturally extends to the network predictionsunder congestion scenario (multiple connections sharing a bandwidth over a single link). We areactually able to show, using PlanetLab datasets, that LastMile prediction is better in such scenarios.In the third chapter, we propose new algorithms for solving the large scale broadcast problem.We assume that the network is modeled by the LastMile model. We show that under thisassumption, we are able to provide algorithms with provable, strong approximation ratios. Takingadvantage of the simplicity and elasticity of the model, we can even extend it, so that it captures theidea of connectivity artifacts, in our case firewalls preventing some nodes to communicate directlybetween each other. In the extended case we are also able to provide approximation algorithmswith provable performance.The chapters 1 to 3 form three successful steps of our program to develop from scratch amathematical network communication model, prove it experimentally, and show that it can beapplied to develop algorithms solving hard problems related to design of communication schemesin networks.In the chapter 4 we show how under different network cost models, using some simplifyingassumptions on the structure of network and queries, one can design very efficient communicationschemes using simple combinatorial techniques. This work is complementary to the previous chapter in the sense that previously when designing communication schemes, we assumed atomicityof connections, i.e. that we have no control over routing of simple connections. In chapter 4 weshow how to solve the problem of an efficient routing of network request, given that we know thetopology of the network. It shows the importance of instantiating the parameters and the structureof the network in the context of designing efficient communication schemes.; La popularité croissante des applications Internet très gourmandes en bande passante (P2P, streaming,...) nous pousse à considérer le problème suivant :Comment construire des systèmes de communications collectives efficaces sur une plateforme à grande échelle ? Le développement de schéma de communications collectives dans le cadre d'un réseau distribué à grande échelle est une tâche difficile, qui a été largement étudiée et dont de multiples solutions ont été proposées. Toutefois, une nouvelle approche globale et systématique est nécessaire, une approche qui combine des modèles de réseaux et la conception algorithmique.Dans ce mémoire nous proposons l'utilisation de modèles capables de capturer le comportement d'un réseau réel et suffisamment simples pour que leurs propriétés mathématiques puissentêtre étudiées et pour qu'il soit possible de créer des algorithmesoptimaux. Premièrement, nous considérons le problème d'évaluation de la bande passante disponible pour une connexion point-à-point donnée. Nousétudions la façon d'obtenir des jeux de données de bande passante, utilisant plateforme PlanetLab. Nous présentons aussi nos propres jeux de données, jeux obtenus avec bedibe, un logiciel que nous avons développé. Ces données sont nécessaires pour évaluer les performances des différents algorithmesde réseau. Bien qu'on trouve de nombreux jeux de données de latence,les jeux de données de bande passante sont très rares. Nous présentons ensuite un modèle, appelé LastMile, qui estime la bande passante. En profitant des jeux de données décrits précédemment, nous montrons que cet algorithme est capable de prédire la bande passante entre deux noeuds donnés avec une précision comparable au meilleur algorithme connu de prédiction (DMF). De plus le modèle LastMile s'étend naturellement aux prédictions dans le scénario de congestion (plusieurs connexions partageant un même lien). Nous sommes effectivement en mesure de démontrer, à l'aide des ensembles de données PlanetLab, que la prédiction LastMile est préférable dans des tels scénarios.Dans le troisième chapitre, nous proposons des nouveaux algorithmes pour résoudre le problème de diffusion. Nous supposons que le réseau est modélisé par le modèle LastMile. Nous montrons que, sous cette hypothèse, nous sommes en mesure de fournir des algorithmes avec des ratios d'approximation élevés. De plus nous étendons le modèle LastMile, de manière à y intégrer des artéfacts de connectivité, dans notre cas ce sont des firewalls qui empêchent certains nœuds de communiquer directement entre eux. Dans ce dernier cas, nous sommes également en mesure de fournir des algorithmes d'approximation avec des garanties de performances prouvables. Les chapitres 1 à 3 forment les trois étapes accomplies de notre programme qui visent trois buts. Premièrement, développer à partir dezéro un modèle de réseau de communication. Deuxièmement, prouver expérimentalement sa performance. Troisièmement, montrer qu'il peut être utilisé pour développer des algorithmes qui résolvent les problèmes de communications collectives. Dans le 4e chapitre, nous montrons comment on peut concevoir dessystèmes de communication efficaces, selon différents modèles decoûts, en utilisant des techniques combinatoires,tout en utilisant des hypothèses simplificatrices sur la structure duréseau et les requêtes. Ce travail est complémentaire au chapitre précédent puisque auparavant, nous avons adopté l'hypothèse que les connectionsétaient autonomes (i.e. nous n'avons aucun contrôle sur le routage des connexions simples). Dans le chapitre 4, nous montrons comment résoudre le problème du routage économe en énergie, étant donnée une topologie fixée.
Published: 2013

35. Lower Bounds on the Communication Complexity of Binary Local Quantum Measurement Simulation

Author: Kosowski, Adrian, Markiewicz, Marcin, Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Institute of Theoretical Physics and Astrophysics [Univ Gdańsk] (IFTIA), Faculty of Mathematics, Physics and Informatics [Univ Gdańsk], University of Gdańsk (UG)-University of Gdańsk (UG), Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, and Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)
Subjects: FOS: Computer and information sciences, Quantum Physics, Classical Simulation of Quantum Measurements, Quantum Nonlocality, [PHYS.QPHY]Physics [physics]/Quantum Physics [quant-ph], [INFO.INFO-IT]Computer Science [cs]/Information Theory [cs.IT], Information Theory (cs.IT), Computer Science - Information Theory, FOS: Physical sciences, [MATH.MATH-IT]Mathematics [math]/Information Theory [math.IT], Communication Complexity, Quantum Physics (quant-ph)
Abstract: We consider the problem of the classical simulation of quantum measurements in the scenario of communication complexity. Regev and Toner (2007) have presented a 2-bit protocol which simulates one particular correlation function arising from binary projective quantum measurements on arbitrary state, and in particular does not preserve local averages. The question of simulating other correlation functions using a protocol with bounded communication, or preserving local averages, has been posed as an open one. Within this paper we resolve it in the negative: we show that any such protocol must have unbounded communication for some subset of executions. In particular, we show that for any protocol, there exist inputs for which the random variable describing the number of communicated bits has arbitrarily large variance.
Published: 2013

36. Proceedings of the third MEDI international conference

Author: Cuzzocrea, Alfredo, Maabout, Sofian, University of Calabria, Università della Calabria [Arcavacata di Rende] (Unical), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), and Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest
Subjects: [INFO.INFO-DB]Computer Science [cs]/Databases [cs.DB]
Abstract: International audience; This volume of LNCS contains the proceedings of the third international conference on models and data engineering.
Published: 2013

37. Energy-Efficient Leader Election Protocols for Single-Hop Radio Networks

Author: Marcin Kardas, Dominik Pajak, Marek Klonowski, Institute of Mathematics and Computer Science [Wroclaw] (IMCS), Wroclaw University of Science and Technology, Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, and Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)
Subjects: Protocol (science), Leader election, SIMPLE (military communications protocol), business.industry, Computer science, ComputerSystemsOrganization_COMPUTER-COMMUNICATIONNETWORKS, 0102 computer and information sciences, 02 engineering and technology, Energy consumption, 01 natural sciences, 010201 computation theory & mathematics, 0202 electrical engineering, electronic engineering, information engineering, Computer Science::Networking and Internet Architecture, 020201 artificial intelligence & image processing, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], business, Time complexity, Energy (signal processing), Computer network, Efficient energy use
Abstract: International audience; In this paper we investigate leader election protocols for single-hop radio networks from perspective of energetic complexity. We discuss different models of energy consumption and its relation with time complexity. We also present some results about energy consumption in classic protocols optimal with respect to time complexity -- we show that some very basic, intuitive algorithms for simplest models (with known number of stations) do not have to be optimal when energy of stations is restricted. We show that they can be significantly improved by introducing very simple modifications. Our main technical result is however a protocol for solving leader election problem in case of unknown number of stations $n$, working on expectancy within $O(\log^\epsilon n)$ rounds, with each station transmitting $O(1)$ number of times and no station being awake for more than $O(\log \log \log n)$ rounds.
Published: 2013

38. Time and Space-Efficient Algorithms for Mobile Agents in an Anonymous Network

Author: Kosowski, Adrian, Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Combinatoire et Algorithmique, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Université Sciences et Technologies - Bordeaux I, Cyril Gavoille, ANR DISPLEXITY, NCN N N206 491738, NCN DEC-2011/02/A/ST6/00201, Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), and Kosowski, Adrian
Subjects: Anonymous Network, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], De-rendomization, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], Universal Traversal Sequence, ComputingMethodologies_ARTIFICIALINTELLIGENCE, Graph Exploration, Rendezvous in Graphs, Distributed Algorithm, Random Walk, Metropolis Walk, [INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Rotor-Router Walk, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Mobile Agent
Abstract: Computing with mobile agents is rapidly becoming a topic of mainstream research in the theory of distributed computing. The main research questions undertaken in this study concern the feasibility of solving fundamental tasks in an anonymous network, subject to limitations on the resources available to the agent. The considered challenges include: exploring a graph by means of an agent with limited memory, discovery of the network topology, and attempting to meet with another agent in another network (rendezvous). The constraints imposed on the agent include the number of moves which the agent is allowed to perform in the network, the amount of state memory available to the agent, the ability of the agent to communicate with other agents, as well as its a priori knowledge of the network topology or of global parameters.
Published: 2013

39. Reliable Service Allocation in Clouds with Memory and Capacity Constraints

Author: Olivier Beaumont, Paul Renaud-Goud, Pierre Pesneau, Lionel Eyraud-Dubois, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Reformulations based algorithms for Combinatorial Optimization (Realopt), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Institut de Mathématiques de Bordeaux (IMB), Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Labex CPU, ANR-11-INFR-0013,SONGS,Simulation de systèmes de prochaine génération(2011), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Institut de Mathématiques de Bordeaux (IMB), Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Inria Bordeaux - Sud-Ouest, Beaumont, Olivier, and Infrastructures matérielles et logicielles pour la société numérique - Simulation de systèmes de prochaine génération - - SONGS2011 - ANR-11-INFR-0013 - INFRA - VALID
Subjects: Service (business), 020203 distributed computing, Computer science, business.industry, Distributed computing, Reliability (computer networking), Context (computing), Cloud computing, 0102 computer and information sciences, 02 engineering and technology, computer.software_genre, 01 natural sciences, Service-level agreement, 010201 computation theory & mathematics, Virtual machine, 0202 electrical engineering, electronic engineering, information engineering, [INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Heuristics, business, computer, Computer network
Abstract: International audience; We consider allocation problems that arise in the context of service allocation in Clouds. More specifically, on the one part we assume that each Physical Machine (denoted as PM) is offering resources (memory, CPU, disk, network). On the other part, we assume that each application in the IaaS Cloud comes as a set of services running as Virtual Machines (VMs) on top of the set of PMs. In turn, each service requires a given quantity of each resource on each machine where it runs (memory footprint, CPU, disk, network). Moreover, there exists a Service Level Agreement (SLA) between the Cloud provider and the client that can be expressed as follows: the client requires a minimal number of service instances which must be alive at the end of the day, with a given reliability (that can be converted into penalties paid by the provider). In this context, the goal for the Cloud provider is to find an allocation of VMs onto PMs so as to satisfy, at minimal cost, both capacity and reliability constraints for each service. In this paper, we propose a simple model for reliability constraints and we prove that it is possible to derive efficient heuristics.
Published: 2013

40. Splittable Single Source-Sink Routing on CMP Grids: A Sublinear Number of Paths Suffice

Author: Adrian Kosowski, Przemyslaw Uznanski, Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, and Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)
Subjects: Sublinear function, Computer science, Node (networking), [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 020206 networking & telecommunications, 02 engineering and technology, Parallel computing, Network topology, Grid, 020202 computer hardware & architecture, Transmission (telecommunications), 0202 electrical engineering, electronic engineering, information engineering, Routing (electronic design automation), Constant (mathematics)
Abstract: International audience; In single chip multiprocessors (CMP) with grid topologies, a significant part of power consumption is attributed to communications between the cores of the grid. We investigate the problem of routing communications between CMP cores using shortest paths, in a model in which the power cost associated with activating a communication link at a transmission speed of $f$ bytes/second is proportional to $f^\alpha$, for some constant exponent $\alpha > 2$. Our main result is a trade-off showing how the power required for communication in CMP grids depends on the ability to split communication requests between a given pair of node, routing each such request along multiple paths. For a pair of cores in a $m \times n$ grid, the number of available communication paths between them grows exponentially with $n,m$. By contrast, we show that optimal power consumption (up to constant factors) can be achieved by splitting each communication request into $k$ paths, starting from a threshold value of $k = \Theta (n^{1/\left(\alpha-1\right)})$. This threshold is much smaller than $n$ for typical values of $\alpha \approx 3$, and may be considered practically feasible for use in routing schemes on the grid. More generally, we provide efficient algorithms for routing multiple $k$-splittable communication requests between two cores in the grid, providing solutions within a constant approximation of the optimum cost. We support our results with algorithm simulations, showing that for practical instances, our approach using $k$-splittable requests leads to a power cost close to that of the optimal solution with arbitrarily splittable requests, starting from the stated threshold value of $k$.
Published: 2013

41. Efficient Exploration of Anonymous Undirected Graphs

Author: Ralf Klasing, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), ANR-11-BS02-0014,DISPLEXITY,Calculabilité et complexité en distribué(2011), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), and Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest
Subjects: Focus (computing), Theoretical computer science, 010201 computation theory & mathematics, 0202 electrical engineering, electronic engineering, information engineering, Robot, 020206 networking & telecommunications, 0102 computer and information sciences, 02 engineering and technology, Enhanced Data Rates for GSM Evolution, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Undirected graph, 01 natural sciences, Mathematics
Abstract: International audience; We consider the problem of exploring an anonymous undirected graph using an oblivious robot. The studied exploration strategies are designed so that the next edge in the robot's walk is chosen using only local information. In this paper, we present some current developments in the area. In particular, we focus on recent work on equitable strategies and on the multi-agent rotor-router.
Published: 2013

42. Exploration of the T-Interval-Connected Dynamic Graphs: the Case of the Ring

Author: David Ilcinkas, Ahmed Mouhamadou Wade, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Combinatoire et Algorithmique, Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), See paper for details., ANR-11-BS02-0014,DISPLEXITY,Calculabilité et complexité en distribué(2011), Ilcinkas, David, BLANC - Calculabilité et complexité en distribué - - DISPLEXITY2011 - ANR-11-BS02-0014 - BLANC - VALID, Ecole polytechnique de Thiès, Ecole Polytechnique de Thiès, ANR-13-JS02-0002,MACARON,Bouger et Calculer: Agents, Robots et Réseaux(2013), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, and Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)
Subjects: [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, 02 engineering and technology, Exploration problem, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Stability (probability), Theoretical Computer Science, Combinatorics, 0202 electrical engineering, electronic engineering, information engineering, Connection (algebraic framework), Time complexity, Mathematics, Dynamic graphs, Discrete mathematics, Mobile agent, Ring (mathematics), Unit of time, 020206 networking & telecommunications, T-interval-connectivity, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], Computational Theory and Mathematics, 010201 computation theory & mathematics, Theory of computation, Interval (graph theory), 020201 artificial intelligence & image processing, Exploration, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Focus (optics)
Abstract: In this paper, we study the T-interval-connected dynamic graphs from the point of view of the time necessary and sufficient for their exploration by a mobile entity (agent). A dynamic graph (more precisely, an evolving graph) is T-interval-connected (T ≥ 1) if, for every window of T consecutive time steps, there exists a connected spanning subgraph that is stable (always present) during this period. This property of connection stability over time was introduced by Kuhn, Lynch and Oshman (Kuhn et al. 14) (STOC 2010). We focus on the case when the underlying graph is a ring of size n, and we show that the worst-case time complexity for the exploration problem is 2n − T − Θ(1) time units if the agent knows the dynamics of the graph, and $n+ \frac {n}{\max \{1, T-1\} } (\delta -1) \pm {\Theta }(\delta )$ time units otherwise, where δ is the maximum time between two successive appearances of an edge.
Published: 2013

43. Asymptotic Analysis and Random Sampling of Digitally Convex Polyominoes

Author: Bodini, Olivier, Jacquot, Alice, Duchon, Philippe, Mutafchiev, Ljuben R., Laboratoire d'Informatique de Paris-Nord (LIPN), Université Sorbonne Paris Cité (USPC)-Institut Galilée-Université Paris 13 (UP13)-Centre National de la Recherche Scientifique (CNRS), CALIN, Université Sorbonne Paris Cité (USPC)-Institut Galilée-Université Paris 13 (UP13)-Centre National de la Recherche Scientifique (CNRS)-Université Sorbonne Paris Cité (USPC)-Institut Galilée-Université Paris 13 (UP13)-Centre National de la Recherche Scientifique (CNRS), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Université Paris 13 (UP13)-Institut Galilée-Université Sorbonne Paris Cité (USPC)-Centre National de la Recherche Scientifique (CNRS), Université Paris 13 (UP13)-Institut Galilée-Université Sorbonne Paris Cité (USPC)-Centre National de la Recherche Scientifique (CNRS)-Université Paris 13 (UP13)-Institut Galilée-Université Sorbonne Paris Cité (USPC)-Centre National de la Recherche Scientifique (CNRS), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), and Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest
Subjects: FOS: Computer and information sciences, Mathematics::Combinatorics, Discrete Mathematics (cs.DM), Computer Science::Computational Geometry, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Computer Science::Formal Languages and Automata Theory, Computer Science - Discrete Mathematics
Abstract: International audience; Recent work of Brlek \textit{et al.} gives a characterization of digitally convex polyominoes using combinatorics on words. From this work, we derive a combinatorial symbolic description of digitally convex polyominoes and use it to analyze their limit properties and build a uniform sampler. Experimentally, our sampler shows a limit shape for large digitally convex polyominoes.
Published: 2013

44. k-Selection Protocols from Energetic Complexity Perspective

Author: Marek Klonowski, Dominik Pajak, Kamil Wolny, Marcin Kardas, Institute of Mathematics and Computer Science [Wroclaw] (IMCS), Wroclaw University of Science and Technology, Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, and Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)
Subjects: Protocol (science), Exclusive access, Selection (relational algebra), Computational complexity theory, Computer science, Distributed computing, Perspective (graphical), 020206 networking & telecommunications, 0102 computer and information sciences, 02 engineering and technology, Energy consumption, Channel models, 01 natural sciences, Upper and lower bounds, Hop (networking), Radio networks, 010201 computation theory & mathematics, 0202 electrical engineering, electronic engineering, information engineering, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Time complexity
Abstract: In this paper we discuss energetic complexity aspects of k -Selection protocols for a single- hop radio network (that is equivalent to Multiple Access Channel model). The aim is to grant each of k activated stations exclusive access to the communication channel. We consider both deterministic as well as randomized model. Our main goal is to investigate relations between minimal time of execution (time complexity) and energy consumption (energetic complexity). We present lower bound for energetic complexity for some classes of protocols for k -Selection (both deteministic and randomized). We also present and analyse several randomized protocols efficient in terms of both time and energetic complexity.Â
Published: 2013

45. Algorithme distribué de routage compact en temps optimal

Author: Gavoille, Cyril, Glacet, Christian, Hanusse, Nicolas, Ilcinkas, David, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Combinatoire et Algorithmique, Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Nisse, Nicolas and Rousseau, Franck and Busnel, Yann, ANR-11-BS02-0014,DISPLEXITY,Calculabilité et complexité en distribué(2011), European Project: 258307,EC:FP7:ICT,FP7-ICT-2009-5,EULER(2010), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Glacet, Christian, BLANC - Calculabilité et complexité en distribué - - DISPLEXITY2011 - ANR-11-BS02-0014 - BLANC - VALID, Experimental UpdateLess Evolutive Routing - EULER - - EC:FP7:ICT2010-10-01 - 2014-06-30 - 258307 - VALID, and Nisse, Nicolas and Rousseau, Franck and Busnel, Yann
Subjects: distribué, optimal, compact routing, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], routage compact
Abstract: International audience; Nous présentons un algorithme distribué construisant des tables de routage de taille sous-linéaire en n, le nombre de nœuds du réseau. Le temps de convergence est proportionnel au diamètre, ce qui est optimal. Par rapport à BGP, la complexité du nombre de messages échangés est améliorée jusqu'à un facteur n^1/2, alors que la longueur des routes induites par les tables est allongée d'un facteur garanti constant. Notre algorithme est conçu pour un environnement statique synchrone ou asynchrone et produit un schéma name-independent.
Published: 2013

46. Optimizing Resource allocation while handling SLA violations in Cloud Computing platforms

Author: Hubert Larchevêque, Lionel Eyraud-Dubois, Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), ANR-11-INFR-0013,SONGS,Simulation de systèmes de prochaine génération(2011), Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, and Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)
Subjects: Computer science, Distributed computing, resource allocation, Cloud computing, 0102 computer and information sciences, 02 engineering and technology, computer.software_genre, 01 natural sciences, Robustness (computer science), 020204 information systems, 0202 electrical engineering, electronic engineering, information engineering, Resource management, Online algorithm, server consolidation, business.industry, Bin packing problem, cloud computing, Approximation algorithm, 010201 computation theory & mathematics, Virtual machine, Resource allocation, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], business, computer, Resource utilization, Computer network
Abstract: International audience; In this paper we study a resource allocation problem in the context of Cloud Computing, where a set of Virtual Machines (VM) has to be placed on a set of Physical Machines (PM). Each VM has a given demand (e.g. CPU demand), and each PM has a capacity. However, each VM only uses a fraction of its demand. The aim is to exploit the difference between the demand of the VM and its real utilization of the resources, to exploit the capacities of the PMs as much as possible. Moreover, the real consumption of the VMs can change over time (while staying under its original demand), implying sometimes expensive ''SLA violations'', corresponding to some VM's consumption not satisfied because of overloaded PMs. Thus, while optimizing the global resource utilization of the PMs, it is necessary to ensure that at any moment a VM's need evolves, a few number of migrations (moving a VM from PM to PM) is sufficient to find a new configuration in which all the VMs' consumptions are satisfied. We modelize this problem using a fully dynamic bin packing approach and we present an algorithm ensuring a global utilization of the resources of 66%. Moreover, each time a PM is overloaded at most one migration is necessary to fall back in a configuration with no overloaded PM, and only 3 different PMs are concerned by required migrations that may occur to keep the global resource utilization correct. This allows the platform to be highly resilient to a great number of changes.
Published: 2013

47. Reliable Service Allocation in Clouds

Author: Olivier Beaumont, Hubert Larchevêque, Lionel Eyraud-Dubois, Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), ANR-11-INFR-0013,SONGS,Simulation de systèmes de prochaine génération(2011), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, and Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)
Subjects: [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], Service (business), Reliability theory, Computer science, business.industry, Distributed computing, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Approximation algorithm, Cloud computing, 0102 computer and information sciences, 02 engineering and technology, computer.software_genre, 01 natural sciences, Service-level agreement, 010201 computation theory & mathematics, Virtual machine, 0202 electrical engineering, electronic engineering, information engineering, Resource allocation, 020201 artificial intelligence & image processing, Resource management, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], business, computer
Abstract: International audience; We consider several reliability problems that arise when allocating applications to processing resources in a Cloud computing platform. More specifically, we assume on the one hand that each computing resource is associated to a capacity constraint and to a probability of failure. On the other hand, we assume that each service runs as a set of independent instances of identical Virtual Machines, and that the Service Level Agreement between the Cloud provider and the client states that a minimal number of instances of the service should run with a given probability. In this context, given the capacity and failure probabilities of the machines, and the capacity and reliability demands of the services, the question for the cloud provider is to find an allocation of the instances of the services (possibly using replication) onto machines satisfying all types of constraints during a given time period. In this paper, our goal is to assess the impact of the reliability constraint on the complexity of resource allocation problems. We consider several variants of this problem, depending on the number of services and whether their reliability demand is individual or global. We prove several fundamental complexity results ($\#$P' and NP-completeness results) and we provide several optimal and approximation algorithms. In particular, we prove that a basic randomized allocation algorithm, that is easy to implement, provides optimal or quasi-optimal results in several contexts, and we show through simulations that it also achieves very good results in more general settings.
Published: 2013

48. Non Linear Divisible Loads: There is No Free Lunch

Author: Olivier Beaumont, Loris Marchal, Hubert Larchevêque, Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Optimisation des ressources : modèles, algorithmes et ordonnancement (ROMA), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon), Laboratoire de l'Informatique du Parallélisme (LIP), IEEE, Labex CPU, ANR-11-INFR-0013,SONGS,Simulation de systèmes de prochaine génération(2011), INRIA, Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS)
Subjects: 020203 distributed computing, 020301 aerospace & aeronautics, Divisible load theory, Computer science, Divisible Load Theory, Scheduling, Sorting, Processor scheduling, 02 engineering and technology, Parallel computing, Matrix multiplication, Scheduling (computing), Resource Allocation, Matrix Multiplica- tion, Nonlinear system, Quadratic equation, 0203 mechanical engineering, 0202 electrical engineering, electronic engineering, information engineering, No free lunch in search and optimization, Resource allocation, MapReduce, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
Abstract: accepted for publication in IPDPS 2013; International audience; Divisible Load Theory (DLT) has received a lot of attention in the past decade. A divisible load is a perfect parallel task, that can be split arbitrarily and executed in parallel on a set of possibly heterogeneous resources. The success of DLT is strongly related to the existence of many optimal resource allocation and scheduling algorithms, what strongly differs from general scheduling theory. Moreover, recently, close relationships have been underlined between DLT, that provides a fruitful theoretical framework for scheduling jobs on heterogeneous platforms, and \mapreduce, that provides a simple and efficient programming framework to deploy applications on large scale distributed platforms. The success of both have suggested to extend their framework to non-linear complexity tasks. In this paper, we show that both DLT and \mapreduce are better suited to workloads with linear complexity. In particular, we prove that divisible load theory cannot directly be applied to quadratic workloads, such as it has been proposed recently. We precisely state the limits for classical DLT studies and we review and propose solutions based on a careful preparation of the dataset and clever data partitioning algorithms. In particular, through simulations, we show the possible impact of this approach on the volume of communications generated by \mapreduce, in the context of Matrix Multiplication and Outer Product algorithms.; L'ordonnancement de tâches divisibles (DLT) a connu beaucoup de développements ces dernières années. Une tâche divisible est une tâche parfaitement parallélisable, qui peut être découpée en un nombre arbitraire de sous-tâches et exécutée en parallèle sur un ensemble de ressources potentiellement hétérogènes. Le succès de cette théorie vient de l'existence de nombreux algorithmes optimaux pour l'allocation et l'ordonnancement de ces tâches, au contraire des problèmes classiques d'ordonnancement qui sont habituellement NP-complets. De plus, on a récemment constaté la proximité de cette théorie, qui pose les bases théoriques de l'ordonnancement de tâches sur plates-formes hétérogènes, avec des solutions logicielles comme MapReduce, qui permettent de déployer des applications sur des plates-formes distribuées à grande échelle. Devant un tel succès, il a été proposé d'étendre ces solutions à des tâches dont la complexité en calcul n'est plus linéaire en la taille des données. Dans ce rapport, nous montrons que l'ordonnancement de tâches divisibles et MapReduce sont tous deux plus adaptés aux tâches de complexité linéaire. En particulier, nous montrons que l'ordonnancement de tâches divisibles ne peut être appliqué aux tâches de complexité quadratique, comme cela a été proposé récemment. Nous précisons les limites des résultats de cette théorie et pour les tâches non linéaires, nous proposes des solutions utilisant sur une préparation minutieuse des données et un partitionnement efficace du calcul. En particulier, par simulation, nous montrons l'impact de cette méthode sur le volume de communications généré par MapReduce sur des algorithmes de produit de matrices et de produit $u^T \times v$ de deux vecteurs.
Published: 2013

49. Quelques algorithmes entre le monde des graphes et les nuages de points

Author: Bonichon, Nicolas, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Université Sciences et Technologies - Bordeaux I, Robert Cori(cori@labri.fr), Bonichon, Nicolas, Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), and Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest
Subjects: combinatoire bijective, dessin de graphes, algorithmes d'approximations, permutations, spanners géométriques, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS]
Abstract: Quelques algorithmes entre le monde des graphes et les nuages de points.
Published: 2013

50. Worst-case optimal exploration of terrains with obstacles

Author: Arnaud Labourel, Jurek Czyzowicz, David Ilcinkas, Andrzej Pelc, Département d'Informatique et d'Ingénierie (DII), Université du Québec en Outaouais (UQO), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Combinatoire et Algorithmique, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'informatique Fondamentale de Marseille (LIF), Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), and Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU)
Subjects: Convex hull, Computer science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Terrain, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Theoretical Computer Science, Mobile robot, 0202 electrical engineering, electronic engineering, information engineering, Computer vision, ComputingMethodologies_COMPUTERGRAPHICS, business.industry, Obstacle, Polygon, Computer Science Applications, Computational Theory and Mathematics, 010201 computation theory & mathematics, Trajectory, Robot, 020201 artificial intelligence & image processing, Artificial intelligence, Exploration, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], business, Information Systems
Abstract: International audience; A mobile robot represented by a point moving in the plane has to explore an unknown flat terrain with impassable obstacles. Both the terrain and the obstacles are modeled as arbitrary polygons. We consider two scenarios: the unlimited vision, 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 limited vision, when we require additionally that the distance between p and q is at most 1. All points of the terrain (except obstacles) have to be explored and the performance of an exploration algorithm, called its complexity, is measured by the length of the trajectory of the robot. For unlimited vision we show an exploration algorithm with complexity View the MathML source, where P is the total perimeter of the terrain (including perimeters of obstacles), D is the diameter of the convex hull of the terrain, and k is the number of obstacles. We do not assume knowledge of these parameters. We also prove a matching lower bound showing that the above complexity is optimal, even if the terrain is known to the robot. For limited vision we show exploration algorithms with complexity View the MathML source, where A is the area of the terrain (excluding obstacles). Our algorithms work either for arbitrary terrains (if one of the parameters A or k is known) or for c-fat terrains, where c is any constant (unknown to the robot) and no additional knowledge is assumed. (A terrain T with obstacles is c-fat if R/r⩽c, where R is the radius of the smallest disc containing T and r is the radius of the largest disc contained in T.) We also prove a matching lower bound View the MathML source on the complexity of exploration for limited vision, even if the terrain is known to the robot.
Published: 2013

Catalog

Books, media, physical & digital resources

See catalog results

Searchworks

Select search scope, currently: Articles Catalog books, media & more in Jio Institute collections Articles journal articles & other e-resources

Search

Search Constraints

Refine your results

Search Limiters

Topic

Publication Year Range

Language

Journal

Database

Publisher

400 results on '"Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest"'

Search Results

Catalog

Select search scope, currently: Articles

Catalog

books, media & more in Jio Institute collections

Articles

journal articles & other e-resources