OpenRaiser/Intern-Atlas huggingface dataset:
Analyzing the Performance of Lock-Free Data Structures: A Conflict-based Model
Venue: arXiv cs.DS 2015
Year: 2015

This paper considers the modeling and the analysis of the performance of lock-free concurrent data structures. Lock-free designs employ an optimistic conflict control mechanism, allowing several processes to access the shared data object at the same time. They guarantee that at least one concurrent operation finishes in a finite number of its own steps regardless of the state of the operations. Our analysis considers such lock-free data structures that can be represented as linear combinations of fixed size retry loops. Our main contribution is a new way of modeling and analyzing a general class of lock-free algorithms, achieving predictions of throughput that are close to what we observe in practice. We emphasize two kinds of conflicts that shape the performance: (i) hardware conflicts, due to concurrent calls to atomic primitives; (ii) logical conflicts, caused by simultaneous operations on the shared data structure. We show how to deal with these hardware and logical conflicts separately, and how to combine them, so as to calculate the throughput of lock-free algorithms. We propose also a common framework that enables a fair comparison between lock-free implementations by covering the whole contention domain, together with a better understanding of the performance impacting factors. This part of our analysis comes with a method for calculating a good back-off strategy to finely tune the performance of a lock-free algorithm. Our experimental results, based on a set of widely used concurrent data structures and on abstract lock-free designs, show that our analysis follows closely the actual code behavior.
The complexity of cyber attacks in a new layered-security model and the maximum-weight, rooted-subtree problem
Venue: arXiv cs.DS 2015
Year: 2015

In our cyber security model we define the concept of {\em penetration cost}, which is the cost that must be paid in order to break into the next layer of security. Given a tree $T$ rooted at a vertex $r$, a {\em penetrating cost} edge function $c$ on $T$, a {\em target-acquisition} vertex function $p$ on $T$, the attacker's {\em budget} and the {\em game-over threshold} $B,G \in {\mathbb{Q}}^{+}$ respectively, we consider the problem of determining the existence of a rooted subtree $T'$ of $T$ within the attacker's budget (that is, the sum of the costs of the edges in $T'$ is less than or equal to $B$) with total acquisition value more than the game-over threshold (that is, the sum of the target values of the nodes in $T'$ is greater than or equal to $G$). We prove that the general version of this problem is intractable, but does admit a polynomial time approximation scheme. We also analyze the complexity of three restricted versions of the problems, where the penetration cost is the constant function, integer-valued, and rational-valued among a given fixed number of distinct values.
Space Bounds for Reliable Multi-Writer Data Store: Inherent Cost of Read/Write Primitives
Venue: arXiv cs.DC 2015
Year: 2015

Reliable storage emulations from fault-prone components have established themselves as an algorithmic foundation of modern storage services and applications. Most existing reliable storage emulations are built from storage services supporting arbitrary read-modify-write primitives. Since such primitives are not typically exposed by pre-existing or off-the-shelf components (such as cloud storage services or network-attached disks) it is natural to ask if they are indeed essential for efficient storage emulations. In this paper, we answer this question in the affirmative. We show that relaxing the underlying storage to only support read/write operations leads to a linear blow-up in the emulation space requirements. We also show that the space complexity is not adaptive to concurrency, which implies that the storage cannot be reliably reclaimed even in sequential runs. On a positive side, we show that Compare-and-Swap primitives, which are commonly available with many off-the-shelf storage services, can be used to emulate a reliable multi-writer atomic register with constant storage and adaptive time complexity.
Information-theoretically Secure Erasure Codes for Distributed Storage
Venue: arXiv cs.IT 2015
Year: 2015

Repair operations in distributed storage systems potentially expose the data to malicious acts of passive eavesdroppers or active adversaries, which can be detrimental to the security of the system. This paper presents erasure codes and repair algorithms that ensure security of the data in the presence of passive eavesdroppers and active adversaries, while maintaining high availability, reliability and efficiency in the system. Our codes are optimal in that they meet previously proposed lower bounds on the storage, network-bandwidth, and reliability requirements for a wide range of system parameters. Our results thus establish the capacity of such systems. Our codes for security from active adversaries provide an additional appealing feature of `on-demand security' where the desired level of security can be chosen separately for each instance of repair, and our algorithms remain optimal simultaneously for all possible levels. The paper also provides necessary and sufficient conditions governing the transformation of any (non-secure) code into one providing on-demand security.
Encoding TLA+ set theory into many-sorted first-order logic
Venue: arXiv cs.LO 2015
Year: 2015

We present an encoding of Zermelo-Fraenkel set theory into many-sorted first-order logic, the input language of state-of-the-art SMT solvers. This translation is the main component of a back-end prover based on SMT solvers in the TLA+ Proof System.
An experimental Study using ACSL and Frama-C to formulate and verify Low-Level Requirements from a DO-178C compliant Avionics Project
Venue: arXiv cs.SE 2015
Year: 2015

Safety critical avionics software is a natural application area for formal verification. This is reflected in the formal method's inclusion into the certification guideline DO-178C and its formal methods supplement DO-333. Airbus and Dassault-Aviation, for example, have conducted studies in using formal verification. A large German national research project, Verisoft XT, also examined the application of formal methods in the avionics domain. However, formal methods are not yet mainstream, and it is questionable if formal verification, especially formal deduction, can be integrated into the software development processes of a resource constrained small or medium enterprise (SME). ESG, a Munich based medium sized company, has conducted a small experimental study on the application of formal verification on a small portion of a real avionics project. The low level specification of a software function was formalized with ACSL, and the corresponding source code was partially verified using Frama-C and the WP plugin, with Alt-Ergo as automated prover. We established a couple of criteria which a method should meet to be fit for purpose for industrial use in SME, and evaluated these criteria with the experience gathered by using ACSL with Frama-C on a real world example. The paper reports on the results of this study but also highlights some issues regarding the method in general which, in our view, will typically arise when using the method in the domain of embedded real-time programming.
A Parameter Estimation Approach to State Observation of Nonlinear Systems
Venue: arXiv cs.SY 2015
Year: 2015

A novel approach to the problem of partial state estimation of nonlinear systems is proposed. The main idea is to translate the state estimation problem into one of estimation of constant, unknown parameters related to the systems initial conditions. The class of systems for which the method is applicable is identified via two assumptions related to the transformability of the system into a suitable cascaded form and our ability to estimate the unknown parameters. The first condition involves the solvability of a partial differential equation while the second one requires some persistency of excitation--like conditions. The proposed observer is shown to be applicable to position estimation of a class of electromechanical systems, for the reconstruction of the state of power converters and for speed observation of a class of mechanical systems.
Simulating Viscous Fingering with a Timespace Method and Anisotropic Mesh Adaptation
Venue: arXiv cs.CE 2015
Year: 2015

We report findings related to a two dimensional viscous fingering problem solved with a timespace method and anisotropic elements. Timespace methods have attracted interest for solution of time dependent partial differential equations due to the implications of parallelism in the temporal dimension, but there are also attractive features in the context of anisotropic mesh adaptation; not only are heuristics and interpolation errors avoided, but slanted elements in timespace also correspond to long and accurate timesteps, i.e. the anisotropy in timespace can be exploited. We show that our timespace method is restricted by a minimum timestep size, which is due to the growth of numerical perturbations. The lower bound on the timestep is, however, quite high, which is indicative that the number of timesteps can be reduced with several orders of magnitude for practical applications.
Web Content Extraction - a Meta-Analysis of its Past and Thoughts on its Future
Venue: arXiv cs.IR 2015
Year: 2015

In this paper, we present a meta-analysis of several Web content extraction algorithms, and make recommendations for the future of content extraction on the Web. First, we find that nearly all Web content extractors do not consider a very large, and growing, portion of modern Web pages. Second, it is well understood that wrapper induction extractors tend to break as the Web changes; heuristic/feature engineering extractors were thought to be immune to a Web site's evolution, but we find that this is not the case: heuristic content extractor performance also tends to degrade over time due to the evolution of Web site forms and practices. We conclude with recommendations for future work that address these and other findings.
Low Rank Representation on Riemannian Manifold of Square Root Densities
Venue: arXiv cs.CV 2015
Year: 2015

In this paper, we present a novel low rank representation (LRR) algorithm for data lying on the manifold of square root densities. Unlike traditional LRR methods which rely on the assumption that the data points are vectors in the Euclidean space, our new algorithm is designed to incorporate the intrinsic geometric structure and geodesic distance of the manifold. Experiments on several computer vision datasets showcase its noise robustness and superior performance on classification and subspace clustering compared to other state-of-the-art approaches.
On the Distributed Computation of Fractional Connected Dominating Set Packings
Venue: arXiv cs.DC 2015
Year: 2015

One of the most fundamental problems in wireless networks is to achieve high throughput. Fractional Connected Dominating Set (FCDS) Packings can achieve a throughput of $Θ(k/\log n)$ messages for networks with node connectivity $k$, which is optimal regarding routing-based message transmission. FCDS were proposed by Censor-Hillel \emph{et al.} [SODA'14,PODC'14] and are a natural generalization to Connected Dominating Sets (CDS), allowing each node to participate with a fraction of its weight in multiple FCDS. Thus, $Ω(k)$ co-existing transmission backbones are established, taking full advantage of the networks connectivity. We propose a modified distributed algorithm that improves upon previous algorithms for $kΔ\in o(\min\{\frac{n \log n}{k} ,D,\sqrt{n \log n} \log^* n\}\log n)$, where $Δ$ is the maximum node degree, $D$ the diameter and $n$ the number of nodes in the network. We achieve this by explicitly computing connections between tentative dominating sets.
Deep clustering: Discriminative embeddings for segmentation and separation
Venue: arXiv cs.NE 2015
Year: 2015

We address the problem of acoustic source separation in a deep learning framework we call "deep clustering." Rather than directly estimating signals or masking functions, we train a deep network to produce spectrogram embeddings that are discriminative for partition labels given in training data. Previous deep network approaches provide great advantages in terms of learning power and speed, but previously it has been unclear how to use them to separate signals in a class-independent way. In contrast, spectral clustering approaches are flexible with respect to the classes and number of items to be segmented, but it has been unclear how to leverage the learning power and speed of deep networks. To obtain the best of both worlds, we use an objective function that to train embeddings that yield a low-rank approximation to an ideal pairwise affinity matrix, in a class-independent way. This avoids the high cost of spectral factorization and instead produces compact clusters that are amenable to simple clustering methods. The segmentations are therefore implicitly encoded in the embeddings, and can be "decoded" by clustering. Preliminary experiments show that the proposed method can separate speech: when trained on spectrogram features containing mixtures of two speakers, and tested on mixtures of a held-out set of speakers, it can infer masking functions that improve signal quality by around 6dB. We show that the model can generalize to three-speaker mixtures despite training only on two-speaker mixtures. The framework can be used without class labels, and therefore has the potential to be trained on a diverse set of sound types, and to generalize to novel sources. We hope that future work will lead to segmentation of arbitrary sounds, with extensions to microphone array methods as well as image segmentation and other domains.
ESDF: Ensemble Selection using Diversity and Frequency
Venue: arXiv cs.LG 2015
Year: 2015

Recently ensemble selection for consensus clustering has emerged as a research problem in Machine Intelligence. Normally consensus clustering algorithms take into account the entire ensemble of clustering, where there is a tendency of generating a very large size ensemble before computing its consensus. One can avoid considering the entire ensemble and can judiciously select few partitions in the ensemble without compromising on the quality of the consensus. This may result in an efficient consensus computation technique and may save unnecessary computational overheads. The ensemble selection problem addresses this issue of consensus clustering. In this paper, we propose an efficient method of ensemble selection for a large ensemble. We prioritize the partitions in the ensemble based on diversity and frequency. Our method selects top K of the partitions in order of priority, where K is decided by the user. We observe that considering jointly the diversity and frequency helps in identifying few representative partitions whose consensus is qualitatively better than the consensus of the entire ensemble. Experimental analysis on a large number of datasets shows our method gives better results than earlier ensemble selection methods.
Trends in crypto-currencies and blockchain technologies: A monetary theory and regulation perspective
Venue: arXiv cs.CR 2015
Year: 2015

The internet era has generated a requirement for low cost, anonymous and rapidly verifiable transactions to be used for online barter, and fast settling money have emerged as a consequence. For the most part, e-money has fulfilled this role, but the last few years have seen two new types of money emerge. Centralised virtual currencies, usually for the purpose of transacting in social and gaming economies, and crypto-currencies, which aim to eliminate the need for financial intermediaries by offering direct peer-to-peer online payments. We describe the historical context which led to the development of these currencies and some modern and recent trends in their uptake, in terms of both usage in the real economy and as investment products. As these currencies are purely digital constructs, with no government or local authority backing, we then discuss them in the context of monetary theory, in order to determine how they may be have value under each. Finally, we provide an overview of the state of regulatory readiness in terms of dealing with transactions in these currencies in various regions of the world.
Tight Bounds for MIS in Multichannel Radio Networks
Venue: arXiv cs.DC 2015
Year: 2015

Daum et al. [PODC'13] presented an algorithm that computes a maximal independent set (MIS) within $O(\log^2 n/F+\log n \mathrm{polyloglog} n)$ rounds in an $n$-node multichannel radio network with $F$ communication channels. The paper uses a multichannel variant of the standard graph-based radio network model without collision detection and it assumes that the network graph is a polynomially bounded independence graph (BIG), a natural combinatorial generalization of well-known geographic families. The upper bound of that paper is known to be optimal up to a polyloglog factor. In this paper, we adapt algorithm and analysis to improve the result in two ways. Mainly, we get rid of the polyloglog factor in the runtime and we thus obtain an asymptotically optimal multichannel radio network MIS algorithm. In addition, our new analysis allows to generalize the class of graphs from those with polynomially bounded local independence to graphs where the local independence is bounded by an arbitrary function of the neighborhood radius.
Fishing out Winners from Vote Streams
Venue: arXiv cs.CC 2015
Year: 2015

We investigate the problem of winner determination from computational social choice theory in the data stream model. Specifically, we consider the task of summarizing an arbitrarily ordered stream of $n$ votes on $m$ candidates into a small space data structure so as to be able to obtain the winner determined by popular voting rules. As we show, finding the exact winner requires storing essentially all the votes. So, we focus on the problem of finding an {\em $\eps$-winner}, a candidate who could win by a change of at most $\eps$ fraction of the votes. We show non-trivial upper and lower bounds on the space complexity of $\eps$-winner determination for several voting rules, including $k$-approval, $k$-veto, scoring rules, approval, maximin, Bucklin, Copeland, and plurality with run off.
Modeling emergence of norms in multi-agent systems by applying tipping points ideas
Venue: arXiv cs.MA 2015
Year: 2015

Norms are known to be a major factor determining humans behavior. It's also shown that norms can be quite effective tool for building agent-based societies. Various normative architectures have been proposed for designing normative multi-agent systems (NorMAS). Due to human nature of the concept norms, many of these architectures are built based on theories in social sciences. Tipping point theory, as is briefly discussed in this paper, seems to have a great potential to be used for designing normative architectures. This theory deals with the factors that affect social epidemics that arise in human societies. In this paper, we try to apply the main concepts of this theory to agent-based normative architectures. We show several ways to implement these concepts, and study their effects in an agent-based normative scenario.
Mining Brain Networks using Multiple Side Views for Neurological Disorder Identification
Venue: arXiv cs.LG 2015
Year: 2015

Mining discriminative subgraph patterns from graph data has attracted great interest in recent years. It has a wide variety of applications in disease diagnosis, neuroimaging, etc. Most research on subgraph mining focuses on the graph representation alone. However, in many real-world applications, the side information is available along with the graph data. For example, for neurological disorder identification, in addition to the brain networks derived from neuroimaging data, hundreds of clinical, immunologic, serologic and cognitive measures may also be documented for each subject. These measures compose multiple side views encoding a tremendous amount of supplemental information for diagnostic purposes, yet are often ignored. In this paper, we study the problem of discriminative subgraph selection using multiple side views and propose a novel solution to find an optimal set of subgraph features for graph classification by exploring a plurality of side views. We derive a feature evaluation criterion, named gSide, to estimate the usefulness of subgraph patterns based upon side views. Then we develop a branch-and-bound algorithm, called gMSV, to efficiently search for optimal subgraph features by integrating the subgraph mining process and the procedure of discriminative feature selection. Empirical studies on graph classification tasks for neurological disorders using brain networks demonstrate that subgraph patterns selected by the multi-side-view guided subgraph selection approach can effectively boost graph classification performances and are relevant to disease diagnosis.
Drawing and Analyzing Causal DAGs with DAGitty
Venue: arXiv cs.AI 2015
Year: 2015

DAGitty is a software for drawing and analyzing causal diagrams, also known as directed acyclic graphs (DAGs). Functions include identification of minimal sufficient adjustment sets for estimating causal effects, diagnosis of insufficient or invalid adjustment via the identification of biasing paths, identification of instrumental variables, and derivation of testable implications. DAGitty is provided in the hope that it is useful for researchers and students in Epidemiology, Sociology, Psychology, and other empirical disciplines. The software should run in any web browser that supports modern JavaScript, HTML, and SVG. This is the user manual for DAGitty version 2.3. The manual is updated with every release of a new stable version. DAGitty is available at dagitty.net.
Cloud based Big Data Analytics: A Survey of Current Research and Future Directions
Venue: arXiv cs.DC 2015
Year: 2015

The advent of the digital age has led to a rise in different types of data with every passing day. In fact, it is expected that half of the total data will be on the cloud by 2016. This data is complex and needs to be stored, processed and analyzed for information that can be used by organizations. Cloud computing provides an apt platform for big data analytics in view of the storage and computing requirements of the latter. This makes cloud-based analytics a viable research field. However, several issues need to be addressed and risks need to be mitigated before practical applications of this synergistic model can be popularly used. This paper explores the existing research, challenges, open issues and future research direction for this field of study.
Arrow type impossibility theorems over median algebras
Venue: arXiv cs.DM 2015
Year: 2015

We characterize trees as median algebras and semilattices by relaxing conservativeness. Moreover, we describe median homomorphisms between products of median algebras and show that Arrow type impossibility theorems for mappings from a product $\mathbf{A}_1\times \cdots \times \mathbf{A}_n$ of median algebras to a median algebra $\mathbf{B}$ are possible if and only if $\mathbf{B}$ is a tree, when thought of as an ordered structure.
A short note on estimation of WCRE and WCE
Venue: arXiv cs.IT 2015
Year: 2015

In this note the author uses order statistics to estimate WCRE and WCE in terms of empirical and survival functions. An example in both cases normal and exponential WFs is analyzed.