OpenRaiser/Intern-Atlas huggingface dataset:
A Holistic Approach to Log Data Analysis in High-Performance Computing Systems: The Case of IBM Blue Gene/Q
Venue: arXiv cs.DC 2015
Year: 2015

The complexity and cost of managing high-performance computing infrastructures are on the rise. Automating management and repair through predictive models to minimize human interventions is an attempt to increase system availability and contain these costs. Building predictive models that are accurate enough to be useful in automatic management cannot be based on restricted log data from subsystems but requires a holistic approach to data analysis from disparate sources. Here we provide a detailed multi-scale characterization study based on four datasets reporting power consumption, temperature, workload, and hardware/software events for an IBM Blue Gene/Q installation. We show that the system runs a rich parallel workload, with low correlation among its components in terms of temperature and power, but higher correlation in terms of events. As expected, power and temperature correlate strongly, while events display negative correlations with load and power. Power and workload show moderate correlations, and only at the scale of components. The aim of the study is a systematic, integrated characterization of the computing infrastructure and discovery of correlation sources and levels to serve as basis for future predictive modeling efforts.
Learning to Execute
Venue: arXiv cs.NE 2015
Year: 2015

Recurrent Neural Networks (RNNs) with Long Short-Term Memory units (LSTM) are widely used because they are expressive and are easy to train. Our interest lies in empirically evaluating the expressiveness and the learnability of LSTMs in the sequence-to-sequence regime by training them to evaluate short computer programs, a domain that has traditionally been seen as too complex for neural networks. We consider a simple class of programs that can be evaluated with a single left-to-right pass using constant memory. Our main result is that LSTMs can learn to map the character-level representations of such programs to their correct outputs. Notably, it was necessary to use curriculum learning, and while conventional curriculum learning proved ineffective, we developed a new variant of curriculum learning that improved our networks' performance in all experimental conditions. The improved curriculum had a dramatic impact on an addition problem, making it possible to train an LSTM to add two 9-digit numbers with 99% accuracy.
On the complexity of Linearizability
Venue: arXiv cs.LO 2015
Year: 2015

It was shown in Alur et al. [1] that the problem of verifying finite concurrent systems through Linearizability is in EXPSPACE. However, there was still a complexity gap between the easy to obtain PSPACE lower bound and the EXPSPACE upper bound. We show in this paper that Linearizability is EXPSPACE-complete.
Quantifying performance bottlenecks of stencil computations using the Execution-Cache-Memory model
Venue: arXiv cs.PF 2015
Year: 2015

Stencil algorithms on regular lattices appear in many fields of computational science, and much effort has been put into optimized implementations. Such activities are usually not guided by performance models that provide estimates of expected speedup. Understanding the performance properties and bottlenecks by performance modeling enables a clear view on promising optimization opportunities. In this work we refine the recently developed Execution-Cache-Memory (ECM) model and use it to quantify the performance bottlenecks of stencil algorithms on a contemporary Intel processor. This includes applying the model to arrive at single-core performance and scalability predictions for typical corner case stencil loop kernels. Guided by the ECM model we accurately quantify the significance of "layer conditions," which are required to estimate the data traffic through the memory hierarchy, and study the impact of typical optimization approaches such as spatial blocking, strength reduction, and temporal blocking for their expected benefits. We also compare the ECM model to the widely known Roofline model.
Abstraction Refinement for Trace Inclusion of Infinite State Systems
Venue: arXiv cs.LO 2015
Year: 2015

A \emph{data automaton} is a finite automaton equipped with variables (counters or registers) ranging over infinite data domains. A trace of a data automaton is an alternating sequence of alphabet symbols and values taken by the counters during an execution of the automaton. The problem addressed in this paper is the inclusion between the sets of traces (data languages) recognized by such automata. Since the problem is undecidable in general, we give a semi-algorithm based on abstraction refinement, which is proved to be sound and complete, but whose termination is not guaranteed. We have implemented our technique in a~prototype tool and show promising results on several non-trivial examples.
Updating and downdating techniques for optimizing network communicability
Venue: arXiv cs.SI 2015
Year: 2015

The total communicability of a network (or graph) is defined as the sum of the entries in the exponential of the adjacency matrix of the network, possibly normalized by the number of nodes. This quantity offers a good measure of how easily information spreads across the network, and can be useful in the design of networks having certain desirable properties. The total communicability can be computed quickly even for large networks using techniques based on the Lanczos algorithm. In this work we introduce some heuristics that can be used to add, delete, or rewire a limited number of edges in a given sparse network so that the modified network has a large total communicability. To this end, we introduce new edge centrality measures which can be used to guide in the selection of edges to be added or removed. Moreover, we show experimentally that the total communicability provides an effective and easily computable measure of how "well-connected" a sparse network is.
Poisson Group Testing: A Probabilistic Model for Boolean Compressed Sensing
Venue: arXiv cs.IT 2015
Year: 2015

We introduce a novel probabilistic group testing framework, termed Poisson group testing, in which the number of defectives follows a right-truncated Poisson distribution. The Poisson model has a number of new applications, including dynamic testing with diminishing relative rates of defectives. We consider both nonadaptive and semi-adaptive identification methods. For nonadaptive methods, we derive a lower bound on the number of tests required to identify the defectives with a probability of error that asymptotically converges to zero; in addition, we propose test matrix constructions for which the number of tests closely matches the lower bound. For semi-adaptive methods, we describe a lower bound on the expected number of tests required to identify the defectives with zero error probability. In addition, we propose a stage-wise reconstruction algorithm for which the expected number of tests is only a constant factor away from the lower bound. The methods rely only on an estimate of the average number of defectives, rather than on the individual probabilities of subjects being defective.
Minimization Problems Based on Relative $α$-Entropy II: Reverse Projection
Venue: arXiv cs.IT 2015
Year: 2015

In part I of this two-part work, certain minimization problems based on a parametric family of relative entropies (denoted $\mathscr{I}_α$) were studied. Such minimizers were called forward $\mathscr{I}_α$-projections. Here, a complementary class of minimization problems leading to the so-called reverse $\mathscr{I}_α$-projections are studied. Reverse $\mathscr{I}_α$-projections, particularly on log-convex or power-law families, are of interest in robust estimation problems ($α>1$) and in constrained compression settings ($α<1$). Orthogonality of the power-law family with an associated linear family is first established and is then exploited to turn a reverse $\mathscr{I}_α$-projection into a forward $\mathscr{I}_α$-projection. The transformed problem is a simpler quasiconvex minimization subject to linear constraints.
Cryptographic Enforcement of Information Flow Policies without Public Information
Venue: arXiv cs.CR 2015
Year: 2015

Cryptographic access control has been studied for over 30 years and is now a mature research topic. When symmetric cryptographic primitives are used, each protected resource is encrypted and only authorized users should have access to the encryption key. By treating the keys themselves as protected resources, it is possible to develop schemes in which authorized keys are derived from the keys explicitly assigned to the user's possession and publicly available information. It has been generally assumed that each user would be assigned a single key from which all other authorized keys would be derived. Recent work has challenged this assumption by developing schemes that do not require public information, the trade-off being that a user may require more than one key. However, these new schemes, which require a chain partition of the partially ordered set on which the access control policy is based, have some disadvantages. In this paper we define the notion of a tree-based cryptographic enforcement scheme, which, like chain-based schemes, requires no public information. We establish that the strong security properties of chain-based schemes are preserved by tree-based schemes, and provide an efficient construction for deriving a tree-based enforcement scheme from a given policy that minimizes the number of keys required.
Simple PTAS's for families of graphs excluding a minor
Venue: arXiv cs.DS 2015
Year: 2015

We show that very simple algorithms based on local search are polynomial-time approximation schemes for Maximum Independent Set, Minimum Vertex Cover and Minimum Dominating Set, when the input graphs have a fixed forbidden minor.
Log-Optimal Portfolio Selection Using the Blackwell Approachability Theorem
Venue: arXiv cs.AI 2015
Year: 2015

We present a method for constructing the log-optimal portfolio using the well-calibrated forecasts of market values. Dawid's notion of calibration and the Blackwell approachability theorem are used for computing well-calibrated forecasts. We select a portfolio using this "artificial" probability distribution of market values. Our portfolio performs asymptotically at least as well as any stationary portfolio that redistributes the investment at each round using a continuous function of side information. Unlike in classical mathematical finance theory, no stochastic assumptions are made about market values.
Partial Optimality by Pruning for MAP-Inference with General Graphical Models
Venue: arXiv cs.AI 2015
Year: 2015

We consider the energy minimization problem for undirected graphical models, also known as MAP-inference problem for Markov random fields which is NP-hard in general. We propose a novel polynomial time algorithm to obtain a part of its optimal non-relaxed integral solution. Our algorithm is initialized with variables taking integral values in the solution of a convex relaxation of the MAP-inference problem and iteratively prunes those, which do not satisfy our criterion for partial optimality. We show that our pruning strategy is in a certain sense theoretically optimal. Also empirically our method outperforms previous approaches in terms of the number of persistently labelled variables. The method is very general, as it is applicable to models with arbitrary factors of an arbitrary order and can employ any solver for the considered relaxed problem. Our method's runtime is determined by the runtime of the convex relaxation solver for the MAP-inference problem.
Differentially- and non-differentially-private random decision trees
Venue: arXiv cs.LG 2015
Year: 2015

We consider supervised learning with random decision trees, where the tree construction is completely random. The method is popularly used and works well in practice despite the simplicity of the setting, but its statistical mechanism is not yet well-understood. In this paper we provide strong theoretical guarantees regarding learning with random decision trees. We analyze and compare three different variants of the algorithm that have minimal memory requirements: majority voting, threshold averaging and probabilistic averaging. The random structure of the tree enables us to adapt these methods to a differentially-private setting thus we also propose differentially-private versions of all three schemes. We give upper-bounds on the generalization error and mathematically explain how the accuracy depends on the number of random decision trees. Furthermore, we prove that only logarithmic (in the size of the dataset) number of independently selected random decision trees suffice to correctly classify most of the data, even when differential-privacy guarantees must be maintained. We empirically show that majority voting and threshold averaging give the best accuracy, also for conservative users requiring high privacy guarantees. Furthermore, we demonstrate that a simple majority voting rule is an especially good candidate for the differentially-private classifier since it is much less sensitive to the choice of forest parameters than other methods.
Distributed Adaptive Consensus Protocols for Linear Multi-agent Systems with Directed Graphs and External Disturbances
Venue: arXiv cs.SY 2015
Year: 2015

This paper addresses the distributed consensus design problem for linear multi-agent systems with directed communication graphs and external disturbances. Both the cases with strongly connected communication graphs and leader-follower graphs containing a directed spanning tree with the leader as the root are discussed. Distributed adaptive consensus protocols based on the relative states of neighboring agents are designed, which can ensure the ultimate boundedness of the consensus error and adaptive gains in the presence of external disturbances. The upper bounds of the consensus error are further explicitly given. Compared to the existing consensus protocols, the merit of the adaptive protocols proposed in this paper is that they can be computed and implemented in a fully distributed fashion and meanwhile are robust with respect to external disturbances.
Optimal Online Edge Coloring of Planar Graphs with Advice
Venue: arXiv cs.DS 2015
Year: 2015

Using the framework of advice complexity, we study the amount of knowledge about the future that an online algorithm needs to color the edges of a graph optimally, i.e., using as few colors as possible. For graphs of maximum degree $Δ$, it follows from Vizing's Theorem that $O(m\log Δ)$ bits of advice suffice to achieve optimality, where $m$ is the number of edges. We show that for graphs of bounded degeneracy (a class of graphs including e.g. trees and planar graphs), only $O(m)$ bits of advice are needed to compute an optimal solution online, independently of how large $Δ$ is. On the other hand, we show that $Ω(m)$ bits of advice are necessary just to achieve a competitive ratio better than that of the best deterministic online algorithm without advice. Furthermore, we consider algorithms which use a fixed number of advice bits per edge (our algorithm for graphs of bounded degeneracy belongs to this class of algorithms). We show that for bipartite graphs, any such algorithm must use at least $Ω(m\log Δ)$ bits of advice to achieve optimality.
Insights from Nature for Cybersecurity
Venue: arXiv cs.CR 2015
Year: 2015

The alarming rise in the quantity of malware in the last few years poses a serious challenge to the security community and requires urgent response. However, current countermeasures seem to be no longer effective. Thus, it is our belief that it is now time for researchers and security experts to turn to nature in the search for novel inspirations for defense systems. Nature has provided species with a whole range of offensive and defensive techniques, which have been developing and improving in the course of billions of years of evolution. The extremely diverse living conditions have promoted a large variation in the devised bio-security solutions. In this paper we introduce a novel PROTECTION framework in which common denominators of the encountered offensive and defensive means are proposed and presented. The bio-inspired solutions are discussed in the context of cybersecurity, where some principles have already been adopted. The deployment of the whole nature-based framework should aid the design and improvement process of modern cyber-defense systems.
Binary Polarization Kernels from Code Decompositions
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, code decompositions (a.k.a. code nestings) are used to design binary polarization kernels. The proposed kernels are in general non-linear. They provide a better polarization exponent than the previously known kernels of the same dimensions. In particular, non-linear kernels of dimensions 14, 15, and 16 are constructed and are shown to have optimal asymptotic error-correction performance. The optimality is proved by showing that the exponents of these kernels achieve a new upper bound that is developed in this paper.
Coding scheme for 3D vertical flash memory
Venue: arXiv cs.IT 2015
Year: 2015

Recently introduced 3D vertical flash memory is expected to be a disruptive technology since it overcomes scaling challenges of conventional 2D planar flash memory by stacking up cells in the vertical direction. However, 3D vertical flash memory suffers from a new problem known as fast detrapping, which is a rapid charge loss problem. In this paper, we propose a scheme to compensate the effect of fast detrapping by intentional inter-cell interference (ICI). In order to properly control the intentional ICI, our scheme relies on a coding technique that incorporates the side information of fast detrapping during the encoding stage. This technique is closely connected to the well-known problem of coding in a memory with defective cells. Numerical results show that the proposed scheme can effectively address the problem of fast detrapping.
Integer Forcing-and-Forward Transceiver Design for MIMO Multi-Pair Two-Way Relaying
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we propose a new transmission scheme, named as Integer Forcing-and-Forward (IFF), for communications among multi-pair multiple-antenna users in which each pair exchanges their messages with the help of a single multi antennas relay in the multiple-access and broadcast phases. The proposed scheme utilizes Integer Forcing Linear Receiver (IFLR) at relay, which uses equations, i.e., linear integer-combinations of messages, to harness the intra-pair interference. Accordingly, we propose the design of mean squared error (MSE) based transceiver, including precoder and projection matrices for the relay and users, assuming that the perfect channel state information (CSI) is available. In this regards, in the multiple-access phase, we introduce two new MSE criteria for the related precoding and filter designs, i.e., the sum of the equations MSE (Sum-Equation MSE) and the maximum of the equations MSE (Max-Equation MSE), to exploit the equations in the relay. In addition, the convergence of the proposed criteria is proven as well. Moreover, in the broadcast phase, we use the two traditional MSE criteria, i.e. the sum of the users' mean squred errors (Sum MSE) and the maximum of the users' mean squared errors (Max MSE), to design the related precoding and filters for recovering relay's equations by the users. Then, we consider a more practical scenario with imperfect CSI. For this case, IFLR receiver is modified, and another transceiver design is proposed, which take into account the effect of channels estimation error. We evaluate the performance of our proposed strategy and compare the results with the conventional amplify-and-forward (AF) and denoise-and-forward (DF) strategies for the same scenario. The results indicate the substantial superiority of the proposed strategy in terms of the outage probability and the sum rate.
High Dynamic Range Imaging by Perceptual Logarithmic Exposure Merging
Venue: arXiv cs.CV 2015
Year: 2015

In this paper we emphasize a similarity between the Logarithmic-Type Image Processing (LTIP) model and the Naka-Rushton model of the Human Visual System (HVS). LTIP is a derivation of the Logarithmic Image Processing (LIP), which further replaces the logarithmic function with a ratio of polynomial functions. Based on this similarity, we show that it is possible to present an unifying framework for the High Dynamic Range (HDR) imaging problem, namely that performing exposure merging under the LTIP model is equivalent to standard irradiance map fusion. The resulting HDR algorithm is shown to provide high quality in both subjective and objective evaluations.
Upper Bound on the Capacity of Discrete-Time Wiener Phase Noise Channels
Venue: arXiv cs.IT 2015
Year: 2015

A discrete-time Wiener phase noise channel with an integrate-and-dump multi-sample receiver is studied. An upper bound to the capacity with an average input power constraint is derived, and a high signal-to-noise ratio (SNR) analysis is performed. If the oversampling factor grows as $\text{SNR}^α$ for $0\le α\le 1$, then the capacity pre-log is at most $(1+α)/2$ at high SNR.
Subset-Universal Lossy Compression
Venue: arXiv cs.IT 2015
Year: 2015

A lossy source code $\mathcal{C}$ with rate $R$ for a discrete memoryless source $S$ is called subset-universal if for every $0<R'< R$, almost every subset of $2^{nR'}$ of its codewords achieves average distortion close to the source's distortion-rate function $D(R')$. In this paper we prove the asymptotic existence of such codes. Moreover, we show the asymptotic existence of a code that is subset-universal with respect to all sources with the same alphabet.
Bounds for complexity of syndrome decoding for poset metrics
Venue: arXiv cs.IT 2015
Year: 2015

In this work we show how to decompose a linear code relatively to any given poset metric. We prove that the complexity of syndrome decoding is determined by a maximal (primary) such decomposition and then show that a refinement of a partial order leads to a refinement of the primary decomposition. Using this and considering already known results about hierarchical posets, we can establish upper and lower bounds for the complexity of syndrome decoding relatively to a poset metric.
Permission-Based Separation Logic for Multithreaded Java Programs
Venue: arXiv cs.LO 2015
Year: 2015

This paper presents a program logic for reasoning about multithreaded Java-like programs with dynamic thread creation, thread joining and reentrant object monitors. The logic is based on concurrent separation logic. It is the first detailed adaptation of concurrent separation logic to a multithreaded Java-like language. The program logic associates a unique static access permission with each heap location, ensuring exclusive write accesses and ruling out data races. Concurrent reads are supported through fractional permissions. Permissions can be transferred between threads upon thread starting, thread joining, initial monitor entrancies and final monitor exits. In order to distinguish between initial monitor entrancies and monitor reentrancies, auxiliary variables keep track of multisets of currently held monitors. Data abstraction and behavioral subtyping are facilitated through abstract predicates, which are also used to represent monitor invariants, preconditions for thread starting and postconditions for thread joining. Value-parametrized types allow to conveniently capture common strong global invariants, like static object ownership relations. The program logic is presented for a model language with Java-like classes and interfaces, the soundness of the program logic is proven, and a number of illustrative examples are presented.