We present an efficient algorithm for providing transactional guarantees when federating a transactional object store with a stream processing engine. The object store allows transactions to programmatically access and update persistent tables as inmemory map objects. The stream processing engine processes continuous queries on events from designated map objects to generate continuously updated derived views. Stream processing traditionally provides an “eventual correctness” guarantee; however our clients insisted upon a uniform transactional quality of service for the federated system: in particular, the system must guarantee that no transaction can observe an updated map object and a stale value of a derived view. A straightforward approach would entail executing all stream processing within the scope of transactions, and this comes at a performance cost. Our approach, based on a hybrid optimistic concurrency control technique, allows stream processing to proceed in parallel, usually after commit time. We present our algorithm along with experimental performance evaluations of both approaches.

We present and evaluate a low-overhead approach for achieving high-availability in distributed event-processing middleware systems consisting of networks of stateful software components that communicate by either one-way (send) or two-way (call) messages. The approach is based on transparently augmenting each component to produce a deterministic component whose state can be recovered by checkpoint and replay. Determinism is achieved by augmenting messages with virtual times, and by scheduling message handling in virtual time order. Scheduling delays are reduced by computing virtual times with estimators: deterministic functions that approximate the expected real times of arrival. We describe our algorithms, show how Java components can be transparently augmented with checkpointing code and with good estimators, discuss how our deterministic runtime can be tuned to reduce overhead, and provide experimental results to measure the overhead of determinism relative to non-determinism.

In this paper, we describe the SMILE (Smart MIddleware, Light Ends) system which is one of the earliest systems built in the area of distributed event stream processing. SMILE unites the "publish-subscribe" model of messaging middleware with the "continuous query" model of database systems. In SMILE, information producers, which may be sensors, applications, or databases, generate streams of events, such as RFID data, news items or stock trades; consumers specify stateful subscriptions to derived views, such as "individuals trading top 5 total volume of stock Y within x minutes before a major news story about the same company Y"; the SMILE system constructs and deploys a dataflow network of computations which process events from producers, compute derived views and deliver continuous and timely updates of subscribed views to consumers. Research challenges addressed by SMILE include: rigorously defining the semantics for correct state delivery; implementing this semantics in the presence of failure; distributing computations optimally over a network of multiple servers; scheduling and controlling message flow in this network; smoothly integrating this technology with other components, e.g., databases, services, user interfaces. SMILE is applicable to any "sense and respond" scenario that requires monitoring and processing of events as they are generated. Applications span multiple industries, e.g., monitoring financial opportunities and detecting potential fraud in financial industry, systems management and alerts in data centers, inventory management in RFID applications, and business performance management. In this paper, we describe the SMILE system, its architecture, services supported, and implementation details, and its use in multiple application scenarios.

This paper presents a general knowledge model for propagating information in a content-based publish-subscribe system. The model is used to derive an efficient and scalable Protocol for exactly-once delivery to large numbers (tens of thousands per broker) of content-based subscribers in either publisher order or uniform total order Our protocol allows intermediate content filtering at each hop, but requires persistent storage only at the publishing site. It is tolerant of message drops, message reorderings, node failures, and link failures, and maintains only "soft" state at intermediate nodes. We evaluate the performance of our implementation both under failure-free conditions and with fault injection.

Publish-subscribe messaging middleware typically offers limited and low-level options for quality of service, such as best-effort delivery versus reliable delivery, or ordered versus unordered. We propose a new, high-level approach to specifying quality of service, in which the consumer specifies an event stream interpretation function that maps an event stream into a state that represents the consumer's semantics of the stream. Under this approach, the system may deliver either the subscribed event stream, or any alternative stream whose image under the interpretation function yields the same state. Event stream interpretation gives consumers the ability to more accurately specify the tolerable distortions of perfect message delivery, and gives middleware implementations the flexibility to use more efficient protocols for message delivery and failure recovery while preserving application safety.

We introduce Guava, a dialect of Java whose rules statically guarantee that parallel threads access shared data only through synchronized methods. Our dialect distinguishes three categories of classes: (1) monitors, which may be referenced from multiple threads, but whose methods are accessed serially; (2) values, which cannot be referenced and therefore are never shared; and (3) objects, which can have multiple references but only from within one thread, and therefore do not need to be synchronized. Guava circumvents the problems associated with today's Java memory model, which must define behavior when concurrent threads access shared memory without synchronization.We present an overview of the syntax and the semantic rules of Guava. We discuss how implementations of Guava can exploit these rules to re-enable compiler optimizations inhibited by standard Java. We discuss how compilers for certain multiprocessor architectures can automatically generate certain programming idioms, such as double-check reads, as optimizations of serialized monitors.

We present an approach for merging message streams from producers distributed over a network, using a deterministic algorithm that is independent of any nondeterminism of the system, such as the amount of time the messages are delayed by the network, or their arrival order. Thus, if this algorithm is replicated at multiple "mergers", then each merger will merge the message streams in exactly the same way. The technique is therefore a solution to atomic broadcast and global atomic multicast [12]. We assume that each producer has access to (approximately) synchronized clocks and can estimate the expected message rates of all producers. We proposean algorithm, called the Bias Algorithm. To measure the performance of the Bias Algorithm, we assume that messages are generated by memoryless processes operating at known message rates, and we measure the expected total merge delay at a given time L. For the case of two producer processes, we give optimal algorithms in this metric, and show that the optimal algorithm converges to our Bias algorithm when L!1. We reconfirm our optimality result using Dynamic Programming theory, and we use simulations to validate the robustness of this optimality result under more realistic conditions. Our motivating application is middleware for a widely-distributed publish-subscribe system, where subscribers require uniform reliable ordered delivery. To allow recovery, messages are logged to stable storage at "logger" nodes, which serve as the sources for the message streams to be merged. We discuss the practical benefits of our approach in such environments.

The publish/subscribe (or pub/sub) paradigm is an increasingly popular model for interconnecting applications in a distributed environment. Many existing pub/sub systems are based on pre-defined subjects, and hence are able to exploit multicast technologies to provide scalability and availability. An emerging alternative to subject-based systems, known as content-based systems, allow information consumers to request events based on the content of published events. This model is considerably more flexible than subject-based pub/sub. However, it was previously not known how to efficiently multicast published events to interested content-based subscribers within a large and geographically distributed network of broker (or router) machines. We develop and evaluate a novel and efficient distributed algorithm for this purpose, called -link matching". Link matching performs just enough computation at each node to determine the subset of links to which an event should be forwarded. We show via simulations that: link matching yields higher throughput than flooding when subscriptions are selective; and the overall CPU utilization of link matching is comparable to that of centralized matching.

Content-based subscription systems are an emerging alternative to traditional publish-subscribe systems, because they permit more flexible subscriptions along multiple dimensions. In these systems, each subscription is a predicate which may test arbitrary attributes within an event. However, the matching problem for content-based systems — determining for each event the subset of all subscriptions whose predicates match the event — is still an open problem. We present an efficient, scalable solution to the matching problem. Our solution has an expected time complexity that is sub-linear in the number of subscriptions, and it has a space complexity that is linear. Specifically, we prove that for predicates reducible to conjunctions of elementary tests, the expected time to match a random event is no greater than O(N 1;) where N is the number of subscriptions, and is a closed-form expression that depends on the number and type of attributes (in some cases, 1=2). We present some optimizations to our algorithms that improve the search time. We also present the results of simulations that validate the theoretical bounds and that show acceptable performance levels for tens of thousands of subscriptions. 1

This paper describes algorithms for implementing a high-level programming model for synchronous distributed groupware applications. In this model, several application data objects may be atomically updated, and these objects automatically maintain consistency with their replicas using an optimistic algorithm. Changes to these objects may be optimistically or pessimistically observed by view objects by taking consistent snapshots. The algorithms for both update propagation and view notification are based upon optimistic guess propagation principles adapted for fast commit by using primary copy replication techniques. The main contribution of the paper is the synthesis of these two algorithmic techniques-guess propagation and primary copy replication-for implementing a framework that is easy to program to and is well suited for the needs of groupware applications.

This paper describes algorithms for implementing a high-level programming model for synchronous distributed groupware applications. In this model, several application data objects may be atomically updated, and these objects automatically maintain consistency with their replicas using an optimistic algorithm. Changes to these objects may be optimistically or pessimistically observed by view objects by taking consistent snapshots. The algorithms for both update propagation and view notification are based upon optimistic guess propagation principles, adapted for fast commit by using primary copy replication techniques. The main contribution of the paper is the synthesis of these two algorithmic techniques-guess propagation and primary copy replication-for implementing a framework that is easy to program and is well suited for the needs of groupware applications.

In this article we examine the augmentation of application interfaces with enhanced specifications that include sequencing constraints called protocols.Protocols make explicit the relationship between messages (methods) supported by the application.These relationships are usually only given implicitly, either in the code or in textual comments.We define notions of interface compatibility based upon protocols and show how compatibility can be checked, discovering a class of errors that cannot be discovered via the type system alone.We then define software adaptors that can be used to bridge the difference between applications that have functionally compatible but type-and protocol-incompatible interfaces.We discuss what it means for an adaptor to be well formed.Leveraging the information provided by protocols, we show how adaptors can be automatically generated from a high-level description, called an interface mapping.

In this paper we show how to augment object-oriented application interfaces with enhanced specifications that include sequencing constraints called protocols. Protocols make explicit the relationship between messages (methods) supported by the application. These relationships are usually only given implicitly, either in the code or in textual comments. We define notions of interface compatibility based upon protocols and show how compatibility can be checked, discovering a class of errors that cannot be discovered via the type system alone. We then define software adaptors that can be used to bridge the difference between object-oriented applications that have functionally compatible but type incompatible interfaces. We discuss what it means for an adaptor to be well-formed. Leveraging the information provided by protocols, we show how adaptors can be automatically generated from a high-level description, called an interface mapping.

The authors present a practical extension to typestate checking, which is capable of proving programs free of uninitialized variable errors even when these programs contain conditionally initialized variables where the initialization of a variable depends upon the equality of one or more tag variables to a constant. The user need not predeclare the relationship between a conditionally initialized variable and its tags, and this relationship may change from one point in the program to another. The technique generalizes liveness analysis to conditional liveness analysis. Like typestate checking, this technique incorporates a dataflow analysis algorithm in which each point in a program is labeled with a lattice point describing statically tracked information, including the initialization of variables. The labeling is then used to check for programming errors such as referencing a variable which may be uninitialized.>

We present a transparent program transformation which converts a sequential execution of S1 ; S2 by a process in a multiprocess environment into an optimistic parallel execution of S1 and S2 . Such a transformation is valuable in the case where S1 and S2 cannot be parallelized by static analysis either because S2 reads a value from S1 or because S1 and S2 each interact with an external process. The optimistic transformation works under a weaker set of conditions: (1) if the value S2 reads from S1 can usually, but not always, be correctly guessed ahead of time, and (2) if S1 and S2 interact with an external process, conflicts which violate the ordering of S1 and S2 are possible but rare. Practical applications of this approach include executing the likely outcome of a test in parallel with making the test, and converting sequences of calls into streams of asynchronous sends. We analyze the problem using the framework of guarded computations, in which each computation is tagged with th...

An incremental computation is one that is performed repeatedly on nearly identical inputs. Incremental computations occur naturally in many environments, such as compilers, language-based editors, spreadsheets, and formatters. This article describes a proposed tool for making it easy to write incremental programs. The tool consists of a programming language, INC, and a set of compile-time transformations for the primitive elements of INC. A programmer defines an algorithm in INC without regard to efficient incremental execution. The transformations automatically convert this algorithm into an efficient incremental algorithm. INC is a functional language. The implementation of an INC program is a network of processes. Each INC function is transformed into a process that receives and transmits messages describing changes to its inputs and outputs. We give an overview to the language and illustrate the incremental techniques employed by INC. We present the static and incremental complexity bounds for the primitive INC functions. We also present some example programs illustrating INC's flexibility.

article INC: a language for incremental computations Share on Authors: D. Yellin IBM T. J. Watson Research Center, Yorktown Heights, NY IBM T. J. Watson Research Center, Yorktown Heights, NYView Profile , R. Strom IBM T. J. Watson Research Center, Yorktown Heights, NY IBM T. J. Watson Research Center, Yorktown Heights, NYView Profile Authors Info & Claims ACM SIGPLAN NoticesVolume 23Issue 7July 1988 pp 115–124https://doi.org/10.1145/960116.54002Online:01 June 1988Publication History 16citation327DownloadsMetricsTotal Citations16Total Downloads327Last 12 Months4Last 6 weeks1 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

Article Free Access Share on Process semantics: universal axioms compositional rules, and applications Authors: van Vicious Nguyen IBM Thomas J. Watson Research Center, P.O. Box 704, Yorktown Heights, NY, USA IBM Thomas J. Watson Research Center, P.O. Box 704, Yorktown Heights, NY, USAView Profile , Rob Strom IBM Thomas J. Watson Research Center, P.O. Box 704, Yorktown Heights, NY, USA IBM Thomas J. Watson Research Center, P.O. Box 704, Yorktown Heights, NY, USAView Profile Authors Info & Claims PODC '88: Proceedings of the seventh annual ACM Symposium on Principles of distributed computingJanuary 1988 Pages 232–247https://doi.org/10.1145/62546.62585Published:01 January 1988Publication History 1citation230DownloadsMetricsTotal Citations1Total Downloads230Last 12 Months0Last 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 SiteeReaderPDF

The authors introduce a new programming language concept, called typestate, which is a refinement of the concept of type. Whereas the type of a data object determines the set of operations over permitted on the object, typestate determines the subset of these operations which is permitted in a particular context. Typestate tracking is a program analysis technique which enhances program reliability by detecting at compile-time syntactically legal but semantically undefined execution sequences. These include reading a variable before it has been initialized and dereferencing a pointer after the dynamic object has been deallocated. The authors define typestate, give examples of its application, and show how typestate checking may be embedded into a compiler. They discuss the consequences of typestate checking for software reliability and software structure, and summarize their experience in using a high-level language incorporating typestate checking.

Optimistic Recovery is a new technique supporting application-independent transparent recovery from processor failures in distributed systems. In optimistic recovery communication, computation and checkpointing proceed asynchronously. Synchronization is replaced by causal dependency tracking , which enables a posteriori reconstruction of a consistent distributed system state following a failure using process rollback and message replay . Because there is no synchronization among computation, communication, and checkpointing, optimistic recovery can tolerate the failure of an arbitrary number of processors and yields better throughput and response time than other general recovery techniques whenever failures are infrequent.

This paper discusses features of a secure systems programming language designed and implemented at IBM's Watson Research Lab. Two features of the language design were instrumental in permitting security to be enforced with minimum run-time cost: (1) Language constructs (e.g. pointer variables) which could result in aliasing were removed from the programmer's direct control and replaced by higher level primitive types; and (2) traditional strong type checking was enhanced with typestate checking, a new mechanism in which the compiler guarantees that for all execution paths, the sequence of operations on each variable obeys a finite state grammar associated with that variable's type. Examples are given to illustrate the application of these mechanisms.