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

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

Start Over Author "Networks, Graphs and Algorithms (GANG)"

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

151. Termination of the Iterated Strong-Factor Operator on Multipartite Graphs

Author: Christophe Crespelle, Thi Ha Duong Phan, The Hung Tran, Dynamic Networks : Temporal and Structural Capture Approach (DANTE), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), É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), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS)-Institut Rhône-Alpin des systèmes complexes (IXXI), École normale supérieure - Lyon (ENS Lyon)-Université Lumière - Lyon 2 (UL2)-Université Joseph Fourier - Grenoble 1 (UJF)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Lumière - Lyon 2 (UL2)-Université Joseph Fourier - Grenoble 1 (UJF)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS), Vietnam Academy of Science and Technology (VAST), 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), É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), and École normale supérieure de Lyon (ENS de Lyon)-Université Lumière - Lyon 2 (UL2)-Université Joseph Fourier - Grenoble 1 (UJF)-Université Jean Moulin - Lyon 3 (UJML)
Subjects: Hutchinson operator, Discrete mathematics, General Computer Science, Finite-rank operator, Compact operator, Shift operator, Theoretical Computer Science, Quasinormal operator, Semi-elliptic operator, Combinatorics, Pseudo-monotone operator, Multiplication operator, [INFO]Computer Science [cs], ComputingMilieux_MISCELLANEOUS, Mathematics
Abstract: International audience; The clean-factor operator is a multipartite graph operator that has been introduced in the context of complex network modelling. Here, we consider a less constrained variation of the clean-factor operator, named strong-factor operator, and we prove that, as for the clean-factor operator, the iteration of the strong-factor operator always terminates, independently of the graph given as input. Obtaining termination for all graphs using minimal constraints on the definition of the operator is crucial for the modelling purposes for which the clean-factor operator has been introduced. Moreover we show that the relaxation of constraints we operate not only preserves termination but also preserves the termination time, in the sense that the strong-factor series always terminates before the clean-factor series. In addition to those results, we answer an open question from Latapy et al. [12] by showing that the iteration of the factor operator, which is a proper relaxation of both operators mentioned above, does not always terminate.
Published: 2015

152. Nonclassicality of Temporal Correlations

Author: Marcin Markiewicz, Adrian Kosowski, Stephen Brierley, Tomasz Paterek, Anna Przysiezna, School of Physical and Mathematical Sciences, Heilbronn Institute for Mathematical Research, University of Bristol [Bristol], 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), Institute of Theoretical Physics and Astrophysics [Univ Gdańsk] (IFTIA), Faculty of Mathematics, Physics and Informatics [Univ Gdańsk], University of Gdańsk (UG)-University of Gdańsk (UG), Nanyang Technological University [Singapour], and National University of Singapore (NUS)
Subjects: Physics, [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], Sequence, Quantum Physics, Property (programming), General Physics and Astronomy, Contrast (statistics), FOS: Physical sciences, Physics & Applied Physics, 01 natural sciences, 010305 fluids & plasmas, [PHYS.QPHY]Physics [physics]/Quantum Physics [quant-ph], Qubit, 0103 physical sciences, Content (measure theory), Quantum system, Statistical physics, Quantum information, 010306 general physics, Quantum Physics (quant-ph), Quantum
Abstract: The results of space-like separated measurements are independent of distant measurement settings, a property one might call two-way no-signalling. In contrast, time-like separated measurements are only one-way no-signalling since the past is independent of the future but not vice-versa. For this reason temporal correlations that are formally identical to non-classical spatial correlations can still be modelled classically. We define non-classical temporal correlations as the ones which cannot be simulated by propagating in time a classical information content of a quantum system. We first show that temporal correlations between results of any projective quantum measurements on a qubit can be simulated classically. Then we present a sequence of POVM measurements on a single $m$-level quantum system that cannot be explained by propagating in time $m$-level classical system and using classical computers with unlimited memory., 6 pages, 1 figure
Published: 2015

153. LiveRank: How to Refresh Old Crawls

Author: The Dang Huynh, Fabien Mathieu, Laurent Viennot, 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), Alcatel-Lucent Bell Labs France [Nozay], Alcatel-Lucent Bell Labs France, 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), and Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)
Subjects: Computer science, media_common.quotation_subject, Liveness, crawl, 02 engineering and technology, Hyperlink, Focused crawler, LiveRank, law.invention, Ranking (information retrieval), World Wide Web, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], PageRank, law, 020204 information systems, Web page, 0202 electrical engineering, electronic engineering, information engineering, Pagerank, 020201 artificial intelligence & image processing, Fraction (mathematics), Quality (business), media_common
Abstract: International audience; This paper considers the problem of refreshing a crawl. More precisely, given a collection of Web pages (with hyperlinks) gathered at some time, we want to identify a significant fraction of these pages that still exist at present time. The liveness of an old page can be tested through an online query at present time. We call LiveRank a ranking of the old pages so that active nodes are more likely to appear first. The quality of a LiveRank is measured by the number of queries necessary to identify a given fraction of the alive pages when using the LiveRank order. We study different scenarios from a static setting where the LiveRank is computed before any query is made, to dynamic settings where the LiveRank can be updated as queries are processed. Our results show that building on the PageRank can lead to efficient LiveRanks for Web graphs.
Published: 2014

154. Randomized distributed decision

Author: Mika Göös, David Peleg, Amos Korman, Merav Parter, Pierre Fraigniaud, Department of Computer Science and Applied Mathematics [Rehovot], Weizmann Institute of Science [Rehovot, Israël], 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), and University of Toronto
Subjects: Boosting (machine learning), Theoretical computer science, Computer Networks and Communications, Computer science, 020206 networking & telecommunications, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Theoretical Computer Science, Randomized algorithm, Computational Theory and Mathematics, 010201 computation theory & mathematics, Hardware and Architecture, Distributed decision, Distributed algorithm, Theory of computation, 0202 electrical engineering, electronic engineering, information engineering, Complexity class, Distributed language, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Computer communication networks, ComputingMilieux_MISCELLANEOUS
Abstract: The paper tackles the power of randomization in the context of local distributed computing by analyzing the ability to "boost" the success probability of deciding a distributed language using a Monte-Carlo algorithm. We prove that, in many cases, the ability to increase the success probability for deciding distributed languages is rather limited. This contrasts with the sequential computing setting where boosting can systematically be achieved by repeating the randomized execution.
Published: 2014

155. Caesar: A Content Router for High-Speed Forwarding on Content Names

Author: Roger Boislaigue, Leonardo Linguaglossa, Rafael Laufer, Diego Perino, Matteo Varvello, Alcatel-Lucent Bell Labs, Alcatel Lucent Bell Labs, ALCATEL-ALCATEL, 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), 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: Router, router, Virtual routing and forwarding, architecture, Computer science, business.industry, computer.internet_protocol, Routing table, Packet processing, IP forwarding, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], networking, Packet forwarding, computer.software_genre, Bidirectional Forwarding Detection, ICN, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], Operating system, Forwarding plane, forwarding, [INFO]Computer Science [cs], business, computer, Computer network
Abstract: International audience; Internet users are interested in content regardless of its location; however, the current client/server architecture still requires requests to be directed to a specific server. Information-centric networking (ICN) is a recent vein that relaxes this requirement through the use of name-based forwarding, where forwarding decisions are based on content names instead of IP addresses. Despite previous name-based forwarding strategies have been proposed, almost none have actually built a content router. To fill this gap, in this paper we design and prototype a content router called Caesar for high-speed forwarding on content names. Caesar introduces several innovative features, including (i) a longest-prefix matching algorithm based on a novel data structure called prefix Bloom filter; (ii) an incremental design which allows for easy integration with existing protocols and network equipment; (iii) a forwarding scheme where multiple line cards collaborate in a distributed fashion; and (iv) support for offloading packet processing to graphics processing units (GPUs). We build Caesar as an enterprise router, and show that every line card sustains up to 10 Gbps using a forwarding table with more than 10 million content prefixes. Distributed forwarding allows the forwarding table to grow even further, and to scale linearly with the number of line cards at the cost of only a few microseconds in the packet processing latency. GPU offloading, in turn, trades off a few milliseconds of latency for a large speedup in the forwarding rate.
Published: 2014

156. Fair Synchronization in the Presence of Process Crashes and its Weakest Failure Detector

Author: Hugues Fauconnier, Carole Delporte-Gallet, Michel Raynal, 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), 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), 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)-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), ANR-11-BS02-0014,DISPLEXITY,Calculabilité et complexité en distribué(2011), SYSTÈMES LARGE ÉCHELLE (IRISA-D1), 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, and Institut National de Recherche en Informatique et en Automatique (Inria)
Subjects: Fairness, Computer science, Distributed computing, Concurrency, [SCCO.COMP]Cognitive science/Computer science, Context (language use), Crash, 0102 computer and information sciences, 02 engineering and technology, Synchronization, 01 natural sciences, Process scheduling, Synchronization (computer science), 0202 electrical engineering, electronic engineering, information engineering, Read/write shared memory, Asynchronous system, Process crash, Failure detector, Wait-freedom, 020203 distributed computing, business.industry, Process (computing), Non-blocking progress property, Modular design, Computer engineering, 010201 computation theory & mathematics, Asynchronous communication, Multicore, business, Starvation freedom
Abstract: International audience; A non-blocking implementation of a concurrentobject is an implementation that does not prevent concurrentaccesses to the internal representation of the object, whileguaranteeing the deadlock-freedom progress condition withoutusing locks. Considering a failure free context, G. Taubenfeldhas introduced (DISC 2013) a simple modular approach,captured under a new problem called the fair synchronizationproblem, to transform a non-blocking implementation intoa starvation-free implementation satisfying a strong fairnessrequirement. This paper extends this approach in severaldirections. It first generalizes the fair synchronization problemto read/write asynchronous systems where any number ofprocesses may crash. Then, it introduces a new failure detectorand uses it to solve the fair synchronization problem whenprocesses may crash. This failure detector, denoted QP (QuasiPerfect), is very close to, but strictly weaker than, the perfectfailure detector. Last but not least, the paper shows that theproposed failure detector QP is optimal in the sense that theinformation on failures it provides to the processes can beextracted from any algorithm solving the fair synchronizationproblem in the presence of any number of process crashfailures.
Published: 2014

157. Confidence Sharing: An Economic Strategy for Efficient Information Flows in Animal Groups

Author: Amos Korman, Ofer Feinerman, Efrat Greenwald, 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), Ant Collective Behavior Group, and Weizmann Institute of Science [Rehovot, Israël]
Subjects: Computer and Information Sciences, Theoretical computer science, Computer science, Computation, Information Theory, Population Modeling, Context (language use), Information theory, Mathematical proof, Models, Biological, Reduction (complexity), Cellular and Molecular Neuroscience, Channel capacity, Cognition, Genetics, Animals, Limit (mathematics), Molecular Biology, Animal Signaling and Communication, lcsh:QH301-705.5, Ecology, Evolution, Behavior and Systematics, ComputingMilieux_MISCELLANEOUS, Ecology, Animal Behavior, business.industry, Information Dissemination, Information sharing, Communication, [SDV.BA]Life Sciences [q-bio]/Animal biology, Biology and Life Sciences, Computational Biology, Collective Animal Behavior, Animal Cognition, [SDV.BIBS]Life Sciences [q-bio]/Quantitative Methods [q-bio.QM], [MATH.MATH-PR]Mathematics [math]/Probability [math.PR], Computational Theory and Mathematics, Social Networks, lcsh:Biology (General), Modeling and Simulation, Cognitive Science, Artificial intelligence, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], business, Zoology, Network Analysis, Algorithms, Research Article, Neuroscience
Abstract: Social animals may share information to obtain a more complete and accurate picture of their surroundings. However, physical constraints on communication limit the flow of information between interacting individuals in a way that can cause an accumulation of errors and deteriorated collective behaviors. Here, we theoretically study a general model of information sharing within animal groups. We take an algorithmic perspective to identify efficient communication schemes that are, nevertheless, economic in terms of communication, memory and individual internal computation. We present a simple and natural algorithm in which each agent compresses all information it has gathered into a single parameter that represents its confidence in its behavior. Confidence is communicated between agents by means of active signaling. We motivate this model by novel and existing empirical evidences for confidence sharing in animal groups. We rigorously show that this algorithm competes extremely well with the best possible algorithm that operates without any computational constraints. We also show that this algorithm is minimal, in the sense that further reduction in communication may significantly reduce performances. Our proofs rely on the Cramér-Rao bound and on our definition of a Fisher Channel Capacity. We use these concepts to quantify information flows within the group which are then used to obtain lower bounds on collective performance. The abstract nature of our model makes it rigorously solvable and its conclusions highly general. Indeed, our results suggest confidence sharing as a central notion in the context of animal communication., Author Summary Cooperative groups are abundant on all scales of the biological world. Despite much empirical evidence on a wide variety of natural communication schemes, there is still a growing need for rigorous tools to quantify and understand the information flows involved. Here, we borrow techniques from information theory and theoretical distributed computing to study information sharing within animal groups. We consider a group of individuals that integrate personal and social information to obtain improved knowledge of their surroundings. We rigorously show that communication between such individuals can be compressed into simple messages that contain an opinion and a corresponding confidence parameter. While this algorithm is extremely efficient, further reduction in communication capacity may greatly hamper collective performances.
Published: 2014

158. On Proof-Labeling Schemes versus Silent Self-stabilizing Algorithms

Author: Boaz Patt-Shamir, Lélia Blin, Pierre Fraigniaud, Université d'Évry-Val-d'Essonne (UEVE), Networks and Performance Analysis (NPA), Laboratoire d'Informatique de Paris 6 (LIP6), Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-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, 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 Engineering, Tel Aviv University (TAU), Pascal Felber, Vijay Garg, ANR-11-BS02-0014,DISPLEXITY,Calculabilité et complexité en distribué(2011), and Tel Aviv University [Tel Aviv]
Subjects: Leader election, Scheme (mathematics), Converse, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Binary strings, Space (mathematics), Time complexity, Algorithm, Mathematics, Running time, Linear number
Abstract: It follows from the definition of silent self-stabilization, and from the definition of proof-labeling scheme, that if there exists a silent self-stabilizing algorithm using l-bit registers for solving a task ${\mathcal{T}} $, then there exists a proof-labeling scheme for ${\mathcal{T}} $ using registers of at most l bits. The first result in this paper is the converse to this statement. We show that if there exists a proof-labeling scheme for a task ${\mathcal{T}} $, using l-bit registers, then there exists a silent self-stabilizing algorithm using registers of at most O(l + logn) bits for solving ${\mathcal{T}} $, where n is the number of processes in the system. Therefore, as far as memory space is concerned, the design of silent self-stabilizing algorithms essentially boils down to the design of compact proof-labeling schemes. The second result in this paper addresses time complexity. We show that, for every task ${\mathcal{T}} $ with k-bits output size in n-node networks, there exists a silent self-stabilizing algorithm solving ${\mathcal{T}} $ in O(n) rounds, using registers of O(n 2 + kn) bits. Therefore, as far as running time is concerned, every task has a silent self-stabilizing algorithm converging in a linear number of rounds.
Published: 2014

159. A High Speed Information-Centric Network in a Mobile Backhaul Setting

Author: Roger Boislaigue, Matteo Varvello, Massimo Gallo, Diego Perino, Giovanna Carofiglio, Zied Ben Houidi, Leonardo Linguaglossa, Luca Muscariello, Alcatel-Lucent Bell Labs, Alcatel Lucent Bell Labs, ALCATEL-ALCATEL, 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), 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), Orange Labs [Paris], and Telecom Orange
Subjects: Router, router, architecture, business.industry, Computer science, ComputerSystemsOrganization_COMPUTER-COMMUNICATIONNETWORKS, protocols, 020206 networking & telecommunications, 02 engineering and technology, ICN, Backhaul (telecommunications), [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], User experience design, 0202 electrical engineering, electronic engineering, information engineering, Forwarding plane, Cellular network, forwarding, Network providers, business, Computer network
Abstract: International audience; We demonstrate a high speed Information-Centric Network in a mobile backhaul setting. Specifically, we show the fea-sibility of an information aware data plane and we highlight the significant benefits it provides in terms of both user ex-perience and network provider cost in the backhaul setting. Our setup consists of high-speed ICN devices employed in a down-scaled realistic representation of a mobile backhaul topology, fed with traffic workloads characterized from Or-ange's mobile network.
Published: 2014

160. An Exercise in Concurrency: From Non-blocking Objects to Fair Objects

Author: Michel Raynal, Hugues Fauconnier, Carole Delporte, 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), 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), 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), ANR-11-BS02-0014,DISPLEXITY,Calculabilité et complexité en distribué(2011), 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), and 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)
Subjects: Computer science, business.industry, Distributed computing, Concurrency, [SCCO.COMP]Cognitive science/Computer science, Context (language use), Modular design, 16. Peace & justice, Object (computer science), Blocking (computing), Synchronization (computer science), Concurrent computing, business, Representation (mathematics), ComputingMilieux_MISCELLANEOUS
Abstract: A non-blocking implementation of a concurrent object is an implementation that does not prevent concurrent accesses to the internal representation of the object, while guaranteeing the deadlock-freedom progress condition without using locks. Considering a failure free context, this paper presents a simple modular approach to transform a non-blocking implementation into a starvation-free implementation satisfying a strong fairness requirement. This approach, which is due to G. Taubenfeld, is illustrated with the implementation of a concurrent stack. The spirit of the paper is mainly pedagogical. Its aim is not to introduce new concepts or algorithms, but to show that a powerful, simple, and modular transformation can provide concurrent objects with strong fairness properties.
Published: 2014

161. Graphs with large chromatic number induce $3k$-cycles

Author: Bonamy, Marthe, Thomassé, Stéphan, Charbit, Pierre, 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), 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), 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), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), 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, and École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL)
Subjects: FOS: Computer and information sciences, Mathematics::Combinatorics, Discrete Mathematics (cs.DM), [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Computer Science - Discrete Mathematics
Abstract: Answering a question of Kalai and Meshulam, we prove that graphs without induced cycles of length $3k$ have bounded chromatic number. This implies the very first case of a much broader question asserting that every graph with large chromatic number induces a graph $H$ such that the sum of the Betti numbers of the independence complex of $H$ is also large., 13 pages
Published: 2014

162. Influence of the tie-break rule on the end-vertex problem

Author: Pierre Charbit, Antoine Mamcarz, Michel Habib, 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), and ANR-10-JCJC-0204,HEREDIA,Classes héréditaires de graphes(2010)
Subjects: Factor-critical graph, General Computer Science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Interval graph, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Theoretical Computer Science, law.invention, [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], Combinatorics, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], Lexicographic breadth-first search, law, Graph power, Chordal graph, Line graph, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], Discrete Mathematics and Combinatorics, Cubic graph, Mathematics, Distance-hereditary graph
Abstract: End-vertices of a given graph search may have some nice properties, as for example it is well known that the last vertex of Lexicographic Breadth First Search (LBFS) in a chordal graph is simplicial, see Rose, Tarjan and Lueker 1976. Therefore it is interesting to consider if these vertices can be recognized in polynomial time or not, as first studied in Corneil, Köhler and Lanlignel 2010. A graph search is a mechanism for systematically visiting the vertices of a graph. At each step of a graph search, the key point is the choice of the next vertex to be explored. Graph searches only differ by this selection mechanism during which a tie-break rule is used. In this paper we study how the choice of the tie-break in case of equality during the search, for a given graph search including the classic ones such as BFS and DFS, can determine the complexity of the end-vertex problem. In particular we prove a counterintuitive NP-completeness result for Breadth First Search solving a problem raised in Corneil, Köhler and Lanlignel 2010.
Published: 2014

163. Décision et vérification distribuées dans le modèle local

Author: Arfaoui, Heger, 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), Paris Diderot University, and Pierre Fraigniaud
Subjects: distribué, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], distriubted, local, verification, vérification
Abstract: This thesis lays in the context of distributed computing on networks, and more particularlyon the locality aspects that appear in that context. By the systematic studyof decision problems, we introduce the complexity classes ULD and UNLD for localdecision and verication respectively, and give separation results describing a hierarchyinvolving other classes of local decision in the literature. These results areaccompanied by a classication of several distributed problems based on the hierarchywe introduce. We examine and discuss two key ingredients in local decision andverication: the interpretation function on the outputs, and node identication.In this thesis, we also isolate the aspect of locality by studying it through theprism of the non-signaling model, which, even though not realistic, oers interestingtheoretical possibilities, including the derivation of lower bounds for distributedquantum computing without having to manipulate objects of that theory. Finally,by placing ourselves at the extreme limit of locality constraints, we consider the particularclass of two-player games in absence of any communication and examine thelimits of quantum distributed computing for this class of games.; Cette thèse s'inscrit dans le contexte du calcul distribué sur les réseaux, et,plus particulièrement, sur les aspects de localité qui apparaissent dans cecadre. Par l'étude systématique des problèmes de décision, nous introduisonsles classes de complexité ULD et UNLD pour la décision et la vérificationlocale, et présentons des résultats de séparation décrivant une hiérarchieimpliquant d'autres classes relatives à la littérature de la décisionlocale. Ces résultats sont accompagnés de la classification de plusieursproblèmes distribués selon la hiérarchie introduite. Nous examinons etdiscutons dans ce cadre deux ingrédients ayant un rôle clé dans la décision etla vérification locale : la fonction d'interprétation des sorties, etl'identification des noeuds du réseau.Nous isolons également dans cette thèse l'aspect de la localité en l'étudiantsous le prisme du modèle "non-signalling", qui bien que n'étant pas un modèleréaliste, ouvre des possibilités théoriques intéressantes, notamment sur ladérivation de bornes inférieures pour le calcul distribué quantique, sans avoirà manipuler les objets de cette théorie. Finalement, en nous plaçant à lalimite extrême des contraintes de localité, nous considérons la classeparticulière de jeux à deux joueurs en l'absence de communication, et examinonsles limites du calcul distribué quantique pour cette classe de jeux.
Published: 2014

164. Local Distributed Decision and Verification

Author: Arfaoui, Heger, 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), Paris Diderot University, and Pierre Fraigniaud
Subjects: distribué, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], distriubted, local, verification, vérification
Abstract: This thesis lays in the context of distributed computing on networks, and more particularlyon the locality aspects that appear in that context. By the systematic studyof decision problems, we introduce the complexity classes ULD and UNLD for localdecision and verication respectively, and give separation results describing a hierarchyinvolving other classes of local decision in the literature. These results areaccompanied by a classication of several distributed problems based on the hierarchywe introduce. We examine and discuss two key ingredients in local decision andverication: the interpretation function on the outputs, and node identication.In this thesis, we also isolate the aspect of locality by studying it through theprism of the non-signaling model, which, even though not realistic, oers interestingtheoretical possibilities, including the derivation of lower bounds for distributedquantum computing without having to manipulate objects of that theory. Finally,by placing ourselves at the extreme limit of locality constraints, we consider the particularclass of two-player games in absence of any communication and examine thelimits of quantum distributed computing for this class of games.; Cette thèse s'inscrit dans le contexte du calcul distribué sur les réseaux, et,plus particulièrement, sur les aspects de localité qui apparaissent dans cecadre. Par l'étude systématique des problèmes de décision, nous introduisonsles classes de complexité ULD et UNLD pour la décision et la vérificationlocale, et présentons des résultats de séparation décrivant une hiérarchieimpliquant d'autres classes relatives à la littérature de la décisionlocale. Ces résultats sont accompagnés de la classification de plusieursproblèmes distribués selon la hiérarchie introduite. Nous examinons etdiscutons dans ce cadre deux ingrédients ayant un rôle clé dans la décision etla vérification locale : la fonction d'interprétation des sorties, etl'identification des noeuds du réseau.Nous isolons également dans cette thèse l'aspect de la localité en l'étudiantsous le prisme du modèle "non-signalling", qui bien que n'étant pas un modèleréaliste, ouvre des possibilités théoriques intéressantes, notamment sur ladérivation de bornes inférieures pour le calcul distribué quantique, sans avoirà manipuler les objets de cette théorie. Finalement, en nous plaçant à lalimite extrême des contraintes de localité, nous considérons la classeparticulière de jeux à deux joueurs en l'absence de communication, et examinonsles limites du calcul distribué quantique pour cette classe de jeux.
Published: 2014

165. Rendezvous of Distance-aware Mobile Agents in Unknown Graphs

Author: Das, Shantanu, Dereniowski, Dariusz, Kosowski, Adrian, Uznanski, Przemyslaw, Laboratoire d'informatique Fondamentale de Marseille (LIF), Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU), Department of Algorithms and Systems Modelling [ETI GUT] (Gdansk University of Technology), Faculty of Electronics, Telecommunications and Informatics [GUT Gdańsk] (ETI), Gdańsk University of Technology (GUT)-Gdańsk University of Technology (GUT), 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), ANR-11-BS02-0014,DISPLEXITY,Calculabilité et complexité en distribué(2011), and Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS)
Subjects: FOS: Computer and information sciences, Computer Science::Multiagent Systems, Lower Bounds, Anonymous Networks, Rendezvous, Computer Science - Data Structures and Algorithms, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Data Structures and Algorithms (cs.DS), Distance Oracle, Mobile Agent, Synchronous
Abstract: International audience; We study the problem of rendezvous of two mobile agents starting at distinct locations in an unknown graph. The agents have distinct labels and walk in synchronous steps. However the graph is unlabelled and the agents have no means of marking the nodes of the graph and cannot communicate with or see each other until they meet at a node. When the graph is very large we want the time to rendezvous to be independent of the graph size and to depend only on the initial distance between the agents and some local parameters such as the degree of the vertices, and the size of the agent's label. It is well known that even for simple graphs of degree $\Delta$, the rendezvous time can be exponential in $\Delta$ in the worst case. In this paper, we introduce a new version of the rendezvous problem where the agents are equipped with a device that measures its distance to the other agent after every step. We show that these \emph{distance-aware} agents are able to rendezvous in any unknown graph, in time polynomial in all the local parameters such the degree of the nodes, the initial distance $D$ and the size of the smaller of the two agent labels $l = \min(l_1, l_2)$. Our algorithm has a time complexity of $O(\Delta(D+\log{l}))$ and we show an almost matching lower bound of $\Omega(\Delta(D+\log{l}/\log{\Delta}))$ on the time complexity of any rendezvous algorithm in our scenario. Further, this lower bound extends existing lower bounds for the general rendezvous problem without distance awareness.
Published: 2014

166. Breathe before speaking: efficient information dissemination despite noisy, limited and anonymous communication

Author: Bernhard Haeupler, Amos Korman, Ofer Feinerman, Ant Collective Behavior Group, Weizmann Institute of Science [Rehovot, Israël], Microsoft Research Silicon Valley, Microsoft Corporation [Redmond, Wash.], 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), 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, Weizmann Institute of Science, Computer Science Department - Carnegie Mellon University, University of Pittsburgh (PITT), and Pennsylvania Commonwealth System of Higher Education (PCSHE)-Pennsylvania Commonwealth System of Higher Education (PCSHE)
Subjects: FOS: Computer and information sciences, Theoretical computer science, Computer Networks and Communications, Computer science, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Theoretical Computer Science, 03 medical and health sciences, Gossip, Synchronization (computer science), 0202 electrical engineering, electronic engineering, information engineering, Relevance (information retrieval), ComputingMilieux_MISCELLANEOUS, 030304 developmental biology, 0303 health sciences, Focus (computing), business.industry, [SDV.BA]Life Sciences [q-bio]/Animal biology, 020206 networking & telecommunications, Communication noise, Asymptotically optimal algorithm, Computer Science - Distributed, Parallel, and Cluster Computing, Computational Theory and Mathematics, Transmission (telecommunications), 010201 computation theory & mathematics, Hardware and Architecture, Models of communication, Theory of computation, Distributed, Parallel, and Cluster Computing (cs.DC), [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], business, Error detection and correction, Computer network
Abstract: Distributed computing models typically assume reliable communication between processors. While such assumptions often hold for engineered networks, e.g., due to underlying error correction protocols, their relevance to biological systems, wherein messages are often distorted before reaching their destination, is quite limited. In this study we take a first step towards reducing this gap by rigorously analyzing a model of communication in large anonymous populations composed of simple agents which interact through short and highly unreliable messages. We focus on the broadcast problem and the majority-consensus problem. Both are fundamental information dissemination problems in distributed computing, in which the goal of agents is to converge to some prescribed desired opinion. We initiate the study of these problems in the presence of communication noise. Our model for communication is extremely weak and follows the push gossip communication paradigm: In each round each agent that wishes to send information delivers a message to a random anonymous agent. This communication is further restricted to contain only one bit (essentially representing an opinion). Lastly, the system is assumed to be so noisy that the bit in each message sent is flipped independently with probability $$1/2-\epsilon $$ , for some small $$\epsilon >0$$ . Even in this severely restricted, stochastic and noisy setting we give natural protocols that solve the noisy broadcast and majority-consensus problems efficiently. Our protocols run in $$O(\log n/\epsilon ^2)$$ rounds and use $$O(n \log n / \epsilon ^2)$$ messages/bits in total, where n is the number of agents. These bounds are asymptotically optimal and, in fact, are as fast and message efficient as if each agent would have been simultaneously informed directly by an agent that knows the prescribed desired opinion. Our efficient, robust, and simple algorithms suggest balancing between silence and transmission, synchronization, and majority-based decisions as important ingredients towards understanding collective communication schemes in anonymous and noisy populations.
Published: 2014

167. Colored Modular and Split Decompositions of Graphs with Applications to Trigraphs

Author: Antoine Mamcarz, Michel Habib, 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: graph algorithms, Computer science, trigraphs, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], modular decomposition, 0102 computer and information sciences, 01 natural sciences, ACM: G.: Mathematics of Computing, Combinatorics, [INFO]Computer Science [cs], Graph algorithms, 0101 mathematics, Time complexity, ComputingMilieux_MISCELLANEOUS, Discrete mathematics, business.industry, 010102 general mathematics, Modular design, ACM: F.: Theory of Computation, Graph, Modular decomposition, Colored, 010201 computation theory & mathematics, Trigraph, split decomposition, business, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract: We introduce the colored decompositions framework, in which vertices of the graph can be equipped with colors, and in which the goal is to find decompositions of this graph that do not separate the color classes. In this paper, we give two linear time algorithms for the colored modular and split decompositions of graphs, and we apply them to give linear time algorithms for the modular and split decompositions of trigraphs, which improves a result of Thomasse, Trotignon and Vuskovic (2013). As a byproduct, we introduce the non-separating families that allow us to prove that those two decompositions have the same properties on graphs and on trigraphs.
Published: 2014

168. Distributedly Testing Cycle-Freeness

Author: Pierre Fraigniaud, Fabien Mathieu, Heger Arfaoui, David Ilcinkas, 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), 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), 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), Alcatel Lucent Bell Labs, ALCATEL, See paper for details., ANR-11-BS02-0014,DISPLEXITY,Calculabilité et complexité en distribué(2011), and Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)
Subjects: [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], Central authority, Theoretical computer science, Property (programming), Node (networking), Free group, Distributed testing, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Appropriate use, Graph property, Wireless sensor network, Mathematics
Abstract: International audience; We tackle \emph{local distributed testing} of graph properties. This framework is well suited to contexts in which data dispersed among the nodes of a network can be collected by some central authority (like in, e.g., sensor networks). In local distributed testing, each node can provide the central authority with just a few information about what it perceives from its neighboring environment, and, based on the collected information, the central authority is aiming at deciding whether or not the network satisfies some property. We analyze in depth the prominent example of checking \emph{cycle-freeness}, and establish tight bounds on the amount of information to be transferred by each node to the central authority for deciding cycle-freeness. In particular, we show that distributedly testing cycle-freeness requires at least $\lceil{\log d}\rceil-1$ bits of information per node in graphs with maximum degree~$d$, even for connected graphs. Our proof is based on a novel version of the seminal result by Naor and Stockmeyer (1995) enabling to reduce the study of certain kinds of algorithms to order-invariant algorithms, and on an appropriate use of the known fact that every free group can be linearly ordered.
Published: 2014

169. Reducing Manipulability

Author: Durand, François, Mathieu, Fabien, Noirie, Ludovic, 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), 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), Alcatel-Lucent Bell Labs France [Nozay], and Alcatel-Lucent Bell Labs France
Subjects: Manipulability rate, Voting Systems, [INFO.INFO-GT]Computer Science [cs]/Computer Science and Game Theory [cs.GT], [INFO.INFO-MA]Computer Science [cs]/Multiagent Systems [cs.MA], Condorcet Winner
Abstract: International audience; We consider a general framework for voting systems with arbitrary types of ballots such as orders of preference, grades, etc. We investigate their manipulability: in what states of the population may a coalition of electors, by casting an insincere ballot, secure a result that is better from their point of view?We define a straightforward way to make a voting system respect the Condorcet criterion and we prove that, for a large class of voting systems, this Condorcification is at most as manipulable as the original system. Then we exhibit a sufficient condition, which is frequently met, that ensures this improvement to be strict.These results show that the investigation for a reasonable voting system with minimal manipulability can be restricted to systems that meet the Condorcet criterion.
Published: 2014

170. Making most voting systems meet the Condorcet criterion reduces their manipulability

Author: Durand, François, Mathieu, Fabien, Noirie, Ludovic, 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), 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), Alcatel-Lucent Bell Labs France [Nozay], Alcatel-Lucent Bell Labs France, and 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)
Subjects: JEL code : D71, Condorcet winner, Voting systems, manipulability, [SHS.SCIPO]Humanities and Social Sciences/Political science
Abstract: Since any non-trivial voting system is susceptible to manipulation, we investigate how it is possible to reduce the set of situations where it is manipulable, that is, such that a coalition of voters, by casting an insincere ballot, may secure an outcome that is better from their point of view. We prove that, for a large class of voting systems, a simple modiﬁcation allows to reduce manipulability. This modiﬁcation is Condorciﬁcation: when there is a Condorcet winner, designate her; otherwise, use the original rule. Our very general framework allows to do this for any voting system, whatever the form of the original ballots. Hence, when searching for a voting system whose manipulability is minimal, one can restrict to those that meet the Condorcet criterion.; Puisque tout mode de scrutin non trivial est sensible à la manipulation, nous examinons comment il est possible de réduire l'ensemble des situations où il est manipulable, c'est-à-dire où une coalition d'électeurs, en produisant des bulletins non sincère, peuvent obtenir un résultat qui est meilleur de leur point de vue. Nous prouvons que, pour une importante classe de modes de scrutin, une transformation simple permet de réduire la manipulabilité. Cette transformation est la condorcification : quand il y a un vainqueur de Condorcet, il est élu; sinon, on utilise la règle originale. Notre formalisme très général permet de le faire pour tout mode de scrutin, quelle que soit la forme des bulletins dans le mode de scrutin original. Par conséquent, si on cherche un mode de scrutin dont la manipulabilité est minimale (parmi une classe raisonnable), on peut se restreindre à ceux qui vérifient le critère de Condorcet.
Published: 2014

171. Making a voting system depend only on orders of preference reduces its manipulability rate

Author: Durand, François, Mathieu, Fabien, Noirie, Ludovic, 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), 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), Alcatel-Lucent Bell Labs France [Nozay], Alcatel-Lucent Bell Labs France, and 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)
Subjects: Voting system, JEL code : D71, linear orders, Condorcet winner, manipulability, [SHS.SCIPO]Humanities and Social Sciences/Political science
Abstract: For any non-trivial voting system, there exists manipulable situations where a coalition of voters, by casting an insincere ballot, may secure an outcome that is better from their point of view. In this paper, we investigate how it is possible to reduce the manipulability rate, which is the probability of such situations in a given culture, i.e. a probabilistic structure of the population. We prove that when electors are independent, the culture meets a condition that we call decomposability. And when this condition is met, for any voting system that uses more complex ballots than orders of preferences (for example grades), there exists a "reasonable" voting system that depends only on orders of preference and whose manipulability rate is at most as high. Combining this result with Condorciﬁcation theorem from Durand et al. (2014) and Green-Armytage et al. (2014), we conclude that when searching for a "reasonable" voting system whose manipulability is minimal, one can restrict to those that depend only on orders of preference and meet the Condorcet criterion.; Pour tout mode de scrutin non trivial, il existe des situations manipulables où une coalition d'électeurs, en produisant des bulletins non sincères, peut obtenir un résultat qui est meilleur de leur point de vue. Dans ce papier, nous examinons comment il est possible de réduire le taux de manipulabilité, qui est la probabilité d'une telle situation dans une culture donnée, c'est-à-dire une structure probabiliste de la population. Nous prouvons que quand les électeurs sont indépendants, la culture vérifie une condition que nous appelons décomposabilité. Et quand cette condition est vérifiée, pour tout mode de scrutin qui utilise des bulletins plus riches que des ordres de préférence (par exemple des notes), il existe un mode de scrutin raisonnable qui dépend seulement des ordres de préférences et dont le taux de manipulabilité est inférieur ou égal. Combinant ce résultat avec le théorème de condorcification prouvé par Durand et al. (2014) et Green-Armytage et al (2014), nous concluons que si on cherche un mode de scrutin (dans une classe raisonnable) dont la manipulabilité est minimale, on peut se restreindre à ceux qui dépendent uniquement des ordres de préférence et qui vérifient le critère de Condorcet.
Published: 2014

172. Élection d'un chemin dans un réseau : étude de la manipulabilité

Author: Durand, François, Mathieu, Fabien, Noirie, Ludovic, 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), 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), Alcatel-Lucent Bell Labs France [Nozay], and Alcatel-Lucent Bell Labs France
Subjects: Routage multi-opérateurs, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], manipulation, systèmes de vote
Abstract: International audience; Internet est devenu un écosystème économique où interviennent de nombreux acteurs concurrents. Pour les décisions faisant intervenir plusieurs acteurs, il faut un mécanisme équitable qui évite si possible la manipulation du processus de prise de décision par certains. Dans cet article, nous illustrons comment les systèmes de vote peuvent être appliqués sur le cas du choix d'un chemin dans le réseau qui fait intervenir plusieurs opérateurs, et nous montrons que le choix du système de vote a un fort impact sur la manipulabilité du résultat et l'efficacité globale du processus de décision. Une version étendue de cet article a été publiée à ICQT 2013.
Published: 2014

173. Élection du Best Paper AlgoTel 2012 : étude de la manipulabilité

Author: Durand, François, Mathieu, Fabien, Noirie, Ludovic, 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), 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), Alcatel-Lucent Bell Labs France [Nozay], and Alcatel-Lucent Bell Labs France
Subjects: [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], Communauté AlgoTel, Manipulabilité, Systèmes de vote
Abstract: International audience; Les systèmes de vote interviennent dès qu'une décision collective doit être prise pour choisir une option parmi plusieurs, et peuvent se retrouver dans de nombreux contextes : élections politiques, sélection d'un candidat par un comité, décision dans un réseau... Un des problèmes à résoudre est celui de la manipulation, ou vote tactique : le résultat d'une élection peut-il dépendre d'un éventuel vote stratégique d'une partie des électeurs ? Il est connu depuis les années 1970 que tous les systèmes sauf la dictature sont susceptibles d'être manipulés. Peut-être n'est-ce qu'un résultat théorique n'ayant pas beaucoup d'impact en pratique ? Dans cet article, nous répondons à cette question sur un cas concret qui intéressera certainement la communauté AlgoTel : l'élection du Best Paper AlgoTel 2012. Nous nous basons sur les bulletins exprimés pour fournir une étude quantitative de la manipulabilité du résultat en fonction du mode de scrutin. Nous montrons que même dans une situation où il existe a priori un vainqueur canonique, les possibilités de manipulation sont nombreuses et varient suivant le mode de scrutin choisi. Nous observons aussi qu'un mode de scrutin se démarque nettement des autres par sa faible manipulabilité : le vote à tours instantanés.
Published: 2014

174. Allocation adaptative de registres en utilisant un nombre linéaire de registres

Author: Delporte-Gallet, Carole, Fauconnier, Hugues, Gafni, Eli, Lamport, Leslie, 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), Computer Science Department [Los Angeles] (UCLA), University of California [Los Angeles] (UCLA), University of California-University of California, Microsoft Research [Redmond], Microsoft Corporation [Redmond, Wash.], and University of California (UC)-University of California (UC)
Subjects: distributed algorithms, shared memory, wait-free, [SCCO.COMP]Cognitive science/Computer science, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], space complexity, read/write registers, renaming
Abstract: International audience; On présente un algorithme adaptatif dans lequel les processus utilisent des registres multi écrivains multi lecteurs. Cet algorithme permet à chaque processus d'obtenir un accès exclusif à un registre dont il sera l'écrivain unique et que tous les processus pourront lire. L'algorithme est adaptatif : il ne connait pas a priori le nombre de processus qui vont demander un accés exclusif en écriture à un registre. C'est le premier algorithme permettant d'obtenir ce résultat en utilisant des registres dont le nombre est une fonction linéaire du nombre de participants. Les précédents algorithmes adaptatifs utilisent au moins Theta(n^{3/2}) registres.
Published: 2014

175. LiveRank : comment faire du neuf avec du vieux ?

Author: Huynh, The Dang, Mathieu, Fabien, Viennot, Laurent, 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), Alcatel-Lucent Bell Labs France [Nozay], Alcatel-Lucent Bell Labs France, 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), and Mathieu, Fabien
Subjects: PageRank, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], [INFO.INFO-NI] Computer Science [cs]/Networking and Internet Architecture [cs.NI], Graphes du Web, ré-actualisation
Abstract: International audience; Une capture du Web n'est valable qu'à l'instant où elle est faite et se périme ensuite petit à petit. Dans cet article, nous cherchons à savoir comment récupérer d'une ancienne capture un maximum de pages toujours vivantes en un minimum de requêtes. Plus précisément notre contribution est la suivante : nous posons le problème sous la forme du calcul d'un ranking, le LiveRank, qui essaie de séparer les pages mortes des pages vivantes ; nous proposons plusieurs LiveRanks basés sur le PageRank, avec ou sans apprentissage ; nous validons notre approche sur un graphe réel et évaluons numériquement le gain que peut apporter un bon LiveRank.
Published: 2014

176. Distinguishing Views in Symmetric Networks: A Tight Lower Bound

Author: Dominik Pajak, Adrian Kosowski, Dariusz Dereniowski, Department of Algorithms and Systems Modelling [ETI GUT] (Gdansk University of Technology), Faculty of Electronics, Telecommunications and Informatics [GUT Gdańsk] (ETI), Gdańsk University of Technology (GUT)-Gdańsk University of Technology (GUT), 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), Computer Laboratory [Cambridge], University of Cambridge [UK] (CAM), and ANR-11-BS02-0014,DISPLEXITY,Calculabilité et complexité en distribué(2011)
Subjects: FOS: Computer and information sciences, Discrete mathematics, 020203 distributed computing, Discrete Mathematics (cs.DM), General Computer Science, Existential quantification, Node (networking), [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Quotient graph, Theoretical Computer Science, Combinatorics, Tree encoding, 010201 computation theory & mathematics, Computer Science - Data Structures and Algorithms, 0202 electrical engineering, electronic engineering, information engineering, Data Structures and Algorithms (cs.DS), Mathematics, Computer Science - Discrete Mathematics
Abstract: International audience; The view of a node in a port-labeled network is an infinite tree encoding all walks in the network originating from this node. We prove that for any integers $n\geq D\geq 1$, there exists a port-labeled network with at most $n$ nodes and diameter at most $D$ which contains a pair of nodes whose (infinite) views are different, but whose views truncated to depth $\Omega(D\log (n/D))$ are identical.
Published: 2014

177. A separation of (n -1)-consensus and n-consensus in read-write shared-memory systems

Author: Delporte-Gallet, Carole, Fauconnier, Hugues, Toueg, Sam, 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), Department of Computer Science [University of Toronto] (DCS), and University of Toronto
Subjects: shared memory, consensus, [SCCO.COMP]Cognitive science/Computer science
Abstract: A fundamental research theme in distributed computing is the comparison of systems in terms of their ability to solve basic problems such as consensus that cannot be solved in completely asynchronous systems. In particular, in a seminal work [14], Herlihy compares shared-memory systems in terms of the shared objects that they have: he proved that there are shared objects that are powerful enough to solve consensus among n processes, but are too weak to solve consensus among n + 1 processes; such objects are placed at level n of a wait-free hierarchy. The importance of this hierarchy comes from Herlihy's universality result: intuitively, every object at level n of this hierarchy can be used to implement any object shared by n processes in a wait-free manner. As in [14], we compare shared-memory systems with respect to their ability to solve consensus among n processes. But instead of comparing systems defined by the shared objects that they have, we compare readwrite systems defined by the process schedules that they allow. These systems capture a large set of systems, e.g., systems whose synchrony ranges from fully synchronous to completely asynchronous, several systems with failure detectors, and "obstruction-free" systems. In this paper, we consider read-write systems defined in terms of process schedules, and investigate the following natural question: For every n, is there a system of n processes that is strong enough to solve consensus among every subset of n -1 processes in the system, but not enough to solve consensus among all the n processes of the system? We show that the answer to the above question is "yes", and so these systems can be classified into hierarchy akin to Herlihy's hierarchy.
Published: 2014

178. Leader Election in Rings with Homonyms

Author: Hung Tran-The, Hugues Fauconnier, Carole Delporte-Gallet, 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), and ANR-11-BS02-0014,DISPLEXITY,Calculabilité et complexité en distribué(2011)
Subjects: Discrete mathematics, Ring (mathematics), Leader election, Mathematics::Commutative Algebra, Divisor, [SCCO.COMP]Cognitive science/Computer science, 020207 software engineering, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Homonym, Ring size, Identifier, 010201 computation theory & mathematics, If and only if, ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION, Leader, 0202 electrical engineering, electronic engineering, information engineering, Election algorithm, Mathematics
Abstract: International audience; Considering the case of homonyms processes (some processesmay share the same identifier) on a ring, we give here a necessary andsufficient condition on the number of identifiers to enable leader election.We prove that if l is the number of identifiers then message-terminatingelection is possible if and only if l is greater than the greatest properdivisor of the ring size even if the processes do not know the ring size.If the ring size is known, we propose a process-terminating algorithmexchanging O(n log(n)) messages that is optimal.
Published: 2014

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

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

180. Easy identification of generalized common and conserved nested intervals

Author: Mathieu Raffinot, Irena Rusu, Fabien de Montgolfier, 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), Laboratoire d'Informatique de Nantes Atlantique (LINA), Mines Nantes (Mines Nantes)-Université de Nantes (UN)-Centre National de la Recherche Scientifique (CNRS), and Centre National de la Recherche Scientifique (CNRS)-Mines Nantes (Mines Nantes)-Université de Nantes (UN)
Subjects: FOS: Computer and information sciences, Discrete mathematics, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Computational Biology, Genomics, Combinatorics, Set (abstract data type), Computational Mathematics, Computational Theory and Mathematics, Modeling and Simulation, Multigene Family, Computer Science - Data Structures and Algorithms, Genetics, Nested intervals, Interval (graph theory), Data Structures and Algorithms (cs.DS), Molecular Biology, Algorithms, Mathematics
Abstract: International audience; In this paper we explain how to easily compute gene clusters, formalized by classical or generalized nested common or conserved intervals, between a set of K genomes represented as K permutations. A b-nested common (resp. conserved) interval I of size |I| is either an interval of size 1 or a common (resp. conserved) interval that contains another b-nested common (resp. conserved) interval of size at least |I|-b. When b=1, this corresponds to the classical notion of nested interval. We exhibit two simple algorithms to output all b-nested common or conserved intervals between K permutations in O(Kn+nocc) time, where nocc is the total number of such intervals. We also explain how to count all b-nested intervals in O(Kn) time. New properties of the family of conserved intervals are proposed to do so.
Published: 2014

181. Q-subdifferential and Q-conjugate for global optimality

Author: Ider Tseveendorj, Dominique Fortin, 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), CARO, Parallélisme, Réseaux, Systèmes, Modélisation (PRISM), Université de Versailles Saint-Quentin-en-Yvelines (UVSQ)-Centre National de la Recherche Scientifique (CNRS)-Université de Versailles Saint-Quentin-en-Yvelines (UVSQ)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS)-Université de Versailles Saint-Quentin-en-Yvelines (UVSQ)-Centre National de la Recherche Scientifique (CNRS)-Université de Versailles Saint-Quentin-en-Yvelines (UVSQ), and Fortin, Dominique
Subjects: Computational Mathematics, Pure mathematics, global optimality conditions, Legendre-Fenchel conjugate, continuous lagrangian multipliers, Mathematical analysis, subdifferential, Subderivative, Global optimality, Conjugate, Mathematics
Abstract: International audience; Нормальный конус и субдифференциал могут быть обобщены с помощью различных непрерывных функций; в данной статье затрагивается версия Q-субдифференциала с несепарабельной функцией. Получены необходимые и достаточные условия оптимальности для задач бесусловной невыпуклой оптимизации в термине Q-субдифференциала. В задачах с ограничениями типа неравенств предложено использовать непрерывную функцию вместо обычных скалярных множителей Лагранжа, что позволяют получить условия оптимальности. Подобным же образом преобразование Лежандра-Фенхеля обобщается в Q-сопряженное и получены условия глобальной оптимальности в термине Q-сопряженных
Published: 2014

182. Computing H-Joins with Application to 2-Modular Decomposition

Author: Antoine Mamcarz, Fabien de Montgolfier, Michel Habib, 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, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)
Subjects: General Computer Science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, 01 natural sciences, Graph, Combinatorics, Pathwidth, Graph power, Cograph, 0101 mathematics, Complement graph, Graph decompositions, Mathematics, Discrete mathematics, Applied Mathematics, 010102 general mathematics, Neighbourhood (graph theory), H-Join, 16. Peace & justice, Computer Science Applications, Modular decomposition, Homogeneous pairs, 010201 computation theory & mathematics, Bipartite graph, Bound graph, Algorithms
Abstract: International audience; We present here a general framework to design algorithms that compute H-join. For a given bipartite graph H, we say that a graph G admits a H-join decomposition or simply a H-join, if the vertices of G can be partitioned in |H| parts connected as in H. This graph H is a kind of pattern, that we want to discover in G. This framework allows us to present fastest known algorithms for the computation of P 4-join (aka N-join), P 5-join (aka W-join), C 6-join (aka 6-join). We also generalize this method to find a homogeneous pair (also known as 2-module), a pair {M 1,M 2} such that for every vertex x∉(M 1∪M 2) and i∈{1,2}, x is either adjacent to all vertices in M i or to none of them. First used in the context of perfect graphs (Chvátal and Sbihi in Graphs Comb. 3:127-139, 1987), it is a generalization of splits (a.k.a. 1-joins) and of modules. The algorithmics to compute them appears quite involved. In this paper, we describe an O(mn 2)-time algorithm computing all maximal homogeneous pairs of a graph, which not only improves a previous bound of O(mn 3) for finding only one pair (Everett et al. in Discrete Appl. Math. 72:209-218, 1997), but also uses a nice structural property of homogenous pairs, allowing to compute a canonical decomposition tree for sesquiprime graphs (i.e., graphs G having no module and such that for every vertex v∈G, G−v also has no module).
Published: 2014

183. Asynchronous Consensus with Bounded Memory

Author: Delporte-Gallet, Carole, Fauconnier, Hugues, 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), and ANR-11-BS02-0014,DISPLEXITY,Calculabilité et complexité en distribué(2011)
Subjects: Computer Science::Multiagent Systems, Shared memory, consensus, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], space complexity
Abstract: We present here a bounded memory consensus Obstruction-Free algorithm for the asynchronous shared memory model. More precisely for a set of n processes, this algorithm uses n + 1 multi-writer multi-reader (MWMR) registers, each of these registers being of size O(log(n)) bits. Then we get a O(n log(n))-bits size complexity consensus algorithm with single-writer multi-reader (SWMR) registers and a O(n log(n))-bits complexity consensus algorithm in the asynchronous message passing model with a majority of correct processes. As it is easy to ensure the Obstruction-Free assumption with randomization (or with leader election failure detector) we obtain a bounded memory size randomized consensus algorithm and a bounded memory size consensus algorithm with failure detector.
Published: 2014

184. Fast Rendezvous on a Cycle by Agents with Different Speeds

Author: Amos Korman, Shay Kutten, Yoav Rodeh, Ofer Feinerman, Weizmann Institute of Science [Rehovot, Israël], 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), Technion - Israel Institute of Technology [Haifa], and Jerusalem College of Engineering, Anna University
Subjects: FOS: Computer and information sciences, General Computer Science, pebble, Computer science, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, White board, Upper and lower bounds, Theoretical Computer Science, Computer Science - Robotics, rendezvous, 0202 electrical engineering, electronic engineering, information engineering, Order (group theory), Symmetry breaking, Discrete mathematics, cycle, Work (physics), Multiplicative function, Rendezvous, Order (ring theory), 020207 software engineering, speed, Asynchrony (computer programming), Computer Science - Distributed, Parallel, and Cluster Computing, 010201 computation theory & mathematics, Obstacle, white board, 020201 artificial intelligence & image processing, Distributed, Parallel, and Cluster Computing (cs.DC), asynchrony, heterogeneity, mobile agents, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Robotics (cs.RO), Algorithm
Abstract: The difference between the speed of the actions of different processes is typically considered as an obstacle that makes the achievement of cooperative goals more difficult. In this work, we aim to highlight potential benefits of such asynchrony phenomena to tasks involving symmetry breaking. Specifically, in this paper, identical except for their speeds mobile agents are placed at arbitrary locations on a continuous cycle of length n and use their speed difference in order to rendezvous fast. We normalize the speed of the slower agent to be 1, and fix the speed of the faster agent to be some ci¾?>i¾?1. An agent does not know whether it is the slower agent or the faster one. The straightforward distributed-race DR algorithm is the one in which both agents simply start walking until rendezvous is achieved. It is easy to show that, in the worst case, the rendezvous time of DR is n/ci¾?-i¾?1. Note that in the interesting case, where c is very close to 1 e.g., ci¾?=i¾?1i¾?+i¾?1/n k , this bound becomes huge. Our first result is a lower bound showing that, up to a multiplicative factor of 2, this bound is unavoidable, even in a model that allows agents to leave arbitrary marks the white board model, even assuming sense of direction, and even assuming n and c are known to agents. That is, we show that under such assumptions, the rendezvous time of any algorithm is at least $\frac{n}{2c-1}$ if ci¾?≤i¾?3 and slightly larger specifically, $\frac{n}{c+1}$ if ci¾?>i¾?3. We then manage to construct an algorithm that precisely matches the lower bound for the case ci¾?≤i¾?2, and almost matches it when ci¾?>i¾?2. Moreover, our algorithm performs under weaker assumptions than those stated above, as it does not assume sense of direction, and it allows agents to leave only a single mark a pebble and only at the place where they start the execution. Finally, we investigate the setting in which no marks can be used at all, and show tight bounds for ci¾?≤i¾?2, and almost tight bounds for ci¾?>i¾?2.
Published: 2014

185. Static Quantum Games Revisited

Author: Markiewicz, Marcin, Kosowski, Adrian, Tylec, Tomasz, Pykacz, Jaroslaw, Gavoille, Cyril, Institute of Theoretical Physics and Astrophysics [Univ Gdańsk] (IFTIA), Faculty of Mathematics, Physics and Informatics [Univ Gdańsk], University of Gdańsk (UG)-University of Gdańsk (UG), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Networks, Graphs and Algorithms (GANG), Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), University of Gdańsk (UG), 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.), Inria, 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: quantum, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], game
Published: 2014

186. Greedy routing in small-world networks with power-law degrees

Author: George Giakkoupis, Pierre Fraigniaud, 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), As Scalable As Possible: foundations of large scale dynamic distributed systems (ASAP), 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)-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), SYSTÈMES LARGE ÉCHELLE (IRISA-D1), 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, and Institut National de Recherche en Informatique et en Automatique (Inria)
Subjects: Degree (graph theory), Computer Networks and Communications, Expected value, Binary logarithm, Theoretical Computer Science, Combinatorics, Distribution (mathematics), Computational Theory and Mathematics, Hardware and Architecture, Log-log plot, Statistics, Exponent, Probability distribution, [INFO]Computer Science [cs], Mathematics, Complement (set theory)
Abstract: In this paper we study decentralized routing in small-world networks that combine a wide variation in node degrees with a notion of spatial embedding. Specifically, we consider a variant of J. Kleinberg's grid-based small-world model in which (1) the number of long-range edges of each node is not fixed, but is drawn from a power-law probability distribution with exponent parameter $$\alpha \ge 0$$ ? ? 0 and constant mean, and (2) the long-range edges are considered to be bidirectional for the purposes of routing. This model is motivated by empirical observations indicating that several real networks have degrees that follow a power-law distribution. The measured power-law exponent $$\alpha $$ ? for these networks is often in the range between 2 and 3. For the small-world model we consider, we show that when $$2 < \alpha < 3$$ 2 < ? < 3 the standard greedy routing algorithm, in which a node forwards the message to its neighbor that is closest to the target in the grid, finishes in an expected number of $$O(\log ^{\alpha -1} n\cdot \log \log n)$$ O ( log ? - 1 n · log log n ) steps, for any source---target pair. This is asymptotically smaller than the $$O(\log ^2 n)$$ O ( log 2 n ) steps needed in Kleinberg's original model with the same average degree, and approaches $$O(\log n)$$ O ( log n ) as $$\alpha $$ ? approaches 2. Further, we show that when $$0\le \alpha < 2$$ 0 ≤ ? < 2 or $$\alpha \ge 3$$ ? ? 3 the expected number of steps is $$O(\log ^2 n)$$ O ( log 2 n ) , while for $$\alpha = 2$$ ? = 2 it is $$O(\log ^{4/3} n)$$ O ( log 4 / 3 n ) . We complement these results with lower bounds that match the upper bounds within at most a $$\log \log n$$ log log n factor.
Published: 2014

187. Into the Square - On the Complexity of Quadratic-Time Solvable Problems

Author: Borassi, Michele, Crescenzi, Pierluigi, Habib, Michel, IMT Institute of Advanced Studies, Dipartimento di Sistemi e Informatica (DSI), Università degli Studi di Firenze = University of Florence (UniFI), 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), and Università degli Studi di Firenze = University of Florence [Firenze] (UNIFI)
Subjects: FOS: Computer and information sciences, Computer Science - Computational Complexity, TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO]Computer Science [cs], Computational Complexity (cs.CC), MathematicsofComputing_DISCRETEMATHEMATICS
Abstract: This paper will analyze several quadratic-time solvable problems, and will classify them into two classes: problems that are solvable in truly subquadratic time (that is, in time $O(n^{2-\epsilon})$ for some $\epsilon>0$) and problems that are not, unless the well known Strong Exponential Time Hypothesis (SETH) is false. In particular, we will prove that some quadratic-time solvable problems are indeed easier than expected. We will provide an algorithm that computes the transitive closure of a directed graph in time $O(mn^{\frac{\omega+1}{4}})$, where $m$ denotes the number of edges in the transitive closure and $\omega$ is the exponent for matrix multiplication. As a side effect, we will prove that our algorithm runs in time $O(n^{\frac{5}{3}})$ if the transitive closure is sparse. The same time bounds hold if we want to check whether a graph is transitive, by replacing m with the number of edges in the graph itself. As far as we know, this is the fastest algorithm for sparse transitive digraph recognition. Finally, we will apply our algorithm to the comparability graph recognition problem (dating back to 1941), obtaining the first truly subquadratic algorithm. The second part of the paper deals with hardness results. Starting from an artificial quadratic-time solvable variation of the k-SAT problem, we will construct a graph of Karp reductions, proving that a truly subquadratic-time algorithm for any of the problems in the graph falsifies SETH. The analyzed problems are the following: computing the subset graph, finding dominating sets, computing the betweenness centrality of a vertex, computing the minimum closeness centrality, and computing the hyperbolicity of a pair of vertices. We will also be able to include in our framework three proofs already appeared in the literature, concerning the graph diameter computation, local alignment of strings and orthogonality of vectors., Comment: Submitted at SODA 2015
Published: 2014

188. Epstein-Barr virus infection and clinical outcome in breast cancer patients correlate with immune cell TNF-α/IFN-γ response

Author: Catherine Fallecker, Samira Fafi-Kremer, Sofia Franco, Carlos Freire de Oliveira, Artur Paiva, Gina Marrão, Emmanuel Drouet, Mohammed Habib, Teresa Simões Silva, Patrice Morand, Dominique J. Bicout, Unit for Virus Host-Cell Interactions [Grenoble] (UVHCI), Centre National de la Recherche Scientifique (CNRS)-European Molecular Biology Laboratory [Grenoble] (EMBL)-Université Joseph Fourier - Grenoble 1 (UJF), Instituto Português de Sangue e da Transplantação [Coimbra] (IPST), 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), Instituto Superior de Engenharia de Coimbra, Universidade de Trás-os-Montes e Alto Douro (UTAD), Environnement et Prédiction de la Santé des Populations (TIMC-IMAG-EPSP), Techniques de l'Ingénierie Médicale et de la Complexité - Informatique, Mathématiques et Applications, Grenoble - UMR 5525 (TIMC-IMAG), VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Joseph Fourier - Grenoble 1 (UJF)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Joseph Fourier - Grenoble 1 (UJF), Laboratoire de l'Accélérateur Linéaire (LAL), Centre National de la Recherche Scientifique (CNRS)-Institut National de Physique Nucléaire et de Physique des Particules du CNRS (IN2P3)-Université Paris-Sud - Paris 11 (UP11), Interaction virus-hôte et maladies du foie, Université de Strasbourg (UNISTRA)-Institut National de la Santé et de la Recherche Médicale (INSERM), Departamento de Patologia [Coimbra], Centro Hospitalar e Universitário [Coimbra], Departamento de Ginecologia [Coimbra], Universidade de Coimbra [Coimbra]-Centro Hospitalar e Universitário [Coimbra], Université Joseph Fourier - Grenoble 1 (UJF)-European Molecular Biology Laboratory [Grenoble] (EMBL)-Centre National de la Recherche Scientifique (CNRS), Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS), and Université Paris-Sud - Paris 11 (UP11)-Institut National de Physique Nucléaire et de Physique des Particules du CNRS (IN2P3)-Centre National de la Recherche Scientifique (CNRS)
Subjects: Adult, Cancer Research, Epstein-Barr Virus Infections, Herpesvirus 4, Human, Survival, T-Lymphocytes, Breast Neoplasms, Peripheral blood mononuclear cell, Virus, Interferon-gamma, Immune system, Breast cancer, Immunocompetent cells, EBV, Genetics, Medicine, Humans, Viral load, Epstein–Barr virus infection, IFN-γ, Survival analysis, Aged, Aged, 80 and over, Tumor, biology, [SDV.BBM.BS]Life Sciences [q-bio]/Biochemistry, Molecular Biology/Structural Biology [q-bio.BM], business.industry, Tumor Necrosis Factor-alpha, Middle Aged, medicine.disease, Survival Analysis, 3. Good health, Killer Cells, Natural, Oncology, Multivariate analysis, TNF-α, Immunology, biology.protein, Tumor necrosis factor alpha, Female, Antibody, business, Research Article, ZEBRA
Abstract: Background For nearly two decades now, various studies have reported detecting the Epstein-Barr virus (EBV) in breast cancer (BC) cases. Yet the results are unconvincing, and their interpretation has remained a matter of debate. We have now presented prospective data on the effect of EBV infection combined with survival in patients enrolled in a prospective study. Methods We assessed 85 BC patients over an 87-month follow-up period to determine whether EBV infection, evaluated by qPCR in both peripheral blood mononuclear cells (PBMCs) and tumor biopsies, interacted with host cell components that modulate the evolution parameters of BC. We also examined the EBV replicating form by the titration of serum anti-ZEBRA antibodies. Immunological studies were performed on a series of 35 patients randomly selected from the second half of the survey, involving IFN-γ and TNF-α intracellular immunostaining tests performed via flow cytometry analysis in peripheral NK and T cells, in parallel with EBV signature. The effect of the EBV load in the blood or tumor tissue on patient survival was analyzed using univariate and multivariate analyses, combined with an analysis of covariance. Results Our study represents the first ever report of the impact of EBV on the clinical outcome of BC patients, regardless of tumor histology or treatment regimen. No correlation was found between: (i) EBV detection in tumor or PBMCs and tumor characteristics; (ii) EBV and other prognostic factors. Notably, patients exhibiting anti-ZEBRA antibodies at high titers experienced poorer overall survival (p = 0.002). Those who recovered from their disease were found to have a measurable EBV DNA load, together with a high frequency of IFN-γ and TNF-α producing PBMCs (p = 0.04), which indicates the existence of a Th1-type polarized immune response in both the tumor and its surrounding tissue. Conclusions The replicative form of EBV, as investigated using anti-ZEBRA titers, correlated with poorer outcomes, whereas the latent form of the virus that was measured and quantified using the EBV tumor DNA conferred a survival advantage to BC patients, which could occur through the activation of non-specific anti-tumoral immune responses. Electronic supplementary material The online version of this article (doi:10.1186/1471-2407-14-665) contains supplementary material, which is available to authorized users.
Published: 2013

189. Adaptive Register Allocation with a Linear Number of Registers

Author: Leslie Lamport, Hugues Fauconnier, Eli Gafni, Carole Delporte-Gallet, 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), Computer Science Department [Los Angeles] (UCLA), University of California [Los Angeles] (UCLA), University of California-University of California, Microsoft Research [Redmond], Microsoft Corporation [Redmond, Wash.], Yehuda Afek, and University of California (UC)-University of California (UC)
Subjects: Adaptive algorithm, Computer science, x86 debug register, [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], 020206 networking & telecommunications, 0102 computer and information sciences, 02 engineering and technology, Parallel computing, 01 natural sciences, Shared memory, 010201 computation theory & mathematics, Distributed algorithm, 0202 electrical engineering, electronic engineering, information engineering, Memory type range register, Base and bounds, Hardware_REGISTER-TRANSFER-LEVELIMPLEMENTATION, Linear number, Register allocation
Abstract: International audience; We give an adaptive algorithm in which processes use multi-writer multi-reader registers to acquire exclusive write access to their own single-writer, multi-reader registers. It is the first such algorithm that uses a number of registers linear in the number of participating processes. Previous adaptive algorithms require at least Θ(n 3/2) registers.
Published: 2013

190. On the manipulability of voting systems: application to multi-operator networks

Author: Ludovic Noirie, François Durand, Fabien Mathieu, 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), 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), Alcatel-Lucent Bell Labs France [Nozay], Alcatel-Lucent Bell Labs France, and LINCS
Subjects: Operations research, business.industry, Computer science, media_common.quotation_subject, 05 social sciences, Computer security, computer.software_genre, Outcome (game theory), [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], Tactical voting, Order (exchange), Voting, 0502 economics and business, Path (graph theory), The Internet, Instant-runoff voting, 050207 economics, business, Game theory, computer, 050205 econometrics, media_common
Abstract: http://www.cnsm-conf.org/2013/documents/papers/ICQT/p292-durand.pdf; International audience; Internet is a large-scale and highly competitive economic ecosystem. In order to make fair decisions, while preventing the economic actors from manipulating the natural outcome of the decision process, game theory is a natural framework, and voting systems represent an interesting alternative that, to our knowledge, has not yet being considered. They allow competing entities to decide among different options. In this paper, we investigate their use for end-to-end path selection in multi-operator networks, analyzing their manipulability by tactical voting and their economic efficiency.We show that Instant Runoff Voting is much more efficient and resistant to tactical voting than the natural system which tries to get the economic optimum.
Published: 2013

191. Toward more localized local algorithms: removing assumptions concerning global knowledge

Author: Laurent Viennot, Amos Korman, Jean-Sébastien Sereni, 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), Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Laboratory of Information, Network and Communication Sciences (LINCS), 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), 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), 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] (IMT)
Subjects: FOS: Computer and information sciences, Computer Networks and Communications, Computer science, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Theoretical Computer Science, Computer Science - Data Structures and Algorithms, 0202 electrical engineering, electronic engineering, information engineering, Data Structures and Algorithms (cs.DS), Probabilistic analysis of algorithms, Pruning (decision trees), Local algorithm, Computer communication networks, Weighted Majority Algorithm, 020206 networking & telecommunications, State (functional analysis), Randomized algorithm, Running time, Computer Science - Distributed, Parallel, and Cluster Computing, Computational Theory and Mathematics, Distributed algorithm, 010201 computation theory & mathematics, Hardware and Architecture, Theory of computation, Distributed, Parallel, and Cluster Computing (cs.DC), Coloring problem, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Algorithm, Pruning (morphology)
Abstract: International audience; Numerous sophisticated local algorithm were suggested in the literature for various fundamental problems. Notable examples are the MIS and (∆+1)-coloring algorithms by Barenboim and Elkin [6], by Kuhn [22], and by Panconesi and Srinivasan [34], as well as the O(∆ 2)-coloring algorithm by Linial [28]. Unfortunately, most known local algorithms (including, in particular, the aforementioned algorithms) are non-uniform, that is, local algorithms generally use good estimations of one or more global parameters of the network, e.g., the maximum degree ∆ or the number of nodes n. This paper provides a method for transforming a non-uniform local algorithm into a uniform one. Furthermore , the resulting algorithm enjoys the same asymp-totic running time as the original non-uniform algorithm. Our method applies to a wide family of both deterministic and randomized algorithms. Specifically, it applies to almost all state of the art non-uniform algorithms for MIS and Maximal Matching, as well as to many results concerning the coloring problem. (In particular, it applies to all aforementioned algorithms.) To obtain our transformations we introduce a new distributed tool called pruning algorithms, which we believe may be of independent interest.
Published: 2013

192. Rumor Spreading in Random Evolving Graphs

Author: Andrea E. F. Clementi, Riccardo Silvestri, Pierluigi Crescenzi, Pierre Fraigniaud, Carola Doerr, Alessandro Panconesi, Francesco Pasquale, M. Isopi, Università degli Studi di Roma Tor Vergata [Roma], Dipartimento di Sistemi e Informatica (DSI), Università degli Studi di Firenze = University of Florence (UniFI), Recherche Opérationnelle (RO), Laboratoire d'Informatique de Paris 6 (LIP6), Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS), 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), Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Physics Department,Rome University 'LaSapienza' (Physics Department,Rome University 'LaSapienza'), Università degli Studi di Roma 'La Sapienza' = Sapienza University [Rome] (UNIROMA), Hans L. Bodlaender, Giuseppe F. Italiano, Università degli Studi di Firenze = University of Florence [Firenze] (UNIFI), Università degli Studi di Roma 'La Sapienza' = Sapienza University [Rome], Università degli Studi di Firenze [Firenze], Centre National de la Recherche Scientifique (CNRS)-Université Paris Diderot - Paris 7 (UPD7), and Università degli Studi di Roma 'La Sapienza' [Rome]
Subjects: Random Evolving Graphs, FOS: Computer and information sciences, Random Evolving Graphs, Markov Chains, Rumor Spreading, Discrete Mathematics (cs.DM), Structure (category theory), 0102 computer and information sciences, 02 engineering and technology, Time step, 01 natural sciences, Graph model, FOS: Mathematics, 0202 electrical engineering, electronic engineering, information engineering, Order (group theory), [INFO]Computer Science [cs], Protocol (object-oriented programming), Mathematics, Social and Information Networks (cs.SI), Discrete mathematics, Settore INF/01 - Informatica, Probability (math.PR), Computer Science - Social and Information Networks, 020206 networking & telecommunications, Rumor, Markov Chains, Settore MAT/06 - Probabilita' e Statistica Matematica, Computer Science - Distributed, Parallel, and Cluster Computing, 010201 computation theory & mathematics, Rumor Spreading, Distributed, Parallel, and Cluster Computing (cs.DC), Enhanced Data Rates for GSM Evolution, Constant (mathematics), Algorithm, Mathematics - Probability, Computer Science - Discrete Mathematics
Abstract: Randomized gossip is one of the most popular way of disseminating information in large scale networks. This method is appreciated for its simplicity, robustness, and efficiency. In the "push" protocol, every informed node selects, at every time step (a.k.a. round), one of its neighboring node uniformly at random and forwards the information to this node. This protocol is known to complete information spreading in $O(\log n)$ time steps with high probability (w.h.p.) in several families of $n$-node "static" networks. The Push protocol has also been empirically shown to perform well in practice, and, specifically, to be robust against dynamic topological changes. In this paper, we aim at analyzing the Push protocol in "dynamic" networks. We consider the "edge-Markovian" evolving graph model which captures natural temporal dependencies between the structure of the network at time $t$, and the one at time $t+1$. Precisely, a non-edge appears with probability $p$, while an existing edge dies with probability $q$. In order to fit with real-world traces, we mostly concentrate our study on the case where $p=��(1/n)$ and $q$ is constant. We prove that, in this realistic scenario, the Push protocol does perform well, completing information spreading in $O(\log n)$ time steps w.h.p. Note that this performance holds even when the network is, w.h.p., disconnected at every time step (e.g., when $p << (\log n) / n$). Our result provides the first formal argument demonstrating the robustness of the Push protocol against network changes. We also address other ranges of parameters $p$ and $q$ (e.g., $p+q=1$ with arbitrary $p$ and $q$, and $p=1/n$ with arbitrary $q$). Although they do not precisely fit with the measures performed on real-world traces, they can be of independent interest for other settings. The results in these cases confirm the positive impact of dynamism.
Published: 2013

193. Self-organizing Flows in Social Networks

Author: Laurent Viennot, Laurent Massoulié, Nidhi Hegde, Technicolor R & I [Cesson Sévigné], Technicolor, Microsoft Research - Inria Joint Centre (MSR - INRIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Microsoft Research Laboratory Cambridge-Microsoft Corporation [Redmond, Wash.], 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), 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), Alcatel-Lucent Bell Labs France [Nozay], and Alcatel-Lucent Bell Labs France
Subjects: FOS: Computer and information sciences, Physics - Physics and Society, Theoretical computer science, General Computer Science, Computer science, Information Dissemination, FOS: Physical sciences, Context (language use), 0102 computer and information sciences, 02 engineering and technology, Physics and Society (physics.soc-ph), 01 natural sciences, Theoretical Computer Science, Computer Science - Networking and Internet Architecture, symbols.namesake, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], Computer Science - Computer Science and Game Theory, 020204 information systems, Economics, 0202 electrical engineering, electronic engineering, information engineering, Price of anarchy, budget of attention, Network formation, Dimension (data warehouse), Simulation, Abstraction (linguistics), Social and Information Networks (cs.SI), Networking and Internet Architecture (cs.NI), price of anarchy, Social network, business.industry, self organisation, Computer Science - Social and Information Networks, social filtering, 010201 computation theory & mathematics, Nash equilibrium, symbols, 020201 artificial intelligence & image processing, business, Computer Science and Game Theory (cs.GT)
Abstract: International audience; Social networks offer users new means of accessing information, essentially relying on ''social filtering'', i.e. propagation and filtering of information by social contacts. The sheer amount of data flowing in these networks, combined with the limited budget of attention of each user, makes it difficult to ensure that social filtering brings relevant content to the interested users. Our motivation in this paper is to measure to what extent self-organization of the social network results in efficient social filtering. To this end we introduce flow games, a simple abstraction that models network formation under selfish user dynamics, featuring user-specific interests and budget of attention. In the context of homogeneous user interests, we show that selfish dynamics converge to a stable network structure (namely a pure Nash equilibrium) with close-to-optimal information dissemination. We show in contrast, for the more realistic case of heterogeneous interests, that convergence, if it occurs, may lead to information dissemination that can be arbitrarily inefficient, as captured by an unbounded ''price of anarchy''. Nevertheless the situation differs when users' interests exhibit a particular structure, captured by a metric space with low doubling dimension. In that case, natural autonomous dynamics converge to a stable configuration. Moreover, users obtain all the information of interest to them in the corresponding dissemination, provided their budget of attention is logarithmic in the size of their interest set., x-id-hal = hal-00761046
Published: 2013

194. The consensus problem in Homonymous models

Author: Tran-The, Hung, 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), Université Paris-Diderot - Paris VII, and Hugues Fauconnier
Subjects: consensus, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
Abstract: So far, the distributed computing community has either assumed that all the processes of a distributed system have distinct identifiers or, more rarely, that the processes are anonymous and have no identifiers. These are two extremes of the same general model: namely, n processes use l different identifiers, where 1 l n. We call this model homonymous model. To determine the power of homonymous model as well as the importance of identifiers in distributed computing, this thesis studies the consensus problem, one of the most famous distributed computing problem. We give necessary and sufficient conditions on the number of identifiers for solving consensus in a distributed system with t faulty processes in the synchronous case. We show that in crash, send omission and general omission failures model, the uniform consensus is solvable even if processes are anonymous. Thus, identifiers are not useful in that case. However identifiers become important in Byzantine failures model: 3t + 1 identifiers is necessary and sufficient for Byzantine agreement. Surprisingly the number of identifiers must be greater than n+3t 2 in presence of three facets of uncertainty: partial synchrony, Byzantine failures and homonyms. This demonstrates two differences from the classical model (which has l = n): there are situations where relaxing synchrony to partial synchrony renders agreement impossible, and, in the partially synchronous case, increasing the number of correct processes can actually make it harder to reach agreement.
Published: 2013

195. Problème du Consensus dans le Modèle Homonyme

Author: Tran-The, Hung, 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), Université Paris-Diderot - Paris VII, and Hugues Fauconnier
Subjects: consensus, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
Abstract: So far, the distributed computing community has either assumed that all the processes of a distributed system have distinct identifiers or, more rarely, that the processes are anonymous and have no identifiers. These are two extremes of the same general model: namely, n processes use l different identifiers, where 1 l n. We call this model homonymous model. To determine the power of homonymous model as well as the importance of identifiers in distributed computing, this thesis studies the consensus problem, one of the most famous distributed computing problem. We give necessary and sufficient conditions on the number of identifiers for solving consensus in a distributed system with t faulty processes in the synchronous case. We show that in crash, send omission and general omission failures model, the uniform consensus is solvable even if processes are anonymous. Thus, identifiers are not useful in that case. However identifiers become important in Byzantine failures model: 3t + 1 identifiers is necessary and sufficient for Byzantine agreement. Surprisingly the number of identifiers must be greater than n+3t 2 in presence of three facets of uncertainty: partial synchrony, Byzantine failures and homonyms. This demonstrates two differences from the classical model (which has l = n): there are situations where relaxing synchrony to partial synchrony renders agreement impossible, and, in the partially synchronous case, increasing the number of correct processes can actually make it harder to reach agreement.
Published: 2013

196. Black Art: Obstruction-Free k-set Agreement with |MWMR registers| < |proccesses

Author: Eli Gafni, Sergio Rajsbaum, Hugues Fauconnier, Carole Delporte-Gallet, 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), Computer Science Department [Los Angeles] (UCLA), University of California [Los Angeles] (UCLA), University of California (UC)-University of California (UC), Instituto de Matematicas [México], Universidad Nacional Autónoma de México = National Autonomous University of Mexico (UNAM), Vincent Gramoli and Rachid Guerraoui, University of California-University of California, and Universidad Nacional Autónoma de México (UNAM)
Subjects: Emulation, Theoretical computer science, K-set, Computer science, media_common.quotation_subject, [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Agreement, Task (project management), Shared memory, 010201 computation theory & mathematics, Reading (process), Communication bandwidth, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, media_common
Abstract: International audience; When n processes communicate by writing to and reading from k
Published: 2013

197. Contenu généré par les utilisateurs : une étude sur DailyMotion

Author: Carlinet, Yannick, Huynh, The Dang, Kauffmann, Bruno, Mathieu, Fabien, Noirie, Ludovic, Tixeuil, Sébastien, Orange Labs [Issy les Moulineaux], France Télécom, 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), Alcatel-Lucent Bell Labs France [Nozay], Alcatel-Lucent Bell Labs France, 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), 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.), Networks and Performance Analysis (NPA), Laboratoire d'Informatique de Paris 6 (LIP6), and Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)
Subjects: [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI]
Abstract: International audience; Actuellement, une large part du trafic Internet vient de sites de "User-Generated Content" (UGC). Comprendre les caractéristiques de ce trafic est important pour les opérateurs (dimensionnement réseau), les fournisseurs (garantie de la qualité de service) et les équipementiers (conception d'équipements adaptés). Dans ce contexte, nous proposons d'analyser et de modéliser des traces d'usage du site DailyMotion.
Published: 2013

198. Can P2P Networks be Super-Scalable?

Author: François Baccelli, Ilkka Norros, Rémi Varloot, Fabien Mathieu, University of Texas at Austin [Austin], Dynamics of Geometric Networks (DYOGENE), 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)-Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Laboratory of Information, Network and Communication Sciences (LINCS), 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), 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), VTT Technical Research Centre of Finland (VTT), Département d'informatique - ENS Paris (DI-ENS), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria), 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), Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria Paris-Rocquencourt
Subjects: FOS: Computer and information sciences, Computer science, Distributed computing, media_common.quotation_subject, 02 engineering and technology, 01 natural sciences, Computer Science::Digital Libraries, Computer Science - Networking and Internet Architecture, 010104 statistics & probability, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], system fluid limit, 0202 electrical engineering, electronic engineering, information engineering, Stochastic geometry, 0101 mathematics, Function (engineering), scalability, media_common, Network model, Networking and Internet Architecture (cs.NI), Fluid limit, P2P, business.industry, 020206 networking & telecommunications, Scalability, Performance Analysis, business, peer-to-peer networking, Computer network
Abstract: We propose a new model for peer-to-peer networking which takes the network bottlenecks into account beyond the access. This model can cope with key features of P2P networking like degree or locality constraints together with the fact that distant peers often have a smaller rate than nearby peers. Using a network model based on rate functions, we give a closed form expression of peers download performance in the system's fluid limit, as well as approximations for the other cases. Our results show the existence of realistic settings for which the average download time is a decreasing function of the load, a phenomenon that we call super-scalability., Comment: arXiv admin note: substantial text overlap with arXiv:1108.4129
Published: 2013

199. Médiation Scientifique : une facette de nos métiers de la recherche

Author: Rousseau, Antoine, Darnaud, Aurélie, Goglin, Brice, Acharian, Céline, Leininger, Christine, Godin, Christophe, Holik, Clarisse, Kirchner, Claude, Rives, Diane, Darquie, Elodie, Kerrien, Erwan, Neyret, Fabrice, Masseglia, Florent, Dufour, Florian, Berry, Gérard, Dowek, Gilles, Robak, Hélène, Xypas, Hélène, Illina, Irina, Gnaedig, Isabelle, Jongwane, Joanna, Ehrel, Jocelyne, Viennot, Laurent, Guion, Laure, Calderan, Lisette, Kovacic, Lola, Collin, Marie, Enard, Marie-Agnès, Comte, Marie-Hélène, Quinson, Martin, Olivi, Martine, Giraud, Mathieu, Dorémus, Mathilde, Ogouchi, Mia, Droin, Muriel, Lacaux, Nathalie, Rougier, Nicolas, Roussel, Nicolas, Guitton, Pascal, Peterlongo, Pierre, Cornus, Rose-Marie, Vandermeersch, Simon, Maheo, Sophie, Lefebvre, Sylvain, Boldo, Sylvie, Viéville, Thierry, Poirel, Véronique, Chabreuil, Aline, Fischer, Arnaud, Farge, Claude, Vadel, Claude, Astic, Isabelle, Dumont, Jean-Pierre, Féjoz, Loic, Rambert, Patrick, Paradinas, Pierre, de Quatrebarbes, Sophie, Laurent, Stéphane, Modelling, Observations, Identification for Environmental Sciences (MOISE), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Laboratoire Jean Kuntzmann (LJK), Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Centre National de la Recherche Scientifique (CNRS)-Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria), Efficient runtime systems for parallel architectures (RUNTIME), Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Inria Siège, Modeling plant morphogenesis at different scales, from genes to phenotype (VIRTUAL PLANTS), 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)-Institut National de la Recherche Agronomique (INRA)-Amélioration génétique et adaptation des plantes méditerranéennes et tropicales (UMR AGAP), Centre de Coopération Internationale en Recherche Agronomique pour le Développement (Cirad)-Institut National de la Recherche Agronomique (INRA)-Centre international d'études supérieures en sciences agronomiques (Montpellier SupAgro)-Institut national d’études supérieures agronomiques de Montpellier (Montpellier SupAgro), Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Centre de Coopération Internationale en Recherche Agronomique pour le Développement (Cirad)-Institut National de la Recherche Agronomique (INRA)-Centre international d'études supérieures en sciences agronomiques (Montpellier SupAgro)-Institut national d’études supérieures agronomiques de Montpellier (Montpellier SupAgro), Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro), Amélioration génétique et adaptation des plantes méditerranéennes et tropicales (UMR AGAP), Formal islands: foundations and applications (PAREO), INRIA Lorraine, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique de Lorraine (INPL)-Université Nancy 2-Université Henri Poincaré - Nancy 1 (UHP)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique de Lorraine (INPL)-Université Nancy 2-Université Henri Poincaré - Nancy 1 (UHP), Visual Augmentation of Complex Environments (MAGRIT), Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Algorithms, Computation, Image and Geometry (LORIA - ALGO), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL), Models and Algorithms for Visualization and Rendering (MAVERICK), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Jean Kuntzmann (LJK), Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS), Scientific Data Management (ZENITH), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Inria Sophia Antipolis - Méditerranée (CRISAM), Chaire Algorithmes, machines et langages, Collège de France (CdF (institution)), Deduction modulo, interopérabilité et démonstration automatique (DEDUCTEAM), Inria Lille - Nord Europe, Analysis, perception and recognition of speech (PAROLE), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Natural Language Processing & Knowledge Discovery (LORIA - NLPKD), Theoretical adverse computations, and safety (CARTE), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Simulations and Algorithms on Grids for Environment (SAGE), 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), 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), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-É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), 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, 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), Information Scientifique et Technique (IST Sophia Antipolis Méditerranée), Algorithms for the Grid (ALGORILLE), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Networks, Systems and Services (LORIA - NSS), Analysis and Problems of Inverse type in Control and Signal processing (APICS), Bioinformatics and Sequence Analysis (BONSAI), Laboratoire d'Informatique Fondamentale de Lille (LIFL), Université de Lille, Sciences et Technologies-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lille, Sciences Humaines et Sociales-Centre National de la Recherche Scientifique (CNRS)-Université de Lille, Sciences et Technologies-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lille, Sciences Humaines et Sociales-Centre National de la Recherche Scientifique (CNRS)-Inria Lille - Nord Europe, fuscia, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université numérique ingénierie et technologie - UNIT-Université des sciences en ligne - UNISCIEL, Mnemonic Synergy (Mnemosyne), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institut des Maladies Neurodégénératives [Bordeaux] (IMN), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS), Méthodes et outils pour l'Interaction à gestes (MINT2), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Scalable, Optimized and Parallel Algorithms for Genomics (GenScale), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-GESTION DES DONNÉES ET DE LA CONNAISSANCE (IRISA-D7), Geometry and Lighting (ALICE), Formally Verified Programs, Certified Tools and Numerical Computations (TOCCATA), Laboratoire de Recherche en Informatique (LRI), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Realtime-at-Work (RTaW), Centre for Quantitative methods and Operations Management (QuantOM), Université de Liège, Inria, Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Centre de Coopération Internationale en Recherche Agronomique pour le Développement (Cirad)-Institut National de la Recherche Agronomique (INRA)-Centre international d'études supérieures en sciences agronomiques (Montpellier SupAgro)-Institut national d’études supérieures agronomiques de Montpellier (Montpellier SupAgro)-Centre de Coopération Internationale en Recherche Agronomique pour le Développement (Cirad)-Institut National de la Recherche Agronomique (INRA)-Centre international d'études supérieures en sciences agronomiques (Montpellier SupAgro)-Institut national d’études supérieures agronomiques de Montpellier (Montpellier SupAgro), Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Inria Sophia Antipolis - Méditerranée (CRISAM), Collège de France - Chaire Algorithmes, machines et langages, 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), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Inria Bordeaux - Sud-Ouest, Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut Polytechnique de Grenoble - Grenoble Institute of Technology-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut Polytechnique de Grenoble - Grenoble Institute of Technology-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut National Polytechnique de Grenoble (INPG), 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, Institut national d’études supérieures agronomiques de Montpellier (Montpellier SupAgro)-Institut National de la Recherche Agronomique (INRA)-Centre de Coopération Internationale en Recherche Agronomique pour le Développement (Cirad)-Centre international d'études supérieures en sciences agronomiques (Montpellier SupAgro)-Institut national d’études supérieures agronomiques de Montpellier (Montpellier SupAgro)-Institut National de la Recherche Agronomique (INRA)-Centre de Coopération Internationale en Recherche Agronomique pour le Développement (Cirad)-Centre international d'études supérieures en sciences agronomiques (Montpellier SupAgro)-Inria Sophia Antipolis - Méditerranée (CRISAM), Institut national d’études supérieures agronomiques de Montpellier (Montpellier SupAgro)-Institut National de la Recherche Agronomique (INRA)-Centre de Coopération Internationale en Recherche Agronomique pour le Développement (Cirad)-Centre international d'études supérieures en sciences agronomiques (Montpellier SupAgro), 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, 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)-Inria Paris-Rocquencourt, 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-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-Inria Bordeaux - Sud-Ouest, Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS), Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189 (CRIStAL), Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Ecole Centrale de Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Ecole Centrale de Lille-Inria Lille - Nord Europe, GESTION DES DONNÉES ET DE LA CONNAISSANCE (IRISA-D7), Université de Rennes (UNIV-RENNES)-CentraleSupélec-Inria Rennes – Bretagne Atlantique, none, Centre National de la Recherche Scientifique (CNRS)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Université Joseph Fourier - Grenoble 1 (UJF)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Centre National de la Recherche Scientifique (CNRS)-Université Joseph Fourier - Grenoble 1 (UJF)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Inria Grenoble - Rhône-Alpes, Centre National de la Recherche Scientifique (CNRS)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Université Joseph Fourier - Grenoble 1 (UJF)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Centre National de la Recherche Scientifique (CNRS)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Université Joseph Fourier - Grenoble 1 (UJF)-Université Pierre Mendès France - Grenoble 2 (UPMF), Department of Formal Methods (LORIA - FM), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Inria Nancy - Grand Est, Université de Lille-Centrale Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centrale Lille-Centre National de la Recherche Scientifique (CNRS), and Department of Algorithms, Computation, Image and Geometry (LORIA - ALGO)
Subjects: service public, culture scientifique, médiation scientifique, [INFO]Computer Science [cs], popularisation des sciences, recherche
Abstract: Dans ce monde devenu numérique nous savons que c'est une de nos missions d'acteur de la recherche publique, que de rendre accessibles les sciences du numérique au plus grand nombre. Ceci afin que chaque citoyenne et citoyen maîtrise, au delà des usages, les principaux fondements de cette mutation numérique. Et nous croyons que c'est l'acquisition d'une culture scientifique sur ces sujets qui est le levier de cette appropriation. C'est notre mission et notre plaisir d'y contribuer. Ce document a pour but d'aider chaque collègue Inria intéressé à participer à ce volet de nos missions. Devenue une facette de notre métier, comme le rappelle le Plan Stratégique Inria [1], ce que nous appelons médiation scientifique en sciences du numérique (alias, " mecsci ") se professionnalise et change d'échelle. Et c'est environ 1 % de nos ressources qui a vocation à y être consacré. Pour tout l'institut on parle donc de près de 40 équivalents temps-plein distribués à travers le travail quotidien ou ponctuel de plusieurs centaines de collègues chercheurs, ingénieurs, communicants, etc.. Une telle énergie mérite d'être bien employée : au service des meilleurs objectifs ; vers des cibles bien définies qui ont de vrais besoins sur ces sujets ; dans le cadre d'actions leviers qui aident à faire bouger les choses ; et avec une méthodologie efficace qui optimise ce que nous investissons dans de telles activités ; tout en respectant et en encourageant les dynamiques locales et individuelles indépendantes qui restent les sources vives de la médiation scientifique. Voilà pourquoi il y a juste besoin d'offrir en partage à chacune et chacun les éléments fondateurs et méthodologiques de cette médiation scientifique. Offrir aussi quelques bonnes pratiques très concrètes. On parle donc ici d'une organisation distribuée d'actions collaboratives d'où émerge le service public de popularisation scientifique visé. C'est ce que ce document se propose de décrire ici.
Published: 2013

200. Convergence of the D-iteration algorithm: convergence rate and asynchronous distributed scheme

Author: Hong, Dohy, Mathieu, Fabien, Burnside, Gérard, Alcatel-Lucent Bell Labs France [Nozay], Alcatel-Lucent Bell Labs France, 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), 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), and LINCS
Subjects: eigenvector, fixed point, numerical computation, ACM: G.: Mathematics of Computing/G.1: NUMERICAL ANALYSIS/G.1.0: General, distributed computation, ACM: G.: Mathematics of Computing/G.1: NUMERICAL ANALYSIS/G.1.3: Numerical Linear Algebra, Linear algebra, [INFO.INFO-NA]Computer Science [cs]/Numerical Analysis [cs.NA], iteration, [MATH.MATH-NA]Mathematics [math]/Numerical Analysis [math.NA]
Abstract: In this paper, we define the general framework to describe the diffusion operators associated to a positive matrix. We define the equations associated to diffusion operators and present some general properties of their state vectors. We show how this can be applied to prove and improve the convergence of a fixed point problem associated to the matrix iteration scheme, including for distributed computation framework. The approach can be understood as a decomposition of the matrix-vector product operation in elementary operations at the vector entry level.
Published: 2013

Catalog

Books, media, physical & digital resources

See catalog results

Searchworks

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

Search

Search Constraints

Refine your results

Search Limiters

Topic

Publication Year Range

Language

Journal

Database

Publisher

290 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