Author: "Networks, Graphs and Algorithms (GANG)" / Topic: 02 engineering and technology - Searchworks@Jio Institute Digital Library Search Results

Your search keyword '"Networks, Graphs and Algorithms (GANG)"' showing total 118 results

Start Over Author "Networks, Graphs and Algorithms (GANG)" Topic 02 engineering and technology

118 results on '"Networks, Graphs and Algorithms (GANG)"'

1. Decomposing a Graph into Shortest Paths with Bounded Eccentricity

Author: Laurent Viennot, Fabien de Montgolfier, Etienne Birmelé, Léo Planche, Mathématiques Appliquées Paris 5 (MAP5 - UMR 8145), Université Paris Descartes - Paris 5 (UPD5)-Institut National des Sciences Mathématiques et de leurs Interactions (INSMI)-Centre National de la Recherche Scientifique (CNRS), Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Networks, Graphs and Algorithms (GANG), 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), Laboratory of Information, Network and Communication Sciences (LINCS), Université Pierre et Marie Curie - Paris 6 (UPMC)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institut Mines-Télécom [Paris] (IMT), Institut Mines-Télécom [Paris] (IMT)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Pierre et Marie Curie - Paris 6 (UPMC), Planche, Léo, Mathématiques Appliquées à Paris 5 ( MAP5 - UMR 8145 ), Université Paris Descartes - Paris 5 ( UPD5 ) -Institut National des Sciences Mathématiques et de leurs Interactions-Centre National de la Recherche Scientifique ( CNRS ), Institut de Recherche en Informatique Fondamentale ( IRIF ), Université Paris Diderot - Paris 7 ( UPD7 ) -Centre National de la Recherche Scientifique ( CNRS ), Networks, Graphs and Algorithms ( GANG ), 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 ), Laboratory of Information, Network and Communication Sciences ( LINCS ), Université Pierre et Marie Curie - Paris 6 ( UPMC ) -Institut National de Recherche en Informatique et en Automatique ( Inria ) -Institut Mines-Télécom [Paris], MAP5 - Mathématiques Appliquées à Paris 5 (MAP5), Centre National de la Recherche Scientifique (CNRS) - Institut National des Sciences Mathématiques et de leurs Interactions - Université Paris Descartes - Paris 5 (UPD5), Institut de Recherche en Informatique Fondamentale (IRIF), 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) - 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), and Université Pierre et Marie Curie - Paris 6 (UPMC) - Institut National de Recherche en Informatique et en Automatique (Inria) - Institut Mines-Télécom [Paris]
Subjects: Graph center, Graph Clustering, BFS, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], ComputingMethodologies_IMAGEPROCESSINGANDCOMPUTERVISION, MESP, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], 02 engineering and technology, 0102 computer and information sciences, Strength of a graph, Graph Decomposition, 01 natural sciences, law.invention, Combinatorics, 03 medical and health sciences, 0302 clinical medicine, law, Line graph, 0202 electrical engineering, electronic engineering, information engineering, Discrete Mathematics and Combinatorics, [ INFO.INFO-DS ] Computer Science [cs]/Data Structures and Algorithms [cs.DS], Complement graph, Mathematics, Discrete mathematics, 000 Computer science, knowledge, general works, Applied Mathematics, Distance Labeling, 020207 software engineering, 16. Peace & justice, Tree decomposition, Butterfly graph, Modular decomposition, 010201 computation theory & mathematics, 030220 oncology & carcinogenesis, Computer Science, Null graph
Abstract: International audience; We introduce the problem of hub-laminar decomposition which generalizes that of computing a shortest path with minimum eccentricity (MESP). Intuitively, it consists in decomposing a graph into several paths that collectively have small eccentricity and meet only near their extremities. The problem is related to computing an isometric cycle with minimum eccentricity (MEIC). It is also linked to DNA reconstitution in the context of metagenomics in biology. We show that a graph having such a decomposition with long enough paths can be decomposed in polynomial time with approximated guaranties on the parameters of the decomposition. Moreover, such a decomposition with few paths allows to compute a compact representation of distances with additive distortion. We also show that having an isometric cycle with small eccentricity is related to the possibility of embedding the graph in a cycle with low distortion.
Published: 2017

2. Minimum Eccentricity Shortest Path Problem: an Approximation Algorithm and Relation with the k-Laminarity Problem

Author: Fabien de Montgolfier, Léo Planche, Etienne Birmelé, Mathématiques Appliquées Paris 5 (MAP5 - UMR 8145), Université Paris Descartes - Paris 5 (UPD5)-Institut National des Sciences Mathématiques et de leurs Interactions (INSMI)-Centre National de la Recherche Scientifique (CNRS), Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), MAC2 (Idex USPC), MAC2, Networks, Graphs and Algorithms (GANG), 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), Mathématiques Appliquées à Paris 5 ( MAP5 - UMR 8145 ), Université Paris Descartes - Paris 5 ( UPD5 ) -Institut National des Sciences Mathématiques et de leurs Interactions-Centre National de la Recherche Scientifique ( CNRS ), Institut de Recherche en Informatique Fondamentale ( IRIF ), Université Paris Diderot - Paris 7 ( UPD7 ) -Centre National de la Recherche Scientifique ( CNRS ), Networks, Graphs and Algorithms ( GANG ), 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, and Institut National de Recherche en Informatique et en Automatique ( Inria ) -Institut National de Recherche en Informatique et en Automatique ( Inria )
Subjects: FOS: Computer and information sciences, [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], k-Laminar Graph, BFS, Discrete Mathematics (cs.DM), [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, 02 engineering and technology, Computational Complexity (cs.CC), [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Graph search, 01 natural sciences, Eccentricity, Combinatorics, Diameter, 0202 electrical engineering, electronic engineering, information engineering, Yen's algorithm, [ INFO.INFO-DS ] Computer Science [cs]/Data Structures and Algorithms [cs.DS], Mathematics, Discrete mathematics, [ INFO.INFO-DM ] Computer Science [cs]/Discrete Mathematics [cs.DM], Longest path problem, Widest path problem, Graph theory, Computer Science - Computational Complexity, Euclidean shortest path, [ INFO.INFO-CC ] Computer Science [cs]/Computational Complexity [cs.CC], Shortest Path Faster Algorithm, 010201 computation theory & mathematics, Shortest path problem, 020201 artificial intelligence & image processing, K shortest path routing, Approximation Algorithms, Distance, Computer Science - Discrete Mathematics
Abstract: International audience; The Minimum Eccentricity Shortest Path (MESP) Problem consists in determining a shortest path (a path whose length is the distance between its extremities) of minimum eccentricity in a graph. It was introduced by Dragan and Leitert [9] who described a linear-time algorithm which is an 8-approximation of the problem. In this paper, we study deeper the double-BFS procedure used in that algorithm and extend it to obtain a linear-time 3-approximation algorithm. We moreover study the link between the MESP problem and the notion of laminarity, introduced by Völkel et al [12], corresponding to its restriction to a diameter (i.e. a shortest path of maximum length), and show tight bounds between MESP and laminarity parameters.
Published: 2016

3. New Encodings of Pseudo-Boolean Constraints into CNF

Author: Olivier Roussel, Yacine Boufkhad, Olivier Bailleux, Laboratoire Informatique de Recherche sur les Systèmes Intelligents et leurs Applications (LIRSIA), Université de Bourgogne (UB), 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), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Centre de Recherche en Informatique de Lens (CRIL), Université d'Artois (UA)-Centre National de la Recherche Scientifique (CNRS), Boufkhad, Yacine, Laboratoire Informatique de Recherche sur les Systèmes Intelligents et leurs Applications ( LIRSIA ), Université de Bourgogne ( UB ), 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 ), Université Paris Diderot - Paris 7 ( UPD7 ) -Centre National de la Recherche Scientifique ( CNRS ), Centre de Recherche en Informatique de Lens ( CRIL ), and Université d'Artois ( UA ) -Centre National de la Recherche Scientifique ( CNRS )
Subjects: Discrete mathematics, [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], Polynomial, 021103 operations research, Unit propagation, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0211 other engineering and technologies, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], 02 engineering and technology, Computer Science::Computational Complexity, Expressive power, Exponential function, Combinatorics, [ INFO.INFO-CC ] Computer Science [cs]/Computational Complexity [cs.CC], Encoding (memory), 0202 electrical engineering, electronic engineering, information engineering, Local consistency, 020201 artificial intelligence & image processing, Point (geometry), [INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC], [ INFO.INFO-DS ] Computer Science [cs]/Data Structures and Algorithms [cs.DS], Mathematics
Abstract: International audience; This paper answers affirmatively the open question of the existence of a polynomial size CNF encoding of pseudo-Boolean (PB) constraints such that generalized arc consistency (GAC) is maintained through unit propagation (UP). All previous encodings of PB constraints either did not allow UP to maintain GAC, or were of exponential size in the worst case. This paper presents an encoding that realizes both of the desired properties. From a theoretical point of view, this narrows the gap between the expressive power of clauses and the one of pseudo-Boolean constraints.
Published: 2009

4. Redundancy in distributed proofs

Author: Ami Paz, Mor Perry, Laurent Feuilloley, Juho Hirvonen, Pierre Fraigniaud, Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Networks, Graphs and Algorithms (GANG), 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), Tel Aviv University (TAU), Universidad de Chile, Institut de Recherche en Informatique Fondamentale, Department of Computer Science, University of Vienna, Weizmann Institute of Science, Aalto-yliopisto, Aalto University, Tel Aviv University [Tel Aviv], Schmid, Ulrich, Hirvonen, Juho, Professorship Suomela J., and Tel Aviv University
Subjects: FOS: Computer and information sciences, Theoretical computer science, Correctness, Proof-labeling schemes, Computer Networks and Communications, Computer science, 0102 computer and information sciences, 02 engineering and technology, Gas meter prover, Mathematical proof, 01 natural sciences, Article, Theoretical Computer Science, 0202 electrical engineering, electronic engineering, information engineering, Redundancy (engineering), Nondeterminism, non-determinism, ta113, 000 Computer science, knowledge, general works, Spanning tree, Node (networking), Distributed verification, 020206 networking & telecommunications, Certificate, Space-time tradeoffs, Computer Science - Distributed, Parallel, and Cluster Computing, Computational Theory and Mathematics, 010201 computation theory & mathematics, Hardware and Architecture, Distributed algorithm, Distributed graph algorithms, Computer Science, Distributed, Parallel, and Cluster Computing (cs.DC), [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
Abstract: Distributed proofs are mechanisms enabling the nodes of a network to collectivity and efficiently check the correctness of Boolean predicates on the structure of the network, or on data-structures distributed over the nodes (e.g., spanning trees or routing tables). We consider mechanisms consisting of two components: a \emph{prover} assigning a \emph{certificate} to each node, and a distributed algorithm called \emph{verifier} that is in charge of verifying the distributed proof formed by the collection of all certificates. In this paper, we show that many network predicates have distributed proofs offering a high level of redundancy, explicitly or implicitly. We use this remarkable property of distributed proofs for establishing perfect tradeoffs between the \emph{size of the certificate} stored at every node, and the \emph{number of rounds} of the verification protocol. If we allow every node to communicate to distance at most $t$, one might expect that the certificate sizes can be reduced by a multiplicative factor of at least~$t$. In trees, cycles and grids, we show that such tradeoffs can be established for \emph{all} network predicates, i.e., it is always possible to linearly decrease the certificate size. In arbitrary graphs, we show that any part of the certificates common to all nodes can be evenly redistributed among these nodes, achieving even a better tradeoff: this common part of the certificate can be reduced by the size of a smallest ball of radius $t$ in the network. In addition to these general results, we establish several upper and lower bounds on the certificate sizes used for distributed proofs for spanning trees, minimum-weight spanning trees, diameter, additive and multiplicative spanners, and more, improving and generalizing previous results from the literature.
Published: 2020

5. On the weakest information on failures to solve mutual exclusion and consensus in asynchronous crash-prone read/write systems

Author: Hugues Fauconnier, Michel Raynal, Carole Delporte-Gallet, Networks, Graphs and Algorithms (GANG), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP)-Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP), the World Is Distributed Exploring the tension between scale and coordination (WIDE), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-SYSTÈMES LARGE ÉCHELLE (IRISA-D1), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes 1 (UR1), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), ANR-16-CE40-0023,DESCARTES,Abstraction modulaire pour le calcul distribué(2016), Université de Bretagne Sud (UBS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-CentraleSupélec-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Bretagne Sud (UBS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), and Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1)
Subjects: Theoretical computer science, Asynchronous system, Computer Networks and Communications, Process (engineering), Computer science, Message passing, 020206 networking & telecommunications, 02 engineering and technology, Theoretical Computer Science, Artificial Intelligence, Hardware and Architecture, Asynchronous communication, 0202 electrical engineering, electronic engineering, information engineering, A priori and a posteriori, 020201 artificial intelligence & image processing, Mutual exclusion, Impossibility, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Semaphore, Software, ComputingMilieux_MISCELLANEOUS
Abstract: Mutual exclusion and consensus are among the most important coordination problems encountered in asynchronous concurrent systems, whether processes communicate using read/write registers or message passing. Unfortunately, neither can be solved in crash-prone systems, as soon as even a single process may crash. Hence, an important question: which is the weakest information on failures that must be given to the processes so that these problems can be solved whatever the number of crashes. This approach to circumvent impossibility results is known under the name failure detectors. Considering mutual exclusion and consensus in a crash-prone asynchronous system where the processes communicate through read/write registers, this article answers the previous question by presenting two failure detectors. The first, called Quasi-Perfect (QP) allows mutual exclusion to be solved in the presence of any number of process crashes. The second, called Ω ⁎ , allows consensus to be solved in the general model where not all but an a priori unknown subset of processes participates in consensus. In addition to algorithms solving each of the previous problems with the help of the associated failure detector, the article shows that QP and Ω ⁎ provides the weakest information on failures needed to solve mutex exclusion and participant-restricted consensus respectively.
Published: 2021

6. Simple and Fast Distributed Computation of Betweenness Centrality

Author: Ami Paz, Pierluigi Crescenzi, Pierre Fraigniaud, Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP), Networks, Graphs and Algorithms (GANG), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP)-Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP), Fraigniaud, Pierre, 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)-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), Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité), and Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité)
Subjects: Routing protocol, Social and Information Networks (cs.SI), FOS: Computer and information sciences, Theoretical computer science, Computer science, Computation, [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], Computer Science - Social and Information Networks, 02 engineering and technology, Network topology, Graph, Betweenness centrality, Computer Science - Distributed, Parallel, and Cluster Computing, Distributed algorithm, Convergence (routing), 0202 electrical engineering, electronic engineering, information engineering, [INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Graph (abstract data type), 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], ComputingMilieux_MISCELLANEOUS, Network analysis
Abstract: Betweenness centrality is a graph parameter that has been successfully applied to network analysis. In the context of computer networks, it was considered for various objectives, ranging from routing to service placement. However, as observed by Maccari et al. [INFOCOM 2018], research on betweenness centrality for improving protocols was hampered by the lack of a usable, fully distributed algorithm for computing this parameter. We resolve this issue by designing an efficient algorithm for computing betweenness centrality, which can be implemented by minimal modifications to any distance-vector routing protocol based on Bellman-Ford. The convergence time of our implementation is shown to be proportional to the diameter of the network.
Published: 2020

7. Randomized proof-labeling schemes

Author: Boaz Patt-Shamir, Mor Baruch, Pierre Fraigniaud, Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP), Tel Aviv University (TAU), Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Networks, Graphs and Algorithms (GANG), 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), 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, Department of Electrical Engineering, and Tel Aviv University [Tel Aviv]
Subjects: Scheme (programming language), Correctness, Theoretical computer science, Proof-labeling schemes, Computer Networks and Communications, 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, Upper and lower bounds, Non-determinism, Theoretical Computer Science, 0202 electrical engineering, electronic engineering, information engineering, Communication complexity, ComputingMilieux_MISCELLANEOUS, computer.programming_language, Randomized algorithms, Probabilistic logic, Distributed verification, 020206 networking & telecommunications, Predicate (mathematical logic), Randomized algorithm, Computational Theory and Mathematics, 010201 computation theory & mathematics, Hardware and Architecture, Distributed algorithm, Theory of computation, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], computer, Algorithm
Abstract: International audience; A proof-labeling scheme, introduced by Korman, Kutten and Peleg [PODC 2005], is a mechanism enabling to certify the legality of a network configuration with respect to a boolean predicate. Such a mechanism finds applications in many frameworks, including the design of fault-tolerant distributed algorithms. In a proof-labeling scheme, the verification phase consists of exchanging labels between neighbors. The size of these labels depends on the network predicate to be checked. There are predicates requiring large labels, of poly-logarithmic size (e.g., MST), or even polynomial size (e.g., Symmetry). In this paper, we introduce the notion of randomized proof-labeling schemes. By reduction from deterministic schemes, we show that randomization enables the amount of communication to be exponentially reduced. As a consequence, we show that checking any network predicate can be done with probability of correctness as close to one as desired by exchanging just a logarithmic number of bits between neighbors. Moreover, we design a novel space lower bound technique that applies to both deterministic and randomized proof-labeling schemes. Using this technique, we establish several tight bounds on the verification complexity of classical distributed computing problems, such as MST construction, and of classical predicates such as acyclicity, connectivity, and cycle length.
Published: 2018

8. Brief Announcement: Distributed Computing in the Asynchronous {LOCAL} Model

Author: Pierre Fraigniaud, Hugues Fauconnier, Mikaël Rabie, Carole Delporte-Gallet, Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Networks, Graphs and Algorithms (GANG), 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), and This research is supported by the ANR project DESCARTES (ref. DS0702-2016). Additional support from the INRIA project GANG.
Subjects: Discrete mathematics, TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES, Deterministic algorithm, Computer science, [SCCO.COMP]Cognitive science/Computer science, 0102 computer and information sciences, 02 engineering and technology, Computer Science::Computational Complexity, 01 natural sciences, Task (project management), TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES, 010201 computation theory & mathematics, Asynchronous communication, TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY, 020204 information systems, 0202 electrical engineering, electronic engineering, information engineering, ComputingMilieux_MISCELLANEOUS, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract: International audience; We show that, for any task T associated to a locally checkable labeling (lcl), if T is solvable in t rounds by a deterministic algorithm in the local model, then T remains solvable by a deterministic algorithm in O(t) rounds in an asynchronous variant of the local model whenever t=O(polylogn).
Published: 2019

9. Synchronous t-Resilient Consensus in Arbitrary Graphs

Author: Armando Castañeda, Pierre Fraigniaud, Matthieu Roy, Sergio Rajsbaum, Ami Paz, Corentin Travers, Technion - Israel Institute of Technology [Haifa], 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), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Instituto de Matematicas [México], Universidad Nacional Autónoma de México (UNAM), Équipe Tolérance aux fautes et Sûreté de Fonctionnement informatique (LAAS-TSF), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, Universidad Politécnica de Madrid (UPM), Supported by ANR Project DESCARTES, INRIA Project GANG, UNAM-PAPIIT IA102417 and IN109917, and Fondation des Sciences Mathématiques de Paris., ANR-16-CE40-0023,DESCARTES,Abstraction modulaire pour le calcul distribué(2016), Universidad Nacional Autónoma de México = National Autonomous University of Mexico (UNAM), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse 1 Capitole (UT1)-Université Toulouse - Jean Jaurès (UT2J)-Institut National Polytechnique (Toulouse) (Toulouse INP), and Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse 1 Capitole (UT1)-Université Toulouse - Jean Jaurès (UT2J)
Subjects: Discrete mathematics, Consensus, Computer science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Complete graph, Crash, Combinatorial topology, 0102 computer and information sciences, 02 engineering and technology, Radius, 01 natural sciences, Upper and lower bounds, Computer Science Applications, Theoretical Computer Science, Synchronous network, Computational Theory and Mathematics, 010201 computation theory & mathematics, Distributed graph algorithms, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Crash failures, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Information Systems
Abstract: Best Paper Award; International audience; We study the number of rounds needed to solve consensus in a synchronous network G where at most t nodes may fail by crashing. This problem has been thoroughly studied when G is a complete graph, but very little is known when G is arbitrary. We define a notion of radius that considers all ways in which t nodes may crash, and present an algorithm that solves consensus in radius rounds. Then we derive a lower bound showing that our algorithm is optimal for vertex-transitive graphs, among oblivious algorithms.
Published: 2019

10. Participant-Restricted Consensus in Asynchronous Crash-Prone Read/Write Systems and Its Weakest Failure Detector

Author: Michel Raynal, Hugues Fauconnier, Carole Delporte-Gallet, Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Networks, Graphs and Algorithms (GANG), 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), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Bretagne Sud (UBS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-CentraleSupélec-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), The Hong Kong Polytechnic University [Hong Kong] (POLYU), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), and Delporte-Gallet, Carole
Subjects: 050101 languages & linguistics, Asynchronous system, Computer science, Concurrency, 05 social sciences, Detector, [SCCO.COMP]Cognitive science/Computer science, Crash, 02 engineering and technology, Object (computer science), Computer engineering, [SCCO.COMP] Cognitive science/Computer science, Asynchronous communication, Models of communication, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, 0501 psychology and cognitive sciences, Failure detector, ComputingMilieux_MISCELLANEOUS
Abstract: A failure detector is a device (object) that provides the processes with information on failures. Failure detectors were introduced to enrich asynchronous systems so that it becomes possible to solve problems (or implement concurrent objects) that are otherwise impossible to solve in pure asynchronous systems where processes are prone to crash failures. The most famous failure detector (which is called “eventual leader” and denoted $\varOmega $) is the weakest failure detector which allows consensus to be solved in n-process asynchronous systems where up to $t=n-1$ processes may crash in the read/write communication model, and up to \(t
Published: 2019

11. On the Minimum Eccentricity Isometric Cycle Problem

Author: Léo Planche, Etienne Birmelé, Fabien de Montgolfier, Mathématiques Appliquées Paris 5 (MAP5 - UMR 8145), Université Paris Descartes - Paris 5 (UPD5)-Institut National des Sciences Mathématiques et de leurs Interactions (INSMI)-Centre National de la Recherche Scientifique (CNRS), 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), and Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)
Subjects: General Computer Science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 020206 networking & telecommunications, 0102 computer and information sciences, 02 engineering and technology, Isometric exercise, k-domination, k-covering, 01 natural sciences, Graph, Isometric cycle, Theoretical Computer Science, Eccentricity, Combinatorics, 010201 computation theory & mathematics, 0202 electrical engineering, electronic engineering, information engineering, Astrophysics::Earth and Planetary Astrophysics, MathematicsofComputing_DISCRETEMATHEMATICS, Mathematics
Abstract: International audience; In this paper we investigate the Minimum Eccentricity Isometric Cycle (MEIC) problem. Given a graph, this problem consists in finding an isometric cycle with smallest possible eccentricity k. We show that this problem is NP-Hard and we propose a 3-approximation algorithm running in O(n(m + kn)) time.
Published: 2019

12. A General Algorithmic Scheme for Modular Decompositions of Hypergraphs and Applications

Author: Lalla Mouatadid, Fabien de Montgolfier, Mengchuan Zou, Michel Habib, Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Networks, Graphs and Algorithms (GANG), 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 Computer Science [University of Toronto] (DCS), and University of Toronto
Subjects: Discrete mathematics, Polynomial, business.industry, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, 02 engineering and technology, Modular design, 01 natural sciences, Modular decomposition, Orthogonality, 010201 computation theory & mathematics, Scheme (mathematics), 0202 electrical engineering, electronic engineering, information engineering, Decomposition (computer science), 020201 artificial intelligence & image processing, [INFO]Computer Science [cs], Focus (optics), business, Time complexity, ComputingMilieux_MISCELLANEOUS, MathematicsofComputing_DISCRETEMATHEMATICS, Mathematics
Abstract: We study here algorithmic aspects of modular decomposition of hypergraphs. In the literature one can find three different definitions of modules, namely: the standard one [19], the k-subset modules [6] and the Courcelle’s one [11]. Using the fundamental tools defined for combinatorial decompositions such as partitive and orthogonal families, we directly derive a linear time algorithm for Courcelle’s decomposition. Then we introduce a general algorithmic tool for partitive families and apply it for the other two definitions of modules to derive polynomial algorithms. For standard modules it leads to an algorithm in $O(n^3 \cdot l)$ time (where n is the number of vertices and l is the sum of the size of the edges). For k-subset modules we obtain $O(n^3\cdot m\cdot l)$ (where m is the number of edges). This is an improvement from the best known algorithms for k-subset modular decomposition, which was not polynomial w.r.t. n and m, and is in $O(n^{3k-5})$ time [6] where k denotes the maximal size of an edge. Finally we focus on applications of orthogonality to modular decompositions of tournaments, simplifying the algorithm from [18]. The question of designing a linear time algorithms for the standard modular decomposition of hypergraphs remains open.
Published: 2019

13. A Topological Perspective on Distributed Network Algorithms

Author: Ami Paz, Matthieu Roy, Sergio Rajsbaum, Pierre Fraigniaud, Armando Castañeda, Corentin Travers, Technion - Israel Institute of Technology [Haifa], Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Networks, Graphs and Algorithms (GANG), 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), Instituto de Matematicas [México], Universidad Nacional Autónoma de México (UNAM), Équipe Tolérance aux fautes et Sûreté de Fonctionnement informatique (LAAS-TSF), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, 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), Pierre Fraigniaud and Corentin Travers are supported by ANR projects DESCARTES and FREDA, Pierre Fraigniaud receives additional support from INRIA project GANG, Ami Paz is supported by the Fondation Sciences Mathématiques de Paris (FSMP), Sergio Rajsbaum is supported by project unam-papiit IN109917., Keren Censor-Hillel, Michele Flammini, ANR-16-CE40-0023,DESCARTES,Abstraction modulaire pour le calcul distribué(2016), Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP), Universidad Nacional Autónoma de México = National Autonomous University of Mexico (UNAM), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse 1 Capitole (UT1)-Université Toulouse - Jean Jaurès (UT2J)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse 1 Capitole (UT1)-Université Toulouse - Jean Jaurès (UT2J), and 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
Subjects: FOS: Computer and information sciences, Network algorithms, General Computer Science, Computer science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Structure (category theory), Combinatorial topology, 0102 computer and information sciences, 02 engineering and technology, Topology, 01 natural sciences, Theoretical Computer Science, 0202 electrical engineering, electronic engineering, information engineering, ComputingMilieux_MISCELLANEOUS, Message passing, Perspective (graphical), 020207 software engineering, 16. Peace & justice, Distributed computing, Shared memory, Computer Science - Distributed, Parallel, and Cluster Computing, Distributed algorithm, 010201 computation theory & mathematics, Distributed graph algorithms, 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]
Abstract: International audience; More than two decades ago, combinatorial topology was shown to be useful for analyzing distributed fault-tolerant algorithms in shared memory systems and in message passing systems. In this work, we show that combinatorial topology can also be useful for analyzing distributed algorithms in networks of arbitrary structure. To illustrate this, we analyze consensus, set-agreement, and approximate agreement in networks, and derive lower bounds for these problems under classical computational settings, such as the LOCAL model and dynamic networks.
Published: 2019

14. When an optimal dominating set with given constraints exists

Author: Narges Ghareghani, Mohammad Reza Hooshmandasl, Reza Naserasr, Omid Etesami, Pouyeh Sharifani, Michel Habib, Institute for Research in Fundamental Sciences [Tehran] (IPM), Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Networks, Graphs and Algorithms (GANG), 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), Yazd University, The research of the second author was in part supported by the grant 96050016 from IPM and the research of the third and fifth author was supported by grant number ANR-17-CE40-0022., ANR-17-CE40-0022,HOSIGRA,Homomorphismes de graphes signés(2017), and Institute for Research in Fundamental Sciences (IPM)
Subjects: General Computer Science, Total dominating set, Comparability, Permutation graphs, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Graph, Theoretical Computer Science, Vertex (geometry), Combinatorics, Dominating set, 010201 computation theory & mathematics, Chordal graph, Bounded function, 0202 electrical engineering, electronic engineering, information engineering, NP-hardness, Interval graphs, 020201 artificial intelligence & image processing, [INFO]Computer Science [cs], Mathematics
Abstract: A dominating set is a set S of vertices in a graph such that every vertex not in S is adjacent to a vertex in S. In this paper, we consider the set of all optimal (i.e. smallest) dominating sets S, and ask of the existence of at least one such set S with given constraints. The constraints say that the number of neighbors in S of a vertex inside S must be in a given set ρ, and the number of neighbors of a vertex outside S must be in a given set σ. For example, if ρ is [ 1 , k ] , and σ is the nonnegative integers, this corresponds to “ [ 1 , k ] -domination.” First, we consider the complexity of recognizing whether an optimal dominating set with given constraints exists or not. We show via two different reductions that this problem is NP-hard for certain given constraints. This, in particular, answers a question of [M. Chellali et al., [ 1 , 2 ] -dominating sets in graphs, Discrete Applied Mathematics 161 (2013) 2885–2893] regarding the constraint that the number of neighbors in the set be upper-bounded by 2. We also consider the corresponding question regarding “total” dominating sets. Next, we consider some well-structured classes of graphs, including permutation and interval graphs (and their subfamilies), and determine exactly the smallest k such that for all graphs in that family an optimal dominating set exists where every vertex is dominated at most k times. We also consider the problem for trees (with implications for chordal and comparability graphs) and graphs with bounded “asteroidal number”.
Published: 2019

15. Towards Synthesis of Distributed Algorithms with {SMT} Solvers

Author: Carole Delporte-Gallet, Yan Jurski, Arnaud Sangnier, François Laroussinie, Hugues Fauconnier, Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Networks, Graphs and Algorithms (GANG), 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), and Delporte-Gallet, Carole
Subjects: Correctness, Computer science, [SCCO.COMP]Cognitive science/Computer science, 020207 software engineering, Context (language use), 0102 computer and information sciences, 02 engineering and technology, Parallel computing, 01 natural sciences, [SCCO.COMP] Cognitive science/Computer science, 010201 computation theory & mathematics, Distributed algorithm, Satisfiability modulo theories, 0202 electrical engineering, electronic engineering, information engineering, Temporal logic, Finite state, Time complexity, ComputingMilieux_MISCELLANEOUS
Abstract: We consider the problem of synthesizing distributed algorithms working on a specific execution context. We show it is possible to use the linear time temporal logic in order to both specify the correctness of algorithms and their execution contexts. We then provide a method allowing to reduce the synthesis problem of finite state algorithms to some model-checking problems. We finally apply our technique to automatically generate algorithms for consensus and epsilon-agreement in the case of two processes using the SMT solver Z3.
Published: 2019

16. On the Weakest Failure Detector for Read/Write-Based Mutual Exclusion

Author: Michel Raynal, Hugues Fauconnier, Carole Delporte-Gallet, Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Networks, Graphs and Algorithms (GANG), 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), The Hong Kong Polytechnic University [Hong Kong] (POLYU), the World Is Distributed Exploring the tension between scale and coordination (WIDE), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-SYSTÈMES LARGE ÉCHELLE (IRISA-D1), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), Université de Bretagne Sud (UBS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-CentraleSupélec-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Bretagne Sud (UBS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes 1 (UR1), and Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique)
Subjects: Computer engineering, 010201 computation theory & mathematics, Asynchronous communication, Computer science, 0202 electrical engineering, electronic engineering, information engineering, [SCCO.COMP]Cognitive science/Computer science, 020201 artificial intelligence & image processing, 0102 computer and information sciences, 02 engineering and technology, Failure detector, Mutual exclusion, 01 natural sciences, ComputingMilieux_MISCELLANEOUS
Abstract: Failure detectors are devices (objects) that provides the processes with information on failures. They were introduced to enrich asynchronous systems so that it becomes possible to solve problems (or implement concurrent objects) that are otherwise impossible to solve in pure asynchronous systems where processes are prone to crash failures. The most famous failure detector (which is called “eventual leader” and denoted $\varOmega $) is the weakest failure detector which allows consensus to be solved in n-process asynchronous systems where up to $t=n-1$ processes may crash in the read/write communication model, and up to \(t
Published: 2019

17. Fast Public Transit Routing with Unrestricted Walking Through Hub Labeling

Author: Duc-Minh Phan, Laurent Viennot, Got It Vietnam, 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), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Laboratory of Information, Network and Communication Sciences (LINCS), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut Mines-Télécom [Paris] (IMT)-Sorbonne Université (SU), Université Paris Diderot - Paris 7 (UPD7), ANR-17-CE22-0016,MultiMod,Routage dans les grands réseaux de transports multi-modal(2017), and ANR-17-CE22-0016,MultiMod,Scalable routing in Multi-Modal transportation networks(2017)
Subjects: FOS: Computer and information sciences, Speedup, Computer science, Public transportation, 02 engineering and technology, Interval (mathematics), Route planning, Arrival time, Computer Science - Networking and Internet Architecture, Hub labeling, Contraction hierarchies, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], Computer Science - Data Structures and Algorithms, 0502 economics and business, 11. Sustainability, 0202 electrical engineering, electronic engineering, information engineering, Data Structures and Algorithms (cs.DS), Networking and Internet Architecture (cs.NI), 050210 logistics & transportation, business.industry, 05 social sciences, Walking time, Travel time, Public transport, 020201 artificial intelligence & image processing, Routing (electronic design automation), business, Computer network
Abstract: We propose a novel technique for answering routing queries in public transportation networks that allows unrestricted walking. We consider several types of queries: earliest arrival time, Pareto-optimal journeys regarding arrival time, number of transfers and walking time, and profile, i.e. finding all Pareto-optimal journeys regarding travel time and arrival time in a given time interval. Our techniques uses hub labeling to represent unlimited foot transfers and can be adapted to both classical algorithms RAPTOR and CSA. We obtain significant speedup compared to the state-of-the-art approach based on contraction hierarchies. A research report version is deposited on HAL with number hal-02161283.
Published: 2019

18. Diameter computation on $H$-minor free graphs and graphs of bounded (distance) VC-dimension

Author: Guillaume Ducoffe, Michel Habib, Laurent Viennot, National Institute for Research and Development in Informatics [Bucharest] (ICI), University of Bucharest (UniBuc), Université Paris Cité (UPCité), Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité), Networks, Graphs and Algorithms (GANG), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité), This work was supported by project PN 19 37 04 01 'New solutions for complex problems in current ICT researchfields based on modelling and optimization', funded by the Romanian Core Program of the Ministry of Researchand Innovation (MCI) 2019-2022. This work was also supported by a grant of Romanian Ministry of Research andInnovation CCCDI-UEFISCDI. project no. 17PCCDI/2018., ANR-17-CE40-0015,DISTANCIA,Théorie métrique des graphes(2017), ANR-17-CE22-0016,MultiMod,Routage dans les grands réseaux de transports multi-modal(2017), University of Bucharest, Faculty of Mathematics and Computer Science, National Institute for Research and Development in Informatics [Bucharest], Université de Paris, 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)-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), ANR-17-CE22-0016,MultiMod,Scalable routing in Multi-Modal transportation networks(2017), Université de Paris (UP), Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP), and Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP)-Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP)
Subjects: FOS: Computer and information sciences, 010201 computation theory & mathematics, Computer Science - Data Structures and Algorithms, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Data Structures and Algorithms (cs.DS), 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences
Abstract: We propose to study unweighted graphs of constant distance VC-dimension as a broad generalization of many graph classes for which we can compute the diameter in truly subquadratic-time. In particular for any fixed $H$, the class of $H$-minor free graphs has distance VC-dimension at most $|V(H)|-1$. Our first main result is that on graphs of distance VC-dimension at most $d$, for any fixed $k$ we can either compute the diameter or conclude that it is larger than $k$ in time $\tilde{\cal O}(k\cdot mn^{1-\varepsilon_d})$, where $\varepsilon_d \in (0;1)$ only depends on $d$. Then as a byproduct of our approach, we get the first truly subquadratic-time algorithm for constant diameter computation on all the nowhere dense graph classes. Finally, we show how to remove the dependency on $k$ for any graph class that excludes a fixed graph $H$ as a minor. More generally, our techniques apply to any graph with constant distance VC-dimension and polynomial expansion. As a result for all such graphs one obtains a truly subquadratic-time algorithm for computing their diameter. Our approach is based on the work of Chazelle and Welzl who proved the existence of spanning paths with strongly sublinear stabbing number for every hypergraph of constant VC-dimension. We show how to compute such paths efficiently by combining the best known approximation algorithms for the stabbing number problem with a clever use of $\varepsilon$-nets, region decomposition and other partition techniques., Comment: Submitted. Abstract shortened for the ArXiv listing
Published: 2019
Full Text: View/download PDF

19. Fast approximation of eccentricities and distances in hyperbolic graphs

Author: Hend Alrasheed, Michel Habib, Yann Vaxès, Victor Chepoi, Feodor F. Dragan, Algorithmique, Combinatoire et Recherche Opérationnelle (ACRO), Laboratoire d'Informatique et Systèmes (LIS), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS), Kent State University, Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Networks, Graphs and Algorithms (GANG), 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), The research of V.C., M.H., and Y.V. was supported by ANR project DISTANCIA (ANR-17-CE40-0015)., ANR-17-CE40-0015,DISTANCIA,Théorie métrique des graphes(2017), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS), and Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)
Subjects: General Computer Science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0211 other engineering and technologies, Monotonic function, 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG], 01 natural sciences, Theoretical Computer Science, Combinatorics, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], [INFO]Computer Science [cs], Time complexity, [MATH.MATH-MG]Mathematics [math]/Metric Geometry [math.MG], ComputingMilieux_MISCELLANEOUS, Mathematics, 021103 operations research, Shortest-path tree, Graph, Computer Science Applications, Vertex (geometry), Computational Theory and Mathematics, Distance matrix, 010201 computation theory & mathematics, Geometry and Topology, Centrality, Biological network
Abstract: International audience; We show that the eccentricities (and thus the centrality indices) of all vertices of a δ-hyperbolic graph G = (V, E) can be computed in linear time with an additive one-sided error of at most cδ, i.e., after a linear time preprocessing, for every vertex v of G one can compute in O(1) time an estimateê(v) of its eccentricity eccG(v) such that eccG(v) ≤ê(v) ≤ eccG(v) + cδ for a small constant c. We prove that every δ-hyperbolic graph G has a shortest path tree, constructible in linear time, such that for every vertex v of G, eccG(v) ≤ eccT (v) ≤ eccG(v) + cδ. These results are based on an interesting monotonicity property of the eccentricity function of hyperbolic graphs: the closer a vertex is to the center of G, the smaller its eccentricity is. We also show that the distance matrix of G with an additive one-sided error of at most c ′ δ can be computed in O(|V | 2 log 2 |V |) time, where c ′ < c is a small constant. Recent empirical studies show that many real-world graphs (including Internet application networks, web networks, collaboration networks, social networks, biological networks, and others) have small hyperbolicity. So, we analyze the performance of our algorithms for approximating centrality and distance matrix on a number of real-world networks. Our experimental results show that the obtained estimates are even better than the theoretical bounds.
Published: 2019

20. On the complexity of the shortest-path broadcast problem

Author: Hovhannes A. Harutyunyan, Pierluigi Crescenzi, Geppino Pucci, Andrea Pietracaprina, Pierre Fraigniaud, Chiara Pierucci, Magnús M. Halldórsson, Université de Florence, Università degli Studi di Firenze = University of Florence [Firenze] (UNIFI), 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), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), School of Computer Science [Reykjavik], Reykjavík University, Concordia University [Montreal], Universita degli Studi di Padova, ANR-11-BS02-0014,DISPLEXITY,Calculabilité et complexité en distribué(2011), Università degli Studi di Firenze = University of Florence (UniFI), Università degli Studi di Padova = University of Padua (Unipd), Università degli Studi di Firenze [Firenze], and ANR-11-BS02-014,DISPLEXITY,Calculabilité et complexité en distribué(2011)
Subjects: [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Shortest paths, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Combinatorics, Simple (abstract algebra), TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY, Layered graphs, 0202 electrical engineering, electronic engineering, information engineering, Discrete Mathematics and Combinatorics, Time complexity, Mathematics, Discrete mathematics, Spanning tree, Applied Mathematics, Multiplicative function, 020206 networking & telecommunications, Directed graph, Binary logarithm, Broadcast time, Communication networks, 010201 computation theory & mathematics, Shortest path problem, Node (circuits), [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], MathematicsofComputing_DISCRETEMATHEMATICS
Abstract: International audience; We study the shortest-path broadcast problem in graphs and digraphs, where a message has to be transmitted from a source node s to all the nodes along shortest paths, in the classical telephone model. For both graphs and digraphs, we show that the problem is equivalent to the broadcast problem in layered directed graphs. We then prove that this latter problem is NP-hard, and therefore that the shortest-path broadcast problem is NP-hard in graphs as well as in digraphs. Nevertheless, we prove that a simple polynomial-time algorithm, called MDST-broadcast, based on min-degree spanning trees, approximates the optimal broadcast time within a multiplicative factor 3/2 in 3-layer digraphs, and O(log n/loglog n) in arbitrary multi-layer digraphs. As a consequence, one can approximate the optimal shortest-path broadcast time in polynomial time within a multiplicative factor 3/2 whenever the source has eccentricity at most 2, and within a multiplicative factor O(log n/\log\log n) in the general case, for both graphs and digraphs. The analysis of MDST-broadcast is tight, as we prove that this algorithm cannot approximate the optimal broadcast time within a factor smaller than Omega(log n/log\log n).
Published: 2016

21. Parameterized Complexity of Independent Set in H-Free Graphs

Author: Édouard Bonnet, Pierre Charbit, Rémi Watrigant, Nicolas Bousquet, Stéphan Thomassé, Centre National de la Recherche Scientifique (CNRS), Université de Lyon, Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS 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 - Lyon (ENS Lyon), Modèles de calcul, Complexité, Combinatoire (MC2), 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 - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Optimisation Combinatoire (G-SCOP_OC ), Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Networks, Graphs and Algorithms (GANG), 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), 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.), Université Claude Bernard Lyon 1 (UCBL), ANR-10-LABX-0070,MILYON,Community of mathematics and fundamental computer science in Lyon(2010), ANR-17-CE40-0015,DISTANCIA,Théorie métrique des graphes(2017), Optimisation Combinatoire (G-SCOP_OC), Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA), Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP), 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), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA)-Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA)-Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité), École normale supérieure de Lyon (ENS de Lyon), 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), OC (G-SCOP_OC), Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP)-Institut National Polytechnique de Grenoble (INPG)-Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP)-Institut National Polytechnique de Grenoble (INPG)-Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS), and ANR-11-IDEX-0007-02/10-LABX-0070,MILYON,Community of mathematics and fundamental computer science in Lyon(2011)
Subjects: FOS: Computer and information sciences, Polynomial, General Computer Science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Induced subgraph, Parameterized complexity, 0102 computer and information sciences, 02 engineering and technology, Computational Complexity (cs.CC), [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Combinatorics, Computer Science - Data Structures and Algorithms, 0202 electrical engineering, electronic engineering, information engineering, Data Structures and Algorithms (cs.DS), [MATH]Mathematics [math], Finite set, ComputingMilieux_MISCELLANEOUS, Mathematics, Disjoint union, 000 Computer science, knowledge, general works, H-Free Graphs, Parameterized Algorithms, Applied Mathematics, Independent Set, Parametrized complexity, 16. Peace & justice, Computer Science Applications, Computer Science - Computational Complexity, 010201 computation theory & mathematics, Independent set, Theory of computation, Computer Science, Iterative compression, 020201 artificial intelligence & image processing, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract: In this paper, we investigate the complexity of Maximum Independent Set (MIS) in the class of $H$-free graphs, that is, graphs excluding a fixed graph as an induced subgraph. Given that the problem remains $NP$-hard for most graphs $H$, we study its fixed-parameter tractability and make progress towards a dichotomy between $FPT$ and $W[1]$-hard cases. We first show that MIS remains $W[1]$-hard in graphs forbidding simultaneously $K_{1, 4}$, any finite set of cycles of length at least $4$, and any finite set of trees with at least two branching vertices. In particular, this answers an open question of Dabrowski et al. concerning $C_4$-free graphs. Then we extend the polynomial algorithm of Alekseev when $H$ is a disjoint union of edges to an $FPT$ algorithm when $H$ is a disjoint union of cliques. We also provide a framework for solving several other cases, which is a generalization of the concept of \emph{iterative expansion} accompanied by the extraction of a particular structure using Ramsey's theorem. Iterative expansion is a maximization version of the so-called \emph{iterative compression}. We believe that our framework can be of independent interest for solving other similar graph problems. Finally, we present positive and negative results on the existence of polynomial (Turing) kernels for several graphs $H$., An extended abstract appeared in the proceedings of IPEC 2018
Published: 2018

22. EPTAS for Max Clique on Disks and Unit Balls

Author: Marthe Bonamy, Edouard Bonnet, Nicolas Bousquet, Pierre Charbit, Stephan Thomasse, 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), Centre National de la Recherche Scientifique (CNRS), Modèles de calcul, Complexité, Combinatoire (MC2), Laboratoire de l'Informatique du Parallélisme (LIP), É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-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Optimisation Combinatoire (G-SCOP_OC ), Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), 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), Université Paris Diderot - Paris 7 (UPD7)-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.), ANR-17-CE40-0015,DISTANCIA,Théorie métrique des graphes(2017), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), École normale supérieure - Lyon (ENS 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 - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), 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-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)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université Sciences et Technologies - Bordeaux 1-Université Bordeaux Segalen - Bordeaux 2, OC (G-SCOP_OC), and Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP)-Institut National Polytechnique de Grenoble (INPG)-Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP)-Institut National Polytechnique de Grenoble (INPG)-Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS)
Subjects: Computational Geometry (cs.CG), FOS: Computer and information sciences, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 68Q25, 020206 networking & telecommunications, 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, 010201 computation theory & mathematics, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], 0202 electrical engineering, electronic engineering, information engineering, Computer Science - Computational Geometry, F.2.2
Abstract: We propose a polynomial-time algorithm which takes as input a finite set of points of $\mathbb R^3$ and compute, up to arbitrary precision, a maximum subset with diameter at most $1$. More precisely, we give the first randomized EPTAS and deterministic PTAS for Maximum Clique in unit ball graphs. Our approximation algorithm also works on disk graphs with arbitrary radii. Almost three decades ago, an elegant polynomial-time algorithm was found for Maximum Clique on unit disk graphs [Clark, Colbourn, Johnson; Discrete Mathematics '90]. Since then, it has been an intriguing open question whether or not tractability can be extended to general disk graphs. Recently, it was shown that the disjoint union of two odd cycles is never the complement of a disk graph [Bonnet, Giannopoulos, Kim, Rz\k{a}\.{z}ewski, Sikora; SoCG '18]. This enabled the authors to derive a QPTAS and a subexponential algorithm for Max Clique on disk graphs. In this paper, we improve the approximability to a randomized EPTAS (and a deterministic PTAS). More precisely, we obtain a randomized EPTAS for computing the independence number on graphs having no disjoint union of two odd cycles as an induced subgraph, bounded VC-dimension, and large independence number. We then address the question of computing Max Clique for disks in higher dimensions. We show that intersection graphs of unit balls, like disk graphs, do not admit the complement of two odd cycles as an induced subgraph. This, in combination with the first result, straightforwardly yields a randomized EPTAS for Max Clique on unit ball graphs. In stark contrast, we show that on ball and unit 4-dimensional disk graphs, Max Clique is NP-hard and does not admit an approximation scheme even in subexponential-time, unless the Exponential Time Hypothesis fails., Comment: 19 pages, 3 figures
Published: 2018

23. Implementing Snapshot Objects on Top of Crash-Prone Asynchronous Message-Passing Systems

Author: Hugues Fauconnier, Michel Raynal, Sergio Rajsbaum, Carole Delporte-Gallet, Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Networks, Graphs and Algorithms (GANG), 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), Instituto de Matematicas [México], Universidad Nacional Autónoma de México = National Autonomous University of Mexico (UNAM), the World Is Distributed Exploring the tension between scale and coordination (WIDE), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-SYSTÈMES LARGE ÉCHELLE (IRISA-D1), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), Universidad Nacional Autónoma de México (UNAM), 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.), As Scalable As Possible: foundations of large scale dynamic distributed systems (ASAP), SYSTÈMES LARGE ÉCHELLE (IRISA-D1), Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria), ASAP INRIA de Rennes, Université de Bretagne Sud (UBS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-CentraleSupélec-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Bretagne Sud (UBS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), CentraleSupélec-Télécom Bretagne-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-CentraleSupélec-Télécom Bretagne-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Inria Rennes – Bretagne Atlantique, Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-CentraleSupélec-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Université de Rennes (UNIV-RENNES)-CentraleSupélec-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Rennes (ENS Rennes)-Télécom Bretagne-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-CentraleSupélec, Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), and Raynal, Michel
Subjects: Linearizability, Computer science, Distributed computing, message passing, [SCCO.COMP]Cognitive science/Computer science, Crash, 0102 computer and information sciences, 02 engineering and technology, Parallel computing, [INFO] Computer Science [cs], Pro-cess crash failure, 01 natural sciences, shared memory, 020204 information systems, [INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], 0202 electrical engineering, electronic engineering, information engineering, Concurrent computing, [INFO]Computer Science [cs], Snapshot object, Distributed shared memory, Message passing, snapshot, 020206 networking & telecommunications, Atomic read/write register, Asynchronous message-passing system, Computational Theory and Mathematics, Shared memory, 010201 computation theory & mathematics, Hardware and Architecture, Asynchronous communication, Signal Processing, Snapshot (computer storage), [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
Abstract: In asynchronous crash-prone read/write shared-memory systems there is the notion of a snapshot object, which simulates the behavior of an array of single-writer/multi-reader (SWMR) shared registers that can be read atomically. Processes in the system can access the object invoking (any number of times) two operations, denoted $\mathsf {write}()$ and $\mathsf {snapshot}()$ . A process invokes $\mathsf {write}()$ to update the value of its register in the array. When it invokes $\mathsf {snapshot}()$ , the process obtains the values of all registers, as if it read them simultaneously. It is known that a snapshot object can be implemented on top of SWMR registers, tolerating any number of process failures. Snapshot objects provide a level of abstraction higher than individual SWMR registers, and they simplify the design of applications. Building a snapshot object on an asynchronous crash-prone message-passing system has similar benefits. The object can be implemented by using the known simulations of a SWMR shared memory on top of an asynchronous message-passing system (if less than half the processes can crash), and then build a snapshot object on top of the simulated SWMR memory. This paper presents an algorithm that implements a snapshot object directly on top of the message-passing system, without building an intermediate layer of a SWMR shared memory. To the authors knowledge, the proposed algorithm is the first providing such a direct construction. The algorithm is more efficient than the indirect solution, yet relatively simple.
Published: 2018

24. Parallel Bayesian Search with no Coordination

Author: Amos Korman, Pierre Fraigniaud, Yoav Rodeh, Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Networks, Graphs and Algorithms (GANG), 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), Weizmann Institute of Science [Rehovot, Israël], This work has received funding from the European Research Council (ERC) under the European Union's Horizon 2020research and innovation programme (grant agreement No 648032)., This work has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 648032)., and Weizmann Institute of Science
Subjects: Competitive analysis, Computer science, Computation, 0102 computer and information sciences, 02 engineering and technology, 2-opt, 01 natural sciences, Bayesian search theory, Randomized algorithm, 010201 computation theory & mathematics, Artificial Intelligence, Hardware and Architecture, Control and Systems Engineering, Search algorithm, Robustness (computer science), 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Algorithm, Software, ComputingMilieux_MISCELLANEOUS, Information Systems, Linear search
Abstract: Coordinating the actions of agents (e.g., volunteers analyzing radio signals in SETI@home) yields efficient search algorithms. However, such an efficiency is often at the cost of implementing complex coordination mechanisms which may be expensive in terms of communication and/or computation overheads. Instead, non-coordinating algorithms, in which each agent operates independently from the others, are typically very simple, and easy to implement. They are also inherently robust to slight misbehaviors, or even crashes of agents. In this article, we investigate the “price of non-coordinating,” in terms of search performance, and we show that this price is actually quite small. Specifically, we consider a parallel version of a classical Bayesian search problem, where set of k ≥1 searchers are looking for a treasure placed in one of the boxes indexed by positive integers, according to some distribution p . Each searcher can open a random box at each step, and the objective is to find the treasure in a minimum number of steps. We show that there is a very simple non-coordinating algorithm which has expected running time at most 4(1−1/ k +1) 2 OPT+10, where OPT is the expected running time of the best fully coordinated algorithm. Our algorithm does not even use the precise description of the distribution p , but only the relative likelihood of the boxes. We prove that, under this restriction, our algorithm has the best possible competitive ratio with respect to OPT. For the case where a complete description of the distribution p is given to the search algorithm, we describe an optimal non-coordinating algorithm for Bayesian search. This latter algorithm can be twice as fast as our former algorithm in practical scenarios such as uniform distributions. All these results provide a complete characterization of non-coordinating Bayesian search. The take-away message is that, for their simplicity and robustness, non-coordinating algorithms are viable alternatives to complex coordinating mechanisms subject to significant overheads. Most of these results apply as well to linear search, in which the indices of the boxes reflect their relative importance, and where important boxes must be visited first.
Published: 2018

25. The Assignment Problem

Author: Carole Delporte-Gallet, Giuliano Losa, Eli Gafni, Hugues Fauconnier, Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Networks, Graphs and Algorithms (GANG), 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), Computer Science Department [Los Angeles] (UCLA), University of California [Los Angeles] (UCLA), University of California-University of California, and University of California (UC)-University of California (UC)
Subjects: Renaming, Theoretical computer science, General Computer Science, Computer science, [SCCO.COMP]Cognitive science/Computer science, 0102 computer and information sciences, 02 engineering and technology, CCS CONCEPTS • Theory of computation → Distributed algorithms, 01 natural sciences, Assignment, Theoretical Computer Science, Resource Allocation, Set (abstract data type), Resource (project management), Shared-Memory, 0202 electrical engineering, electronic engineering, information engineering, Wait-Free, Concurrent computing, Mutual Exclusion, Queue, 020207 software engineering, Concurrent algorithms, Partition (database), Allocator, Shared memory, 010201 computation theory & mathematics, Asynchronous communication, Resource allocation, Mutual exclusion, Assignment problem
Abstract: In the allocation problem, asynchronous processors must partition a set of items so that each processor leaves knowing all items exclusively allocated to it. We introduce a new variant of the allocation problem called the assignment problem, in which processors might leave having only partial knowledge of their assigned items. The missing items in a processor's assignment must eventually be announced by other processors. While allocation has consensus number 2, we show that the assignment problem is solvable read-write wait-free when k processors compete for at least 2 k − 1 items. Moreover, we propose a long-lived read-write wait-free assignment algorithm which is fair, allocating no more than 2 items per processor, and in which a slow processor may delay the assignment of at most n items, where n is the number of processors. The assignment problem and its read-write solution may be of practical interest for implementing resource allocators and work queues, which are pervasive concurrent programming patterns, as well as stream-processing systems.
Published: 2018

26. What Can Be Verified Locally?

Author: Pierre Fraigniaud, Gianlorenzo D'Angelo, Alkida Balliu, Dennis Olivetti, Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Gran Sasso Science Institute (GSSI), National Institute for Nuclear Physics (INFN), Networks, Graphs and Algorithms (GANG), 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), Istituto Nazionale di Fisica Nucleare (INFN), Department of Computer Science, Gran Sasso Science Institute, CNRS, Aalto-yliopisto, Aalto University, and Fraigniaud, Pierre
Subjects: Network computing, TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES, Theoretical computer science, General Computer Science, Computer Networks and Communications, Computer science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Local model, 010103 numerical & computational mathematics, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Theoretical Computer Science, Turing machine, symbols.namesake, 020204 information systems, [INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], 0202 electrical engineering, electronic engineering, information engineering, Decision problems, 0101 mathematics, Local algorithm, ta113, 000 Computer science, knowledge, general works, Applied Mathematics, 16. Peace & justice, Distributed computing, Predicate (grammar), TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES, Computational Theory and Mathematics, 010201 computation theory & mathematics, Computer Science, symbols, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
Abstract: International audience; We are considering distributed network computing, in which computing entities are connected by a network modeled as a connected graph. These entities are located at the nodes of the graph, and they exchange information by message-passing along its edges. In this context, we are adopting the classical framework for local distributed decision, in which nodes must collectively decide whether their network configuration satisfies some given boolean predicate, by having each node interacting with the nodes in its vicinity only. A network configuration is accepted if and only if every node individually accepts. It is folklore that not every Turing-decidable network property (e.g., whether the network is planar) can be decided locally whenever the computing entities are Turing machines (TM). On the other hand, it is known that every Turing-decidable network property can be decided locally if nodes are running non-deterministic Turing machines (NTM). However, this holds only if the nodes have the ability to guess the identities of the nodes currently in the network. That is, for different sets of identities assigned to the nodes, the correct guesses of the nodes might be different. If one asks the nodes to use the same guess in the same network configuration even with different identity assignments, i.e., to perform identity-oblivious guesses, then it is known that not every Turing-decidable network property can be decided locally. In this paper, we show that every Turing-decidable network property can be decided locally if nodes are running alternating Turing machines (ATM), and this holds even if nodes are bounded to perform identity-oblivious guesses. More specifically, we show that, for every network property, there is a local algorithm for ATMs, with at most 2 alternations, that decides that property. To this aim, we define a hierarchy of classes of decision tasks where the lowest level contains tasks solvable with TMs, the first level those solvable with NTMs, and level k contains those tasks solvable with ATMs with k alternations. We characterize the entire hierarchy, and show that it collapses in the second level. In addition, we show separation results between the classes of network properties that are locally decidable with TMs, NTMs, and ATMs. Finally, we establish the existence of completeness results for each of these classes, using novel notions of local reduction.
Published: 2018

27. Decidability classes for mobile agents computing

Author: Pierre Fraigniaud, Andrzej Pelc, 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), Département d'Informatique et d'Ingénierie (DII), and Université du Québec en Outaouais (UQO)
Subjects: FOS: Computer and information sciences, Mathematical optimization, Reduction (recursion theory), Theoretical computer science, Computer Networks and Communications, Computer science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, 02 engineering and technology, Computational Complexity (cs.CC), 01 natural sciences, Theoretical Computer Science, Artificial Intelligence, 0202 electrical engineering, electronic engineering, information engineering, Computer Science - Multiagent Systems, Protocol (object-oriented programming), Class (computer programming), Decision problem, Graph, Decidability, Computer Science - Computational Complexity, Computer Science - Distributed, Parallel, and Cluster Computing, 010201 computation theory & mathematics, Hardware and Architecture, 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], Software, Multiagent Systems (cs.MA)
Abstract: We establish a classification of decision problems that are to be solved by mobile agents operating in unlabeled graphs, using a deterministic protocol. The classification is with respect to the ability of a team of agents to solve the problem, possibly with the aid of additional information. In particular, our focus is on studying differences between the decidability of a decision problem by agents and its verifiability when a certificate for a positive answer is provided to the agents. We show that the class MAV of mobile agents verifiable problems is much wider than the class MAD of mobile agents decidable problems. Our main result shows that there exist natural MAV-complete problems: the most difficult problems in this class, to which all problems in MAV are reducible. Our construction of a MAV-complete problem involves two main ingredients in mobile agents computability: the topology of the quotient graph and the number of operating agents. Beyond the class MAV we show that, for a single agent, three natural oracles yield a strictly increasing chain of relative decidability classes.
Published: 2017

28. Certification of Compact Low-Stretch Routing Schemes

Author: Alkida Balliu, Pierre Fraigniaud, 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), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Gran Sasso Science Institute (GSSI), Istituto Nazionale di Fisica Nucleare (INFN), Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP), Fraigniaud, Pierre, and National Institute for Nuclear Physics (INFN)
Subjects: FOS: Computer and information sciences, Routing protocol, Correctness, General Computer Science, Computer science, Routing table, [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, Blocking (statistics), 01 natural sciences, [INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], 0202 electrical engineering, electronic engineering, information engineering, ComputingMilieux_MISCELLANEOUS, ta113, Discrete mathematics, 000 Computer science, knowledge, general works, Handshaking, Computer Science - Distributed, Parallel, and Cluster Computing, 010201 computation theory & mathematics, Computer Science, Content (measure theory), 020201 artificial intelligence & image processing, Node (circuits), Distributed, Parallel, and Cluster Computing (cs.DC), Routing (electronic design automation), [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
Abstract: On the one hand, the correctness of routing protocols in networks is an issue of utmost importance for guaranteeing the delivery of messages from any source to any target. On the other hand, a large collection of routing schemes have been proposed during the last two decades, with the objective of transmitting messages along short routes, while keeping the routing tables small. Regrettably, all these schemes share the property that an adversary may modify the content of the routing tables with the objective of, e.g., blocking the delivery of messages between some pairs of nodes, without being detected by any node. In this paper, we present a simple certification mechanism which enables the nodes to locally detect any alteration of their routing tables. In particular, we show how to locally verify the stretch-3 routing scheme by Thorup and Zwick [SPAA 2001] by adding certificates of $\widetilde{O}(\sqrt{n})$ bits at each node in $n$-node networks, that is, by keeping the memory size of the same order of magnitude as the original routing tables. We also propose a new name-independent routing scheme using routing tables of size $\widetilde{O}(\sqrt{n})$ bits. This new routing scheme can be locally verified using certificates on $\widetilde{O}(\sqrt{n})$ bits. Its stretch is3 if using handshaking, and 5 otherwise.
Published: 2017

29. The Dependent Doors Problem: An Investigation into Sequential Decisions without Feedback

Author: Yoav Rodeh, Amos Korman, 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), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Weizmann Institute of Science [Rehovot, Israël], Weizmann Institute of Science, and Herbstritt, Marc
Subjects: FOS: Computer and information sciences, Sequence, Mathematical optimization, Focus (computing), 000 Computer science, knowledge, general works, Computer science, Computer Science - Artificial Intelligence, 020206 networking & telecommunications, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Multi-armed bandit, Term (time), [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI], Mathematics (miscellaneous), Artificial Intelligence (cs.AI), 010201 computation theory & mathematics, Computer Science, 0202 electrical engineering, electronic engineering, information engineering, Probability distribution, Doors, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Set (psychology), Abstraction (linguistics)
Abstract: We introduce the dependent doors problem as an abstraction for situations in which one must perform a sequence of dependent decisions, without receiving feedback information on the effectiveness of previously made actions. Informally, the problem considers a set of d doors that are initially closed, and the aim is to open all of them as fast as possible. To open a door, the algorithm knocks on it, and it might open or not according to some probability distribution. This distribution may depend on which other doors are currently open, as well as on which other doors were open during each of the previous knocks on that door. The algorithm aims to minimize the expected time until all doors open. Crucially, it must act at any time without knowing whether or which other doors have already opened. In this work, we focus on scenarios where dependencies between doors are both positively correlated and acyclic. The fundamental distribution of a door describes the probability it opens in the best of conditions (with respect to other doors being open or closed). We show that if in two configurations of d doors corresponding doors share the same fundamental distribution, then these configurations have the same optimal running time up to a universal constant, no matter what the dependencies between doors and what the distributions. We also identify algorithms that are optimal up to a universal constant factor. For the case in which all doors share the same fundamental distribution, we additionally provide a simpler algorithm and a formula to calculate its running time. We furthermore analyse the price of lacking feedback for several configurations governed by standard fundamental distributions. In particular, we show that the price is logarithmic in d for memoryless doors but can potentially grow to be linear in d for other distributions. We then turn our attention to investigate precise bounds. Even for the case of two doors, identifying the optimal sequence is an intriguing combinatorial question. Here, we study the case of two cascading memoryless doors. That is, the first door opens on each knock independently with probability p 1 . The second door can only open if the first door is open, in which case it will open on each knock independently with probability p 2 . We solve this problem almost completely by identifying algorithms that are optimal up to an additive term of 1.
Published: 2017

30. Parallel Search with no Coordination

Author: Yoav Rodeh, Amos Korman, Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Networks, Graphs and Algorithms (GANG), 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), Weizmann Institute of Science [Rehovot, Israël], European Project: 648032,H2020,ERC-2014-CoG,DBA(2015), and Weizmann Institute of Science
Subjects: FOS: Computer and information sciences, Computer science, Computer Science::Information Retrieval, Probabilistic logic, 020206 networking & telecommunications, 0102 computer and information sciences, 02 engineering and technology, robustness, Time step, non-coordination, 01 natural sciences, Bayesian search, Bayesian search theory, Distribution (mathematics), Computer Science - Distributed, Parallel, and Cluster Computing, 010201 computation theory & mathematics, Robustness (computer science), 0202 electrical engineering, electronic engineering, information engineering, Distributed, Parallel, and Cluster Computing (cs.DC), [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], parallel computation, Algorithm, Parallel search
Abstract: We consider a parallel version of a classical Bayesian search problem. $k$ agents are looking for a treasure that is placed in one of the boxes indexed by $\mathbb{N}^+$ according to a known distribution $p$. The aim is to minimize the expected time until the first agent finds it. Searchers run in parallel where at each time step each searcher can "peek" into a box. A basic family of algorithms which are inherently robust is \emph{non-coordinating} algorithms. Such algorithms act independently at each searcher, differing only by their probabilistic choices. We are interested in the price incurred by employing such algorithms when compared with the case of full coordination. We first show that there exists a non-coordination algorithm, that knowing only the relative likelihood of boxes according to $p$, has expected running time of at most $10+4(1+\frac{1}{k})^2 T$, where $T$ is the expected running time of the best fully coordinated algorithm. This result is obtained by applying a refined version of the main algorithm suggested by Fraigniaud, Korman and Rodeh in STOC'16, which was designed for the context of linear parallel search.We then describe an optimal non-coordinating algorithm for the case where the distribution $p$ is known. The running time of this algorithm is difficult to analyse in general, but we calculate it for several examples. In the case where $p$ is uniform over a finite set of boxes, then the algorithm just checks boxes uniformly at random among all non-checked boxes and is essentially $2$ times worse than the coordinating algorithm.We also show simple algorithms for Pareto distributions over $M$ boxes. That is, in the case where $p(x) \sim 1/x^b$ for $0< b < 1$, we suggest the following algorithm: at step $t$ choose uniformly from the boxes unchecked in ${1, . . . ,min(M, \lfloor t/\sigma\rfloor)}$, where $\sigma = b/(b + k - 1)$. It turns out this algorithm is asymptotically optimal, and runs about $2+b$ times worse than the case of full coordination.
Published: 2017

31. Distributed Detection of Cycles

Author: Dennis Olivetti, Pierre Fraigniaud, 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), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Université Paris-Diderot, Department of Computer Science, Aalto-yliopisto, Aalto University, and Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP)
Subjects: Network computing, Property testing, FOS: Computer and information sciences, Computer science, Distributed property testing, Existential quantification, education, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Context (language use), Distributed decision, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, 0202 electrical engineering, electronic engineering, information engineering, 0101 mathematics, Cycle detection, ComputingMilieux_MISCELLANEOUS, Theory of computation, Discrete mathematics, 010102 general mathematics, Congest model, 16. Peace & justice, Distributed computing, Computer Science Applications, Computational Theory and Mathematics, Computer Science - Distributed, Parallel, and Cluster Computing, 010201 computation theory & mathematics, Hardware and Architecture, Distributed algorithm, Graph algorithms analysis, Modeling and Simulation, Distributed algorithms, 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], Constant (mathematics), Algorithm, Software, Design and analysis of algorithms
Abstract: Distributed property testing in networks has been introduced by Brakerski and Patt-Shamir [6], with the objective of detecting the presence of large dense sub-networks in a distributed manner. Recently, Censor-Hillel et al. [7] have revisited this notion and formalized it in a broader context. In particular, they have shown how to detect 3-cycles in a constant number of rounds by a distributed algorithm. In a follow-up work, Fraigniaud et al. [21] have shown how to detect 4-cycles in a constant number of rounds as well. However, the techniques in these latter works were shown not to generalize to larger cycles C k with k ≥ 5. In this article, we completely settle the problem of cycle detection by establishing the following result: For every k ≥ 3, there exists a distributed property testing algorithm for C k -freeness, performing in a constant number of rounds. All these results hold in the classical congest model for distributed network computing. Our algorithm is 1-sided error. Its round-complexity is O (1ϵ) where ϵ ∈ (0,1) is the property-testing parameter measuring the gap between legal and illegal instances.
Published: 2017

32. Multiple Random Walks on Paths and Grids

Author: Ivaskovic, Andrej, Kosowski, Adrian, Pająk, Dominik, Sauerwald, Thomas, Herbstritt, Marc, Computer Laboratory [Cambridge], University of Cambridge [UK] (CAM), 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), and Wroclaw University of Science and Technology
Subjects: 000 Computer science, knowledge, general works, and phrases random walks, parallel computing, randomized algorithms, 010401 analytical chemistry, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Computer Science, 0202 electrical engineering, electronic engineering, information engineering, 020206 networking & telecommunications, random walks, 02 engineering and technology, 01 natural sciences, 0104 chemical sciences
Abstract: International audience; We derive several new results on multiple random walks on "low dimensional" graphs. First, inspired by an example of a weighted random walk on a path of three vertices given by Efremenko and Reingold, we prove the following dichotomy: as the path length n tends to infinity, we have a super-linear speed-up w.r.t. the cover time if and only if the number of walks k is equal to 2. An important ingredient of our proofs is the use of a continuous-time analogue of multiple random walks, which might be of independent interest. Finally, we also present the first tight bounds on the speed-up of the cover time for any d-dimensional grid with d >= 2 being an arbitrary constant, and reveal a sharp transition between linear and logarithmic speed-up.
Published: 2017

33. Maximum Induced Matching Algorithms via Vertex Ordering Characterizations

Author: Lalla Mouatadid, Michel Habib, 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), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Department of Computer Science [University of Toronto] (DCS), and University of Toronto
Subjects: FOS: Computer and information sciences, General 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, law.invention, law, Computer Science - Data Structures and Algorithms, Line graph, 0202 electrical engineering, electronic engineering, information engineering, Data Structures and Algorithms (cs.DS), Time complexity, ComputingMilieux_MISCELLANEOUS, Mathematics, 000 Computer science, knowledge, general works, Applied Mathematics, Trapezoid graph, Sigma, 16. Peace & justice, Graph, Computer Science Applications, Vertex (geometry), 010201 computation theory & mathematics, Computer Science, Theory of computation, Bipartite graph, 020201 artificial intelligence & image processing, Algorithm
Abstract: We study the maximum induced matching problem on a graph G. Induced matchings correspond to independent sets in L^2(G), the square of the line graph of G. The problem is NP-complete on bipartite graphs. In this work, we show that for a number of graph families with forbidden vertex orderings, almost all forbidden patterns on three vertices are preserved when taking the square of the line graph. These orderings can be computed in linear time in the size of the input graph. In particular, given a graph class \mathcal{G} characterized by a vertex ordering, and a graph G=(V,E) \in \mathcal{G} with a corresponding vertex ordering \sigma of V, one can produce (in linear time in the size of G) an ordering on the vertices of L^2(G), that shows that L^2(G) \in \mathcal{G} - for a number of graph classes \mathcal{G} - without computing the line graph or the square of the line graph of G. These results generalize and unify previous ones on showing closure under L^2(\cdot) for various graph families. Furthermore, these orderings on L^2(G) can be exploited algorithmically to compute a maximum induced matching on G faster. We illustrate this latter fact in the second half of the paper where we focus on cocomparability graphs, a large graph class that includes interval, permutation, trapezoid graphs, and co-graphs, and we present the first \mathcal{O}(mn) time algorithm to compute a maximum weighted induced matching on cocomparability graphs; an improvement from the best known \mathcal{O}(n^4) time algorithm for the unweighted case.
Published: 2017
Full Text: View/download PDF

34. On computing the diameter of real-world undirected graphs

Author: Andrea Marino, Roberto Grossi, Michel Habib, Pilu Crescenzi, Leonardo Lanzi, Department of Systems and Computer Science [Florence], Università degli Studi di Firenze = University of Florence (UniFI), Dipartimento di Informatica [Pisa], University of Pisa - Università di Pisa, Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Networks, Graphs and Algorithms (GANG), 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), Dipartimento di Sistemi e Informatica (DSI), and Università degli Studi di Firenze = University of Florence [Firenze] (UNIFI)
Subjects: Discrete mathematics, General Computer Science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Breadth-first search, 0102 computer and information sciences, 02 engineering and technology, Complex network, 01 natural sciences, Graph, Longest path problem, Theoretical Computer Science, Combinatorics, Indifference graph, 010201 computation theory & mathematics, Shortest path problem, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Undirected graph, Random geometric graph, MathematicsofComputing_DISCRETEMATHEMATICS, Mathematics
Abstract: International audience; We propose a new algorithm for the classical problem of computing the diameter of undirected unweighted graphs, namely, the maximum distance among all the pairs of nodes, where the distance of a pair of nodes is the number of edges contained in the shortest path connecting these two nodes. Although its worst-case complexity is O(nm) time, where n is the number of nodes and m is the number of edges of the graph, we experimentally show that our algorithm works in O(m) time in practice, requiring few breadth-first searches to complete its task on almost 200 real-world graphs.
Published: 2013

35. Survey of Piecewise Convex Maximization and PCMP over Spherical Sets

Author: Ider Tseveendorj, Dominique Fortin, Laboratoire de Mathématiques de Versailles (LMV), Université de Versailles Saint-Quentin-en-Yvelines (UVSQ)-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS), 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, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)
Subjects: Convex analysis, Pointwise, 0209 industrial biotechnology, 021103 operations research, Line search, 0211 other engineering and technologies, Regular polygon, 02 engineering and technology, Combinatorics, 020901 industrial engineering & automation, Piecewise, Entropy maximization, Affine transformation, [MATH]Mathematics [math], Convex function, Mathematics
Abstract: International audience; The main investigation in this chapter is concerned with a piecewise convex function which can be defined by the pointwise minimum of convex functions, F(x)=min{f1(x),…,fm(x)}. Such piecewise convex functions closely approximate nonconvex functions, that seems to us as a natural extension of the piecewise affine approximation from convex analysis. Maximizing F(⋅ ) over a convex domain have been investigated during the last decade by carrying tools based mostly on linearization and affine separation. In this chapter, we present a brief overview of optimality conditions, methods, and some attempts to solve this difficult nonconvex optimization problem. We also review how the line search paradigm leads to a radius search paradigm, in the sense that sphere separation which seems to us more appropriate than the affine separation. Some simple, but illustrative, examples showing the issues in searching for a global solution are given.
Published: 2016

36. Making Local Algorithms Wait-Free: The Case of Ring Coloring

Author: Armando Castañeda, Sergio Rajsbaum, Hugues Fauconnier, Carole Delporte, Michel Raynal, Technion - Israel Institute of Technology [Haifa], Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Networks, Graphs and Algorithms (GANG), 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), Instituto de Matematicas [México], Universidad Nacional Autónoma de México (UNAM), As Scalable As Possible: foundations of large scale dynamic distributed systems (ASAP), SYSTÈMES LARGE ÉCHELLE (IRISA-D1), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), CentraleSupélec-Télécom Bretagne-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-CentraleSupélec-Télécom Bretagne-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria), Universidad Nacional Autónoma de México = National Autonomous University of Mexico (UNAM), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-SYSTÈMES LARGE ÉCHELLE (IRISA-D1), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Télécom Bretagne-CentraleSupélec-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.), the World Is Distributed Exploring the tension between scale and coordination (WIDE), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), C. Delporte, H. Fauconnier, and M. Raynal, were partially supported by the French ANR project DESCARTES, devoted to abstraction layers in distributed computing. A. Castaneda was supported in part by UNAM PAPIIT-DGAPA projects IA101015 and IA102417. S. Rajsbaum was supported in part by UNAM PAPIIT-DGAPA project IN107714.All the authors want to thank INRIA for its support in the context of the INRIA-UNAM ' ́Equipe Associée' LiDiCo (At the Limits of DistributedComputing)., Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-CentraleSupélec-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Université de Rennes (UNIV-RENNES)-CentraleSupélec-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Rennes (ENS Rennes)-Télécom Bretagne-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-CentraleSupélec, Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Université de Bretagne Sud (UBS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-CentraleSupélec-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Bretagne Sud (UBS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), and Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1)
Subjects: Vertex (graph theory), Locality of a computation, Theoretical computer science, Computer science, Computation, [SCCO.COMP]Cognitive science/Computer science, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Message-passing, Theoretical Computer Science, Cole and Vishkin's coloring, 020204 information systems, local, 0202 electrical engineering, electronic engineering, information engineering, [INFO]Computer Science [cs], Mathematics, Node (networking), Message passing, Locality, wait free, Vertex coloring problem, Process crash failure, Asynchrony (computer programming), Synchronous communication, Algorithm, Computational Theory and Mathematics, 010201 computation theory & mathematics, Asynchronous communication, Wait-freedom, Theory of computation, Graph (abstract data type), Synchronous distributed computing
Abstract: International audience; When considering distributed computing, reliable message-passing synchronous systems on the one side, and asynchronous failure-prone shared-memory systems on the other side, remain two quite independently studied ends of the relia-bility/asynchrony spectrum. The concept of locality of a computation is central to the first one, while the concept of wait-freedom is central to the second one. The paper proposes a new DECOUPLED model in an attempt to reconcile these two worlds. It consists of a synchronous and reliable communication graph of n nodes, and on top a set of asynchronous crash-prone processes, each attached to a communication node. To illustrate the DECOUPLED model, the paper presents an asynchronous 3-coloring algorithm for the processes of a ring. From the processes point of view, the This article is part Theory Comput Syst algorithm is wait-free. From a locality point of view, each process uses information only from processes at distance O(log * n) from it. This local wait-free algorithm is based on an extension of the classical Cole and Vishkin's vertex coloring algorithm in which the processes are not required to start simultaneously.
Published: 2016

37. Sublinear-Space Distance Labeling Using Hubs

Author: Adrian Kosowski, Przemyslaw Uznanski, Paweł Gawrychowski, University of Warsaw (UW), 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 Computer Science [ETH Zürich] (D-INFK), Eidgenössische Technische Hochschule - Swiss Federal Institute of Technology in Zürich [Zürich] (ETH Zürich), Cyril Gavoille, David Ilcinkas, and Eidgenössische Technische Hochschule - Swiss Federal Institute of Technology [Zürich] (ETH Zürich)
Subjects: FOS: Computer and information sciences, Sublinear function, [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, Combinatorics, ComputingMethodologies_PATTERNRECOGNITION, Distance labeling, 010201 computation theory & mathematics, Computer Science - Data Structures and Algorithms, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Data Structures and Algorithms (cs.DS), ComputingMilieux_MISCELLANEOUS, Mathematics, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract: A distance labeling scheme is an assignment of bit-labels to the vertices of an undirected, unweighted graph such that the distance between any pair of vertices can be decoded solely from their labels. We propose a series of new labeling schemes within the framework of so-called hub labeling (HL, also known as landmark labeling or 2-hop-cover labeling), in which each node $u$ stores its distance to all nodes from an appropriately chosen set of hubs $S(u) \subseteq V$. For a queried pair of nodes $(u,v)$, the length of a shortest $u-v$-path passing through a hub node from $S(u)\cap S(v)$ is then used as an upper bound on the distance between $u$ and $v$. We present a hub labeling which allows us to decode exact distances in sparse graphs using labels of size sublinear in the number of nodes. For graphs with at most $n$ nodes and average degree $\Delta$, the tradeoff between label bit size $L$ and query decoding time $T$ for our approach is given by $L = O(n \log \log_\Delta T / \log_\Delta T)$, for any $T \leq n$. Our simple approach is thus the first sublinear-space distance labeling for sparse graphs that simultaneously admits small decoding time (for constant $\Delta$, we can achieve any $T=\omega(1)$ while maintaining $L=o(n)$), and it also provides an improvement in terms of label size with respect to previous slower approaches. By using similar techniques, we then present a $2$-additive labeling scheme for general graphs, i.e., one in which the decoder provides a 2-additive-approximation of the distance between any pair of nodes. We achieve almost the same label size-time tradeoff $L = O(n \log^2 \log T / \log T)$, for any $T \leq n$. To our knowledge, this is the first additive scheme with constant absolute error to use labels of sublinear size. The corresponding decoding time is then small (any $T=\omega(1)$ is sufficient).
Published: 2016

38. Brief Announcement: Self-stabilizing Clock Synchronization with 3-bit Messages

Author: Amos Korman, Emanuele Natale, Lucas Boczkowski, 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), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Combinatorics, Optimization and Algorithms for Telecommunications (COATI), 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), Université Côte d'Azur (UCA)-Université Côte d'Azur (UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Nice Sophia Antipolis (... - 2019) (UNS), Université Côte d'Azur (UCA)-Université Côte d'Azur (UCA)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Côte d'Azur (UCA)-Université Côte d'Azur (UCA)-Centre National de la Recherche Scientifique (CNRS)-Inria Sophia Antipolis - Méditerranée (CRISAM), Centre National de la Recherche Scientifique (CNRS), Université Côte d'Azur (UCA), Université Côte d'Azur (UCA)-Université Côte d'Azur (UCA)-Centre National de la Recherche Scientifique (CNRS), 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), Université Nice Sophia Antipolis (1965 - 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 (1965 - 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), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA), 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 (... - 2019) (UNS)
Subjects: education.field_of_study, Theoretical computer science, Computer science, Population, Self-stabilization, 0102 computer and information sciences, 02 engineering and technology, Network protocols, Distributed computer systems, Binary consensus, 01 natural sciences, Clock synchronization, Atomic broadcast, Terminating Reliable Broadcast, Consensus, 010201 computation theory & mathematics, Asynchronous communication, 020204 information systems, 0202 electrical engineering, electronic engineering, information engineering, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], education, Dissemination, ComputingMilieux_MISCELLANEOUS
Abstract: This paper is motivated by the aspiration to identify the weakest computational models that allow for efficient, robust distributed computation. We focus on one of the most fundamental building-blocks in distributed computing, namely, Broadcast. In this problem, a unique source agent $s$ needs to disseminate a bit $b$ to the rest of the population. To account for unpredictability issues that may result from uncoordinated executions, we consider a self-stabilizing setting, in which a correct configuration must be reached eventually, despite processors starting the execution with arbitrary initial states (that do not violate the requirement for the existence of a unique source). Similarly to many works on broadcast, we consider a synchronous communication model on a complete anonymous network, in which in each round, each agent can extract information from two other agents, chosen uniformly at random. Our focus is on identifying the smallest message size that is required in order to achieve fast self-stabilizing broadcast. We first observe that with an extra bit added to the message-size and a small additive penalty to the running time, the self-stabilizing broadcast problem can be reduced to a self-stabilizing clock-synchronization problem, where agents aim to synchronize their clocks modulo some integer T. Our main technical contribution lies in solving the latter problem in poly-logarithmic time using only 3 bits per interaction. This allows for a self-stabilizing broadcast protocol that uses only 4 bits per interaction and converges in O log n time.
Published: 2016

39. t-Resilient Immediate Snapshot Is Impossible

Author: Carole Delporte, Sergio Rajsbaum, Hugues Fauconnier, Michel Raynal, Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Networks, Graphs and Algorithms (GANG), 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), As Scalable As Possible: foundations of large scale dynamic distributed systems (ASAP), SYSTÈMES LARGE ÉCHELLE (IRISA-D1), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), CentraleSupélec-Télécom Bretagne-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-CentraleSupélec-Télécom Bretagne-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria), Instituto de Matematicas [México], Universidad Nacional Autónoma de México (UNAM), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-SYSTÈMES LARGE ÉCHELLE (IRISA-D1), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Universidad Nacional Autónoma de México = National Autonomous University of Mexico (UNAM), Raynal, Michel, 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.), Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-CentraleSupélec-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Université de Rennes (UNIV-RENNES)-CentraleSupélec-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Rennes (ENS Rennes)-Télécom Bretagne-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-CentraleSupélec, and DELPORTE-GALLET, CAROLE
Subjects: Theoretical computer science, Linearizability, Consensus, t-resilience, Computer science, Distributed computabil-ity, Crash, 0102 computer and information sciences, 02 engineering and technology, [INFO] Computer Science [cs], 01 natural sciences, Shared memory, Iterated model, 0202 electrical engineering, electronic engineering, information engineering, [INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], [INFO]Computer Science [cs], Asynchronous system, Impossibility, Immediate snapshot, k-Set Agreement, Snapshot object, Process crash failure, 020207 software engineering, Atomic read/write register, ACM: F.: Theory of Computation, 010201 computation theory & mathematics, Wait-freedom, Snapshot (computer storage), Process identifier, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
Abstract: Immediate snapshot is the basic communication object on which relies the read/write distributed computing model made up of n crash-prone asynchronous processes, called iterated distributed model. Each iteration step (usually called a round) uses a new immediate snapshot object, which allows the processes to communicate and cooperate. More precisely, the x-th immediate snapshot object can be used by a process only when it executes the x-th round. An immediate snapshot object can be implemented by an (n − 1)-resilient algorithm, i.e. an algorithm that tolerates up to (n − 1) process crashes (also called wait-free algorithm). Considering a t-crash system model (i.e. a model in which up to t processes are allowed to crash), this paper is on the construction of an extension of immediate snapshot objects to t-resiliency. In the t-crash system model, at each round each process may be ensured to get values from at least n − t processes, and t-immediate snapshot has the properties of classical immediate snapshot (1-immediate snapshot) but ensures that each process will get values form at least n − t processes. Its main result is the following. While there is a (deterministic) t-resilient read/write-based algorithm implementing t-immediate snapshot in a t-crash system when t = n − 1, there is no t-resilient algorithm in a t-crash model when t ∈ [1..(n−2)]. This means that the notion of t-resilience is inop-erative when one has to implement immediate snapshot for these values of t: the model assumption " at most t < n − 1 processes may crash " does not provide us with additional computational power allowing for the design of genuine t-resilient algorithms (genuine meaning that such a t-resilient algorithm would work in the t-crash model, but not in the (t + 1)-crash model). To show these results, the paper relies on well-known distributed computing agreement problems such as consensus and k-set agreement.
Published: 2016

40. Brief Announcement: Sublinear-Space Distance Labeling Using Hubs

Author: Przemyslaw Uznanski, Adrian Kosowski, Paweł Gawrychowski, University of Warsaw (UW), 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 Computer Science [ETH Zürich] (D-INFK), Eidgenössische Technische Hochschule - Swiss Federal Institute of Technology [Zürich] (ETH Zürich), and Eidgenössische Technische Hochschule - Swiss Federal Institute of Technology in Zürich [Zürich] (ETH Zürich)
Subjects: ta113, Discrete mathematics, Distributed Data Structures, Sublinear function, Edge-graceful labeling, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Distance Labeling, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Upper and lower bounds, Graph, Combinatorics, Distance labeling, 010201 computation theory & mathematics, Approximation error, 0202 electrical engineering, electronic engineering, information engineering, Distributed data structures, 020201 artificial intelligence & image processing, Distance Oracles, Graphs, Algorithms, Decoding methods, ComputingMilieux_MISCELLANEOUS, Mathematics
Abstract: A distance labeling scheme is an assignment of bit-labels to the vertices of an undirected, unweighted graph such that the distance between any pair of vertices can be decoded solely from their labels. We propose a series of new labeling schemes within the framework of so-called hub labeling (HL, also known as landmark labeling or 2-hop-cover labeling), in which each node u stores its distance to all nodes from an appropriately chosen set of hubs S(u) ⊆ V. For a queried pair of nodes (u,v), the length of a shortest u--v-path passing through a hub node from S(u)∩S(v) is then used as an upper bound on the distance between u and v.We present a hub labeling which allows us to decode exact distances in sparse graphs using labels of size sublinear in the number of nodes. For graphs with at most n nodes and average degree Δ, the tradeoff between label bit size L and query decoding time T for our approach is given by L = O(n log logΔT / logΔT), for any T ≤ n. Our simple approach is thus the first sublinear-space distance labeling for sparse graphs that simultaneously admits small decoding time (for constant Δ, we can achieve any T=Ω(1) while maintaining L=o(n)), and it also provides an improvement in terms of label size with respect to previous slower approaches.By using similar techniques, we then present a 2-additive labeling scheme for general graphs, i.e., one in which the decoder provides a 2-additive-approximation of the distance between any pair of nodes. We achieve the same label size-time tradeoff L = O(n log2 log T / log T), for any T ≤ n. To our knowledge, this is the first additive scheme with constant absolute error to use labels of sublinear size. The corresponding decoding time is then small (any T=Ω(1) is sufficient).
Published: 2016

41. Perfect Failure Detection with Very Few Bits

Author: Thibault Rieutord, Petr Kuznetsov, Sergio Rajsbaum, Pierre Fraigniaud, Corentin Travers, Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Networks, Graphs and Algorithms (GANG), 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), Instituto de Matematicas [México], Universidad Nacional Autónoma de México = National Autonomous University of Mexico (UNAM), 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), Télécom ParisTech, Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP), Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité), Institut Polytechnique de Paris (IP Paris), Télécom Paris, Autonomic and Critical Embedded Systems (ACES), Laboratoire Traitement et Communication de l'Information (LTCI), Institut Mines-Télécom [Paris] (IMT)-Télécom Paris-Institut Mines-Télécom [Paris] (IMT)-Télécom Paris, Département Informatique et Réseaux (INFRES), Département Ingénierie Logiciels et Systèmes (DILS), Laboratoire d'Intégration des Systèmes et des Technologies (LIST (CEA)), Direction de Recherche Technologique (CEA) (DRT (CEA)), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Direction de Recherche Technologique (CEA) (DRT (CEA)), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Université Paris-Saclay, ANR-16-CE40-0023,DESCARTES,Abstraction modulaire pour le calcul distribué(2016), ANR-17-CE40-0013,FREDDA,Méthodes formelles pour la conception d'algorithmes distribués(2017), Universidad Nacional Autónoma de México (UNAM), 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, Fraigniaud, Pierre, Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), ECOS Nord (Project M12M01), LaBRI - Laboratoire Bordelais de Recherche en Informatique, and ANR-10-IDEX-0003,IDEX BORDEAUX,Initiative d'excellence de l'Université de Bordeaux(2010)
Subjects: Computer science, failure detector, [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, Higman's lemma, 01 natural sciences, Oracle, Theoretical Computer Science, Complete information, 020204 information systems, [INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], 0202 electrical engineering, electronic engineering, information engineering, [INFO]Computer Science [cs], Failure detector, ComputingMilieux_MISCELLANEOUS, Mathematics, Discrete mathematics, Process (computing), Function (mathematics), Computer Science Applications, well-quasi order, Alpha (programming language), Computational Theory and Mathematics, 010201 computation theory & mathematics, Asynchronous communication, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Constant (mathematics), Algorithm, Information Systems, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract: A failure detector is a distributed oracle that provides each process with a module that continuously outputs an estimate of which processes in the system have failed. The perfect failure detector provides accurate and eventually complete information about process failures. We show that, in asynchronous failure-prone message-passing systems, perfect failure detection can be achieved by an oracle that outputs at most $\lceil \log \alpha (n)\rceil +1$ bits per process in n-process systems, where $\alpha $ denotes the inverse-Ackermann function. This result is essentially optimal, as we also show that, in the same environment, no failure detector outputting a constant number of bits per process can achieve perfect failure detection.
Published: 2016

42. Beyond Highway Dimension: Small Distance Labels Using Tree Skeletons

Author: Adrian Kosowski, Laurent Viennot, 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, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)
Subjects: FOS: Computer and information sciences, 021103 operations research, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0211 other engineering and technologies, Distance Labeling, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Computer Science - Distributed, Parallel, and Cluster Computing, 010201 computation theory & mathematics, Computer Science - Data Structures and Algorithms, Skeleton Dimension, Shortest Path Tree, Data Structures and Algorithms (cs.DS), Distributed, Parallel, and Cluster Computing (cs.DC), [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Highway Dimension
Abstract: The goal of a hub-based distance labeling scheme for a network G = (V, E) is to assign a small subset S(u) $\subseteq$ V to each node u $\in$ V, in such a way that for any pair of nodes u, v, the intersection of hub sets S(u) $\cap$ S(v) contains a node on the shortest uv-path. The existence of small hub sets, and consequently efficient shortest path processing algorithms, for road networks is an empirical observation. A theoretical explanation for this phenomenon was proposed by Abraham et al. (SODA 2010) through a network parameter they called highway dimension, which captures the size of a hitting set for a collection of shortest paths of length at least r intersecting a given ball of radius 2r. In this work, we revisit this explanation, introducing a more tractable (and directly comparable) parameter based solely on the structure of shortest-path spanning trees, which we call skeleton dimension. We show that skeleton dimension admits an intuitive definition for both directed and undirected graphs, provides a way of computing labels more efficiently than by using highway dimension, and leads to comparable or stronger theoretical bounds on hub set size., Comment: SODA 2017 - 28th ACM-SIAM Symposium on Discrete Algorithms, Jan 2017, Barcelona, Spain. 2017
Published: 2016
Full Text: View/download PDF

43. Sparsifying Congested Cliques and Core-Periphery Networks

Author: Zvi Lotker, Alkida Balliu, Dennis Olivetti, Pierre Fraigniaud, 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), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Gran Sasso Science Institute (GSSI), Istituto Nazionale di Fisica Nucleare (INFN), Ben-Gurion University of the Negev (BGU), and National Institute for Nuclear Physics (INFN)
Subjects: Clique, Random graph, Computation, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 020206 networking & telecommunications, 0102 computer and information sciences, 02 engineering and technology, Binary logarithm, 01 natural sciences, Combinatorics, 010201 computation theory & mathematics, Distributed algorithm, Bounded function, Core (graph theory), 0202 electrical engineering, electronic engineering, information engineering, Fraction (mathematics), [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Mathematics, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract: International audience; The \emph{core-periphery} network architecture proposed by Avin et al. [ICALP 2014] was shown to support fast computation for many distributed algorithms, while being much sparser than the \emph{congested clique}. For being efficient, the core-periphery architecture is however bounded to satisfy three axioms, among which is the capability of the core to emulate the clique, i.e., to implement the all-to-all communication pattern, in $O(1)$ rounds in the \CONGEST\ model. In this paper, we show that implementing all-to-all communication in $k$ rounds can be done in $n$-node networks with roughly $n^2/k$ edges, and this bound is tight. Hence, sparsifying the core beyond just saving a fraction of the edges requires to relax the constraint on the time to simulate the congested clique. We show that, for $p\gg \sqrt{\log n/n}$, a random graph in ${\cal G}_{n,p}$ can, w.h.p., perform the all-to-all communication pattern in $O(\min\{\frac{1}{p^2},n p\})$ rounds. Finally, we show that if the core can emulate the congested clique in $t$ rounds, then there exists a distributed MST construction algorithm performing in $O(t\log n)$ rounds. Hence, for $t=O(1)$, our (deterministic) algorithm improves the best known (randomized) algorithm for constructing MST in core-periphery networks by a factor $\Theta(\log n)$.
Published: 2016

44. Setting Ports in an Anonymous Network: How to Reduce the Level of Symmetry?

Author: Ralf Klasing, Dominik Pajak, Adrian Kosowski, 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), Wroclaw University of Science and Technology, Jukka Suomela, 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, Wroclaw University of Technology [Wroclaw], 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: Vertex (graph theory), 020203 distributed computing, Engineering, Theoretical computer science, business.industry, Distributed computing, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, 02 engineering and technology, Level of symmetry, Anonymous network, Port-labeled network, 01 natural sciences, Port (computer networking), Graph, View, 010201 computation theory & mathematics, Asynchronous communication, Homogeneous space, 0202 electrical engineering, electronic engineering, information engineering, Symmetry breaking, business, ComputingMilieux_MISCELLANEOUS
Abstract: A fundamental question in the setting of anonymous graphs concerns the ability of nodes to spontaneously break symmetries, based on their local perception of the network. In contrast to previous work, which focuses on symmetry breaking under arbitrary port labelings, in this paper, we study the following design question: Given an anonymous graph G without port labels, how to assign labels to the ports of G, in interval form at each vertex, so that symmetry breaking can be achieved using a message-passing protocol requiring as few rounds of synchronous communication as possible?
Published: 2016

45. Minimizing Message Size in Stochastic Communication Patterns: Fast Self-Stabilizing Protocols with 3 bits

Author: Lucas Boczkowski, Amos Korman, Emanuele Natale, 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), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Università degli Studi di Roma 'La Sapienza' = Sapienza University [Rome], European Project: 648032,H2020,ERC-2014-CoG,DBA(2015), Max Planck Institute for Informatics [Saarbrücken], Simons Institute for the Theory of Computing, This work has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research andinnovation programme (grant agreement No 64803), Università degli Studi di Roma 'La Sapienza' [Rome], and Università degli Studi di Roma 'La Sapienza' = Sapienza University [Rome] (UNIROMA)
Subjects: FOS: Computer and information sciences, Computer Networks and Communications, Computer science, Modulo, Population, Context (language use), 02 engineering and technology, 0102 computer and information sciences, 01 natural sciences, Clock synchronization, Theoretical Computer Science, Set (abstract data type), 03 medical and health sciences, 0302 clinical medicine, 0202 electrical engineering, electronic engineering, information engineering, education, Discrete mathematics, education.field_of_study, [SDV.BA]Life Sciences [q-bio]/Animal biology, 020206 networking & telecommunications, Binary logarithm, Computational Theory and Mathematics, Computer Science - Distributed, Parallel, and Cluster Computing, 010201 computation theory & mathematics, Hardware and Architecture, 030220 oncology & carcinogenesis, Bounded function, Distributed, Parallel, and Cluster Computing (cs.DC), [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Integer (computer science)
Abstract: This paper considers the basic $\mathcal{PULL}$ model of communication, in which in each round, each agent extracts information from few randomly chosen agents. We seek to identify the smallest amount of information revealed in each interaction (message size) that nevertheless allows for efficient and robust computations of fundamental information dissemination tasks. We focus on the Majority Bit Dissemination problem that considers a population of $n$ agents, with a designated subset of source agents. Each source agent holds an input bit and each agent holds an output bit. The goal is to let all agents converge their output bits on the most frequent input bit of the sources (the majority bit). Note that the particular case of a single source agent corresponds to the classical problem of Broadcast. We concentrate on the severe fault-tolerant context of self-stabilization, in which a correct configuration must be reached eventually, despite all agents starting the execution with arbitrary initial states. We first design a general compiler which can essentially transform any self-stabilizing algorithm with a certain property that uses $\ell$-bits messages to one that uses only $\log \ell$-bits messages, while paying only a small penalty in the running time. By applying this compiler recursively we then obtain a self-stabilizing Clock Synchronization protocol, in which agents synchronize their clocks modulo some given integer $T$, within $\tilde O(\log n\log T)$ rounds w.h.p., and using messages that contain $3$ bits only. We then employ the new Clock Synchronization tool to obtain a self-stabilizing Majority Bit Dissemination protocol which converges in $\tilde O(\log n)$ time, w.h.p., on every initial configuration, provided that the ratio of sources supporting the minority opinion is bounded away from half. Moreover, this protocol also uses only 3 bits per interaction., Comment: 28 pages, 4 figures
Published: 2016
Full Text: View/download PDF

46. Decentralized Asynchronous Crash-Resilient Runtime Verification

Author: Borzoo Bonakdarpour, Pierre Fraigniaud, Sergio Rajsbaum, David Rosenblueth, Corentin Travers, 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), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Department of Electrical and Computer Engineering [Waterloo] (ECE), University of Waterloo [Waterloo], Instituto de Matematicas [México], Universidad Nacional Autónoma de México (UNAM), Instituto de Matematicas (UNAM), Laboratoire Bordelais de Recherche en Informatique (LaBRI), 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)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Universidad Nacional Autónoma de México = National Autonomous University of Mexico (UNAM), 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: 000 Computer science, knowledge, general works, Artificial Intelligence, Hardware and Architecture, Control and Systems Engineering, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Computer Science, 0202 electrical engineering, electronic engineering, information engineering, 020207 software engineering, 020201 artificial intelligence & image processing, 02 engineering and technology, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Software, Information Systems
Abstract: Runtime verification is a lightweight method for monitoring the formal specification of a system during its execution. It has recently been shown that a given state predicate can be monitored consistently by a set of crash-prone asynchronous distributed monitors observing the system, only if each monitor can emit verdicts taken from a large enough finite set. We revisit this impossibility result in the concrete context of linear-time logic ( ltl ) semantics for runtime verification, that is, when the correctness of the system is specified by an ltl formula on its execution traces. First, we show that monitors synthesized based on the 4-valued semantics of ltl ( rv-ltl ) may result in inconsistent distributed monitoring, even for some simple ltl formulas. More generally, given any ltl formula φ, we relate the number of different verdicts required by the monitors for consistently monitoring φ, with a specific structural characteristic of φ called its alternation number . Specifically, we show that, for every k ≥ 0 , there is an ltl formula φ with alternation number k that cannot be verified at runtime by distributed monitors emitting verdicts from a set of cardinality smaller than k + 1. On the positive side, we define a family of logics, called distributed ltl (abbreviated as dltl ), parameterized by k ≥ 0, which refines rv-ltl by incorporating 2k + 4 truth values. Our main contribution is to show that, for every k ≥ 0, every ltl formula φ with alternation number k can be consistently monitored by distributed monitors, each running an automaton based on a (2 ⌈ k /2 ⌉ +4)-valued logic taken from the dltl family.
Published: 2016
Full Text: View/download PDF

47. A hierarchy of local decision

Author: Laurent Feuilloley, Juho Hirvonen, Pierre Fraigniaud, Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS), Helsinki Institute for Information Technology (HIIT), Aalto University-University of Helsinki, Department of Information and Computer Science [Aalto], Aalto University-University of Helsinki-Aalto University-University of Helsinki, The first and second authors received additional supports from ANR project DISPLEXITY, and from INRIA project GANG., ANR-11-BS02-0014,DISPLEXITY,Calculabilité et complexité en distribué(2011), Universidad de Chile, Institut de Recherche en Informatique Fondamentale, Professorship Suomela J., Department of Computer Science, Aalto-yliopisto, Aalto University, Networks, Graphs and Algorithms (GANG), 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), Helsingin yliopisto = Helsingfors universitet = University of Helsinki-Aalto University-Helsingin yliopisto = Helsingfors universitet = University of Helsinki-Aalto University, Ioannis Chatzigiannakis Michael Mitzenmacher, Yuval Rabani, Sangiorgi, Davide, Université Sorbonne Paris Cité, Aalto University-Aalto University, and Fraigniaud, Pierre
Subjects: FOS: Computer and information sciences, General Computer Science, Distributed hierarchy, Computer science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Local model, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, 02 engineering and technology, Distributed decision, Gas meter prover, Minimum spanning tree, Mathematical proof, 01 natural sciences, Theoretical Computer Science, Distributed non-determinism, Proof-labeling scheme, [INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], 0202 electrical engineering, electronic engineering, information engineering, [INFO]Computer Science [cs], Locality, Discrete mathematics, Simple graph, Automorphism, Exponential function, Automaton, Distributed Network Computing, Computer Science - Distributed, Parallel, and Cluster Computing, 010201 computation theory & mathematics, Distributed Algorithm, TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS, Local certification, Computer Science::Mathematical Software, 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], MathematicsofComputing_DISCRETEMATHEMATICS
Abstract: We extend the notion of distributed decision in the framework of distributed network computing, inspired by recent results on so-called distributed graph automata. We show that, by using distributed decision mechanisms based on the interaction between a prover and a disprover, the size of the certificates distributed to the nodes for certifying a given network property can be drastically reduced. For instance, we prove that minimum spanning tree can be certified with $O(\log n)$-bit certificates in $n$-node graphs, with just one interaction between the prover and the disprover, while it is known that certifying MST requires $\Omega(\log^2 n)$-bit certificates if only the prover can act. The improvement can even be exponential for some simple graph properties. For instance, it is known that certifying the existence of a nontrivial automorphism requires $\Omega(n^2)$ bits if only the prover can act. We show that there is a protocol with two interactions between the prover and the disprover enabling to certify nontrivial automorphism with $O(\log n)$-bit certificates. These results are achieved by defining and analysing a local hierarchy of decision which generalizes the classical notions of proof-labelling schemes and locally checkable proofs., Comment: 16 pages, 1 figure
Published: 2016
Full Text: View/download PDF

48. A tie-break model for graph search

Author: Antoine Mamcarz, Michel Habib, Derek G. Corneil, Fabien de Montgolfier, Jérémie Dusart, Department of Computer Science [University of Toronto] (DCS), University of Toronto, Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), 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), and Centre National de la Recherche Scientifique (CNRS)-Université Paris Diderot - Paris 7 (UPD7)
Subjects: FOS: Computer and information sciences, BFS, Bidirectional search, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], multi-sweep algorithms, 0102 computer and information sciences, 02 engineering and technology, DFS, tie-break mechanisms, 01 natural sciences, Computer Science - Data Structures and Algorithms, 0202 electrical engineering, electronic engineering, information engineering, Discrete Mathematics and Combinatorics, Data Structures and Algorithms (cs.DS), [INFO]Computer Science [cs], Distributed File System, Mathematics, Discrete mathematics, Applied Mathematics, Formalism (philosophy of mathematics), 010201 computation theory & mathematics, Graph (abstract data type), Graph search model, 020201 artificial intelligence & image processing, LBFS, LDFS
Abstract: International audience; In this paper, we consider the problem of the recognition of various kinds of orderings produced bygraph searches. To this aim, we introduce a new framework, the Tie-Breaking Label Search (TBLS),in order to handle a broad variety of searches. This new model is based on partial orders denedon the label set and it unies the General Label Search (GLS) formalism of Krueger, Simonet andBerry (2011), and the \pattern-conditions" formalism of Corneil and Krueger (2008). It allowsus to derive some general properties including new pattern-conditions (yielding memory-ecientcerticates) for many usual searches, including BFS, DFS, LBFS and LDFS. Furthermore, thenew model allows easy expression of multi-sweep uses of searches that depend on previous (search)orderings of the graph's vertex set.
Published: 2016

49. Locality in Distributed Graph Algorithms

Author: Pierre Fraigniaud, Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Networks, Graphs and Algorithms (GANG), 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, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)
Subjects: Network computing, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, 02 engineering and technology, Maximal Independent Set, 01 natural sciences, Combinatorics, Physics::Popular Physics, Network Computing, Computability theory, 020204 information systems, 0202 electrical engineering, electronic engineering, information engineering, Coloring, Connectivity, Mathematics, Locality, Mathematics::History and Overview, 020206 networking & telecommunications, 16. Peace & justice, Computer Science::Computers and Society, Decidability, Colored, Distributed algorithm, 010201 computation theory & mathematics, Maximal independent set, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Distributed Computing
Abstract: In the context of distributed network computing, an important concern is the ability to design local algorithms, that is, distributed algorithms in which every node (Each node is a computing entity, which has the ability to exchange messages with its neighbors in the network along its communication links.) of the network can deliver its result after having consulted only nodes in its vicinity. The word “vicinity” has a rather vague interpretation in general. Nevertheless, the objective is commonly to design algorithms in which every node outputs after having exchanged information with nodes at constant distance from it (i.e., at distance independent of the number of nodes n in the networks) or at distance at most polylogarithmic in n, but certainly significantly smaller than n or than the diameter of the network. The tasks to be solved by distributed algorithms acting in networks can be formalized as follows. The network itself is modeled by an undirected connected graph G with node set V.G/ and edge set E.G/, without loops and double edges. In the sequel, by graph we are only referring to this specific type of graphs. Nodes are labeled by a function ` W V ! f0; 1g that assigns to every node v its label `.v/. A pair .G; `/, where G is a graph and ` is a labeling of G, is called configuration, and a collection L of configurations is called a distributed language. A typical example of a distributed language is: Lproperly colored D f.G; `/ W `.v/ ¤ `.v0/ for all fv; v0g 2 E.G/g. Unless specified otherwise, we are always assuming that the considered languages are decidable in the sense of classical (sequential) computability theory. To every distributed language L can be associated a construction task which consists in computing the appropriate labels for a given network (Here, we are restricting ourselves to input-free construction tasks, but the content of this chapter can be generalized to tasks with inputs, in which case the labels are input-output pairs, and, given the inputs, the nodes must produce the appropriate outputs to fit in the considered language.)
Published: 2016

50. Core-periphery clustering and collaboration networks

Author: Pierluigi Crescenzi, Pierre Fraigniaud, Zvi Lotker, Paolo Penna, 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), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Dipartimento di Ingegneria dell'Informazione [Firenze] (DINFO), Università degli Studi di Firenze = University of Florence (UniFI), Ben-Gurion University of the Negev (BGU), Eidgenössische Technische Hochschule - Swiss Federal Institute of Technology [Zürich] (ETH Zürich), Università degli Studi di Firenze = University of Florence [Firenze] (UNIFI), Università degli Studi di Firenze [Firenze], and Eidgenössische Technische Hochschule - Swiss Federal Institute of Technology in Zürich [Zürich] (ETH Zürich)
Subjects: 020204 information systems, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, 02 engineering and technology, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], ComputingMilieux_MISCELLANEOUS
Abstract: International audience
Published: 2016

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

118 results on '"Networks, Graphs and Algorithms (GANG)"'

Search Results

Catalog

Select search scope, currently: Articles

Catalog

books, media & more in Jio Institute collections

Articles

journal articles & other e-resources