11936833
The weakest specifunction
The weakest specifunction has been introduced to generalise the notions of weakest prespecification and weakest parallel environment. It calculates the weakest specification function whose value refines the target specification when applied to a given component; thus it forms the basis for compositional refinement, an essential ingredient in program derivation. But unlike those previous calculi it is able to deal with several unknown components simultaneously and hence has wider applicability. In this paper we extend the general theory of the weakest specifunction, identifying those spaces in which it behaves miraculously. The par-seq specifunction places an established component in parallel with a required component and the result in sequence with another required component to meet a given specification. We extend the study of the par-seq specifunction in the context of log s, an intermediate-level language for reactive computing in an abstraction of the PRAM and BSP models of computation, and provide a single complete law for its use in program derivation. The resulting calculus is applied to the derivation of a distributed algorithm for dynamic load balancing.
15862425
A Fixpoint Theory for Non-monotonic Parallelism
This paper studies parallel recursions. The trace specification language used in this paper incorporates sequentiality, nondeterminism, reactiveness (including infinite traces), conjunctive parallelism and general recursion. The language is the minimum of its kind and thus provides a context in which we can study parallel recursions in general. In order to use Tarski's theorem to determine the fixpoints of recursions, we need to identify a well-founded partial order. A theorem of this paper shows that no appropriate order exists. Tarski's theorem alone is not enough to determine the fixpoints of parallel recursions. Instead of using Tarski's theorem directly, we reason about the fixpoints of terminating and nonterminating behaviours separately. Such reasoning is supported by the laws of a new composition called partition. We propose a fixpoint technique called the partitioned fixpoint, which is the least fixpoint of the nonterminating behaviours after the terminating behaviours reach their greatest fixpoint. The surprising result is that although a recursion may not be monotonic with regard to the lexical order, it must have the partitioned fixpoint, which equals the least lexical-order fixpoint. Since the partitioned fixpoint is well defined in any complete lattice, the results are applicable to various semantic models. Major existing fixpoint techniques simply become special cases of the partitioned fixpoint. For example, an Egli-Milner-monotonic recursion has its least Egli-Milner fixpoint, which can be shown to be the same as the partitioned fixpoint. The new technique is more general than the least Egli-Milner fixpoint in that the partitioned fixpoint can be determined even when a recursion is not Egli-Milner monotonic. Examples of non-monotonic recursions with fair-interleaving parallelism are studied. Their partitioned fixpoints are shown to be consistent with our intuitions.
15321284
From Durational Specifications to TLA Designs of Timed Automata
Different temporal logics tend to emphasise different aspects of a hybrid system. In this paper, we study the predicative interpretation of Duration Calculus (DC) and Temporal Logic of Actions (TLA) and the link between them. A notation called generic composition is used to simplify the manipulation of predicates. The modalities of possibility and necessity become generic composition and its inverse of converse respectively. The transformation between different temporal logics is also characterised as such modalities. The formalism provides a framework in which human experience about hybrid system development can be formalised as refinement laws. A high-level durational specification can be decomposed to two durational specifications driven by an automaton. In such a stepwise design process, durational features are reduced while automaton features increase gradually. The application of the technique is demonstrated in the case study of the gas burner problem.
17662809
Hierarchical Organisation of Predicate-Semantic Models
This paper introduces techniques to organise predicate- semantic models in a hierarchical structure so that a new model can inherit the laws of the existing ones. Generic composition is used to simplify the manipulation of predicates. Necessary restrictions are imposed on the definition of each model so that the inheritance relation can be established by checking a few conditions on the healthiness conditions and the commands. Much of the checking can be supported by laws of generic composition. The techniques also help simplify the proof of well-definedness of program combinators (i.e. their closure in the semantic space) so that we no longer need to prove it (in predicate calculus) for every new model.
13475813
Compositional Reasoning for Pointer Structures
This paper studies the compositional definition and behaviour of properties that arise in pointer structures. A pointer structure is represented as a (pointer) graph. A pointer property is a set of pointer structures. A parameterised binary combinator is defined that enables important properties (like acyclicity, canonicity and reachability) to be defined in a compositional manner. The technique of parameterising a combinator derives from the definition of parallel-by-merge in ‘Unifying Theories of Programming'. It is applied here to the study of disjointness combinators that extend the separating conjunction of Separation Logic. A case study is provided to demonstrate how these ideas are used, in the form of rules of Hoare logic, to verify the correctness of an Object-Oriented program.
1010133
A fixpoint theory for non-monotonic parallelism
This paper studies parallel recursion. The trace specification language used in this paper incorporates sequentiality, nondeterminism, reactiveness (including infinite traces), three forms of parallelism (including conjunctive, fair-interleaving and synchronous parallelism) and general recursion. In order to use Tarski’s theorem to determine the fixpoints of recursions, we need to identify a well-founded partial order. Several orders are considered, including a new order called the lexical order, which tends to simulate the execution of a recursion in a similar manner as the Egli-Milner order. A theorem of this paper shows that no appropriate order exists for the language. Tarski’s theorem alone is not enough to determine the fixpoints of parallel recursions. Instead of using Tarski’s theorem directly, we reason about the fixpoints of terminating and nonterminating behaviours separately. Such reasoning is supported by the laws of a new composition called partition. We propose a fixpoint technique called the partitioned fixpoint, which is the least fixpoint of the nonterminating behaviours after the terminating behaviours reach their greatest fixpoint. The surprising result is that although a recursion may not be lexical-order monotonic, it must have the partitioned fixpoint, which is equal to the least lexicalorder fixpoint. Since the partitioned fixpoint is well defined in any complete lattice, the results are applicable to various semantic models. Existing fixpoint techniques simply become special cases of the partitioned fixpoint. For example, an Egli-Milnermonotonic recursion has its least Egli-Milner fixpoint, which can be shown to be the same as the partitioned fixpoint. The new technique is more general than the least Egli-Milner fixpoint in that the partitioned fixpoint can be determined even when a recursion is not Egli-Milner monotonic. Examples of non-monotonic recursions are studied. Their partitioned fixpoints are shown to be consistent with our intuition.
166109
End-to-End Inference of Router Packet Forwarding Priority
Packet forwarding prioritization (PFP) in routers is one of the mechanisms commonly available to network administrators. PFP can have a significant impact on the performance of applications, the accuracy of measurement tools' results and the effectiveness of network troubleshooting procedures. Despite their potential impact, no information on PFP settings is readily available to end users. In this paper, we present an end-to-end approach for packet forwarding priority inference and its associated tool, POPI. This is the first attempt to infer router packet-forwarding priority through end-to-end measurement. Our POPI tool enables users to discover such network policies through the monitoring and rank classification of loss rates for different packet types. We validated our approach via statistical analysis, simulation, and wide-area experimentation in PlanetLab. As part of our wide-area experiments, we employed POPI to analyze 156 random paths across 162 PlanetLab nodes. We discovered 15 paths flagged with multiple priorities, 13 of which were further validated through hop-by-hop loss rates measurements. In addition, we surveyed all related network operators and received responses for about half of them confirming our inferences.
41090805
Distributed policy specification and enforcement in service-oriented business systems
Service-oriented computing (SOC) and Web services (WS) provide a flexible computing platform for electronic business and commerce. Introducing policy-based computing to service-oriented business systems adds another dimension of flexibility and security. While service composition and re-composition in service-oriented business systems allow major system reconstruction, policy-based computing can better deal with the small and routine changes of business processing. This paper reports our latest research on integrating policy-based computing into service-oriented business system and discusses its feasibility, benefits and cost. Under this research, we designed a policy specification and enforcement language PSEL for specifying system constraints and business rules. We implemented a runtime environment in which a service-oriented business system can be modeled, analyzed, deployed, and executed with policy enforcement. Automated tools have been developed to facilitate the entire development process. The cost of policy-based computing is experimentally evaluated
20308502
Object signatures for supporting efficient navigation in object-oriented databases
Most methods that have been proposed to improve query processing in object-oriented databases are designed for the aggregation hierarchy. Although the structure of the generalization hierarchy is similar to the aggregation hierarchy, techniques developed for the aggregation hierarchy cannot fully use the characteristics of the generalization hierarchy to improve performance. We devise a new object signature for the generalization hierarchy. The object signature consists of two parts: a reference signature and a structure signature. The former can be used to eliminate objects that do not match the nested predicates specified in the query, and the latter can be used to eliminate objects that do not belong to the target classes. We propose some processing methods using the object signatures for queries that involve generalization hierarchies. In addition, we define cost models of the object signature and then compare the performance of the traditional query processing method with the object signature method. The results show that using the object signatures can effectively reduce the number of disk accesses in a query.
39700388
Surface Spatial Index Structure of High-Dimensional Space
This paper proposes a spatial index structure based on a new space-partitioning method. Previous research proposed various high dimensional index structures. However, when dimensionality becomes high, the effectiveness of the spatial index structure disappears. This problem is called the “curse of dimensionality”. This paper focuses on the fact that the volume of high dimensional space is mostly occupied by its surface and then proposes a new surface index structure. The utility of this new surface spatial index structure is illustrated through a series of experiments.
6045052
Basis pursuit for tracking
This paper introduces a novel adaptive texture feature selection algorithm for tracking. Specifically, we provide a statistical wavelet basis paradigm to maximally separate statistical characteristics of the object-in-interest and its background. The algorithm is based upon nonlinearly selecting basis elements out of dual dictionaries in an iterative fashion to continually improve a cost function that is suitable for tracking. We demonstrate that such a selection is effective with several difficult sequences that are affected by lighting changes, occlusion and background motion.