OpenRaiser/Intern-Atlas huggingface dataset:
A Communication Model for Adaptive Service Provisioning in Hybrid Wireless Networks
Venue: arXiv cs.NI 2007
Year: 2007

Mobile entities with wireless links are able to form a mobile ad-hoc network. Such an infrastructureless network does not have to be administrated. However, self-organizing principles have to be applied to deal with upcoming problems, e.g. information dissemination. These kinds of problems are not easy to tackle, requiring complex algorithms. Moreover, the usefulness of pure ad-hoc networks is arguably limited. Hence, enthusiasm for mobile ad-hoc networks, which could eliminate the need for any fixed infrastructure, has been damped. The goal is to overcome the limitations of pure ad-hoc networks by augmenting them with instant Internet access, e.g. via integration of UMTS respectively GSM links. However, this raises multiple questions at the technical as well as the organizational level. Motivated by characteristics of small-world networks that describe an efficient network even without central or organized design, this paper proposes to combine mobile ad-hoc networks and infrastructured networks to form hybrid wireless networks. One main objective is to investigate how this approach can reduce the costs of a permanent backbone link and providing in the same way the benefits of useful information from Internet connectivity or service providers. For the purpose of bridging between the different types of networks, an adequate middleware service is the focus of our investigation. This paper shows our first steps forward to this middleware by introducing the Injection Communication paradigm as principal concept.
VPSPACE and a transfer theorem over the complex field
Venue: arXiv cs.CC 2007
Year: 2007

We extend the transfer theorem of [KP2007] to the complex field. That is, we investigate the links between the class VPSPACE of families of polynomials and the Blum-Shub-Smale model of computation over C. Roughly speaking, a family of polynomials is in VPSPACE if its coefficients can be computed in polynomial space. Our main result is that if (uniform, constant-free) VPSPACE families can be evaluated efficiently then the class PAR of decision problems that can be solved in parallel polynomial time over the complex field collapses to P. As a result, one must first be able to show that there are VPSPACE families which are hard to evaluate in order to separate P from NP over C, or even from PAR.
Non-Cooperative Scheduling of Multiple Bag-of-Task Applications
Venue: arXiv cs.DC 2007
Year: 2007

Multiple applications that execute concurrently on heterogeneous platforms compete for CPU and network resources. In this paper we analyze the behavior of $K$ non-cooperative schedulers using the optimal strategy that maximize their efficiency while fairness is ensured at a system level ignoring applications characteristics. We limit our study to simple single-level master-worker platforms and to the case where each scheduler is in charge of a single application consisting of a large number of independent tasks. The tasks of a given application all have the same computation and communication requirements, but these requirements can vary from one application to another. In this context, we assume that each scheduler aims at maximizing its throughput. We give closed-form formula of the equilibrium reached by such a system and study its performance. We characterize the situations where this Nash equilibrium is optimal (in the Pareto sense) and show that even though no catastrophic situation (Braess-like paradox) can occur, such an equilibrium can be arbitrarily bad for any classical performance measure.
On the growth of components with non fixed excesses
Venue: arXiv cs.DM 2007
Year: 2007

Denote by an $l$-component a connected graph with $l$ edges more than vertices. We prove that the expected number of creations of $(l+1)$-component, by means of adding a new edge to an $l$-component in a randomly growing graph with $n$ vertices, tends to 1 as $l,n$ tends to $\infty$ but with $l = o(n^{1/4})$. We also show, under the same conditions on $l$ and $n$, that the expected number of vertices that ever belong to an $l$-component is $\sim (12l)^{1/3} n^{2/3}$.
Information Criteria and Arithmetic Codings : An Illustration on Raw Images
Venue: arXiv cs.IT 2007
Year: 2007

In this paper we give a short theoretical description of the general predictive adaptive arithmetic coding technique. The links between this technique and the works of J. Rissanen in the 80's, in particular the BIC information criterion used in parametrical model selection problems, are established. We also design lossless and lossy coding techniques of images. The lossless technique uses a mix between fixed-length coding and arithmetic coding and provides better compression results than those separate methods. That technique is also seen to have an interesting application in the domain of statistics since it gives a data-driven procedure for the non-parametrical histogram selection problem. The lossy technique uses only predictive adaptive arithmetic codes and shows how a good choice of the order of prediction might lead to better results in terms of compression. We illustrate those coding techniques on a raw grayscale image.
FreeBSD Mandatory Access Control Usage for Implementing Enterprise Security Policies
Venue: arXiv cs.CR 2007
Year: 2007

FreeBSD was one of the first widely deployed free operating systems to provide mandatory access control. It supports a number of classic MAC models. This tutorial paper addresses exploiting this implementation to enforce typical enterprise security policies of varying complexities.
How to measure efficiency?
Venue: arXiv cs.GT 2007
Year: 2007

In the context of applied game theory in networking environments, a number of concepts have been proposed to measure both efficiency and optimality of resource allocations, the most famous certainly being the price of anarchy and the Jain index. Yet, very few have tried to question these measures and compare them one to another, in a general framework, which is the aim of the present article.
FIPA-based Interoperable Agent Mobility Proposal
Venue: arXiv cs.MA 2007
Year: 2007

This paper presents a proposal for a flexible agent mobility architecture based on IEEE-FIPA standards and intended to be one of them. This proposal is a first step towards interoperable mobility mechanisms, which are needed for future agent migration between different kinds of platforms. Our proposal is presented as a flexible and robust architecture that has been successfully implemented in the JADE and AgentScape platforms. It is based on an open set of protocols, allowing new protocols and future improvements to be accommodated in the architecture. With this proposal we demonstrate that a standard architecture for agent mobility capable of supporting several agent platforms can be defined and implemented.
Power Allocation for Discrete-Input Delay-Limited Fading Channels
Venue: arXiv cs.IT 2007
Year: 2007

We consider power allocation algorithms for fixed-rate transmission over Nakagami-m non-ergodic block-fading channels with perfect transmitter and receiver channel state information and discrete input signal constellations, under both short- and long-term power constraints. Optimal power allocation schemes are shown to be direct applications of previous results in the literature. We show that the SNR exponent of the optimal short-term scheme is given by m times the Singleton bound. We also illustrate the significant gains available by employing long-term power constraints. In particular, we analyze the optimal long-term solution, showing that zero outage can be achieved provided that the corresponding short-term SNR exponent with the same system parameters is strictly greater than one. Conversely, if the short-term SNR exponent is smaller than one, we show that zero outage cannot be achieved. In this case, we derive the corresponding long-term SNR exponent as a function of the Singleton bound. Due to the nature of the expressions involved, the complexity of optimal schemes may be prohibitive for system implementation. We therefore propose simple sub-optimal power allocation schemes whose outage probability performance is very close to the minimum outage probability obtained by optimal schemes. We also show the applicability of these techniques to practical systems employing orthogonal frequency division multiplexing.
Building Portable Thread Schedulers for Hierarchical Multiprocessors: the BubbleSched Framework
Venue: arXiv cs.DC 2007
Year: 2007

Exploiting full computational power of current more and more hierarchical multiprocessor machines requires a very careful distribution of threads and data among the underlying non-uniform architecture. Unfortunately, most operating systems only provide a poor scheduling API that does not allow applications to transmit valuable scheduling hints to the system. In a previous paper, we showed that using a bubble-based thread scheduler can significantly improve applications' performance in a portable way. However, since multithreaded applications have various scheduling requirements, there is no universal scheduler that could meet all these needs. In this paper, we present a framework that allows scheduling experts to implement and experiment with customized thread schedulers. It provides a powerful API for dynamically distributing bubbles among the machine in a high-level, portable, and efficient way. Several examples show how experts can then develop, debug and tune their own portable bubble schedulers.
Efficient Multidimensional Data Redistribution for Resizable Parallel Computations
Venue: arXiv cs.DC 2007
Year: 2007

Traditional parallel schedulers running on cluster supercomputers support only static scheduling, where the number of processors allocated to an application remains fixed throughout the execution of the job. This results in under-utilization of idle system resources thereby decreasing overall system throughput. In our research, we have developed a prototype framework called ReSHAPE, which supports dynamic resizing of parallel MPI applications executing on distributed memory platforms. The resizing library in ReSHAPE includes support for releasing and acquiring processors and efficiently redistributing application state to a new set of processors. In this paper, we derive an algorithm for redistributing two-dimensional block-cyclic arrays from $P$ to $Q$ processors, organized as 2-D processor grids. The algorithm ensures a contention-free communication schedule for data redistribution if $P_r \leq Q_r$ and $P_c \leq Q_c$. In other cases, the algorithm implements circular row and column shifts on the communication schedule to minimize node contention.
Resource control of object-oriented programs
Venue: arXiv cs.PL 2007
Year: 2007

A sup-interpretation is a tool which provides an upper bound on the size of a value computed by some symbol of a program. Sup-interpretations have shown their interest to deal with the complexity of first order functional programs. For instance, they allow to characterize all the functions bitwise computable in Alogtime. This paper is an attempt to adapt the framework of sup-interpretations to a fragment of oriented-object programs, including distinct encodings of numbers through the use of constructor symbols, loop and while constructs and non recursive methods with side effects. We give a criterion, called brotherly criterion, which ensures that each brotherly program computes objects whose size is polynomially bounded by the inputs sizes.
Space-time coding techniques with bit-interleaved coded modulations for MIMO block-fading channels
Venue: arXiv cs.IT 2007
Year: 2007

The space-time bit-interleaved coded modulation (ST-BICM) is an efficient technique to obtain high diversity and coding gain on a block-fading MIMO channel. Its maximum-likelihood (ML) performance is computed under ideal interleaving conditions, which enables a global optimization taking into account channel coding. Thanks to a diversity upperbound derived from the Singleton bound, an appropriate choice of the time dimension of the space-time coding is possible, which maximizes diversity while minimizing complexity. Based on the analysis, an optimized interleaver and a set of linear precoders, called dispersive nucleo algebraic (DNA) precoders are proposed. The proposed precoders have good performance with respect to the state of the art and exist for any number of transmit antennas and any time dimension. With turbo codes, they exhibit a frame error rate which does not increase with frame length.
A new lower bound on the independence number of a graph
Venue: arXiv cs.DM 2007
Year: 2007

For a given connected graph G on n vertices and m edges, we prove that its independence number is at least (2m+n+2-sqrt(sqr(2m+n+2)-16sqr(n)))/8.
The Complexity of Determining Existence a Hamiltonian Cycle is $O(n^3)$
Venue: arXiv cs.DS 2007
Year: 2007

The Hamiltonian cycle problem in digraph is mapped into a matching cover bipartite graph. Based on this mapping, it is proved that determining existence a Hamiltonian cycle in graph is $O(n^3)$.
Abstract Storage Devices
Venue: arXiv cs.DM 2007
Year: 2007

A quantum storage device differs radically from a conventional physical storage device. Its state can be set to any value in a certain (infinite) state space, but in general every possible read operation yields only partial information about the stored state. The purpose of this paper is to initiate the study of a combinatorial abstraction, called abstract storage device (ASD), which models deterministic storage devices with the property that only partial information about the state can be read, but that there is a degree of freedom as to which partial information should be retrieved. This concept leads to a number of interesting problems which we address, like the reduction of one device to another device, the equivalence of devices, direct products of devices, as well as the factorization of a device into primitive devices. We prove that every ASD has an equivalent ASD with minimal number of states and of possible read operations. Also, we prove that the reducibility problem for ASD's is NP-complete, that the equivalence problem is at least as hard as the graph isomorphism problem, and that the factorization into binary-output devices (if it exists) is unique.
Cache Analysis of Non-uniform Distribution Sorting Algorithms
Venue: arXiv cs.DS 2007
Year: 2007

We analyse the average-case cache performance of distribution sorting algorithms in the case when keys are independently but not necessarily uniformly distributed. The analysis is for both `in-place' and `out-of-place' distribution sorting algorithms and is more accurate than the analysis presented in \cite{RRESA00}. In particular, this new analysis yields tighter upper and lower bounds when the keys are drawn from a uniform distribution. We use this analysis to tune the performance of the integer sorting algorithm MSB radix sort when it is used to sort independent uniform floating-point numbers (floats). Our tuned MSB radix sort algorithm comfortably outperforms a cache-tuned implementations of bucketsort \cite{RR99} and Quicksort when sorting uniform floats from $[0, 1)$.
Application of a design space exploration tool to enhance interleaver generation
Venue: arXiv cs.AR 2007
Year: 2007

This paper presents a methodology to efficiently explore the design space of communication adapters. In most digital signal processing (DSP) applications, the overall performance of the system is significantly affected by communication architectures, as a consequence the designers need specifically optimized adapters. By explicitly modeling these communications within an effective graph-theoretic model and analysis framework, we automatically generate an optimized architecture, named Space-Time AdapteR (STAR). Our design flow inputs a C description of Input/Output data scheduling, and user requirements (throughput, latency, parallelism...), and formalizes communication constraints through a Resource Constraints Graph (RCG). Design space exploration is then performed through associated tools, to synthesize a STAR component under time-to-market constraints. The proposed approach has been tested to design an industrial data mixing block example: an Ultra-Wideband interleaver.
EasyVoice: Integrating voice synthesis with Skype
Venue: arXiv cs.CY 2007
Year: 2007

This paper presents EasyVoice, a system that integrates voice synthesis with Skype. EasyVoice allows a person with voice disabilities to talk with another person located anywhere in the world, removing an important obstacle that affect these people during a phone or VoIP-based conversation.
NP by means of lifts and shadows
Venue: arXiv cs.CC 2007
Year: 2007

We show that every NP problem is polynomially equivalent to a simple combinatorial problem: the membership problem for a special class of digraphs. These classes are defined by means of shadows (projections) and by finitely many forbidden colored (lifted) subgraphs. Our characterization is motivated by the analysis of syntactical subclasses with the full computational power of NP, which were first studied by Feder and Vardi. Our approach applies to many combinatorial problems and it induces the characterization of coloring problems (CSP) defined by means of shadows. This turns out to be related to homomorphism dualities. We prove that a class of digraphs (relational structures) defined by finitely many forbidden colored subgraphs (i.e. lifted substructures) is a CSP class if and only if all the the forbidden structures are homomorphically equivalent to trees. We show a surprising richness of coloring problems when restricted to most frequent graph classes. Using results of Nešetřil and Ossona de Mendez for bounded expansion classes (which include bounded degree and proper minor closed classes) we prove that the restriction of every class defined as the shadow of finitely many colored subgraphs equals to the restriction of a coloring (CSP) class.
There Exist some Omega-Powers of Any Borel Rank
Venue: arXiv cs.LO 2007
Year: 2007

Omega-powers of finitary languages are languages of infinite words (omega-languages) in the form V^omega, where V is a finitary language over a finite alphabet X. They appear very naturally in the characterizaton of regular or context-free omega-languages. Since the set of infinite words over a finite alphabet X can be equipped with the usual Cantor topology, the question of the topological complexity of omega-powers of finitary languages naturally arises and has been posed by Niwinski (1990), Simonnet (1992) and Staiger (1997). It has been recently proved that for each integer n > 0, there exist some omega-powers of context free languages which are Pi^0_n-complete Borel sets, that there exists a context free language L such that L^omega is analytic but not Borel, and that there exists a finitary language V such that V^omega is a Borel set of infinite rank. But it was still unknown which could be the possible infinite Borel ranks of omega-powers. We fill this gap here, proving the following very surprising result which shows that omega-powers exhibit a great topological complexity: for each non-null countable ordinal alpha, there exist some Sigma^0_alpha-complete omega-powers, and some Pi^0_alpha-complete omega-powers.
Opportunistic Scheduling and Beamforming for MIMO-SDMA Downlink Systems with Linear Combining
Venue: arXiv cs.IT 2007
Year: 2007

Opportunistic scheduling and beamforming schemes are proposed for multiuser MIMO-SDMA downlink systems with linear combining in this work. Signals received from all antennas of each mobile terminal (MT) are linearly combined to improve the {\em effective} signal-to-noise-interference ratios (SINRs). By exploiting limited feedback on the effective SINRs, the base station (BS) schedules simultaneous data transmission on multiple beams to the MTs with the largest effective SINRs. Utilizing the extreme value theory, we derive the asymptotic system throughputs and scaling laws for the proposed scheduling and beamforming schemes with different linear combining techniques. Computer simulations confirm that the proposed schemes can substantially improve the system throughput.
A Comparison of Push and Pull Techniques for Ajax
Venue: arXiv cs.SE 2007
Year: 2007

Ajax applications are designed to have high user interactivity and low user-perceived latency. Real-time dynamic web data such as news headlines, stock tickers, and auction updates need to be propagated to the users as soon as possible. However, Ajax still suffers from the limitations of the Web's request/response architecture which prevents servers from pushing real-time dynamic web data. Such applications usually use a pull style to obtain the latest updates, where the client actively requests the changes based on a predefined interval. It is possible to overcome this limitation by adopting a push style of interaction where the server broadcasts data when a change occurs on the server side. Both these options have their own trade-offs. This paper explores the fundamental limits of browser-based applications and analyzes push solutions for Ajax technology. It also shows the results of an empirical study comparing push and pull.
Encounter-based worms: Analysis and Defense
Venue: arXiv cs.NI 2007
Year: 2007

Encounter-based network is a frequently-disconnected wireless ad-hoc network requiring immediate neighbors to store and forward aggregated data for information disseminations. Using traditional approaches such as gateways or firewalls for deterring worm propagation in encounter-based networks is inappropriate. We propose the worm interaction approach that relies upon automated beneficial worm generation aiming to alleviate problems of worm propagations in such networks. To understand the dynamic of worm interactions and its performance, we mathematically model worm interactions based on major worm interaction factors including worm interaction types, network characteristics, and node characteristics using ordinary differential equations and analyze their effects on our proposed metrics. We validate our proposed model using extensive synthetic and trace-driven simulations. We find that, all worm interaction factors significantly affect the pattern of worm propagations. For example, immunization linearly decreases the infection of susceptible nodes while on-off behavior only impacts the duration of infection. Using realistic mobile network measurements, we find that encounters are bursty, multi-group and non-uniform. The trends from the trace-driven simulations are consistent with the model, in general. Immunization and timely deployment seem to be the most effective to counter the worm attacks in such scenarios while cooperation may help in a specific case. These findings provide insight that we hope would aid to develop counter-worm protocols in future encounter-based networks.
Scheduling multiple divisible loads on a linear processor network
Venue: arXiv cs.DC 2007
Year: 2007

Min, Veeravalli, and Barlas have recently proposed strategies to minimize the overall execution time of one or several divisible loads on a heterogeneous linear network, using one or more installments. We show on a very simple example that their approach does not always produce a solution and that, when it does, the solution is often suboptimal. We also show how to find an optimal schedule for any instance, once the number of installments per load is given. Then, we formally state that any optimal schedule has an infinite number of installments under a linear cost model as the one assumed in the original papers. Therefore, such a cost model cannot be used to design practical multi-installment strategies. Finally, through extensive simulations we confirmed that the best solution is always produced by the linear programming approach, while solutions of the original papers can be far away from the optimal.