A shared-variable concurrency analysis of multi-threaded object-oriented programs

In this paper a proof outline logic is introduced for the partial correctness of multi-threaded object-oriented programs like in Java. The main contribution is a generalization of the Owicki& Gries proof method for shared-variable concurrency to dynamic thread creation. This paper also provides a formal justification of this generalization in terms of soundness and completeness proofs.     

Multiagent reasoning with probability,time, and beliefs

Any agent interacting with the real world must be able to reason about uncertainty in the world, about the actions that may occur in the world (either due to the agent or those initiated by other agents), about the (probabilistic) beliefs of other agents, and how these (probabilistic) beliefs are changing over time. In this article, we develop a family of logics that a reasoning agent may use to perform successively more sophisticated types of reasoning in such environments. We also characterize different types of agents. Furthermore, we provide a logic that enables a systems designer (who may have populated an environment with a collection of such autonomous agents) to reason about the system of agents as a whole. © 1995 John Wiley & Sons, Inc.     

Software concurrency in real time control systems: A software nucleus

This paper gives the rationale for the design of a nucleus to support real time control applications. In particular, mechanisms for communication between concurrent tasks are reviewed and analysed in the context of this application area. Finally, although no implementation is discussed in detail, techniques which have proved useful in implementing this nucleus on three different machines are described.     

Practical abduction: characterization,decomposition and concurrency

Abstract

Abductive inferences seem to be ubiquitous in cognition, and cognitive agents often solve complex abduction tasks very rapidly. However, abduction characterized as ‘inference to the best explanation’ is in general computationally intractable. This paper describes three related ideas for understanding how intelligent agents might efficiently perform abduction tasks. First, we recharacterize the abduction task as inference to a confident explanation, where a confident explanation is internally consistent, parsimonious, distinctly more plausible than alternative explanations, and explains as much of the data as possible with high confidence. Second, we describe a decomposition of the task of synthesizing a confident explanation into several subtasks so that the synthesis starts from islands of relative certainty and then grows opportunistically. This decomposition helps in controlling the computational cost of accommodating interactions among explanatory hypotheses, especially incompatibility interactions. Third, we present a concurrent mechanism for synthesizing confident explanations. The mechanism exploits data and processing dependencies afforded by the decomposition of the synthesis task. The emphasis of this approach to abduction is on characterizing the constraints of the abduction task and exploiting these constraints for making abductive inferences. In describing this approach, we also clarify the precise class of abduction problems addressed by the RED-2 system, and report on some new experiments. The main result is a computational model that not only enables efficient abductive inferences but also accommodates explanatory interactions, uncertainty, and data collection.     

基于冲突概率的组合服务事务混合并发控制算法

由于Web服务的松散耦合性及独立性的特点，组合服务中的两个服务可以并行运行。针对这一特点，结合乐观并发与悲观并发控制的优点，提出一种基于冲突发生概率的混合并发控制机制，以提高Web服务的并发度。由于充分考虑了不同组合服务实例的并发控制，以及同一种组合服务实例的并发控制，使得该机制能够确保在复杂的应用环境中，多个组合服务实例并发执行的正确性和一致性。     

Extending Prolog with modularity,concurrency and meta-rules

This paper presents the main features of an extension to Prolog toward modularity and concurrency—calledCommunicating Prolog Units (CPU)—whose main aim is to allow logic programming to be used as an effective tool for system programming and prototyping. While Prolog supports only a single set of clauses and sequential computations, CPU allows programmers to define different theories (P-unis) and parallel processes interacting via P-units, according to a model very similar to Linda’s generative communication. The possibility of expressingmeta-rules to specify where and how object-level (sub)golas have to be proved, not only enhances modularity, but also increases the expressive power and flexibility of CPU systems.     

Type theory and concurrency

This paper describes the use of an automated reasoning tool, the Nuprl system, to formalize Milner's Calculus of Communicating Systems (CCS). The goals of this work are two-fold: the first is to investigate the feasibility of using systems like Nuprl to handle the formal detail arising from reasoning about concurrency, while the second is to develop a framework in which various formalisms for reasoning about concurrency may be presented in an automated fashion. To these ends, an implementation in Nuprl of a formal theory of concurrency is described, an implementation of CCS in this mechanized semantic theory presented, and two means of analyzing CCS terms are investigated.     

Data redistribution and concurrency

The role of data distribution in concurrent computations is twofold: achieving load balanced computations and minimizing the number of synchronization points and/or message exchanges. It is clear that the optimal data distribution is dependent on the particular algorithm. However, when faced with typical application programs several algorithms involving varying types of computation may have to be performed on the same data at different stages of the computation. In between these stages a redistribution of the data may be necessary. Memory is often a constraining factor in highly concurrent machines and there is usually great advantage if the data redistribution can be done in place. In this paper we propose a general in place concurrent data redistribution algorithm and we identify the data distributions that can be mapped into one another by the proposed technique.     

JAC: declarative Java concurrency

The Java programming language has a low‐level concurrency model which is hard to use and does not blend well with inheritance. JAC is an extension of Java that introduces a higher level of concurrency, hiding threads and separating thread synchronization from application logic in a declarative fashion. The emphasis is on limiting the differences between sequential and concurrent code, thus furthering code reuse, and on avoiding inheritance anomalies. This is achieved by taking a middle road between concurrent code on the one hand and complete separation of sequential application logic from concurrency mechanisms on the other. An extensive comparison with related approaches is given for motivating our design decisions. Copyright © 2005 John Wiley & Sons, Ltd.     

ARS: an integrated package for shared-variable and message-passing computations in object-based systems

This paper describes the ARS library package, which supports two implementation versions of an object-based system: a shared-variable and a message-passing version. The two versions have the same object structure and synchronisation but differ in their process structure and inter-process communication models. Thus, the mechanisms related to the uniform features are common for the two versions, but the process multiplexing mechanisms differ. As a consequence, the performance characteristics of the two versions of a system related to uniform features are similar, while those related to the process multiplexing differ significantly. We present an overview of the computational model supported by the ARS package, the internal structure of the package and compare overheads in two versions of an object-based system supported by the package. © 1998 John Wiley & Sons, Ltd.     

RTC: Language support for real-time concurrency

This paper presents a model and language constructs for expressing timing and concurrency requirements in distributed real-time programs. Our approach combines an abstract data type paradigm for the specification of shared resources and a distributed transaction-based paradigm for the specification of application processes. Resources provide abstract views of shared system entities, such as devices and data structures. Each resource has a state and defines a set ofactions that can be invoked by processes to examine or change its state. A resource also specifies scheduling constraints on the execution of its actions to ensure its consistency. Processes access resources by invoking actions and by expressing precedence, execution and timing constraints on action invocations. The implementation of our language constructs and the use of this system to control the simulation of a distributed robotics application is also described.This work is supported in part by the following grants: ARO DAAG-29-84-k-0061, ONR N000014-89-J-1131, and NSF CCR90-14621.     

EuList threads: A concurrency toolbox

Many current high level languages have been designed with support for concurrency in mind, providing constructs for the programmer to build explicit parallelism into a program. TheEuLisp threads mechanism, in conjunction with locks, and a generic event waiting operation provides a set of primitive tools with which such concurrency abstractions can be constructed. The object system (Telos) provides a powerful approach to building and controlling these abstractions. We provide a synopsis of this concurrency toolbox, and demonstrate the construction of a number of established abstractions using the facilities ofEuLisp: pcall, futures, stack groups, channels, CSP and Linda.     

Hypersequents,logical consequence and intermediate logics for concurrency

The existence of simple semantics and appropriate cut-free Gentzen-type formulations are fundamental intrinsic criteria for the usefulness of logics. In this paper we show that by using hypersequents (which are multisets of ordinary sequents) we can provide such Gentzen-type systems to many logics. In particular, by using a hypersequential generalization of intuitionistic sequents we can construct cut-free systems for some intermediate logics (including Dummett's LC) which have simple algebraic semantics that suffice, e.g., for decidability. We discuss the possible interpretations of these logics in terms of parallel computation and the role that the usual connectives play in them (which is sometimes different than in the sequential case).     

Linking operational semantics and algebraic semantics for a probabilistic timed shared-variable language

Complex software systems typically involve features like time, concurrency and probability, with probabilistic computations playing an increasing role. However, it is currently challenging to formalize languages incorporating all those features. Recently, the language PTSC has been proposed to integrate probability and time with shared-variable concurrency (Zhu et al. (2006, 2009) [51] and [53]), where the operational semantics has been explored and a set of algebraic laws has been investigated via bisimulation. This paper investigates the link between the operational and algebraic semantics of PTSC, highlighting both its theoretical and practical aspects.The link is obtained by deriving the operational semantics from the algebraic semantics, an approach that may be understood as establishing soundness of the operational semantics with respect to the algebraic semantics. Algebraic laws are provided that suffice to convert any PTSC program into a form consisting of a guarded choice or an internal choice between programs, which are initially deterministic. That form corresponds to a simple execution of the program, so it is used as a basis for an operational semantics. In that way, the operational semantics is derived from the algebraic semantics, with transition rules resulting from the derivation strategy. In fact the derived transition rules and the derivation strategy are shown to be equivalent, which may be understood as establishing completeness of the operational semantics with respect to the algebraic semantics.That theoretical approach to the link is complemented by a practical one, which animates the link using Prolog. The link between the two semantics proceeds via head normal form. Firstly, the generation of head normal form is explored, in particular animating the expansion laws for probabilistic interleaving. Then the derivation of the operational semantics is animated using a strategy that exploits head normal form. The operational semantics is also animated. These animations, which again supports to claim soundness and completeness of the operational semantics with respect to the algebraic, are interesting because they provide a practical demonstration of the theoretical results.     

Models for concurrency: towards a classification

Models for concurrency can be classified with respect to three relevant parameters: behaviour/ system, interleaving/noninterleaving, linear/branching time. When modelling a process, a choice concerning such parameters corresponds to choosing the level of abstraction of the resulting semantics.

In this paper, we move a step towards a classification of models for concurrency based on the parameters above. Formally, we choose a representative of any of the eight classes of models obtained by varying the three parameters, and we study the formal relationships between them using the language of category theory.     

Modular synchronization in distributed, multiversion databases:version control and concurrency control

A version control mechanism is proposed that enhances the modularity and extensibility of multiversion concurrency control algorithms. The multiversion algorithms are decoupled into two components: version control and concurrency control. This permits modular development of multiversion protocols and simplifies the task of proving the correctness of these protocols. A set of procedures for version control is described that defines the interface with the version control component. It is shown that the same interface can be used by the database actions of both two-phase locking and time-stamp concurrency control protocols to access multiversion data. An interesting feature of the framework is that the execution of read-only transactions becomes completely independent of the underlying concurrency control implementation. Unlike other multiversion algorithms, read-only transactions in this scheme do not modify any version-related information, and therefore do not interfere with the execution of read-write transactions. The extension of the multiversion algorithms to a distributed environment becomes very simple     

Grid file concurrency

The grid file is a partial match search structure which is equally efficient for range queries involving any subset of the attributes of the key of a file. This paper proposes a method of safe correct concurrent access to the grid file, using a minimum number of locks. In particular, searchers are never locked out from any part of the search structure.     

The hB^\Pi-tree: a multi-attribute index supporting concurrency, recovery and node consolidation

We propose a new multi-attribute index. Our approach combines the hB-tree, a multi-attribute index, and the -tree, an abstract index which offers efficient concurrency and recovery methods. We call the resulting method the hB-tree. We describe several versions of the hB-tree, each using a different node-splitting and index-term-posting algorithm. We also describe a new node deletion algorithm. We have implemented all the versions of the hB-tree. Our performance results show that even the version that offers no performance guarantees, actually performs very well in terms of storage utilization, index size (fan-out), exact-match and range searching, under various data types and distributions. We have also shown that our index is fairly insensitive to increases in dimension. Thus, it is suitable for indexing high-dimensional applications. This property and the fact that all our versions of the hB-tree can use the -tree concurrency and recovery algorithms make the hB-tree a promising candidate for inclusion in a general-purpose DBMS. Edited by R. Sacks-Davis. Received 27 June 1994 / Accepted 26 September 1995     

Generalised rely-guarantee concurrency: an algebraic foundation

The rely-guarantee technique allows one to reason compositionally about concurrent programs. To handle interference the technique makes use of rely and guarantee conditions, both of which are binary relations on states. A rely condition is an assumption that the environment performs only atomic steps satisfying the rely relation and a guarantee is a commitment that every atomic step the program makes satisfies the guarantee relation. In order to investigate rely-guarantee reasoning more generally, in this paper we allow interference to be represented by a process rather than a relation and hence derive more general rely-guarantee laws. The paper makes use of a weak conjunction operator between processes, which generalises a guarantee relation to a guarantee process, and introduces a rely quotient operator, which generalises a rely relation to a process. The paper focuses on the algebraic properties of the general rely-guarantee theory. The Jones-style rely-guarantee theory can be interpreted as a model of the general algebraic theory and hence the general laws presented here hold for that theory.