OpenRaiser/Intern-Atlas huggingface dataset:
Temporal Logics on Words with Multiple Data Values
Venue: arXiv cs.LO 2010
Year: 2010

The paper proposes and studies temporal logics for attributed words, that is, data words with a (finite) set of (attribute,value)-pairs at each position. It considers a basic logic which is a semantical fragment of the logic $LTL^\downarrow_1$ of Demri and Lazic with operators for navigation into the future and the past. By reduction to the emptiness problem for data automata it is shown that this basic logic is decidable. Whereas the basic logic only allows navigation to positions where a fixed data value occurs, extensions are studied that also allow navigation to positions with different data values. Besides some undecidable results it is shown that the extension by a certain UNTIL-operator with an inequality target condition remains decidable.
Optimal Packet Scheduling in an Energy Harvesting Communication System
Venue: arXiv cs.IT 2010
Year: 2010

We consider the optimal packet scheduling problem in a single-user energy harvesting wireless communication system. In this system, both the data packets and the harvested energy are modeled to arrive at the source node randomly. Our goal is to adaptively change the transmission rate according to the traffic load and available energy, such that the time by which all packets are delivered is minimized. Under a deterministic system setting, we assume that the energy harvesting times and harvested energy amounts are known before the transmission starts. For the data traffic arrivals, we consider two different scenarios. In the first scenario, we assume that all bits have arrived and are ready at the transmitter before the transmission starts. In the second scenario, we consider the case where packets arrive during the transmissions, with known arrival times and sizes. We develop optimal off-line scheduling policies which minimize the time by which all packets are delivered to the destination, under causality constraints on both data and energy arrivals.
Typicality Graphs:Large Deviation Analysis
Venue: arXiv cs.IT 2010
Year: 2010

Let $\mathcal{X}$ and $\mathcal{Y}$ be finite alphabets and $P_{XY}$ a joint distribution over them, with $P_X$ and $P_Y$ representing the marginals. For any $ε> 0$, the set of $n$-length sequences $x^n$ and $y^n$ that are jointly typical \cite{ckbook} according to $P_{XY}$ can be represented on a bipartite graph. We present a formal definition of such a graph, known as a \emph{typicality} graph, and study some of its properties.
Coalition Formation Games for Distributed Cooperation Among Roadside Units in Vehicular Networks
Venue: arXiv cs.IT 2010
Year: 2010

Vehicle-to-roadside (V2R) communications enable vehicular networks to support a wide range of applications for enhancing the efficiency of road transportation. While existing work focused on non-cooperative techniques for V2R communications between vehicles and roadside units (RSUs), this paper investigates novel cooperative strategies among the RSUs in a vehicular network. We propose a scheme whereby, through cooperation, the RSUs in a vehicular network can coordinate the classes of data being transmitted through V2R communications links to the vehicles. This scheme improves the diversity of the information circulating in the network while exploiting the underlying content-sharing vehicle-to-vehicle communication network. We model the problem as a coalition formation game with transferable utility and we propose an algorithm for forming coalitions among the RSUs. For coalition formation, each RSU can take an individual decision to join or leave a coalition, depending on its utility which accounts for the generated revenues and the costs for coalition coordination. We show that the RSUs can self-organize into a Nash-stable partition and adapt this partition to environmental changes. Simulation results show that, depending on different scenarios, coalition formation presents a performance improvement, in terms of the average payoff per RSU, ranging between 20.5% and 33.2%, relative to the non-cooperative case.
A Hybrid Parallelization of AIM for Multi-Core Clusters: Implementation Details and Benchmark Results on Ranger
Venue: arXiv cs.CE 2010
Year: 2010

This paper presents implementation details and empirical results for a hybrid message passing and shared memory paralleliziation of the adaptive integral method (AIM). AIM is implemented on a (near) petaflop supercomputing cluster of quad-core processors and its accuracy, complexity, and scalability are investigated by solving benchmark scattering problems. The timing and speedup results on up to 1024 processors show that the hybrid MPI/OpenMP parallelization of AIM exhibits better strong scalability (fixed problem size speedup) than pure MPI parallelization of it when multiple cores are used on each processor.
Real-Time Multi-path Tracking of Probabilistic Available Bandwidth
Venue: arXiv cs.NI 2010
Year: 2010

Applications such as traffic engineering and network provisioning can greatly benefit from knowing, in real time, what is the largest input rate at which it is possible to transmit on a given path without causing congestion. We consider a probabilistic formulation for available bandwidth where the user specifies the probability of achieving an output rate almost as large as the input rate. We are interested in estimating and tracking the network-wide probabilistic available bandwidth (PAB) on multiple paths simultaneously with minimal overhead on the network. We propose a novel framework based on chirps, Bayesian inference, belief propagation and active sampling to estimate the PAB. We also consider the time evolution of the PAB by forming a dynamic model and designing a tracking algorithm based on particle filters. We implement our method in a lightweight and practical tool that has been deployed on the PlanetLab network to do online experiments. We show through these experiments and simulations that our approach outperforms block-based algorithms in terms of input rate cost and probability of successful transmission.
Large-System Analysis of Multiuser Detection with an Unknown Number of Users: A High-SNR Approach
Venue: arXiv cs.IT 2010
Year: 2010

We analyze multiuser detection under the assumption that the number of users accessing the channel is unknown by the receiver. In this environment, users' activity must be estimated along with any other parameters such as data, power, and location. Our main goal is to determine the performance loss caused by the need for estimating the identities of active users, which are not known a priori. To prevent a loss of optimality, we assume that identities and data are estimated jointly, rather than in two separate steps. We examine the performance of multiuser detectors when the number of potential users is large. Statistical-physics methodologies are used to determine the macroscopic performance of the detector in terms of its multiuser efficiency. Special attention is paid to the fixed-point equation whose solution yields the multiuser efficiency of the optimal (maximum a posteriori) detector in the large signal-to-noise ratio regime. Our analysis yields closed-form approximate bounds to the minimum mean-squared error in this regime. These illustrate the set of solutions of the fixed-point equation, and their relationship with the maximum system load. Next, we study the maximum load that the detector can support for a given quality of service (specified by error probability).
Inner Product Spaces for MinSum Coordination Mechanisms
Venue: arXiv cs.GT 2010
Year: 2010

We study policies aiming to minimize the weighted sum of completion times of jobs in the context of coordination mechanisms for selfish scheduling problems. Our goal is to design local policies that achieve a good price of anarchy in the resulting equilibria for unrelated machine scheduling. To obtain the approximation bounds, we introduce a new technique that while conceptually simple, seems to be quite powerful. With this method we are able to prove the following results. First, we consider Smith's Rule, which orders the jobs on a machine in ascending processing time to weight ratio, and show that it achieves an approximation ratio of 4. We also demonstrate that this is the best possible for deterministic non-preemptive strongly local policies. Since Smith's Rule is always optimal for a given assignment, this may seem unsurprising, but we then show that better approximation ratios can be obtained if either preemption or randomization is allowed. We prove that ProportionalSharing, a preemptive strongly local policy, achieves an approximation ratio of 2.618 for the weighted sum of completion times, and an approximation ratio of 2.5 in the unweighted case. Again, we observe that these bounds are tight. Next, we consider Rand, a natural non-preemptive but randomized policy. We show that it achieves an approximation ratio of at most 2.13; moreover, if the sum of the weighted completion times is negligible compared to the cost of the optimal solution, this improves to π/2. Finally, we show that both ProportionalSharing and Rand induce potential games, and thus always have a pure Nash equilibrium (unlike Smith's Rule). This also allows us to design the first \emph{combinatorial} constant-factor approximation algorithm minimizing weighted completion time for unrelated machine scheduling that achieves a factor of 2+ εfor any ε> 0.
Weighted Indices for Evaluating the Quality of Research with Multiple Authorship
Venue: arXiv cs.IR 2010
Year: 2010

Devising an index to measure the quality of research is a challenging task. In this paper, we propose a set of indices to evaluate the quality of research produced by an author. Our indices utilize a policy that assigns the weights to multiple authors of a paper. We have considered two weight assignment policies: positionally weighted and equally weighted. We propose two classes of weighted indices: weighted h-indices and weighted citation h-cuts. Further, we compare our weighted h-indices with the original h-index for a selected set of authors. As opposed to h-index, our weighted h-indices take into account the weighted contributions of individual authors in multi-authored papers, and may serve as an improvement over h-index. The other class of weighted indices that we call weighted citation h-cuts take into account the number of citations that are in excess of those required to compute the index, and may serve as a supplement to h-index or its variants.
On a Low-Rate TLDPC Code Ensemble and the Necessary Condition on the Linear Minimum Distance for Sparse-Graph Codes
Venue: arXiv cs.IT 2010
Year: 2010

This paper addresses the issue of design of low-rate sparse-graph codes with linear minimum distance in the blocklength. First, we define a necessary condition which needs to be satisfied when the linear minimum distance is to be ensured. The condition is formulated in terms of degree-1 and degree-2 variable nodes and of low-weight codewords of the underlying code, and it generalizies results known for turbo codes [8] and LDPC codes. Then, we present a new ensemble of low-rate codes, which itself is a subclass of TLDPC codes [4], [5], and which is designed under this necessary condition. The asymptotic analysis of the ensemble shows that its iterative threshold is situated close to the Shannon limit. In addition to the linear minimum distance property, it has a simple structure and enjoys a low decoding complexity and a fast convergence.
A Critical Path Approach to Analyzing Parallelism of Algorithmic Variants. Application to Cholesky Inversion
Venue: arXiv cs.DC 2010
Year: 2010

Algorithms come with multiple variants which are obtained by changing the mathematical approach from which the algorithm is derived. These variants offer a wide spectrum of performance when implemented on a multicore platform and we seek to understand these differences in performances from a theoretical point of view. To that aim, we derive and present the critical path lengths of each algorithmic variant for our application problem which enables us to determine a lower bound on the time to solution. This metric provides an intuitive grasp of the performance of a variant and we present numerical experiments to validate the tightness of our lower bounds on practical applications. Our case study is the Cholesky inversion and its use in computing the inverse of a symmetric positive definite matrix.
On Finding Similar Items in a Stream of Transactions
Venue: arXiv cs.DS 2010
Year: 2010

While there has been a lot of work on finding frequent itemsets in transaction data streams, none of these solve the problem of finding similar pairs according to standard similarity measures. This paper is a first attempt at dealing with this, arguably more important, problem. We start out with a negative result that also explains the lack of theoretical upper bounds on the space usage of data mining algorithms for finding frequent itemsets: Any algorithm that (even only approximately and with a chance of error) finds the most frequent k-itemset must use space Omega(min{mb,n^k,(mb/phi)^k}) bits, where mb is the number of items in the stream so far, n is the number of distinct items and phi is a support threshold. To achieve any non-trivial space upper bound we must thus abandon a worst-case assumption on the data stream. We work under the model that the transactions come in random order, and show that surprisingly, not only is small-space similarity mining possible for the most common similarity measures, but the mining accuracy improves with the length of the stream for any fixed support threshold.
Partition Refinement of Component Interaction Automata: Why Structure Matters More Than Size
Venue: arXiv cs.SE 2010
Year: 2010

Automata-based modeling languages, like Component Interaction Automata, offer an attractive means to capture and analyze the behavioral aspects of interacting components. At the center of these modeling languages we find finite state machines that allow for a fine-grained description how and when specific service requests may interact with other components or the environment. Unfortunately, automata-based approaches suffer from exponential state explosion, a major obstacle to the successful application of these formalisms in modeling real-world scenarios. In order to cope with the complexity of individual specifications we can apply partition refinement, an abstraction technique to alleviate the state explosion problem. But this technique too exhibits exponential time and space complexity and, worse, does not offer any guarantees for success. To better understand as to why partition refinement succeeds in some cases while it fails in others, we conducted an empirical study on the performance of a partition refinement algorithm for Component Interaction Automata specifications. As a result we have identified suitable predictors for the expected effectiveness of partition refinement. It is the structure, not the size, of a specification that weighs heavier on the outcome of partition refinement. In particular, Component Interaction Automata specifications for real-world systems are capable of producing scale-free networks containing structural artifacts that can assist the partition refinement algorithm not only converge earlier, but also yield a significant state space reduction on occasion.
Behavioural Models for Group Communications
Venue: arXiv cs.DC 2010
Year: 2010

Group communication is becoming a more and more popular infrastructure for efficient distributed applications. It consists in representing locally a group of remote objects as a single object accessed in a single step; communications are then broadcasted to all members. This paper provides models for automatic verification of group-based applications, typically for detecting deadlocks or checking message ordering. We show how to encode group communication, together with different forms of synchronisation for group results. The proposed models are parametric such that, for example, different group sizes or group members could be experimented with the minimum modification of the original model.
Estimation and Registration on Graphs
Venue: arXiv cs.NI 2010
Year: 2010

A statistical framework is introduced for a broad class of problems involving synchronization or registration of data across a sensor network in the presence of noise. This framework enables an estimation-theoretic approach to the design and characterization of synchronization algorithms. The Fisher information is expressed in terms of the distribution of the measurement noise and standard mathematical descriptors of the network's graph structure for several important cases. This leads to maximum likelihood and approximate maximum-likelihood registration algorithms and also to distributed iterative algorithms that, when they converge, attain statistically optimal solutions. The relationship between optimal estimation in this setting and Kirchhoff's laws is also elucidated.
On Powers of Gaussian White Noise
Venue: arXiv cs.IT 2010
Year: 2010

Classical Gaussian white noise in communications and signal processing is viewed as the limit of zero mean second order Gaussian processes with a compactly supported flat spectral density as the support goes to infinity. The difficulty of developing a theory to deal with nonlinear transformations of white noise has been to interpret the corresponding limits. In this paper we show that a renormalization and centering of powers of band-limited Gaussian processes is Gaussian white noise and as a consequence, homogeneous polynomials under suitable renormalization remain white noises.
Broadcasting with an Energy Harvesting Rechargeable Transmitter
Venue: arXiv cs.IT 2010
Year: 2010

In this paper, we investigate the transmission completion time minimization problem in a two-user additive white Gaussian noise (AWGN) broadcast channel, where the transmitter is able to harvest energy from the nature, using a rechargeable battery. The harvested energy is modeled to arrive at the transmitter randomly during the course of transmissions. The transmitter has a fixed number of packets to be delivered to each receiver. Our goal is to minimize the time by which all of the packets for both users are delivered to their respective destinations. To this end, we optimize the transmit powers and transmission rates intended for both users. We first analyze the structural properties of the optimal transmission policy. We prove that the optimal total transmit power has the same structure as the optimal single-user transmit power. We also prove that there exists a cut-off power level for the stronger user. If the optimal total transmit power is lower than this cut-off level, all transmit power is allocated to the stronger user, and when the optimal total transmit power is larger than this cut-off level, all transmit power above this level is allocated to the weaker user. Based on these structural properties of the optimal policy, we propose an algorithm that yields the globally optimal off-line scheduling policy. Our algorithm is based on the idea of reducing the two-user broadcast channel problem into a single-user problem as much as possible.
Adaptive Bit Partitioning for Multicell Intercell Interference Nulling with Delayed Limited Feedback
Venue: arXiv cs.IT 2010
Year: 2010

Base station cooperation can exploit knowledge of the users' channel state information (CSI) at the transmitters to manage co-channel interference. Users have to feedback CSI of the desired and interfering channels using finite-bandwidth backhaul links. Existing codebook designs for single-cell limited feedback can be used for multicell cooperation by partitioning the available feedback resources between the multiple channels. In this paper, a new feedback-bit allocation strategy is proposed, as a function of the delays in the communication links and received signal strengths in the downlink. Channel temporal correlation is modeled as a function of delay using the Gauss-Markov model. Closed-form expressions for bit partitions are derived to allocate more bits to quantize the stronger channels with smaller delays and fewer bits to weaker channels with larger delays, assuming random vector quantization. Cellular network simulations are used to show that the proposed algorithm yields higher sum-rates than an equal-bit allocation technique.
The Emerging Web of Social Machines
Venue: arXiv cs.SE 2010
Year: 2010

We define a notion of social machine and envisage an algebra that can describe networks of such. To start with, social machines are defined as tuples of input, output, processes, constraints, state, requests and responses; apart from defining the machines themselves, the algebra defines a set of connectors and conditionals that can be used to describe the interactions between any number of machines in a multitude of ways, as a means to represent real machines interacting in the real web, such as Twitter, Twitter running on top of Amazon AWS, mashups built using Twitter and, obviously, other social machines. This work is not a theoretical paper as yet; but, in more than one sense, we think we have found a way to describe web based information systems and are starting to work on what could be a practical way of dealing with the complexity of this emerging web of social machines that is all around us. This version should be read as work in progress and comments, observations, bugs... are most welcome and should be sent to the email of the first, corresponding author.
Wireless Sensor Network based Future of Telecom Applications
Venue: arXiv cs.HC 2010
Year: 2010

A system and method for enabling human beings to communicate by way of their monitored brain activity. The brain activity of an individual is monitored and transmitted to a remote location (e.g. by satellite). At the remote location, the monitored brain activity is compared with pre-recorded normalized brain activity curves, waveforms, or patterns to determine if a match or substantial match is found. If such a match is found, then the computer at the remote location determines that the individual was attempting to communicate the word, phrase, or thought corresponding to the matched stored normalized signal.
Scalable XML Collaborative Editing with Undo short paper
Venue: arXiv cs.DB 2010
Year: 2010

Commutative Replicated Data-Type (CRDT) is a new class of algorithms that ensures scalable consistency of replicated data. It has been successfully applied to collaborative editing of texts without complex concurrency control. In this paper, we present a CRDT to edit XML data. Compared to existing approaches for XML collaborative editing, our approach is more scalable and handles all the XML editing aspects : elements, contents, attributes and undo. Indeed, undo is recognized as an important feature for collaborative editing that allows to overcome system complexity through error recovery or collaborative conflict resolution.