OpenRaiser/Intern-Atlas huggingface dataset:
Exploiting System Hierarchy to Compute Repair Plans in Probabilistic Model-based Diagnosis
Venue: arXiv cs.AI 2013
Year: 2013

The goal of model-based diagnosis is to isolate causes of anomalous system behavior and recommend inexpensive repair actions in response. In general, precomputing optimal repair policies is intractable. To date, investigators addressing this problem have explored approximations that either impose restrictions on the system model (such as a single fault assumption) or compute an immediate best action with limited lookahead. In this paper, we develop a formulation of repair in model-based diagnosis and a repair algorithm that computes optimal sequences of actions. This optimal approach is costly but can be applied to precompute an optimal repair strategy for compact systems. We show how we can exploit a hierarchical system specification to make this approach tractable for large systems. When introducing hierarchy, we also consider the tradeoff between simply replacing a component and decomposing it to repair its subcomponents. The hierarchical repair algorithm is suitable for off-line precomputation of an optimal repair strategy. A modification of the algorithm takes advantage of an iterative deepening scheme to trade off inference time and the quality of the computed strategy.
Inference with Causal Independence in the CPSC Network
Venue: arXiv cs.AI 2013
Year: 2013

This paper reports experiments with the causal independence inference algorithm proposed by Zhang and Poole (1994b) on the CPSC network created by Pradhan et al. (1994). It is found that the algorithm is able to answer 420 of the 422 possible zero-observation queries, 94 of 100 randomly generated five-observation queries, 87 of 100 randomly generated ten-observation queries, and 69 of 100 randomly generated twenty-observation queries.
Asymptotic Data Rates of Receive-Diversity Systems with MMSE Estimation and Spatially Correlated Interferers
Venue: arXiv cs.IT 2013
Year: 2013

An asymptotic technique is presented to characterize the bits/symbol achievable on a representative wireless link in a spatially distributed network with active interferers at correlated positions, N receive diversity branches, and linear Minimum-Mean-Square-Error (MMSE) receivers. This framework is then applied to systems including analogs to Matern type I and type II networks which are useful to model systems with Medium-Access Control (MAC), cellular uplinks with orthogonal transmissions and frequency reuse, and Boolean cluster networks. It is found that for our network models, with moderately large N, the correlation between interferer positions does not significantly influence the bits/symbol resulting in simple approximations for the data rates achievable in such networks which are known to be difficult to analyze and for which few analytical results are available.
Linear Coding Schemes for the Distributed Computation of Subspaces
Venue: arXiv cs.IT 2013
Year: 2013

Let $X_1, ..., X_m$ be a set of $m$ statistically dependent sources over the common alphabet $\mathbb{F}_q$, that are linearly independent when considered as functions over the sample space. We consider a distributed function computation setting in which the receiver is interested in the lossless computation of the elements of an $s$-dimensional subspace $W$ spanned by the elements of the row vector $[X_1, \ldots, X_m]Γ$ in which the $(m \times s)$ matrix $Γ$ has rank $s$. A sequence of three increasingly refined approaches is presented, all based on linear encoders. The first approach uses a common matrix to encode all the sources and a Korner-Marton like receiver to directly compute $W$. The second improves upon the first by showing that it is often more efficient to compute a carefully chosen superspace $U$ of $W$. The superspace is identified by showing that the joint distribution of the $\{X_i\}$ induces a unique decomposition of the set of all linear combinations of the $\{X_i\}$, into a chain of subspaces identified by a normalized measure of entropy. This subspace chain also suggests a third approach, one that employs nested codes. For any joint distribution of the $\{X_i\}$ and any $W$, the sum-rate of the nested code approach is no larger than that under the Slepian-Wolf (SW) approach. Under the SW approach, $W$ is computed by first recovering each of the $\{X_i\}$. For a large class of joint distributions and subspaces $W$, the nested code approach is shown to improve upon SW. Additionally, a class of source distributions and subspaces are identified, for which the nested-code approach is sum-rate optimal.
Naturally Rehearsing Passwords
Venue: arXiv cs.CR 2013
Year: 2013

We introduce quantitative usability and security models to guide the design of password management schemes --- systematic strategies to help users create and remember multiple passwords. In the same way that security proofs in cryptography are based on complexity-theoretic assumptions (e.g., hardness of factoring and discrete logarithm), we quantify usability by introducing usability assumptions. In particular, password management relies on assumptions about human memory, e.g., that a user who follows a particular rehearsal schedule will successfully maintain the corresponding memory. These assumptions are informed by research in cognitive science and validated through empirical studies. Given rehearsal requirements and a user's visitation schedule for each account, we use the total number of extra rehearsals that the user would have to do to remember all of his passwords as a measure of the usability of the password scheme. Our usability model leads us to a key observation: password reuse benefits users not only by reducing the number of passwords that the user has to memorize, but more importantly by increasing the natural rehearsal rate for each password. We also present a security model which accounts for the complexity of password management with multiple accounts and associated threats, including online, offline, and plaintext password leak attacks. Observing that current password management schemes are either insecure or unusable, we present Shared Cues--- a new scheme in which the underlying secret is strategically shared across accounts to ensure that most rehearsal requirements are satisfied naturally while simultaneously providing strong security. The construction uses the Chinese Remainder Theorem to achieve these competing goals.
Quantum-inspired Huffman Coding
Venue: arXiv cs.IT 2013
Year: 2013

Huffman Compression, also known as Huffman Coding, is one of many compression techniques in use today. The two important features of Huffman coding are instantaneousness that is the codes can be interpreted as soon as they are received and variable length that is a most frequent symbol has length smaller than a less frequent symbol. The traditional Huffman coding has two procedures: constructing a tree in O(n^2) and then traversing it in O(n). Quantum computing is a promising approach of computation that is based on equations from Quantum Mechanics. Instantaneousness and variable length features are difficult to generalize to the quantum case. The quantum coding field is pioneered by Schumacher works on block coding scheme. To encode N signals sequentially, it requires O(N3) computational steps. The encoding and decoding processes are far from instantaneous. Moreover, the lengths of all the codewords are the same. A Huffman-coding-inspired scheme for the storage of quantum information takes O(N(log N)a) computational steps for a sequential implementation on non-parallel machines.
Prediction and Clustering in Signed Networks: A Local to Global Perspective
Venue: arXiv cs.SI 2013
Year: 2013

The study of social networks is a burgeoning research area. However, most existing work deals with networks that simply encode whether relationships exist or not. In contrast, relationships in signed networks can be positive ("like", "trust") or negative ("dislike", "distrust"). The theory of social balance shows that signed networks tend to conform to some local patterns that, in turn, induce certain global characteristics. In this paper, we exploit both local as well as global aspects of social balance theory for two fundamental problems in the analysis of signed networks: sign prediction and clustering. Motivated by local patterns of social balance, we first propose two families of sign prediction methods: measures of social imbalance (MOIs), and supervised learning using high order cycles (HOCs). These methods predict signs of edges based on triangles and \ell-cycles for relatively small values of \ell. Interestingly, by examining measures of social imbalance, we show that the classic Katz measure, which is used widely in unsigned link prediction, actually has a balance theoretic interpretation when applied to signed networks. Furthermore, motivated by the global structure of balanced networks, we propose an effective low rank modeling approach for both sign prediction and clustering. For the low rank modeling approach, we provide theoretical performance guarantees via convex relaxations, scale it up to large problem sizes using a matrix factorization based algorithm, and provide extensive experimental validation including comparisons with local approaches. Our experimental results indicate that, by adopting a more global viewpoint of balance structure, we get significant performance and computational gains in prediction and clustering tasks on signed networks. Our work therefore highlights the usefulness of the global aspect of balance theory for the analysis of signed networks.
Rate-Compatible Short-Length Protograph LDPC Codes
Venue: arXiv cs.IT 2013
Year: 2013

This paper produces a rate-compatible protograph LDPC code at 1k information blocklength with superior performance in both waterfall and error floor regions. The design of such codes has proved difficult in the past because the constraints imposed by structured design (protographs), rate-compatibility, as well as small block length, are not easily satisfied together. For example, as the block length decreases, the predominance of decoding threshold as the main parameter in coding design is reduced, thus complicating the search for good codes. Our rate-compatible protograph codes have rates ranging from 1/3 to 4/5 and show no error floor down to $10^{-6}$ FER.
Sequence Diagram Test Case Specification and Virtual Integration Analysis using Timed-Arc Petri Nets
Venue: arXiv cs.SE 2013
Year: 2013

In this paper, we formally define Test Case Sequence Diagrams (TCSD) as an easy-to-use means to specify test cases for components including timing constraints. These test cases are modeled using the UML2 syntax and can be specified by standard UML-modeling-tools. In a component-based design an early identification of errors can be achieved by a virtual integration of components before the actual system is build. We define such a procedure which integrates the individual test cases of the components according to the interconnections of a given architecture and checks if all specified communication sequences are consistent. Therefore, we formally define the transformation of TCSD into timed-arc Petri nets and a process for the combination of these nets. The applicability of our approach is demonstrated on an avionic use case from the ARP4761 standard.
Assembling the Proofs of Ordered Model Transformations
Venue: arXiv cs.LO 2013
Year: 2013

In model-driven development, an ordered model transformation is a nested set of transformations between source and target classes, in which each transformation is governed by its own pre and post- conditions, but structurally dependent on its parent. Following the proofs-as-model-transformations approach, in this paper we consider a formalisation in Constructive Type Theory of the concepts of model and model transformation, and show how the correctness proofs of potentially large ordered model transformations can be systematically assembled from the proofs of the specifications of their parts, making them easier to derive.
Towards a Framework for Behavioral Specifications of OSGi Components
Venue: arXiv cs.SE 2013
Year: 2013

We present work on behavioral specifications of OSGi components. Our behavioral specifications are based on finite automata like formalisms. Behavioral specifications can be used to find appropriate components to interact with, detect incompatibilities between communication protocols of components and potential problems resulting from the interplay of non-deterministic component specifications. These operations can be carried out during development and at runtime of a system. Furthermore, we describe work carried out using the Eclipse based implementation of our framework.
Implications for Improving Accessibility to E-Commerce Websites in Developing Countries: A Subjective Study of Sri Lankan Hotel Websites
Venue: arXiv cs.CY 2013
Year: 2013

This research explores the accessibility issues with regard to the e-commerce websites in developing countries, through a subjective study of Sri Lankan hotel websites. A web survey and a web content analysis were conducted as the methods to elicit data on web accessibility. Factors preventing accessibility were hypothesized as an initial experiment. Hazardous design elements are identified through web content analysis, the results of which are utilized to develop specific implications for improving web accessibility. The hypothesis tests show that there is no significant correlation between accessibility and geographical or economic factors. However, physical impairments of users have a considerable influence on the accessibility. Especially, visual and mobility impaired users experience poor accessibility. Poor readability and less navigable page designs are two observable issues, which pose threats to accessibility. The lack of conformance to W3C accessibility guidelines and the poor design process are the specific shortcomings which reduce the overall accessibility. Guidelines aim to improve the accessibility of sites with a strategic focus. Further enhancements are suggested with adherence to principles and user centered design and developing customizable web portals compatible for connections with differing speeds. A need for developing new design models for differencing user groups and implementing web accessibility strategy are emphasized as vital steps towards effective information dissemination via e-commerce websites in the developing countries.
Are Yao Graph and Theta Graph Void Free?
Venue: arXiv cs.NI 2013
Year: 2013

Greedy Forwarding algorithm is a widely-used routing algorithm for wireless networks. However, it can fail if network topologies (usually modeled by geometric graphs) contain voids. Since Yao Graph and Theta Graph are two types of geometric graphs exploited to construct wireless network topologies, this paper studies whether these two types of graphs can contain voids. Specifically, this paper shows that when the number of cones in a Yao Graph or Theta Graph is less than 6, Yao Graph and Theta Graph can have voids, but when the number of cones equals or exceeds 6, Yao Graph and Theta Graph are free of voids.
On the performance of a hybrid genetic algorithm in dynamic environments
Venue: arXiv cs.NE 2013
Year: 2013

The ability to track the optimum of dynamic environments is important in many practical applications. In this paper, the capability of a hybrid genetic algorithm (HGA) to track the optimum in some dynamic environments is investigated for different functional dimensions, update frequencies, and displacement strengths in different types of dynamic environments. Experimental results are reported by using the HGA and some other existing evolutionary algorithms in the literature. The results show that the HGA has better capability to track the dynamic optimum than some other existing algorithms.
Classification and Characterization of Core Grid Protocols for Global Grid Computing
Venue: arXiv cs.DC 2013
Year: 2013

Grid computing has attracted many researchers over a few years, and as a result many new protocols have emerged and also evolved since its inception a decade ago. Grid protocols play major role in implementing services that facilitate coordinated resource sharing across diverse organizations. In this paper, we provide comprehensive coverage of different core Grid protocols that can be used in Global Grid Computing. We establish the classification of core Grid protocols into i) Grid network communication and Grid data transfer protocols, ii) Grid information security protocols, iii) Grid resource information protocols, iv) Grid management protocols, and v) Grid interface protocols, depending upon the kind of activities handled by these protocols. All the classified protocols are also organized into layers of the Hourglass model of Grid architecture to understand dependency among these protocols. We also present the characteristics of each protocol. For better understanding of these protocols, we also discuss applied protocols as examples from either Globus toolkit or other popular Grid middleware projects. We believe that our classification and characterization of Grid protocols will enable better understanding of core Grid protocols and will motivate further research in the area of Global Grid Computing.
Locally Repairable Codes with Multiple Repair Alternatives
Venue: arXiv cs.IT 2013
Year: 2013

Distributed storage systems need to store data redundantly in order to provide some fault-tolerance and guarantee system reliability. Different coding techniques have been proposed to provide the required redundancy more efficiently than traditional replication schemes. However, compared to replication, coding techniques are less efficient for repairing lost redundancy, as they require retrieval of larger amounts of data from larger subsets of storage nodes. To mitigate these problems, several recent works have presented locally repairable codes designed to minimize the repair traffic and the number of nodes involved per repair. Unfortunately, existing methods often lead to codes where there is only one subset of nodes able to repair a piece of lost data, limiting the local repairability to the availability of the nodes in this subset. In this paper, we present a new family of locally repairable codes that allows different trade-offs between the number of contacted nodes per repair, and the number of different subsets of nodes that enable this repair. We show that slightly increasing the number of contacted nodes per repair allows to have repair alternatives, which in turn increases the probability of being able to perform efficient repairs. Finally, we present pg-BLRC, an explicit construction of locally repairable codes with multiple repair alternatives, constructed from partial geometries, in particular from Generalized Quadrangles. We show how these codes can achieve practical lengths and high rates, while requiring a small number of nodes per repair, and providing multiple repair alternatives.
Invisible Flow Watermarks for Channels with Dependent Substitution, Deletion, and Bursty Insertion Errors
Venue: arXiv cs.CR 2013
Year: 2013

Flow watermarks efficiently link packet flows in a network in order to thwart various attacks such as stepping stones. We study the problem of designing good flow watermarks. Earlier flow watermarking schemes mostly considered substitution errors, neglecting the effects of packet insertions and deletions that commonly happen within a network. More recent schemes consider packet deletions but often at the expense of the watermark visibility. We present an invisible flow watermarking scheme capable of enduring a large number of packet losses and insertions. To maintain invisibility, our scheme uses quantization index modulation (QIM) to embed the watermark into inter-packet delays, as opposed to time intervals including many packets. As the watermark is injected within individual packets, packet losses and insertions may lead to watermark desynchronization and substitution errors. To address this issue, we add a layer of error-correction coding to our scheme. Experimental results on both synthetic and real network traces demonstrate that our scheme is robust to network jitter, packet drops and splits, while remaining invisible to an attacker.
Call-by-Value and Call-by-Name Dual Calculi with Inductive and Coinductive Types
Venue: arXiv cs.LO 2013
Year: 2013

This paper extends the dual calculus with inductive types and coinductive types. The paper first introduces a non-deterministic dual calculus with inductive and coinductive types. Besides the same duality of the original dual calculus, it has the duality of inductive and coinductive types, that is, the duality of terms and coterms for inductive and coinductive types, and the duality of their reduction rules. Its strong normalization is also proved, which is shown by translating it into a second-order dual calculus. The strong normalization of the second-order dual calculus is proved by translating it into the second-order symmetric lambda calculus. This paper then introduces a call-by-value system and a call-by-name system of the dual calculus with inductive and coinductive types, and shows the duality of call-by-value and call-by-name, their Church-Rosser properties, and their strong normalization. Their strong normalization is proved by translating them into the non-deterministic dual calculus with inductive and coinductive types.
Measuring Visual Complexity of Cluster-Based Visualizations
Venue: arXiv cs.AI 2013
Year: 2013

Handling visual complexity is a challenging problem in visualization owing to the subjectiveness of its definition and the difficulty in devising generalizable quantitative metrics. In this paper we address this challenge by measuring the visual complexity of two common forms of cluster-based visualizations: scatter plots and parallel coordinatess. We conceptualize visual complexity as a form of visual uncertainty, which is a measure of the degree of difficulty for humans to interpret a visual representation correctly. We propose an algorithm for estimating visual complexity for the aforementioned visualizations using Allen's interval algebra. We first establish a set of primitive 2-cluster cases in scatter plots and another set for parallel coordinatess based on symmetric isomorphism. We confirm that both are the minimal sets and verify the correctness of their members computationally. We score the uncertainty of each primitive case based on its topological properties, including the existence of overlapping regions, splitting regions and meeting points or edges. We compare a few optional scoring schemes against a set of subjective scores by humans, and identify the one that is the most consistent with the subjective scores. Finally, we extend the 2-cluster measure to k-cluster measure as a general purpose estimator of visual complexity for these two forms of cluster-based visualization.
Design of Nonlinear State Observers for One-Sided Lipschitz Systems
Venue: arXiv cs.SY 2013
Year: 2013

Control and state estimation of nonlinear systems satisfying a Lipschitz continuity condition have been important topics in nonlinear system theory for over three decades, resulting in a substantial amount of literature. The main criticism behind this approach, however, has been the restrictive nature of the Lipschitz continuity condition and the conservativeness of the related results. This work deals with an extension to this problem by introducing a more general family of nonlinear functions, namely one-sided Lipschitz functions. The corresponding class of systems is a superset of its well-known Lipschitz counterpart and possesses inherent advantages with respect to conservativeness. In this paper, first the problem of state observer design for this class of systems is established, the challenges are discussed and some analysis-oriented tools are provided. Then, a solution to the observer design problem is proposed in terms of nonlinear matrix inequalities which in turn are converted into numerically efficiently solvable linear matrix inequalities.