10370670
Top-Down Design of Bulk-Synchronous Parallel Programs
This paper studies top-down program development techniques for Bulk-Synchronous Parallelism. In that context a specification formalism LOGS, for 'the Logic of Global Synchrony', has been proposed for the specification and high-level development of BSP designs. This paper extends the use of LOGS to provide support for the protection of local variables in BSP programs, thus completing the link between specifications and programs.
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.
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.
8852685
Generic Composition
Abstract. This paper presents a technique called generic composition to provide a uniform basis for modal operators, sequential composition, different kinds of parallel compositions and various healthiness conditions appearing in a variety of semantic theories. The weak inverse of generic composition is defined. A completeness theorem shows that any predicate can be written in terms of generic composition and its weak inverse. A number of algebraic laws that support reasoning are derived.
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.
33072384
Side Chain Conformational Preferences in Protein Structures
887532
A Suite of Schemes for User-Level Network Diagnosis without Infrastructure
It is highly desirable and important for end users, with no special privileges, identify and pinpoint faults inside the network that degrade the performance of their applications. However, existing tools are inaccurate to infer the link-level loss rates and have large diagnosis granularity (in terms of the number of hops). To address these problems, we propose a suite of user-level diagnosis approaches in two categories: (1) only need to be deployed at the source and (2) deployed at both source and destination. For the former, we propose two fragmentation aided diagnosis approaches (FAD), Algebraic FAD and Opportunistic FAD, which uses IP fragmentation to enable accurate link-level loss rate inference. For the latter category, we propose Striped Probe Analysis (SPA) which significantly improves the diagnosis granularity over those of the source-only approaches. Internet experiments are applied to evaluate each individual schemes (including an improved version of the state-of-the-art tool, Tulip [1]) and various hybrid approaches. The results indicate that our approaches dramatically outperform existing work (especially for diagnosis granularity) and provide not only the best performance but also smooth tradeoff among deployment requirement, diagnosis accuracy and granularity.
9049589
A service-oriented modeling and simulation framework for rapid development of distributed applications
Abstract The paper presents a service-oriented distributed modeling and simulation framework that supports the development and evaluation of large scale distributed systems such as network-centric and system-of-systems applications. The distinct features of the framework include a modeling and specification language, dynamic model checking for completeness and consistency, automated code generation from the specification, simulation of different architectures with a template-based platform builder, service-oriented multi-agent simulation for easy re-configuration and re-composition, formal policy specification and enforcement for dynamic verification, and dynamic analyses for evaluation and monitoring. The framework and most of the tools reported in this paper have been implemented and applied in several industrial projects. This paper presents the design principles, user interfaces, its runtime infrastructure, and the experiment results on its performance.
2536834
Extensible detection and indexing of highlight events in broadcasted sports video
Content-based indexing is fundamental to support and sustain the ongoing growth of broadcasted sports video. The main challenge is to design extensible frameworks to detect and index highlight events. This paper presents: 1) A statistical-driven event detection approach that utilizes a minimum amount of manual knowledge and is based on a universal scope-of-detection and audio-visual features; 2) A semi-schema-based indexing that combines the benefits of schema-based modeling to ensure that the video indexes are valid at all time without manual checking, and schema-less modeling to allow several passes of instantiation in which additional elements can be declared. To demonstrate the performance of the events detection, a large dataset of sport videos with a total of around 15 hours including soccer, basketball and Australian football is used.
28100130
Global Software Enterprise: A New Software Constructing Architecture
Based on current service-oriented architecture (SOA), this paper introduces a consumer-oriented SOA software constructing architecture: the global software enterprise (GSE) architecture. In this architecture, the software construction starts from the consumers' publishing their requirements in the form of application or service specification which they exactly want. The consumer also publishes the expectation for the services the application needs in the form of collaboration specification and test scripts. The service providers then produce services that meet the needs of the applications. This new approach reduces the workload for the consumer and the communication between the consumer and provider. It also extends the design and code sharing, and thus further improves the software productivity