An abstract business process contains a description the protocol that a business process engages in without revealing the internal computation of the process. This description provides the information necessary to compose the process with other Web services. BPEL supports this by providing distinct dialects for specifying abstract and executable processes. Unfortunately, BPEL does not prevent complex computations from being included in an abstract process. This complicates the protocol description, unnecessarily reveals implementation details, and makes it difficult to analyze correctness. We propose some restrictions on the data manipulation constructs that can be used in an abstract BPEL process. The restrictions permit a full description of a protocol while hiding computation. A restricted abstract process can easily be converted into an abstract BPEL process or expanded into an executable BPEL process. Based on these restrictions we propose a formal model for a business process and use it as the basis of an algorithm for demonstrating the process. We then sketch an algorithm for synthesizing a protocol based on a formal specification of its outcome and the tasks available for its construction.

We introduce a logic model to formally specify the semantics of workflows and their composite tasks described as BPEL4WS abstract processes. Based on the model, we present a set of inference rules to deduce the strongest postcondition and weakest precondition of a workflow and demonstrate that automatic workflow verification is possible due to the restrictions on data manipulation in an abstract process. We then sketch an algorithm that automatically synthesizes a workflow given its specification and a task library.

Many transaction processing applications execute at isolation levels lower than SERIALIZABLE in order to increase throughput and reduce response time. However, the resulting schedules might not be serializable and, hence, not necessarily correct. The semantics of a particular application determines whether that application will run correctly at a lower level and, in practice, it appears that many applications do. The decision to choose an isolation level at which to run an application and the analysis of the correctness of the resulting execution is usually done informally. We develop a formal technique to analyze and reason about the correctness of the execution of an application at isolation levels other than SERIALIZABLE. We use a new notion of correctness, semantic correctness, a criterion weaker than serializability, to investigate correctness. In particular, for each isolation level, we prove a condition under which the execution of transactions at that level will be semantically correct. In addition to the ANSI/ISO isolation levels of READ UNCOMMITTED, READ COMMITTED, and REPEATABLE READ, we also prove a condition for correct execution at the READ-COMMITTED with first-committer-wins and at SNAPSHOT isolation. We assume that different transactions in the same application can be executing at different levels, but that each transaction is executing at least at READ UNCOMMITTED.

Many transaction processing applications execute at isolation levels lower than serializable in order to increase throughput and reduce response time. The problem is that non-serializable schedules are not guaranteed to be correct for all applications. The semantics of a particular application determines whether that application will run correctly at a lower isolation level, and in practice it appears that many applications do. Unfortunately, we know of an analysis technique that has been developed to test an application for its correctness at a particular level. Apparently decisions of this nature are made on an informal basis. In this paper we describe such a technique in a formal way. We use a new definition of correctness, semantic correctness, which is weaker than serializability, to investigate the correctness of such executions. For each isolation level, we prove a condition under which transactions that execute at that level will be semantically correct. In addition to the ANSI/ISO isolation levels of read uncommitted, read committed, and repeatable read, we also prove a condition for correct execution at the read committed with first-committer-wins (a variation of read committed) and at the snapshot isolation level. We assume that different transactions can be executing at different isolation levels, but that each transaction is executing at least at the read uncommitted level.

Serializability has been widely accepted as the correctness criterion for databases subject to concurrent access. Serializable execution is generally implemented using a two phase locking algorithm that locks items in the database to delay transactions that care in danger of performing in a nonserializable fashion. Such delays are unacceptable in high performance database systems and in systems supporting long running transactions. A number of models have been proposed in which transactions are decomposed into smaller, atomic, interleavable steps. A shortcoming of much of this work is that little guidance is provided as to how transactions should be decomposed and what interleavings preserve correct execution. We previously proposed a new correctness criterion, weaker than serializability, that guarantees that each transaction satisfies its specification (A. Bernstein and P. Lewis, 1996). Based on that correctness criterion, we have designed and implemented a new concurrency control. Experiments using the new concurrency control demonstrate significant improvement in performance when lock contention is high.

Databases are replicated to improve performance and availability. The notion of correctness that has commonly been adopted for concurrent access by transactions to shared, possibly replicated, data is serializability. However, serializability may be impractical in high-performance applications since it imposes too stringent a restriction on concurrency. When serializability is relaxed, the integrity constraints describing the data may be violated. By allowing bounded violations of the integrity constraints, however, we are able to increase the concurrency of transactions that execute in a replicated environment. In this article, we introduce the notion of an N-ignorant transaction, which is a transaction that may be ignorant of the results of at most N prior transactions, which is a transaction that may be ignorant of the results of at most N prior transactions. A system in which all transactions are N-ignorant can have an N + 1-fold increase in concurrency over serializable systems, at the expense of bounded violations of its integrity constraints. We present algorithms for implementing replicated databases in N-ignorant systems. We then provide constructive methods for calculating the reachable states in such systems, given the value of N , so that one may assess the maximum liability that is incurred in allowing constraint violation. Finally, we generalize the notion of N-ignorance to a matrix of ignorance for the purpose of higher concurrency.

Article Bounded ignorance in replicated systems Share on Authors: Narayanan Krishnakumar Dept. of Computer Science, SUNY at Stony Brook, Stony Brook, NY Dept. of Computer Science, SUNY at Stony Brook, Stony Brook, NYView Profile , Arthur J. Bernstein Dept. of Computer Science, SUNY at Stony Brook, Stony Brook, NY Dept. of Computer Science, SUNY at Stony Brook, Stony Brook, NYView Profile Authors Info & Claims PODS '91: Proceedings of the tenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systemsApril 1991 Pages 63–74https://doi.org/10.1145/113413.113419Online:01 April 1991Publication History 36citation278DownloadsMetricsTotal Citations36Total Downloads278Last 12 Months4Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

A nonblocking quorum protocol for replica control which guarantees one-copy serializability is developed. The effects of a nonblocking protocol are analyzed, and it is shown that the gains can be substantial under certain conditions. It is demonstrated that in order for the protocol to be useful, it must be integrated with a propagation mechanism. It is also shown that the access latency can be reduced significantly in a replicated environment. An interesting aspect of the quorum protocol is that it essentially uses a read quorom/write-quorom approach for concurrency control but uses a read-one/write-all approach for replica control. It is shown that the nonblocking quorom protocol provides the same level of availability and fault tolerance as the quorum protocol proposed by D.K. Gifford (1979).>

A formalism for comparing the average execution time of distributed protocols is provided. The comparisons are made independently of the properties of the network on which the protocols are executed. The formalism takes into account computation time, the time to transfer information, the time spent by a site waiting to synchronize with other sites, and the overlap among them. A framework in which the information transfer and synchronization requirements of a protocol are separately and explicitly specified is developed. A knowledge formalism is used to specify the protocol's specification requirements. Transformations on protocols which may change the synchronization structure, the information transferred, or the amount of local computation are defined. It is shown that, if a sequence of such transformations can be applied to a protocol to obtain another protocol, the final protocol runs at least as fast as the initial. Two notions of comparison, containment and reducibility, are given, and their properties are explored. Several protocols, including those for atomic commitment and snapshot recording, are analyzed to illustrate the technique.>

An interprocess communication structure for a distributed language is described which provides message level communication, multicast, and a generalized naming facility. The design is oriented to the needs of low level algorithms which, for example, might be used in a distributed operating system to support resource allocation or enhance reliability. The proposal is illustrated by programming several distributed algorithms from the literature. An implementation is described that takes advantage of physical multicast technology, and reduces to more conventional schemes for common communication paradigms.

An algorithm for storing information redundantly on the nodes of a broadcast network is proposed. A voting technique is used to increase reliability. Since multiple votes are cast only when copies of a data item disagree, the algorithm has the property that communication overhead is minimal. In addition, nodes storing erroneous copies are automatically resynchronized. A Markov analysis is performed which relates parameters of the algorithm to the mean time to failure.

Detecting a nonexistent deadlock in distributed systems has been referred to as false deadlock detection. This correspondence shows that false deadlock wi1l never occur in a system of two-phase locking transactions. We also describe an algorithm to avoid false deadlock detection when transactions are not two-phase locking.

We propose efficient algorithms to maintain a replicated dictionary using a log in an unreliable network. A non-serializable approach is used to achieve high concurrency. The solutions are resilient to both node and communication failures. Optimizations are developed for networks which are not completely connected.

Staged circuit switching (SCS) is a message-switching technique that combines a new protocol with new communication hardware. Protocol and hardware are designed specifically for networks that are intended to function as integrated, general-purpose MIMD machines, i.e. for "network computers".

Design and implementation of an inter-address-space communication mechanism for the SBN network computer are described. SBN's basic communication primitives appear in context of a new distributed systems programming language strongly supported by the network communication kernel. A model in which all communication takes place via a distributed global buffer results in simplicity, generality and power in the communication primitives. Implementation issues raised by the requirements of the global buffer model are discussed in context of the SBN impementation effort.

Wirth [Wi77] categorized programs into three classes. The most difficult type of program to understand and write is a real-time program. Much work has been done in the formal verification of sequential programs, but much remains to be done for concurrent and real-time programs. The critical nature of typical real-time applications makes the validity problem for real-time programs particularly important. Owicki and Lamport [OL80] present a relatively new method for verifying concurrent programs using temporal logic. This paper presents an extension of their work to the area of real-time programs. A model and proof system are presented and their use demonstrated using examples from the literature.

Abstract This paper describes a proposal for a modification to the language Modula. The modification was motivated by a desire to bring to the language the ability to build hierarchical systems and to support program verification efforts. In the modified language, called SB‐Mod, modules are grouped into levels and calls are permitted from the modules of one level to those of a higher level. Verification is supported through a set of clearly described synchronization constructs and by restricting the flow of information between levels. A result of this is that levels do not interfere with each other and can be treated separately for purposes of verification. In considering modifications, an attempt was made to provide the user with a variety of control mechanisms, while at the same time avoiding situations in which excessive run‐time overhead would be incurred.

In a recent paper C.A.R. Hoare outlined a language for concurrent programming. Guarded commands and nondeterminism are two features of the language. This paper points out two problems that arise in connection with these features and addresses one of them.

Protection in capability-based operating systems is comsidered. The concept of a conditional capability, which is a generalization of a conventional capability, is proposed. The conditional capability can only be exercised when certain conditions relating to the context of its use are satisfied. It is shown that such capabilities form a basis upon which features such as domains of protection, revocation, and type extension can be built. The implementation of these features can be isolated into sepuate modules thus leaving the basic protection module uncluttered and simplifying the overall structure of the system.

Synchronous and asynchronous operation of software systems are defined. It is argued that certifying the correct operation of a system in the synchronous mode is significantly simpler than in the asynchronous mode. A series of compile-time and run-time restrictions for systems constructed in Concuirent Pascal are presented which assure equivalent operation in the synchronous and asynchronous modes.

In Concurrent Pascal, the syntactic and semantic definition of the language prevents the inadvertent definition of a program that might violate the integrity of a shared data object. However, the language also does not allow the dynamic allocation of reusable resources among processes, and this restriction seems unnecessarily stingent. This paper proposes the addition to Concurrent Pascal of a new type of program component, to be called a resource manager. By this means, dynamic resource allocation can be accomplished both safely and efficiently. The notion that a process holds access rights to a resource is generalized to the notion that it holds capability rights, but the capability to atually make use of a resource is granted dynamically. The anonymity of dynamically allocatable resources is also guaranteed.

An algorithm is described for synthesizing a specified response function within the framework of a feedback scheduler. The scheduler uses a single queue and feeds back jobs to positions which are dependent on their attained service.

The notion of level structured operating systems is receiving growing acceptance in the computing community. These systems are implemented and debugged incrementally, one level at a time. Each level provides a pseudo-machine interface upon which the next level can be implemented. Such systems offer significant advantages from the piont of view of debugging, reliability, understandability, and modifiability over conventionally organized systems. The efficiency price which must be paid for this type of organization can be overcome by providing some simple mechanisms in the hardware to support the level structure. It is the purpose of this paper to point out where the hardware support is needed and to suggest one way of implementing these features.

A flexible feedback queueing model for a computer system is described. The model consists of a single server and a queue into which jobs are inserted at positions which are functions of their attained service. Special cases of the model include both the round robin and the first-come-first-served disciplines, but a wide variety of other algorithms, having different performance characteristics, can also be obtained. The model is analyzed using Markovian assumptions, and both the finite quantum and processor sharing cases are considered. The relationship of the model to system overhead is also treated.

The paper contains a description of the structure of processes and the interprocess communication facility implemented within a general purpose operating system. Processes within the system operate asynchronously. The communication facility allows a process to signal another process, to send information to it, to cause it to be suspended or to cause it to be terminated.

A class of binary recurrent codes for correcting independent errors is given which has guaranteed error-limiting properties. These codes can be simply decoded using threshold decoding, and will recover from any decoding error caused by either an uncorrectable transmission error or a temporary malfunction of the encoder or decoder. A number of such codes are given along with a synthesis procedure. The results of a computer simulation are given which indicate that these codes perform better in some situations than other codes using threshold decoding.

A set of conditions are described which determine whether or not two successive portions of a given program can be performed in parallel and still produce the same results. The conditions are general and can be applied to sections of the program of arbitrary size. The conditions are interesting because of the light they shed on the structure of programs amenable to parallel processing and the memory organization of a multi-computer system.

Various encoding schemes are examined from the point of view of minimizing the mean magnitude error of a signal caused by transmission through a binary symmetric channel. A necessary property is developed for optimal codes for any binary symmetric channel and any set of quantization levels. The class of optimal codes is found for the case where the probability of error is small but realistic. This class of codes includes the natural numbering and some unit distance codes, among which are the Gray codes.

A linear coding scheme for the correction of all possible single errors during arithmetic operations on binary number representations is discussed. The coded form of a numberkis the binary representation of the numberkt, wheretis a positive integer. The code corrects all errors of the form\pm2^i, whereiis less thann, the number of digits in the code words. The problem of determining the largest numberkwhich may be encoded for a particular value oftis discussed. It is also shown that as the number of arithmetic operations to be performed increases, the use of this coding scheme becomes more significant in improving the reliability of the computational unit. An asymmetric process (in which only 1-errors or only O-errors are to be corrected) is also investigated and compared with the symmetric process.