OpenRaiser/Intern-Atlas huggingface dataset:
General Auction-Theoretic Strategies for Distributed Partner Selection in Cooperative Wireless Networks
Venue: arXiv cs.IT 2010
Year: 2010

It is unrealistic to assume that all nodes in an ad hoc wireless network would be willing to participate in cooperative communication, especially if their desired Quality-of- Service (QoS) is achievable via direct transmission. An incentivebased auction mechanism is presented to induce cooperative behavior in wireless networks with emphasis on users with asymmetrical channel fading conditions. A single-object secondprice auction is studied for cooperative partner selection in singlecarrier networks. In addition, a multiple-object bundled auction is analyzed for the selection of multiple simultaneous partners in a cooperative orthogonal frequency-division multiplexing (OFDM) setting. For both cases, we characterize equilibrium outage probability performance, seller revenue, and feedback bounds. The auction-based partner selection allows winning bidders to achieve their desired QoS while compensating the seller who assists them. At the local level sellers aim for revenue maximization, while connections are drawn to min-max fairness at the network level. The proposed strategies for partner selection in self-configuring cooperative wireless networks are shown to be robust under conditions of uncertainty in the number of users requesting cooperation, as well as minimal topology and channel link information available to individual users.
Analyzing the Social Structure and Dynamics of E-mail and Spam in Massive Backbone Internet Traffic
Venue: arXiv cs.SI 2010
Year: 2010

E-mail is probably the most popular application on the Internet, with everyday business and personal communications dependent on it. Spam or unsolicited e-mail has been estimated to cost businesses significant amounts of money. However, our understanding of the network-level behavior of legitimate e-mail traffic and how it differs from spam traffic is limited. In this study, we have passively captured SMTP packets from a 10 Gbit/s Internet backbone link to construct a social network of e-mail users based on their exchanged e-mails. The focus of this paper is on the graph metrics indicating various structural properties of e-mail networks and how they evolve over time. This study also looks into the differences in the structural and temporal characteristics of spam and non-spam networks. Our analysis on the collected data allows us to show several differences between the behavior of spam and legitimate e-mail traffic, which can help us to understand the behavior of spammers and give us the knowledge to statistically model spam traffic on the network-level in order to complement current spam detection techniques.
Software Development Standard and Software Engineering Practice: A Case Study of Bangladesh
Venue: arXiv cs.SE 2010
Year: 2010

Improving software process to achieve high quality in a software development organization is the key factor to success. Bangladeshi software firms have not experienced much in this particular area in comparison to other countries. The ISO 9001 and CMM standard has become a basic part of software development. The main objectives of our study are: 1) To understand the software development process uses by the software developer firms in Bangladesh 2) To identify the development practices based on established quality standard and 3) To establish a standardized and coherent process for the development of software for a specific project. It is revealed from this research that software industries of Bangladesh are lacking in target set for software process and improvement, involvement of quality control activities, and standardize business expertise practice. This paper investigates the Bangladeshi software industry in the light of the above challenges.
Rate Region Frontiers for n-user Interference Channel with Interference as Noise
Venue: arXiv cs.IT 2010
Year: 2010

This paper presents the achievable rate region frontiers for the n-user interference channel when there is no cooperation at the transmit nor at the receive side. The receiver is assumed to treat the interference as additive thermal noise and does not employ multiuser detection. In this case, the rate region frontier for the n-user interference channel is found to be the union of n hyper-surface frontiers of dimension n-1, where each is characterized by having one of the transmitters transmitting at full power. The paper also finds the conditions determining the convexity or concavity of the frontiers for the case of two-user interference channel, and discusses when a time sharing approach should be employed with specific results pertaining to the two-user symmetric channel.
Quantization of Discrete Probability Distributions
Venue: arXiv cs.IT 2010
Year: 2010

We study the problem of quantization of discrete probability distributions, arising in universal coding, as well as other applications. We show, that in many situations this problem can be reduced to the covering problem for the unit simplex. This setting yields precise asymptotic characterization in the high-rate regime. We also describe a simple and asymptotically optimal algorithm for solving this problem. Performance of this algorithm is studied and compared with several known solutions.
Vulnerability Analysis of PAP for RFID Tags
Venue: arXiv cs.CR 2010
Year: 2010

In this paper, we analyze the security of an RFID authentication protocol proposed by Liu and Bailey [1], called Privacy and Authentication Protocol (PAP), and show its vulnerabilities and faulty assumptions. PAP is a privacy and authentication protocol designed for passive tags. The authors claim that the protocol, being resistant to commonly assumed attacks, requires little computation and provides privacy protection and authentication. Nevertheless, we propose two traceability attacks and an impersonation attack, in which the revealing of secret information (i.e., secret key and static identifier) shared between the tag and the reader is unnecessary. Moreover, we review all basic assumptions on which the design of the protocol resides, and show how many of them are incorrect and are contrary to the common assumptions in RFID systems.
Capacity Limits of Multiuser Multiantenna Cognitive Networks
Venue: arXiv cs.IT 2010
Year: 2010

Unlike point-to-point cognitive radio, where the constraint imposed by the primary rigidly curbs the secondary throughput, multiple secondary users have the potential to more efficiently harvest the spectrum and share it among themselves. This paper analyzes the sum throughput of a multiuser cognitive radio system with multi-antenna base stations, either in the uplink or downlink mode. The primary and secondary have $N$ and $n$ users, respectively, and their base stations have $M$ and $m$ antennas, respectively. We show that an uplink secondary throughput grows with $\frac{m}{N +1}\log n$ if the primary is a downlink system, and grows with $\frac{m}{M +1}\log n$ if the primary is an uplink system. These growth rates are shown to be optimal and can be obtained with a simple threshold-based user selection rule. Furthermore, we show that the secondary throughput can grow proportional to $\log n$ while simultaneously pushing the interference on the primary down to zero, asymptotically. Furthermore, we show that a downlink secondary throughput grows with $m\log \log n$ in the presence of either an uplink or downlink primary system. In addition, the interference on the primary can be made to go to zero asymptotically while the secondary throughput increases proportionally to $\log \log n$. Thus, unlike the point-to-point case, multiuser cognitive radios can achieve non-trivial sum throughput despite stringent primary interference constraints.
ElasTraS: An Elastic Transactional Data Store in the Cloud
Venue: arXiv cs.DB 2010
Year: 2010

Over the last couple of years, "Cloud Computing" or "Elastic Computing" has emerged as a compelling and successful paradigm for internet scale computing. One of the major contributing factors to this success is the elasticity of resources. In spite of the elasticity provided by the infrastructure and the scalable design of the applications, the elephant (or the underlying database), which drives most of these web-based applications, is not very elastic and scalable, and hence limits scalability. In this paper, we propose ElasTraS which addresses this issue of scalability and elasticity of the data store in a cloud computing environment to leverage from the elastic nature of the underlying infrastructure, while providing scalable transactional data access. This paper aims at providing the design of a system in progress, highlighting the major design choices, analyzing the different guarantees provided by the system, and identifying several important challenges for the research community striving for computing in the cloud.
Addressing the Challenge of Distributed Interactive Simulation With Data Distribution Service
Venue: arXiv cs.NI 2010
Year: 2010

Real-Time availability of information is of most importance in large scale distributed interactive simulation in network-centric communication. Information generated from multiple federates must be distributed and made available to interested parties and providing the required QoS for consistent communication. The remainder of this paper discuss design alternative for realizing high performance distributed interactive simulation (DIS) application using the OMG Data Distribution Service (DDS), which is a QoS enabled publish/subscribe platform standard for time-critical, data-centric and large scale distributed networks. The considered application, in the civil domain, is used for remote education in driving schools. An experimental design evaluates the bandwidth and the latency performance of DDS and a comparison with the High Level Architecture performance is given.
Green Modulations in Energy-Constrained Wireless Sensor Networks
Venue: arXiv cs.IT 2010
Year: 2010

Due to the unique characteristics of sensor devices, finding the energy-efficient modulation with a low-complexity implementation (refereed to as green modulation) poses significant challenges in the physical layer design of Wireless Sensor Networks (WSNs). Toward this goal, we present an in-depth analysis on the energy efficiency of various modulation schemes using realistic models in the IEEE 802.15.4 standard to find the optimum distance-based scheme in a WSN over Rayleigh and Rician fading channels with path-loss. We describe a proactive system model according to a flexible duty-cycling mechanism utilized in practical sensor apparatus. The present analysis includes the effect of the channel bandwidth and the active mode duration on the energy consumption of popular modulation designs. Path-loss exponent and DC-DC converter efficiency are also taken into consideration. In considering the energy efficiency and complexity, it is demonstrated that among various sinusoidal carrier-based modulations, the optimized Non-Coherent M-ary Frequency Shift Keying (NC-MFSK) is the most energy-efficient scheme in sparse WSNs for each value of the path-loss exponent, where the optimization is performed over the modulation parameters. In addition, we show that the On-Off Keying (OOK) displays a significant energy saving as compared to the optimized NC-MFSK in dense WSNs with small values of path-loss exponent.
Consecutive ones property testing: cut or swap
Venue: arXiv cs.DS 2010
Year: 2010

Let C be a finite set of $N elements and R = {R_1,R_2, ..,R_m} a family of M subsets of C. The family R verifies the consecutive ones property if there exists a permutation P of C such that each R_i in R is an interval of P. There already exist several algorithms to test this property in sum_{i=1}^m |R_i| time, all being involved. We present a simpler algorithm, based on a new partitioning scheme.
Doubly Exponential Solution for Randomized Load Balancing Models with General Service Times
Venue: arXiv cs.DM 2010
Year: 2010

In this paper, we provide a novel and simple approach to study the supermarket model with general service times. This approach is based on the supplementary variable method used in analyzing stochastic models extensively. We organize an infinite-size system of integral-differential equations by means of the density dependent jump Markov process, and obtain a close-form solution: doubly exponential structure, for the fixed point satisfying the system of nonlinear equations, which is always a key in the study of supermarket models. The fixed point is decomposited into two groups of information under a product form: the arrival information and the service information. based on this, we indicate two important observations: the fixed point for the supermarket model is different from the tail of stationary queue length distribution for the ordinary M/G/1 queue, and the doubly exponential solution to the fixed point can extensively exist even if the service time distribution is heavy-tailed. Furthermore, we analyze the exponential convergence of the current location of the supermarket model to its fixed point, and study the Lipschitz condition in the Kurtz Theorem under general service times. Based on these analysis, one can gain a new understanding how workload probing can help in load balancing jobs with general service times such as heavy-tailed service.
NESVM: a Fast Gradient Method for Support Vector Machines
Venue: arXiv cs.LG 2010
Year: 2010

Support vector machines (SVMs) are invaluable tools for many practical applications in artificial intelligence, e.g., classification and event recognition. However, popular SVM solvers are not sufficiently efficient for applications with a great deal of samples as well as a large number of features. In this paper, thus, we present NESVM, a fast gradient SVM solver that can optimize various SVM models, e.g., classical SVM, linear programming SVM and least square SVM. Compared against SVM-Perf \cite{SVM_Perf}\cite{PerfML} (its convergence rate in solving the dual SVM is upper bounded by $\mathcal O(1/\sqrt{k})$, wherein $k$ is the number of iterations.) and Pegasos \cite{Pegasos} (online SVM that converges at rate $\mathcal O(1/k)$ for the primal SVM), NESVM achieves the optimal convergence rate at $\mathcal O(1/k^{2})$ and a linear time complexity. In particular, NESVM smoothes the non-differentiable hinge loss and $\ell_1$-norm in the primal SVM. Then the optimal gradient method without any line search is adopted to solve the optimization. In each iteration round, the current gradient and historical gradients are combined to determine the descent direction, while the Lipschitz constant determines the step size. Only two matrix-vector multiplications are required in each iteration round. Therefore, NESVM is more efficient than existing SVM solvers. In addition, NESVM is available for both linear and nonlinear kernels. We also propose "homotopy NESVM" to accelerate NESVM by dynamically decreasing the smooth parameter and using the continuation method. Our experiments on census income categorization, indoor/outdoor scene classification, event recognition and scene recognition suggest the efficiency and the effectiveness of NESVM. The MATLAB code of NESVM will be available on our website for further assessment.
Security Mitigations for Return-Oriented Programming Attacks
Venue: arXiv cs.CR 2010
Year: 2010

With the discovery of new exploit techniques, new protection mechanisms are needed as well. Mitigations like DEP (Data Execution Prevention) or ASLR (Address Space Layout Randomization) created a significantly more difficult environment for vulnerability exploitation. Attackers, however, have recently developed new exploitation methods which are capable of bypassing the operating system's security protection mechanisms. In this paper we present a short summary of novel and known mitigation techniques against return-oriented programming (ROP) attacks. The techniques described in this article are related mostly to x86-32 processors and Microsoft Windows operating systems.
Noise in Naming Games, partial synchronization and community detection in social networks
Venue: arXiv cs.MA 2010
Year: 2010

The Naming Games (NG) are agent-based models for agreement dynamics, peer pressure and herding in social networks, and protocol selection in autonomous ad-hoc sensor networks. By introducing a small noise term to the NG, the resulting Markov Chain model called Noisy Naming Games (NNG) are ergodic, in which all partial consensus states are recurrent. By using Gibbs-Markov equivalence we show how to get the NNG's stationary distribution in terms of the local specification of a related Markov Random Field (MRF). By ordering the partially-synchronized states according to their Gibbs energy, taken here to be a good measure of social tension, this method offers an enhanced method for community-detection in social interaction data. We show how the lowest Gibbs energy multi-name states separate and display the hidden community structures within a social network.
Percolation and Connectivity in the Intrinsically Secure Communications Graph
Venue: arXiv cs.IT 2010
Year: 2010

The ability to exchange secret information is critical to many commercial, governmental, and military networks. The intrinsically secure communications graph (iS-graph) is a random graph which describes the connections that can be securely established over a large-scale network, by exploiting the physical properties of the wireless medium. This paper aims to characterize the global properties of the iS-graph in terms of: (i) percolation on the infinite plane, and (ii) full connectivity on a finite region. First, for the Poisson iS-graph defined on the infinite plane, the existence of a phase transition is proven, whereby an unbounded component of connected nodes suddenly arises as the density of legitimate nodes is increased. This shows that long-range secure communication is still possible in the presence of eavesdroppers. Second, full connectivity on a finite region of the Poisson iS-graph is considered. The exact asymptotic behavior of full connectivity in the limit of a large density of legitimate nodes is characterized. Then, simple, explicit expressions are derived in order to closely approximate the probability of full connectivity for a finite density of legitimate nodes. The results help clarify how the presence of eavesdroppers can compromise long-range secure communication.
Recovering Grammar Relationships for the Java Language Specification
Venue: arXiv cs.PL 2010
Year: 2010

Grammar convergence is a method that helps discovering relationships between different grammars of the same language or different language versions. The key element of the method is the operational, transformation-based representation of those relationships. Given input grammars for convergence, they are transformed until they are structurally equal. The transformations are composed from primitive operators; properties of these operators and the composed chains provide quantitative and qualitative insight into the relationships between the grammars at hand. We describe a refined method for grammar convergence, and we use it in a major study, where we recover the relationships between all the grammars that occur in the different versions of the Java Language Specification (JLS). The relationships are represented as grammar transformation chains that capture all accidental or intended differences between the JLS grammars. This method is mechanized and driven by nominal and structural differences between pairs of grammars that are subject to asymmetric, binary convergence steps. We present the underlying operator suite for grammar transformation in detail, and we illustrate the suite with many examples of transformations on the JLS grammars. We also describe the extraction effort, which was needed to make the JLS grammars amenable to automated processing. We include substantial metadata about the convergence process for the JLS so that the effort becomes reproducible and transparent.
Online Learning in Case of Unbounded Losses Using the Follow Perturbed Leader Algorithm
Venue: arXiv cs.LG 2010
Year: 2010

In this paper the sequential prediction problem with expert advice is considered for the case where losses of experts suffered at each step cannot be bounded in advance. We present some modification of Kalai and Vempala algorithm of following the perturbed leader where weights depend on past losses of the experts. New notions of a volume and a scaled fluctuation of a game are introduced. We present a probabilistic algorithm protected from unrestrictedly large one-step losses. This algorithm has the optimal performance in the case when the scaled fluctuations of one-step losses of experts of the pool tend to zero.
Learning from Profession Knowledge: Application on Knitting
Venue: arXiv cs.AI 2010
Year: 2010

Knowledge Management is a global process in companies. It includes all the processes that allow capitalization, sharing and evolution of the Knowledge Capital of the firm, generally recognized as a critical resource of the organization. Several approaches have been defined to capitalize knowledge but few of them study how to learn from this knowledge. We present in this paper an approach that helps to enhance learning from profession knowledge in an organisation. We apply our approach on knitting industry.
Distributed solving through model splitting
Venue: arXiv cs.AI 2010
Year: 2010

Constraint problems can be trivially solved in parallel by exploring different branches of the search tree concurrently. Previous approaches have focused on implementing this functionality in the solver, more or less transparently to the user. We propose a new approach, which modifies the constraint model of the problem. An existing model is split into new models with added constraints that partition the search space. Optionally, additional constraints are imposed that rule out the search already done. The advantages of our approach are that it can be implemented easily, computations can be stopped and restarted, moved to different machines and indeed solved on machines which are not able to communicate with each other at all.
Collaborative Spectrum Sensing from Sparse Observations in Cognitive Radio Networks
Venue: arXiv cs.IT 2010
Year: 2010

Spectrum sensing, which aims at detecting spectrum holes, is the precondition for the implementation of cognitive radio (CR). Collaborative spectrum sensing among the cognitive radio nodes is expected to improve the ability of checking complete spectrum usage. Due to hardware limitations, each cognitive radio node can only sense a relatively narrow band of radio spectrum. Consequently, the available channel sensing information is far from being sufficient for precisely recognizing the wide range of unoccupied channels. Aiming at breaking this bottleneck, we propose to apply matrix completion and joint sparsity recovery to reduce sensing and transmitting requirements and improve sensing results. Specifically, equipped with a frequency selective filter, each cognitive radio node senses linear combinations of multiple channel information and reports them to the fusion center, where occupied channels are then decoded from the reports by using novel matrix completion and joint sparsity recovery algorithms. As a result, the number of reports sent from the CRs to the fusion center is significantly reduced. We propose two decoding approaches, one based on matrix completion and the other based on joint sparsity recovery, both of which allow exact recovery from incomplete reports. The numerical results validate the effectiveness and robustness of our approaches. In particular, in small-scale networks, the matrix completion approach achieves exact channel detection with a number of samples no more than 50% of the number of channels in the network, while joint sparsity recovery achieves similar performance in large-scale networks.