On the Minimization of Communication in Networked Systems with a Central Station

The problem of minimizing communication in a distributed networked system is considered in a discrete-event formalism where the system is modeled as a finite-state automaton. The system consists of a central station and a set of N local agents, each observing a set of local events. The central station needs to know exactly the state of the system, whereas local agents need to disambiguate certain pre-specified pairs of states for purposes of control or diagnosis. This requirement is achieved by communication, which occurs only between the central station and the local agents but not among the local agents. A communication policy is defined as a set of event occurrences to be communicated between the central station and the local agents. A communication policy is said to be minimal if any removal of communication of event occurrences will affect the correctness of the solution. Under an assumption on the absence of cycles (other than self-loops) in the system model, this paper presents an algorithm that computes a minimal communication policy in polynomial time in all parameters of the system. These results improve upon previous algorithms for solving minimum communication problems.

Diagnosability Analysis of a Class of Hierarchical State Machines

This paper addresses the problem of fault detection and isolation for a particular class of discrete event dynamical systems called hierarchical finite state machines (HFSMs). A new version of the property of diagnosability for discrete event systems tailored to HFSMs is introduced. This notion, called L₁-diagnosability, captures the possibility of detecting an unobservable fault event using only high level observations of the behavior of an HFSM. Algorithms for testing L₁-diagnosability are presented. In addition, new methodologies are presented for studying the diagnosability properties of HFSMs that are not L₁-diagnosable. These methodologies avoid the complete expansion of an HFSM into its corresponding flat automaton by focusing the expansion on problematic indeterminate cycles only in the associated extended diagnoser.

Optimal Node Visitation in Acyclic Stochastic Digraphs with Multi-threaded Traversals and Internal Visitation Requirements

The original definition of the problem of optimal node visitation (ONV) in acyclic stochastic digraphs concerns the identification of a routing policy that will enable the visitation of each leaf node a requested number of times, while minimizing the expected number of the graph traversals. The original work of Bountourelis and Reveliotis (2006) formulated this problem as a Stochastic Shortest Path (SSP) problem, and since the state space of this SSP formulation is exponentially sized with respect to the number of the target nodes, it also proposed a suboptimal policy that is computationally tractable and asymptotically optimal. This paper extends the results of Bountourelis and Reveliotis (2006) to the cases where (i) the tokens traversing the graph can “split” during certain transitions to a number of (sub-)tokens, allowing, thus, the satisfaction of many visitation requirements during a single graph traversal, and (ii) there are additional visitation requirements attached to the internal graph nodes, which, however, can be served only when the visitation requirements of their successors have been fully met. In addition, the presented set of results establishes stronger convergence properties for the proposed suboptimal policies, and it provides a formal complexity analysis of the considered ONV formulations. From a practical standpoint, the extension of the original results performed in this paper enables their effective usage in the application domains that motivated the ONV problem, in the first place.

An inexpensive unstructured platform for wireless mobile peer-to-peer networks

In this paper, we propose an unstructured platform, namely I nexpensive P eer-to- P eer S ubsystem (IPPS), for wireless mobile peer-to-peer networks. The platform addresses the constraints of expensive bandwidth of wireless medium, and limited memory and computing power of mobile devices. It uses a computationally-, memory requirement- and communication- wise inexpensive gossip protocol as the main maintenance operation, and exploits location information of the wireless nodes to minimize the number of link-level messages for communication between peers. As a result, the platform is not only lightweight by itself, but also provides a low cost framework for different peer-to-peer applications. In addition, further enhancements are introduced to enrich the platform with robustness and tolerance to failures without incurring any additional computational and memory complexity, and communication between peers. In specific, we propose schemes for a peer (1) to chose a partner for a gossip iteration, (2) to maintain the neighbors, and (3) to leave the peer-to-peer network. Simulation results are given to demonstrate the performance of the platform.

A New Learning Algorithm for Optimal Stopping

A linear programming formulation of the optimal stopping problem for Markov decision processes is approximated using linear function approximation. Using this formulation, a reinforcement learning scheme based on a primal-dual method and incorporating a sampling device called ‘split sampling’ is proposed and analyzed. An illustrative example from option pricing is also included.

On the relative value of cross-company and within-company data for defect prediction

We propose a practical defect prediction approach for companies that do not track defect related data. Specifically, we investigate the applicability of cross-company (CC) data for building localized defect predictors using static code features. Firstly, we analyze the conditions, where CC data can be used as is. These conditions turn out to be quite few. Then we apply principles of analogy-based learning (i.e. nearest neighbor (NN) filtering) to CC data, in order to fine tune these models for localization. We compare the performance of these models with that of defect predictors learned from within-company (WC) data. As expected, we observe that defect predictors learned from WC data outperform the ones learned from CC data. However, our analyses also yield defect predictors learned from NN-filtered CC data, with performance close to, but still not better than, WC data. Therefore, we perform a final analysis for determining the minimum number of local defect reports in order to learn WC defect predictors. We demonstrate in this paper that the minimum number of data samples required to build effective defect predictors can be quite small and can be collected quickly within a few months. Hence, for companies with no local defect data, we recommend a two-phase approach that allows them to employ the defect prediction process instantaneously. In phase one, companies should use NN-filtered CC data to initiate the defect prediction process and simultaneously start collecting WC (local) data. Once enough WC data is collected (i.e. after a few months), organizations should switch to phase two and use predictors learned from WC data.

Ordinal Optimization and Quantification of Heuristic Designs

This paper focuses on the performance evaluation of complex man-made systems, such as assembly lines, electric power grid, traffic systems, and various paper processing bureaucracies, etc. For such problems, applying the traditional optimization tool of mathematical programming and gradient descent procedures of continuous variables optimization are often inappropriate or infeasible, as the design variables are usually discrete and the accurate evaluation of the system performance via a simulation model can take too much calculation. General search type and heuristic methods are the only two methods to tackle the problems. However, the “goodness” of heuristic methods is generally difficult to quantify while search methods often involve extensive evaluation of systems at many design choices in a large search space using a simulation model resulting in an infeasible computation burden. The purpose of this paper is to address these difficulties simultaneously by extending the recently developed methodology of Ordinal Optimization (OO). Uniform samples are taken out from the whole search space and evaluated with a crude but computationally easy model when applying OO. And, we argue, after ordering via the crude performance estimates, that the lined-up uniform samples can be seen as an approximate ruler. By comparing the heuristic design with such a ruler, we can quantify the heuristic design, just as we measure the length of an object with a ruler. In a previous paper we showed how to quantify a heuristic design for a special case but we did not have the OO ruler idea at that time. In this paper we propose the OO ruler idea and extend the quantifying method to the general case and the multiple independent results case. Experimental results of applying the ruler are also given to illustrate the utility of this approach.

State Observer for DES Under Partial Observation with Time Petri Nets

This paper deals with a state observation approach for Discrete Event Systems with a known behavior. The system behavior is modeled using a Time Petri Net model. The proposed approach exploits temporal constraints to assess the system state and therefore detect and determine faults given partial observability of events. The goal here is to track the system state and to identify the event scenarios which occur on the system. Our approach uses the class graph of the Time Petri Net which models the complete system behavior to develop a state observer which is a base to perform online fault detection and diagnosing.

Exploiting unlabeled data to improve peer-to-peer traffic classification using incremental tri-training method

Unlabeled training examples are readily available in many applications, but labeled examples are fairly expensive to obtain. For instance, in our previous works on classification of peer-to-peer (P2P) Internet traffics, we observed that only about 25% of examples can be labeled as “P2P”or “NonP2P” using a port-based heuristic rule. We also expect that even fewer examples can be labeled in the future as more and more P2P applications use dynamic ports. This fact motivates us to investigate the techniques which enhance the accuracy of P2P traffic classification by exploiting the unlabeled examples. In addition, the Internet data flows dynamically in large volumes (streaming data). In P2P applications, new communities of peers often join and old communities of peers often leave, requiring the classifiers to be capable of updating the model incrementally, and dealing with concept drift. Based on these requirements, this paper proposes an incremental Tri-Training (iTT) algorithm. We tested our approach on a real data stream with 7.2 Mega labeled examples and 20.4 Mega unlabeled examples. The results show that iTT algorithm can enhance accuracy of P2P traffic classification by exploiting unlabeled examples. In addition, it can effectively deal with dynamic nature of streaming data to detect the changes in communities of peers. We extracted attributes only from the IP layer, eliminating the privacy concern associated with the techniques that use deep packet inspection.

A practical approach to testing GUI systems

GUI systems are becoming increasingly popular thanks to their ease of use when compared against traditional systems. However, GUI systems are often challenging to test due to their complexity and special features. Traditional testing methodologies are not designed to deal with the complexity of GUI systems; using these methodologies can result in increased time and expense. In our proposed strategy, a GUI system will be divided into two abstract tiers—the component tier and the system tier. On the component tier, a flow graph will be created for each GUI component. Each flow graph represents a set of relationships between the pre-conditions, event sequences and post-conditions for the corresponding component. On the system tier, the components are integrated to build up a viewpoint of the entire system. Tests on the system tier will interrogate the interactions between the components. This method for GUI testing is simple and practical; we will show the effectiveness of this approach by performing two empirical experiments and describing the results found.

Presenting software engineering results using structured abstracts: a randomised experiment

When conducting a systematic literature review, researchers usually determine the relevance of primary studies on the basis of the title and abstract. However, experience indicates that the abstracts for many software engineering papers are of too poor a quality to be used for this purpose. A solution adopted in other domains is to employ structured abstracts to improve the quality of information provided. This study consists of a formal experiment to investigate whether structured abstracts are more complete and easier to understand than non-structured abstracts for papers that describe software engineering experiments. We constructed structured versions of the abstracts for a random selection of 25 papers describing software engineering experiments. The 64 participants were each presented with one abstract in its original unstructured form and one in a structured form, and for each one were asked to assess its clarity (measured on a scale of 1 to 10) and completeness (measured with a questionnaire that used 18 items). Based on a regression analysis that adjusted for participant, abstract, type of abstract seen first, knowledge of structured abstracts, software engineering role, and preference for conventional or structured abstracts, the use of structured abstracts increased the completeness score by 6.65 (SE 0.37, p < 0.001) and the clarity score by 2.98 (SE 0.23, p < 0.001). 57 participants reported their preferences regarding structured abstracts: 13 (23%) had no preference; 40 (70%) preferred structured abstracts; four preferred conventional abstracts. Many conventional software engineering abstracts omit important information. Our study is consistent with studies from other disciplines and confirms that structured abstracts can improve both information content and readability. Although care must be taken to develop appropriate structures for different types of article, we recommend that Software Engineering journals and conferences adopt structured abstracts.

Efficient Maintenance of Continuous Queries for Trajectories

We address the problem of optimizing the maintenance of continuous queries in Moving Objects Databases, when a set of pending continuous queries need to be reevaluated as a result of bulk updates to the trajectories of moving objects. Such bulk updates may happen when traffic abnormalities, e.g., accidents or road works, affect a subset of trajectories in the corresponding regions, throughout the duration of these abnormalities. The updates to the trajectories may in turn affect the correctness of the answer sets for the pending continuous queries in much larger geographic areas. We present a comprehensive set of techniques, both static and dynamic, for improving the performance of reevaluating the continuous queries in response to the bulk updates. The static techniques correspond to specifying the values for the various semantic dimensions of trigger execution. The dynamic techniques include an in-memory shared reevaluation algorithm, extending query indexing to queries described by trajectories and query reevaluation ordering based on space-filling curves. We have completely implemented our system prototype on top of an existing Object-Relational Database Management System, Oracle 9i, and conducted extensive experimental evaluations using realistic data sets to demonstrate the validity of our approach.

Retrieval of Spatial Join Pattern Instances from Sensor Networks

We study the continuous evaluation of spatial join queries and extensions thereof, defined by interesting combinations of sensor readings (events) that co-occur in a spatial neighborhood. An example of such a pattern is “a high temperature reading in the vicinity of at least four high-pressure readings”. We devise protocols for ‘in-network’ evaluation of this class of queries, aiming at the minimization of power consumption. In addition, we develop cost models that suggest the appropriateness of each protocol, based on various factors, including selectivity of query elements, energy requirements for sensing, and network topology. Finally, we experimentally compare the effectiveness of the proposed solutions on an experimental platform that emulates real sensor networks.

Theory of relative defect proneness

In this study, we investigated the functional form of the size-defect relationship for software modules through replicated studies conducted on ten open-source products. We consistently observed a power-law relationship where defect proneness increases at a slower rate compared to size. Therefore, smaller modules are proportionally more defect prone. We externally validated the application of our results for two commercial systems. Given limited and fixed resources for code inspections, there would be an impressive improvement in the cost-effectiveness, as much as 341% in one of the systems, if a smallest-first strategy were preferred over a largest-first one. The consistent results obtained in this study led us to state a theory of relative defect proneness (RDP): In large-scale software systems, smaller modules will be proportionally more defect-prone compared to larger ones. We suggest that practitioners consider our results and give higher priority to smaller modules in their focused quality assurance efforts.

Software quality analysis by combining multiple projects and learners

When building software quality models, the approach often consists of training data mining learners on a single fit dataset. Typically, this fit dataset contains software metrics collected during a past release of the software project that we want to predict the quality of. In order to improve the predictive accuracy of such quality models, it is common practice to combine the predictive results of multiple learners to take advantage of their respective biases. Although multi-learner classifiers have been proven to be successful in some cases, the improvement is not always significant because the information in the fit dataset sometimes can be insufficient. We present an innovative method to build software quality models using majority voting to combine the predictions of multiple learners induced on multiple training datasets. To our knowledge, no previous study in software quality has attempted to take advantage of multiple software project data repositories which are generally spread across the organization. In a large scale empirical study involving seven real-world datasets and seventeen learners, we show that, on average, combining the predictions of one learner trained on multiple datasets significantly improves the predictive performance compared to one learner induced on a single fit dataset. We also demonstrate empirically that combining multiple learners trained on a single training dataset does not significantly improve the average predictive accuracy compared to the use of a single learner induced on a single fit dataset.

Simulation-based analysis of UML statechart diagrams: methods and case studies

We present a comprehensive unified modeling language (UML) statechart diagram analysis framework. This framework allows one to progressively perform different analysis operations to analyze UML statechart diagrams at different levels of model complexity. The analysis operations supported by the framework are based on analyzing Petri net models converted from UML statechart diagrams using a previously proposed transformation approach. After introducing the general framework, the paper emphasizes two simulation-based analysis operations from the framework: direct MSC inspection, which provides a visual representation of system behavior described by statechart diagrams; and a pattern-based trace query technique, which can be used to define and query system properties. Two case-study examples are presented with different emphasis. The gas station example is a simple multi-object system used to demonstrate both the visual and query-based analysis operations. The early warning system example uses only one object, but features composite states and includes analysis specifically aimed at one composite state feature, history states.

PatchPeer: A scalable video-on-demand streaming system in hybrid wireless mobile peer-to-peer networks

Video-on-demand service in wireless networks is one important step to achieving the goal of providing video services anywhere anytime. Typically, carrier mobile networks are used to deliver videos wirelessly. Since every video stream comes from the base station, regardless of what bandwidth sharing techniques are being utilized, the media stream system is still limited by the network capacity of the base station. The key to overcome the scalability issue is to exploit resources available at mobile clients in a peer-to-peer setting. We observe that it is common to have a carrier mobile network and a mobile peer-to-peer network co-exist in a wireless environment. A feature of such hybrid environment is that the former offers high availability assurance, while the latter presents an opportunistic use of resources available at mobile clients. Our proposed video-on-demand technique, PatchPeer, leverages this network characteristic to allow the video-on-demand system scale beyond the bandwidth capacity of the server. Mobile clients in PatchPeer are no longer passive receivers, but also active senders of video streams to other mobile clients. Our extensive performance study shows that PatchPeer can accept more clients than the current state-of-the-art technique, while maintaining the same Quality-of-Service to clients.

Event Counting of Partially-Observed Discrete-Event Systems with Uniformly and Nonuniformly Bounded Diagnosis Delays

We present an approach dealing with repeated fault events in the framework of model-based monitoring of discrete-event systems (DES). Various notions of diagnosability reported in the literature deal with uniformly bounded finite detection of counting delays over all faulty behaviors (uniform delays for brevity). The situation where the diagnosability notion of interest fails to hold under a given observation configuration leads typically to the deployment of more observational devices (e.g., sensors), which may be costly or infeasible. As an alternative to the additional deployment of observational devices, one might want to relax the uniformity of delays, while delays remain finite. To this end, we introduce a notion of diagnosability characterized with nonuniformly bounded finite counting delays (nonuniform counting delays for brevity), where finite delay bounds can vary on faulty behaviors. To evaluate the introduced notion of diagnosability with nonuniform counting delays, a polynomial-time verification algorithm is developed. Notably, the developed verification technique can readily be modified to construct a computationally superior verification algorithm for diagnosability under uniformly bounded finite counting delays (uniform counting delays for brevity) as compared to an algorithm previously reported in the literature. We also develop a novel on-line event counting algorithm that improves the time and space complexities of the currently available algorithms for the counting of special events.

Quadtree-based eigendecomposition for pose estimation in the presence of occlusion and background clutter

Eigendecomposition-based techniques are popular for a number of computer vision problems, e.g., object and pose estimation, because they are purely appearance based and they require few on-line computations. Unfortunately, they also typically require an unobstructed view of the object whose pose is being detected. The presence of occlusion and background clutter precludes the use of the normalizations that are typically applied and significantly alters the appearance of the object under detection. This work presents an algorithm that is based on applying eigendecomposition to a quadtree representation of the image dataset used to describe the appearance of an object. This allows decisions concerning the pose of an object to be based on only those portions of the image in which the algorithm has determined that the object is not occluded. The accuracy and computational efficiency of the proposed approach is evaluated on 16 different objects with up to 50% of the object being occluded and on images of ships in a dockyard.