OpenRaiser/Intern-Atlas huggingface dataset:
A New and Efficient Algorithm-Based Fault Tolerance Scheme for A Million Way Parallelism
Venue: arXiv cs.DC 2011
Year: 2011

Fault tolerance overhead of high performance computing (HPC) applications is becoming critical to the efficient utilization of HPC systems at large scale. HPC applications typically tolerate fail-stop failures by checkpointing. Another promising method is in the algorithm level, called algorithmic recovery. These two methods can achieve high efficiency when the system scale is not very large, but will both lose their effectiveness when systems approach the scale of Exaflops, where the number of processors including in system is expected to achieve one million. This paper develops a new and efficient algorithm-based fault tolerance scheme for HPC applications. When failure occurs during the execution, we do not stop to wait for the recovery of corrupted data, but replace them with the corresponding redundant data and continue the execution. A background accelerated recovery method is also proposed to rebuild redundancy to tolerate multiple times of failures during the execution. To demonstrate the feasibility of our new scheme, we have incorporated it to the High Performance Linpack. Theoretical analysis demonstrates that our new fault tolerance scheme can still be effective even when the system scale achieves the Exaflops. Experiment using SiCortex SC5832 verifies the feasibility of the scheme, and indicates that the advantage of our scheme can be observable even in a small scale.
Continuum Limits of Markov Chains with Application to Network Modeling
Venue: arXiv cs.NI 2011
Year: 2011

In this paper we investigate the continuum limits of a class of Markov chains. The investigation of such limits is motivated by the desire to model very large networks. We show that under some conditions, a sequence of Markov chains converges in some sense to the solution of a partial differential equation. Based on such convergence we approximate Markov chains modeling networks with a large number of components by partial differential equations. While traditional Monte Carlo simulation for very large networks is practically infeasible, partial differential equations can be solved with reasonable computational overhead using well-established mathematical tools.
Human as Real-Time Sensors of Social and Physical Events: A Case Study of Twitter and Sports Games
Venue: arXiv cs.SI 2011
Year: 2011

In this work, we study how Twitter can be used as a sensor to detect frequent and diverse social and physical events in real-time. We devise efficient data collection and event recognition solutions that work despite various limits on free access to Twitter data. We describe a web service implementation of our solution and report our experience with the 2010-2011 US National Football League (NFL) games. The service was able to recognize NFL game events within 40 seconds and with accuracy up to 90%. This capability will be very useful for not only real-time electronic program guide for live broadcast programs but also refined auction of advertisement slots. More importantly, it demonstrates for the first time the feasibility of using Twitter for real-time social and physical event detection for ubiquitous computing.
Logic circuits from zero forcing
Venue: arXiv cs.DM 2011
Year: 2011

We design logic circuits based on the notion of zero forcing on graphs; each gate of the circuits is a gadget in which zero forcing is performed. We show that such circuits can evaluate every monotone Boolean function. By using two vertices to encode each logical bit, we obtain universal computation. We also highlight a phenomenon of "back forcing" as a property of each function. Such a phenomenon occurs in a circuit when the input of gates which have been already used at a given time step is further modified by a computation actually performed at a later stage. Finally, we point out that zero forcing can be also used to implement reversible computation. The model introduced here provides a potentially new tool in the analysis of Boolean functions, with particular attention to monotonicity.
Space Lower Bounds for Online Pattern Matching
Venue: arXiv cs.DS 2011
Year: 2011

We present space lower bounds for online pattern matching under a number of different distance measures. Given a pattern of length m and a text that arrives one character at a time, the online pattern matching problem is to report the distance between the pattern and a sliding window of the text as soon as the new character arrives. We require that the correct answer is given at each position with constant probability. We give Omega(m) bit space lower bounds for L_1, L_2, L_\infty, Hamming, edit and swap distances as well as for any algorithm that computes the cross-correlation/convolution. We then show a dichotomy between distance functions that have wildcard-like properties and those that do not. In the former case which includes, as an example, pattern matching with character classes, we give Omega(m) bit space lower bounds. For other distance functions, we show that there exist space bounds of Omega(log m) and O(log^2 m) bits. Finally we discuss space lower bounds for non-binary inputs and show how in some cases they can be improved.
Tactics for Reasoning modulo AC in Coq
Venue: arXiv cs.MS 2011
Year: 2011

We present a set of tools for rewriting modulo associativity and commutativity (AC) in Coq, solving a long-standing practical problem. We use two building blocks: first, an extensible reflexive decision procedure for equality modulo AC; second, an OCaml plug-in for pattern matching modulo AC. We handle associative only operations, neutral elements, uninterpreted function symbols, and user-defined equivalence relations. By relying on type-classes for the reification phase, we can infer these properties automatically, so that end-users do not need to specify which operation is A or AC, or which constant is a neutral element.
An Analysis of Phase Transition in NK Landscapes
Venue: arXiv cs.AI 2011
Year: 2011

In this paper, we analyze the decision version of the NK landscape model from the perspective of threshold phenomena and phase transitions under two random distributions, the uniform probability model and the fixed ratio model. For the uniform probability model, we prove that the phase transition is easy in the sense that there is a polynomial algorithm that can solve a random instance of the problem with the probability asymptotic to 1 as the problem size tends to infinity. For the fixed ratio model, we establish several upper bounds for the solubility threshold, and prove that random instances with parameters above these upper bounds can be solved polynomially. This, together with our empirical study for random instances generated below and in the phase transition region, suggests that the phase transition of the fixed ratio model is also easy.
Propositional Independence - Formula-Variable Independence and Forgetting
Venue: arXiv cs.AI 2011
Year: 2011

Independence -- the study of what is relevant to a given problem of reasoning -- has received an increasing attention from the AI community. In this paper, we consider two basic forms of independence, namely, a syntactic one and a semantic one. We show features and drawbacks of them. In particular, while the syntactic form of independence is computationally easy to check, there are cases in which things that intuitively are not relevant are not recognized as such. We also consider the problem of forgetting, i.e., distilling from a knowledge base only the part that is relevant to the set of queries constructed from a subset of the alphabet. While such process is computationally hard, it allows for a simplification of subsequent reasoning, and can thus be viewed as a form of compilation: once the relevant part of a knowledge base has been extracted, all reasoning tasks to be performed can be simplified.
Partition distances
Venue: arXiv cs.DM 2011
Year: 2011

Alternative novel measures of the distance between any two partitions of a n-set are proposed and compared, together with a main existing one, namely 'partition-distance' D(.,.). The comparison achieves by checking their restriction to modular elements of the partition lattice, as well as in terms of suitable classifiers. Two of the new measures obtain through the size, a function mapping every partition into the number of atoms finer than that partition. One of these size-based distances extends to geometric lattices the traditional Hamming distance between subsets, when these latter are regarded as hypercube vertexes or binary n-vectors. After carefully framing the environment, a main comparison finally results from the following bounding problem: for every value k, with 0<k<n, of partition-distance D(.,.), determine the minimum and maximum of the 'indicator-Hamming' distance d(P,Q) proposed here over all pairs of partitions P,Q such that D(P,Q)=k.
Optimal Bi-Valued Auctions
Venue: arXiv cs.DS 2011
Year: 2011

We investigate \emph{bi-valued} auctions in the digital good setting and construct an explicit polynomial time deterministic auction. We prove an unconditional tight lower bound which holds even for random superpolynomial auctions. The analysis of the construction uses the adoption of the finer lens of \emph{general competitiveness} which considers additive losses on top of multiplicative ones. The result implies that general competitiveness is the right notion to use in this setting, as this optimal auction is uncompetitive with respect to competitive measures which do not consider additive losses.
Computing hypergraph width measures exactly
Venue: arXiv cs.CC 2011
Year: 2011

Hypergraph width measures are a class of hypergraph invariants important in studying the complexity of constraint satisfaction problems (CSPs). We present a general exact exponential algorithm for a large variety of these measures. A connection between these and tree decompositions is established. This enables us to almost seamlessly adapt the combinatorial and algorithmic results known for tree decompositions of graphs to the case of hypergraphs and obtain fast exact algorithms. As a consequence, we provide algorithms which, given a hypergraph H on n vertices and m hyperedges, compute the generalized hypertree-width of H in time O*(2^n) and compute the fractional hypertree-width of H in time O(m*1.734601^n).
On Polynomial Sized MDP Succinct Policies
Venue: arXiv cs.AI 2011
Year: 2011

Policies of Markov Decision Processes (MDPs) determine the next action to execute from the current state and, possibly, the history (the past states). When the number of states is large, succinct representations are often used to compactly represent both the MDPs and the policies in a reduced amount of space. In this paper, some problems related to the size of succinctly represented policies are analyzed. Namely, it is shown that some MDPs have policies that can only be represented in space super-polynomial in the size of the MDP, unless the polynomial hierarchy collapses. This fact motivates the study of the problem of deciding whether a given MDP has a policy of a given size and reward. Since some algorithms for MDPs work by finding a succinct representation of the value function, the problem of deciding the existence of a succinct representation of a value function of a given size and reward is also considered.
A Generalized Criterion for Signature-based Algorithms to Compute Gröbner Bases
Venue: arXiv cs.SC 2011
Year: 2011

A generalized criterion for signature-based algorithms to compute Gröbner bases is proposed in this paper. This criterion is named by "generalized criterion", because it can be specialized to almost all existing criteria for signature-based algorithms which include the famous F5 algorithm, F5C, extended F5, G$^2$V and the GVW algorithm. The main purpose of current paper is to study in theory which kind of criteria is correct in signature-based algorithms and provide a generalized method to develop new criteria. For this purpose, by studying some key facts and observations of signature-based algorithms, a generalized criterion is proposed. The generalized criterion only relies on a partial order defined on a set of polynomials. When specializing the partial order to appropriate specific orders, the generalized criterion can specialize to almost all existing criteria of signature-based algorithms. For {\em admissible} partial orders, a proof is presented for the correctness of the algorithm that is based on this generalized criterion. And the partial orders implied by the criteria of F5 and GVW are also shown to be admissible. More importantly, the generalized criterion provides an effective method to check whether a new criterion is correct as well as to develop new criteria for signature-based algorithms.
Probabilistic Bounds on the Length of a Longest Edge in Delaunay Graphs of Random Points in d-Dimensions
Venue: arXiv cs.CG 2011
Year: 2011

Motivated by low energy consumption in geographic routing in wireless networks, there has been recent interest in determining bounds on the length of edges in the Delaunay graph of randomly distributed points. Asymptotic results are known for random networks in planar domains. In this paper, we obtain upper and lower bounds that hold with parametric probability in any dimension, for points distributed uniformly at random in domains with and without boundary. The results obtained are asymptotically tight for all relevant values of such probability and constant number of dimensions, and show that the overhead produced by boundary nodes in the plane holds also for higher dimensions. To our knowledge, this is the first comprehensive study on the lengths of long edges in Delaunay graphs
Dynamic Fractional Resource Scheduling vs. Batch Scheduling
Venue: arXiv cs.DC 2011
Year: 2011

We propose a novel job scheduling approach for homogeneous cluster computing platforms. Its key feature is the use of virtual machine technology to share fractional node resources in a precise and controlled manner. Other VM-based scheduling approaches have focused primarily on technical issues or on extensions to existing batch scheduling systems, while we take a more aggressive approach and seek to find heuristics that maximize an objective metric correlated with job performance. We derive absolute performance bounds and develop algorithms for the online, non-clairvoyant version of our scheduling problem. We further evaluate these algorithms in simulation against both synthetic and real-world HPC workloads and compare our algorithms to standard batch scheduling approaches. We find that our approach improves over batch scheduling by orders of magnitude in terms of job stretch, while leading to comparable or better resource utilization. Our results demonstrate that virtualization technology coupled with lightweight online scheduling strategies can afford dramatic improvements in performance for executing HPC workloads.
Secure Mining of Association Rules in Horizontally Distributed Databases
Venue: arXiv cs.DB 2011
Year: 2011

We propose a protocol for secure mining of association rules in horizontally distributed databases. The current leading protocol is that of Kantarcioglu and Clifton (TKDE 2004). Our protocol, like theirs, is based on the Fast Distributed Mining (FDM) algorithm of Cheung et al. (PDIS 1996), which is an unsecured distributed version of the Apriori algorithm. The main ingredients in our protocol are two novel secure multi-party algorithms --- one that computes the union of private subsets that each of the interacting players hold, and another that tests the inclusion of an element held by one player in a subset held by another. Our protocol offers enhanced privacy with respect to the protocol of Kantarcioglu and Clifton. In addition, it is simpler and is significantly more efficient in terms of communication rounds, communication cost and computational cost.
Clustering with Prototype Extraction for Census Data Analysis
Venue: arXiv cs.DB 2011
Year: 2011

Not long ago primary census data became available to publicity. It opened qualitatively new perspectives not only for researchers in demography and sociology, but also for those people, who somehow face processes occurring in society. In this paper authors propose using Data Mining methods for searching hidden patterns in census data. A novel clustering-based technique is described as well. It allows determining factors which influence people behavior, in particular decision-making process (as an example, a decision whether to have a baby or not). Proposed technique is based on clustering a set of respondents, for whom a certain event have already happened (for instance, a baby was born), and discovering clusters' prototypes from a set of respondents, for whom this event hasn't occurred yet. By means of analyzing clusters' and their prototypes' characteristics it is possible to identify which factors influence the decision-making process. Authors also provide an experimental example of the described approach usage.
Permission-Based Separation Logic for Message-Passing Concurrency
Venue: arXiv cs.LO 2011
Year: 2011

We develop local reasoning techniques for message passing concurrent programs based on ideas from separation logics and resource usage analysis. We extend processes with permission- resources and define a reduction semantics for this extended language. This provides a foundation for interpreting separation formulas for message-passing concurrency. We also define a sound proof system permitting us to infer satisfaction compositionally using local, separation-based reasoning.
A Simulation Study for T0/T1 Data Replication and Production Activities
Venue: arXiv cs.DC 2011
Year: 2011

This paper discusses the latest generation of the MONARC (MOdels of Networked Analysis at Regional Centers) simulation framework, as a design and modeling tool for large scale distributed systems applied to HEP experiments. The simulation of Grid architectures has a vital importance in the future deployment of Grid systems for providing the users an appropriate feed-back. We present here an example of simulating complex data processing systems and the way the framework is used to optimize the overall Grid architecture and/or the policies that govern the Grid's use.
LISA (Localhost Information Service Agent)
Venue: arXiv cs.DC 2011
Year: 2011

Grid computing has gained an increasing importance in the last years, especially in the academic environments, offering the possibility to rapidly solve complex scientific problems. The monitoring of the Grid jobs has a vital importance for analyzing the system's performance, for providing the users an appropriate feed-back, and for obtaining historical data which may be used for performance prediction. Several monitoring systems have been developed, with different strategies to collect and store the information. We shall present here a solution based on MonALISA, a distributed service for monitoring, control and global optimization of complex systems, and LISA, a component application of MonALISA which can help in optimizing other applications by means of monitoring services. The advantages of this system are, among others, flexibility, dynamic configuration, high communication performance.
Opportunistic Power Control for Multi-Carrier Interference Channels
Venue: arXiv cs.GT 2011
Year: 2011

We propose a new method for opportunistic power control in multi-carrier interference channels for delay-tolerant data services. In doing so, we utilize a game theoretic framework with novel constraints, where each user tries to maximize its utility in a distributed and opportunistic manner, while satisfying the game's constraints by adapting its transmit power to its channel. In this scheme, users transmit with more power on good sub-channels and do the opposite on bad sub-channels. In this way, in addition to the allocated power on each sub-channel, the total power of all users also depends on channel conditions. Since each user's power level depends on power levels of other users, the game belongs to the \emph{generalized} Nash equilibrium (GNE) problems, which in general, is hard to analyze. We show that the proposed game has a GNE, and derive the sufficient conditions for its uniqueness. Besides, we propose a new pricing scheme for maximizing each user's throughput in an opportunistic manner under its total power constraint; and provide the sufficient conditions for the algorithm's convergence and its GNE's uniqueness. Simulations confirm that our proposed scheme yields a higher throughput for each user and/or has a significantly improved efficiency as compared to other existing opportunistic methods.
SAPA: A Multi-objective Metric Temporal Planner
Venue: arXiv cs.AI 2011
Year: 2011

SAPA is a domain-independent heuristic forward chaining planner that can handle durative actions, metric resource constraints, and deadline goals. It is designed to be capable of handling the multi-objective nature of metric temporal planning. Our technical contributions include (i) planning-graph based methods for deriving heuristics that are sensitive to both cost and makespan (ii) techniques for adjusting the heuristic estimates to take action interactions and metric resource limitations into account and (iii) a linear time greedy post-processing technique to improve execution flexibility of the solution plans. An implementation of SAPA using many of the techniques presented in this paper was one of the best domain independent planners for domains with metric and temporal constraints in the third International Planning Competition, held at AIPS-02. We describe the technical details of extracting the heuristics and present an empirical evaluation of the current implementation of SAPA.
Acquiring Correct Knowledge for Natural Language Generation
Venue: arXiv cs.CL 2011
Year: 2011

Natural language generation (NLG) systems are computer software systems that produce texts in English and other human languages, often from non-linguistic input data. NLG systems, like most AI systems, need substantial amounts of knowledge. However, our experience in two NLG projects suggests that it is difficult to acquire correct knowledge for NLG systems; indeed, every knowledge acquisition (KA) technique we tried had significant problems. In general terms, these problems were due to the complexity, novelty, and poorly understood nature of the tasks our systems attempted, and were worsened by the fact that people write so differently. This meant in particular that corpus-based KA approaches suffered because it was impossible to assemble a sizable corpus of high-quality consistent manually written texts in our domains; and structured expert-oriented KA techniques suffered because experts disagreed and because we could not get enough information about special and unusual cases to build robust systems. We believe that such problems are likely to affect many other NLG systems as well. In the long term, we hope that new KA techniques may emerge to help NLG system builders. In the shorter term, we believe that understanding how individual KA techniques can fail, and using a mixture of different KA techniques with different strengths and weaknesses, can help developers acquire NLG knowledge that is mostly correct.
TALplanner in IPC-2002: Extensions and Control Rules
Venue: arXiv cs.AI 2011
Year: 2011

TALplanner is a forward-chaining planner that relies on domain knowledge in the shape of temporal logic formulas in order to prune irrelevant parts of the search space. TALplanner recently participated in the third International Planning Competition, which had a clear emphasis on increasing the complexity of the problem domains being used as benchmark tests and the expressivity required to represent these domains in a planning system. Like many other planners, TALplanner had support for some but not all aspects of this increase in expressivity, and a number of changes to the planner were required. After a short introduction to TALplanner, this article describes some of the changes that were made before and during the competition. We also describe the process of introducing suitable domain knowledge for several of the competition domains.