OpenRaiser/Intern-Atlas huggingface dataset:
Interference and Deployment Issues for Cognitive Radio Systems in Shadowing Environments
Venue: arXiv cs.IT 2009
Year: 2009

In this paper we describe a model for calculating the aggregate interference encountered by primary receivers in the presence of randomly placed cognitive radios (CRs). We show that incorporating the impact of distance attenuation and lognormal fading on each constituent interferer in the aggregate, leads to a composite interference that cannot be satisfactorily modeled by a lognormal. Using the interference statistics we determine a number of key parameters needed for the deployment of CRs. Examples of these are the exclusion zone radius, needed to protect the primary receiver under different types of fading environments and acceptable interference levels, and the numbers of CRs that can be deployed. We further show that if the CRs have apriori knowledge of the radio environment map (REM), then a much larger number of CRs can be deployed especially in a high density environment. Given REM information, we also look at the CR numbers achieved by two different types of techniques to process the scheduling information.
Swarming Overlay Construction Strategies
Venue: arXiv cs.NI 2009
Year: 2009

Swarming peer-to-peer systems play an increasingly instrumental role in Internet content distribution. It is therefore important to better understand how these systems behave in practice. Recent research efforts have looked at various protocol parameters and have measured how they affect system performance and robustness. However, the importance of the strategy based on which peers establish connections has been largely overlooked. This work utilizes extensive simulations to examine the default overlay construction strategy in BitTorrent systems. Based on the results, we identify a critical parameter, the maximum allowable number of outgoing connections at each peer, and evaluate its impact on the robustness of the generated overlay. We find that there is no single optimal value for this parameter using the default strategy. We then propose an alternative strategy that allows certain new peer connection requests to replace existing connections. Further experiments with the new strategy demonstrate that it outperforms the default one for all considered metrics by creating an overlay more robust to churn. Additionally, our proposed strategy exhibits optimal behavior for a well-defined value of the maximum number of outgoing connections, thereby removing the need to set this parameter in an ad-hoc manner.
Kolkata Paise Restaurant Problem in Some Uniform Learning Strategy Limits
Venue: arXiv cs.GT 2009
Year: 2009

We study the dynamics of some uniform learning strategy limits or a probabilistic version of the "Kolkata Paise Restaurant" problem, where N agents choose among N equally priced but differently ranked restaurants every evening such that each agent can get dinner in the best possible ranked restaurant (each serving only one customer and the rest arriving there going without dinner that evening). We consider the learning to be uniform among the agents and assume that each follow the same probabilistic strategy dependent on the information of the past successes in the game. The numerical results for utilization of the restaurants in some limiting cases are analytically examined.
Empirical study of software quality evolution in open source projects using agile practices
Venue: arXiv cs.SE 2009
Year: 2009

We analyse the time evolution of two open source Java projects: Eclipse and Netbeans, both developed following agile practices, though to a different extent. Our study is centered on quality analysis of the systems, measured as defects absence, and its relation with software metrics evolution. The two projects are described through a software graph in which nodes are represented by Java files and edges describe the existing relation between nodes. We propose a metrics suite for Java files based on Chidamber and Kemerer suite, and use it to study software evolution and its relationship with bug count.
False name manipulations in weighted voting games: splitting, merging and annexation
Venue: arXiv cs.GT 2009
Year: 2009

An important aspect of mechanism design in social choice protocols and multiagent systems is to discourage insincere and manipulative behaviour. We examine the computational complexity of false-name manipulation in weighted voting games which are an important class of coalitional voting games. Weighted voting games have received increased interest in the multiagent community due to their compact representation and ability to model coalitional formation scenarios. Bachrach and Elkind in their AAMAS 2008 paper examined divide and conquer false-name manipulation in weighted voting games from the point of view of Shapley-Shubik index. We analyse the corresponding case of the Banzhaf index and check how much the Banzhaf index of a player increases or decreases if it splits up into sub-players. A pseudo-polynomial algorithm to find the optimal split is also provided. Bachrach and Elkind also mentioned manipulation via merging as an open problem. In the paper, we examine the cases where a player annexes other players or merges with them to increase their Banzhaf index or Shapley-Shubik index payoff. We characterize the computational complexity of such manipulations and provide limits to the manipulation. The annexation non-monotonicity paradox is also discovered in the case of the Banzhaf index. The results give insight into coalition formation and manipulation.
A Type System for Parallel Components
Venue: arXiv cs.PL 2009
Year: 2009

The # component model was proposed to improve the practice of parallel programming. This paper introduces a type system for # programming systems, aiming to lift the abstraction and safety of programming for parallel computing architectures by introducing a notion of abstract component based on universal and existential bounded quantification. Issues about the implementation of such type system in HPE, a # programming system, are also discussed.
Gradient Clock Synchronization using Reference Broadcasts
Venue: arXiv cs.DC 2009
Year: 2009

In this paper we suggest a method by which reference broadcast synchronization (RBS), and other methods of estimating clock values, can be incorporated in standard clock synchronization algorithms to improve synchronization quality. We advocate a logical separation of the task of estimating the clock values of other nodes in the network from the task of using these estimates to output a logical clock value. The separation is achieved by means of a virtual estimate graph, overlaid on top of the real network graph, which represents the information various nodes can obtain about each other. RBS estimates are represented in the estimate graph as edges between nodes at distance 2 from each other in the original network graph. A clock synchronization algorithm then operates on the estimate graph as though it were the original network. To illustrate the merits of this approach, we modify a recent optimal gradient clock synchronization algorithm to work in this setting. The modified algorithm transparently takes advantage of RBS estimates and any other means by which nodes can estimate each others' clock values.
A semantical approach to equilibria and rationality
Venue: arXiv cs.GT 2009
Year: 2009

Game theoretic equilibria are mathematical expressions of rationality. Rational agents are used to model not only humans and their software representatives, but also organisms, populations, species and genes, interacting with each other and with the environment. Rational behaviors are achieved not only through conscious reasoning, but also through spontaneous stabilization at equilibrium points. Formal theories of rationality are usually guided by informal intuitions, which are acquired by observing some concrete economic, biological, or network processes. Treating such processes as instances of computation, we reconstruct and refine some basic notions of equilibrium and rationality from the some basic structures of computation. It is, of course, well known that equilibria arise as fixed points; the point is that semantics of computation of fixed points seems to be providing novel methods, algebraic and coalgebraic, for reasoning about them.
Multiset Ordering Constraints
Venue: arXiv cs.AI 2009
Year: 2009

We identify a new and important global (or non-binary) constraint. This constraint ensures that the values taken by two vectors of variables, when viewed as multisets, are ordered. This constraint is useful for a number of different applications including breaking symmetry and fuzzy constraint satisfaction. We propose and implement an efficient linear time algorithm for enforcing generalised arc consistency on such a multiset ordering constraint. Experimental results on several problem domains show considerable promise.
Optimal byzantine resilient convergence in oblivious robot networks
Venue: arXiv cs.DC 2009
Year: 2009

Given a set of robots with arbitrary initial location and no agreement on a global coordinate system, convergence requires that all robots asymptotically approach the exact same, but unknown beforehand, location. Robots are oblivious-- they do not recall the past computations -- and are allowed to move in a one-dimensional space. Additionally, robots cannot communicate directly, instead they obtain system related information only via visual sensors. We draw a connection between the convergence problem in robot networks, and the distributed \emph{approximate agreement} problem (that requires correct processes to decide, for some constant $ε$, values distance $ε$ apart and within the range of initial proposed values). Surprisingly, even though specifications are similar, the convergence implementation in robot networks requires specific assumptions about synchrony and Byzantine resilience. In more details, we prove necessary and sufficient conditions for the convergence of mobile robots despite a subset of them being Byzantine (i.e. they can exhibit arbitrary behavior). Additionally, we propose a deterministic convergence algorithm for robot networks and analyze its correctness and complexity in various synchrony settings. The proposed algorithm tolerates f Byzantine robots for (2f+1)-sized robot networks in fully synchronous networks, (3f+1)-sized in semi-synchronous networks. These bounds are optimal for the class of cautious algorithms, which guarantee that correct robots always move inside the range of positions of the correct robots.
A Physical Model of Wireless Network
Venue: arXiv cs.NI 2009
Year: 2009

Using an approach developed in physics, we propose a new framework for the study of cellular networks. The key idea of the physical network model we propose is to replace the discrete base stations (BS) entities by a continuum of transmitters which are spatially distributed in the network. This allows us to establish a closed form formula of the other-cell downlink interference factor f, as a function of the location of the mobile. We define here f as the ratio of outer cell received power (i.e. the power received from other cells) to the inner cell received power. This physical model allows calculating the influence of interference on any mobile in a cell, whatever its position. Results obtained with that closed-form formula are close to the ones obtained by simulations using a traditional hexagonal network model. Since the physical model allows to establish a closed form formula of the interference factor, it allows to do analytical studies of wireless networks such as outage probability, quality of service, capacity.
Contraction-free proofs and finitary games for Linear Logic
Venue: arXiv cs.LO 2009
Year: 2009

In the standard sequent presentations of Girard's Linear Logic (LL), there are two "non-decreasing" rules, where the premises are not smaller than the conclusion, namely the cut and the contraction rules. It is a universal concern to eliminate the cut rule. We show that, using an admissible modification of the tensor rule, contractions can be eliminated, and that cuts can be simultaneously limited to a single initial occurrence. This view leads to a consistent, but incomplete game model for LL with exponentials, which is finitary, in the sense that each play is finite. The game is based on a set of inference rules which does not enjoy cut elimination. Nevertheless, the cut rule is valid in the model.
Orthomodular lattices, Foulis Semigroups and Dagger Kernel Categories
Venue: arXiv cs.LO 2009
Year: 2009

This paper is a sequel to arXiv:0902.2355 and continues the study of quantum logic via dagger kernel categories. It develops the relation between these categories and both orthomodular lattices and Foulis semigroups. The relation between the latter two notions has been uncovered in the 1960s. The current categorical perspective gives a broader context and reconstructs this relationship between orthomodular lattices and Foulis semigroups as special instance.
Online Stochastic Matching: Beating 1-1/e
Venue: arXiv cs.DS 2009
Year: 2009

We study the online stochastic bipartite matching problem, in a form motivated by display ad allocation on the Internet. In the online, but adversarial case, the celebrated result of Karp, Vazirani and Vazirani gives an approximation ratio of $1-1/e$. In the online, stochastic case when nodes are drawn repeatedly from a known distribution, the greedy algorithm matches this approximation ratio, but still, no algorithm is known that beats the $1 - 1/e$ bound. Our main result is a 0.67-approximation online algorithm for stochastic bipartite matching, breaking this $1 - {1/e}$ barrier. Furthermore, we show that no online algorithm can produce a $1-ε$ approximation for an arbitrarily small $ε$ for this problem. We employ a novel application of the idea of the power of two choices from load balancing: we compute two disjoint solutions to the expected instance, and use both of them in the online algorithm in a prescribed preference order. To identify these two disjoint solutions, we solve a max flow problem in a boosted flow graph, and then carefully decompose this maximum flow to two edge-disjoint (near-)matchings. These two offline solutions are used to characterize an upper bound for the optimum in any scenario. This is done by identifying a cut whose value we can bound under the arrival distribution.
Cyclic Codes over Some Finite Quaternion Integer Rings
Venue: arXiv cs.IT 2009
Year: 2009

In this paper, cyclic codes are established over some finite quaternion integer rings with respect to the quaternion Mannheim distance, and de- coding algorithm for these codes is given.
Cross-Layer Design of FDD-OFDM Systems based on ACK/NAK Feedbacks
Venue: arXiv cs.IT 2009
Year: 2009

It is well-known that cross-layer scheduling which adapts power, rate and user allocation can achieve significant gain on system capacity. However, conventional cross-layer designs all require channel state information at the base station (CSIT) which is difficult to obtain in practice. In this paper, we focus on cross-layer resource optimization based on ACK/NAK feedback flows in OFDM systems without explicit CSIT. While the problem can be modeled as Markov Decision Process (MDP), brute force approach by policy iteration or value iteration cannot lead to any viable solution. Thus, we derive a simple closed-form solution for the MDP cross-layer problem, which is asymptotically optimal for sufficiently small target packet error rate (PER). The proposed solution also has low complexity and is suitable for realtime implementation. It is also shown to achieve significant performance gain compared with systems that do not utilize the ACK/NAK feedbacks for cross-layer designs or cross-layer systems that utilize very unreliable CSIT for adaptation with mismatch in CSIT error statistics. Asymptotic analysis is also provided to obtain useful design insights.
A fast algorithm for computing minimal-norm solutions to underdetermined systems of linear equations
Venue: arXiv cs.NA 2009
Year: 2009

We introduce a randomized algorithm for computing the minimal-norm solution to an underdetermined system of linear equations. Given an arbitrary full-rank m x n matrix A with m<n, any m x 1 vector b, and any positive real number epsilon less than 1, the procedure computes an n x 1 vector x approximating to relative precision epsilon or better the n x 1 vector p of minimal Euclidean norm satisfying Ap=b. The algorithm typically requires O(mn log(sqrt(n)/epsilon) + m**3) floating-point operations, generally less than the O(m**2 n) required by the classical schemes based on QR-decompositions or bidiagonalization. We present several numerical examples illustrating the performance of the algorithm.
Flexible frontiers for text division into rows
Venue: arXiv cs.OH 2009
Year: 2009

This paper presents an original solution for flexible hand-written text division into rows. Unlike the standard procedure, the proposed method avoids the isolated characters extensions amputation and reduces the recognition error rate in the final stage.
Asymptotic Capacity and Optimal Precoding in MIMO Multi-Hop Relay Networks
Venue: arXiv cs.IT 2009
Year: 2009

A multi-hop relaying system is analyzed where data sent by a multi-antenna source is relayed by successive multi-antenna relays until it reaches a multi-antenna destination. Assuming correlated fading at each hop, each relay receives a faded version of the signal from the previous level, performs linear precoding and retransmits it to the next level. Using free probability theory and assuming that the noise power at relaying levels-- but not at destination-- is negligible, the closed-form expression of the asymptotic instantaneous end-to-end mutual information is derived as the number of antennas at all levels grows large. The so-obtained deterministic expression is independent from the channel realizations while depending only on channel statistics. Moreover, it also serves as the asymptotic value of the average end-to-end mutual information. The optimal singular vectors of the precoding matrices that maximize the average mutual information with finite number of antennas at all levels are also provided. It turns out that the optimal precoding singular vectors are aligned to the eigenvectors of the channel correlation matrices. Thus they can be determined using only the known channel statistics. As the optimal precoding singular vectors are independent from the system size, they are also optimal in the asymptotic regime.
Towards Automated Deduction in Blackmail Case Analysis with Forensic Lucid
Venue: arXiv cs.LO 2009
Year: 2009

This work-in-progress focuses on the refinement of application of the intensional logic to cyberforensic analysis and its benefits are compared with the finite-state automata approach. This work extends the use of the scientific intensional programming paradigm onto modeling and implementation of a cyberforensics investigation process with the backtrace of event reconstruction, modeling the evidence as multidimensional hierarchical contexts, and proving or disproving the claims with it in the intensional manner of evaluation. This is a practical, context-aware improvement over the finite state automata (FSA) approach we have seen in the related works. As a base implementation language model we use in this approach is a new dialect of the Lucid programming language, that we call Forensic Lucid and in this paper we focus on defining hierarchical contexts based on the intensional logic for the evaluation of cyberforensic expressions.
A Minimum Description Length Approach to Multitask Feature Selection
Venue: arXiv cs.LG 2009
Year: 2009

Many regression problems involve not one but several response variables (y's). Often the responses are suspected to share a common underlying structure, in which case it may be advantageous to share information across them; this is known as multitask learning. As a special case, we can use multiple responses to better identify shared predictive features -- a project we might call multitask feature selection. This thesis is organized as follows. Section 1 introduces feature selection for regression, focusing on ell_0 regularization methods and their interpretation within a Minimum Description Length (MDL) framework. Section 2 proposes a novel extension of MDL feature selection to the multitask setting. The approach, called the "Multiple Inclusion Criterion" (MIC), is designed to borrow information across regression tasks by more easily selecting features that are associated with multiple responses. We show in experiments on synthetic and real biological data sets that MIC can reduce prediction error in settings where features are at least partially shared across responses. Section 3 surveys hypothesis testing by regression with a single response, focusing on the parallel between the standard Bonferroni correction and an MDL approach. Mirroring the ideas in Section 2, Section 4 proposes a novel MIC approach to hypothesis testing with multiple responses and shows that on synthetic data with significant sharing of features across responses, MIC sometimes outperforms standard FDR-controlling methods in terms of finding true positives for a given level of false positives. Section 5 concludes.
Managing Distributed MARF with SNMP
Venue: arXiv cs.DC 2009
Year: 2009

The scope of this project's work focuses on the research and prototyping of the extension of the Distributed MARF such that its services can be managed through the most popular management protocol familiarly, SNMP. The rationale behind SNMP vs. MARF's proprietary management protocols, is that can be integrated with the use of common network service and device management, so the administrators can manage MARF nodes via a already familiar protocol, as well as monitor their performance, gather statistics, set desired configuration, etc. perhaps using the same management tools they've been using for other network devices and application servers.
Multi-Linear cryptanalysis in Power Analysis Attacks MLPA
Venue: arXiv cs.CR 2009
Year: 2009

Power analysis attacks against embedded secret key cryptosystems are widely studied since the seminal paper of Paul Kocher, Joshua Ja, and Benjamin Jun in 1998 where has been introduced the powerful Differential Power Analysis. The strength of DPA is such that it became necessary to develop sound and efficient countermeasures. Nowadays embedded cryptographic primitives usually integrate one or several of these countermeasures (e.g. masking techniques, asynchronous designs, balanced dynamic dual-rail gates designs, noise adding, power consumption smoothing, etc. ...). This document presents a simple, yet interesting, countermeasure to DPA and HO-DPA attacks, called brutal countermeasure and new power analysis attacks using multi-linear approximations (MLPA attacks) based on very recent and still unpublished results of Tavernier et al..