169 results on '"Ilcinkas, David"'
Search Results
152. Fast Two-Robot Disk Evacuation with Wireless Communication
- Author
-
Lamprou, Ioannis, Martin, Russell, Schewe, Sven, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Gavoille, Cyril, editor, and Ilcinkas, David, editor
- Published
- 2016
- Full Text
- View/download PDF
153. On Composition and Implementation of Sequential Consistency
- Author
-
Perrin, Matthieu, Petrolia, Matoula, Mostéfaoui, Achour, Jard, Claude, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Gavoille, Cyril, editor, and Ilcinkas, David, editor
- Published
- 2016
- Full Text
- View/download PDF
154. Sublinear-Space Distance Labeling Using Hubs
- Author
-
Gawrychowski, Paweł, Kosowski, Adrian, Uznański, Przemysław, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Gavoille, Cyril, editor, and Ilcinkas, David, editor
- Published
- 2016
- Full Text
- View/download PDF
155. Opacity vs TMS2: Expectations and Reality
- Author
-
Hans, Sandeep, Hassan, Ahmed, Palmieri, Roberto, Peluso, Sebastiano, Ravindran, Binoy, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Gavoille, Cyril, editor, and Ilcinkas, David, editor
- Published
- 2016
- Full Text
- View/download PDF
156. Optimal Fair Computation
- Author
-
Guerraoui, Rachid, Wang, Jingjing, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Gavoille, Cyril, editor, and Ilcinkas, David, editor
- Published
- 2016
- Full Text
- View/download PDF
157. Certified Universal Gathering in for Oblivious Mobile Robots
- Author
-
Courtieu, Pierre, Rieg, Lionel, Tixeuil, Sébastien, Urbain, Xavier, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Gavoille, Cyril, editor, and Ilcinkas, David, editor
- Published
- 2016
- Full Text
- View/download PDF
158. Are Byzantine Failures Really Different from Crash Failures?
- Author
-
Imbs, Damien, Raynal, Michel, Stainer, Julien, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Gavoille, Cyril, editor, and Ilcinkas, David, editor
- Published
- 2016
- Full Text
- View/download PDF
159. Anonymity-Preserving Failure Detectors
- Author
-
Bouzid, Zohir, Travers, Corentin, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Gavoille, Cyril, editor, and Ilcinkas, David, editor
- Published
- 2016
- Full Text
- View/download PDF
160. Non-local Probes Do Not Help with Many Graph Problems
- Author
-
Göös, Mika, Hirvonen, Juho, Levi, Reut, Medina, Moti, Suomela, Jukka, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Gavoille, Cyril, editor, and Ilcinkas, David, editor
- Published
- 2016
- Full Text
- View/download PDF
161. Near-Optimal Low-Congestion Shortcuts on Bounded Parameter Graphs
- Author
-
Haeupler, Bernhard, Izumi, Taisuke, Zuzic, Goran, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Gavoille, Cyril, editor, and Ilcinkas, David, editor
- Published
- 2016
- Full Text
- View/download PDF
162. Distributed Construction of Purely Additive Spanners
- Author
-
Censor-Hillel, Keren, Kavitha, Telikepalli, Paz, Ami, Yehudayoff, Amir, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Gavoille, Cyril, editor, and Ilcinkas, David, editor
- Published
- 2016
- Full Text
- View/download PDF
163. 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
164. 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
165. Optimal Fair Computation
- Author
-
Rachid Guerraoui, Jingjing Wang, Gavoille, Cyril, and Ilcinkas, David
- Subjects
Scheme (programming language) ,Sequence ,message complexity ,Theoretical computer science ,Computation ,optimistic fair computation ,0102 computer and information sciences ,02 engineering and technology ,shortest permutation sequence ,Trusted third party ,01 natural sciences ,Permutation ,010201 computation theory & mathematics ,0202 electrical engineering, electronic engineering, information engineering ,Asynchronous network ,020201 artificial intelligence & image processing ,computer ,Mathematics ,computer.programming_language ,Computer Science::Cryptography and Security - Abstract
A computation scheme among n parties is fair if no party obtains the computation result unless all other \(n-1\) parties obtain the same result. A fair computation scheme is optimistic if n honest parties can obtain the computation result without resorting to a trusted third party. We prove, for the first time, a tight lower-bound on the message complexity of optimistic fair computation for n parties among which \(n-1\) can be malicious in an asynchronous network. We do so by relating the optimal message complexity of optimistic fair computation to the length of the shortest permutation sequence in combinatorics.
166. Calcul de plus courts chemins multicritères et problèmes géométriques connexes
- Author
-
LENTZ, Antonin, Hanusse, Nicolas, Ilcinkas, David, Bose, Prosenjit, Viennot, Laurent, Bonichon, Nicolas, Coudert, David, and Cohen, Johanne
- Subjects
Thêta-Graphes ,Multicritères ,Approximation ,Algorithmique des graphes ,Structures de données
167. Complexité de l'exploration par agent mobile des graphes dynamiques
- Author
-
WADE, Ahmed Mouhamadou, Klasing, Ralf, Ilcinkas, David, Godard, Emmanuel, Chaumette, Serge, Petit, Franck, and Schabanel, Nicolas
- Subjects
T-intervalle-connexité ,Graphe dynamique ,Exploration ,Agent mobile ,PV-graphe
168. Réduction d'ordre partiel pour les systèmes temporisés
- Author
-
RAJANBABU, Govind, Walukiewicz, Igor, Srivathsan, Balaguru, Herbreteau, Frédéric, Petrucci, Laure, Chatain, Thomas, Dal Zilio, Silvano, Ilcinkas, David, and Leroux, Jérôme
- Subjects
Réduction d’ordre partiel ,Abstractions ,Vérification ,Sémantique temporelle locale ,Explosion de l'espace d'état ,Automates temporisés
169. Routing algorithms : from communication cost reduction to network dynamics
- Author
-
Glacet, Christian, Hanusse, Nicolas, Ilcinkas, David, Coudert, David, Gavoille, Cyril, Tixeuil, Sébastien, Viennot, Laurent, and STAR, ABES
- Subjects
[INFO.INFO-OH] Computer Science [cs]/Other [cs.OH] ,Dynamique ,Communication asynchrone ,Graphe ,Calcul distribué ,Coût de communication ,Asynchronous communication ,Compact routing ,Routage compact ,Communication cost ,Distributed computing ,Graph ,Dynamics - Abstract
In order to respond to routing queries, the entities of the network, nammedrouters, require to have a knowledge concerning the topology of the network, thisknowledge is called routing table. The network is modeled by a graph in whichnodes represent routers and edges represent communication links between nodes.This thesis focuses on routing tables computation in a distributed model. In thismodel, computations are done by a set of process placed on nodes. Every processhas for objective to compute the routing table of the node on which he is placed.To perform this computation, processes have to communicate with each other. Inlarge scale network, in the case of a distributed computation, maintaining routingtables up to date can be costly in terms of communication. This thesis focuses mainlyon the problem of communication cost reduction. One of the solution we proposeis to reduce routing tables size which allow to reduce communication cost. In thecentralised model this strategy is well known under the name of compact routing.This thesis presents in particular a distributed compact routing algorithm that allowsto reduce significantly the communication costs in networks like Internet, i.e. theautonomous systems network and others networks that present scale-free properties.This thesis also contains an experimental study of several distributed compact routingalgorithms. Finally, some problems linked to network dynamicity are addressed.More precisely, the problem of network deconnexion during a shortest path treecomputation with auto-stabilisation guaranties, together with a study of the impactof several edges or nodes deletion on the state of the routing tables., Répondre à des requêtes de routage requiert que les entités du réseau, nommées routeurs, aient une connaissance à jour sur la topologie de celui-ci, cette connaissance est appelée table de routage. Le réseau est modélisé par un graphe dans lequel les noeuds représentent les routeurs, et les arêtes les liens de communication entre ceux ci.Cette thèse s’intéresse au calcul des tables de routage dans un modèle distribué.Dans ce modèle, les calculs sont effectués par un ensemble de processus placés sur les noeuds. Chaque processus a pour objectif de calculer la table de routage du noeud sur lequel il se trouve. Pour effectuer ce calcul les processus doivent communiquer entre eux. Dans des réseaux de grande taille, et dans le cadre d’un calcul distribué, le maintien à jour des tables de routage peut être coûteux en terme de communication. L’un des thèmes principaux abordés et celui de la réduction des coûts de communication lors de ce calcul. L’une des solutions apportées consisteà réduire la taille des tables de routage, permettant ainsi de réduire les coûts de communication. Cette stratégie classique dans le modèle centralisé est connue sous le nom de routage compact. Cette thèse présente notamment un algorithme de routage compact distribué permettant de réduire significativement les coûts de communication dans les réseaux tels que le réseau internet, i.e. le réseau des systèmes autonomes ainsi que dans des réseaux sans-échelle. Ce document contient également une étude expérimentale de différents algorithmes de routage compact distribués.Enfin, les problèmes liés à la dynamique du réseau sont également abordés. Plusprécisément le reste de l’étude porte sur un algorithme auto-stabilisant de calcul d’arbre de plus court chemin, ainsi que sur l’impact de la suppression de noeuds ou d’arêtes sur les tables de routage stockées aux routeurs.
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.