OpenRaiser/Intern-Atlas huggingface dataset:
Auto-scaling Web Applications in Clouds: A Taxonomy and Survey
Venue: arXiv cs.DC 2017
Year: 2017

Web application providers have been migrating their applications to cloud data centers, attracted by the emerging cloud computing paradigm. One of the appealing features of the cloud is elasticity. It allows cloud users to acquire or release computing resources on-demand, which enables web application providers to automatically scale the resources provisioned to their applications without human intervention under a dynamic workload to minimize resource cost while satisfying Quality of Service (QoS) requirements. In this paper, we comprehensively analyze the challenges that remain in auto-scaling web applications in clouds and review the developments in this field. We present a taxonomy of auto-scalers according to the identified challenges and key properties. We analyze the surveyed works and map them to the taxonomy to identify the weaknesses in this field. Moreover, based on the analysis, we propose new future directions that can be explored in this area.
Unified Stochastic Geometry Modeling and Analysis of Cellular Networks in LOS/NLOS and Shadowed Fading
Venue: arXiv cs.IT 2017
Year: 2017

Statistical characterization of the signal-to-interference-plus-noise ratio (SINR) via its cumulative distribution function (CDF) is ubiquitous in a vast majority of technical contributions in the area of cellular networks since it boils down to averaging the Laplace transform of the aggregate interference, a benefit accorded at the expense of confinement to the simplistic Rayleigh fading. In this work, to capture diverse fading channels that appear in realistic outdoor/indoor wireless communication scenarios, we tackle the problem differently. By exploting the moment generating function (MGF) of the SINR, we succeed in analytically assessing cellular networks performance over the shadowed κ-μ, κ-μ and η-μ fading models. The latter offer high flexibility by capturing diverse fading channels including Rayleigh, Nakagami-m, Rician, and Rician shadow fading distributions. These channel models have been recently praised for their capability to accurately model dense urban environments, future femtocells and device-to-device (D2D) shadowed channels. In addition to unifying the analysis for different channel models, this work integrates, for the first time, the coverage, the achievable rate, and the bit error probability (BEP), which are largely treated separately in the literature. The developed model and analysis are validated over a broad range of simulation setups and parameters.
Evaluating Induced CCG Parsers on Grounded Semantic Parsing
Venue: arXiv cs.CL 2017
Year: 2017

We compare the effectiveness of four different syntactic CCG parsers for a semantic slot-filling task to explore how much syntactic supervision is required for downstream semantic analysis. This extrinsic, task-based evaluation provides a unique window to explore the strengths and weaknesses of semantics captured by unsupervised grammar induction systems. We release a new Freebase semantic parsing dataset called SPADES (Semantic PArsing of DEclarative Sentences) containing 93K cloze-style questions paired with answers. We evaluate all our models on this dataset. Our code and data are available at https://github.com/sivareddyg/graph-parser.
Covert Attacks in Cyber-Physical Control Systems
Venue: arXiv cs.CR 2017
Year: 2017

The advantages of using communication networks to interconnect controllers and physical plants motivate the increasing number of Networked Control Systems, in industrial and critical infrastructure facilities. However, this integration also exposes such control systems to new threats, typical of the cyber domain. In this context, studies have been conduced, aiming to explore vulnerabilities and propose security solutions for cyber-physical systems. In this paper, it is proposed a covert attack for service degradation, which is planned based on the intelligence gathered by another attack, herein proposed, referred as System Identification attack. The simulation results demonstrate that the joint operation of the two attacks is capable to affect, in a covert and accurate way, the physical behavior of a system.
Refinement types for precisely named cache locations
Venue: arXiv cs.PL 2017
Year: 2017

Many programming language techniques for incremental computation employ programmer-specified names for cached information. At runtime, each name identifies a "cache location" for a dynamic data value or a sub-computation; in sum, these cache location choices guide change propagation and incremental (re)execution. We call a cache location name precise when it identifies at most one value or subcomputation; we call all other names imprecise, or ambiguous. At a minimum, cache location names must be precise to ensure that change propagation works correctly; yet, reasoning statically about names in incremental programs remains an open problem. As a first step, this paper defines and solves the precise name problem, where we verify that incremental programs with explicit names use them precisely. To do so, we give a refinement type and effect system, and prove it sound (every well-typed program uses names precisely). We also demonstrate that this type system is expressive by verifying example programs that compute over efficient representations of incremental sequences and sets. Beyond verifying these programs, our type system also describes their dynamic naming strategies, e.g., for library documentation purposes.
Effective Capacity in MIMO Channels with Arbitrary Inputs
Venue: arXiv cs.IT 2017
Year: 2017

Recently, communication systems that are both spectrum and energy efficient have attracted significant attention. Different from the existing research, we investigate the throughput and energy efficiency of a general class of multiple-input and multiple-output systems with arbitrary inputs when they are subject to statistical quality-of-service (QoS) constraints, which are imposed as limits on the delay violation and buffer overflow probabilities. We employ the effective capacity as the performance metric. We obtain the optimal input covariance matrix that maximizes the effective capacity under a short-term average power constraint. Following that, we perform an asymptotic analysis of the effective capacity in the low signal-to-noise ratio and large-scale antenna regimes. In the low signal-to-noise ratio regime analysis, we utilize the first and second derivatives of the effective capacity when the signal-to-noise ratio approaches zero in order to determine the minimum energy-per-bit and also the slope of the effective capacity versus energy-per-bit curve at the minimum energy-per-bit. We observe that the minimum energy-per-bit is independent of the input distribution, whereas the slope depends on the input distribution. In the large-scale antenna analysis, we show that the effective capacity approaches the average transmission rate in the channel with the increasing number of transmit and/or receive antennas. Particularly, the gap between the effective capacity and the average transmission rate in the channel, which is caused by the QoS constraints, is minimized with the number of antennas. In addition, we put forward the non-asymptotic backlog and delay violation bounds by utilizing the effective capacity. Finally, we substantiate our analytical results through numerical illustrations.
On the Preciseness of Subtyping in Session Types
Venue: arXiv cs.LO 2017
Year: 2017

Subtyping in concurrency has been extensively studied since early 1990s as one of the most interesting issues in type theory. The correctness of subtyping relations has been usually provided as the soundness for type safety. The converse direction, the completeness, has been largely ignored in spite of its usefulness to define the largest subtyping relation ensuring type safety. This paper formalises preciseness (i.e. both soundness and completeness) of subtyping for mobile processes and studies it for the synchronous and the asynchronous session calculi. We first prove that the well-known session subtyping, the branching-selection subtyping, is sound and complete for the synchronous calculus. Next we show that in the asynchronous calculus, this subtyping is incomplete for type-safety: that is, there exist session types T and S such that T can safely be considered as a subtype of S, but T < S is not derivable by the subtyping. We then propose an asynchronous subtyping system which is sound and complete for the asynchronous calculus. The method gives a general guidance to design rigorous channel-based subtypings respecting desired safety properties. Both the synchronous and the asynchronous calculus are first considered with lin ear channels only, and then they are extended with session initialisations and c ommunications of expressions (including shared channels).
Covert Communications on Renewal Packet Channels
Venue: arXiv cs.IT 2017
Year: 2017

Security and privacy are major concerns in modern communication networks. In recent years, the information theory of covert communications, where the very presence of the communication is undetectable to a watchful and determined adversary, has been of great interest. This emerging body of work has focused on additive white Gaussian noise (AWGN), discrete memoryless channels (DMCs), and optical channels. In contrast, our recent work introduced the information-theoretic limits for covert communications over packet channels whose packet timings are governed by a Poisson point process. However, actual network packet arrival times do not generally conform to the Poisson process assumption, and thus here we consider the extension of our work to timing channels characterized by more general renewal processes of rate $λ$. We consider two scenarios. In the first scenario, the source of the packets on the channel cannot be authenticated by Willie, and therefore Alice can insert packets into the channel. We show that if the total number of transmitted packets by Jack is $N$, Alice can covertly insert $\mathcal{O}\left(\sqrt{N}\right)$ packets and, if she transmits more, she will be detected by Willie. In the second scenario, packets are authenticated by Willie but we assume that Alice and Bob share a secret key; hence, Alice alters the timings of the packets according to a pre-shared codebook with Bob to send information to him over a $G/M/1$ queue with service rate $μ>λ$. We show that Alice can covertly and reliably transmit $\mathcal{O}(N)$ bits to Bob when the total number of packets sent from Jack to Steve is $N$.
Covert Single-hop Communication in a Wireless Network with Distributed Artificial Noise Generation
Venue: arXiv cs.IT 2017
Year: 2017

Covert communication, also known as low probability of detection (LPD) communication, prevents the adversary from knowing that a communication is taking place. Recent work has demonstrated that, in a three-party scenario with a transmitter (Alice), intended recipient (Bob), and adversary (Warden Willie), the maximum number of bits that can be transmitted reliably from Alice to Bob without detection by Willie, when additive white Gaussian noise (AWGN) channels exist between all parties, is on the order of the square root of the number of channel uses. In this paper, we begin consideration of network scenarios by studying the case where there are additional "friendly" nodes present in the environment that can produce artificial noise to aid in hiding the communication. We establish achievability results by considering constructions where the system node closest to the warden produces artificial noise and demonstrate a significant improvement in the throughput achieved covertly, without requiring close coordination between Alice and the noise-generating node. Conversely, under mild restrictions on the communication strategy, we demonstrate no higher covert throughput is possible. Extensions to the consideration of the achievable covert throughput when multiple wardens randomly located in the environment collaborate to attempt detection of the transmitter are also considered.
Learning to Translate in Real-time with Neural Machine Translation
Venue: arXiv cs.CL 2017
Year: 2017

Translating in real-time, a.k.a. simultaneous translation, outputs translation words before the input sentence ends, which is a challenging problem for conventional machine translation methods. We propose a neural machine translation (NMT) framework for simultaneous translation in which an agent learns to make decisions on when to translate from the interaction with a pre-trained NMT environment. To trade off quality and delay, we extensively explore various targets for delay and design a method for beam-search applicable in the simultaneous MT setting. Experiments against state-of-the-art baselines on two language pairs demonstrate the efficacy of the proposed framework both quantitatively and qualitatively.
On the Weighted Quartet Consensus problem
Venue: arXiv cs.DS 2017
Year: 2017

In phylogenetics, the consensus problem consists in summarizing a set of phylogenetic trees that all classify the same set of species into a single tree. Several definitions of consensus exist in the literature; in this paper we focus on the Weighted Quartet Consensus problem, a problem with unknown complexity status so far. Here we prove that the Weighted Quartet Consensus problem is NP-hard and we give a 1/2-factor approximation for this problem. During the process, we propose a derandomization procedure of a previously known randomized 1/3-factor approximation. We also investigate the fixed-parameter tractability of this problem.
Game of Power Allocation on Networks
Venue: arXiv cs.SI 2017
Year: 2017

This paper develops a distributed resource allocation game to study countries' pursuit of targets such as self-survival in the networked international environment. The contributions are two. First, the game formalizes countries' power allocation behaviors which fall into the broad category of humans resource allocation behaviors. Second, the game presents a new technical problem, and establishes pure strategy Nash equilibrium existence.
On colouring point visibility graphs
Venue: arXiv cs.CG 2017
Year: 2017

In this paper we show that it can be decided in polynomial time whether or not the visibility graph of a given point set is 4-colourable, and such a 4-colouring, if it exists, can also be constructed in polynomial time. We show that the problem of deciding whether the visibility graph of a point set is 5-colourable, is NP-complete. We give an example of a point visibility graph that has chromatic number 6 while its clique number is only 4.
Hybrid Spectrum Sharing in mmWave Cellular Networks
Venue: arXiv cs.NI 2017
Year: 2017

While spectrum at millimeter wave (mmWave) frequencies is less scarce than at traditional frequencies below 6 GHz, still it is not unlimited, in particular if we consider the requirements from other services using the same band and the need to license mmWave bands to multiple mobile operators. Therefore, an efficient spectrum access scheme is critical to harvest the maximum benefit from emerging mmWave technologies. In this paper, we introduce a new hybrid spectrum access scheme for mmWave networks, where data is aggregated through two mmWave carriers with different characteristics. In particular, we consider the case of a hybrid spectrum scheme between a mmWave band with exclusive access and a mmWave band where spectrum is pooled between multiple operators. To the best of our knowledge, this is the first study proposing hybrid spectrum access for mmWave networks and providing a quantitative assessment of its benefits. Our results show that this approach provides major advantages with respect to traditional fully licensed or fully unlicensed spectrum access schemes, though further work is needed to achieve a more complete understanding of both technical and non technical implications.
The Gray image of constacyclic codes over the finite chain ring $F_{p^m}[u]/\langle u^k\rangle$
Venue: arXiv cs.IT 2017
Year: 2017

Let $\mathbb{F}_{p^m}$ be a finite field of cardinality $p^m$, where $p$ is a prime, and $k, N$ be any positive integers. We denote $R_k=F_{p^m}[u]/\langle u^k\rangle =F_{p^m}+uF_{p^m}+\ldots+u^{k-1}F_{p^m}$ ($u^k=0$) and $λ=a_0+a_1u+\ldots+a_{k-1}u^{k-1}$ where $a_0, a_1,\ldots, a_{k-1}\in F_{p^m}$ satisfying $a_0\neq 0$ and $a_1=1$. Let $r$ be a positive integer satisfying $p^{r-1}+1\leq k\leq p^r$. We defined a Gray map from $R_k$ to $F_{p^m}^{p^r}$ first, then prove that the Gray image of any linear $λ$-constacyclic code over $R_k$ of length $N$ is a distance invariant linear $a_0^{p^r}$-constacyclic code over $F_{p^m}$ of length $p^rN$. Furthermore, the generator polynomials for each linear $λ$-constacyclic code over $R_k$ of length $N$ and its Gray image are given respectively. Finally, some optimal constacyclic codes over $F_{3}$ and $F_{5}$ are constructed.
The Static Center of Pressure Sensitivity: a further Criterion to assess Contact Stability and Balancing Controllers
Venue: arXiv cs.RO 2017
Year: 2017

Legged locomotion has received increasing attention from the robotics community. In this respect, contact stability plays a critical role in ensuring that robots maintain balance, and it is a key element for balancing and walking controllers. The Center of Pressure is a contact stability criterion that defines a point that must be kept strictly inside the support polygon in order to ensure postural stability. In this paper, we introduce the concept of the sensitivity of the static center of pressure: roughly speaking, the rate of change of the center of pressure with respect to the system equilibrium configurations. This new concept can be used as an additional criterion to assess the robustness of the contact stability. We show how the sensitivity of the center of pressure can also be used as a metric to assess balancing controllers by considering two state-of-the-art control strategies. The analytical analysis is performed on a simplified model, and validated during balancing tasks on the iCub humanoid robot.
Template shape estimation: correcting an asymptotic bias
Venue: arXiv cs.CV 2017
Year: 2017

We use tools from geometric statistics to analyze the usual estimation procedure of a template shape. This applies to shapes from landmarks, curves, surfaces, images etc. We demonstrate the asymptotic bias of the template shape estimation using the stratified geometry of the shape space. We give a Taylor expansion of the bias with respect to a parameter $σ$ describing the measurement error on the data. We propose two bootstrap procedures that quantify the bias and correct it, if needed. They are applicable for any type of shape data. We give a rule of thumb to provide intuition on whether the bias has to be corrected. This exhibits the parameters that control the bias' magnitude. We illustrate our results on simulated and real shape data.
Efficient Best-Response Computation for Strategic Network Formation under Attack
Venue: arXiv cs.GT 2017
Year: 2017

Inspired by real world examples, e.g. the Internet, researchers have introduced an abundance of strategic games to study natural phenomena in networks. Unfortunately, almost all of these games have the conceptual drawback of being computationally intractable, i.e. computing a best response strategy or checking if an equilibrium is reached is NP-hard. Thus, a main challenge in the field is to find tractable realistic network formation models. We address this challenge by investigating a very recently introduced model by Goyal et al. [WINE'16] which focuses on robust networks in the presence of a strong adversary who attacks (and kills) nodes in the network and lets this attack spread virus-like to neighboring nodes and their neighbors. Our main result is to establish that this natural model is one of the few exceptions which are both realistic and computationally tractable. In particular, we answer an open question of Goyal et al. by providing an efficient algorithm for computing a best response strategy, which implies that deciding whether the game has reached a Nash equilibrium can be done efficiently as well. Our algorithm essentially solves the problem of computing a minimal connection to a network which maximizes the reachability while hedging against severe attacks on the network infrastructure and may thus be of independent interest.
Stochastic Games for Smart Grid Energy Management with Prospect Prosumers
Venue: arXiv cs.GT 2017
Year: 2017

In this paper, the problem of smart grid energy management under stochastic dynamics is investigated. In the considered model, at the demand side, it is assumed that customers can act as prosumers who own renewable energy sources and can both produce and consume energy. Due to the coupling between the prosumers' decisions and the stochastic nature of renewable energy, the interaction among prosumers is formulated as a stochastic game, in which each prosumer seeks to maximize its payoff, in terms of revenues, by controlling its energy consumption and demand. In particular, the subjective behavior of prosumers is explicitly reflected into their payoff functions using prospect theory, a powerful framework that allows modeling real-life human choices. For this prospect-based stochastic game, it is shown that there always exists a stationary Nash equilibrium where the prosumers' trading policies in the equilibrium are independent of the time and their histories of the play. Moreover, a novel distributed algorithm with no information sharing among prosumers is proposed and shown to converge to an $ε$-Nash equilibrium. On the other hand, at the supply side, the interaction between the utility company and the prosumers is formulated as an online optimization problem in which the utility company's goal is to learn its optimal energy allocation rules. For this case, it is shown that such an optimization problem admits a no-regret algorithm meaning that regardless of the actual outcome of the game among the prosumers, the utility company can follow a strategy that mitigates its allocation costs as if it knew the entire demand market a priori. Simulation results show the convergence of the proposed algorithms to their predicted outcomes and present new insights resulting from prospect theory that contribute toward more efficient energy management in the smart grids.
Gibbsian On-Line Distributed Content Caching Strategy for Cellular Networks
Venue: arXiv cs.NI 2017
Year: 2017

We develop Gibbs sampling based techniques for learning the optimal content placement in a cellular network. A collection of base stations are scattered on the space, each having a cell (possibly overlapping with other cells). Mobile users request for downloads from a finite set of contents according to some popularity distribution. Each base station can store only a strict subset of the contents at a time; if a requested content is not available at any serving base station, it has to be downloaded from the backhaul. Thus, there arises the problem of optimal content placement which can minimize the download rate from the backhaul, or equivalently maximize the cache hit rate. Using similar ideas as Gibbs sampling, we propose simple sequential content update rules that decide whether to store a content at a base station based on the knowledge of contents in neighbouring base stations. The update rule is shown to be asymptotically converging to the optimal content placement for all nodes. Next, we extend the algorithm to address the situation where content popularities and cell topology are initially unknown, but are estimated as new requests arrive to the base stations. Finally, improvement in cache hit rate is demonstrated numerically.