OpenRaiser/Intern-Atlas huggingface dataset:
AstroGrid-D: Grid Technology for Astronomical Science
Venue: arXiv cs.DC 2010
Year: 2010

We present status and results of AstroGrid-D, a joint effort of astrophysicists and computer scientists to employ grid technology for scientific applications. AstroGrid-D provides access to a network of distributed machines with a set of commands as well as software interfaces. It allows simple use of computer and storage facilities and to schedule or monitor compute tasks and data management. It is based on the Globus Toolkit middleware (GT4). Chapter 1 describes the context which led to the demand for advanced software solutions in Astrophysics, and we state the goals of the project. We then present characteristic astrophysical applications that have been implemented on AstroGrid-D in chapter 2. We describe simulations of different complexity, compute-intensive calculations running on multiple sites, and advanced applications for specific scientific purposes, such as a connection to robotic telescopes. We can show from these examples how grid execution improves e.g. the scientific workflow. Chapter 3 explains the software tools and services that we adapted or newly developed. Section 3.1 is focused on the administrative aspects of the infrastructure, to manage users and monitor activity. Section 3.2 characterises the central components of our architecture: The AstroGrid-D information service to collect and store metadata, a file management system, the data management system, and a job manager for automatic submission of compute tasks. We summarise the successfully established infrastructure in chapter 4, concluding with our future plans to establish AstroGrid-D as a platform of modern e-Astronomy.
A Tutorial on Broadcasting Packets over Multiple-Channels in a Multi-Inferface Network Setting in NS-2
Venue: arXiv cs.NI 2010
Year: 2010

With the proliferation of cheaper electronic devices, wireless communication over multiple-channels in a multi-interface network is now possible. For instace, wireless sensor nodes can now operate over multiplechannels. Moreover, cognitive radio sensor networks are also evolving, which also operates over multiple-channels. In the market, we can find antennas that can support the operation of multiple channels, for e.g. the cc2420 antenna that is used for communication between wireless sensor nodes consists of 16 programmable channels. The proper utilization of multiple-channels reduces the interference between the nodes and increase the network throughput. Recently, a Cognitive Radio Cognitive Network (CRCN) patch for NS-2 simulator has proposed to support multi-channel multi-interface capability in NS-2. In this tutorial, we consider how to simulate a multi-channel multiinterface wireless network using the NS-2 simulator. This tutorial is trageted to the novice users who wants to understand the implementation of multi-channel multi-interface in NS-2. We take the Cognitive Radio Cognitive Network (CRCN) patch for NS-2 simulator and demonstrate broadcasting over multiple-channels in a multi-interface network setting. In our seeting, node braodcasts the Hello packets to its neighbors. Neighboring nodes receive the Hello packets if and only if they are tuned to the same channel. We demonstrate through example that the tuning of receivers can be done in two fashions.
Transformations of Logic Programs on Infinite Lists
Venue: arXiv cs.PL 2010
Year: 2010

We consider an extension of logic programs, called ω-programs, that can be used to define predicates over infinite lists. ω-programs allow us to specify properties of the infinite behavior of reactive systems and, in general, properties of infinite sequences of events. The semantics of ω-programs is an extension of the perfect model semantics. We present variants of the familiar unfold/fold rules which can be used for transforming ω-programs. We show that these new rules are correct, that is, their application preserves the perfect model semantics. Then we outline a general methodology based on program transformation for verifying properties of ω-programs. We demonstrate the power of our transformation-based verification methodology by proving some properties of Buechi automata and ω-regular languages.
Queue Length Asymptotics for Generalized Max-Weight Scheduling in the presence of Heavy-Tailed Traffic
Venue: arXiv cs.NI 2010
Year: 2010

We investigate the asymptotic behavior of the steady-state queue length distribution under generalized max-weight scheduling in the presence of heavy-tailed traffic. We consider a system consisting of two parallel queues, served by a single server. One of the queues receives heavy-tailed traffic, and the other receives light-tailed traffic. We study the class of throughput optimal max-weight-alpha scheduling policies, and derive an exact asymptotic characterization of the steady-state queue length distributions. In particular, we show that the tail of the light queue distribution is heavier than a power-law curve, whose tail coefficient we obtain explicitly. Our asymptotic characterization also contains an intuitively surprising result - the celebrated max-weight scheduling policy leads to the worst possible tail of the light queue distribution, among all non-idling policies. Motivated by the above negative result regarding the max-weight-alpha policy, we analyze a log-max-weight (LMW) scheduling policy. We show that the LMW policy guarantees an exponentially decaying light queue tail, while still being throughput optimal.
Properties of optimal prefix-free machines as instantaneous codes
Venue: arXiv cs.IT 2010
Year: 2010

The optimal prefix-free machine U is a universal decoding algorithm used to define the notion of program-size complexity H(s) for a finite binary string s. Since the set of all halting inputs for U is chosen to form a prefix-free set, the optimal prefix-free machine U can be regarded as an instantaneous code for noiseless source coding scheme. In this paper, we investigate the properties of optimal prefix-free machines as instantaneous codes. In particular, we investigate the properties of the set U^{-1}(s) of codewords associated with a symbol s. Namely, we investigate the number of codewords in U^{-1}(s) and the distribution of codewords in U^{-1}(s) for each symbol s, using the toolkit of algorithmic information theory.
Improving the Sphere-Packing Bound for Binary Codes over Memoryless Symmetric Channels
Venue: arXiv cs.IT 2010
Year: 2010

A lower bound on the minimum required code length of binary codes is obtained. The bound is obtained based on observing a close relation between the Ulam's liar game and channel coding. In fact, Spencer's optimal solution to the game is used to derive this new bound which improves the famous Sphere-Packing Bound.
FPGA Implementation of a Reconfigurable Viterbi Decoder for WiMAX Receiver
Venue: arXiv cs.AR 2010
Year: 2010

Field Programmable Gate Array technology (FPGA) is a highly configurable option for implementing many sophisticated signal processing tasks in Software Defined Radios (SDRs). Those types of radios are realized using highly configurable hardware platforms. Convolutional codes are used in every robust digital communication system and Viterbi algorithm is employed in wireless communications to decode the convolutional codes. Such decoders are complex and dissipate large amount of power. In this paper, a low power-reconfigurable Viterbi decoder for WiMAX receiver is described using a VHDL code for FPGA implementation. The proposed design is implemented on Xilinx Virtex-II Pro, XC2vpx30 FPGA using the FPGA Advantage Pro package provided by Mentor Graphics and ISE 10.1 by Xilinx.
Piecewise Convex-Concave Approximation in the $\ell_{\infty}$ Norm
Venue: arXiv cs.NA 2010
Year: 2010

Suppose that $\ff \in \reals^{n}$ is a vector of $n$ error-contaminated measurements of $n$ smooth values measured at distinct and strictly ascending abscissae. The following projective technique is proposed for obtaining a vector of smooth approximations to these values. Find \yy\ minimizing $\| \yy - \ff \|_{\infty}$ subject to the constraints that the second order consecutive divided differences of the components of \yy\ change sign at most $q$ times. This optimization problem (which is also of general geometrical interest) does not suffer from the disadvantage of the existence of purely local minima and allows a solution to be constructed in $O(nq)$ operations. A new algorithm for doing this is developed and its effectiveness is proved. Some of the results of applying it to undulating and peaky data are presented, showing that it is economical and can give very good results, particularly for large densely-packed data, even when the errors are quite large.
Gbits/s physical-layer stream ciphers based on chaotic light
Venue: arXiv cs.CR 2010
Year: 2010

We propose a novel high-speed stream cipher encryption scheme based on the true random key generated by a chaotic semiconductor laser. A 5-Gbits/s non-return-to-zero plaintext is successfully encrypted and decrypted using this cryptography. The scheme can be applied in the areas of real-time high-speed physical encryption.
Computational Complexity Analysis of Simple Genetic Programming On Two Problems Modeling Isolated Program Semantics
Venue: arXiv cs.NE 2010
Year: 2010

Analyzing the computational complexity of evolutionary algorithms for binary search spaces has significantly increased their theoretical understanding. With this paper, we start the computational complexity analysis of genetic programming. We set up several simplified genetic programming algorithms and analyze them on two separable model problems, ORDER and MAJORITY, each of which captures an important facet of typical genetic programming problems. Both analyses give first rigorous insights on aspects of genetic programming design, highlighting in particular the impact of accepting or rejecting neutral moves and the importance of a local mutation operator.
Braess's Paradox for Flows Over Time
Venue: arXiv cs.GT 2010
Year: 2010

We study the properties of Braess's paradox in the context of the model of congestion games with flow over time introduced by Koch and Skutella. We compare them to the well known properties of Braess's paradox for Wardrop's model of games with static flows. We show that there are networks which do not admit Braess's paradox in Wardrop's model, but which admit it in the model with flow over time. Moreover, there is a topology that admits a much more severe Braess's ratio for this model. Further, despite its symmetry for games with static flow, we show that Braess's paradox is not symmetric for flows over time. We illustrate that there are network topologies which exhibit Braess's paradox, but for which the transpose does not. Finally, we conjecture a necessary and sufficient condition of existence of Braess's paradox in a network, and prove the condition of existence of the paradox either in the network or in its transpose.
Automated Termination Analysis for Logic Programs with Cut
Venue: arXiv cs.LO 2010
Year: 2010

Termination is an important and well-studied property for logic programs. However, almost all approaches for automated termination analysis focus on definite logic programs, whereas real-world Prolog programs typically use the cut operator. We introduce a novel pre-processing method which automatically transforms Prolog programs into logic programs without cuts, where termination of the cut-free program implies termination of the original program. Hence after this pre-processing, any technique for proving termination of definite logic programs can be applied. We implemented this pre-processing in our termination prover AProVE and evaluated it successfully with extensive experiments.
Catching the Ouroboros: On Debugging Non-ground Answer-Set Programs
Venue: arXiv cs.PL 2010
Year: 2010

An important issue towards a broader acceptance of answer-set programming (ASP) is the deployment of tools which support the programmer during the coding phase. In particular, methods for debugging an answer-set program are recognised as a crucial step in this regard. Initial work on debugging in ASP mainly focused on propositional programs, yet practical debuggers need to handle programs with variables as well. In this paper, we discuss a debugging technique that is directly geared towards non-ground programs. Following previous work, we address the central debugging question why some interpretation is not an answer set. The explanations provided by our method are computed by means of a meta-programming technique, using a uniform encoding of a debugging request in terms of ASP itself. Our method also permits programs containing comparison predicates and integer arithmetics, thus covering a relevant language class commonly supported by all state-of-the-art ASP solvers.
Handling Data-Based Concurrency in Context-Aware Service Protocols
Venue: arXiv cs.SE 2010
Year: 2010

Dependency analysis is a technique to identify and determine data dependencies between service protocols. Protocols evolving concurrently in the service composition need to impose an order in their execution if there exist data dependencies. In this work, we describe a model to formalise context-aware service protocols. We also present a composition language to handle dynamically the concurrent execution of protocols. This language addresses data dependency issues among several protocols concurrently executed on the same user device, using mechanisms based on data semantic matching. Our approach aims at assisting the user in establishing priorities between these dependencies, avoiding the occurrence of deadlock situations. Nevertheless, this process is error-prone, since it requires human intervention. Therefore, we also propose verification techniques to automatically detect possible inconsistencies specified by the user while building the data dependency set. Our approach is supported by a prototype tool we have implemented.
Fully Dynamic Data Structure for Top-k Queries on Uncertain Data
Venue: arXiv cs.DB 2010
Year: 2010

Top-$k$ queries allow end-users to focus on the most important (top-$k$) answers amongst those which satisfy the query. In traditional databases, a user defined score function assigns a score value to each tuple and a top-$k$ query returns $k$ tuples with the highest score. In uncertain database, top-$k$ answer depends not only on the scores but also on the membership probabilities of tuples. Several top-$k$ definitions covering different aspects of score-probability interplay have been proposed in recent past~\cite{R10,R4,R2,R8}. Most of the existing work in this research field is focused on developing efficient algorithms for answering top-$k$ queries on static uncertain data. Any change (insertion, deletion of a tuple or change in membership probability, score of a tuple) in underlying data forces re-computation of query answers. Such re-computations are not practical considering the dynamic nature of data in many applications. In this paper, we propose a fully dynamic data structure that uses ranking function $PRF^e(α)$ proposed by Li et al.~\cite{R8} under the generally adopted model of $x$-relations~\cite{R11}. $PRF^e$ can effectively approximate various other top-$k$ definitions on uncertain data based on the value of parameter $α$. An $x$-relation consists of a number of $x$-tuples, where $x$-tuple is a set of mutually exclusive tuples (up to a constant number) called alternatives. Each $x$-tuple in a relation randomly instantiates into one tuple from its alternatives. For an uncertain relation with $N$ tuples, our structure can answer top-$k$ queries in $O(k\log N)$ time, handles an update in $O(\log N)$ time and takes $O(N)$ space. Finally, we evaluate practical efficiency of our structure on both synthetic and real data.
Reputation-Based Attack-Resistant Cooperation Stimulation (RACS) For Mobile Ad hoc Networks
Venue: arXiv cs.NI 2010
Year: 2010

In mobile ad hoc networks (MANET), nodes usually belong to different authorities and pursue different goals. In order to maximize their own performance, nodes in such networks tend to be selfish and are not willing to forward packets for benefit of others. Meanwhile, some nodes may behave maliciously and try to disrupt the network through wasting other nodes resources in a very large scale. In this article, we present a reputation-based attack resistant cooperation stimulation (RACS) system which ensures that damage caused by malicious nodes can be bounded and cooperation among the selfish nodes can be enforced. Mathematical analyses of the system as well as the simulation results have confirmed effectiveness of our proposed system. RACS is completely self-organizing and distributed. It does not require any tamper-proof hardware or central management policy.
Analysis of Frequency-Agile CSMA Wireless Networks
Venue: arXiv cs.NI 2010
Year: 2010

This paper proposes and analyzes the performance of a simple frequency-agile CSMA MAC protocol. In this MAC, a node carrier-senses multiple frequency channels simultaneously, and it takes the first opportunity to transmit on any one of the channels when allowed by the CSMA backoff mechanism. We show that the frequency-agile MAC can effectively 1) boost throughput and 2) remove temporal starvation. Furthermore, the MAC can be implemented on the existing multiple-frequency setup in Wi-Fi using multi-radio technology, and it can co-exist with the legacy MAC using single radio. This paper provides exact stationary throughput analysis for regular 1D and thin-strip 2D CSMA networks using a "transfer-matrix" approach. In addition, accurate approximations are given for 2D grid networks. Our closed-form formulas accurately quantify the throughput gain of frequency-agile CSMA. To characterize temporal starvation, we use the metric of "mean residual access time" (MRAT). Our simulations and closed-form approximations indicate that the frequency-agile MAC can totally eliminate temporal starvation in 2D grid networks, reducing its MRAT by orders of magnitude. Finally, this paper presents a "coloring theorem" to justify the use of the frequency-agile MAC in general network topologies. Our analysis and theorem suggest that with enough frequency channels, the frequency-agile MAC can effectively decouple the detrimental interactions between neighboring links responsible for low throughput and starvation.
The Value of Staying Current when Beamforming
Venue: arXiv cs.IT 2010
Year: 2010

Beamforming is a widely used method of provisioning high quality wireless channels that leads to high data rates and simple decoding structures. It requires feedback of Channel State Information (CSI) from receiver to transmitter, and the accuracy of this information is limited by rate constraints on the feedback channel and by delay. It is important to understand how the performance gains associated with beamforming depend on the accuracy or currency of the Channel State Information. This paper quantifies performance degradation caused by aging of CSI. It uses outage probability to measure the currency of CSI, and to discount the performance gains associated with ideal beamforming. Outage probability is a function of the beamforming algorithm and results are presented for Transmit Antenna Selection and other widely used methods. These results are translated into effective diversity orders for Multiple Input Single Output (MISO) and Multiuser Multiple Input Multiple Output (MIMO) systems.
Parallel and distributed Gröbner bases computation in JAS
Venue: arXiv cs.DC 2010
Year: 2010

This paper considers parallel Gröbner bases algorithms on distributed memory parallel computers with multi-core compute nodes. We summarize three different Gröbner bases implementations: shared memory parallel, pure distributed memory parallel and distributed memory combined with shared memory parallelism. The last algorithm, called distributed hybrid, uses only one control communication channel between the master node and the worker nodes and keeps polynomials in shared memory on a node. The polynomials are transported asynchronous to the control-flow of the algorithm in a separate distributed data structure. The implementation is generic and works for all implemented (exact) fields. We present new performance measurements and discuss the performance of the algorithms.
Weblog patterns and human dynamics with decreasing interest
Venue: arXiv cs.SI 2010
Year: 2010

Weblog is the fourth way of network exchange after Email, BBS and MSN. Most bloggers begin to write blogs with great interest, and then their interests gradually achieve a balance with the passage of time. In order to describe the phenomenon that people's interest in something gradually decreases until it reaches a balance, we first propose the model that describes the attenuation of interest and reflects the fact that people's interest becomes more stable after a long time. We give a rigorous analysis on this model by non-homogeneous Poisson processes. Our analysis indicates that the interval distribution of arrival-time is a mixed distribution with exponential and power-law feature, that is, it is a power law with an exponential cutoff. Second, we collect blogs in ScienceNet.cn and carry on empirical studies on the interarrival time distribution. The empirical results agree well with the analytical result, obeying a special power law with the exponential cutoff, that is, a special kind of Gamma distribution. These empirical results verify the model, providing an evidence for a new class of phenomena in human dynamics. In human dynamics there are other distributions, besides power-law distributions. These findings demonstrate the variety of human behavior dynamics.
Universal and Robust Distributed Network Codes
Venue: arXiv cs.IT 2010
Year: 2010

Random linear network codes can be designed and implemented in a distributed manner, with low computational complexity. However, these codes are classically implemented over finite fields whose size depends on some global network parameters (size of the network, the number of sinks) that may not be known prior to code design. Also, if new nodes join the entire network code may have to be redesigned. In this work, we present the first universal and robust distributed linear network coding schemes. Our schemes are universal since they are independent of all network parameters. They are robust since if nodes join or leave, the remaining nodes do not need to change their coding operations and the receivers can still decode. They are distributed since nodes need only have topological information about the part of the network upstream of them, which can be naturally streamed as part of the communication protocol. We present both probabilistic and deterministic schemes that are all asymptotically rate-optimal in the coding block-length, and have guarantees of correctness. Our probabilistic designs are computationally efficient, with order-optimal complexity. Our deterministic designs guarantee zero error decoding, albeit via codes with high computational complexity in general. Our coding schemes are based on network codes over ``scalable fields". Instead of choosing coding coefficients from one field at every node, each node uses linear coding operations over an ``effective field-size" that depends on the node's distance from the source node. The analysis of our schemes requires technical tools that may be of independent interest. In particular, we generalize the Schwartz-Zippel lemma by proving a non-uniform version, wherein variables are chosen from sets of possibly different sizes. We also provide a novel robust distributed algorithm to assign unique IDs to network nodes.