BSP -Style Computation: A Semantic Investigation

A BSP (Bulk Synchronous Parallelism) computation is characterized by the generation of asynchronous messages in packages during independent execution of a number of processes and their subsequent delivery at synchronization points. Bundling messages together represents a significant departure from the traditional ‘one communication at a time’ approach. In this paper the semantic consequences of communication packaging are explored. In particular, the BSP communication structure is identified with a general form of substitution—predicate substitution. Predicate substitution provides a means of reasoning about the synchronized delivery of asynchronous communications when the immediate programming context does not explicitly refer to the variables that are to be updated (unlike traditional operations, such as the assignment $x := e$, where the names of the updated variables can be extracted from the context). Proofs of implementations of Newton's root finding method and prefix sum are used to illustrate the practical application of the proposed approach.

Towards hierarchical management of autonomic components: a case study

We address the issue of autonomic management in hierarchical component-based distributed systems. The long term aim is to provide a modelling framework for autonomic management in which QoS goals can be defined, plans for system adaptation described and proofs of achievement of goals by (sequences of) adaptations furnished. Here we present an early step on this path. We restrict our focus to skeleton-based systems in order to exploit their well-defined structure. The autonomic cycle is described using the Orc system orchestration language while the plans are presented as structural modifications together with associated costs and benefits. A case study is presented to illustrate the interaction of managers to maintain QoS goals for throughput under varying conditions of resource availability.

On the continuity of the support of masa-bimodules

We anounce results on the continuity of the map sending a masa-bimodule to its support. The proofs of the results will be published elsewhere.

Unitary SK1 of unitary and graded division algebras

The reduced unitary Whitehead group $\SK$ of a graded division algebra equipped with a unitary involution (i.e., an involution of the second kind) and graded by a torsion-free abelian group is studied. It is shown that calculations in the graded setting are much simpler than their nongraded counterparts. The bridge to the non-graded case is established by proving that the unitary $\SK$ of a tame valued division algebra wih a unitary involution over a henselian field coincides with the unitary $\SK$ of its associated graded division algebra. As a consequence, the graded approach allows us not only to recover results available in the literature with substantially easier proofs, but also to calculate the unitary $\SK$ for much wider classes of division algebras over henselian fields.

Towards identification of Wiener systems with the least amount of a priori information on the nonlinearity

In this paper, we investigate what constitutes the least amount of a priori information on the nonlinearity so that the FIR linear part is identifiable in the non-Gaussian input case. Three types of a priori information are considered including quadrant information, point information and locally monotonous information. In all three cases, identifiability has been established and corresponding identification algorithms are developed with their convergence proofs.

The Computational Complexity of Dominance and Consistency in CP-Nets

We investigate the computational complexity of testing dominance and consistency in CP-nets. Previously, the complexity of dominance has been determined for restricted classes in which the dependency graph of the CP-net is acyclic. However, there are preferences of interest that define cyclic dependency graphs; these are modeled with general CP-nets. In our main results, we show here that both dominance and consistency for general CP-nets are PSPACE-complete. We then consider the concept of strong dominance, dominance equivalence and dominance incomparability, and several notions of optimality, and identify the complexity of the corresponding decision problems. The reductions used in the proofs are from STRIPS planning, and thus reinforce the earlier established connections between both areas.

Characterization of Transmission Losses

In this paper, characterizing transmission losses according to their origin is carried out. Transmission loss is decomposed into three components. The first is due to the current flow from generators to loads. The second is due to the circulating current between generators. The third represents the contribution of network structure and controls to increasing or decreasing transmission losses. Analytical proofs of the proposed loss decomposition are presented along with methods of allocating each component to the parties contributing to it. Illustration on simple dc and ac systems is presented. Results of application of the proposed method compared with other methods are also presented.

Modified Information Criteria and Selection of Long Memory Time Series Models

The problem of model selection of a univariate long memory time series is investigated once a semi parametric estimator for the long memory parameter has been used. Standard information criteria are not consistent in this case. A Modified Information Criterion (MIC) that overcomes these difficulties is introduced and proofs that show its asymptotic validity are provided. The results are general and cover a wide range of short memory processes. Simulation evidence compares the new and existing methodologies and empirical applications in monthly inflation and daily realized volatility are presented.

New Results for the MAP Problem in Bayesian Networks

This paper presents new results for the (partial) maximum a posteriori (MAP) problem in Bayesian networks, which is the problem of querying the most probable state configuration of some of the network variables given evidence. First, it is demonstrated that the problem remains hard even in networks with very simple topology, such as binary polytrees and simple trees (including the Naive Bayes structure). Such proofs extend previous complexity results for the problem. Inapproximability results are also derived in the case of trees if the number of states per variable is not bounded. Although the problem is shown to be hard and inapproximable even in very simple scenarios, a new exact algorithm is described that is empirically fast in networks of bounded treewidth and bounded number of states per variable. The same algorithm is used as basis of a Fully Polynomial Time Approximation Scheme for MAP under such assumptions. Approximation schemes were generally thought to be impossible for this problem, but we show otherwise for classes of networks that are important in practice. The algorithms are extensively tested using some well-known networks as well as random generated cases to show their effectiveness.

Fast Rule Mining over Multi-dimensional Windows

Association rule mining is an indispensable tool for discovering
insights from large databases and data warehouses.
The data in a warehouse being multi-dimensional, it is often
useful to mine rules over subsets of data defined by selections
over the dimensions. Such interactive rule mining
over multi-dimensional query windows is difficult since rule
mining is computationally expensive. Current methods using
pre-computation of frequent itemsets require counting
of some itemsets by revisiting the transaction database at
query time, which is very expensive. We develop a method
(RMW) that identifies the minimal set of itemsets to compute
and store for each cell, so that rule mining over any
query window may be performed without going back to the
transaction database. We give formal proofs that the set of
itemsets chosen by RMW is sufficient to answer any query
and also prove that it is the optimal set to be computed
for 1 dimensional queries. We demonstrate through an extensive
empirical evaluation that RMW achieves extremely
fast query response time compared to existing methods, with
only moderate overhead in pre-computation and storage

Triangular Objects and Systematic K-Theory

We investigate modules over “systematic” rings. Such rings are “almost graded” and have appeared under various names in the literature; they are special cases of the G-systems of Grzeszczuk. We analyse their K-theory in the presence of conditions on the support, and explain how this generalises and unifies calculations of graded and filtered K-theory scattered in the literature. Our treatment makes systematic use of the formalism of idempotent completion and a theory of triangular objects in additive categories, leading to elementary and transparent proofs throughout.