title: Throughput Scaling Laws for Wireless Networks with Fading Channels

abstract: A network of $n$ wireless communication links is considered. Fading is assumed to be the dominant factor affecting the strength of the channels between nodes. The objective is to analyze the achievable throughput of the network when power allocation is allowed. By proposing a decentralized on-off power allocation strategy, a lower bound on the achievable throughput is obtained for a general fading model. In particular, under Rayleigh fading conditions the achieved sum-rate is of order $\log n$, which is, by a constant factor, larger than what is obtained with a centralized scheme in the work of Gowaikar et al. Similar to most of previous works on large networks, the proposed scheme assigns a vanishingly small rate for each link. However, it is shown that by allowing the sum-rate to decrease by a factor $\alpha<1$, this scheme is capable of providing non-zero rate-per-links of order $\Theta(1)$. To obtain larger non-zero rate-per-links, the proposed scheme is modified to a centralized version. It turns out that for the same number of active links the centralized scheme achieves a much larger rate-per-link. Moreover, at large values of rate-per-link, it achieves a sum-rate close to $\log n$, i.e., the maximum achieved by the decentralized scheme.


title: Maximizing the Probability of Delivery of Multipoint Relay Broadcast Protocol in Wireless Ad Hoc Networks with a Realistic Physical Layer

abstract: It is now commonly accepted that the unit disk graph used to model the physical layer in wireless networks does not reflect real radio transmissions, and that the lognormal shadowing model better suits to experimental simulations. Previous work on realistic scenarios focused on unicast, while broadcast requirements are fundamentally different and cannot be derived from unicast case. Therefore, broadcast protocols must be adapted in order to still be efficient under realistic assumptions. In this paper, we study the well-known multipoint relay protocol (MPR). In the latter, each node has to choose a set of neighbors to act as relays in order to cover the whole 2-hop neighborhood. We give experimental results showing that the original method provided to select the set of relays does not give good results with the realistic model. We also provide three new heuristics in replacement and their performances which demonstrate that they better suit to the considered model. The first one maximizes the probability of correct reception between the node and the considered relays multiplied by their coverage in the 2-hop neighborhood. The second one replaces the coverage by the average of the probabilities of correct reception between the considered neighbor and the 2-hop neighbors it covers. Finally, the third heuristic keeps the same concept as the second one, but tries to maximize the coverage level of the 2-hop neighborhood: 2-hop neighbors are still being considered as uncovered while their coverage level is not higher than a given coverage threshold, many neighbors may thus be selected to cover the same 2-hop neighbors.


title: Propositional theories are strongly equivalent to logic programs

abstract: This paper presents a property of propositional theories under the answer sets semantics (called Equilibrium Logic for this general syntax): any theory can always be reexpressed as a strongly equivalent disjunctive logic program, possibly with negation in the head. We provide two different proofs for this result: one involving a syntactic transformation, and one that constructs a program starting from the countermodels of the theory in the intermediate logic of here-and-there.


title: About the domino problem in the hyperbolic plane, a new solution

abstract: In this paper we improve the approach of a previous paper about the domino problem in the hyperbolic plane, see arXiv.cs.CG/0603093. This time, we prove that the general problem of the hyperbolic plane with \`a la Wang tiles is undecidable.


title: MacWilliams Identity for the Rank Metric

abstract: This paper investigates the relationship between the rank weight distribution of a linear code and that of its dual code. The main result of this paper is that, similar to the MacWilliams identity for the Hamming metric, the rank weight distribution of any linear code can be expressed as an analytical expression of that of its dual code. Remarkably, our new identity has a similar form to the MacWilliams identity for the Hamming metric. Our new identity provides a significant analytical tool to the rank weight distribution analysis of linear codes. We use a linear space based approach in the proof for our new identity, and adapt this approach to provide an alternative proof of the MacWilliams identity for the Hamming metric. Finally, we determine the relationship between moments of the rank distribution of a linear code and those of its dual code, and provide an alternative derivation of the rank weight distribution of maximum rank distance codes.


title: Packing and Covering Properties of Rank Metric Codes

abstract: This paper investigates packing and covering properties of codes with the rank metric. First, we investigate packing properties of rank metric codes. Then, we study sphere covering properties of rank metric codes, derive bounds on their parameters, and investigate their asymptotic covering properties.


title: On the Feedback Capacity of Power Constrained Gaussian Noise Channels with Memory

abstract: For a stationary additive Gaussian-noise channel with a rational noise power spectrum of a finite-order $L$, we derive two new results for the feedback capacity under an average channel input power constraint. First, we show that a very simple feedback-dependent Gauss-Markov source achieves the feedback capacity, and that Kalman-Bucy filtering is optimal for processing the feedback. Based on these results, we develop a new method for optimizing the channel inputs for achieving the Cover-Pombra block-length-$n$ feedback capacity by using a dynamic programming approach that decomposes the computation into $n$ sequentially identical optimization problems where each stage involves optimizing $O(L^2)$ variables. Second, we derive the explicit maximal information rate for stationary feedback-dependent sources. In general, evaluating the maximal information rate for stationary sources requires solving only a few equations by simple non-linear programming. For first-order autoregressive and/or moving average (ARMA) noise channels, this optimization admits a closed form maximal information rate formula. The maximal information rate for stationary sources is a lower bound on the feedback capacity, and it equals the feedback capacity if the long-standing conjecture, that stationary sources achieve the feedback capacity, holds.


title: Delayed Feedback Capacity of Stationary Sources over Linear Gaussian Noise Channels

abstract: We consider a linear Gaussian noise channel used with delayed feedback. The channel noise is assumed to be a ARMA (autoregressive and/or moving average) process. We reformulate the Gaussian noise channel into an intersymbol interference channel with white noise, and show that the delayed-feedback of the original channel is equivalent to the instantaneous-feedback of the derived channel. By generalizing results previously developed for Gaussian channels with instantaneous feedback and applying them to the derived intersymbol interference channel, we show that conditioned on the delayed feedback, a conditional Gauss-Markov source achieves the feedback capacity and its Markov memory length is determined by the noise spectral order and the feedback delay. A Kalman-Bucy filter is shown to be optimal for processing the feedback. The maximal information rate for stationary sources is derived in terms of channel input power constraint and the steady state solution of the Riccati equation of the Kalman-Bucy filter used in the feedback loop.


title: Citation advantage of Open Access articles likely explained by quality differential and media effects

abstract: In a study of articles published in the Proceedings of the National Academy of Sciences, Gunther Eysenbach discovered a significant citation advantage for those articles made freely-available upon publication (Eysenbach 2006). While the author attempted to control for confounding factors that may have explained the citation differential, the study was unable to control for characteristics of the article that may have led some authors to pay the additional page charges ($1,000) for immediate OA status. OA articles published in PNAS were more than twice as likely to be featured on the front cover of the journal (3.3% vs. 1.4%), nearly twice as likely to be picked up by the media (15% vs. 8%) and when cited reached, on average, nearly twice as many news outlets as subscription-based articles (4.2 vs. 2.6). The citation advantage of Open Access articles in PNAS may likely be explained by a quality differential and the amplification of media effects.


title: Coding Solutions for the Secure Biometric Storage Problem

abstract: The paper studies the problem of securely storing biometric passwords, such as fingerprints and irises. With the help of coding theory Juels and Wattenberg derived in 1999 a scheme where similar input strings will be accepted as the same biometric. In the same time nothing could be learned from the stored data. They called their scheme a "fuzzy commitment scheme". In this paper we will revisit the solution of Juels and Wattenberg and we will provide answers to two important questions: What type of error-correcting codes should be used and what happens if biometric templates are not uniformly distributed, i.e. the biometric data come with redundancy. Answering the first question will lead us to the search for low-rate large-minimum distance error-correcting codes which come with efficient decoding algorithms up to the designed distance. In order to answer the second question we relate the rate required with a quantity connected to the "entropy" of the string, trying to estimate a sort of "capacity", if we want to see a flavor of the converse of Shannon's noisy coding theorem. Finally we deal with side-problems arising in a practical implementation and we propose a possible solution to the main one that seems to have so far prevented real life applications of the fuzzy scheme, as far as we know.


title: Analysis and design of raptor codes for joint decoding using Information Content evolution

abstract: In this paper, we present an analytical analysis of the convergence of raptor codes under joint decoding over the binary input additive white noise channel (BIAWGNC), and derive an optimization method. We use Information Content evolution under Gaussian approximation, and focus on a new decoding scheme that proves to be more efficient: the joint decoding of the two code components of the raptor code. In our general model, the classical tandem decoding scheme appears to be a subcase, and thus, the design of LT codes is also possible.


title: Why is a new Journal of Informetrics needed?

abstract: In our study we analysed 3.889 records which were indexed in the Library and Information Science Abstracts (LISA) database in the research field of informetrics. We can show the core journals of the field via a Bradford (power law) distribution and corroborate on the basis of the restricted LISA data set that it was the appropriate time to found a new specialized journal dedicated to informetrics. According to Bradford's Law of scattering (pure quantitative calculation), Egghe's Journal of Informetrics (JOI) first issue to appear in 2007, comes most probable at the right time.


title: A Delta Debugger for ILP Query Execution

abstract: Because query execution is the most crucial part of Inductive Logic Programming (ILP) algorithms, a lot of effort is invested in developing faster execution mechanisms. These execution mechanisms typically have a low-level implementation, making them hard to debug. Moreover, other factors such as the complexity of the problems handled by ILP algorithms and size of the code base of ILP data mining systems make debugging at this level a very difficult job. In this work, we present the trace-based debugging approach currently used in the development of new execution mechanisms in hipP, the engine underlying the ACE Data Mining system. This debugger uses the delta debugging algorithm to automatically reduce the total time needed to expose bugs in ILP execution, thus making manual debugging step much lighter.


title: On using Tracer Driver for External Dynamic Process Observation

abstract: One is interested here in the observation of dynamic processes starting from the traces which they leave or those that one makes them produce. It is considered here that it should be possible to make several observations simultaneously, using a large variety of independently developed analyzers. For this purpose, we introduce the original notion of ``full trace'' to capture the idea that a process can be instrumented in such a way that it may broadcast all information which could ever be requested by any kind of observer. Each analyzer can then find in the full trace the data elements which it needs. This approach uses what has been called a "tracer driver" which completes the tracer and drives it to answer the requests of the analyzers. A tracer driver allows to restrict the flow of information and makes this approach tractable. On the other side, the potential size of a full trace seems to make the idea of full trace unrealistic. In this work we explore the consequences of this notion in term of potential efficiency, by analyzing the respective workloads between the (full) tracer and many different analyzers, all being likely run in true parallel environments. To illustrate this study, we use the example of the observation of the resolution of constraints systems (proof-tree, search-tree and propagation) using sophisticated visualization tools, as developed in the project OADymPPaC (2001-2004). The processes considered here are computer programs, but we believe the approach can be extended to many other kinds of processes.


title: JavaTA: A Logic-based Debugger for Java

abstract: This paper presents a logic based approach to debugging Java programs. In contrast with traditional debugging we propose a debugging methodology for Java programs using logical queries on individual execution states and also over the history of execution. These queries were arrived at by a systematic study of errors in object-oriented programs in our earlier research. We represent the salient events during the execution of a Java program by a logic database, and implement the queries as logic programs. Such an approach allows us to answer a number of useful and interesting queries about a Java program, such as the calling sequence that results in a certain outcome, the state of an object at a particular execution point, etc. Our system also provides the ability to compose new queries during a debugging session. We believe that logic programming offers a significant contribution to the art of object-oriented programs debugging.


title: Towards Execution Time Estimation for Logic Programs via Static Analysis and Profiling

abstract: Effective static analyses have been proposed which infer bounds on the number of resolutions or reductions. These have the advantage of being independent from the platform on which the programs are executed and have been shown to be useful in a number of applications, such as granularity control in parallel execution. On the other hand, in distributed computation scenarios where platforms with different capabilities come into play, it is necessary to express costs in metrics that include the characteristics of the platform. In particular, it is specially interesting to be able to infer upper and lower bounds on actual execution times. With this objective in mind, we propose an approach which combines compile-time analysis for cost bounds with a one-time profiling of the platform in order to determine the values of certain parameters for a given platform. These parameters calibrate a cost model which, from then on, is able to compute statically time bound functions for procedures and to predict with a significant degree of accuracy the execution times of such procedures in the given platform. The approach has been implemented and integrated in the CiaoPP system.


title: ExSched: Solving Constraint Satisfaction Problems with the Spreadsheet Paradigm

abstract: We report on the development of a general tool called ExSched, implemented as a plug-in for Microsoft Excel, for solving a class of constraint satisfaction problems. The traditional spreadsheet paradigm is based on attaching arithmetic expressions to individual cells and then evaluating them. The ExSched interface generalizes the spreadsheet paradigm to allow finite domain constraints to be attached to the individual cells that are then solved to get a solution. This extension provides a user-friendly interface for solving constraint satisfaction problems that can be modeled as 2D tables, such as scheduling problems, timetabling problems, product configuration, etc. ExSched can be regarded as a spreadsheet interface to CLP(FD) that hides the syntactic and semantic complexity of CLP(FD) and enables novice users to solve many scheduling and timetabling problems interactively.


title: A Web-based Tool Combining Different Type Analyses

abstract: There are various kinds of type analysis of logic programs. These include for example inference of types that describe an over-approximation of the success set of a program, inference of well-typings, and abstractions based on given types. Analyses can be descriptive or prescriptive or a mixture of both, and they can be goal-dependent or goal-independent. We describe a prototype tool that can be accessed from a web browser, allowing various type analyses to be run. The first goal of the tool is to allow the analysis results to be examined conveniently by clicking on points in the original program clauses, and to highlight ill-typed program constructs, empty types or other type anomalies. Secondly the tool allows combination of the various styles of analysis. For example, a descriptive regular type can be automatically inferred for a given program, and then that type can be used to generate the minimal "domain model" of the program with respect to the corresponding pre-interpretation, which can give more precise information than the original descriptive type.


title: Some Issues on Incremental Abstraction-Carrying Code

abstract: Abstraction-Carrying Code (ACC) has recently been proposed as a framework for proof-carrying code (PCC) in which the code supplier provides a program together with an abstraction (or abstract model of the program) whose validity entails compliance with a predefined safety policy. The abstraction thus plays the role of safety certificate and its generation (and validation) is carried out automatically by a fixed-point analyzer. Existing approaches for PCC are developed under the assumption that the consumer reads and validates the entire program w.r.t. the full certificate at once, in a non incremental way. In this abstract, we overview the main issues on incremental ACC. In particular, in the context of logic programming, we discuss both the generation of incremental certificates and the design of an incremental checking algorithm for untrusted updates of a (trusted) program, i.e., when a producer provides a modified version of a previously validated program. By update, we refer to any arbitrary change on a program, i.e., the extension of the program with new predicates, the deletion of existing predicates and the replacement of existing predicates by new versions for them. We also discuss how each kind of update affects the incremental extension in terms of accuracy and correctness.


title: (l,s)-Extension of Linear Codes

abstract: We construct new linear codes with high minimum distance d. In at least 12 cases these codes improve the minimum distance of the previously known best linear codes for fixed parameters n,k. Among these new codes there is an optimal ternary [88,8,54] code. We develop an algorithm, which starts with already good codes C, i.e. codes with high minimum distance d for given length n and dimension k over the field GF(q). The algorithm is based on the newly defined (l,s)-extension. This is a generalization of the well-known method of adding a parity bit in the case of a binary linear code of odd minimum weight. (l,s)-extension tries to extend the generator matrix of C by adding l columns with the property that at least s of the l letters added to each of the codewords of minimum weight in C are different from 0. If one finds such columns the minimum distance of the extended code is d+s provided that the second smallest weight in C was at least d+s. The question whether such columns exist can be settled using a Diophantine system of equations.


title: On factorisation forests

abstract: The theorem of factorisation forests shows the existence of nested factorisations -- a la Ramsey -- for finite words. This theorem has important applications in semigroup theory, and beyond. The purpose of this paper is to illustrate the importance of this approach in the context of automata over infinite words and trees. We extend the theorem of factorisation forest in two directions: we show that it is still valid for any word indexed by a linear ordering; and we show that it admits a deterministic variant for words indexed by well-orderings. A byproduct of this work is also an improvement on the known bounds for the original result. We apply the first variant for giving a simplified proof of the closure under complementation of rational sets of words indexed by countable scattered linear orderings. We apply the second variant in the analysis of monadic second-order logic over trees, yielding new results on monadic interpretations over trees. Consequences of it are new caracterisations of prefix-recognizable structures and of the Caucal hierarchy.


title: The problem determination of Functional Dependencies between attributes Relation Scheme in the Relational Data Model. El problema de determinar Dependencias Funcionales entre atributos en los esquemas en el Modelo Relacional

abstract: An alternative definition of the concept is given of functional dependence among the attributes of the relational schema in the Relational Model, this definition is obtained in terms of the set theory. For that which a theorem is demonstrated that establishes equivalence and on the basis theorem an algorithm is built for the search of the functional dependences among the attributes. The algorithm is illustrated by a concrete example


title: Browser-based distributed evolutionary computation: performance and scaling behavior

abstract: The challenge of ad-hoc computing is to find the way of taking advantage of spare cycles in an efficient way that takes into account all capabilities of the devices and interconnections available to them. In this paper we explore distributed evolutionary computation based on the Ruby on Rails framework, which overlays a Model-View-Controller on evolutionary computation. It allows anybody with a web browser (that is, mostly everybody connected to the Internet) to participate in an evolutionary computation experiment. Using a straightforward farming model, we consider different factors, such as the size of the population used. We are mostly interested in how they impact on performance, but also the scaling behavior when a non-trivial number of computers is applied to the problem. Experiments show the impact of different packet sizes on performance, as well as a quite limited scaling behavior, due to the characteristics of the server. Several solutions for that problem are proposed.


title: The Impact of CSI and Power Allocation on Relay Channel Capacity and Cooperation Strategies

abstract: Capacity gains from transmitter and receiver cooperation are compared in a relay network where the cooperating nodes are close together. Under quasi-static phase fading, when all nodes have equal average transmit power along with full channel state information (CSI), it is shown that transmitter cooperation outperforms receiver cooperation, whereas the opposite is true when power is optimally allocated among the cooperating nodes but only CSI at the receiver (CSIR) is available. When the nodes have equal power with CSIR only, cooperative schemes are shown to offer no capacity improvement over non-cooperation under the same network power constraint. When the system is under optimal power allocation with full CSI, the decode-and-forward transmitter cooperation rate is close to its cut-set capacity upper bound, and outperforms compress-and-forward receiver cooperation. Under fast Rayleigh fading in the high SNR regime, similar conclusions follow. Cooperative systems provide resilience to fading in channel magnitudes; however, capacity becomes more sensitive to power allocation, and the cooperating nodes need to be closer together for the decode-and-forward scheme to be capacity-achieving. Moreover, to realize capacity improvement, full CSI is necessary in transmitter cooperation, while in receiver cooperation optimal power allocation is essential.


title: Maximum Entropy in the framework of Algebraic Statistics: A First Step

abstract: Algebraic statistics is a recently evolving field, where one would treat statistical models as algebraic objects and thereby use tools from computational commutative algebra and algebraic geometry in the analysis and computation of statistical models. In this approach, calculation of parameters of statistical models amounts to solving set of polynomial equations in several variables, for which one can use celebrated Grobner bases theory. Owing to the important role of information theory in statistics, this paper as a first step, explores the possibility of describing maximum and minimum entropy (ME) models in the framework of algebraic statistics. We show that ME-models are toric models (a class of algebraic statistical models) when the constraint functions (that provide the information about the underlying random variable) are integer valued functions, and the set of statistical models that results from ME-methods are indeed an affine variety.


title: Optimal Order of Decoding for Max-Min Fairness in $K$-User Memoryless Interference Channels

abstract: A $K$-user memoryless interference channel is considered where each receiver sequentially decodes the data of a subset of transmitters before it decodes the data of the designated transmitter. Therefore, the data rate of each transmitter depends on (i) the subset of receivers which decode the data of that transmitter, (ii) the decoding order, employed at each of these receivers. In this paper, a greedy algorithm is developed to find the users which are decoded at each receiver and the corresponding decoding order such that the minimum rate of the users is maximized. It is proven that the proposed algorithm is optimal.


title: The framework for simulation of dynamics of mechanical aggregates

abstract: A framework for simulation of dynamics of mechanical aggregates has been developed. This framework enables us to build model of aggregate from models of its parts. Framework is a part of universal framework for science and engineering.


title: Algorithmic Complexity Bounds on Future Prediction Errors

abstract: We bound the future loss when predicting any (computably) stochastic sequence online. Solomonoff finitely bounded the total deviation of his universal predictor $M$ from the true distribution $mu$ by the algorithmic complexity of $mu$. Here we assume we are at a time $t>1$ and already observed $x=x_1...x_t$. We bound the future prediction performance on $x_{t+1}x_{t+2}...$ by a new variant of algorithmic complexity of $mu$ given $x$, plus the complexity of the randomness deficiency of $x$. The new complexity is monotone in its condition in the sense that this complexity can only decrease if the condition is prolonged. We also briefly discuss potential generalizations to Bayesian model classes and to classification problems.


title: Signature Sequence of Intersection Curve of Two Quadrics for Exact Morphological Classification

abstract: We present an efficient method for classifying the morphology of the intersection curve of two quadrics (QSIC) in PR3, 3D real projective space; here, the term morphology is used in a broad sense to mean the shape, topological, and algebraic properties of a QSIC, including singularity, reducibility, the number of connected components, and the degree of each irreducible component, etc. There are in total 35 different QSIC morphologies with non-degenerate quadric pencils. For each of these 35 QSIC morphologies, through a detailed study of the eigenvalue curve and the index function jump we establish a characterizing algebraic condition expressed in terms of the Segre characteristics and the signature sequence of a quadric pencil. We show how to compute a signature sequence with rational arithmetic so as to determine the morphology of the intersection curve of any two given quadrics. Two immediate applications of our results are the robust topological classification of QSIC in computing B-rep surface representation in solid modeling and the derivation of algebraic conditions for collision detection of quadric primitives.


title: Applications of Polyhedral Computations to the Analysis and Verification of Hardware and Software Systems

abstract: Convex polyhedra are the basis for several abstractions used in static analysis and computer-aided verification of complex and sometimes mission critical systems. For such applications, the identification of an appropriate complexity-precision trade-off is a particularly acute problem, so that the availability of a wide spectrum of alternative solutions is mandatory. We survey the range of applications of polyhedral computations in this area; give an overview of the different classes of polyhedra that may be adopted; outline the main polyhedral operations required by automatic analyzers and verifiers; and look at some possible combinations of polyhedra with other numerical abstractions that have the potential to improve the precision of the analysis. Areas where further theoretical investigations can result in important contributions are highlighted.


title: Feasible Depth

abstract: This paper introduces two complexity-theoretic formulations of Bennett's logical depth: finite-state depth and polynomial-time depth. It is shown that for both formulations, trivial and random infinite sequences are shallow, and a slow growth law holds, implying that deep sequences cannot be created easily from shallow sequences. Furthermore, the E analogue of the halting language is shown to be polynomial-time deep, by proving a more general result: every language to which a nonnegligible subset of E can be reduced in uniform exponential time is polynomial-time deep.


title: Group Secret Key Generation Algorithms

abstract: We consider a pair-wise independent network where every pair of terminals in the network observes a common pair-wise source that is independent of all the sources accessible to the other pairs. We propose a method for secret key agreement in such a network that is based on well-established point-to-point techniques and repeated application of the one-time pad. Three specific problems are investigated. 1) Each terminal's observations are correlated only with the observations of a central terminal. All these terminals wish to generate a common secret key. 2) In a pair-wise independent network, two designated terminals wish to generate a secret key with the help of other terminals. 3) All the terminals in a pair-wise independent network wish to generate a common secret key. A separate protocol for each of these problems is proposed. Furthermore, we show that the protocols for the first two problems are optimal and the protocol for the third problem is efficient, in terms of the resulting secret key rates.


title: Universal Algorithmic Intelligence: A mathematical top->down approach

abstract: Sequential decision theory formally solves the problem of rational agents in uncertain worlds if the true environmental prior probability distribution is known. Solomonoff's theory of universal induction formally solves the problem of sequence prediction for unknown prior distribution. We combine both ideas and get a parameter-free theory of universal Artificial Intelligence. We give strong arguments that the resulting AIXI model is the most intelligent unbiased agent possible. We outline how the AIXI model can formally solve a number of problem classes, including sequence prediction, strategic games, function minimization, reinforcement and supervised learning. The major drawback of the AIXI model is that it is uncomputable. To overcome this problem, we construct a modified algorithm AIXItl that is still effectively more intelligent than any other time t and length l bounded agent. The computation time of AIXItl is of the order t x 2^l. The discussion includes formal definitions of intelligence order relations, the horizon problem and relations of the AIXI theory to other AI approaches.


title: Optimal Throughput-Diversity-Delay Tradeoff in MIMO ARQ Block-Fading Channels

abstract: In this paper, we consider an automatic-repeat-request (ARQ) retransmission protocol signaling over a block-fading multiple-input, multiple-output (MIMO) channel. Unlike previous work, we allow for multiple fading blocks within each transmission (ARQ round), and we constrain the transmitter to fixed rate codes constructed over complex signal constellations. In particular, we examine the general case of average input-power-constrained constellations as well as the practically important case of finite discrete constellations. This scenario is a suitable model for practical wireless communications systems employing orthogonal frequency division multiplexing techniques over a MIMO ARQ channel. Two cases of fading dynamics are considered, namely short-term static fading where channel fading gains change randomly for each ARQ round, and long-term static fading where channel fading gains remain constant over all ARQ rounds pertaining to a given message. As our main result, we prove that for the block-fading MIMO ARQ channel with discrete input signal constellation satisfying a short-term power constraint, the optimal signal-to-noise ratio (SNR) exponent is given by a modified Singleton bound, relating all the system parameters. To demonstrate the practical significance of the theoretical analysis, we present numerical results showing that practical Singleton-bound-achieving maximum distance separable codes achieve the optimal SNR exponent.


title: A novel set of rotationally and translationally invariant features for images based on the non-commutative bispectrum

abstract: We propose a new set of rotationally and translationally invariant features for image or pattern recognition and classification. The new features are cubic polynomials in the pixel intensities and provide a richer representation of the original image than most existing systems of invariants. Our construction is based on the generalization of the concept of bispectrum to the three-dimensional rotation group SO(3), and a projection of the image onto the sphere.


title: Interference Automata

abstract: We propose a computing model, the Two-Way Optical Interference Automata (2OIA), that makes use of the phenomenon of optical interference. We introduce this model to investigate the increase in power, in terms of language recognition, of a classical Deterministic Finite Automaton (DFA) when endowed with the facility of optical interference. The question is in the spirit of Two-Way Finite Automata With Quantum and Classical States (2QCFA) [A. Ambainis and J. Watrous, Two-way Finite Automata With Quantum and Classical States, Theoretical Computer Science, 287 (1), 299-311, (2002)] wherein the classical DFA is augmented with a quantum component of constant size. We test the power of 2OIA against the languages mentioned in the above paper. We give efficient 2OIA algorithms to recognize languages for which 2QCFA machines have been shown to exist, as well as languages whose status vis-a-vis 2QCFA has been posed as open questions. Finally we show the existence of a language that cannot be recognized by a 2OIA but can be recognized by an $O(n^3)$ space Turing machine.


title: Space-time codes with controllable ML decoding complexity for any number of transmit antennas

abstract: We construct a class of linear space-time block codes for any number of transmit antennas that have controllable ML decoding complexity with a maximum rate of 1 symbol per channel use. The decoding complexity for $M$ transmit antennas can be varied from ML decoding of $2^{\lceil \log_2M \rceil -1}$ symbols together to single symbol ML decoding. For ML decoding of $2^{\lceil \log_2M \rceil - n}$ ($n=1,2,...$) symbols together, a diversity of $\min(M,2^{\lceil \log_2M \rceil-n+1})$ can be achieved. Numerical results show that the performance of the constructed code when $2^{\lceil \log_2M \rceil-1}$ symbols are decoded together is quite close to the performance of ideal rate-1 orthogonal codes (that are non-existent for more than 2 transmit antennas).


title: On the Correlation of Geographic and Network Proximity at Internet Edges and its Implications for Mobile Unicast and Multicast Routing

abstract: Significant effort has been invested recently to accelerate handover operations in a next generation mobile Internet. Corresponding works for developing efficient mobile multicast management are emergent. Both problems simultaneously expose routing complexity between subsequent points of attachment as a characteristic parameter for handover performance in access networks. As continuous mobility handovers necessarily occur between access routers located in geographic vicinity, this paper investigates on the hypothesis that geographically adjacent edge networks attain a reduced network distances as compared to arbitrary Internet nodes. We therefore evaluate and analyze edge distance distributions in various regions for clustered IP ranges on their geographic location such as a city. We use traceroute to collect packet forwarding path and round-trip-time of each intermediate node to scan-wise derive an upper bound of the node distances. Results of different scanning origins are compared to obtain the best estimation of network distance of each pair. Our results are compared with corresponding analysis of CAIDA Skitter data, overall leading to fairly stable, reproducible edge distance distributions. As a first conclusion on expected impact on handover performance measures, our results indicate a general optimum for handover anticipation time in 802.11 networks of 25 ms.


title: Effective Beam Width of Directional Antennas in Wireless Ad Hoc Networks

abstract: It is known at a qualitative level that directional antennas can be used to boost the capacity of wireless ad hoc networks. Lacking is a measure to quantify this advantage and to compare directional antennas of different footprint patterns. This paper introduces the concept of the effective beam width (and the effective null width as its dual counterpart) as a measure which quantitatively captures the capacity-boosting capability of directional antennas. Beam width is commonly defined to be the directional angle spread within which the main-lobe beam power is above a certain threshold. In contrast, our effective beam width definition lumps the effects of the (i) antenna pattern, (ii) active-node distribution, and (iii) channel characteristics, on network capacity into a single quantitative measure. We investigate the mathematical properties of the effective beam width and show how the convenience afforded by these properties can be used to analyze the effectiveness of complex directional antenna patterns in boosting network capacity, with fading and multi-user interference taken into account. In particular, we derive the extent to which network capacity can be scaled with the use of phased array antennas. We show that a phased array antenna with N elements can boost transport capacity of an Aloha-like network by a factor of order N^1.620.


title: Certifying controls and systems software

abstract: Software system certification presents itself with many challenges, including the necessity to certify the system at the level of functional requirements, code and binary levels, the need to chase down run-time errors, and the need for proving timing properties of the eventual, compiled system. This paper illustrates possible approaches for certifying code that arises from control systems requirements as far as stability properties are concerned. The relative simplicity of the certification process should encourage the development of systematic procedures for certifying control system codes for more complex environments.


title: The Case for Redundant Arrays of Internet Links (RAIL)

abstract: It is well-known that wide-area networks face today several performance and reliability problems. In this work, we propose to solve these problems by connecting two or more local-area networks together via a Redundant Array of Internet Links (or RAIL) and by proactively replicating each packet over these links. In that sense, RAIL is for networks what RAID (Redundant Array of Inexpensive Disks) was for disks. In this paper, we describe the RAIL approach, present our prototype (called the RAILedge), and evaluate its performance. First, we demonstrate that using multiple Internet links significantly improves the end-to-end performance in terms of network-level as well as application-level metrics for Voice-over-IP and TCP. Second, we show that a delay padding mechanism is needed to complement RAIL when there is significant delay disparity between the paths. Third, we show that two paths provide most of the benefit, if carefully managed. Finally, we discuss a RAIL-network architecture, where RAILedges make use of path redundancy, route control and application-specific mechanisms, to improve WAN performance.


title: Byzantine Fault Tolerance for Nondeterministic Applications

abstract: All practical applications contain some degree of nondeterminism. When such applications are replicated to achieve Byzantine fault tolerance (BFT), their nondeterministic operations must be controlled to ensure replica consistency. To the best of our knowledge, only the most simplistic types of replica nondeterminism have been dealt with. Furthermore, there lacks a systematic approach to handling common types of nondeterminism. In this paper, we propose a classification of common types of replica nondeterminism with respect to the requirement of achieving Byzantine fault tolerance, and describe the design and implementation of the core mechanisms necessary to handle such nondeterminism within a Byzantine fault tolerance framework.


title: Complex networks and human language

abstract: This paper introduces how human languages can be studied in light of recent development of network theories. There are two directions of exploration. One is to study networks existing in the language system. Various lexical networks can be built based on different relationships between words, being semantic or syntactic. Recent studies have shown that these lexical networks exhibit small-world and scale-free features. The other direction of exploration is to study networks of language users (i.e. social networks of people in the linguistic community), and their role in language evolution. Social networks also show small-world and scale-free features, which cannot be captured by random or regular network models. In the past, computational models of language change and language emergence often assume a population to have a random or regular structure, and there has been little discussion how network structures may affect the dynamics. In the second part of the paper, a series of simulation models of diffusion of linguistic innovation are used to illustrate the importance of choosing realistic conditions of population structure for modeling language change. Four types of social networks are compared, which exhibit two categories of diffusion dynamics. While the questions about which type of networks are more appropriate for modeling still remains, we give some preliminary suggestions for choosing the type of social networks for modeling.


title: Citation Advantage For OA Self-Archiving Is Independent of Journal Impact Factor, Article Age, and Number of Co-Authors

abstract: Eysenbach has suggested that the OA (Green) self-archiving advantage might just be an artifact of potential uncontrolled confounding factors such as article age (older articles may be both more cited and more likely to be self-archived), number of authors (articles with more authors might be more cited and more self-archived), subject matter (the subjects that are cited more, self-archive more), country (same thing), number of authors, citation counts of authors, etc. Chawki Hajjem (doctoral candidate, UQaM) had already shown that the OA advantage was present in all cases when articles were analysed separately by age, subject matter or country. He has now done a multiple regression analysis jointly testing (1) article age, (2) journal impact factor, (3) number of authors, and (4) OA self-archiving as separate factors for 442,750 articles in 576 (biomedical) journals across 11 years, and has shown that each of the four factors contributes an independent, statistically significant increment to the citation counts. The OA-self-archiving advantage remains a robust, independent factor. Having successfully responded to his challenge, we now challenge Eysenbach to demonstrate -- by testing a sufficiently broad and representative sample of journals at all levels of the journal quality, visibility and prestige hierarchy -- that his finding of a citation advantage for Gold OA (articles published OA on the high-profile website of the only journal he tested (PNAS) over Green OA articles in the same journal (self-archived on the author's website) was not just an artifact of having tested only one very high-profile journal.


title: The Open Access Citation Advantage: Quality Advantage Or Quality Bias?

abstract: Many studies have now reported the positive correlation between Open Access (OA) self-archiving and citation counts ("OA Advantage," OAA). But does this OAA occur because (QB) authors are more likely to self-selectively self-archive articles that are more likely to be cited (self-selection "Quality Bias": QB)? or because (QA) articles that are self-archived are more likely to be cited ("Quality Advantage": QA)? The probable answer is both. Three studies [by (i) Kurtz and co-workers in astrophysics, (ii) Moed in condensed matter physics, and (iii) Davis & Fromerth in mathematics] had reported the OAA to be due to QB [plus Early Advantage, EA, from self-archiving the preprint before publication, in (i) and (ii)] rather than QA. These three fields, however, (1) have less of a postprint access problem than most other fields and (i) and (ii) also happen to be among the minority of fields that (2) make heavy use of prepublication preprints. Chawki Hajjem has now analyzed preliminary evidence based on over 100,000 articles from multiple fields, comparing self-selected self-archiving with mandated self-archiving to estimate the contributions of QB and QA to the OAA. Both factors contribute, and the contribution of QA is greater.


title: Real-Time Model-Checking: Parameters everywhere

abstract: In this paper, we study the model-checking and parameter synthesis problems of the logic TCTL over discrete-timed automata where parameters are allowed both in the model (timed automaton) and in the property (temporal formula). Our results are as follows. On the negative side, we show that the model-checking problem of TCTL extended with parameters is undecidable over discrete-timed automata with only one parametric clock. The undecidability result needs equality in the logic. On the positive side, we show that the model-checking and the parameter synthesis problems become decidable for a fragment of the logic where equality is not allowed. Our method is based on automata theoretic principles and an extension of our method to express durations of runs in timed automata using Presburger arithmetic.


title: Time and the Prisoner's Dilemma

abstract: This paper examines the integration of computational complexity into game theoretic models. The example focused on is the Prisoner's Dilemma, repeated for a finite length of time. We show that a minimal bound on the players' computational ability is sufficient to enable cooperative behavior. In addition, a variant of the repeated Prisoner's Dilemma game is suggested, in which players have the choice of opting out. This modification enriches the game and suggests dominance of cooperative strategies. Competitive analysis is suggested as a tool for investigating sub-optimal (but computationally tractable) strategies and game theoretic models in general. Using competitive analysis, it is shown that for bounded players, a sub-optimal strategy might be the optimal choice, given resource limitations.


title: Predicate Abstraction with Under-approximation Refinement

abstract: We propose an abstraction-based model checking method which relies on refinement of an under-approximation of the feasible behaviors of the system under analysis. The method preserves errors to safety properties, since all analyzed behaviors are feasible by definition. The method does not require an abstract transition relation to be generated, but instead executes the concrete transitions while storing abstract versions of the concrete states, as specified by a set of abstraction predicates. For each explored transition the method checks, with the help of a theorem prover, whether there is any loss of precision introduced by abstraction. The results of these checks are used to decide termination or to refine the abstraction by generating new abstraction predicates. If the (possibly infinite) concrete system under analysis has a finite bisimulation quotient, then the method is guaranteed to eventually explore an equivalent finite bisimilar structure. We illustrate the application of the approach for checking concurrent programs.


title: The Fundamental Theorems of Interval Analysis

abstract: Expressions are not functions. Confusing the two concepts or failing to define the function that is computed by an expression weakens the rigour of interval arithmetic. We give such a definition and continue with the required re-statements and proofs of the fundamental theorems of interval arithmetic and interval analysis. Revision Feb. 10, 2009: added reference to and acknowledgement of P. Taylor.


title: Knowledge State Algorithms: Randomization with Limited Information

abstract: We introduce the concept of knowledge states; many well-known algorithms can be viewed as knowledge state algorithms. The knowledge state approach can be used to to construct competitive randomized online algorithms and study the tradeoff between competitiveness and memory. A knowledge state simply states conditional obligations of an adversary, by fixing a work function, and gives a distribution for the algorithm. When a knowledge state algorithm receives a request, it then calculates one or more "subsequent" knowledge states, together with a probability of transition to each. The algorithm then uses randomization to select one of those subsequents to be the new knowledge state. We apply the method to the paging problem. We present optimally competitive algorithm for paging for the cases where the cache sizes are k=2 and k=3. These algorithms use only a very limited number of bookmarks.


title: Dirac Notation, Fock Space and Riemann Metric Tensor in Information Retrieval Models

abstract: Using Dirac Notation as a powerful tool, we investigate the three classical Information Retrieval (IR) models and some their extensions. We show that almost all such models can be described by vectors in Occupation Number Representations (ONR) of Fock spaces with various specifications on, e.g., occupation number, inner product or term-term interactions. As important cases of study, Concept Fock Space (CFS) is introduced for Boolean model; the basic formulas for Singular Value Decomposition (SVD) of Latent Semantic Indexing (LSI) Model are manipulated in terms of Dirac notation. And, based on SVD, a Riemannian metric tensor is introduced, which not only can be used to calculate the relevance of documents to a query, but also may be used to measure the closeness of documents in data clustering.


title: Trusted Ticket Systems and Applications

abstract: Trusted Computing is a security base technology that will perhaps be ubiquitous in a few years in personal computers and mobile devices alike. Despite its neutrality with respect to applications, it has raised some privacy concerns. We show that trusted computing can be applied for service access control in a manner protecting users' privacy. We construct a ticket system -- a concept which is at the heart of Identity Management -- relying solely on the capabilities of the trusted platform module and the standards specified by the Trusted Computing Group. Two examples show how it can be used for pseudonymous and protected service access.


title: Non-Repudiation in Internet Telephony

abstract: We present a concept to achieve non-repudiation for natural language conversations over the Internet. The method rests on chained electronic signatures applied to pieces of packet-based, digital, voice communication. It establishes the integrity and authenticity of the bidirectional data stream and its temporal sequence and thus the security context of a conversation. The concept is close to the protocols for Voice over the Internet (VoIP), provides a high level of inherent security, and extends naturally to multilateral non-repudiation, e.g., for conferences. Signatures over conversations can become true declarations of will in analogy to electronically signed, digital documents. This enables binding verbal contracts, in principle between unacquainted speakers, and in particular without witnesses. A reference implementation of a secure VoIP archive is exhibited.


title: State constraints and list decoding for the AVC

abstract: List decoding for arbitrarily varying channels (AVCs) under state constraints is investigated. It is shown that rates within $\epsilon$ of the randomized coding capacity of AVCs with input-dependent state can be achieved under maximal error with list decoding using lists of size $O(1/\epsilon)$. Under average error an achievable rate region and converse bound are given for lists of size $L$. These bounds are based on two different notions of symmetrizability and do not coincide in general. An example is given that shows that for list size $L$ the capacity may be positive but strictly smaller than the randomized coding capacity. This behavior is different than the situation without state constraints.


title: A Generic Analysis Environment for Curry Programs

abstract: We present CurryBrowser, a generic analysis environment for the declarative multi-paradigm language Curry. CurryBrowser supports browsing through the program code of an application written in Curry, i.e., the main module and all directly or indirectly imported modules. Each module can be shown in different formats (e.g., source code, interface, intermediate code) and, inside each module, various properties of functions defined in this module can be analyzed. In order to support the integration of various program analyses, CurryBrowser has a generic interface to connect local and global analyses implemented in Curry. CurryBrowser is completely implemented in Curry using libraries for GUI programming and meta-programming.


title: Proceedings of the 16th Workshop in Logic-based Methods in Programming Environments (WLPE2006)

abstract: This volume contains the papers presented at WLPE'06: the 16th Workshop on Logic-based Methods in Programming Environments held on August 16, 2006 in the Seattle Sheraton Hotel and Towers, Seattle, Washington (USA). It was organised as a satellite workshop of ICLP'06, the 22th International Conference on Logic Programming.


title: Power-Bandwidth Tradeoff in Dense Multi-Antenna Relay Networks

abstract: We consider a dense fading multi-user network with multiple active multi-antenna source-destination pair terminals communicating simultaneously through a large common set of $K$ multi-antenna relay terminals in the full spatial multiplexing mode. We use Shannon-theoretic tools to analyze the tradeoff between energy efficiency and spectral efficiency (known as the power- bandwidth tradeoff) in meaningful asymptotic regimes of signal-to-noise ratio (SNR) and network size. We design linear distributed multi-antenna relay beamforming (LDMRB) schemes that exploit the spatial signature of multi-user interference and characterize their power-bandwidth tradeoff under a system wide power constraint on source and relay transmissions. The impact of multiple users, multiple relays and multiple antennas on the key performance measures of the high and low SNR regimes is investigated in order to shed new light on the possible reduction in power and bandwidth requirements through the usage of such practical relay cooperation techniques. Our results indicate that point-to-point coded multi-user networks supported by distributed relay beamforming techniques yield enhanced energy efficiency and spectral efficiency, and with appropriate signaling and sufficient antenna degrees of freedom, can achieve asymptotically optimal power-bandwidth tradeoff with the best possible (i.e., as in the cutset bound) energy scaling of $K^{-1}$ and the best possible spectral efficiency slope at any SNR for large number of relay terminals.


title: Contains and Inside relationships within combinatorial Pyramids

abstract: Irregular pyramids are made of a stack of successively reduced graphs embedded in the plane. Such pyramids are used within the segmentation framework to encode a hierarchy of partitions. The different graph models used within the irregular pyramid framework encode different types of relationships between regions. This paper compares different graph models used within the irregular pyramid framework according to a set of relationships between regions. We also define a new algorithm based on a pyramid of combinatorial maps which allows to determine if one region contains the other using only local calculus.


title: Time- and Space-Efficient Evaluation of Some Hypergeometric Constants

abstract: The currently best known algorithms for the numerical evaluation of hypergeometric constants such as $\zeta(3)$ to $d$ decimal digits have time complexity $O(M(d) \log^2 d)$ and space complexity of $O(d \log d)$ or $O(d)$. Following work from Cheng, Gergel, Kim and Zima, we present a new algorithm with the same asymptotic complexity, but more efficient in practice. Our implementation of this algorithm improves slightly over existing programs for the computation of $\pi$, and we announce a new record of 2 billion digits for $\zeta(3)$.


title: Characterization of Rate Region in Interference Channels with Constrained Power

abstract: In this paper, an $n$-user Gaussian interference channel, where the power of the transmitters are subject to some upper-bounds is studied. We obtain a closed-form expression for the rate region of such a channel based on the Perron-Frobenius theorem. While the boundary of the rate region for the case of unconstrained power is a well-established result, this is the first result for the case of constrained power. We extend this result to the time-varying channels and obtain a closed-form solution for the rate region of such channels.


title: Online Bandwidth Allocation

abstract: The paper investigates a version of the resource allocation problem arising in the wireless networking, namely in the OVSF code reallocation process. In this setting a complete binary tree of a given height $n$ is considered, together with a sequence of requests which have to be served in an online manner. The requests are of two types: an insertion request requires to allocate a complete subtree of a given height, and a deletion request frees a given allocated subtree. In order to serve an insertion request it might be necessary to move some already allocated subtrees to other locations in order to free a large enough subtree. We are interested in the worst case average number of such reallocations needed to serve a request. It was proved in previous work that the competitive ratio of the optimal online algorithm solving this problem is between 1.5 and O(n). We partially answer the question about its exact value by giving an O(1)-competitive online algorithm. Same model has been used in the context of memory management systems, and analyzed for the number of reallocations needed to serve a request in the worst case. In this setting, our result is a corresponding amortized analysis.


title: Logic Meets Algebra: the Case of Regular Languages

abstract: The study of finite automata and regular languages is a privileged meeting point of algebra and logic. Since the work of Buchi, regular languages have been classified according to their descriptive complexity, i.e. the type of logical formalism required to define them. The algebraic point of view on automata is an essential complement of this classification: by providing alternative, algebraic characterizations for the classes, it often yields the only opportunity for the design of algorithms that decide expressibility in some logical fragment. We survey the existing results relating the expressibility of regular languages in logical fragments of MSO[S] with algebraic properties of their minimal automata. In particular, we show that many of the best known results in this area share the same underlying mechanics and rely on a very strong relation between logical substitutions and block-products of pseudovarieties of monoid. We also explain the impact of these connections on circuit complexity theory.


title: Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Totals

abstract: Data analysis applications typically aggregate data across many dimensions looking for anomalies or unusual patterns. The SQL aggregate functions and the GROUP BY operator produce zero-dimensional or one-dimensional aggregates. Applications need the N-dimensional generalization of these operators. This paper defines that operator, called the data cube or simply cube. The cube operator generalizes the histogram, cross-tabulation, roll-up, drill-down, and sub-total constructs found in most report writers. The novelty is that cubes are relations. Consequently, the cube operator can be imbedded in more complex non-procedural data analysis programs. The cube operator treats each of the N aggregation attributes as a dimension of N-space. The aggregate of a particular set of attribute values is a point in this space. The set of points forms an N-dimensional cube. Super-aggregates are computed by aggregating the N-cube to lower dimensional spaces. This paper (1) explains the cube and roll-up operators, (2) shows how they fit in SQL, (3) explains how users can define new aggregate functions for cubes, and (4) discusses efficient techniques to compute the cube. Many of these features are being added to the SQL Standard.


title: Data Management: Past, Present, and Future

abstract: Soon most information will be available at your fingertips, anytime, anywhere. Rapid advances in storage, communications, and processing allow us move all information into Cyberspace. Software to define, search, and visualize online information is also a key to creating and accessing online information. This article traces the evolution of data management systems and outlines current trends. Data management systems began by automating traditional tasks: recording transactions in business, science, and commerce. This data consisted primarily of numbers and character strings. Today these systems provide the infrastructure for much of our society, allowing fast, reliable, secure, and automatic access to data distributed throughout the world. Increasingly these systems automatically design and manage access to the data. The next steps are to automate access to richer forms of data: images, sound, video, maps, and other media. A second major challenge is automatically summarizing and abstracting data in anticipation of user requests. These multi-media databases and tools to access them will be a cornerstone of our move to Cyberspace.


title: A Critique of ANSI SQL Isolation Levels

abstract: ANSI SQL-92 defines Isolation Levels in terms of phenomena: Dirty Reads, Non-Repeatable Reads, and Phantoms. This paper shows that these phenomena and the ANSI SQL definitions fail to characterize several popular isolation levels, including the standard locking implementations of the levels. Investigating the ambiguities of the phenomena leads to clearer definitions; in addition new phenomena that better characterize isolation types are introduced. An important multiversion isolation type, Snapshot Isolation, is defined.


title: Queues Are Databases

abstract: Message-oriented-middleware (MOM) has become an small industry. MOM offers queued transaction processing as an advance over pure client-server transaction processing. This note makes four points: Queued transaction processing is less general than direct transaction processing. Queued systems are built on top of direct systems. You cannot build a direct system atop a queued system. It is difficult to build direct, conversational, or distributed transactions atop a queued system. Queues are interesting databases with interesting concurrency control. It is best to build these mechanisms into a standard database system so other applications can use these interesting features. Queue systems need DBMS functionality. Queues need security, configuration, performance monitoring, recovery, and reorganization utilities. Database systems already have these features. A full-function MOM system duplicates these database features. Queue managers are simple TP-monitors managing server pools driven by queues. Database systems are encompassing many server pool features as they evolve to TP-lite systems.


title: Supporting Finite Element Analysis with a Relational Database Backend, Part I: There is Life beyond Files

abstract: In this paper, we show how to use a Relational Database Management System in support of Finite Element Analysis. We believe it is a new way of thinking about data management in well-understood applications to prepare them for two major challenges, - size and integration (globalization). Neither extreme size nor integration (with other applications over the Web) was a design concern 30 years ago when the paradigm for FEA implementation first was formed. On the other hand, database technology has come a long way since its inception and it is past time to highlight its usefulness to the field of scientific computing and computer based engineering. This series aims to widen the list of applications for database designers and for FEA users and application developers to reap some of the benefits of database development.


title: Supporting Finite Element Analysis with a Relational Database Backend, Part II: Database Design and Access

abstract: This is Part II of a three article series on using databases for Finite Element Analysis (FEA). It discusses (1) db design, (2) data loading, (3) typical use cases during grid building, (4) typical use cases during simulation (get and put), (5) typical use cases during analysis (also done in Part III) and some performance measures of these cases. It argues that using a database is simpler to implement than custom data schemas, has better performance because it can use data parallelism, and better supports FEA modularity and tool evolution because database schema evolution, data independence, and self-defining data.


title: Thousands of DebitCredit Transactions-Per-Second: Easy and Inexpensive

abstract: A $2k computer can execute about 8k transactions per second. This is 80x more than one of the largest US bank's 1970's traffic - it approximates the total US 1970's financial transaction volume. Very modest modern computers can easily solve yesterday's problems.


title: A Measure of Transaction Processing 20 Years Later

abstract: This provides a retrospective of the paper "A Measure of Transaction Processing" published in 1985. It shows that transaction processing peak performance and price-peformance have improved about 100,000x respectively and that sort/sequential performance has approximately doubled each year (so a million fold improvement) even though processor performance plateaued in 1995.


title: Using Table Valued Functions in SQL Server 2005 To Implement a Spatial Data Library

abstract: This article explains how to add spatial search functions (point-near-point and point in polygon) to Microsoft SQL Server 2005 using C# and table-valued functions. It is possible to use this library to add spatial search to your application without writing any special code. The library implements the public-domain C# Hierarchical Triangular Mesh (HTM) algorithms from Johns Hopkins University. That C# library is connected to SQL Server 2005 via a set of scalar-valued and table-valued functions. These functions act as a spatial index.


title: Indexing the Sphere with the Hierarchical Triangular Mesh

abstract: We describe a method to subdivide the surface of a sphere into spherical triangles of similar, but not identical, shapes and sizes. The Hierarchical Triangular Mesh (HTM) is a quad-tree that is particularly good at supporting searches at different resolutions, from arc seconds to hemispheres. The subdivision scheme is universal, providing the basis for addressing and for fast lookups. The HTM provides the basis for an efficient geospatial indexing scheme in relational databases where the data have an inherent location on either the celestial sphere or the Earth. The HTM index is superior to cartographical methods using coordinates with singularities at the poles. We also describe a way to specify surface regions that efficiently represent spherical query areas. This article presents the algorithms used to identify the HTM triangles covering such regions.


title: Petascale Computational Systems

abstract: Computational science is changing to be data intensive. Super-Computers must be balanced systems; not just CPU farms but also petascale IO and networking arrays. Anyone building CyberInfrastructure should allocate resources to support a balanced Tier-1 through Tier-3 design.


title: Empirical Measurements of Disk Failure Rates and Error Rates

abstract: The SATA advertised bit error rate of one error in 10 terabytes is frightening. We moved 2 PB through low-cost hardware and saw five disk read error events, several controller failures, and many system reboots caused by security patches. We conclude that SATA uncorrectable read errors are not yet a dominant system-fault source - they happen, but are rare compared to other problems. We also conclude that UER (uncorrectable error rate) is not the relevant metric for our needs. When an uncorrectable read error happens, there are typically several damaged storage blocks (and many uncorrectable read errors.) Also, some uncorrectable read errors may be masked by the operating system. The more meaningful metric for data architects is Mean Time To Data Loss (MTTDL.)


title: Large-Scale Query and XMatch, Entering the Parallel Zone

abstract: Current and future astronomical surveys are producing catalogs with millions and billions of objects. On-line access to such big datasets for data mining and cross-correlation is usually as highly desired as unfeasible. Providing these capabilities is becoming critical for the Virtual Observatory framework. In this paper we present various performance tests that show how using Relational Database Management Systems (RDBMS) and a Zoning algorithm to partition and parallelize the computation, we can facilitate large-scale query and cross-match.


title: To BLOB or Not To BLOB: Large Object Storage in a Database or a Filesystem?

abstract: Application designers often face the question of whether to store large objects in a filesystem or in a database. Often this decision is made for application design simplicity. Sometimes, performance measurements are also used. This paper looks at the question of fragmentation - one of the operational issues that can affect the performance and/or manageability of the system as deployed long term. As expected from the common wisdom, objects smaller than 256KB are best stored in a database while objects larger than 1M are best stored in the filesystem. Between 256KB and 1MB, the read:write ratio and rate of object overwrite or replacement are important factors. We used the notion of "storage age" or number of object overwrites as way of normalizing wall clock time. Storage age allows our results or similar such results to be applied across a number of read:write ratios and object replacement rates.


title: A Framework for Designing MIMO systems with Decision Feedback Equalization or Tomlinson-Harashima Precoding

abstract: We consider joint transceiver design for general Multiple-Input Multiple-Output communication systems that implement interference (pre-)subtraction, such as those based on Decision Feedback Equalization (DFE) or Tomlinson-Harashima precoding (THP). We develop a unified framework for joint transceiver design by considering design criteria that are expressed as functions of the Mean Square Error (MSE) of the individual data streams. By deriving two inequalities that involve the logarithms of the individual MSEs, we obtain optimal designs for two classes of communication objectives, namely those that are Schur-convex and Schur-concave functions of these logarithms. For Schur-convex objectives, the optimal design results in data streams with equal MSEs. This design simultaneously minimizes the total MSE and maximizes the mutual information for the DFE-based model. For Schur-concave objectives, the optimal DFE design results in linear equalization and the optimal THP design results in linear precoding. The proposed framework embraces a wide range of design objectives and can be regarded as a counterpart of the existing framework of linear transceiver design.


title: Life Under Your Feet: An End-to-End Soil Ecology Sensor Network, Database, Web Server, and Analysis Service

abstract: Wireless sensor networks can revolutionize soil ecology by providing measurements at temporal and spatial granularities previously impossible. This paper presents a soil monitoring system we developed and deployed at an urban forest in Baltimore as a first step towards realizing this vision. Motes in this network measure and save soil moisture and temperature in situ every minute. Raw measurements are periodically retrieved by a sensor gateway and stored in a central database where calibrated versions are derived and stored. The measurement database is published through Web Services interfaces. In addition, analysis tools let scientists analyze current and historical data and help manage the sensor network. The article describes the system design, what we learned from the deployment, and initial results obtained from the sensors. The system measures soil factors with unprecedented temporal precision. However, the deployment required device-level programming, sensor calibration across space and time, and cross-referencing measurements with external sources. The database, web server, and data analysis design required considerable innovation and expertise. So, the ratio of computer-scientists to ecologists was 3:1. Before sensor networks can fulfill their potential as instruments that can be easily deployed by scientists, these technical problems must be addressed so that the ratio is one nerd per ten ecologists.


title: The Zones Algorithm for Finding Points-Near-a-Point or Cross-Matching Spatial Datasets

abstract: Zones index an N-dimensional Euclidian or metric space to efficiently support points-near-a-point queries either within a dataset or between two datasets. The approach uses relational algebra and the B-Tree mechanism found in almost all relational database systems. Hence, the Zones Algorithm gives a portable-relational implementation of points-near-point, spatial cross-match, and self-match queries. This article corrects some mistakes in an earlier article we wrote on the Zones Algorithm and describes some algorithmic improvements. The Appendix includes an implementation of point-near-point, self-match, and cross-match using the USGS city and stream gauge database.


abstract: Cross-match spatially clusters and organizes several astronomical point-source measurements from one or more surveys. Ideally, each object would be found in each survey. Unfortunately, the observation conditions and the objects themselves change continually. Even some stationary objects are missing in some observations; sometimes objects have a variable light flux and sometimes the seeing is worse. In most cases we are faced with a substantial number of differences in object detections between surveys and between observations taken at different times within the same survey or instrument. Dealing with such missing observations is a difficult problem. The first step is to classify misses as ephemeral - when the object moved or simply disappeared, masked - when noise hid or corrupted the object observation, or edge - when the object was near the edge of the observational field. This classification and a spatial library to represent and manipulate observational footprints help construct a Match table recording both hits and misses. Transitive closure clusters friends-of-friends into object bundles. The bundle summary statistics are recorded in a Bundle table. This design is an evolution of the Sloan Digital Sky Survey cross-match design that compared overlapping observations taken at different times. Cross-Matching Multiple Spatial Observations and Dealing with Missing Data.


title: SkyServer Traffic Report - The First Five Years

abstract: The SkyServer is an Internet portal to the Sloan Digital Sky Survey Catalog Archive Server. From 2001 to 2006, there were a million visitors in 3 million sessions generating 170 million Web hits, 16 million ad-hoc SQL queries, and 62 million page views. The site currently averages 35 thousand visitors and 400 thousand sessions per month. The Web and SQL logs are public. We analyzed traffic and sessions by duration, usage pattern, data product, and client type (mortal or bot) over time. The analysis shows (1) the site's popularity, (2) the educational website that delivered nearly fifty thousand hours of interactive instruction, (3) the relative use of interactive, programmatic, and batch-local access, (4) the success of offering ad-hoc SQL, personal database, and batch job access to scientists as part of the data publication, (5) the continuing interest in "old" datasets, (6) the usage of SQL constructs, and (7) a novel approach of using the corpus of correct SQL queries to suggest similar but correct statements when a user presents an incorrect SQL statement.


title: A Prototype for Educational Planning Using Course Constraints to Simulate Student Populations

abstract: Distance learning universities usually afford their students the flexibility to advance their studies at their own pace. This can lead to a considerable fluctuation of student populations within a program's courses, possibly affecting the academic viability of a program as well as the related required resources. Providing a method that estimates this population could be of substantial help to university management and academic personnel. We describe how to use course precedence constraints to calculate alternative tuition paths and then use Markov models to estimate future populations. In doing so, we identify key issues of a large scale potential deployment.


title: On the Software and Knowledge Engineering Aspects of the Educational Process

abstract: The Hellenic Open University has embarked on a large-scale effort to enhance its textbook-based material with content that demonstrably supports the basic tenets of distance learning. The challenge is to set up a framework that allows for the production-level creation, distribution and consumption of content, and at the same time, evaluate the effort in terms of technological, educational and organizational knowledge gained. This paper presents a model of the educational process that is used as a development backbone and argues about its conceptual and technical practicality at large.


title: Towards Practical Typechecking for Macro Tree Transducers

abstract: Macro tree transducers (mtt) are an important model that both covers many useful XML transformations and allows decidable exact typechecking. This paper reports our first step toward an implementation of mtt typechecker that has a practical efficiency. Our approach is to represent an input type obtained from a backward inference as an alternating tree automaton, in a style similar to Tozawa's XSLT0 typechecking. In this approach, typechecking reduces to checking emptiness of an alternating tree automaton. We propose several optimizations (Cartesian factorization, state partitioning) on the backward inference process in order to produce much smaller alternating tree automata than the naive algorithm, and we present our efficient algorithm for checking emptiness of alternating tree automata, where we exploit the explicit representation of alternation for local optimizations. Our preliminary experiments confirm that our algorithm has a practical performance that can typecheck simple transformations with respect to the full XHTML in a reasonable time.


title: Pitch Tracking of Acoustic Signals based on Average Squared Mean Difference Function

abstract: In this paper, a method of pitch tracking based on variance minimization of locally periodic subsamples of an acoustic signal is presented. Replicates along the length of the periodically sampled data of the signal vector are taken and locally averaged sample variances are minimized to estimate the fundamental frequency. Using this method, pitch tracking of any text independent voiced signal is possible for different speakers.


title: Distributed Detection in Sensor Networks with Limited Range Sensors

abstract: We consider a multi-object detection problem over a sensor network (SNET) with limited range sensors. This problem complements the widely considered decentralized detection problem where all sensors observe the same object. While the necessity for global collaboration is clear in the decentralized detection problem, the benefits of collaboration with limited range sensors is unclear and has not been widely explored. In this paper we develop a distributed detection approach based on recent development of the false discovery rate (FDR). We first extend the FDR procedure and develop a transformation that exploits complete or partial knowledge of either the observed distributions at each sensor or the ensemble (mixture) distribution across all sensors. We then show that this transformation applies to multi-dimensional observations, thus extending FDR to multi-dimensional settings. We also extend FDR theory to cases where distributions under both null and positive hypotheses are uncertain. We then propose a robust distributed algorithm to perform detection. We further demonstrate scalability to large SNETs by showing that the upper bound on the communication complexity scales linearly with the number of sensors that are in the vicinity of objects and is independent of the total number of sensors. Finally, we deal with situations where the sensing model may be uncertain and establish robustness of our techniques to such uncertainties.


title: Scatter of Weak Robots

abstract: In this paper, we first formalize the problem to be solved, i.e., the Scatter Problem (SP). We then show that SP cannot be deterministically solved. Next, we propose a randomized algorithm for this problem. The proposed solution is trivially self-stabilizing. We then show how to design a self-stabilizing version of any deterministic solution for the Pattern Formation and the Gathering problems.


title: Ontology from Local Hierarchical Structure in Text

abstract: We study the notion of hierarchy in the context of visualizing textual data and navigating text collections. A formal framework for ``hierarchy'' is given by an ultrametric topology. This provides us with a theoretical foundation for concept hierarchy creation. A major objective is {\em scalable} annotation or labeling of concept maps. Serendipitously we pursue other objectives such as deriving common word pair (and triplet) phrases, i.e., word 2- and 3-grams. We evaluate our approach using (i) a collection of texts, (ii) a single text subdivided into successive parts (for which we provide an interactive demonstrator), and (iii) a text subdivided at the sentence or line level. While detailing a generic framework, a distinguishing feature of our work is that we focus on {\em locality} of hierarchic structure in order to extract semantic information.


title: A Note on Local Ultrametricity in Text

abstract: High dimensional, sparsely populated data spaces have been characterized in terms of ultrametric topology. This implies that there are natural, not necessarily unique, tree or hierarchy structures defined by the ultrametric topology. In this note we study the extent of local ultrametric topology in texts, with the aim of finding unique ``fingerprints'' for a text or corpus, discriminating between texts from different domains, and opening up the possibility of exploiting hierarchical structures in the data. We use coherent and meaningful collections of over 1000 texts, comprising over 1.3 million words.


title: Supplement to: Code Spectrum and Reliability Function: Binary Symmetric Channel

abstract: A much simpler proof of Theorem 1 from M.Burnashev "Code spectrum and reliability function: Binary symmetric channel" is presented.


title: Certification of the QR factor R, and of lattice basis reducedness

abstract: Given a lattice basis of n vectors in Z^n, we propose an algorithm using 12n^3+O(n^2) floating point operations for checking whether the basis is LLL-reduced. If the basis is reduced then the algorithm will hopefully answer ''yes''. If the basis is not reduced, or if the precision used is not sufficient with respect to n, and to the numerical properties of the basis, the algorithm will answer ''failed''. Hence a positive answer is a rigorous certificate. For implementing the certificate itself, we propose a floating point algorithm for computing (certified) error bounds for the entries of the R factor of the QR matrix factorization. This algorithm takes into account all possible approximation and rounding errors. The cost 12n^3+O(n^2) of the certificate is only six times more than the cost of numerical algorithms for computing the QR factorization itself, and the certificate may be implemented using matrix library routines only. We report experiments that show that for a reduced basis of adequate dimension and quality the certificate succeeds, and establish the effectiveness of the certificate. This effectiveness is applied for certifying the output of fastest existing floating point heuristics of LLL reduction, without slowing down the whole process.


title: Structure and Problem Hardness: Goal Asymmetry and DPLL Proofs in<br> SAT-Based Planning

abstract: In Verification and in (optimal) AI Planning, a successful method is to formulate the application as boolean satisfiability (SAT), and solve it with state-of-the-art DPLL-based procedures. There is a lack of understanding of why this works so well. Focussing on the Planning context, we identify a form of problem structure concerned with the symmetrical or asymmetrical nature of the cost of achieving the individual planning goals. We quantify this sort of structure with a simple numeric parameter called AsymRatio, ranging between 0 and 1. We run experiments in 10 benchmark domains from the International Planning Competitions since 2000; we show that AsymRatio is a good indicator of SAT solver performance in 8 of these domains. We then examine carefully crafted synthetic planning domains that allow control of the amount of structure, and that are clean enough for a rigorous analysis of the combinatorial search space. The domains are parameterized by size, and by the amount of structure. The CNFs we examine are unsatisfiable, encoding one planning step less than the length of the optimal plan. We prove upper and lower bounds on the size of the best possible DPLL refutations, under different settings of the amount of structure, as a function of size. We also identify the best possible sets of branching variables (backdoors). With minimum AsymRatio, we prove exponential lower bounds, and identify minimal backdoors of size linear in the number of variables. With maximum AsymRatio, we identify logarithmic DPLL refutations (and backdoors), showing a doubly exponential gap between the two structural extreme cases. The reasons for this behavior -- the proof arguments -- illuminate the prototypical patterns of structure causing the empirical behavior observed in the competition benchmarks.


title: Graph Operations on Clique-Width Bounded Graphs

abstract: Clique-width is a well-known graph parameter. Many NP-hard graph problems admit polynomial-time solutions when restricted to graphs of bounded clique-width. The same holds for NLC-width. In this paper we study the behavior of clique-width and NLC-width under various graph operations and graph transformations. We give upper and lower bounds for the clique-width and NLC-width of the modified graphs in terms of the clique-width and NLC-width of the involved graphs.


title: Certification of bounds on expressions involving rounded operators

abstract: Gappa uses interval arithmetic to certify bounds on mathematical expressions that involve rounded as well as exact operators. Gappa generates a theorem with its proof for each bound treated. The proof can be checked with a higher order logic automatic proof checker, either Coq or HOL Light, and we have developed a large companion library of verified facts for Coq dealing with the addition, multiplication, division, and square root, in fixed- and floating-point arithmetics. Gappa uses multiple-precision dyadic fractions for the endpoints of intervals and performs forward error analysis on rounded operators when necessary. When asked, Gappa reports the best bounds it is able to reach for a given expression in a given context. This feature is used to quickly obtain coarse bounds. It can also be used to identify where the set of facts and automatic techniques implemented in Gappa becomes insufficient. Gappa handles seamlessly additional properties expressed as interval properties or rewriting rules in order to establish more intricate bounds. Recent work showed that Gappa is perfectly suited to the proof of correctness of small pieces of software. Proof obligations can be written by designers, produced by third-party tools or obtained by overloading arithmetic operators.


title: Verification Across Intellectual Property Boundaries

abstract: In many industries, the importance of software components provided by third-party suppliers is steadily increasing. As the suppliers seek to secure their intellectual property (IP) rights, the customer usually has no direct access to the suppliers' source code, and is able to enforce the use of verification tools only by legal requirements. In turn, the supplier has no means to convince the customer about successful verification without revealing the source code. This paper presents an approach to resolve the conflict between the IP interests of the supplier and the quality interests of the customer. We introduce a protocol in which a dedicated server (called the "amanat") is controlled by both parties: the customer controls the verification task performed by the amanat, while the supplier controls the communication channels of the amanat to ensure that the amanat does not leak information about the source code. We argue that the protocol is both practically useful and mathematically sound. As the protocol is based on well-known (and relatively lightweight) cryptographic primitives, it allows a straightforward implementation on top of existing verification tool chains. To substantiate our security claims, we establish the correctness of the protocol by cryptographic reduction proofs.


title: Faster Inversion and Other Black Box Matrix Computations Using Efficient Block Projections

abstract: Block projections have been used, in [Eberly et al. 2006], to obtain an efficient algorithm to find solutions for sparse systems of linear equations. A bound of softO(n^(2.5)) machine operations is obtained assuming that the input matrix can be multiplied by a vector with constant-sized entries in softO(n) machine operations. Unfortunately, the correctness of this algorithm depends on the existence of efficient block projections, and this has been conjectured. In this paper we establish the correctness of the algorithm from [Eberly et al. 2006] by proving the existence of efficient block projections over sufficiently large fields. We demonstrate the usefulness of these projections by deriving improved bounds for the cost of several matrix problems, considering, in particular, ``sparse'' matrices that can be be multiplied by a vector using softO(n) field operations. We show how to compute the inverse of a sparse matrix over a field F using an expected number of softO(n^(2.27)) operations in F. A basis for the null space of a sparse matrix, and a certification of its rank, are obtained at the same cost. An application to Kaltofen and Villard's Baby-Steps/Giant-Steps algorithms for the determinant and Smith Form of an integer matrix yields algorithms requiring softO(n^(2.66)) machine operations. The derived algorithms are all probabilistic of the Las Vegas type.


title: A New Self-Stabilizing Maximal Matching Algorithm

abstract: The maximal matching problem has received considerable attention in the self-stabilizing community. Previous work has given different self-stabilizing algorithms that solves the problem for both the adversarial and fair distributed daemon, the sequential adversarial daemon, as well as the synchronous daemon. In the following we present a single self-stabilizing algorithm for this problem that unites all of these algorithms in that it stabilizes in the same number of moves as the previous best algorithms for the sequential adversarial, the distributed fair, and the synchronous daemon. In addition, the algorithm improves the previous best moves complexities for the distributed adversarial daemon from O(n^2) and O(delta m) to O(m) where n is the number of processes, m is thenumber of edges, and delta is the maximum degree in the graph.


title: A Peer-to-Peer Browsable File Index using a Popularity Based Global Namespace

abstract: The distribution of files using decentralized, peer-to-peer (P2P) systems, has significant advantages over centralized approaches. It is however more difficult to settle on the best approach for file sharing. Most file sharing systems are based on query string searches, leading to a relatively simple but inefficient broadcast or to an efficient but relatively complicated index in a structured environment. In this paper we use a browsable peer-to-peer file index consisting of files which serve as directory nodes, interconnecting to form a directory network. We implemented the system based on BitTorrent and Kademlia. The directory network inherits all of the advantages of decentralization and provides browsable, efficient searching. To avoid conflict between users in the P2P system while also imposing no additional restrictions, we allow multiple versions of each directory node to simultaneously exist -- using popularity as the basis for default browsing behavior. Users can freely add files and directory nodes to the network. We show, using a simulation of user behavior and file quality, that the popularity based system consistently leads users to a high quality directory network; above the average quality of user updates. Q


title: The parallel implementation of the Astr\'{e}e static analyzer

abstract: The Astr\'{e}e static analyzer is a specialized tool that can prove the absence of runtime errors, including arithmetic overflows, in large critical programs. Keeping analysis times reasonable for industrial use is one of the design objectives. In this paper, we discuss the parallel implementation of the analysis.


title: The pitfalls of verifying floating-point computations

abstract: Current critical systems commonly use a lot of floating-point computations, and thus the testing or static analysis of programs containing floating-point operators has become a priority. However, correctly defining the semantics of common implementations of floating-point is tricky, because semantics may change with many factors beyond source-code level, such as choices made by compilers. We here give concrete examples of problems that can appear and solutions to implement in analysis software.


title: A Static Analyzer for Large Safety-Critical Software

abstract: We show that abstract interpretation-based static program analysis can be made efficient and precise enough to formally verify a class of properties for a family of large programs with few or no false alarms. This is achieved by refinement of a general purpose static analyzer and later adaptation to particular programs of the family by the end-user through parametrization. This is applied to the proof of soundness of data manipulation operations at the machine level for periodic synchronous safety critical embedded software. The main novelties are the design principle of static analyzers by refinement and adaptation through parametrization, the symbolic manipulation of expressions to improve the precision of abstract transfer functions, the octagon, ellipsoid, and decision tree abstract domains, all with sound handling of rounding errors in floating point computations, widening strategies (with thresholds, delayed) and the automatic determination of the parameters (parametrized packing).