OpenRaiser/Intern-Atlas huggingface dataset:
Buffered Aloha with K-Exponential Backoff -- Part II: Delay Analysis
Venue: arXiv cs.NI 2009
Year: 2009

This paper presents the delay analysis for buffered Aloha networks with K-Exponential Backoff. Mean access delay and mean queueing delay are derived and demonstrated via the examples of Geometric Retransmission (K=1) and Exponential Backoff (K=infinity). The comparison shows that higher delay is incurred with Geometric Retransmission when the aggregate input rate is small, and the delay gap is enlarged as the number of nodes n increases. With a high traffic input rate, however, the delay performance with Exponential Backoff severely deteriorates. The mean queueing delay will be unbounded if the aggregate input rate exceeds 0.3. We also extend the analysis to the contention-window-based backoff model which is widely adopted in practical MAC protocols. It will be revealed that both the retransmission-probability-based and the contention-window-based models exhibit the same stable region and achieve similar queueing performance in most cases, which justifies the intuition that was taken but remained unverified in previous studies: the retransmission-probability-based backoff model can serve as a good approximation of the contention-window-based one.
Parametric packing of selfish items and the subset sum algorithm
Venue: arXiv cs.GT 2009
Year: 2009

The subset sum algorithm is a natural heuristic for the classical Bin Packing problem: In each iteration, the algorithm finds among the unpacked items, a maximum size set of items that fits into a new bin. More than 35 years after its first mention in the literature, establishing the worst-case performance of this heuristic remains, surprisingly, an open problem. Due to their simplicity and intuitive appeal, greedy algorithms are the heuristics of choice of many practitioners. Therefore, better understanding simple greedy heuristics is, in general, an interesting topic in its own right. Very recently, Epstein and Kleiman (Proc. ESA 2008) provided another incentive to study the subset sum algorithm by showing that the Strong Price of Anarchy of the game theoretic version of the bin-packing problem is precisely the approximation ratio of this heuristic. In this paper we establish the exact approximation ratio of the subset sum algorithm, thus settling a long standing open problem. We generalize this result to the parametric variant of the bin packing problem where item sizes lie on the interval (0,α] for some α\leq 1, yielding tight bounds for the Strong Price of Anarchy for all α\leq 1. Finally, we study the pure Price of Anarchy of the parametric Bin Packing game for which we show nearly tight upper and lower bounds for all α\leq 1.
Fact Sheet on Semantic Web
Venue: arXiv cs.AI 2009
Year: 2009

The report gives an overview about activities on the topic Semantic Web. It has been released as technical report for the project "KTweb -- Connecting Knowledge Technologies Communities" in 2003.
Slowly synchronizing automata with zero and incomplete sets
Venue: arXiv cs.FL 2009
Year: 2009

Using combinatorial properties of incomplete sets in a free monoid we construct a series of n-state deterministic automata with zero whose shortest synchronizing word has length n^2/4+n/2-1.
Alice Meets Bob: A Comparative Usability Study of Wireless Device Pairing Methods for a "Two-User" Setting
Venue: arXiv cs.CR 2009
Year: 2009

When users want to establish wireless communication between/among their devices, the channel has to be bootstrapped first. To prevent any malicious control of or eavesdropping over the communication, the channel is desired to be authenticated and confidential. The process of setting up a secure communication channel between two previously unassociated devices is referred to as "Secure Device Pairing". When there is no prior security context, e.g., shared secrets, common key servers or public key certificates, device pairing requires user involvement into the process. The idea usually involves leveraging an auxiliary human-perceptible channel to authenticate the data exchanged over the insecure wireless channel. We observe that the focus of prior research has mostly been limited to pairing scenarios where a single user controls both the devices. In this paper, we consider more general and emerging "two-user" scenarios, where two different users establish pairing between their respective devices. Although a number of pairing methods exists in the literature, only a handful of those are applicable to the two-user setting. We present the first study to identify the methods practical for two-user pairing scenarios, and comparatively evaluate the usability of these methods. Our results identify methods best-suited for users, in terms of efficiency, error-tolerance and of course, usability. Our work sheds light on the applicability and usability of pairing methods for emerging two-user scenarios, a topic largely ignored so far.
Probabilistic Automata over Infinite Words: Expressiveness, Efficiency, and Decidability
Venue: arXiv cs.FL 2009
Year: 2009

Probabilistic omega-automata are variants of nondeterministic automata for infinite words where all choices are resolved by probabilistic distributions. Acceptance of an infinite input word can be defined in different ways: by requiring that (i) the probability for the accepting runs is positive (probable semantics), or (ii) almost all runs are accepting (almost-sure semantics), or (iii) the probability measure of the accepting runs is greater than a certain threshold (threshold semantics). The underlying notion of an accepting run can be defined as for standard omega-automata by means of a Buechi condition or other acceptance conditions, e.g., Rabin or Streett conditions. In this paper, we put the main focus on the probable semantics and provide a summary of the fundamental properties of probabilistic omega-automata concerning expressiveness, efficiency, and decision problems.
Tunable locally-optimal geographical forwarding in wireless sensor networks with sleep-wake cycling nodes
Venue: arXiv cs.NI 2009
Year: 2009

We consider a wireless sensor network whose main function is to detect certain infrequent alarm events, and to forward alarm packets to a base station, using geographical forwarding. The nodes know their locations, and they sleep-wake cycle, waking up periodically but not synchronously. In this situation, when a node has a packet to forward to the sink, there is a trade-off between how long this node waits for a suitable neighbor to wake up and the progress the packet makes towards the sink once it is forwarded to this neighbr. Hence, in choosing a relay node, we consider the problem of minimizing average delay subject to a constraint on the average progress. By constraint relaxation, involving a Lagrange multiplier, we formulate this next hop relay selection problem as a Markov decision process (MDP). The exact optimal solution (BF (Best Forward)) can be found, but is computationally intensive. Next, we consider a mathematically simplified model for which the optimal policy (SF (Simplified Forward)) turns out to be a simple one-step-look-ahead rule. Simulations show that SF is very close in performance to BF, even for reasonably small node density. We then study the end-to-end performance of SF in comparison with two extremal policies: Max Forward (MF), which makes the maximum possible progress per hop and thus reduces network energy consumption, and First Forward (FF), which forwards the packet to the first node to wake up, and thus tends to make end-to-end forwarding delays small. We find that, with appropriate choice of one hop average progress constraint, SF can be tuned to provide a favorable trade-off between end-to-end packet delay and the number of hops in the forwarding path.
A Proposed Algorithm to improve security & Efficiency of SSL-TLS servers using Batch RSA decryption
Venue: arXiv cs.CR 2009
Year: 2009

Today, Internet becomes the essential part of our lives. Over 90 percent of the ecommerce is developed on the Internet. A security algorithm became very necessary for producer client transactions assurance and the financial applications safety. The rsa algorithm applicability derives from algorithm properties like confidentiality, safe authentication, data safety and integrity on the internet. Thus, this kind of networks can have a more easy utilization by practical accessing from short, medium, even long distance and from different public places. Rsa encryption in the client side is relatively cheap, whereas, the corresponding decryption in the server side is expensive because its private exponent is much larger. Thus ssl tls servers become swamped to perform public key decryption operations when the simultaneous requests increase quickly .The batch rsa method is useful for such highly loaded web server .In our proposed algorithm by reducing the response time and clients tolerable waiting time an improvement in performance of ssl tls servers can be done. The proposed algorithm should provide the reasonable response time and optimizes server performance significantly. At Encryption side, to withstand many attacks like brute force attack, subtle attack etc. we also adapted a parameter generation method, which sieve all the parameters strictly, and filter out every insecure parameter.
Testing the Equivalence of Regular Languages
Venue: arXiv cs.FL 2009
Year: 2009

The minimal deterministic finite automaton is generally used to determine regular languages equality. Antimirov and Mosses proposed a rewrite system for deciding regular expressions equivalence of which Almeida et al. presented an improved variant. Hopcroft and Karp proposed an almost linear algorithm for testing the equivalence of two deterministic finite automata that avoids minimisation. In this paper we improve the best-case running time, present an extension of this algorithm to non-deterministic finite automata, and establish a relationship between this algorithm and the one proposed in Almeida et al. We also present some experimental comparative results. All these algorithms are closely related with the recent coalgebraic approach to automata proposed by Rutten.
Nondeterministic State Complexity of Positional Addition
Venue: arXiv cs.FL 2009
Year: 2009

Consider nondeterministic finite automata recognizing base-k positional notation of numbers. Assume that numbers are read starting from their least significant digits. It is proved that if two sets of numbers S and T are represented by nondeterministic automata of m and n states, respectively, then their sum {s+t | s in S, t in T} is represented by a nondeterministic automaton with 2mn+2m+2n+1 states. Moreover, this number of states is necessary in the worst case for all k>=9.
On the Shuffle Automaton Size for Words
Venue: arXiv cs.FL 2009
Year: 2009

We investigate the state size of DFAs accepting the shuffle of two words. We provide words u and v, such that the minimal DFA for u shuffled with v requires an exponential number of states. We also show some conditions for the words u and v which ensure a quadratic upper bound on the state size of u shuffled with v. Moreover, switching only two letters within one of u or v is enough to trigger the change from quadratic to exponential.
Cooperative Training for Attribute-Distributed Data: Trade-off Between Data Transmission and Performance
Venue: arXiv cs.DC 2009
Year: 2009

This paper introduces a modeling framework for distributed regression with agents/experts observing attribute-distributed data (heterogeneous data). Under this model, a new algorithm, the iterative covariance optimization algorithm (ICOA), is designed to reshape the covariance matrix of the training residuals of individual agents so that the linear combination of the individual estimators minimizes the ensemble training error. Moreover, a scheme (Minimax Protection) is designed to provide a trade-off between the number of data instances transmitted among the agents and the performance of the ensemble estimator without undermining the convergence of the algorithm. This scheme also provides an upper bound (with high probability) on the test error of the ensemble estimator. The efficacy of ICOA combined with Minimax Protection and the comparison between the upper bound and actual performance are both demonstrated by simulations.
Interference alignment-based sum capacity bounds for random dense Gaussian interference networks
Venue: arXiv cs.IT 2009
Year: 2009

We consider a dense $K$ user Gaussian interference network formed by paired transmitters and receivers placed independently at random in a fixed spatial region. Under natural conditions on the node position distributions and signal attenuation, we prove convergence in probability of the average per-user capacity $\csum/K$ to $\half \ep \log(1 + 2 \SNR)$. The achievability result follows directly from results based on an interference alignment scheme presented in recent work of Nazer et al. Our main contribution comes through an upper bound, motivated by ideas of `bottleneck capacity' developed in recent work of Jafar. By controlling the physical location of transmitter--receiver pairs, we can match a large proportion of these pairs to form so-called $ε$-bottleneck links, with consequent control of the sum capacity.
Optimal Scheduling for Fair Resource Allocation in Ad Hoc Networks with Elastic and Inelastic Traffic
Venue: arXiv cs.NI 2009
Year: 2009

This paper studies the problem of congestion control and scheduling in ad hoc wireless networks that have to support a mixture of best-effort and real-time traffic. Optimization and stochastic network theory have been successful in designing architectures for fair resource allocation to meet long-term throughput demands. However, to the best of our knowledge, strict packet delay deadlines were not considered in this framework previously. In this paper, we propose a model for incorporating the quality of service (QoS) requirements of packets with deadlines in the optimization framework. The solution to the problem results in a joint congestion control and scheduling algorithm which fairly allocates resources to meet the fairness objectives of both elastic and inelastic flows, and per-packet delay requirements of inelastic flows.
On Computing Compression Trees for Data Collection in Sensor Networks
Venue: arXiv cs.NI 2009
Year: 2009

We address the problem of efficiently gathering correlated data from a wired or a wireless sensor network, with the aim of designing algorithms with provable optimality guarantees, and understanding how close we can get to the known theoretical lower bounds. Our proposed approach is based on finding an optimal or a near-optimal {\em compression tree} for a given sensor network: a compression tree is a directed tree over the sensor network nodes such that the value of a node is compressed using the value of its parent. We consider this problem under different communication models, including the {\em broadcast communication} model that enables many new opportunities for energy-efficient data collection. We draw connections between the data collection problem and a previously studied graph concept, called {\em weakly connected dominating sets}, and we use this to develop novel approximation algorithms for the problem. We present comparative results on several synthetic and real-world datasets showing that our algorithms construct near-optimal compression trees that yield a significant reduction in the data collection cost.
Dynamic Bandwidth Management in Distributed VoD based on the User Class Using Agents
Venue: arXiv cs.NI 2009
Year: 2009

This paper proposes a dynamic bandwidth management algorithm in which more bandwidth is allocated for higher class users and also higher priority is given to the videos with higher popularity within a class using agent technology. The popularity and weight profile of the videos which is used for efficiently allocating bandwidth is periodically updated by a mobile agent. The proposed approach allocates more bandwidth for higher class users and gives higher priority for higher weight videos [popular videos] so that they can be served with high QoS, reduces the load on the central multimedia server and maximizes the channel utilization between the neighboring proxy servers and the central multimedia server and lower video rejection ratio. The simulation results prove the reduction of load on central multimedia server by load sharing among the neighboring proxy servers, maximum bandwidth utilization, and more bandwidth allocation for higher class users.
Treewidth of Erdös-Rényi Random Graphs, Random Intersection Graphs, and Scale-Free Random Graphs
Venue: arXiv cs.DM 2009
Year: 2009

We prove that the treewidth of an Erdös-Rényi random graph $\rg{n, m}$ is, with high probability, greater than $βn$ for some constant $β> 0$ if the edge/vertex ratio $\frac{m}{n}$ is greater than 1.073. Our lower bound $\frac{m}{n} > 1.073$ improves the only previously-known lower bound. We also study the treewidth of random graphs under two other random models for large-scale complex networks. In particular, our result on the treewidth of \rigs strengths a previous observation on the average-case behavior of the \textit{gate matrix layout} problem. For scale-free random graphs based on the Barabási-Albert preferential-attachment model, our result shows that if more than 12 vertices are attached to a new vertex, then the treewidth of the obtained network is linear in the size of the network with high probability.
On Random Construction of a Bipolar Sensing Matrix with Compact Representation
Venue: arXiv cs.IT 2009
Year: 2009

A random construction of bipolar sensing matrices based on binary linear codes is introduced and its RIP (Restricted Isometry Property) is analyzed based on an argument on the ensemble average of the weight distribution of binary linear codes.
Algorithmic Decision Optimization Techniques for Multiple Types of Agents with Contrasting Interests
Venue: arXiv cs.GT 2009
Year: 2009

In this paper I present several algorithmic techniques for improving the decision process of multiple types of agents behaving in environments where their interests are in conflict. The interactions between the agents are modelled by using several types of two-player games, where the agents have identical roles and compete for the same resources, or where they have different roles, like in query-response games. The described situations have applications in modelling behavior in many types of environments, like distributed systems, learning environments, resource negotiation environments, and many others. The mentioned models are applicable in a wide range of domains, like computer science or the industrial (e.g. metallurgical), economic or financial sector.
Approach To Solving Cybercrime And Cybersecurity
Venue: arXiv cs.CY 2009
Year: 2009

Cybercrime is becoming ever more serious. Findings from 2002 Computer Crime and Security Survey show an upward trend that demonstrates a need for a timely review of existing approaches to fighting this new phenomenon in the information age. In this paper, we provide an overview of Cybercrime and present an international perspective on fighting Cybercrime. This work seeks to define the concept of cyber-crime, identify reasons for cyber-crime, how it can be eradicated, look at those involved and the reasons for their involvement, we would look at how best to detect a criminal mail and in conclusion, proffer recommendations that would help in checking the increasing rate of cyber-crimes and criminals.
Intelligent Advisory System for Supporting University Managers in Law
Venue: arXiv cs.CY 2009
Year: 2009

The rights and duties of both staff members and students are regulated by a large and different numbers of legal regulations and rules. This large number of rules and regulations makes the decision-making process time consuming and error boring. Smart advisory systems could provide rapid and accurate advices to managers and give the arguments for these advices. This paper presents an intelligent advisory system in law to assist the legal educational processes in universities and institutes. The aims of the system are: to provide smart legal advisors in the universities and institutes, to integrate rules and regulations of universities and institutes in the e-government, to ease the burden on the legal advisor and the provision of consulting services to users, to achieve accurate and timely presentation of the legal opinion to a given problem and to assure flexibility for accepting changes in the rules and legal regulations. The system is based on experienced jurists and the rules and regulations of the law organizing Saudi Arabia universities and institutes.
Performance Evaluation of Mesh based Multicast Reactive Routing Protocol under Black Hole Attack
Venue: arXiv cs.CR 2009
Year: 2009

A mobile ad-hoc network is an autonomous system of mobile nodes connected by wireless links in which nodes cooperate by forwarding packets for each other thereby enabling communication beyond direct wireless transmission range. The wireless and dynamic nature of ad-hoc networks makes them vulnerable to attacks especially in routing protocols. Providing security in mobile ad-hoc networks has been a major issue over the recent years. One of the prominent mesh base reactive multicast routing protocols used in ad-hoc networks is On Demand Multicast Routing protocol (ODMRP). The security of ODMRP is compromised by a primary routing attack called black hole attack. In this attack a malicious node advertises itself as having the shortest path to the node whose packets it wants to intercept. This paper discusses the impact of black hole attack on ODMRP under various scenarios. The performance is evaluated using metrics such as packet delivery ratio and end to end delay for various numbers of senders and receivers via simulation. Simulations are carried out using network simulator ns-2. The results enable us to propose solutions to counter the effect of black hole attack.
Polarization for arbitrary discrete memoryless channels
Venue: arXiv cs.IT 2009
Year: 2009

Channel polarization, originally proposed for binary-input channels, is generalized to arbitrary discrete memoryless channels. Specifically, it is shown that when the input alphabet size is a prime number, a similar construction to that for the binary case leads to polarization. This method can be extended to channels of composite input alphabet sizes by decomposing such channels into a set of channels with prime input alphabet sizes. It is also shown that all discrete memoryless channels can be polarized by randomized constructions. The introduction of randomness does not change the order of complexity of polar code construction, encoding, and decoding. A previous result on the error probability behavior of polar codes is also extended to the case of arbitrary discrete memoryless channels. The generalization of polarization to channels with arbitrary finite input alphabet sizes leads to polar-coding methods for approaching the true (as opposed to symmetric) channel capacity of arbitrary channels with discrete or continuous input alphabets.
Still doing evolutionary algorithms with Perl
Venue: arXiv cs.NE 2009
Year: 2009

Algorithm::Evolutionary (A::E from now on) was introduced in 2002, after a talk in YAPC::EU in Munich. 7 years later, A::E is in its 0.67 version (past its "number of the beast" 0.666), and has been used extensively, to the point of being the foundation of much of the (computer) science being done by our research group (and, admittedly, not many others). All is not done, however; now A::E is being integrated with POE so that evolutionary algorithms (EAs) can be combined with all kinds of servers and used in client, servers, and anything in between. In this companion to the talk I will explain what evolutionary algorithms are, what they are being used for, how to do them with Perl (using these or other fine modules found in CPAN) and what evolutionary algorithms can do for Perl at large.