Search

Your search keyword '"Department of Computer Science [Purdue]"' showing total 18 results
Start Over Author "Department of Computer Science [Purdue]" Topic 01 natural sciences
18 results on '"Department of Computer Science [Purdue]"'

1. Full-field thermal imaging of quasiballistic crosstalk reduction in nanoscale devices

Author

Xavier Cartoixà, Maryam Parsa, Yee Rui Koh, Bjorn Vermeersch, Ali Shakouri, Je-Hyeong Bahk, Alvar Torelló, Pol Torres, Peide D. Ye, Yi Xuan, F. Xavier Alvarez, Amirkoushyar Ziabari, Birck Nanotechnology Center, Purdue University [West Lafayette], Universitat Autònoma de Barcelona (UAB), Laboratoire d'Innovation pour les Technologies des Energies Nouvelles et les nanomatériaux (LITEN), Institut National de L'Energie Solaire (INES), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Université Savoie Mont Blanc (USMB [Université de Savoie] [Université de Chambéry])-Centre National de la Recherche Scientifique (CNRS)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Université Savoie Mont Blanc (USMB [Université de Savoie] [Université de Chambéry])-Centre National de la Recherche Scientifique (CNRS), Department of Computer Science [Purdue], University of California [Santa Cruz] (UC Santa Cruz), University of California (UC), European Project: 645776,H2020,H2020-NMP-2014-two-stage,ALMA(2015), Centre National de la Recherche Scientifique (CNRS)-Université Savoie Mont Blanc (USMB [Université de Savoie] [Université de Chambéry])-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Centre National de la Recherche Scientifique (CNRS)-Université Savoie Mont Blanc (USMB [Université de Savoie] [Université de Chambéry])-Commissariat à l'énergie atomique et aux énergies alternatives (CEA), University of California [Santa Cruz] (UCSC), and University of California

Subjects
Materials science, Science, General Physics and Astronomy, 02 engineering and technology, Imaging techniques, 01 natural sciences, Article, General Biochemistry, Genetics and Molecular Biology, Crosstalk, symbols.namesake, Thermal conductivity, 0103 physical sciences, Thermal, [SPI.NANO]Engineering Sciences [physics]/Micro and nanotechnologies/Microelectronics, lcsh:Science, 010306 general physics, Nanoscopic scale, [PHYS]Physics [physics], Multidisciplinary, Nanoscale materials, business.industry, General Chemistry, Full field, 021001 nanoscience & nanotechnology, Condensed matter physics, Semiconductor, Fourier transform, Nanoscale devices, symbols, Optoelectronics, lcsh:Q, 0210 nano-technology, business, Submicron scale
Abstract

Understanding nanoscale thermal transport is of substantial importance for designing contemporary semiconductor technologies. Heat removal from small sources is well established to be severely impeded compared to diffusive predictions due to the ballistic nature of the dominant heat carriers. Experimental observations are commonly interpreted through a reduction of effective thermal conductivity, even though most measurements only probe a single aggregate thermal metric. Here, we employ thermoreflectance thermal imaging to directly visualise the 2D temperature field produced by localised heat sources on InGaAs with characteristic widths down to 100 nm. Besides displaying effective thermal performance reductions up to 50% at the active junctions in agreement with prior studies, our steady-state thermal images reveal that, remarkably, 1–3 μm adjacent to submicron devices the crosstalk is actually reduced by up to fourfold. Submicrosecond transient imaging additionally shows responses to be faster than conventionally predicted. A possible explanation based on hydrodynamic heat transport, and some open questions, are discussed., When thermal fields in semiconductors approach the submicron scale, non-diffusive heat transport is observed where Fourier based heat transport models fail. Here, the authors use thermal imaging to visualise these thermal field variations and in turn derive a hydrodynamic heat transport model.

Published
2018
Full Text
View/download PDF

2. Authoring landscapes by combining ecosystem and terrain erosion simulation

Author

Guillaume Cordonnier, Marie-Paule Cani, Bedrich Benes, Eric Guérin, Adrien Peytavie, James Gain, Eric Galin, Intuitive Modeling and Animation for Interactive Graphics & Narrative Environments (IMAGINE ), 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)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Laboratoire Jean Kuntzmann (LJK ), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), Modélisation Géométrique, Géométrie Algorithmique, Fractales (GeoMod), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), 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)-Centre National de la Recherche Scientifique (CNRS)-Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS), University of Cape Town, Department of Computer Science [Purdue], Purdue University [West Lafayette], ERC, Fonds National pour la Société Numérique, ANR, NSF, ANR-16-CE33-0001,HDWorlds,Modèles procéduraux paramétriques pour la représentation d'univers virtuels complexes(2016), European Project: 291184,EC:FP7:ERC,ERC-2011-ADG_20110209,EXPRESSIVE(2012), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), and Université de Lyon-Université Lumière - Lyon 2 (UL2)

Subjects
010504 meteorology & atmospheric sciences, Exploit, Landscapes, Computer science, Interface (Java), Terrain, 02 engineering and technology, 01 natural sciences, GeneralLiterature_MISCELLANEOUS, ACM: I.: Computing Methodologies/I.3: COMPUTER GRAPHICS, Computer graphics, 0202 electrical engineering, electronic engineering, information engineering, medicine, [INFO]Computer Science [cs], Ecosystem, ComputingMethodologies_COMPUTERGRAPHICS, 0105 earth and related environmental sciences, Vegetation, business.industry, Environmental resource management, 020207 software engineering, 15. Life on land, Computer Graphics and Computer-Aided Design, [INFO.INFO-GR]Computer Science [cs]/Graphics [cs.GR], Stochastic, Variety (cybernetics), Erosion, medicine.symptom, Simulation of Natural Phenomena, Vegetation (pathology), business
Abstract

The paper was presented at Siggraph 2017; International audience; We introduce a novel framework for interactive landscape authoring that supports bi-directional feedback between erosion and vegetation simulation. Vegetation and terrain erosion have strong mutual impact and their interplay innuences the overall realism of virtual scenes. Despite their importance, these complex interactions have been neglected in computer graphics. Our framework overcomes this by simulating the eeect of a variety of geomor-phological agents and the mutual interaction between diierent material and vegetation layers, including rock, sand, humus, grass, shrubs, and trees. Users are able to exploit these interactions with an authoring interface that consistently shapes the terrain and populates it with details. Our method, validated through side-by-side comparison with real terrains, can be used not only to generate realistic static landscapes, but also to follow the temporal evolution of a landscape over a few centuries.

Published
2017
Full Text
View/download PDF

3. Dendry: A Procedural Model for Dendritic Patterns

Author

Damien Rohmer, Bedrich Benes, Mathieu Gaillard, Marie-Paule Cani, Eric Galin, Eric Guérin, Guérin, Eric, Modèles procéduraux paramétriques pour la représentation d'univers virtuels complexes - - HDWorlds2016 - ANR-16-CE33-0001 - AAPG2016 - VALID, Department of Computer Science [Purdue], Purdue University [West Lafayette], Modélisation Géométrique, Géométrie Algorithmique, Fractales (GeoMod), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Université Lumière - Lyon 2 (UL2), Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X), Fonds National pour la Societé Numérique - PAPAYA P110720-2659260, ANR HDWorlds, and ANR-16-CE33-0001,HDWorlds,Modèles procéduraux paramétriques pour la représentation d'univers virtuels complexes(2016)

Subjects
Computer science, [INFO.INFO-GR] Computer Science [cs]/Graphics [cs.GR], 020207 software engineering, 02 engineering and technology, Function (mathematics), 010502 geochemistry & geophysics, 01 natural sciences, [INFO.INFO-GR]Computer Science [cs]/Graphics [cs.GR], Maxima and minima, Tree structure, 0202 electrical engineering, electronic engineering, information engineering, Range (statistics), Memory footprint, Geometric modeling, Procedural modeling, Algorithm, Smoothing, ComputingMilieux_MISCELLANEOUS, 0105 earth and related environmental sciences
Abstract

We introduce Dendry, a procedural function that generates dendritic patterns and is locally computable. The function is controlled by parameters such as the level of branching, the degree of local smoothing, random seeding and local disturbance parameters, and the range of the branching angles. It is also controlled by a global control function that defines the overall shape and can be used, for example, to initialize local minima. The algorithm returns the distance to a tree structure which is implicitly constructed on the fly, while requiring a small memory footprint. The evaluation can be performed in parallel for multiple points and scales linearly with the number of cores. We demonstrate an application of our model to the generation of terrain heighfields with consistent river networks. A quad core implementation of our algorithm takes about ten seconds for a 512 × 512 resolution grid on the CPU.

Published
2019

4. Verifying a Concurrent Garbage Collector with a Rely-Guarantee Methodology

Author

Jan Vitek, Gustavo Petri, Yannick Zakowski, Delphine Demange, David Cachera, Suresh Jagannathan, David Pichardie, École normale supérieure - Rennes (ENS Rennes), Software certification with semantic analysis (CELTIQUE), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-LANGAGE ET GÉNIE LOGICIEL (IRISA-D4), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Department of Computer Science [Purdue], Purdue University [West Lafayette], Northeastern University [Boston], ANR-14-CE28-0004,DISCOVER,Représentations Intermédiaires et Sémantiques de la Concurrence pour les Compilateurs Vérifiés(2014), Université de Bretagne Sud (UBS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-CentraleSupélec-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Bretagne Sud (UBS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes 1 (UR1), and Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique)

Subjects
Soundness, Intermediate language, [INFO.INFO-PL]Computer Science [cs]/Programming Languages [cs.PL], Programming language, Computer science, Concurrent data structure, Proof assistant, 020207 software engineering, 0102 computer and information sciences, 02 engineering and technology, computer.software_genre, 01 natural sciences, Computational Theory and Mathematics, 010201 computation theory & mathematics, Artificial Intelligence, TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS, 0202 electrical engineering, electronic engineering, information engineering, Compiler, computer, Software, Program logic, Garbage collection
Abstract

International audience; Concurrent garbage collection algorithms are a challenge for program verification. In this paper, we address this problem by proposing a mechanized proof methodology based on the Rely-Guarantee proof technique. We design a compiler intermediate representation with strong type guarantees, dedicated support for abstract concurrent data structures, and high-level iterators on runtime internals. In addition, we define an Rely-Guarantee program logic supporting an incremental proof methodology where annotations and invariants can be progressively enriched. We formalize the intermediate representation, the proof system, and prove the soundness of the methodology in the Coq proof assistant. Equipped with this, we prove a fully concurrent garbage collector where mutators never have to wait for the collector.

Published
2018
Full Text
View/download PDF

5. Feedforward Neural Networks for Caching: Enough or Too Much?

Author

Vladyslav Fedchenko, Bruno Ribeiro, Giovanni Neglia, Network Engineering and Operations (NEO ), 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), Department of Computer Science [Purdue], and Purdue University [West Lafayette]

Subjects
FOS: Computer and information sciences, Scheme (programming language), Computer Networks and Communications, Computer science, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Computer Science - Networking and Internet Architecture, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], 0202 electrical engineering, electronic engineering, information engineering, computer.programming_language, Networking and Internet Architecture (cs.NI), Hardware_MEMORYSTRUCTURES, Artificial neural network, business.industry, Estimator, 020206 networking & telecommunications, Recurrent neural network, 010201 computation theory & mathematics, Hardware and Architecture, Feedforward neural network, Artificial intelligence, business, computer, Software
Abstract

International audience; We propose a caching policy that uses a feedforward neural network (FNN) to predict content popularity. Our scheme outperforms popular eviction policies like LRU or ARC, but also a new policy relying on the more complex recurrent neural networks. At the same time, replacing the FNN predictor with a naive linear estimator does not degrade caching performance significantly, questioning then the role of neural networks for these applications.

Published
2018
Full Text
View/download PDF

6. Revisiting random walk based sampling in networks: Evasion of burn-in period and frequent regenerations

Author

Vivek S. Borkar, Arun Kadavankandy, Jithin K. Sreedharan, Konstantin Avrachenkov, Network Engineering and Operations (NEO ), 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), Department of Electrical Engineering [IIT-Bombay] (EE-IIT), Indian Institute of Technology Kanpur (IIT Kanpur), Department of Computer Science [Purdue], and Purdue University [West Lafayette]

Subjects
Mean squared error, Respondent-driven sampling, Computer science, Stability (learning theory), 02 engineering and technology, Stochastic approximation, 01 natural sciences, lcsh:QA75.5-76.95, [INFO.INFO-SI]Computer Science [cs]/Social and Information Networks [cs.SI], 010104 statistics & probability, symbols.namesake, [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], [MATH.MATH-ST]Mathematics [math]/Statistics [math.ST], Reinforcement learning, 0202 electrical engineering, electronic engineering, information engineering, 0101 mathematics, Network sampling, Random walks on graph, lcsh:T58.5-58.64, lcsh:Information technology, Research, Sampling (statistics), Estimator, 020206 networking & telecommunications, Markov chain Monte Carlo, Complex network, Random walk, Computer Science Applications, Human-Computer Interaction, Modeling and Simulation, symbols, lcsh:Electronic computers. Computer science, Algorithm, Information Systems
Abstract

International audience; Background: In the framework of network sampling, random walk (RW) based estimation techniques provide many pragmatic solutions while uncovering the unknown network as little as possible. Despite several theoretical advances in this area, RW based sampling techniques usually make a strong assumption that the samples are in stationary regime, and hence are impelled to leave out the samples collected during the burn-in period. Methods: This work proposes two sampling schemes without burn-in time constraint to estimate the average of an arbitrary function defined on the network nodes, for example, the average age of users in a social network. The central idea of the algorithms lies in exploiting regeneration of RWs at revisits to an aggregated super-node or to a set of nodes, and in strategies to enhance the frequency of such regenerations either by contracting the graph or by making the hitting set larger. Our first algorithm, which is based on reinforcement learning (RL), uses stochastic approximation to derive an estimator. This method can be seen as intermediate between purely stochastic Markov chain Monte Carlo iterations and deterministic relative value iterations. The second algorithm, which we call the Ratio with Tours (RT)-estimator, is a modified form of respondent-driven sampling (RDS) that accommodates the idea of regeneration. Results: We study the methods via simulations on real networks. We observe that the trajectories of RL-estimator are much more stable than those of standard random walk based estimation procedures, and its error performance is comparable to that of respondent-driven sampling (RDS) which has a smaller asymptotic variance than many other estimators. Simulation studies also show that the mean squared error of RT-esti-mator decays much faster than that of RDS with time. Conclusion: The newly developed RW based estimators (RL-and RT-estimators) allow to avoid burn-in period, provide better control of stability along the sample path, and overall reduce the estimation time. Our estimators can be applied in social and complex networks.

Published
2018
Full Text
View/download PDF

7. Verifying a Concurrent Garbage Collector using a Rely-Guarantee Methodology

Author

Gustavo Petri, David Cachera, Delphine Demange, Jan Vitek, David Pichardie, Yannick Zakowski, Suresh Jagannathan, Software certification with semantic analysis (CELTIQUE), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-LANGAGE ET GÉNIE LOGICIEL (IRISA-D4), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes 1 (UR1), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Department of Computer Science [Purdue], Purdue University [West Lafayette], Northeastern University [Boston], ANR 14-CE28-0004, NSF CCF- 1318227, CCF-1544542, SHF-1518844, ONR N00014-15-1-2332, ANR-14-CE28-0004,DISCOVER,Représentations Intermédiaires et Sémantiques de la Concurrence pour les Compilateurs Vérifiés(2014), Université de Bretagne Sud (UBS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-CentraleSupélec-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Bretagne Sud (UBS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), 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)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique)

Subjects
Soundness, Intermediate language, Computer science, Programming language, Concurrent data structure, Proof assistant, [SCCO.COMP]Cognitive science/Computer science, 020207 software engineering, 0102 computer and information sciences, 02 engineering and technology, computer.software_genre, 01 natural sciences, 010201 computation theory & mathematics, TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS, 0202 electrical engineering, electronic engineering, information engineering, Compiler, computer, Garbage collection, Program logic
Abstract

International audience; Concurrent garbage collection algorithms are an emblematic challenge in the area of concurrent program verification. In this paper, we address this problem by proposing a mechanized proof methodology based on the popular Rely-Guarantee (RG) proof technique. We design a specific compiler intermediate representation (IR) with strong type guarantees, dedicated support for abstract concurrent data structures, and high-level iterators on runtime internals. In addition, we define an RG program logic supporting an incremental proof methodology where annotations and invariants can be progressively enriched.We formalize the IR, the proof system, and prove the soundness of the methodology in the Coq proof assistant. Equipped with this IR, we prove a fully concurrent garbage collector where mutators never have to wait for the collector.

Published
2017
Full Text
View/download PDF

8. Inference in OSNs via Lightweight Partial Crawls

Author

Bruno Ribeiro, Jithin K. Sreedharan, Konstantin Avrachenkov, Models for the performance analysis and the control of networks (MAESTRO), 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), Department of Computer Science [Purdue], Purdue University [West Lafayette], Bell Labs Inria Joint Lab, and ADR Network Science

Subjects
Theoretical computer science, Computer science, Computer Networks and Communications, Bayesian inference, Context (language use), 02 engineering and technology, Crawling, computer.software_genre, 01 natural sciences, Social network analysis, 010104 statistics & probability, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], Graph sampling, 020204 information systems, 0202 electrical engineering, electronic engineering, information engineering, Random walk on graphs, 0101 mathematics, Random graph, Application programming interface, Social network, business.industry, Node (networking), Social network analysis (criminology), 020206 networking & telecommunications, Distributed algorithm, Hardware and Architecture, Data mining, Web crawler, business, computer, Software
Abstract

International audience; Are Online Social Network (OSN) A users more likely to form friendships with those with similar attributes? Do users at an OSN B score content more favorably than OSN C users? Such questions frequently arise in the context of Social Network Analysis (SNA) but often crawling an OSN network via its Application Programming Interface (API) is the only way to gather data from a third party. To date, these partial API crawls are the majority of public datasets and the synonym of lack of statistical guarantees in incomplete-data comparisons, severely limiting SNA research progress. Using regenerative properties of the random walks, we propose estimation techniques based on short crawls that have proven statistical guarantees. Moreover, our short crawls can be implemented in massively distributed algorithms. We also provide an adaptive crawler that makes our method parameter-free, significantly improving our statistical guarantees. We then derive the Bayesian approximation of the posterior of the estimates, and in addition, obtain an estima-tor for the expected value of node and edge statistics in an equivalent configuration model or Chung-Lu random graph model of the given network (where nodes are connected randomly) and use it as a basis for testing null hypotheses. The theoretical results are supported with simulations on a variety of real-world networks.

Published
2016
Full Text
View/download PDF

9. Parallelism in Matrix Computations

Author

Ahmed H. Sameh, Efstratios Gallopoulos, Bernard Philippe, 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), 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), Department of Computer Science [Purdue], Purdue University [West Lafayette], Department of Computer Engineering and Informatics [Patras], University of Patras, 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), University of Patras [Patras], Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), and Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)

Subjects
Analysis of parallel algorithms, Numerical linear algebra, Matrix-free methods, Computer science, MathematicsofComputing_NUMERICALANALYSIS, 020206 networking & telecommunications, 010103 numerical & computational mathematics, 02 engineering and technology, computer.software_genre, 01 natural sciences, Toeplitz matrix, Algebra, Matrix (mathematics), Fundamental matrix (linear differential equation), Matrix function, 0202 electrical engineering, electronic engineering, information engineering, 0101 mathematics, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Algorithm, computer, ComputingMilieux_MISCELLANEOUS, [MATH.MATH-NA]Mathematics [math]/Numerical Analysis [math.NA], Sparse matrix
Abstract

This book is primarily intended as a research monograph that could also be used in graduate courses for the design of parallel algorithms in matrix computations. It assumes general but not extensive knowledge of numerical linear algebra, parallel architectures, and parallel programming paradigms. The book consists of four parts: (I) Basics; (II) Dense and Special Matrix Computations; (III) Sparse Matrix Computations; and (IV) Matrix functions and characteristics. Part I deals with parallel programming paradigms and fundamental kernels, including reordering schemes for sparse matrices. Part II is devoted to dense matrix computations such as parallel algorithms for solving linear systems, linear least squares, the symmetric algebraic eigenvalue problem, and the singular-value decomposition. It also deals with the development of parallel algorithms for special linear systems such as banded, Vandermonde, Toeplitz, and block Toeplitz systems. Part III addresses sparse matrix computations: (a) the development of parallel iterative linear system solvers with emphasis on scalable preconditioners, (b) parallel schemes for obtaining a few of the extreme eigenpairs or those contained in a given interval in the spectrum of a standard or generalized symmetric eigenvalue problem, and (c) parallel methods for computing a few of the extreme singular triplets. Part IV focuses on the development of parallel algorithms for matrix functions and special characteristics such as the matrix pseudospectrum and the determinant. The book also reviews the theoretical and practical background necessary when designing these algorithms and includes an extensive bibliography that will be useful to researchers and students alike. The book brings together many existing algorithms for the fundamental matrix computations that have a proven track record of efficient implementation in terms of data locality and data transfer on state-of-the-art systems, as well as several algorithms that are presented for the first time, focusing on the opportunities for parallelism and algorithm robustness.

Published
2016
Full Text
View/download PDF

10. Atomicity Refinement for Verified Compilation

Author

Jan Vitek, Vincent Laporte, Gustavo Petri, David Pichardie, Suresh Jagannathan, Department of Computer Science [Purdue], Purdue University [West Lafayette], Software certification with semantic analysis (CELTIQUE), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-LANGAGE ET GÉNIE LOGICIEL (IRISA-D4), 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), 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), and Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)

Subjects
Mechanized proof assistant (Coq), Correctness, Java, Computer science, Concurrency, Compiler, Thread (computing), 0102 computer and information sciences, 02 engineering and technology, computer.software_genre, 01 natural sciences, Synchronization (computer science), 0202 electrical engineering, electronic engineering, information engineering, Abstraction (linguistics), computer.programming_language, Atomicity, [INFO.INFO-PL]Computer Science [cs]/Programming Languages [cs.PL], Programming language, Computer Graphics and Computer-Aided Design, Memory management, 010201 computation theory & mathematics, 020201 artificial intelligence & image processing, Memory model, computer, Software, Garbage collection, Memory semantics
Abstract

International audience; We consider the verified compilation of high-level managed languages like Java or C# whose intermediate representations provide support for shared-memory synchronization and automatic memory management. Our development is framed in the context of the Total Store Order relaxed memory model. Ensuring com-plier correctness is challenging because high-level actions are translated into sequences of non-atomic ac-tions with compiler-injected snippets of racy code; the behavior of this code depends not only on the actions of other threads, but also on out-of-order executions performed by the processor. A naïve proof of correctness would require reasoning over all possible thread interleavings. In this paper we propose a refinement-based proof methodology that precisely relates concurrent code expressed at different abstraction levels, cognizant throughout of the relaxed memory semantics of the underlying processor. Our technique allows the compiler writer to reason compositionally about the atomicity of low-level concurrent code used to implement man-aged services. We illustrate our approach with examples taken from the verification of a concurrent garbage collector.

Published
2014

11. Classification of Markov Sources Through Joint String Complexity: Theory and Experiments

Author

Dimitris Milioris, Wojciech Szpankowski, Philippe Jacquet, Alcatel-Lucent Bell Labs France [Nozay], Alcatel-Lucent Bell Labs France, High performance communication (HIPERCOM), 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-Sud - Paris 11 (UP11)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-École polytechnique (X)-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), École polytechnique (X), Department of Computer Science [Purdue], and Purdue University [West Lafayette]

Subjects
Discrete mathematics, Average-case complexity, TheoryofComputation_MISCELLANEOUS, String (computer science), 020206 networking & telecommunications, 0102 computer and information sciences, 02 engineering and technology, Descriptive complexity theory, 01 natural sciences, symbols.namesake, High Energy Physics::Theory, 010201 computation theory & mathematics, Markov algorithm, 0202 electrical engineering, electronic engineering, information engineering, symbols, Worst-case complexity, Communication complexity, Time complexity, Algorithm, Quantum complexity theory, Mathematics
Abstract

International audience; We propose a classification test to discriminate Markov sources based on the joint string complexity. String complexity is defined as the cardinality of a set of all distinct words (factors) of a given string. For two strings, we define the joint string complexity as the cardinality of the set of words which both strings have in common. In this paper we analyze the average joint complexity when both strings are generated by two Markov sources. We provide fast converging asymptotic expansions and present some experimental results showing usefulness of the joint complexity to text discrimination.

Published
2013

12. A Scalable Hybrid Linear Solver Based on Combinatorial Algorithms

Author

Sathe, Madan, Schenk, Olaf, Uçar, Bora, Sameh, Ahmed, Department of Computer Science (University of Basel), University of Basel (Unibas), Optimisation des ressources : modèles, algorithmes et ordonnancement (ROMA), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Department of Computer Science [Purdue], Purdue University [West Lafayette], Uwe Naumann and Olaf Schenk, École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), and 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)

Subjects
010201 computation theory & mathematics, 010103 numerical & computational mathematics, 0102 computer and information sciences, 0101 mathematics, 01 natural sciences, ComputingMilieux_MISCELLANEOUS
Abstract

International audience

Published
2012
Full Text
View/download PDF

13. On the Ehrenfeucht-Mycielski Balance Conjecture

Author

John C. Kieffer, Wojciech Szpankowski, Department of Electrical and Computer Engineering [Minneapolis] (ECE), University of Minnesota [Twin Cities] (UMN), University of Minnesota System-University of Minnesota System, Department of Computer Science [Purdue], Purdue University [West Lafayette], and Jacquet, Philippe

Subjects
Balance (metaphysics), Sequence, Conjecture, General Computer Science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG], 01 natural sciences, Pseudorandom binary sequence, Substring, Theoretical Computer Science, Combinatorics, [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], [INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG], 010201 computation theory & mathematics, Limit point, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], Ehrenfeucht-Mycielski sequence, Discrete Mathematics and Combinatorics, Interval (graph theory), Tree (set theory), Mathematics
Abstract

In 1992, A. Ehrenfeucht and J. Mycielski defined a seemingly pseudorandom binary sequence which has since been termed the EM-sequence. The balance conjecture for the EM-sequence, still open, is the conjecture that the sequence of EM-sequence initial segment averages converges to $1/2$. In this paper, we do not prove the balance conjecture but we do make some progress concerning it, namely, we prove that every limit point of the aforementioned sequence of averages lies in the interval $[1/4,3/4]$, improving the best previous result that every such limit point belongs to the interval $[0.11,0.89]$. Our approach is novel and exploits an analysis of the growth behavior as $n \to \infty$ of the rooted tree formed by the binary strings appearing at least twice as substrings of the length $n$ initial segment of the EM-sequence.

Published
2007

14. On the Exit Time of a Random Walk with Positive Drift

Author

Wojciech Szpankowski, Michael Drmota, Institut für Geometrie, Vienna University of Technology (TU Wien), Department of Computer Science [Purdue], Purdue University [West Lafayette], and Jacquet, Philippe

Subjects
General Computer Science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Random walk in the plane, Asymptotic distribution, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG], 01 natural sciences, Theoretical Computer Science, Quadrant (plane geometry), Combinatorics, Saddle point, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], 0202 electrical engineering, electronic engineering, information engineering, Discrete Mathematics and Combinatorics, Khodak code, number of paths, Mellin transform, Mathematics, Infinite number, Random walk, Abelian and tauberian theorems, [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], Tauberian theorems, [INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG], 010201 computation theory & mathematics, Bounded function, 020201 artificial intelligence & image processing, exit time, Tunstall's code
Abstract

We study a random walk with positive drift in the first quadrant of the plane. For a given connected region $\mathcal{C}$ of the first quadrant, we analyze the number of paths contained in $\mathcal{C}$ and the first exit time from $\mathcal{C}$. In our case, region $\mathcal{C}$ is bounded by two crossing lines. It is noted that such a walk is equivalent to a path in a tree from the root to a leaf not exceeding a given height. If this tree is the parsing tree of the Tunstall or Khodak variable-to-fixed code, then the exit time of the underlying random walk corresponds to the phrase length not exceeding a given length. We derive precise asymptotics of the number of paths and the asymptotic distribution of the exit time. Even for such a simple walk, the analysis turns out to be quite sophisticated and it involves Mellin transforms, Tauberian theorems, and infinite number of saddle points.

Published
2007

15. Multicast tree structure and the power law

Author

Leonidas Georgiadis, Cedric Adjih, Philippe Jacquet, Wojciech Szpankowski, High performance communication (HIPERCOM), 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-Sud - Paris 11 (UP11)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), Department of Electrical & Computer Engineering [Thessaloniki], Aristotle University of Thessaloniki, Laboratoire de Physique Corpusculaire - Clermont-Ferrand (LPC), Université Blaise Pascal - Clermont-Ferrand 2 (UBP)-Institut National de Physique Nucléaire et de Physique des Particules du CNRS (IN2P3)-Centre National de la Recherche Scientifique (CNRS), Department of Computer Science [Purdue], and Purdue University [West Lafayette]

Subjects
Discrete mathematics, Spanning tree, Theoretical computer science, Degree (graph theory), Multicast, ComputerSystemsOrganization_COMPUTER-COMMUNICATIONNETWORKS, 020206 networking & telecommunications, 0102 computer and information sciences, 02 engineering and technology, Data_CODINGANDINFORMATIONTHEORY, Library and Information Sciences, Network topology, 01 natural sciences, Computer Science Applications, Tree (data structure), [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], Tree structure, 010201 computation theory & mathematics, Reachability, Metric (mathematics), Computer Science::Networking and Internet Architecture, 0202 electrical engineering, electronic engineering, information engineering, Computer Science::Information Theory, Information Systems, Mathematics
Abstract

In this paper, we investigate structural properties of multicast trees that give rise to the so-called multicast power law. The law asserts that the ratio R(n) of the average number of links in a multicast tree connecting the source to n destinations to the average number of links in a unicast path, satisfies asymptotically R(n)/spl ap/cn/sup /spl phi//, 0

Published
2006
Full Text
View/download PDF

16. Philippe flajolet, the father of analytic combinatorics

Author

Wojciech Szpankowski, Brigitte Vallée, Bruno Salvy, Michèle Soria, Bob Sedgewick, Algorithms (ALGORITHMS), 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 [Princeton], Princeton University, Algorithmes, Programmes et Résolution (APR), 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), Department of Computer Science [Purdue], Purdue University [West Lafayette], Equipe AMACC - Laboratoire GREYC - UMR6072, Groupe de Recherche en Informatique, Image et Instrumentation de Caen (GREYC), Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), Normandie Université (NU)-Normandie Université (NU)-Université de Caen Normandie (UNICAEN), Normandie Université (NU)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), Normandie Université (NU), Bousquet-Mélou, Mireille, Wachs, Michelle, Hultman, Axel, Université de Caen Normandie (UNICAEN), Normandie Université (NU)-Normandie Université (NU)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), Normandie Université (NU)-Centre National de la Recherche Scientifique (CNRS)-Université de Caen Normandie (UNICAEN), and Normandie Université (NU)-Centre National de la Recherche Scientifique (CNRS)

Subjects
General Computer Science, media_common.quotation_subject, 02 engineering and technology, [MATH] Mathematics [math], 0102 computer and information sciences, [INFO] Computer Science [cs], 01 natural sciences, Prime (order theory), Theoretical Computer Science, Combinatorics, Mathematics (miscellaneous), 0202 electrical engineering, electronic engineering, information engineering, Discrete Mathematics and Combinatorics, [INFO]Computer Science [cs], [MATH]Mathematics [math], media_common, Mathematics, Taste (sociology), obituary, General Medicine, Obituary, Epistemology, Algebra, 010201 computation theory & mathematics, Curiosity, Analytic combinatorics, 020201 artificial intelligence & image processing, Algorithm, Philippe Flajolet, Computer Science(all)
Abstract

Philippe Flajolet, mathematician and computer scientist extraordinaire, suddenly passed away on March 22, 2011, at the prime of his career. He is celebrated for opening new lines of research in analysis of algo- rithms, developing powerful new methods, and solving difficult open problems. His research contributions will have impact for generations, and his approach to research, based on curiosity, a discriminating taste, broad knowledge and interest, intellectual integrity, and a genuine sense of camaraderie, will serve as an inspiration to those who knew him for years to come

Published
2011
Full Text
View/download PDF

17. On the multisearching problem for hypercubes

Author

Mikhail J. Atallah, Andreas Fabri, Department of Computer Science [Purdue], Purdue University [West Lafayette], Geometry, Algorithms and Robotics (PRISME), 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), Ce travail a été partiellement soutenu par National Science Foundation et Esprit Research Basic Action N°7141 (ALCOM II), and INRIA

Subjects
Control and Optimization, Parallel algorithms, Computer science, Trapezoidal decomposition, [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], Parallel algorithm, Multisearch, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Combinatorics, Set (abstract data type), Computer Science::Hardware Architecture, Multisearching, 0202 electrical engineering, electronic engineering, information engineering, Point location, Time complexity, Mathematics, Discrete mathematics, Sequence, Computer Sciences, Sorting, ComputerSystemsOrganization_PROCESSORARCHITECTURES, Binary logarithm, Computational geometry, Search tree, Computer Science Applications, 020202 computer hardware & architecture, Hypercube, Computational Mathematics, Computational Theory and Mathematics, 010201 computation theory & mathematics, 020201 artificial intelligence & image processing, Geometry and Topology, Constant (mathematics)
Abstract

We build on the work of Dehne and Rau-Chaplin and give improved bounds for the multisearch problem on a hypercube. This is a parallel search problem where the elements in the structure S to be searched are totally ordered, but where it is not possible to compare in constant time any two given queries q and q'. This problem is fundamental in computational geometry, for example it models planar point location in a slab. More precisely, we are given on a n-processor hypercube a sorted n-element sequence S and a set Q of n queries and we need to find for each query q [??]Q its location in the sorted S. Note that one cannot solve this problem by sorting S[??] Q, because every comparison- based parallel sorting algorithm needs to compare a pair q, q' [??]Q in constant time. We present an improved algorithm for the multisearch problem, one that takes 0(log n(log log n)3) time on a n-processor hypercube. This essentially replaces a logarithmic factor in the time complexities of previous schemes by a (log log n)3 factor. The hypercube model for which we claim our bounds is the standard one, with 0(1) memory registers per processor, and with one-port communication. Each register can store 0(log n) bits, so that a processor knows its ID.

Published
1994
Full Text
View/download PDF

18. Co-Design and Verification of an Available File System

Author

Patrick Eugster, Marc Shapiro, Mahsa Najafzadeh, Department of Computer Science [Purdue], Purdue University [West Lafayette], DistributEd aLgorithms and sYStems (DELYS), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Isil Dillig, and Jens Palsberg

Subjects
File system, Structure (mathematical logic), Computer science, Semantics (computer science), Concurrency, Strong consistency, 0102 computer and information sciences, 02 engineering and technology, computer.software_genre, 01 natural sciences, 010201 computation theory & mathematics, POSIX, 0202 electrical engineering, electronic engineering, information engineering, Operating system, 020201 artificial intelligence & image processing, [INFO]Computer Science [cs], Sequential model, Distributed File System, computer
Abstract

International audience; Distributed file systems play a vital role in large-scale enterprise services. However, the designer of a distributed file system faces a vexing choice between strong consistency and asynchronous replica-tion. The former supports a standard sequential model by synchronising operations, but is slow and fragile. The latter is highly available and responsive, but exposes users to concurrency anomalies. In this paper, we describe a rigorous and general approach to navigating this trade-off by leveraging static verification tools that allow to verify different file system designs. We show that common file system operations can run concurrently without synchronisation, while still retaining a semantics reasonably similar to Posix hierarchical structure. The one exception is the move operation, for which we prove that, unless synchronised, it will have an anomalous behaviour.

Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results