OpenRaiser/Intern-Atlas huggingface dataset:
Minimizing Maximum Response Time and Delay Factor in Broadcast Scheduling
Venue: arXiv cs.DS 2009
Year: 2009

We consider online algorithms for pull-based broadcast scheduling. In this setting there are n pages of information at a server and requests for pages arrive online. When the server serves (broadcasts) a page p, all outstanding requests for that page are satisfied. We study two related metrics, namely maximum response time (waiting time) and maximum delay-factor and their weighted versions. We obtain the following results in the worst-case online competitive model. - We show that FIFO (first-in first-out) is 2-competitive even when the page sizes are different. Previously this was known only for unit-sized pages [10] via a delicate argument. Our proof differs from [10] and is perhaps more intuitive. - We give an online algorithm for maximum delay-factor that is O(1/eps^2)-competitive with (1+\eps)-speed for unit-sized pages and with (2+\eps)-speed for different sized pages. This improves on the algorithm in [12] which required (2+\eps)-speed and (4+\eps)-speed respectively. In addition we show that the algorithm and analysis can be extended to obtain the same results for maximum weighted response time and delay factor. - We show that a natural greedy algorithm modeled after LWF (Longest-Wait-First) is not O(1)-competitive for maximum delay factor with any constant speed even in the setting of standard scheduling with unit-sized jobs. This complements our upper bound and demonstrates the importance of the tradeoff made in our algorithm.
On Implementation of a Safer C Library, ISO/IEC TR 24731
Venue: arXiv cs.SE 2009
Year: 2009

The functions standardized as part of ISO C 1999 and their addendums improved very little the security options from the previously available library. The largest flaw remained that no function asked for the buffer size of destination buffers for any function copying data into a user-supplied buffer. According to earlier research we performed, we know that error condition handling was the first solution to security vulnerabilities, followed by precondition validation. The standard C functions typically perform little precondition validation and error handling, allowing for a wide range of security issues to be introduced in their use. ISO/IEC TR 24731, titled as "TR 24731: Safer C library functions", defines 41 new library functions for memory copying, string handling (both for normal and wide character strings), time printing, sorting, searching etc. Another innovation it brings is a constraint handling architecture, forcing error handling when certain security-related preconditions are violated when the functions are called. It also specifies the null-termination of all strings manipulated through its function and introduces a new unsigned integer type that helps preventing integer overflows and underflows. It is currently implemented by Microsoft as part of their Visual Studio 2005 and above. We examine the architecture of our implementation of ISO/IEC TR 24731. We first introduce our architectural philosophy before informing the reader about the Siemens Four View Model, an architectural methodology for the conception of large-scale software systems. Afterwards, we examine each of the view, as architected for our library. Finally, we conclude with other software engineering matters that were of high importance in the development of our implementation.
Power Saving Strategies and Technologies in Network Equipment Opportunities and Challenges, Risk and Rewards
Venue: arXiv cs.NI 2009
Year: 2009

Drawing from todays best-in-class solutions, we identify power-saving strategies that have succeeded in the past and look forward to new ideas and paradigms. We strongly believe that designing energy-efficient network equipment can be compared to building sports cars, task-oriented, focused and fast. However, unlike track-bound sports cars, ultra-fast and purpose-built silicon yields better energy efficiency when compared to more generic family sedan designs that mitigate go-to-market risks by being the masters of many tasks. Thus, we demonstrate that the best opportunities for power savings come via protocol simplification, best-of-breed technology, and silicon and software optimization, to achieve the least amount of processing necessary to move packets. We also look to the future of networking from a new angle, where energy efficiency and environmental concerns are viewed as fundamental design criteria and forces that need to be harnessed to continually create more powerful networking equipment.
Combinatorial pyramids and discrete geometry for energy-minimizing segmentation
Venue: arXiv cs.CV 2009
Year: 2009

This paper defines the basis of a new hierarchical framework for segmentation algorithms based on energy minimization schemes. This new framework is based on two formal tools. First, a combinatorial pyramid encode efficiently a hierarchy of partitions. Secondly, discrete geometric estimators measure precisely some important geometric parameters of the regions. These measures combined with photometrical and topological features of the partition allows to design energy terms based on discrete measures. Our segmentation framework exploits these energies to build a pyramid of image partitions with a minimization scheme. Some experiments illustrating our framework are shown and discussed.
Equalization for Non-Coherent UWB Systems with Approximate Semi-Definite Programming
Venue: arXiv cs.IT 2009
Year: 2009

In this paper, we propose an approximate semi-definite programming framework for demodulation and equalization of non-coherent ultra-wide-band communication systems with inter-symbol-interference. It is assumed that the communication systems follow non-linear second-order Volterra models. We formulate the demodulation and equalization problems as semi-definite programming problems. We propose an approximate algorithm for solving the formulated semi-definite programming problems. Compared with the existing non-linear equalization approaches, the proposed semi-definite programming formulation and approximate solving algorithm have low computational complexity and storage requirements. We show that the proposed algorithm has satisfactory error probability performance by simulation results. The proposed non-linear equalization approach can be adopted for a wide spectrum of non-coherent ultra-wide-band systems, due to the fact that most non-coherent ultra-wide-band systems with inter-symbol-interference follow non-linear second-order Volterra signal models.
Empirical evaluation of construction heuristics for the multidimensional assignment problem
Venue: arXiv cs.DS 2009
Year: 2009

The multidimensional assignment problem (MAP) (abbreviated s-AP in the case of s dimensions) is an extension of the well-known assignment problem. The most studied case of MAP is 3-AP, though the problems with larger values of s have also a number of applications. In this paper we consider four fast construction heuristics for MAP. One of the heuristics is new. A modification of the heuristics is proposed to optimize the access to slow computer memory. The results of computational experiments for several instance families are provided and discussed.
Secured Communication over Frequency-Selective Fading Channels: a practical Vandermonde precoding
Venue: arXiv cs.IT 2009
Year: 2009

In this paper, we study the frequency-selective broadcast channel with confidential messages (BCC) in which the transmitter sends a confidential message to receiver 1 and a common message to receivers 1 and 2. In the case of a block transmission of N symbols followed by a guard interval of L symbols, the frequency-selective channel can be modeled as a N * (N+L) Toeplitz matrix. For this special type of multiple-input multiple-output (MIMO) channels, we propose a practical Vandermonde precoding that consists of projecting the confidential messages in the null space of the channel seen by receiver 2 while superposing the common message. For this scheme, we provide the achievable rate region, i.e. the rate-tuple of the common and confidential messages, and characterize the optimal covariance inputs for some special cases of interest. It is proved that the proposed scheme achieves the optimal degree of freedom (d.o.f) region. More specifically, it enables to send l <= L confidential messages and N-l common messages simultaneously over a block of N+L symbols. Interestingly, the proposed scheme can be applied to secured multiuser scenarios such as the K+1-user frequency-selective BCC with K confidential messages and the two-user frequency-selective BCC with two confidential messages. For each scenario, we provide the achievable secrecy degree of freedom (s.d.o.f.) region of the corresponding frequency-selective BCC and prove the optimality of the Vandermonde precoding. One of the appealing features of the proposed scheme is that it does not require any specific secrecy encoding technique but can be applied on top of any existing powerful encoding schemes.
On the injectivity of the global function of a cellular automaton in the hyperbolic plane (extended abstract)
Venue: arXiv cs.CC 2009
Year: 2009

In this paper, we look at the following question. We consider cellular automata in the hyperbolic plane, (see Margenstern, 2000, 2007 and Margenstern, Morita, 2001) and we consider the global function defined on all possible configurations. Is the injectivity of this function undecidable? The problem was answered positively in the case of the Euclidean plane by Jarkko Kari, in 1994. In the present paper, we show that the answer is also positive for the hyperbolic plane: the problem is undecidable.
A Particular Universal Cellular Automaton
Venue: arXiv cs.CC 2009
Year: 2009

Signals are a classical tool used in cellular automata constructions that proved to be useful for language recognition or firing-squad synchronisation. Particles and collisions formalize this idea one step further, describing regular nets of colliding signals. In the present paper, we investigate the use of particles and collisions for constructions involving an infinite number of interacting particles. We obtain a high-level construction for a new smallest intrinsically universal cellular automaton with 4 states.
Limitations of Self-Assembly at Temperature One (extended abstract)
Venue: arXiv cs.CC 2009
Year: 2009

We prove that if a subset X of the integer Cartesian plane weakly self-assembles at temperature 1 in a deterministic (Winfree) tile assembly system satisfying a natural condition known as *pumpability*, then X is a finite union of doubly periodic sets. This shows that only the most simple of infinite shapes and patterns can be constructed using pumpable temperature 1 tile assembly systems, and gives strong evidence for the thesis that temperature 2 or higher is required to carry out general-purpose computation in a tile assembly system. Finally, we show that general-purpose computation is possible at temperature 1 if negative glue strengths are allowed in the tile assembly model.
Quantifying the Availability of TV White Spaces for Cognitive Radio Operation in the UK
Venue: arXiv cs.NI 2009
Year: 2009

Cognitive radio is being intensively researched for opportunistic access to the so-called TV White Spaces (TVWS): large portions of the VHF/UHF TV bands which become available on a geographical basis after the digital switchover. Using accurate digital TV (DTV) coverage maps together with a database of DTV transmitters, we develop a methodology for identifying TVWS frequencies at any given location in the United Kingdom. We use our methodology to investigate variations in TVWS as a function of the location and transmit power of cognitive radios, and examine how constraints on adjacent channel interference imposed by regulators may affect the results. Our analysis provides a realistic view on the spectrum opportunity associated with cognitive devices, and presents the first quantitative study of the availability and frequency composition of TWVS outside the United States.
Quasi-cyclic LDPC codes with high girth
Venue: arXiv cs.IT 2009
Year: 2009

We study a class of quasi-cyclic LDPC codes. We provide precise conditions guaranteeing high girth in their Tanner graph. Experimentally, the codes we propose perform no worse than random LDPC codes with their same parameters, which is a significant achievement for algebraic codes.
Modified Euclidean Algorithms for Decoding Reed-Solomon Codes
Venue: arXiv cs.IT 2009
Year: 2009

The extended Euclidean algorithm (EEA) for polynomial greatest common divisors is commonly used in solving the key equation in the decoding of Reed-Solomon (RS) codes, and more generally in BCH decoding. For this particular application, the iterations in the EEA are stopped when the degree of the remainder polynomial falls below a threshold. While determining the degree of a polynomial is a simple task for human beings, hardware implementation of this stopping rule is more complicated. This paper describes a modified version of the EEA that is specifically adapted to the RS decoding problem. This modified algorithm requires no degree computation or comparison to a threshold, and it uses a fixed number of iterations. Another advantage of this modified version is in its application to the errors-and-erasures decoding problem for RS codes where significant hardware savings can be achieved via seamless computation.
A Monte-Carlo Implementation of the SAGE Algorithm for Joint Soft Multiuser and Channel Parameter Estimation
Venue: arXiv cs.IT 2009
Year: 2009

An efficient, joint transmission delay and channel parameter estimation algorithm is proposed for uplink asynchronous direct-sequence code-division multiple access (DS-CDMA) systems based on the space-alternating generalized expectation maximization (SAGE) framework. The marginal likelihood of the unknown parameters, averaged over the data sequence, as well as the expectation and maximization steps of the SAGE algorithm are derived analytically. To implement the proposed algorithm, a Markov Chain Monte Carlo (MCMC) technique, called Gibbs sampling, is employed to compute the {\em a posteriori} probabilities of data symbols in a computationally efficient way. Computer simulations show that the proposed algorithm has excellent estimation performance. This so-called MCMC-SAGE receiver is guaranteed to converge in likelihood.
Relaying Simultaneous Multicast Messages
Venue: arXiv cs.IT 2009
Year: 2009

The problem of multicasting multiple messages with the help of a relay, which may also have an independent message of its own to multicast, is considered. As a first step to address this general model, referred to as the compound multiple access channel with a relay (cMACr), the capacity region of the multiple access channel with a "cognitive" relay is characterized, including the cases of partial and rate-limited cognition. Achievable rate regions for the cMACr model are then presented based on decode-and-forward (DF) and compress-and-forward (CF) relaying strategies. Moreover, an outer bound is derived for the special case in which each transmitter has a direct link to one of the receivers while the connection to the other receiver is enabled only through the relay terminal. Numerical results for the Gaussian channel are also provided.
Exploiting Semiconductor Properties for Hardware Trojans
Venue: arXiv cs.AR 2009
Year: 2009

This paper discusses the possible introduction of hidden reliability defects during CMOS foundry fabrication processes that may lead to accelerated wearout of the devices. These hidden defects or hardware Trojans can be created by deviation from foundry design rules and processing parameters. The Trojans are produced by exploiting time-based wearing mechanisms (HCI, NBTI, TDDB and EM) and/or condition-based triggers (ESD, Latchup and Softerror). This class of latent damage is difficult to test due to its gradual degradation nature. The paper describes life-time expectancy results for various Trojan induced scenarios. Semiconductor properties, processing and design parameters critical for device reliability and Trojan creation are discussed.
Squeezing the Arimoto-Blahut algorithm for faster convergence
Venue: arXiv cs.IT 2009
Year: 2009

The Arimoto--Blahut algorithm for computing the capacity of a discrete memoryless channel is revisited. A so-called ``squeezing'' strategy is used to design algorithms that preserve its simplicity and monotonic convergence properties, but have provably better rates of convergence.
Diversity Analysis of Peaky FSK Signaling in Fading Channels
Venue: arXiv cs.IT 2009
Year: 2009

Error performance of noncoherent detection of on-off frequency shift keying (OOFSK) modulation over fading channels is analyzed when the receiver is equipped with multiple antennas. The analysis is conducted for two cases: 1) the case in which the receiver has the channel distribution knowledge only; and 2) the case in which the receiver perfectly knows the fading magnitudes. For both cases, the maximum a posteriori probability (MAP) detection rule is derived and analytical probability of error expressions are obtained. Numerical and simulation results indicate that for sufficiently low duty cycle values, lower error probabilities with respect to FSK signaling are achieved. Equivalently, when compared to FSK modulation, OOFSK with low duty cycle requires less energy to achieve the same probability of error, which renders this modulation a more energy efficient transmission technique. Also, through numerical results, the impact of number of antennas, antenna correlation, duty cycle values, and unknown channel fading on the performance are investigated.
Soft Constraints for Quality Aspects in Service Oriented Architectures
Venue: arXiv cs.AI 2009
Year: 2009

We propose the use of Soft Constraints as a natural way to model Service Oriented Architecture. In the framework, constraints are used to model components and connectors and constraint aggregation is used to represent their interactions. The "quality of a service" is measured and considered when performing queries to service providers. Some examples consist in the levels of cost, performance and availability required by clients. In our framework, the QoS scores are represented by the softness level of the constraint and the measure of complex (web) services is computed by combining the levels of the components.
Towards a Unifying View of QoS-Enhanced Web Service Description and Discovery Approaches
Venue: arXiv cs.SE 2009
Year: 2009

The number of web services increased vastly in the last years. Various providers offer web services with the same functionality, so for web service consumers it is getting more complicated to select the web service, which best fits their requirements. That is why a lot of the research efforts point to discover semantic means for describing web services taking into account not only functional characteristics of services, but also the quality of service (QoS) properties such as availability, reliability, response time, trust, etc. This motivated us to research current approaches presenting complete solutions for QoS enabled web service description, publication and discovery. In this paper we present comparative analysis of these approaches according to their common principals. Based on such analysis we extract the essential aspects from them and propose a pattern for the development of QoS-aware service-oriented architectures.
Application of non-uniform laxity to EDF for aperiodic tasks to improve task utilisation on multicore platforms
Venue: arXiv cs.PF 2009
Year: 2009

This paper proposes a new scheduler applying the concept of non-uniform laxity to Earliest deadline first (EDF) approach for aperiodic tasks. This scheduler improves task utilisation (Execution time / deadline) and also increases the number of tasks that are being scheduled. Laxity is a measure of the spare time permitted for the task before it misses its deadline, and is computed using the expression (deadline - (current time + execution time)). Weight decides the priority of the task and is defined by the expression (quantum slice time / allocated time)*total core time for the task. Quantum slice time is the time actually used, allocated time is the time allocated by the scheduler, and total core time is the time actually reserved by the core for execution of one quantum of the task. Non-uniform laxity enables scheduling of tasks that have higher priority before the normal execution of other tasks and is computed by multiplying the weight of the task with its laxity. The algorithm presented in the paper has been simulated on Cheddar, a real time scheduling tool and also on SESC, an architectural simulator for multicore platforms, for upto 5000 random task sets, and upto 5000 cores. This scheduler improves task utilisation by 35% and the number of tasks being scheduled by 36%, compared to conventional EDF.
Reduced-Feedback Opportunistic Scheduling and Beamforming with GMD for MIMO-OFDMA
Venue: arXiv cs.IT 2009
Year: 2009

Opportunistic scheduling and beamforming schemes have been proposed previously by the authors for reduced-feedback MIMO-OFDMA downlink systems where the MIMO channel of each subcarrier is decomposed into layered spatial subchannels. It has been demonstrated that significant feedback reduction can be achieved by returning information about only one beamforming matrix (BFM) for all subcarriers from each MT, compared to one BFM for each subcarrier in the conventional schemes. However, since the previously proposed channel decomposition was derived based on singular value decomposition, the resulting system performance is impaired by the subchannels associated with the smallest singular values. To circumvent this obstacle, this work proposes improved opportunistic scheduling and beamforming schemes based on geometric mean decomposition-based channel decomposition. In addition to the inherent advantage in reduced feedback, the proposed schemes can achieve improved system performance by decomposing the MIMO channels into spatial subchannels with more evenly distributed channel gains. Numerical results confirm the effectiveness of the proposed opportunistic scheduling and beamforming schemes.
An Event Based Approach To Situational Representation
Venue: arXiv cs.DB 2009
Year: 2009

Many application domains require representing interrelated real-world activities and/or evolving physical phenomena. In the crisis response domain, for instance, one may be interested in representing the state of the unfolding crisis (e.g., forest fire), the progress of the response activities such as evacuation and traffic control, and the state of the crisis site(s). Such a situation representation can then be used to support a multitude of applications including situation monitoring, analysis, and planning. In this paper, we make a case for an event based representation of situations where events are defined to be domain-specific significant occurrences in space and time. We argue that events offer a unifying and powerful abstraction to building situational awareness applications. We identify challenges in building an Event Management System (EMS) for which traditional data and knowledge management systems prove to be limited and suggest possible directions and technologies to address the challenges.
A Refined Experience Sampling Method to Capture Mobile User Experience
Venue: arXiv cs.HC 2009
Year: 2009

This paper reviews research methods used to understand the user experience of mobile technology. The paper presents an improvement of the Experience Sampling Method and case studies supporting its design. The paper concludes with an agenda of future work for improving research in this field. Keywords: Research methods, topology, case study, contrasting graph, Experience Sampling Method