OpenRaiser/Intern-Atlas huggingface dataset:
Rate Compatible Protocol for Information Reconciliation: An application to QKD
Venue: arXiv cs.IT 2010
Year: 2010

Information Reconciliation is a mechanism that allows to weed out the discrepancies between two correlated variables. It is an essential component in every key agreement protocol where the key has to be transmitted through a noisy channel. The typical case is in the satellite scenario described by Maurer in the early 90's. Recently the need has arisen in relation with Quantum Key Distribution (QKD) protocols, where it is very important not to reveal unnecessary information in order to maximize the shared key length. In this paper we present an information reconciliation protocol based on a rate compatible construction of Low Density Parity Check codes. Our protocol improves the efficiency of the reconciliation for the whole range of error rates in the discrete variable QKD context. Its adaptability together with its low interactivity makes it specially well suited for QKD reconciliation.
A Markov Chain Model for the Analysis of Round-Robin Scheduling Scheme
Venue: arXiv cs.NI 2010
Year: 2010

In the literature of Round-Robin scheduling scheme, each job is processed, one after the another after giving a fix quantum. In case of First-come first-served, each process is executed, if the previously arrived processed is completed. Both these scheduling schemes are used in this paper as its special cases. A Markov chain model is used to compare several scheduling schemes of the class. An index measure is defined to compare the model based efficiency of different scheduling schemes. One scheduling scheme which is the mixture of FIFO and round robin is found efficient in terms of model based study. The system simulation procedure is used to derive the conclusion of the content
Eigen-Based Transceivers for the MIMO Broadcast Channel with Semi-Orthogonal User Selection
Venue: arXiv cs.IT 2010
Year: 2010

This paper studies the sum rate performance of two low complexity eigenmode-based transmission techniques for the MIMO broadcast channel, employing greedy semi-orthogonal user selection (SUS). The first approach, termed ZFDPC-SUS, is based on zero-forcing dirty paper coding; the second approach, termed ZFBF-SUS, is based on zero-forcing beamforming. We first employ new analytical methods to prove that as the number of users K grows large, the ZFDPC-SUS approach can achieve the optimal sum rate scaling of the MIMO broadcast channel. We also prove that the average sum rates of both techniques converge to the average sum capacity of the MIMO broadcast channel for large K. In addition to the asymptotic analysis, we investigate the sum rates achieved by ZFDPC-SUS and ZFBF-SUS for finite K, and show that ZFDPC-SUS has significant performance advantages. Our results also provide key insights into the benefit of multiple receive antennas, and the effect of the SUS algorithm. In particular, we show that whilst multiple receive antennas only improves the asymptotic sum rate scaling via the second-order behavior of the multi-user diversity gain; for finite K, the benefit can be very significant. We also show the interesting result that the semi-orthogonality constraint imposed by SUS, whilst facilitating a very low complexity user selection procedure, asymptotically does not reduce the multi-user diversity gain in either first (log K) or second-order (loglog K) terms.
Achievable Rate Regions for Discrete Memoryless Interference Channel with State Information
Venue: arXiv cs.IT 2010
Year: 2010

In this paper, we study the state-dependent two-user interference channel, where the state information is non-causally known at both transmitters but unknown to either of the receivers. We propose two coding schemes for the discrete memoryless case: simultaneous encoding for the sub-messages in the first one and superposition encoding in the second one, both with rate splitting and Gel'fand-Pinsker coding. The corresponding achievable rate regions are established.
Performance Analysis of QoS in PMP Mode WiMax Networks
Venue: arXiv cs.NI 2010
Year: 2010

IEEE 802.16 standard supports two different topologies: point to multipoint (PMP) and Mesh. In this paper, a QoS mechanism for point to multipoint of IEEE 802.16 and BS scheduler for PMP Mode is proposed. This paper also describes quality of service over WiMAX networks. Average WiMAX delay, Average WiMAX load and Average WiMAX throughput at base station is analyzed and compared by applying different scheduler at Base station and at fixed nodes.
Fuzzy Modeling and Natural Language Processing for Panini's Sanskrit Grammar
Venue: arXiv cs.CL 2010
Year: 2010

Indian languages have long history in World Natural languages. Panini was the first to define Grammar for Sanskrit language with about 4000 rules in fifth century. These rules contain uncertainty information. It is not possible to Computer processing of Sanskrit language with uncertain information. In this paper, fuzzy logic and fuzzy reasoning are proposed to deal to eliminate uncertain information for reasoning with Sanskrit grammar. The Sanskrit language processing is also discussed in this paper.
The entropy per coordinate of a random vector is highly constrained under convexity conditions
Venue: arXiv cs.IT 2010
Year: 2010

The entropy per coordinate in a log-concave random vector of any dimension with given density at the mode is shown to have a range of just 1. Uniform distributions on convex bodies are at the lower end of this range, the distribution with i.i.d. exponentially distributed coordinates is at the upper end, and the normal is exactly in the middle. Thus in terms of the amount of randomness as measured by entropy per coordinate, any log-concave random vector of any dimension contains randomness that differs from that in the normal random variable with the same maximal density value by at most 1/2. As applications, we obtain an information-theoretic formulation of the famous hyperplane conjecture in convex geometry, entropy bounds for certain infinitely divisible distributions, and quantitative estimates for the behavior of the density at the mode on convolution. More generally, one may consider so-called convex or hyperbolic probability measures on Euclidean spaces; we give new constraints on entropy per coordinate for this class of measures, which generalize our results under the log-concavity assumption, expose the extremal role of multivariate Pareto-type distributions, and give some applications.
A hands-on Assessment of Transport Protocols with Lower than Best Effort Priority
Venue: arXiv cs.NI 2010
Year: 2010

Last year, the official BitTorrent client switched to LEDBAT, a new congestion control algorithm targeting a lower-than Best Effort transport service. In this paper, we study this new protocol through packet-level simulations, with a special focus on a performance comparison with other lower-than Best Effort protocols such as TCP-LP and TCP-NICE: our aim is indeed to quantify and relatively weight the level of Low-priority provided by such protocols. Our results show that LEDBAT transport generally achieves the lowest possible level of priority, with the default configurations of TCP-NICE and TCP-LP representing increasing levels of aggressiveness. In addition, we perform a careful sensitivity analysis of LEDBAT performance, by tuning its main parameters in both inter-protocol (against TCP) and intra-protocol (against LEDBAT itself) scenarios. In the inter-protocol case, although in case of misconfiguration LEDBAT competes as aggressively as TCP, however we show that it is not possible to achieve an arbitrary level of low-priority by merely tuning its parameters. In the intra-protocol case, we show that coexistence of legacy flows with slightly dissimilar settings, or experiencing different network conditions, can result in significant unfairness.
Satisfiability Thresholds for k-CNF Formula with Bounded Variable Intersections
Venue: arXiv cs.DM 2010
Year: 2010

We determine the thresholds for the number of variables, number of clauses, number of clause intersection pairs and the maximum clause degree of a k-CNF formula that guarantees satisfiability under the assumption that every two clauses share at most $α$ variables. More formally, we call these formulas $α$-intersecting and define, for example, a threshold $μ_i(k,α)$ for the number of clause intersection pairs $i$, such that every $α$-intersecting k-CNF formula in which at most $μ_i(k,α)$ pairs of clauses share a variable is satisfiable and there exists an unsatisfiable $α$-intersecting k-CNF formula with $μ_m(k,α)$ such intersections. We provide a lower bound for these thresholds based on the Lovasz Local Lemma and a nearly matching upper bound by constructing an unsatisfiable k-CNF to show that $μ_i(k,α) = \tildeΘ(2^{k(2+1/α)})$. Similar thresholds are determined for the number of variables ($μ_n = \tildeΘ(2^{k/α})$) and the number of clauses ($μ_m = \tildeΘ(2^{k(1+\frac{1}α)})$) (see [Scheder08] for an earlier but independent report on this threshold). Our upper bound construction gives a family of unsatisfiable formula that achieve all four thresholds simultaneously.
Extension of Wirtinger's Calculus to Reproducing Kernel Hilbert Spaces and the Complex Kernel LMS
Venue: arXiv cs.LG 2010
Year: 2010

Over the last decade, kernel methods for nonlinear processing have successfully been used in the machine learning community. The primary mathematical tool employed in these methods is the notion of the Reproducing Kernel Hilbert Space. However, so far, the emphasis has been on batch techniques. It is only recently, that online techniques have been considered in the context of adaptive signal processing tasks. Moreover, these efforts have only been focussed on real valued data sequences. To the best of our knowledge, no adaptive kernel-based strategy has been developed, so far, for complex valued signals. Furthermore, although the real reproducing kernels are used in an increasing number of machine learning problems, complex kernels have not, yet, been used, in spite of their potential interest in applications that deal with complex signals, with Communications being a typical example. In this paper, we present a general framework to attack the problem of adaptive filtering of complex signals, using either real reproducing kernels, taking advantage of a technique called \textit{complexification} of real RKHSs, or complex reproducing kernels, highlighting the use of the complex gaussian kernel. In order to derive gradients of operators that need to be defined on the associated complex RKHSs, we employ the powerful tool of Wirtinger's Calculus, which has recently attracted attention in the signal processing community. To this end, in this paper, the notion of Wirtinger's calculus is extended, for the first time, to include complex RKHSs and use it to derive several realizations of the Complex Kernel Least-Mean-Square (CKLMS) algorithm. Experiments verify that the CKLMS offers significant performance improvements over several linear and nonlinear algorithms, when dealing with nonlinearities.
Classical and Intuitionistic Subexponential Logics are Equally Expressive
Venue: arXiv cs.LO 2010
Year: 2010

It is standard to regard the intuitionistic restriction of a classical logic as increasing the expressivity of the logic because the classical logic can be adequately represented in the intuitionistic logic by double-negation, while the other direction has no truth-preserving propositional encodings. We show here that subexponential logic, which is a family of substructural refinements of classical logic, each parametric over a preorder over the subexponential connectives, does not suffer from this asymmetry if the preorder is systematically modified as part of the encoding. Precisely, we show a bijection between synthetic (i.e., focused) partial sequent derivations modulo a given encoding. Particular instances of our encoding for particular subexponential preorders give rise to both known and novel adequacy theorems for substructural logics.
Abstract Fixpoint Computations with Numerical Acceleration Methods
Venue: arXiv cs.PL 2010
Year: 2010

Static analysis by abstract interpretation aims at automatically proving properties of computer programs. To do this, an over-approximation of program semantics, defined as the least fixpoint of a system of semantic equations, must be computed. To enforce the convergence of this computation, widening operator is used but it may lead to coarse results. We propose a new method to accelerate the computation of this fixpoint by using standard techniques of numerical analysis. Our goal is to automatically and dynamically adapt the widening operator in order to maintain precision.
H2O: An Autonomic, Resource-Aware Distributed Database System
Venue: arXiv cs.DB 2010
Year: 2010

This paper presents the design of an autonomic, resource-aware distributed database which enables data to be backed up and shared without complex manual administration. The database, H2O, is designed to make use of unused resources on workstation machines. Creating and maintaining highly-available, replicated database systems can be difficult for untrained users, and costly for IT departments. H2O reduces the need for manual administration by autonomically replicating data and load-balancing across machines in an enterprise. Provisioning hardware to run a database system can be unnecessarily costly as most organizations already possess large quantities of idle resources in workstation machines. H2O is designed to utilize this unused capacity by using resource availability information to place data and plan queries over workstation machines that are already being used for other tasks. This paper discusses the requirements for such a system and presents the design and implementation of H2O.
Optimal whitespace synchronization strategies
Venue: arXiv cs.GT 2010
Year: 2010

The whitespace-discovery problem describes two parties, Alice and Bob, trying to establish a communication channel over one of a given large segment of whitespace channels. Subsets of the channels are occupied in each of the local environments surrounding Alice and Bob, as well as in the global environment between them (Eve). In the absence of a common clock for the two parties, the goal is to devise time-invariant (stationary) strategies minimizing the synchronization time. This emerged from recent applications in discovery of wireless devices. We model the problem as follows. There are $N$ channels, each of which is open (unoccupied) with probability $p_1,p_2,q$ independently for Alice, Bob and Eve respectively. Further assume that $N \gg 1/(p_1 p_2 q)$ to allow for sufficiently many open channels. Both Alice and Bob can detect which channels are locally open and every time-slot each of them chooses one such channel for an attempted sync. One aims for strategies that, with high probability over the environments, guarantee a shortest possible expected sync time depending only on the $p_i$'s and $q$. Here we provide a stationary strategy for Alice and Bob with a guaranteed expected sync time of $O(1 / (p_1 p_2 q^2))$ given that each party also has knowledge of $p_1,p_2,q$. When the parties are oblivious of these probabilities, analogous strategies incur a cost of a poly-log factor, i.e.\ $\tilde{O}(1 / (p_1 p_2 q^2))$. Furthermore, this performance guarantee is essentially optimal as we show that any stationary strategies of Alice and Bob have an expected sync time of at least $Ω(1/(p_1 p_2 q^2))$.
An External Description for MIMO Systems Sampled in an Aperiodic Way
Venue: arXiv cs.DM 2010
Year: 2010

An external description for aperiodically sampled MIMO linear systems has been developed. Emphasis is on the sampling period sequence, included among the variables to be handled. The computational procedure is simple and no use of polynomial matrix theory is required. This input/output description is believed to be a basic formulation for its later application to the problem of optimal control and/or identification of linear dynamical systems.
Nested Polar Codes for Wiretap and Relay Channels
Venue: arXiv cs.IT 2010
Year: 2010

We show that polar codes asymptotically achieve the whole capacity-equivocation region for the wiretap channel when the wiretapper's channel is degraded with respect to the main channel, and the weak secrecy notion is used. Our coding scheme also achieves the capacity of the physically degraded receiver-orthogonal relay channel. We show simulation results for moderate block length for the binary erasure wiretap channel, comparing polar codes and two edge type LDPC codes.
Detecting Anomalous Process Behaviour using Second Generation Artificial Immune Systems
Venue: arXiv cs.AI 2010
Year: 2010

Artificial Immune Systems have been successfully applied to a number of problem domains including fault tolerance and data mining, but have been shown to scale poorly when applied to computer intrusion detec- tion despite the fact that the biological immune system is a very effective anomaly detector. This may be because AIS algorithms have previously been based on the adaptive immune system and biologically-naive mod- els. This paper focuses on describing and testing a more complex and biologically-authentic AIS model, inspired by the interactions between the innate and adaptive immune systems. Its performance on a realistic process anomaly detection problem is shown to be better than standard AIS methods (negative-selection), policy-based anomaly detection methods (systrace), and an alternative innate AIS approach (the DCA). In addition, it is shown that runtime information can be used in combination with system call information to enhance detection capability.
Near-Optimal Deviation-Proof Medium Access Control Designs in Wireless Networks
Venue: arXiv cs.NI 2010
Year: 2010

Distributed medium access control (MAC) protocols are essential for the proliferation of low cost, decentralized wireless local area networks (WLANs). Most MAC protocols are designed with the presumption that nodes comply with prescribed rules. However, selfish nodes have natural motives to manipulate protocols in order to improve their own performance. This often degrades the performance of other nodes as well as that of the overall system. In this work, we propose a class of protocols that limit the performance gain which nodes can obtain through selfish manipulation while incurring only a small efficiency loss. The proposed protocols are based on the idea of a review strategy, with which nodes collect signals about the actions of other nodes over a period of time, use a statistical test to infer whether or not other nodes are following the prescribed protocol, and trigger a punishment if a departure from the protocol is perceived. We consider the cases of private and public signals and provide analytical and numerical results to demonstrate the properties of the proposed protocols.
Dynamic Range Reporting in External Memory
Venue: arXiv cs.DS 2010
Year: 2010

In this paper we describe a dynamic external memory data structure that supports range reporting queries in three dimensions in $O(\log_B^2 N + \frac{k}{B})$ I/O operations, where $k$ is the number of points in the answer and $B$ is the block size. This is the first dynamic data structure that answers three-dimensional range reporting queries in $\log_B^{O(1)} N + O(\frac{k}{B})$ I/Os.
Sustainable Throughput of Wireless LANs with Multi-Packet Reception Capability under Bounded Delay-Moment Requirements
Venue: arXiv cs.NI 2010
Year: 2010

With the rapid proliferation of broadband wireless services, it is of paramount importance to understand how fast data can be sent through a wireless local area network (WLAN). Thanks to a large body of research following the seminal work of Bianchi, WLAN throughput under saturated traffic condition has been well understood. By contrast, prior investigations on throughput performance under unsaturated traffic condition was largely based on phenomenological observations, which lead to a common misconception that WLAN can support a traffic load as high as saturation throughput, if not higher, under non-saturation condition. In this paper, we show through rigorous analysis that this misconception may result in unacceptable quality of service: mean packet delay and delay jitter may approach infinity even when the traffic load is far below the saturation throughput. Hence, saturation throughput is not a sound measure of WLAN capacity under non-saturation condition. To bridge the gap, we define safe-bounded-mean-delay (SBMD) throughput and safe-bounded-delay-jitter (SBDJ) throughput that reflect the actual network capacity users can enjoy when they require finite mean delay and delay jitter, respectively. Our earlier work proved that in a WLAN with multi-packet reception (MPR) capability, saturation throughput scales super-linearly with the MPR capability of the network. This paper extends the investigation to the non-saturation case and shows that super-linear scaling also holds for SBMD and SBDJ throughputs. Our results here complete the demonstration of MPR as a powerful capacity-enhancement technique for WLAN under both saturation and non-saturation conditions.
A note on the stability of multiclass Markovian queueing networks
Venue: arXiv cs.NI 2010
Year: 2010

In this paper we show that in a multiclass Markovian network with unit rate servers, the condition that the average load $ρ$ at every server is less than unity is indeed sufficient for the stability or positive recurrence for \emph{any} work conserving scheduling policy and \emph{class-independent} routing. We use a variation of the positive recurrence criterion for multidimensional discrete-time Markov chains over countable state spaces due to Rosberg (JAP, Vol.~17, No.~3, 1980) and a monotonicity argument to establish this assertion.
Analysis of Microprocessor Based Protective Re-lay's (MBPR) Differential Equation Algorithms
Venue: arXiv cs.OH 2010
Year: 2010

This paper analyses and explains from the systems point of view, microprocessor based protective relay (MBPR) systems with emphasis on differential equation algorithms. Presently, the application of protective relaying in power systems, using MBPR systems, based on the differential equation algorithm is valued more than the protection relaying based on any other type of algorithm, because of advantages in accuracy and implementation. MBPR differential equation approach can tolerate some errors caused by power system abnormality such as DC offset. This paper shows that the algorithm is a system description based and it is immune from distortions such as DC-offset. Differential equation algorithms implemented in MBPR are widely used in the protection of transmission and distribution lines, transformers, buses, motors, etc. The parameters from the system, utilized in these algorithms, are obtained from the power system current i(t) or voltage v(t), which are abnormal values under fault or distortion situations. So, an error study for the algorithm is considered necessary.
Interactive Reconciliation with Low-Density Parity-Check Codes
Venue: arXiv cs.IT 2010
Year: 2010

Efficient information reconciliation is crucial in several scenarios, being quantum key distribution a remarkable example. However, efficiency is not the only requirement for determining the quality of the information reconciliation process. In some of these scenarios we find other relevant parameters such as the interactivity or the adaptability to different channel statistics. We propose an interactive protocol for information reconciliation based on low-density parity-check codes. The coding rate is adapted in real time by using simultaneously puncturing and shortening strategies, allowing it to cover a predefined error rate range with just a single code. The efficiency of the information reconciliation process using the proposed protocol is considerably better than the efficiency of its non-interactive version.