OpenRaiser/Intern-Atlas huggingface dataset:
Scheduling on Grid with communication Delay
Venue: arXiv cs.DC 2015
Year: 2015

Parallel processing, the core of High Performance Computing (HPC), was and still the most effective way in improving the speed of computer systems. For the past few years, the substantial developments in the computing power of processors and the network speed have strikingly changed the landscape of HPC. Geography distributed heterogeneous systems can now cooperate and share resources to execute one application. This computing infrastructure is known as computational Grid or Grid Computing. Grid can be viewed as a distributed large-scale cluster computing. From other perspective, it constitutes the major part of Cloud Computing Systems in addition to thin clients and utility computing [1,2, 3]. Hence, Grid computing has attracted many researchers [4]. The interest in Grid computing has gone beyond the paradigm of traditional Grid computing to a Wireless Grid computing [5,6].
Connectivity Preserving Network Transformers
Venue: arXiv cs.DC 2015
Year: 2015

The Population Protocol model is a distributed model that concerns systems of very weak computational entities that cannot control the way they interact. The model of Network Constructors is a variant of Population Protocols capable of (algorithmically) constructing abstract networks. Both models are characterized by a fundamental inability to terminate. In this work, we investigate the minimal strengthenings of the latter that could overcome this inability. Our main conclusion is that initial connectivity of the communication topology combined with the ability of the protocol to transform the communication topology plus a few other local and realistic assumptions are sufficient to guarantee not only termination but also the maximum computational power that one can hope for in this family of models. The technique is to transform any initial connected topology to a less symmetric and detectable topology without ever breaking its connectivity during the transformation. The target topology of all of our transformers is the spanning line and we call Terminating Line Transformation the corresponding problem. We first study the case in which there is a pre-elected unique leader and give a time-optimal protocol for Terminating Line Transformation. We then prove that dropping the leader without additional assumptions leads to a strong impossibility result. In an attempt to overcome this, we equip the nodes with the ability to tell, during their pairwise interactions, whether they have at least one neighbor in common. Interestingly, it turns out that this local and realistic mechanism is sufficient to make the problem solvable. In particular, we give a very efficient protocol that solves Terminating Line Transformation when all nodes are initially identical. The latter implies that the model computes with termination any symmetric predicate computable by a Turing Machine of space $Θ(n^2)$.
Utility-Preserving Differentially Private Data Releases Via Individual Ranking Microaggregation
Venue: arXiv cs.CR 2015
Year: 2015

Being able to release and exploit open data gathered in information systems is crucial for researchers, enterprises and the overall society. Yet, these data must be anonymized before release to protect the privacy of the subjects to whom the records relate. Differential privacy is a privacy model for anonymization that offers more robust privacy guarantees than previous models, such as $k$-anonymity and its extensions. However, it is often disregarded that the utility of differentially private outputs is quite limited, either because of the amount of noise that needs to be added to obtain them or because utility is only preserved for a restricted type and/or a limited number of queries. On the contrary, $k$-anonymity-like data releases make no assumptions on the uses of the protected data and, thus, do not restrict the number and type of doable analyses. Recently, some authors have proposed mechanisms to offer general-purpose differentially private data releases. This paper extends such works with a specific focus on the preservation of the utility of the protected data. Our proposal builds on microaggregation-based anonymization, which is more flexible and utility-preserving than alternative anonymization methods used in the literature, in order to reduce the amount of noise needed to satisfy differential privacy. In this way, we improve the utility of differentially private data releases. Moreover, the noise reduction we achieve does not depend on the size of the data set, but just on the number of attributes to be protected, which is a more desirable behavior for large data sets. The utility benefits brought by our proposal are empirically evaluated and compared with related works for several data sets and metrics.
Predicting Online Protest Participation of Social Media Users
Venue: arXiv cs.SI 2015
Year: 2015

Social media has emerged to be a popular platform for people to express their viewpoints on political protests like the Arab Spring. Millions of people use social media to communicate and mobilize their viewpoints on protests. Hence, it is a valuable tool for organizing social movements. However, the mechanisms by which protest affects the population is not known, making it difficult to estimate the number of protestors. In this paper, we are inspired by sociological theories of protest participation and propose a framework to predict from the user's past status messages and interactions whether the next post of the user will be a declaration of protest. Drawing concepts from these theories, we model the interplay between the user's status messages and messages interacting with him over time and predict whether the next post of the user will be a declaration of protest. We evaluate the framework using data from the social media platform Twitter on protests during the recent Nigerian elections and demonstrate that it can effectively predict whether the next post of a user is a declaration of protest.
Gradient Descent Algorithm Inspired Adaptive Time Synchronization in Wireless Sensor Networks
Venue: arXiv cs.DC 2015
Year: 2015

Our motivation in this paper is to take another step forward from complex and heavyweight synchronization protocols to the easy-to-implement and lightweight synchronization protocols in WSNs. To this end, we present GraDeS, a novel multi-hop time synchronization protocol based upon gradient descent algorithm. We give details about our implementation of GraDeS and present its experimental evaluation in our testbed of MICAz sensor nodes. Our observations indicate that GraDeS is scalable, it has identical memory and processing overhead, better convergence time and comparable synchronization performance as compared to existing lightweight solutions.
Breaking the log n barrier on rumor spreading
Venue: arXiv cs.DS 2015
Year: 2015

$O(\log n)$ rounds has been a well known upper bound for rumor spreading using push&pull in the random phone call model (i.e., uniform gossip in the complete graph). A matching lower bound of $Ω(\log n)$ is also known for this special case. Under the assumption of this model and with a natural addition that nodes can call a partner once they learn its address (e.g., its IP address) we present a new distributed, address-oblivious and robust algorithm that uses push&pull with pointer jumping to spread a rumor to all nodes in only $O(\sqrt{\log n})$ rounds, w.h.p. This algorithm can also cope with $F= O(n/2^{\sqrt{\log n}})$ node failures, in which case all but $O(F)$ nodes become informed within $O(\sqrt{\log n})$ rounds, w.h.p.
3D Reconstruction of Crime Scenes and Design Considerations for an Interactive Investigation Tool
Venue: arXiv cs.CV 2015
Year: 2015

Crime Scene Investigation (CSI) is a carefully planned systematic process with the purpose of acquiring physical evidences to shed light upon the physical reality of the crime and eventually detect the identity of the criminal. Capturing images and videos of the crime scene is an important part of this process in order to conduct a deeper analysis on the digital evidence for possible hints. This work brings this idea further to use the acquired footage for generating a 3D model of the crime scene. Results show that realistic reconstructions can be obtained using sophisticated computer vision techniques. The paper also discusses a number of important design considerations describing key features that should be present in a powerful interactive CSI analysis tool.
Norm-Free Radon-Nikodym Approach to Machine Learning
Venue: arXiv cs.LG 2015
Year: 2015

For Machine Learning (ML) classification problem, where a vector of $\mathbf{x}$--observations (values of attributes) is mapped to a single $y$ value (class label), a generalized Radon--Nikodym type of solution is proposed. Quantum--mechanics --like probability states $ψ^2(\mathbf{x})$ are considered and "Cluster Centers", corresponding to the extremums of $<yψ^2(\mathbf{x})>/<ψ^2(\mathbf{x})>$, are found from generalized eigenvalues problem. The eigenvalues give possible $y^{[i]}$ outcomes and corresponding to them eigenvectors $ψ^{[i]}(\mathbf{x})$ define "Cluster Centers". The projection of a $ψ$ state, localized at given $\mathbf{x}$ to classify, on these eigenvectors define the probability of $y^{[i]}$ outcome, thus avoiding using a norm ($L^2$ or other types), required for "quality criteria" in a typical Machine Learning technique. A coverage of each `Cluster Center" is calculated, what potentially allows to separate system properties (described by $y^{[i]}$ outcomes) and system testing conditions (described by $C^{[i]}$ coverage). As an example of such application $y$ distribution estimator is proposed in a form of pairs $(y^{[i]},C^{[i]})$, that can be considered as Gauss quadratures generalization. This estimator allows to perform $y$ probability distribution estimation in a strongly non--Gaussian case.
Spectral Compressed Sensing via CANDECOMP/PARAFAC Decomposition of Incomplete Tensors
Venue: arXiv cs.NA 2015
Year: 2015

We consider the line spectral estimation problem which aims to recover a mixture of complex sinusoids from a small number of randomly observed time domain samples. Compressed sensing methods formulates line spectral estimation as a sparse signal recovery problem by discretizing the continuous frequency parameter space into a finite set of grid points. Discretization, however, inevitably incurs errors and leads to deteriorated estimation performance. In this paper, we propose a new method which leverages recent advances in tensor decomposition. Specifically, we organize the observed data into a structured tensor and cast line spectral estimation as a CANDECOMP/PARAFAC (CP) decomposition problem with missing entries. The uniqueness of the CP decomposition allows the frequency components to be super-resolved with infinite precision. Simulation results show that the proposed method provides a competitive estimate accuracy compared with existing state-of-the-art algorithms.
Joint Channel Training and Feedback for FDD Massive MIMO Systems
Venue: arXiv cs.IT 2015
Year: 2015

Massive multiple-input multiple-output (MIMO) is widely recognized as a promising technology for future 5G wireless communication systems. To achieve the theoretical performance gains in massive MIMO systems, accurate channel state information at the transmitter (CSIT) is crucial. Due to the overwhelming pilot signaling and channel feedback overhead, however, conventional downlink channel estimation and uplink channel feedback schemes might not be suitable for frequency-division duplexing (FDD) massive MIMO systems. In addition, these two topics are usually separately considered in the literature. In this paper, we propose a joint channel training and feedback scheme for FDD massive MIMO systems. Specifically, we firstly exploit the temporal correlation of time-varying channels to propose a differential channel training and feedback scheme, which simultaneously reduces the overhead for downlink training and uplink feedback. We next propose a structured compressive sampling matching pursuit (S-CoSaMP) algorithm to acquire a reliable CSIT by exploiting the structured sparsity of wireless MIMO channels. Simulation results demonstrate that the proposed scheme can achieve substantial reduction in the training and feedback overhead.
Adapting Caching to Audience Retention Rate: Which Video Chunk to Store?
Venue: arXiv cs.NI 2015
Year: 2015

Rarely do users watch online contents entirely. We study how to take this into account to improve the performance of cache systems for video-on-demand and video-sharing platforms in terms of traffic reduction on the core network. We exploit the notion of "Audience retention rate", introduced by mainstream online content platforms and measuring the popularity of different parts of the same video content. We first characterize the performance limits of a cache able to store parts of videos, when the popularity and the audience retention rate of each video are available to the cache manager. We then relax the assumption of known popularity and we propose a LRU (Least Recently Used) cache replacement policy that operates on the first chunks of each video. We characterize its performance by extending the well-known Che's approximation to this case. We prove that, by refining the chunk granularity, the chunk-LRU policy increases its performance. It is shown numerically that even for a small number of chunks (N=20), the gains of chunk-LRU are still significant in comparison to standard LRU policy that caches entire files, and they are almost optimal.
Distributed Methods for Computing Approximate Equilibria
Venue: arXiv cs.GT 2015
Year: 2015

We present a new, distributed method to compute approximate Nash equilibria in bimatrix games. In contrast to previous approaches that analyze the two payoff matrices at the same time (for example, by solving a single LP that combines the two players payoffs), our algorithm first solves two independent LPs, each of which is derived from one of the two payoff matrices, and then compute approximate Nash equilibria using only limited communication between the players. Our method has several applications for improved bounds for efficient computations of approximate Nash equilibria in bimatrix games. First, it yields a best polynomial-time algorithm for computing \emph{approximate well-supported Nash equilibria (WSNE)}, which guarantees to find a 0.6528-WSNE in polynomial time. Furthermore, since our algorithm solves the two LPs separately, it can be used to improve upon the best known algorithms in the limited communication setting: the algorithm can be implemented to obtain a randomized expected-polynomial-time algorithm that uses poly-logarithmic communication and finds a 0.6528-WSNE. The algorithm can also be carried out to beat the best known bound in the query complexity setting, requiring $O(n \log n)$ payoff queries to compute a 0.6528-WSNE. Finally, our approach can also be adapted to provide the best known communication efficient algorithm for computing \emph{approximate Nash equilibria}: it uses poly-logarithmic communication to find a 0.382-approximate Nash equilibrium.
Convolutional Monte Carlo Rollouts in Go
Venue: arXiv cs.LG 2015
Year: 2015

In this work, we present a MCTS-based Go-playing program which uses convolutional networks in all parts. Our method performs MCTS in batches, explores the Monte Carlo search tree using Thompson sampling and a convolutional network, and evaluates convnet-based rollouts on the GPU. We achieve strong win rates against open source Go programs and attain competitive results against state of the art convolutional net-based Go-playing programs.
Price discrimination for energy trading in smart grid: A game theoretic approach
Venue: arXiv cs.SY 2015
Year: 2015

Pricing schemes are an important smart grid feature to affect typical energy usage behavior of energy users (EUs). However, most existing schemes use the assumption that a buyer pays the same price per unit of energy to all suppliers at any particular time when energy is bought. By contrast, here a discriminate pricing technique using game theory is studied. A cake cutting game is investigated, in which participating EUs in a smart community decide on the price per unit of energy to charge a shared facility controller (SFC) in order to sell surplus energy. The focus is to study fairness criteria to maximize sum benefits to EUs and ensure an envy-free energy trading market. A benefit function is designed that leverages generation of discriminate pricing by each EU, according to the amount of surplus energy that an EU trades with the SFC and the EU's sensitivity to price. It is shown that the game possesses a socially optimal, and hence also Pareto optimal, solution. Further, an algorithm that can be implemented by each EU in a distributed manner to reach the optimal solution is proposed. Numerical case studies are given that demonstrate beneficial properties of the scheme.
Fast Generation of Spatially Embedded Random Networks
Venue: arXiv cs.DS 2015
Year: 2015

Spatially Embedded Random Networks such as the Waxman random graph have been used in a variety of settings for synthesizing networks. However, little thought has been put into fast generation of these networks. Existing techniques are $O(n^2)$ where $n$ is the number of nodes in the graph. In this paper we present an $O(n + e)$ algorithm, where $e$ is the number of edges.
A Survey of multimedia streaming in wireless sensor networks: progress, issues and design challenges
Venue: arXiv cs.NI 2015
Year: 2015

Advancements in Complementary Metal Oxide Semiconductor (CMOS) technology have enabled Wireless Sensor Networks (WSN) to gather, process and transport multimedia (MM) data as well and not just limited to handling ordinary scalar data anymore. This new generation of WSN type is called Wireless Multimedia Sensor Networks (WMSNs). Better and yet relatively cheaper sensors that are able to sense both scalar data and multimedia data with more advanced functionalities such as being able to handle rather intense computations easily have sprung up. In this paper, the applications, architectures, challenges and issues faced in the design of WMSNs are explored. Security and privacy issues, over all requirements, proposed and implemented solutions so far, some of the successful achievements and other related works in the field are also highlighted. Open research areas are pointed out and a few solution suggestions to the still persistent problems are made, which, to the best of my knowledge, so far have not been explored yet.
Impacts of structural factors on energy consumption in cluster-based wireless sensor networks: a comprehensive analysis
Venue: arXiv cs.NI 2015
Year: 2015

Limited energy is the major driving factor for research on wireless sensor networks. Clustering alleviates this energy shortage problem by reducing data traffic conveyed over the network and therefore several clustering methods are proposed in the literature. Researchers put forward their methods by making serious assumptions such as always locating single sink at one side of the topology or making clusters near to the sink with smaller sizes. However, to the best of our knowledge, there is no comprehensive research that investigates the effects of various structural alternatives on energy consumption of wireless sensor networks. In this paper, we thoroughly analyse the impact of various structural approaches such as cluster size, number of tiers in the topology, node density, position and number of sinks. Extensive simulation results are provided. The results show that the best performance about
A Practical Layered Model for Flexible-grid Optical Networks to Reduce the Routing Complexity
Venue: arXiv cs.NI 2015
Year: 2015

This article proposes a new layered model to represent the spectrum assignment on flexible-grid optical networks. This model can reduce the time-complexity of existing routing and spectrum assignment methods by providing a data structure that captures the current spectrum usage of the network links.
Flexibility of Networks: a new measure for network design space analysis?
Venue: arXiv cs.NI 2015
Year: 2015

Flexibility is often claimed as a competitive advantage when proposing new network designs. However, most proposals provide only qualitative arguments for their improved support of flexibility. Quantitative arguments vary a lot among different proposals. A general understanding for flexibility is not yet clearly defined, leaving it to the reader to draw the right conclusions based on background information. The term flexibility is commonly defined as the ability to adapt to changes. For networks, flexibility would refer to the ability to adapt the available network resources, such as flows or topology, to changes of design requirements, e.g., shorter latency budgets or different traffic distributions. Recent concepts such as Software Defined Networking, Network Virtualization and Network Function Virtualization have emerged claiming to provide more flexibility in networks. Nevertheless, a deeper understanding of what flexibility means and how it could be quantified to compare different network designs remains open. In this paper, we ask whether flexibility can be a new measure for network design space analysis. As it is quite challenging to formulate a flexibility measure that covers all network aspects, we propose an initial set of flexibility aspects to start grounding guidelines. Our initial selection is backed up by an analysis of Software Defined Networking, Network Virtualization and Network Function Virtualization for their support of the selected flexibility aspects. Our research methodology is based on a systematic approach that leads to network design guidelines with respect to flexibility.
A New Coordinated Beamformer for MIMO-based Ad Hoc Networks
Venue: arXiv cs.IT 2015
Year: 2015

The study proposes a new scheme for MIMO-based ad hoc networks. This is accomplished, while using the Interference Driving Technique (IDT) over Nakagami-m fading channels with perfect channel state information at both the transmitter and receiver. The use of this technique is proposed to decrease the impact of all the unwanted interferences, routinely caused by the overlap of the defined radio transmission ranges related to the used nodes. Indeed, IDT is utilized as a coordinated beamformer in a cooperative scheme, according to mean squared error criterion. The methodology and also analytical results are conducted to prove the aptitude of the paper.
Design and Optimal Configuration of Full-Duplex MAC Protocol for Cognitive Radio Networks Considering Self-Interference
Venue: arXiv cs.NI 2015
Year: 2015

In this paper, we propose an adaptive Medium Access Control (MAC) protocol for full-duplex (FD) cognitive radio networks in which FD secondary users (SUs) perform channel contention followed by concurrent spectrum sensing and transmission, and transmission only with maximum power in two different stages (called the FD sensing and transmission stages, respectively) in each contention and access cycle. The proposed FD cognitive MAC (FDC-MAC) protocol does not require synchronization among SUs and it efficiently utilizes the spectrum and mitigates the self-interference in the FD transceiver. We then develop a mathematical model to analyze the throughput performance of the FDC-MAC protocol where both half-duplex (HD) transmission (HDTx) and FD transmission (FDTx) modes are considered in the transmission stage. Then, we study the FDC-MAC configuration optimization through adaptively controlling the spectrum sensing duration and transmit power level in the FD sensing stage where we prove that there exists optimal sensing time and transmit power to achieve the maximum throughput and we develop an algorithm to configure the proposed FDC-MAC protocol. Extensive numerical results are presented to illustrate the characteristic of the optimal FDC-MAC configuration and the impacts of protocol parameters and the self-interference cancellation quality on the throughput performance. Moreover, we demonstrate the significant throughput gains of the FDC-MAC protocol with respect to existing half-duplex MAC (HD MAC) and single-stage FD MAC protocols.