OpenRaiser/Intern-Atlas huggingface dataset:
A Framework for a Multiagent-based Scheduling of Parallel Jobs
Venue: arXiv cs.DC 2015
Year: 2015

This paper presents a multiagent approach as a paradigm for scheduling parallel jobs in a parallel system. Scheduling parallel jobs is performed as a means to balance the load of a system in order to improve the performance of a parallel application. Parallel job scheduling is presented as a mapping between two graphs: one represents the dependency of jobs and the other represents the interconnection among processors. The usual implementation of parallel job scheduling algorithms is via the master-slave paradigm. The master-slave paradigm has inherent communication bottleneck that reduces the performance of the system when more processors are needed to process the jobs. The multiagent approach attempts to distribute the communication latency among the processors which improves the performance of the system as the number of participating processors increases. Presented in this paper is a framework for the behavior of an autonomous agent that cooperates with other agents to achieve a community goal of minimizing the processing time. Achieving this goal means an agent must truthfully share information with other agents via {\em normalization}, {\em task sharing}, and {\em result sharing} procedures. The agents consider a parallel scientific application as a finite-horizon game where truthful information sharing results into performance improvement for the parallel application. The performance of the multiagent-based algorithm is compared to that of an existing one via a simulation of the wavepacket dynamics using the quantum trajectory method (QTM) as a test application. The average parallel cost of running the QTM using the multiagent-based system is lower at higher number of processors.
Formation Control in Multi-Agent Systems Over Packet Dropping Links
Venue: arXiv cs.RO 2015
Year: 2015

One major challenge in implementation of formation control problems stems from the packet loss that occur in these shared communication channel. In the presence of packet loss the coordination information among agents is lost. Moreover, there is a move to use wireless channels in formation control applications. It has been found in practice that packet losses are more pronounced in wireless channels, than their wired counterparts. In our analysis, we first show that packet loss may result in loss of rigidity. In turn this causes the entire formation to fail. Later, we present an estimation based formation control algorithm that is robust to packet loss among agents. The proposed estimation algorithm employs minimal spanning tree algorithm to compute the estimate of the node variables (coordination variables). Consequently, this reduces the communication overhead required for information exchange. Later, using simulation, we verify the data that is to be transmitted for optimal estimation of these variables in the event of a packet loss. Finally, the effectiveness of the proposed algorithm is illustrated using suitable simulation example.
A Fully Controllable Power System - Concept for FACTS and HVDC Placement
Venue: arXiv cs.SY 2015
Year: 2015

This paper puts forward the vision of fully decoupling market operations from security considerations through controllable power flows. In "A Fully Controllable Power System", power system security is no longer dependent on the location of the power injection points. In the ideal case, this leads to the elimination of redispatching costs, which amount to several million dollars per year in large systems. This paper determines the upper and lower bounds for the number of controllable lines and number of controllers to achieve this decoupling in any system. It further introduces the notion of the controllability vector CV, which expresses the effect of any controller on the AC line flows. Based on two alternative definitions for controllability, two controller placement algorithms to maximize controllability are presented and their results are compared.
Greedy Is an Almost Optimal Deque
Venue: arXiv cs.DS 2015
Year: 2015

In this paper we extend the geometric binary search tree (BST) model of Demaine, Harmon, Iacono, Kane, and Patrascu (DHIKP) to accommodate for insertions and deletions. Within this extended model, we study the online Greedy BST algorithm introduced by DHIKP. Greedy BST is known to be equivalent to a maximally greedy (but inherently offline) algorithm introduced independently by Lucas in 1988 and Munro in 2000, conjectured to be dynamically optimal. With the application of forbidden-submatrix theory, we prove a quasilinear upper bound on the performance of Greedy BST on deque sequences. It has been conjectured (Tarjan, 1985) that splay trees (Sleator and Tarjan, 1983) can serve such sequences in linear time. Currently neither splay trees, nor other general-purpose BST algorithms are known to fulfill this requirement. As a special case, we show that Greedy BST can serve output-restricted deque sequences in linear time. A similar result is known for splay trees (Tarjan, 1985; Elmasry, 2004). As a further application of the insert-delete model, we give a simple proof that, given a set U of permutations of [n], the access cost of any BST algorithm is Omega(log |U| + n) on "most" of the permutations from U. In particular, this implies that the access cost for a random permutation of [n] is Omega(n log n) with high probability. Besides the splay tree noted before, Greedy BST has recently emerged as a plausible candidate for dynamic optimality. Compared to splay trees, much less effort has gone into analyzing Greedy BST. Our work is intended as a step towards a full understanding of Greedy BST, and we remark that forbidden-submatrix arguments seem particularly well suited for carrying out this program.
Distributed MAC Protocol Design for Full-Duplex Cognitive Radio Networks
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we consider the Medium Access Control (MAC) protocol design for full-duplex cognitive radio networks (FDCRNs). Our design exploits the fact that full-duplex (FD) secondary users (SUs) can perform spectrum sensing and access simultaneously, which enable them to detect the primary users' (PUs) activity during transmission. The developed FD MAC protocol employs the standard backoff mechanism as in the 802.11 MAC protocol. However, we propose to adopt the frame fragmentation during the data transmission phase for timely detection of active PUs where each data packet is divided into multiple fragments and the active SU makes sensing detection at the end of each data fragment. Then, we develop a mathematical model to analyze the throughput performance of the proposed FD MAC protocol. Furthermore, we propose an algorithm to configure the MAC protocol so that efficient self-interference management and sensing overhead control can be achieved. Finally, numerical results are presented to evaluate the performance of our design and demonstrate the throughput enhancement compared to the existing half-duplex (HD) cognitive MAC protocol.
A divisive spectral method for network community detection
Venue: arXiv cs.SI 2015
Year: 2015

Community detection is a fundamental problem in the domain of complex-network analysis. It has received great attention, and many community detection methods have been proposed in the last decade. In this paper, we propose a divisive spectral method for identifying community structures from networks, which utilizes a sparsification operation to pre-process the networks first, and then uses a repeated bisection spectral algorithm to partition the networks into communities. The sparsification operation makes the community boundaries more clearer and more sharper, so that the repeated spectral bisection algorithm extract high-quality community structures accurately from the sparsified networks. Experiments show that the combination of network sparsification and spectral bisection algorithm is highly successful, the proposed method is more effective in detecting community structures from networks than the others.
Comparison of Coverability and Multi-Scale Coverability in One and Two Dimensions
Venue: arXiv cs.DM 2015
Year: 2015

A word is quasiperiodic (or coverable) if it can be covered with occurrences of another finite word, called its quasiperiod. A word is multi-scale quasiperiodic (or multi-scale coverable) if it has infinitely many different quasiperiods. These notions were previously studied in the domains of text algorithms and combinatorics of right infinite words. We extend them to infinite pictures (two-dimensional words). Then we compare the regularity properties (uniform recurrence, uniform frequencies, topological entropy) of quasiperiodicity with multi-scale quasiperiodicity, and we also compare each of them with its one-dimensional counterpart. We also study which properties of quasiperiods enforce properties on the quasiperiodic words.
IV-matching is strongly NP-hard
Venue: arXiv cs.DM 2015
Year: 2015

IV-matching is a generalization of perfect bipartite matching. The complexity of finding IV-matching in a graph was posted as an open problem at the ICALP 2014 conference. In this note, we resolve the question and prove that, contrary to the expectations of the authors, the given problem is strongly NP-hard (already in the simplest non-trivial case of four layers). Hence it is unlikely that there would be an efficient (polynomial or pseudo-polynomial) algorithm solving the problem.
Bust-a-Move/Puzzle Bobble is NP-Complete
Venue: arXiv cs.CC 2015
Year: 2015

We prove that the classic 1994 Taito video game, known as Puzzle Bobble or Bust-a-Move, is NP-complete. Our proof applies to the perfect-information version where the bubble sequence is known in advance, and it uses just three bubble colors.
A New Approach to DDoS Defense using SDN and NFV
Venue: arXiv cs.NI 2015
Year: 2015

Networks today rely on expensive and proprietary hard- ware appliances, which are deployed at fixed locations, for DDoS defense. This introduces key limitations with respect to flexibility (e.g., complex routing to get traffic to these "chokepoints") and elasticity in handling changing attack patterns. We observe an opportunity to ad- dress these limitations using new networking paradigms such as software-defined networking (SDN) and network functions virtualization (NFV). Based on this observation, we design and implement of Bohatei, an elastic and flexible DDoS defense system. In designing Bohatei, we address key challenges of scalability, responsive- ness, and adversary-resilience. We have implemented defenses for several well-known DDoS attacks in Bohatei. Our evaluations show that Bohatei is scalable (handling 500 Gbps attacks), responsive (mitigating attacks within one minute), and resilient to dynamic adversaries.
Fast Computation of Abelian Runs
Venue: arXiv cs.DS 2015
Year: 2015

Given a word $w$ and a Parikh vector $\mathcal{P}$, an abelian run of period $\mathcal{P}$ in $w$ is a maximal occurrence of a substring of $w$ having abelian period $\mathcal{P}$. Our main result is an online algorithm that, given a word $w$ of length $n$ over an alphabet of cardinality $σ$ and a Parikh vector $\mathcal{P}$, returns all the abelian runs of period $\mathcal{P}$ in $w$ in time $O(n)$ and space $O(σ+p)$, where $p$ is the norm of $\mathcal{P}$, i.e., the sum of its components. We also present an online algorithm that computes all the abelian runs with periods of norm $p$ in $w$ in time $O(np)$, for any given norm $p$. Finally, we give an $O(n^2)$-time offline randomized algorithm for computing all the abelian runs of $w$. Its deterministic counterpart runs in $O(n^2\logσ)$ time.
Buffer overflow vulnerabilities in CUDA: a preliminary analysis
Venue: arXiv cs.CR 2015
Year: 2015

We present a preliminary study of buffer overflow vulnerabilities in CUDA software running on GPUs. We show how an attacker can overrun a buffer to corrupt sensitive data or steer the execution flow by overwriting function pointers, e.g., manipulating the virtual table of a C++ object. In view of a potential mass market diffusion of GPU accelerated software this may be a major concern.
Lightweight Asynchronous Snapshots for Distributed Dataflows
Venue: arXiv cs.DC 2015
Year: 2015

Distributed stateful stream processing enables the deployment and execution of large scale continuous computations in the cloud, targeting both low latency and high throughput. One of the most fundamental challenges of this paradigm is providing processing guarantees under potential failures. Existing approaches rely on periodic global state snapshots that can be used for failure recovery. Those approaches suffer from two main drawbacks. First, they often stall the overall computation which impacts ingestion. Second, they eagerly persist all records in transit along with the operation states which results in larger snapshots than required. In this work we propose Asynchronous Barrier Snapshotting (ABS), a lightweight algorithm suited for modern dataflow execution engines that minimises space requirements. ABS persists only operator states on acyclic execution topologies while keeping a minimal record log on cyclic dataflows. We implemented ABS on Apache Flink, a distributed analytics engine that supports stateful stream processing. Our evaluation shows that our algorithm does not have a heavy impact on the execution, maintaining linear scalability and performing well with frequent snapshots.
Human Shape Variation - An Efficient Implementation using Skeleton
Venue: arXiv cs.CV 2015
Year: 2015

It is at times important to detect human presence automatically in secure environments. This needs a shape recognition algorithm that is robust, fast and has low error rates. The algorithm needs to process camera images quickly to detect any human in the range of vision, and generate alerts, especially if the object under scrutiny is moving in certain directions. We present here a simple, efficient and fast algorithm using skeletons of the images, and simple features like posture and length of the object.
A Java Implementation of Parameter-less Evolutionary Algorithms
Venue: arXiv cs.MS 2015
Year: 2015

The Parameter-less Genetic Algorithm was first presented by Harik and Lobo in 1999 as an alternative to the usual trial-and-error method of finding, for each given problem, an acceptable set-up of the parameter values of the genetic algorithm. Since then, the same strategy has been successfully applied to create parameter-less versions of other population-based search algorithms such as the Extended Compact Genetic Algorithm and the Hierarchical Bayesian Optimization Algorithm. This report describes a Java implementation, Parameter-less Evolutionary Algorithm (P-EAJava), that integrates several parameter-less evolutionary algorithms into a single platform. Along with a brief description of P-EAJava, we also provide detailed instructions on how to use it, how to implement new problems, and how to generate new parameter-less versions of evolutionary algorithms. At present time, P-EAJava already includes parameter-less versions of the Simple Genetic Algorithm, the Extended Compact Genetic Algorithm, the Univariate Marginal Distribution Algorithm, and the Hierarchical Bayesian Optimization Algorithm. The source and binary files of the Java implementation of P-EAJava are available for free download at https://github.com/JoseCPereira/2015ParameterlessEvolutionaryAlgorithmsJava.
An automatic and efficient foreground object extraction scheme
Venue: arXiv cs.CV 2015
Year: 2015

This paper presents a method to differentiate the foreground objects from the background of a color image. Firstly a color image of any size is input for processing. The algorithm converts it to a grayscale image. Next we apply canny edge detector to find the boundary of the foreground object. We concentrate to find the maximum distance between each boundary pixel column wise and row wise and we fill the region that is bound by the edges. Thus we are able to extract the grayscale values of pixels that are in the bounded region and convert the grayscale image back to original color image containing only the foreground object.
Requirement Tracing using Term Extraction
Venue: arXiv cs.SE 2015
Year: 2015

Requirements traceability is an essential step in ensuring the quality of software during the early stages of its development life cycle. Requirements tracing usually consists of document parsing, candidate link generation and evaluation and traceability analysis. This paper demonstrates the applicability of Statistical Term Extraction metrics to generate candidate links. It is applied and validated using two data sets and four types of filters two for each data set, 0.2 and 0.25 for MODIS, 0 and 0.05 for CM1. This method generates requirements traceability matrices between textual requirements artifacts (such as high-level requirements traced to low-level requirements). The proposed method includes ten word frequency metrics divided into three main groups for calculating the frequency of terms. The results show that the proposed method gives better result when compared with the traditional TF-IDF method.
Java Implementation of a Parameter-less Evolutionary Portfolio
Venue: arXiv cs.MS 2015
Year: 2015

The Java implementation of a portfolio of parameter-less evolutionary algorithms is presented. The Parameter-less Evolutionary Portfolio implements a heuristic that performs adaptive selection of parameter-less evolutionary algorithms in accordance with performance criteria that are measured during running time. At present time, the portfolio includes three parameter-less evolutionary algorithms: Parameter-less Univariate Marginal Distribution Algorithm, Parameter-less Extended Compact Genetic Algorithm, and Parameter-less Hierarchical Bayesian Optimization Algorithm. Initial experiments showed that the parameter-less portfolio can solve various classes of problems without the need for any prior parameter setting technique and with an increase in computational effort that can be considered acceptable.
Characterization of Logic Program Revision as an Extension of Propositional Revision
Venue: arXiv cs.AI 2015
Year: 2015

We address the problem of belief revision of logic programs, i.e., how to incorporate to a logic program P a new logic program Q. Based on the structure of SE interpretations, Delgrande et al. adapted the well-known AGM framework to logic program (LP) revision. They identified the rational behavior of LP revision and introduced some specific operators. In this paper, a constructive characterization of all rational LP revision operators is given in terms of orderings over propositional interpretations with some further conditions specific to SE interpretations. It provides an intuitive, complete procedure for the construction of all rational LP revision operators and makes easier the comprehension of their semantic and computational properties. We give a particular consideration to logic programs of very general form, i.e., the generalized logic programs (GLPs). We show that every rational GLP revision operator is derived from a propositional revision operator satisfying the original AGM postulates. Interestingly, the further conditions specific to GLP revision are independent from the propositional revision operator on which a GLP revision operator is based. Taking advantage of our characterization result, we embed the GLP revision operators into structures of Boolean lattices, that allow us to bring to light some potential weaknesses in the adapted AGM postulates. To illustrate our claim, we introduce and characterize axiomatically two specific classes of (rational) GLP revision operators which arguably have a drastic behavior. We additionally consider two more restricted forms of logic programs, i.e., the disjunctive logic programs (DLPs) and the normal logic programs (NLPs) and adapt our characterization result to DLP and NLP revision operators.
On-Board Beam Generation for Multibeam Satellite Systems
Venue: arXiv cs.IT 2015
Year: 2015

This paper aims at designing an on-board beam generation process for multibeam satellite systems with the goal of reducing the traffic at the feeder link. Full frequency reuse among beams is considered and the beamforming at the satellite is designed for supporting interference mitigation techniques. In addition, in order to reduce the payload cost and complexity, this on-board processing is assumed to be constant and the same for forward and return link transmissions. To meet all these requirements a novel robust minimum mean square error (MMSE) optimization is conceived. The benefits of the considered scheme are evaluated with respect to the current approaches both analytically and numerically. Indeed, we show that with the DVB-RCS and DVB-S2 standards, our proposal allows to increase the total throughput within a range between 6\% and 15\% with respect to other on-board processing techniques in the return and forward link, respectively. Furthermore, the proposed solution presents an implicit feeder link bandwidth reduction with respect to the on-ground beam generation process.
Polynomial-time Construction of Optimal Tree-structured Communication Data Layout Descriptions
Venue: arXiv cs.DS 2015
Year: 2015

We show that the problem of constructing tree-structured descriptions of data layouts that are optimal with respect to space or other criteria from given sequences of displacements, can be solved in polynomial time. The problem is relevant for efficient compiler and library support for communication of noncontiguous data, where tree-structured descriptions with low-degree nodes and small index arrays are beneficial for the communication soft- and hardware. An important example is the Message-Passing Interface (MPI) which has a mechanism for describing arbitrary data layouts as trees using a set of increasingly general constructors. Our algorithm shows that the so-called MPI datatype reconstruction problem by trees with the full set of MPI constructors can be solved optimally in polynomial time, refuting previous conjectures that the problem is NP-hard. Our algorithm can handle further, natural constructors, currently not found in MPI. Our algorithm is based on dynamic programming, and requires the solution of a series of shortest path problems on an incrementally built, directed, acyclic graph. The algorithm runs in $O(n^4)$ time steps and requires $O(n^2)$ space for input displacement sequences of length $n$.
Aging display's effect on interpretation of digital pathology slides
Venue: arXiv cs.CV 2015
Year: 2015

It is our conjecture that the variability of colors in a pathology image effects the interpretation of pathology cases, whether it is diagnostic accuracy, diagnostic confidence, or workflow efficiency. In this paper, digital pathology images are analyzed to quantify the perceived difference in color that occurs due to display aging, in particular a change in the maximum luminance, white point, and color gamut. The digital pathology images studied include diagnostically important features, such as the conspicuity of nuclei. Three different display aging models are applied to images: aging of luminance & chrominance, aging of chrominance only, and a stabilized luminance & chrominance (i.e., no aging). These display models and images are then used to compare conspicuity of nuclei using CIE deltaE2000, a perceptual color difference metric. The effect of display aging using these display models and images is further analyzed through a human reader study designed to quantify the effects from a clinical perspective. Results from our reader study indicate significant impact of aged displays on workflow as well as diagnosis as follow. As compared to the originals (no-aging), slides with the effect of aging simulated were significantly more difficult to read (p-value of 0.0005) and took longer to score (p-value of 0.02). Moreover, luminance+chrominance aging significantly reduced inter-session percent agreement of diagnostic scores (p-value of 0.0418).