Search

Showing total 43 results
Start Over Topic computer networks and communications
43 results

1. An E-Commerce Process Model: Perspectives from E-Commerce Entrepreneurs

Author

David Paper, Keith R. Mulbery, and Eric Pedersen

Subjects
Marketing, Knowledge management, Process strategy, Computer Networks and Communications, business.industry, Process (engineering), Strategy and Management, E-commerce, Business model, Computer Science Applications, Ask price, Business, Set (psychology), Qualitative research
Abstract

The failure of dot-coms is a staggering 75% in the first two years. Many of these failures were small and medium-sized enterprises (SMEs). One of the most commonly cited reasons for failure has been lack of a workable strategic business model to guide e-commerce (electronic commerce) efforts. We began this study because we wanted to explore if successful e-commerce SMEs use a guiding strategic process model, and if they do, ask them to articulate the model components. We chose a qualitative research method to obtain a rich description of the e-commerce process. The interview pool consisted of 15 interviews with established SME e-commerce entrepreneurs. From deep analysis of the data, a set of e-commerce process components and interrelationships between those components emerged from the data. We then synthesized (from the rich description) a model of the e-commerce process.

Published
2003
Full Text
View/download PDF

6. Special Issue iJIM 'VANETS'

Author

Call For Papers

Subjects
Computer Networks and Communications, Computer Science Applications
Published
2011

27. Adaptive Request Scheduling for the I/O Forwarding Layer using Reinforcement Learning

Author

Philippe O. A. Navaux, Jean Luca Bez, Toni Cortes, Francieli Zanon Boito, Alberto Miranda, Ramon Nou, Instituto de Informática da UFRGS (UFRGS), Universidade Federal do Rio Grande do Sul [Porto Alegre] (UFRGS), Topology-Aware System-Scale Data Management for High-Performance Computing (TADAAM), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Data Aware Large Scale Computing (DATAMOVE ), 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 d'Informatique de Grenoble (LIG), Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA), Barcelona Supercomputing Center - Centro Nacional de Supercomputacion (BSC - CNS), This study was financed in part by the Coordenac¸ao de Aperfeicoamento de Pessoal de Nıvel Superior - Brasil (CAPES) - Finance Code 001. It has also received support from the Conselho Nacional de Desenvolvimento Cientıfico e Tecnologico (CNPq), Brazil, the LICIA International Laboratory, NCSA-Inria-ANL-BSC-JSC-Riken Joint-Laboratory on Extreme Scale Computing (JLESC), the Spanish Ministry of Science and Innovation under the TIN2015–65316 grant, and the Generalitat de Catalunya under contract 2014– SGR–1051. This research received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 800144. Experiments presented in this paper were carried out using the Grid’5000 testbed, supported by a scientific interest group hosted by Inria and including CNRS, RENATER and several Universities as well as other organizations (see https://www. grid5000.fr). The authors acknowledge the National Laboratory for Scientific Computing (LNCC/MCTI, Brazil) for providing HPC resources of the SDumont supercomputer, which have contributed to the research results reported within this paper., Universitat Politècnica de Catalunya. Departament d'Arquitectura de Computadors, Barcelona Supercomputing Center, Universitat Politècnica de Catalunya. CAP - Grup de Computació d'Altes Prestacions, and Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Inria Bordeaux - Sud-Ouest

Subjects
I/O forwarding, Parallel I/O, I/O scheduling, Computer Networks and Communications, Computer science, Distributed computing, Auto-tuning, 02 engineering and technology, Scheduling (computing), I/O Scheduling, I/O Forwarding, Machine learning, Reinforcement learning, Aprenentatge automàtic, 0202 electrical engineering, electronic engineering, information engineering, Informàtica::Arquitectura de computadors [Àrees temàtiques de la UPC], Input/output, High performance I/O, 020206 networking & telecommunications, Workload, Reinforcement Learning, Hardware and Architecture, Superordinadors, 020201 artificial intelligence & image processing, High performance computing, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Software
Abstract

In this paper, we propose an approach to adapt the I/O forwarding layer of HPC systems to applications’ access patterns. I/O optimization techniques can improve performance for the access patterns they were designed to target, but they often decrease performance for others. Furthermore, these techniques usually depend on the precise tune of their parameters, which commonly falls back to the users. Instead, we propose to do it dynamically at runtime based on the I/O workload observed by the system. Our approach uses a reinforcement learning technique – contextual bandits – to make the system capable of learning the best parameter value to each observed access pattern during its execution. That eliminates the need of a complicated and time-consuming previous training phase. Our case study is the TWINS scheduling algorithm, where performance improvements depend on the time window parameter, which in turn depends on the workload. We evaluate our proposal and demonstrate it can reach a precision of 88% on the parameter selection in the first hundreds of observations of an access pattern, achieving 99% of the optimal performance. We demonstrate that the system – which is expected to live for years – will be able to adapt to changes and optimize its performance after having observed an access pattern for a few (not necessarily contiguous) minutes. This study was financed in part by the Coordenaçao de Aperfeiçoamento de Pessoal de Nível Superior - Brasil (CAPES) - Finance Code 001. It has also received support from the Conselho Nacional de Desenvolvimento Científico e Tecnologico (CNPq), Brazil; the LICIA International Laboratory; NCSA-Inria-ANL-BSC-JSC-Riken Joint-Laboratory on Extreme Scale Computing (JLESC); the Spanish Ministry of Science and Innovation under the TIN2015–65316 grant; and the Generalitat de Catalunya under contract 2014– SGR–1051. This research received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 800144.

Published
2020
Full Text
View/download PDF

28. IR-UWB Radar-Based Robust Heart Rate Detection Using a Deep Learning Technique Intended for Vehicular Applications

Author

Khan, Faheem, Azou, Stéphane, Youssef, Roua, Morel, Pascal, Radoi, Emanuel, Laboratoire des sciences et techniques de l'information, de la communication et de la connaissance (Lab-STICC), École Nationale d'Ingénieurs de Brest (ENIB)-Université de Bretagne Sud (UBS)-Université de Brest (UBO)-École Nationale Supérieure de Techniques Avancées Bretagne (ENSTA Bretagne)-Institut Mines-Télécom [Paris] (IMT)-Centre National de la Recherche Scientifique (CNRS)-Université Bretagne Loire (UBL)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT), École Nationale d'Ingénieurs de Brest (ENIB), Equipe Architectures, Microwaves & Photonic Systems (Lab-STICC_ASMP), Institut Mines-Télécom [Paris] (IMT)-École Nationale d'Ingénieurs de Brest (ENIB)-Université de Bretagne Sud (UBS)-Université de Brest (UBO)-École Nationale Supérieure de Techniques Avancées Bretagne (ENSTA Bretagne)-Institut Mines-Télécom [Paris] (IMT)-Centre National de la Recherche Scientifique (CNRS)-Université Bretagne Loire (UBL)-IMT Atlantique (IMT Atlantique), Université de Brest (UBO), Equipe Security, Intelligence and Integrity of Information (Lab-STICC_SI3), This research has received funding from the European Union’s Horizon 2020 research and innovation program under the Marie Sklodowska-Curie grant agreement No 838037. The content of this paper only reflects the authors’ views and the Research Executive Agency is not responsible for any use that may be made of the information it contains., and European Project: 838037, UWB-IODA SF-PC

Subjects
ultra-wide band, Computer Networks and Communications, perceptive car, deep learning, [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], Hardware and Architecture, Control and Systems Engineering, heart rate detection, Signal Processing, [SDV.IB]Life Sciences [q-bio]/Bioengineering, Electrical and Electronic Engineering, interference mitigation, [SPI.SIGNAL]Engineering Sciences [physics]/Signal and Image processing
Abstract

International audience; This paper deals with robust heart rate detection intended for the in-car monitoring of people. There are two main problems associated with radar-based heart rate detection. Firstly, the signal associated with the human heart is difficult to separate from breathing harmonics in the frequency domain. Secondly, the vital signal is affected by any interference signal from hand gestures, lips motion during speech or any other random body motions (RBM). To handle the problem of the breathing harmonics, we propose a novel algorithm based on time series data instead of the conventionally used frequency domain technique. In our proposed method, a deep learning classifier is used to detect the pattern of the heart rate signal. To deal with the interference mitigation from the random body motions, we identify an optimum location for the radar sensor inside the car. In this paper, a commercially available Novelda Xethru X4 radar is used for signal acquisition and vital sign measurement of 5 people. The performance of the proposed algorithm is compared with and found to be superior to that of the conventional frequency domain technique.

Published
2022
Full Text
View/download PDF

29. Deciding feasibility of a booking in the European gas market on a cycle is in P for the case of passive networks

Author

Johannes Thürauf, Fränk Plein, Martine Labbé, Martin Schmidt, Integrated Optimization with Complex Structure (INOCS), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université libre de Bruxelles (ULB)-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), Département d'Informatique [Bruxelles] (ULB), Faculté des Sciences [Bruxelles] (ULB), Université libre de Bruxelles (ULB)-Université libre de Bruxelles (ULB), Trier University, Friedrich-Alexander Universität Erlangen-Nürnberg (FAU), and Martine Labbé has been partially supported by the Fonds de la Recherche Scientifique - FNRS under Grant no PDR T0098.18. Fränk Plein thanks the Fonds de la Recherche Scientifique - FNRS for his Aspirant fellowship supporting the research for this publication. He also thanks the Deutsche Forschungsgemeinschaft for their support within the project Z01 in CRC TRR 154. This research has been performed as part of the Energie Campus Nürnberg and is supported by funding of the Bavarian State Government. The third and fourth author also thank the DFG for their support within projects A05, B07, and B08 in CRC TRR 154. Finally, we want to thank Lars Schewe for many fruitful discussions on the topic of this paper.

Subjects
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], Gas networks, Mathematical optimization, Computational complexity theory, Computer Networks and Communications, Computer science, Dimension (graph theory), 0211 other engineering and technologies, System of polynomial equations, Modèles mathématiques d'aide à la décision, 02 engineering and technology, Cycle, Optimisation de réseaux, Informatique mathématique, 0502 economics and business, Real algebraic geometry, Time complexity, European entry-exit market, 050210 logistics & transportation, computational complexity, 021103 operations research, cycle, 05 social sciences, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], Maximization, potential-based flows, Potential-based flows, Computational complexity, Nonlinear system, Bookings, Flow (mathematics), bookings, Hardware and Architecture, 90B10, 90C30, 90C35, 90C90, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], gas networks, Software, Information Systems
Abstract

We show that the feasibility of a booking in the European entry-exit gas market can be decided in polynomial time on single-cycle networks that are passive, i.e. do not contain controllable elements. The feasibility of a booking can be characterized by solving polynomially many nonlinear potential-based flow models for computing so-called potential-difference maximizing load flow scenarios. We thus analyze the structure of these models and exploit both the cyclic graph structure as well as specific properties of potential-based flows. This enables us to solve the decision variant of the nonlinear potential-difference maximization by reducing it to a system of polynomials of constant dimension that is independent of the cycle's size. This system of fixed dimension can be handled with tools from real algebraic geometry to derive a polynomial-time algorithm. The characterization in terms of potential-difference maximizing load flow scenarios then leads to a polynomial-time algorithm for deciding the feasibility of a booking. Our theoretical results extend the existing knowledge about the complexity of deciding the feasibility of bookings from trees to single-cycle networks., SCOPUS: ar.j, info:eu-repo/semantics/published

Published
2021
Full Text
View/download PDF

30. Evolution Control for parallel ANN-assisted simulation-based optimization application to Tuberculosis Transmission Control

Author

Mohand-Said Mezmaz, Nouredine Melab, Romain Ragonnet, Guillaume Briffoteaux, Daniel Tuyttens, Optimisation de grande taille et calcul large échelle (BONUS), Inria Lille - Nord Europe, 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), University of Mons [Belgium] (UMONS), Monash University [Melbourne], 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), and Experiments presented in this paper were carried out using the Grid’5000 testbed, supported by a scientific interest group hosted by Inria and including CNRS, RENATER and several Universities as well as other organizations (see https://www.grid5000.fr).

Subjects
Artificial Neural Network, Computer Networks and Communications, Computer science, Monte Carlo method, Context (language use), 02 engineering and technology, [INFO.INFO-NE]Computer Science [cs]/Neural and Evolutionary Computing [cs.NE], Simulation-based optimization, Surrogate-assisted Optimization, 0202 electrical engineering, electronic engineering, information engineering, Massively parallel, Dropout (neural networks), Artificial neural network, Evolution Control, business.industry, Deep learning, 020206 networking & telecommunications, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], Supercomputer, Computer engineering, Hardware and Architecture, 020201 artificial intelligence & image processing, Artificial intelligence, Massively Parallel Computing, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], business, Software, Simulation
Abstract

International audience; In many optimal design searches, the function to optimise is a simulator that is computationally expensive. While current High Performance Computing (HPC) methods are not able to solve such problems efficiently, parallelism can be coupled with approximate models (surrogates or meta-models) that imitate the simulator in timely fashion to achieve better results. This combined approach reduces the number of simulations thanks to surrogate use whereas the remaining evaluations are handled by supercomputers. While the surrogates' ability to limit computational times is very attractive, integrating them into the over-arching optimization process can be challenging. Indeed, it is critical to address the major trade-off between the quality (precision) and the efficiency (execution time) of the resolution. In this article, we investigate Evolution Controls (ECs) which are strategies that define the alternation between the simulator and the surrogate within the optimization process. We propose a new EC based on the prediction uncertainty obtained from Monte Carlo Dropout (MCDropout), a technique originally dedicated to quantifying uncertainty in deep learning. Investigations of such uncertainty-aware ECs remain uncommon in surrogate-assisted evolutionary optimization. In addition, we use parallel computing in a complementary way to address the high computational burden. Our new strategy is implemented in the context of a pioneering application to Tuberculosis Transmission Control. The reported results show that the MCDropout-based EC coupled with massively parallel computing outperforms strategies previously proposed in the field of surrogate-assisted optimization.

Published
2020
Full Text
View/download PDF

31. Towards ultra-scale Branch-and-Bound using a high-productivity language

Author

Tiago Carneiro, Daniel Tuyttens, Jan Gmys, Nouredine Melab, Optimisation de grande taille et calcul large échelle (BONUS), Inria Lille - Nord Europe, 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), University of Mons [Belgium] (UMONS), and The experiments presented in this paper were carried out on the Grid’5000 testbed, hosted by INRIA and including several other organizations. Wethank Bradford Chamberlain, Elliot Ronaghan (Cray inc.) and Paul Hargrove (Berkeley lab.) for helping us to run GASNet on GRID5000. We also thank Michael Ferguson, Lydia Duncan (Cray inc.), and Louis Jenkins (University of Rochester) for their support on Chapel’s Gitter platform.

Subjects
POSIX Threads, Speedup, Branch and bound, Job shop scheduling, Computer Networks and Communications, Computer science, PGAS, Branch-and-Bound, 020206 networking & telecommunications, 02 engineering and technology, Parallel computing, Load balancing (computing), Hardware and Architecture, Ultra-scale optimization, Chapel, Scalability, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Partitioned global address space, MPI+X, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], computer, Software, computer.programming_language
Abstract

Due to the highly irregular nature and prohibitive execution times of Branch-and-Bound (B&B) algorithms applied to combinatorial optimization problems (COPs), their parallelization has received the se two last decades great attention. Indeed, significant efforts have been made to revisit the parallelization of B&B following the rapid evolution of high-performance computing technologies dealing with their associated scientific and technical challenges. However, these parallelization efforts have always been guided by the performance objective setting aside programming productivity. Nevertheless, this latter is crucial for designing ultra-scale algorithms able to harness modern supercomputers which are increasingly complex, including millions of processing cores and heterogeneous building-block devices. In this paper, we investigate the partitioned global address space (PGAS)-based approach using Chapel for the productivity-aware design and implementation of distributed B&B for solving large COPs. The proposed algorithms are intensively experimented using the Flow-shop scheduling problem as a test-case. The Chapel-based implementation is compared to its MPI+X-based traditionally used counterpart in terms of performance, scalability, and productivity. The results show that Chapel is much more expressive and up to 7 . 8 × more productive than MPI+Pthreads. In addition, the Chapel-based search presents performance equivalent to MPI+Pthreads for its best results on 1024 cores and reaches up to 84 % of the linear speedup. However, there are cases where the built-in load balancing provided by Chapel cannot produce regular load among computer nodes. In such cases, the MPI-based search can be up to 4 . 2 × faster and reaches speedups up to 3 × higher than its Chapel-based counterpart. Thorough feedback on the experience is given, pointing out the strengths and limitations of the two opposite approaches (Chapel vs. MPI+X). To the best of our knowledge, the present study is pioneering within the context of exact parallel optimization.

Published
2020
Full Text
View/download PDF

32. Energy-efficient joint video encoding and transmission framework for WVSN

Author

Youssef Fakhri, Patrick Corlay, Driss Aboutajdine, François-Xavier Coudoux, Othmane Alaoui-Fdili, Institut d’Électronique, de Microélectronique et de Nanotechnologie - UMR 8520 (IEMN), Centrale Lille-Institut supérieur de l'électronique et du numérique (ISEN)-Université de Valenciennes et du Hainaut-Cambrésis (UVHC)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université Polytechnique Hauts-de-France (UPHF), Laboratoire de Recherche en Informatique et Télécommunications [Rabat] (GSCM-LRIT), University of Mohammed V, COMmunications NUMériques - IEMN (COMNUM - IEMN), Institut d’Électronique, de Microélectronique et de Nanotechnologie - Département Opto-Acousto-Électronique - UMR 8520 (IEMN-DOAE), Centrale Lille-Institut supérieur de l'électronique et du numérique (ISEN)-Université de Valenciennes et du Hainaut-Cambrésis (UVHC)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université Polytechnique Hauts-de-France (UPHF)-Centrale Lille-Institut supérieur de l'électronique et du numérique (ISEN)-Université de Valenciennes et du Hainaut-Cambrésis (UVHC)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université Polytechnique Hauts-de-France (UPHF)-INSA Institut National des Sciences Appliquées Hauts-de-France (INSA Hauts-De-France)-Institut d’Électronique, de Microélectronique et de Nanotechnologie - UMR 8520 (IEMN), Centrale Lille-Institut supérieur de l'électronique et du numérique (ISEN)-Université de Valenciennes et du Hainaut-Cambrésis (UVHC)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université Polytechnique Hauts-de-France (UPHF)-Centrale Lille-Institut supérieur de l'électronique et du numérique (ISEN)-Université de Valenciennes et du Hainaut-Cambrésis (UVHC)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université Polytechnique Hauts-de-France (UPHF)-INSA Institut National des Sciences Appliquées Hauts-de-France (INSA Hauts-De-France), Faculté des Sciences [Kenitra], Université Ibn Tofaïl (UIT), Université Mohammed V de Rabat [Agdal] (UM5), Centrale Lille-Institut supérieur de l'électronique et du numérique (ISEN)-Université de Valenciennes et du Hainaut-Cambrésis (UVHC)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université Polytechnique Hauts-de-France (UPHF)-Centrale Lille-Institut supérieur de l'électronique et du numérique (ISEN)-Université de Valenciennes et du Hainaut-Cambrésis (UVHC)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université Polytechnique Hauts-de-France (UPHF), Centrale Lille-Institut supérieur de l'électronique et du numérique (ISEN)-Université de Valenciennes et du Hainaut-Cambrésis (UVHC)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université Polytechnique Hauts-de-France (UPHF)-Centrale Lille-Institut supérieur de l'électronique et du numérique (ISEN)-Université de Valenciennes et du Hainaut-Cambrésis (UVHC)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université Polytechnique Hauts-de-France (UPHF)-Institut d’Électronique, de Microélectronique et de Nanotechnologie - UMR 8520 (IEMN), and Acknowledgements This research was supported by the excellence fellowships program of the National Center for Scientific and Technical Research (CNRST) of Morocco (G01/003) and the Franco-Moroccan cooperation program in STICs for the research project 'RECIF'. The authors would also like to thank the editorial office Christian Malan, the editor-in-chief, the guest editors as well as the anonymous reviewers for their efforts and valuable comments and suggestions that have led to improvements in this paper.

Subjects
Computer Networks and Communications, Computer science, Real-time computing, 02 engineering and technology, Video quality, [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI], [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], [SPI]Engineering Sciences [physics], Packet loss, Video encoding, Region of interest, 0202 electrical engineering, electronic engineering, information engineering, Media Technology, [INFO]Computer Science [cs], Block-matching algorithm, "Energy-efficiency in WVSN", business.industry, 020206 networking & telecommunications, Scalable Video Coding, [SPI.TRON]Engineering Sciences [physics]/Electronics, "Video distortion prediction", Rate–distortion optimization, Transmission (telecommunications), Hardware and Architecture, "Cross-layer design", 020201 artificial intelligence & image processing, "Energy consumption prediction", business, [SPI.SIGNAL]Engineering Sciences [physics]/Signal and Image processing, Wireless sensor network, Encoder, "Energy-efficient reliable routing", Software, Computer network
Abstract

JIF=2.101; International audience; In this paper, we propose an energy-efficient joint video encoding and transmission framework for network lifetime extension, under an end-to-end video quality constraint in the Wireless Video Sensor Networks (WVSN). This framework integrates an energy-efficient and adaptive intra-only video encoding scheme based on the H.264/AVC standard, that outputs two service differentiated macroblocks categories, namely the Region Of Interest and the Background. Empirical models describing the physical behavior of the measured energies and distortions, during the video encoding and transmission phases, are derived. These models enable the video source node to dynamically adapt its video encoder's configuration in order to meet the desired quality, while extending the network lifetime. An energy-efficient and reliable multipath multi-priority routing protocol is proposed to route the encoded streams to the sink, while considering the remaining energy, the congestion level as well as the packet loss rates of the intermediate nodes. Moreover, this protocol interacts with the application layer in order to bypass congestion situations and continuously feed it with current statistics. Through extensive numerical simulations, we demonstrate that the proposed framework does not only extend the video sensor lifetime by 54%, but it also performs significant end-to-end video quality enhancement of 35% in terms of Mean Squared Error (MSE) measurement.

Published
2017
Full Text
View/download PDF

33. Automated and/or authentic intimacy: What can we learn about contemporary intimacy from the case of Ashley Madison’s bots?

Author

Katherine Harrison and This paper is based on research funded by the Danish Research Council of Independent Research as part of the 'New Media – New Intimacies' (NewMI) project, number: 4001-00229B FKK.

Subjects
Human-Computer Interaction, Public access, bots, intimacy, humanness, Ashley Madison, Computer Networks and Communications, business.industry, Internet privacy, Sociology, business, Web site
Abstract

In July 2015 the well-known affairs Web site, Ashley Madison, was hacked and both customer details and internal company correspondence were stolen, and later dumped online for public access. In the analysis of the data, it became clear that the site had extensively used bots to attract customers. This paper brings together these bots with a short story by Candas Jane Dorsey about the discomfiting potential of human-machine intimacies. I use the two to help me explore what I argue is an inbuilt and little discussed expectation/requirement of “authentic” intimacy: humanness.

Published
2019

34. Classification of Broadcast News Audio Data Employing Binary Decision Architecture

Author

Peter Feciľak, Anton Čižmár, Jozef Juhar, Jozef Vavrek, and The research in this paper was supported by the Ministry of Education, Science, Research and Sport of the Slovak Republic under the project VEGA 2/0197/15 and the Slovak Research and Development Agency under the project APVV-15-0517.

Subjects
0209 industrial biotechnology, Computational complexity theory, Computer Networks and Communications, Computer science, Binary number, 68T10, 02 engineering and technology, computer.software_genre, Multiclass classification, 020901 industrial engineering & automation, 0202 electrical engineering, electronic engineering, information engineering, Architecture, Support vector machine, audio classification, broadcast news data, binary decision trees, binary decision architecture, other areas of Computing and Informatics, Binary decision diagram, business.industry, 020208 electrical & electronic engineering, Pattern recognition, Support vector machine, ComputingMethodologies_PATTERNRECOGNITION, Computational Theory and Mathematics, Hardware and Architecture, Data mining, Artificial intelligence, Decision table, business, computer, Classifier (UML), Software
Abstract

A novel binary decision architecture (BDA) for broadcast news audio classification task is presented in this paper. The idea of developing such architecture came from the fact that the appropriate combination of multiple binary classifiers for two-class discrimination problem can reduce a miss-classification error without rapid increase in computational complexity. The core element of classification architecture is represented by a binary decision (BD) algorithm that performs discrimination between each pair of acoustic classes, utilizing two types of decision functions. The first one is represented by a simple rule-based approach in which the final decision is made according to the value of selected discrimination parameter. The main advantage of this solution is relatively low processing time needed for classification of all acoustic classes. The cost for that is low classification accuracy. The second one employs support vector machine (SVM) classifier. In this case, the overall classification accuracy is conditioned by finding the optimal parameters for decision function resulting in higher computational complexity and better classification performance. The final form of proposed BDA is created by combining four BD discriminators supplemented by decision table. The effectiveness of proposed BDA, utilizing rule-based approach and the SVM classifier, is compared with two most popular strategies for multiclass classification, namely the binary decision trees (BDT) and the One-Against-One SVM (OAOSVM). Experimental results show that the proposed classification architecture can decrease the overall classification error in comparison with the BDT architecture. On the contrary, an optimization technique for selecting the optimal set of training data is needed in order to overcome the OAOSVM.

Published
2017
Full Text
View/download PDF

35. Evaluation and Implementation of n-Gram-Based Algorithm for Fast Text Comparison

Author

Maciej Wielgosz, Dominik Zurek, Marcin Pietron, Kazimierz Wiatr, Pawel Grzegorz Russek, Ernest Jamro, Pawel Szczepka, and The work presented in this paper was financed by Polish National Center for Research and Development through Synat (SP/I/1/77065/10), PLGrid Plus (POIG.02.03.00-00-096/10) and PLGrid Core (POIG.02.03.00-12-137/13) research programs.

Subjects
0106 biological sciences, n-gram, Knowledge and Information Engineering, Computational Theory and Mathematics, Computer Networks and Communications, Hardware and Architecture, Computer science, Text similarity analysis, n-gram-based model, GPGPU implementation, multi-CPU implementation, 010603 evolutionary biology, 01 natural sciences, Algorithm, Software, 010606 plant biology & botany
Abstract

This paper presents a study of an n-gram-based document comparison method. The method is intended to build a large-scale plagiarism detection system. The work focuses not only on an efficiency of the text similarity extraction but also on the execution performance of the implemented algorithms. We took notice of detection performance, storage requirements and execution time of the proposed approach. The obtained results show the trade-offs between detection quality and computational requirements. The GPGPU and multi-CPU platforms were considered to implement the algorithms and to achieve good execution speed. The method consists of two main algorithms: a document's feature extraction and fast text comparison. The winnowing algorithm is used to generate a compressed representation of the analyzed documents. The authors designed and implemented a dedicated test framework for the algorithm. That allowed for the tuning, evaluation, and optimization of the parameters. Well-known metrics (e.g. precision, recall) were used to evaluate detection performance. The authors conducted the tests to determine the performance of the winnowing algorithm for obfuscated and unobfuscated texts for a different window and n-gram size. Also, a simplified version of the text comparison algorithm was proposed and evaluated to reduce the computational complexity of the text comparison process. The paper also presents GPGPU and multi-CPU implementations of the algorithms for different data structures. The implementation speed was tested for different algorithms' parameters and the size of data. The scalability of the algorithm on multi-CPU platforms was verified. The authors of the paper provide the repository of software tools and programs used to perform the conducted experiments.he appropriate fast document comparison system. Its performance is given in the paper.

Published
2017
Full Text
View/download PDF

36. Expressiveness of component-based frameworks: A study of the expressiveness of BIP

Author

Simon Bliudze, Eduard Baranov, UCL - SST/ICTM/INGI - Pôle en ingénierie informatique, Inria, Université Catholique de Louvain = Catholic University of Louvain [UCL], Self-adaptation for distributed services and large software systems [SPIRALS], Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL], Université Catholique de Louvain = Catholic University of Louvain (UCL), Self-adaptation for distributed services and large software systems (SPIRALS), Inria Lille - Nord Europe, 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), The contribution of Simon Bliudze to the work presented in this paper has been partially funded by Hauts-de-France regional STaRS programme under the grant agreement № 2019.00170., Université Catholique de Louvain (UCL), Ecole Centrale de Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Ecole Centrale de Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), and Ecole Centrale de Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)

Subjects
Computer Networks and Communications, Semantics (computer science), Computer science, 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-SE]Computer Science [cs]/Software Engineering [cs.SE], SOS formats, glue operators, component-based frameworks, BIP, expressiveness, computer.software_genre, 01 natural sciences, Operational semantics, Component (UML), 0202 electrical engineering, electronic engineering, information engineering, Algebraic number, [INFO.INFO-PL]Computer Science [cs]/Programming Languages [cs.PL], Hierarchy (mathematics), Programming language, 020207 software engineering, 16. Peace & justice, 010201 computation theory & mathematics, [INFO.INFO-MA]Computer Science [cs]/Multiagent Systems [cs.MA], Theory of computation, computer, Software, Information Systems
Abstract

International audience; We extend our previous algebraic formalisation of the notion of component-based framework in order to formally define two forms---strong and weak---of the notion of full expressiveness and study their properties. Our earlier result shows that the BIP (Behaviour-Interaction-Priority) framework does not possess the strong full expressiveness with respect to the sub-class of GSOS rules used for the definition of its semantics. In this paper, we refine this comparison detailing the expressiveness of classical BIP, Offer BIP and a number of variations obtained either by relaxing the constraints in the definition of priority models or by introducing positive premises into the rule formats used to define the operational semantics of composition operators. The obtained results are organised into an expressiveness hierarchy.

Published
2019
Full Text
View/download PDF

37. On the Performance of Sliding Window TD-LMMSE Channel Estimation for 5G Waveforms in High Mobility Scenario

Author

Marion Berbineau, Iyad Dayoub, Michel Saideh, Département Composants et Systèmes (IFSTTAR/COSYS), Institut Français des Sciences et Technologies des Transports, de l'Aménagement et des Réseaux (IFSTTAR)-Université de Lyon-PRES Université Nantes Angers Le Mans (UNAM)-PRES Université Lille Nord de France, Institut d’Électronique, de Microélectronique et de Nanotechnologie - Département Opto-Acousto-Électronique - UMR 8520 (IEMN-DOAE), Institut d’Électronique, de Microélectronique et de Nanotechnologie - UMR 8520 (IEMN), Centrale Lille-Institut supérieur de l'électronique et du numérique (ISEN)-Université de Valenciennes et du Hainaut-Cambrésis (UVHC)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université Polytechnique Hauts-de-France (UPHF)-Centrale Lille-Institut supérieur de l'électronique et du numérique (ISEN)-Université de Valenciennes et du Hainaut-Cambrésis (UVHC)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université Polytechnique Hauts-de-France (UPHF), COMmunications NUMériques - IEMN (COMNUM - IEMN), Centrale Lille-Institut supérieur de l'électronique et du numérique (ISEN)-Université de Valenciennes et du Hainaut-Cambrésis (UVHC)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université Polytechnique Hauts-de-France (UPHF)-Centrale Lille-Institut supérieur de l'électronique et du numérique (ISEN)-Université de Valenciennes et du Hainaut-Cambrésis (UVHC)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université Polytechnique Hauts-de-France (UPHF)-Institut d’Électronique, de Microélectronique et de Nanotechnologie - UMR 8520 (IEMN), Centrale Lille-Institut supérieur de l'électronique et du numérique (ISEN)-Université de Valenciennes et du Hainaut-Cambrésis (UVHC)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université Polytechnique Hauts-de-France (UPHF), INSA Institut National des Sciences Appliquées Hauts-de-France (INSA Hauts-De-France), Institut National des Sciences Appliquées (INSA), This work was supported in part by the SMARTIES project within theELSAT2020 program supported by FEDER, the French State, and the Haut deFrance Region and in part by the X2RAIL-1 project from H2020 SHIF2RAILprogram. The review of this paper was coordinated by Dr. N.-D. Dao., PRES Université Lille Nord de France-PRES Université Nantes Angers Le Mans (UNAM)-Université de Lyon-Institut Français des Sciences et Technologies des Transports, de l'Aménagement et des Réseaux (IFSTTAR), Centrale Lille-Institut supérieur de l'électronique et du numérique (ISEN)-Université de Valenciennes et du Hainaut-Cambrésis (UVHC)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université Polytechnique Hauts-de-France (UPHF)-Centrale Lille-Institut supérieur de l'électronique et du numérique (ISEN)-Université de Valenciennes et du Hainaut-Cambrésis (UVHC)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université Polytechnique Hauts-de-France (UPHF)-INSA Institut National des Sciences Appliquées Hauts-de-France (INSA Hauts-De-France)-Institut d’Électronique, de Microélectronique et de Nanotechnologie - UMR 8520 (IEMN), and Centrale Lille-Institut supérieur de l'électronique et du numérique (ISEN)-Université de Valenciennes et du Hainaut-Cambrésis (UVHC)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université Polytechnique Hauts-de-France (UPHF)-Centrale Lille-Institut supérieur de l'électronique et du numérique (ISEN)-Université de Valenciennes et du Hainaut-Cambrésis (UVHC)-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Université Polytechnique Hauts-de-France (UPHF)-INSA Institut National des Sciences Appliquées Hauts-de-France (INSA Hauts-De-France)

Subjects
CHANNEL ESTIMATION, Computer Networks and Communications, Orthogonal frequency-division multiplexing, Computer science, Monte Carlo method, Aerospace Engineering, 02 engineering and technology, [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI], TRAITEMENT DU SIGNAL, TECHNOLOGIE SANS FIL, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], [SPI]Engineering Sciences [physics], TELECOMMUNICATION, LMMSE, Sliding window protocol, 0202 electrical engineering, electronic engineering, information engineering, Waveform, [INFO]Computer Science [cs], Time domain, Electrical and Electronic Engineering, ONDE, Computer Science::Information Theory, 020208 electrical & electronic engineering, 020206 networking & telecommunications, FBMC, Filter bank, Computer Science::Other, [SPI.TRON]Engineering Sciences [physics]/Electronics, TRANSPORT FERROVIAIRE, Modulation, Automotive Engineering, SIMULATION, Algorithm, [SPI.SIGNAL]Engineering Sciences [physics]/Signal and Image processing, 5G, Communication channel
Abstract

The upcoming 5G era is considered as a critical answer to future railway communication needs. In this correspondence, we analyze the performance of sliding window time domain (TD) LMMSE channel estimation technique where a generalized development is proposed and analyzed for 5G filter bank multicarrier-offset quadratic-amplitude modulation waveform candidates. In order to enhance performance, the analytical model is extended to exploit multipaths and multiantennas correlation wherever they do exist e.g., tunnels. TD-LMMSE performance for 5G waveforms and achieved enhancements are verified by Monte Carlo simulations.

Published
2018
Full Text
View/download PDF

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

Author

Ralf Klasing, Adrian Kosowski, Colin Cooper, David Ilcinkas, Department of Computer Science (DCS), King‘s College London, Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Combinatoire et Algorithmique, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), See paper for details., ANR-07-BLAN-0322,ALADDIN,Algorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks(2007), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Department of Algorithms and Systems Modelling [ETI GUT] (Gdansk University of Technology), Faculty of Electronics, Telecommunications and Informatics [GUT Gdańsk] (ETI), Gdańsk University of Technology (GUT)-Gdańsk University of Technology (GUT), ANR-05-MMSA-0006,ALPAGE,ALgorithmique des Plates-formes A Grande Echelle(2005), Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), and Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)

Subjects
Mathematical optimization, Computer Networks and Communications, Computer science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Comparability graph, Random walk, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, law.invention, Theoretical Computer Science, Combinatorics, Indifference graph, Graph exploration, law, Graph power, Line graph, Random regular graph, 0202 electrical engineering, electronic engineering, information engineering, Pancyclic graph, Mathematics, Discrete mathematics, Block graph, graph exploration : Propp machine, Directed graph, Feedback arc set, Computational Theory and Mathematics, 010201 computation theory & mathematics, Hardware and Architecture, Robbins' theorem, Graph (abstract data type), 020201 artificial intelligence & image processing, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], MathematicsofComputing_DISCRETEMATHEMATICS
Abstract

International audience; We consider the problem of exploring an anonymous undirected graph using an oblivious robot. The studied exploration strategies are designed so that the next edge in the robot's walk is chosen using only local information, and so that some local equity (fairness) criterion is satisfied for the adjacent undirected edges. Such strategies can be seen as an attempt to derandomize random walks, and are natural counterparts for undirected graphs of the rotor-router model for symmetric directed graphs. The first of the studied strategies, known as Oldest-First (OF), always chooses the neighboring edge for which the most time has elapsed since its last traversal. Unlike in the case of symmetric directed graphs, we show that such a strategy in some cases leads to exponential cover time. We then consider another strategy called Least-Used-First (LUF) which always uses adjacent edges which have been traversed the smallest number of times. We show that any Least-Used-First exploration covers a graph G=(V,E) of diameter diam within time O(diam|E|), and in the long run traverses all edges of G with the same frequency.

Published
2011
Full Text
View/download PDF

39. The cost of monotonicity in distributed graph searching

Author

Nicolas Nisse, David Soguet, David Ilcinkas, Département d'Informatique et d'Ingénierie (DII), Université du Québec en Outaouais (UQO), Laboratoire de Recherche en Informatique (LRI), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Additional supports from the project 'Fragile' of the ACI Sécurité Informatique, and from the project 'Grand Large' of INRIA., Eduardo Tovar, Philippas Tsigas, Hacène Fouchal, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), See paper for details., ANR-07-BLAN-0322,ALADDIN,Algorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks(2007), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)

Subjects
Monotonicity, Mathematical optimization, Theoretical computer science, Computer Networks and Communications, Computer science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 050801 communication & media studies, 0102 computer and information sciences, 02 engineering and technology, Strength of a graph, Biconnected graph, 01 natural sciences, Theoretical Computer Science, law.invention, 0508 media and communications, Graph power, law, Line graph, 0202 electrical engineering, electronic engineering, information engineering, Graph property, Complement graph, Graph searching, Distance-hereditary graph, Mobile agent, Discrete mathematics, 020203 distributed computing, 05 social sciences, Voltage graph, Directed graph, Butterfly graph, Competitive ratio, Graph bandwidth, Computational Theory and Mathematics, 010201 computation theory & mathematics, Hardware and Architecture, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Null graph, Graph factorization, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract

International audience; Blin {\it et al.} (2006) proposed a distributed protocol that enables the smallest number of searchers to clear any unknown asynchronous graph in a decentralized manner. {\it Unknown} means that the searchers are provided no {\it a priori} information about the graph. However, the strategy that is actually performed lacks of an important property, namely the monotonicity. That is, the clear part of the graph may decrease at some steps of the execution of the protocol. Actually, the protocol of Blin {\it et al.} is executed in exponential time. Nisse and Soguet (2007) proved that, in order to ensure the smallest number of searchers to clear any $n$-node graph in a monotone way, it is necessary and sufficient to provide $\Theta(n \log n)$ bits of information to the searchers by putting short labels on the nodes of the graph. This paper deals with the smallest number of searchers that are necessary and sufficient to monotoneously clear any graph in a decentralized manner, when the searchers have no a priori information about the graph. The distributed graph searching problem considers a team of searchers that is aiming at clearing any connected contaminated graph. The clearing of the graph is required to be {\it connected}, i.e., the clear part of the graph must remain permanently connected, and {\it monotone}, i.e., the clear part of the graph only grows. The {\it search number} $\mcs(G)$ of a graph $G$ is the smallest number of searchers necessary to clear $G$ in a monotone connected way in centralized settings. We prove that any distributed protocol aiming at clearing any unknown n-node graph in a monotone connected way, in decentralized settings, has {\it competitive ratio} $\Theta(\frac{n}{\log n})$. That is, we prove that, for any distributed protocol $\cal P$, there exists a constant $c$ such that for any sufficiently large $n$, there exists a $n$-node graph $G$ such that $\cal P$ requires at least $c\frac{n}{\log n}\, \mcs(G)$ searchers to clear $G$. Moreover, we propose a distributed protocol that allows $O(\frac{n}{\log n})\, \mcs(G)$ searchers to clear any unknown asynchronous $n$-node graph $G$ in a monotone connected way.

Published
2009
Full Text
View/download PDF

40. Analyzing the exhaustiveness of the synapse protocol

Author

Vincenzo Ciancaglini, Zoran Ognjanović, Bojan Marinković, Paola Glavan, Luigi Liquori, Petar Maksimovic, Mathematical Institute of the Serbian Academy of Sciences and Arts, Serbian Academy of Sciences and Arts (SASA), Logical Networks: Self-organizing Overlay Networks and Programmable Overlay Computing Systems (LOGNET), 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), University of Zagreb, and The work presented in this paper was supported by the Serbian Ministry of Education, Science and Technological Development, projects ON174026 and III44006, through Matematicki Institut SANU and by Ministarstvo znanosti, obrazovanja i sporta republike Hrvatske.

Subjects
Theoretical computer science, Computer Networks and Communications, Computer science, Distributed computing, Overlay network, 0102 computer and information sciences, 02 engineering and technology, Peer-to-peer, computer.software_genre, 01 natural sciences, [INFO.INFO-SI]Computer Science [cs]/Social and Information Networks [cs.SI], Synapse, ACM: F.: Theory of Computation/F.3: LOGICS AND MEANINGS OF PROGRAMS, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], 0202 electrical engineering, electronic engineering, information engineering, Abstract State Machines, Protocol (object-oriented programming), Computer communication networks, Retrieval probability, Formal description, Quantitative Biology::Neurons and Cognition, DASM, Peer-to-Peer Protocols, ACM: F.: Theory of Computation/F.3: LOGICS AND MEANINGS OF PROGRAMS/F.3.1: Specifying and Verifying and Reasoning about Programs, ACM: C.: Computer Systems Organization/C.2: COMPUTER-COMMUNICATION NETWORKS, [MATH.MATH-LO]Mathematics [math]/Logic [math.LO], DHT-based overlay networks, 010201 computation theory & mathematics, ACM: C.: Computer Systems Organization/C.2: COMPUTER-COMMUNICATION NETWORKS/C.2.2: Network Protocols, Scalability, Abstract state machines, 020201 artificial intelligence & image processing, computer, Software
Abstract

International audience; The Synapse protocol is a scalable protocol designed for information retrieval over inter-connected heterogeneous overlay networks. In this paper, we give a formal description of Synapse using the Abstract State Machines framework. The formal description pertains to Synapse actions that manipulate distributed keys. Based on this formal description, we present results concerning the expected exhaustiveness for a number of scenarios and systems maintained by the Synapse protocol, and provide comparisons to the results of the corresponding simulations and experiments. We show that the predicted theoretical results match the obtained experimental results, and give recommendations on the design of systems using Synapse.

Published
2015
Full Text
View/download PDF

41. Disconnected Components Detection and Rooted Shortest-Path Tree Maintenance in Networks

Author

Christian Glacet, Nicolas Hanusse, Colette Johnen, David Ilcinkas, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), ANR-16-CE40-0023,DESCARTES,Abstraction modulaire pour le calcul distribué(2016), ANR-16-CE25-0009,ESTATE,Auto-stabilisation et amélioration de la sûreté dans les environnements distribués évoluant dans le temps(2016), ANR-10-IDEX-0003,IDEX BORDEAUX,Initiative d'excellence de l'Université de Bordeaux(2010), See paper for details., and ANR-11-BS02-0014,DISPLEXITY,Calculabilité et complexité en distribué(2011)

Subjects
Routing protocol, Leader election, Theoretical computer science, Computer Networks and Communications, Computer science, 02 engineering and technology, Theoretical Computer Science, Artificial Intelligence, shortest-path, disconnected network, Node (computer science), 0202 electrical engineering, electronic engineering, information engineering, Mathematics, Discrete mathematics, Connected component, routing algorithm, business.industry, Shortest-path tree, 020206 networking & telecommunications, Task (computing), Tree (data structure), self-stabilization, Hardware and Architecture, Asynchronous communication, Shortest path problem, 020201 artificial intelligence & image processing, Enhanced Data Rates for GSM Evolution, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Daemon, business, Software, Computer network
Abstract

Many articles deal with the problem of maintaining a rooted shortest-path tree. However, after some edge deletions, some nodes can be disconnected from the connected component V r of some distinguished node r . In this case, an additional objective is to ensure the detection of the disconnection by the nodes that no longer belong to V r . We present a detailed analysis of a silent self-stabilizing algorithm. We prove that it solves this more demanding task in anonymous weighted networks with the following additional strong properties: it runs without any knowledge on the network and under the unfair daemon, that is without any assumption on the asynchronous model. Moreover, it terminates in less than 2 n + D rounds for a network of n nodes and hop-diameter D .

Published
2014
Full Text
View/download PDF

42. Communication algorithms with advice

Author

Pierre Fraigniaud, Andrzej Pelc, David Ilcinkas, Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Département d'Informatique et d'Ingénierie (DII), Université du Québec en Outaouais (UQO), See paper for details., ANR-07-BLAN-0322,ALADDIN,Algorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks(2007), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), and Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest

Subjects
Computer Networks and Communications, Distributed computing, Message complexity, Network, 0102 computer and information sciences, 02 engineering and technology, Broadcasting, 01 natural sciences, Graph, Theoretical Computer Science, 0202 electrical engineering, electronic engineering, information engineering, Size of advice, Dissemination, Mathematics, Linear number, business.industry, Applied Mathematics, Telecommunications network, Algorithm, Computational Theory and Mathematics, 010201 computation theory & mathematics, Broadcast communication network, Graph (abstract data type), 020201 artificial intelligence & image processing, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], business, Advice (complexity), Wakeup
Abstract

International audience; We study the amount of knowledge about a communication network that must be given to its nodes in order to efficiently disseminate information. Our approach is {\em quantitative}: we investigate the minimum total number of bits of information (minimum size of advice) that has to be available to nodes, regardless of the type of information provided. We compare the size of advice needed to perform broadcast and wakeup (the latter is a broadcast in which nodes can transmit only after getting the source information), both using a linear number of messages (which is optimal). We show that the minimum size of advice permitting the {\em wakeup} with a linear number of messages in a $n$-node network, is $\Theta (n \log n)$, while the {\em broadcast} with a linear number of messages can be achieved with advice of size $O(n)$. We also show that the latter size of advice is almost optimal: no advice of size $o(n)$ can permit to broadcast with a linear number of messages. Thus an efficient wakeup requires strictly more information about the network than an efficient broadcast.

Published
2010
Full Text
View/download PDF

43. Distributed Computing with Advice: Information Sensitivity of Graph Coloring

Author

Andrzej Pelc, Cyril Gavoille, Pierre Fraigniaud, David Ilcinkas, Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Département d'Informatique et d'Ingénierie (DII), Université du Québec en Outaouais (UQO), See paper for details., ANR-07-BLAN-0322,ALADDIN,Algorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks(2007), Andrzej Pelc was supported in part by NSERC discovery grant and by the Research Chair in Distributed Computing of the Université du Québec en Outaouais., Lars Arge, Christian Cachin, Tomasz Jurdzinski, Andrzej Tarlecki, Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), and Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest

Subjects
Network algorithms, Theoretical computer science, Computer Networks and Communications, Computer science, Distributed computing, Computation, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, 02 engineering and technology, network algorithm, 01 natural sciences, Oracle, Theoretical Computer Science, Distributed coloring, Greedy coloring, distributed computing, graph coloring, 0202 electrical engineering, electronic engineering, information engineering, Graph coloring, Advice, Computer communication networks, Information sensitivity, Computational Theory and Mathematics, Hardware and Architecture, 010201 computation theory & mathematics, Theory of computation, Graph (abstract data type), 020201 artificial intelligence & image processing, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
Abstract

International audience; We study the problem of the amount of information (advice) about a graph that must be given to its nodes in order to achieve fast distributed computations. The required size of the advice enables to measure the information sensitivity of a network problem. A problem is information sensitive if little advice is enough to solve the problem rapidly (i.e., much faster than in the absence of any advice), whereas it is information insensitive if it requires giving a lot of information to the nodes in order to ensure fast computation of the solution. In this paper, we study the information sensitivity of distributed graph coloring.

Published
2007
Full Text
View/download PDF