OpenRaiser/Intern-Atlas huggingface dataset:
Dynamic Scheduling of Skippable Periodic Tasks with Energy Efficiency in Weakly Hard Real-Time System
Venue: arXiv cs.OS 2010
Year: 2010

Energy consumption is a critical design issue in real-time systems, especially in battery- operated systems. Maintaining high performance, while extending the battery life between charges is an interesting challenge for system designers. Dynamic Voltage Scaling (DVS) allows a processor to dynamically change speed and voltage at run time, thereby saving energy by spreading run cycles into idle time. Knowing when to use full power and when not, requires the cooperation of the operating system scheduler. Usually, higher processor voltage and frequency leads to higher system throughput while energy reduction can be obtained using lower voltage and frequency. Instead of lowering processor voltage and frequency as much as possible, energy efficient real-time scheduling adjusts voltage and frequency according to some optimization criteria, such as low energy consumption or high throughput, while it meets the timing constraints of the real-time tasks. As the quantity and functional complexity of battery powered portable devices continues to raise, energy efficient design of such devices has become increasingly important. Many real-time scheduling algorithms have been developed recently to reduce energy consumption in the portable devices that use DVS capable processors. Three algorithms namely Red Tasks Only (RTO), Blue When Possible (BWP) and Red as Late as Possible (RLP) are proposed in the literature to schedule the real-time tasks in Weakly-hard real-time systems. This paper proposes optimal slack management algorithms to make the above existing weakly hard real-time scheduling algorithms energy efficient using DVS and DPD techniques.
Fast and Tiny Structural Self-Indexes for XML
Venue: arXiv cs.DB 2010
Year: 2010

XML document markup is highly repetitive and therefore well compressible using dictionary-based methods such as DAGs or grammars. In the context of selectivity estimation, grammar-compressed trees were used before as synopsis for structural XPath queries. Here a fully-fledged index over such grammars is presented. The index allows to execute arbitrary tree algorithms with a slow-down that is comparable to the space improvement. More interestingly, certain algorithms execute much faster over the index (because no decompression occurs). E.g., for structural XPath count queries, evaluating over the index is faster than previous XPath implementations, often by two orders of magnitude. The index also allows to serialize XML results (including texts) faster than previous systems, by a factor of ca. 2-3. This is due to efficient copy handling of grammar repetitions, and because materialization is totally avoided. In order to compare with twig join implementations, we implemented a materializer which writes out pre-order numbers of result nodes, and show its competitiveness.
Improvement of the Han-Kobayashi Rate Region for General Interference Channel-v2
Venue: arXiv cs.IT 2010
Year: 2010

Allowing the input auxiliary random variables to be correlated and using the binning scheme, the Han-Kobayashi (HK) rate region for general interference channel is partially improved. The obtained partially new achievable rate region (i) is compared to the HK region and its simplified description, i.e., Chong-Motani-Garg (CMG) region, in a detailed and favorable manner, by considering different versions of the regions, and (ii) has an interesting and easy interpretation: as expected, any rate in our region has generally two additional terms in comparison with the HK region (one due to the input correlation and the other as a result of the binning scheme). Keywords. Interference channel, Input correlation, Binning scheme
A New Noncoherent Decoder for Wireless Network Coding
Venue: arXiv cs.IT 2010
Year: 2010

This work deals with the decoding aspect of wireless network coding in the canonical two-way relay channel where two senders exchange messages via a common relay and they receive the mixture of two messages. One of the recent works on wireless network coding was well explained by Katti \textit{et al.} in SIGCOMM'07. In this work, we analyze the issue with one of their decoders when minimum-shift keying (MSK) is employed as the modulation format, and propose a new noncoherent decoder in the presence of two interfering signals.
Protection Over Asymmetric Channels, S-MATE: Secure Multipath Adaptive Traffic Engineering
Venue: arXiv cs.IT 2010
Year: 2010

Several approaches have been proposed to the problem of provisioning traffic engineering between core network nodes in Internet Service Provider (ISP) networks. Such approaches aim to minimize network delay, increase capacity, and enhance security services between two core (relay) network nodes, an ingress node and an egress node. MATE (Multipath Adaptive Traffic Engineering) has been proposed for multipath adaptive traffic engineering between an ingress node (source) and an egress node (destination) to distribute the network flow among multiple disjoint paths. Its novel idea is to avoid network congestion and attacks that might exist in edge and node disjoint paths between two core network nodes. This paper proposes protection schemes over asymmetric channels. Precisely, the paper aims to develop an adaptive, robust, and reliable traffic engineering scheme to improve performance and reliability of communication networks. This scheme will also provision Quality of Server (QoS) and protection of traffic engineering to maximize network efficiency. Specifically, S-MATE (secure MATE) is proposed to protect the network traffic between two core nodes (routers, switches, etc.) in a cloud network. S-MATE secures against a single link attack/failure by adding redundancy in one of the operational redundant paths between the sender and receiver nodes. It is also extended to secure against multiple attacked links. The proposed scheme can be applied to secure core networks such as optical and IP networks.
Probabilistic Dynamic Logic of Phenomena and Cognition
Venue: arXiv cs.LO 2010
Year: 2010

The purpose of this paper is to develop further the main concepts of Phenomena Dynamic Logic (P-DL) and Cognitive Dynamic Logic (C-DL), presented in the previous paper. The specific character of these logics is in matching vagueness or fuzziness of similarity measures to the uncertainty of models. These logics are based on the following fundamental notions: generality relation, uncertainty relation, simplicity relation, similarity maximization problem with empirical content and enhancement (learning) operator. We develop these notions in terms of logic and probability and developed a Probabilistic Dynamic Logic of Phenomena and Cognition (P-DL-PC) that relates to the scope of probabilistic models of brain. In our research the effectiveness of suggested formalization is demonstrated by approximation of the expert model of breast cancer diagnostic decisions. The P-DL-PC logic was previously successfully applied to solving many practical tasks and also for modelling of some cognitive processes.
Design of Transport Layer Based Hybrid Covert Channel Detection Engine
Venue: arXiv cs.CR 2010
Year: 2010

Computer network is unpredictable due to information warfare and is prone to various attacks. Such attacks on network compromise the most important attribute, the privacy. Most of such attacks are devised using special communication channel called "Covert Channel". The word "Covert" stands for hidden or non-transparent. Network Covert Channel is a concealed communication path within legitimate network communication that clearly violates security policies laid down. The non-transparency in covert channel is also referred to as trapdoor. A trapdoor is unintended design within legitimate communication whose motto is to leak information. Subliminal channel, a variant of covert channel works similarly except that the trapdoor is set in a cryptographic algorithm. A composition of covert channel with subliminal channel is the "Hybrid Covert Channel". Hybrid covert channel is homogenous or heterogeneous mixture of two or more variants of covert channels either active at same instance or at different instances of time. Detecting such malicious channel activity plays a vital role in removing threat to the legitimate network. In this paper, we present a study of multi-trapdoor covert channels and introduce design of a new detection engine for hybrid covert channel in transport layer visualized in TCP and SSL.
Intelligent Lighting System Using Wireless Sensor Networks
Venue: arXiv cs.NI 2010
Year: 2010

This paper examines the use of Wireless Sensor Networks interfaced with light fittings to allow for daylight substitution techniques to reduce energy usage in existing buildings. This creates a wire free system for existing buildings with minimal disruption and cost.
A Framework for Real-Time Face and Facial Feature Tracking using Optical Flow Pre-estimation and Template Tracking
Venue: arXiv cs.CV 2010
Year: 2010

This work presents a framework for tracking head movements and capturing the movements of the mouth and both the eyebrows in real-time. We present a head tracker which is a combination of a optical flow and a template based tracker. The estimation of the optical flow head tracker is used as starting point for the template tracker which fine-tunes the head estimation. This approach together with re-updating the optical flow points prevents the head tracker from drifting. This combination together with our switching scheme, makes our tracker very robust against fast movement and motion-blur. We also propose a way to reduce the influence of partial occlusion of the head. In both the optical flow and the template based tracker we identify and exclude occluded points.
Binary and nonbinary description of hypointensity in human brain MR images
Venue: arXiv cs.CV 2010
Year: 2010

Accumulating evidence has shown that iron is involved in the mechanism underlying many neurodegenerative diseases, such as Alzheimer's disease, Parkinson's disease and Huntington's disease. Abnormal (higher) iron accumulation has been detected in the brains of most neurodegenerative patients, especially in the basal ganglia region. Presence of iron leads to changes in MR signal in both magnitude and phase. Accordingly, tissues with high iron concentration appear hypo-intense (darker than usual) in MR contrasts. In this report, we proposed an improved binary hypointensity description and a novel nonbinary hypointensity description based on principle components analysis. Moreover, Kendall's rank correlation coefficient was used to compare the complementary and redundant information provided by the two methods in order to better understand the individual descriptions of iron accumulation in the brain.
Use of Python and Phoenix-M Interface in Robotics
Venue: arXiv cs.RO 2010
Year: 2010

In this paper I will show how to use Python programming with a computer interface such as Phoenix-M 1 to drive simple robots. In my quest towards Artificial Intelligence(AI) I am experimenting with a lot of different possibilities in Robotics. This one will try to mimic the working of a simple insect's nervous system using hard wiring and some minimal software usage. This is the precursor to my advanced robotics and AI integration where I plan to use a new paradigm of AI based on Machine Learning and Self Consciousness via Knowledge Feedback and Update Process.
An Adaptive and Multi-Service Routing Protocol for Wireless Sensor Networks
Venue: arXiv cs.NI 2010
Year: 2010

Wireless Sensor Networks (WSNs) are highly distributed networks consisting of a large number of tiny, low-cost, light-weight wireless nodes deployed to monitor an environment or a system. Each node in a WSN consists of three subsystems: the sensor subsystem which senses the environment, the processing subsystem which performs local computations on the sensed data, and the communication subsystem which is responsible for message exchange with neighboring sensor nodes. While an individual sensor node has limited sensing region, processing power, and energy, networking a large number of sensor nodes give rise to a robust, reliable, and accurate sensor network covering a wide region. Thus, routing in WSNs is a very important issue. This paper presents a query-based routing protocol for a WSN that provides different levels of Quality of Service (QoS): energy-efficiency, reliability, low latency and fault-tolerance-under different application scenarios. The algorithm has low computational complexity but can dynamically guarantee different QoS support depending on the requirement of the applications. The novelty of the proposed algorithm is its ability to provide multiple QoS support without reconfiguration and redeployment of the sensor nodes. The algorithm is implemented in network simulator ns-2 and its performance has been evaluated. The results show that the algorithm is more efficient than some of the currently existing routing algorithms for WSNs.
Chameleon: A Color-Adaptive Web Browser for Mobile OLED Displays
Venue: arXiv cs.GR 2010
Year: 2010

Displays based on organic light-emitting diode (OLED) technology are appearing on many mobile devices. Unlike liquid crystal displays (LCD), OLED displays consume dramatically different power for showing different colors. In particular, OLED displays are inefficient for showing bright colors. This has made them undesirable for mobile devices because much of the web content is of bright colors. To tackle this problem, we present the motivational studies, design, and realization of Chameleon, a color adaptive web browser that renders web pages with power-optimized color schemes under user-supplied constraints. Driven by the findings from our motivational studies, Chameleon provides end users with important options, offloads tasks that are not absolutely needed in real-time, and accomplishes real-time tasks by carefully enhancing the codebase of a browser engine. According to measure-ments with OLED smartphones, Chameleon is able to re-duce average system power consumption for web browsing by 41% and reduce display power consumption by 64% without introducing any noticeable delay.
Regularity of Position Sequences
Venue: arXiv cs.CV 2010
Year: 2010

A person is given a numbered sequence of positions on a sheet of paper. The person is asked, "Which will be the next (or the next after that) position?" Everyone has an opinion as to how he or she would proceed. There are regular sequences for which there is general agreement on how to continue. However, there are less regular sequences for which this assessment is less certain. There are sequences for which every continuation is perceived to be arbitrary. I would like to present a mathematical model that reflects these opinions and perceptions with the aid of a valuation function. It is necessary to apply a rich set of invariant features of position sequences to ensure the quality of this model. All other properties of the model are arbitrary.
On Universality in Real Computation
Venue: arXiv cs.CC 2010
Year: 2010

Models of computation operating over the real numbers and computing a larger class of functions compared to the class of general recursive functions invariably introduce a non-finite element of infinite information encoded in an arbitrary non-computable number or non-recursive function. In this paper we show that Turing universality is only possible at every Turing degree but not over all, in that sense universality at the first level is elegantly well defined while universality at higher degrees is at least ambiguous. We propose a concept of universal relativity and universal jump between levels in the arithmetical and analytical hierarchy.
Heterogeneous Strong Computation Migration
Venue: arXiv cs.DC 2010
Year: 2010

The continuous increase in performance requirements, for both scientific computation and industry, motivates the need of a powerful computing infrastructure. The Grid appeared as a solution for inexpensive execution of heavy applications in a parallel and distributed manner. It allows combining resources independently of their physical location and architecture to form a global resource pool available to all grid users. However, grid environments are highly unstable and unpredictable. Adaptability is a crucial issue in this context, in order to guarantee an appropriate quality of service to users. Migration is a technique frequently used for achieving adaptation. The objective of this report is to survey the problem of strong migration in heterogeneous environments like the grids', the related implementation issues and the current solutions.
A Coding Theoretic Study on MLL proof nets
Venue: arXiv cs.LO 2010
Year: 2010

Coding theory is very useful for real world applications. A notable example is digital television. Basically, coding theory is to study a way of detecting and/or correcting data that may be true or false. Moreover coding theory is an area of mathematics, in which there is an interplay between many branches of mathematics, e.g., abstract algebra, combinatorics, discrete geometry, information theory, etc. In this paper we propose a novel approach for analyzing proof nets of Multiplicative Linear Logic (MLL) by coding theory. We define families of proof structures and introduce a metric space for each family. In each family, 1. an MLL proof net is a true code element; 2. a proof structure that is not an MLL proof net is a false (or corrupted) code element. The definition of our metrics reflects the duality of the multiplicative connectives elegantly. In this paper we show that in the framework one error-detecting is possible but one error-correcting not. Our proof of the impossibility of one error-correcting is interesting in the sense that a proof theoretical property is proved using a graph theoretical argument. In addition, we show that affine logic and MLL + MIX are not appropriate for this framework. That explains why MLL is better than such similar logics.
A Bit-Compatible Shared Memory Parallelization for ILU(k) Preconditioning and a Bit-Compatible Generalization to Distributed Memory
Venue: arXiv cs.DC 2011
Year: 2011

ILU(k) is a commonly used preconditioner for iterative linear solvers for sparse, non-symmetric systems. It is often preferred for the sake of its stability. We present TPILU(k), the first efficiently parallelized ILU(k) preconditioner that maintains this important stability property. Even better, TPILU(k) preconditioning produces an answer that is bit-compatible with the sequential ILU(k) preconditioning. In terms of performance, the TPILU(k) preconditioning is shown to run faster whenever more cores are made available to it --- while continuing to be as stable as sequential ILU(k). This is in contrast to some competing methods that may become unstable if the degree of thread parallelism is raised too far. Where Block Jacobi ILU(k) fails in an application, it can be replaced by TPILU(k) in order to maintain good performance, while also achieving full stability. As a further optimization, TPILU(k) offers an optional level-based incomplete inverse method as a fast approximation for the original ILU(k) preconditioned matrix. Although this enhancement is not bit-compatible with classical ILU(k), it is bit-compatible with the output from the single-threaded version of the same algorithm. In experiments on a 16-core computer, the enhanced TPILU(k)-based iterative linear solver performed up to 9 times faster. As we approach an era of many-core computing, the ability to efficiently take advantage of many cores will become ever more important. TPILU(k) also demonstrates good performance on cluster or Grid. For example, the new algorithm achieves 50 times speedup with 80 nodes for general sparse matrices of dimension 160,000 that are diagonally dominant.
Efficiently Simulating Higher-Order Arithmetic by a First-Order Theory Modulo
Venue: arXiv cs.LO 2011
Year: 2011

In deduction modulo, a theory is not represented by a set of axioms but by a congruence on propositions modulo which the inference rules of standard deductive systems---such as for instance natural deduction---are applied. Therefore, the reasoning that is intrinsic of the theory does not appear in the length of proofs. In general, the congruence is defined through a rewrite system over terms and propositions. We define a rigorous framework to study proof lengths in deduction modulo, where the congruence must be computed in polynomial time. We show that even very simple rewrite systems lead to arbitrary proof-length speed-ups in deduction modulo, compared to using axioms. As higher-order logic can be encoded as a first-order theory in deduction modulo, we also study how to reinterpret, thanks to deduction modulo, the speed-ups between higher-order and first-order arithmetics that were stated by Gödel. We define a first-order rewrite system with a congruence decidable in polynomial time such that proofs of higher-order arithmetic can be linearly translated into first-order arithmetic modulo that system. We also present the whole higher-order arithmetic as a first-order system without resorting to any axiom, where proofs have the same length as in the axiomatic presentation.
On collinear sets in straight line drawings
Venue: arXiv cs.CG 2011
Year: 2011

We consider straight line drawings of a planar graph $G$ with possible edge crossings. The \emph{untangling problem} is to eliminate all edge crossings by moving as few vertices as possible to new positions. Let $fix(G)$ denote the maximum number of vertices that can be left fixed in the worst case. In the \emph{allocation problem}, we are given a planar graph $G$ on $n$ vertices together with an $n$-point set $X$ in the plane and have to draw $G$ without edge crossings so that as many vertices as possible are located in $X$. Let $fit(G)$ denote the maximum number of points fitting this purpose in the worst case. As $fix(G)\le fit(G)$, we are interested in upper bounds for the latter and lower bounds for the former parameter. For each $ε>0$, we construct an infinite sequence of graphs with $fit(G)=O(n^{σ+ε})$, where $σ<0.99$ is a known graph-theoretic constant, namely the shortness exponent for the class of cubic polyhedral graphs. To the best of our knowledge, this is the first example of graphs with $fit(G)=o(n)$. On the other hand, we prove that $fix(G)\ge\sqrt{n/30}$ for all $G$ with tree-width at most 2. This extends the lower bound obtained by Goaoc et al. [Discrete and Computational Geometry 42:542-569 (2009)] for outerplanar graphs. Our upper bound for $fit(G)$ is based on the fact that the constructed graphs can have only few collinear vertices in any crossing-free drawing. To prove the lower bound for $fix(G)$, we show that graphs of tree-width 2 admit drawings that have large sets of collinear vertices with some additional special properties.
Quadratic Forms and Space-Time Block Codes from Generalized Quaternion and Biquaternion Algebras
Venue: arXiv cs.IT 2011
Year: 2011

In the context of space-time block codes (STBCs), the theory of generalized quaternion and biquaternion algebras (i.e., tensor products of two quaternion algebras) over arbitrary base fields is presented, as well as quadratic form theoretic criteria to check if such algebras are division algebras. For base fields relevant to STBCs, these criteria are exploited, via Springer's theorem, to construct several explicit infinite families of (bi-)quaternion division algebras. These are used to obtain new $2\x 2$ and $4\x 4$ STBCs.
Greedy D-Approximation Algorithm for Covering with Arbitrary Constraints and Submodular Cost
Venue: arXiv cs.DS 2011
Year: 2011

This paper describes a simple greedy D-approximation algorithm for any covering problem whose objective function is submodular and non-decreasing, and whose feasible region can be expressed as the intersection of arbitrary (closed upwards) covering constraints, each of which constrains at most D variables of the problem. (A simple example is Vertex Cover, with D = 2.) The algorithm generalizes previous approximation algorithms for fundamental covering problems and online paging and caching problems.