There is a recent surge of studies on dynamic-committee proactive secret sharing (DPSS), in which not only will the shares be periodically refreshed (proactive secret sharing), but also the parties who hold the shares will be dynamically changed. It has direct applications in blockchain systems that require committees to manage confidential information, as well as in decentralized storage networks with dynamic participant involvement. Despite substantial attention, DPSS still has high communication complexity, particularly with large-size input data. In this article, we initiate the study of dynamic-committee proactive information dispersal (DPID). From a conceptual perspective, we can regard DPID as DPSS without the requirement for confidentiality. We model and construct DPID schemes with significantly reduced complexity. To demonstrate its efficiency, we also present a general framework for compiling our DPID into DPSS. By integrating our DPID construction, we achieve the first DPSS with much lower communication complexity for large-size data, whose benefits can be clearly shown in our experiments.

Sequential data access for the rapid ingestion of large fact tables from storage is a pivotal yet resource-intensive operation in data warehouse systems, consuming substantial CPU cycles across various components of DBMSs and operating systems. Although bypassing these layers can eliminate access latency, concurrent access to the same table often results in redundant data fetching due to cache-bypassing data transfers. Thus, a new design for data access control is necessary to enhance rapid data ingestion in databases. To address this concern, we propose a novel DB-OS co-design that efficiently supports sequential data access at full device speed. Our approach, zicIO, liberates DBMSs from data access control by preparing required data just before DBMSs access it, while alleviating all known I/O latencies. The core of zicIO lies in its DB-OS co-design, which aims to (1) automate data access control and (2) relieve redundant data fetching through seamless collaboration between the DB and the OS. We implemented zicIO and integrated it with four databases to demonstrate its general applicability. The evaluation showed performance enhancements of up to 9.95x under TPC-H loads.

HTAP systems aim to unify operational and analytical workloads, yet real-time analytics remains constrained by the overhead of extract-transform-load (ETL) operations. Existing solutions often rely on dual-system architectures, incurring substantial resource costs and delays from data reformatting and relocation. We present TracerETL , a progressive ETL framework that enables real-time analytics in standalone DBMSs through instant tuple location discovery during transformation. At its core is Tracer , a counting-based tuple tracking mechanism that constructs a tuple trace vector using per-partition counters. This trace vector deterministically encodes each tuple's future relocation path with arrival order across transformation levels, enabling precise data access at any stage-without auxiliary indexes. We implement TracerETL in PostgreSQL and evaluate it against OLAP- and OLTP-optimized DBMSs. Experimental results show that PostgreSQL with TracerETL accelerates real-time HTAP queries by up to 127×, while efficiently handling progressive data conversion in a standalone DBMS.

We propose a theory that can determine the lowest isolation level that can be allocated to each transaction program in an application in a mixed-isolation-level setting, to guarantee that all executions will be serializable and thus preserve all integrity constraints, even those that are not explicitly declared. This extends prior work applied to completely known transactions, to deal with the realistic situation where transactions are generated by running programs with parameters that are not known in advance. Using our theory, we propose an optimization method that allows for high throughput while ensuring that all executions are serializable. Our method is based on searching for application code modifications that are semantics-preserving while improving the isolation level allocation. We illustrate our approach to the SmallBank benchmark.

Many tools empower analysts and data scientists to consume analysis results in a visual interface. When the underlying data changes, these results need to be updated, but this update can take a long time---all while the user continues to explore the results. Tools can either (i) hide away results that haven't been updated, hindering exploration; (ii) make the updated results immediately available to the user (on the same screen as old results), leading to confusion and incorrect insights; or (iii) present old---and therefore stale---results to the user during the update. To help users reason about these options and others, and make appropriate trade-offs, we introduce Transactional Panorama, a formal framework that adopts transactions to jointly model the system refreshing the analysis results and the user interacting with them. We introduce three key properties that are important for user perception in this context: visibility (allowing users to continuously explore results), consistency (ensuring that results presented are from the same version of the data), and monotonicity (making sure that results don't "go back in time"). Within transactional panorama, we characterize all feasible property combinations, design new mechanisms (that we call lenses) for presenting analysis results to the user while preserving a given property combination, formally prove their relative orderings for various performance criteria, and discuss their use cases. We propose novel algorithms to preserve each property combination and efficiently present fresh analysis results. We implement our framework into a popular, open-source BI tool, illustrate the relative performance implications of different lenses, and demonstrate the benefits of the novel lenses and our optimizations.

This paper describes experiences in teaching Python programming as part of a large-enrolment first-year subject, that is a foundation for an undergraduate major in data science and it is also taken by a wide variety of non-majors across the arts, sciences and business fields. The paper focuses on some central design decisions about the content, sequence, approach, and tool support, and we reflect on how they have worked out and what we changed, as we have taught the subject to about 2500 students over four offerings (including two which were entirely on-line due to the pandemic). Particular aspects that are the focus in this paper include: teaching programming through a sequence of common patterns/idioms for data exploration and analysis, rather than in the language-feature focus that is traditional in programming classes; read-then-write-until-correct presentation for each pattern; explicit presentation of a notional machine for execution, in stages as more language complexity is experienced; starting with core Python before then covering use of libraries such as pandas, matplotlib and scikit-learn.

Many universities are introducing a new major in Data Science into their offering, to reflect the explosive growth in this field and the career opportunities it provides. As a field Data Science has elements from Computer Science and from Statistics, and curricula plans differ widely, both in the balance between the CS and Stats aspects, and also in the emphasis within the computing topics. This paper reports on the curriculum that has been taught for three years now at the University of Sydney. In particular, we describe the approach of a sequence of computing subjects which were developed specifically for the major, in order to bring students over several years to a sophisticated understanding of the data-handling aspects of Data Science. Students also take traditional subjects from both CS (such as Data Structures or AI) and from Statistics (such as Learning from Data and Statistical Inference). The data-centric specially-designed subjects we discuss in this paper are (i) Informatics: Data and Computation (in the first year), (ii) Big Data and Data Diversity (in the second year), and then upper-division subjects on (iii) Data Science Platforms, and (iv) Human-in-the-Loop Data Analytics.

MongoDB is a popular document store that is also available as a cloud-hosted service. MongoDB internally deploys primary-copy asynchronous replication, and it allows clients to vary the Read Preference, so reads can deliberately be directed to secondaries rather than the primary site. Doing this can sometimes improve performance, but the returned data might be stale, whereas the primary always returns the freshest data value. While state-of-practice is for programmers to decide where to direct the reads at application development time, they do not have full understanding then of workload or hardware capacity. It should be better to choose the appropriate Read Preference setting at runtime, as we describe in this paper. We show how a system can detect when the primary copy is saturated in MongoDB-as-a-Service, and use this to choose where reads should be done to improve overall performance. Our approach is aimed at a cloud-consumer; it assumes access to only the limited diagnostic data provided to clients of the hosted service.

A tutorial given at PODS 2019, focussed on several research agendas in the past decade or so, that examine weak isolation levels, and obtain many (or all) of the benefits for application integrity, traditionally achieved by serializable concurrency control. The tutorial presents both the mechanisms and the reasoning approaches from these research works.

Datalog has been applied to several use cases that require very high performance on large rulesets and factsets. It is common to create indexes for relations to improve search performance. However, the existing indexing schemes either require manual index selection or result in insufficient performance on very large tasks. In this paper, we propose an automatic scheme to select indexes. We automatically create the minimum number of indexes to speed up all the searches in a given Datalog program. We have integrated our indexing scheme into an open-source Datalog engine S OUFFLÉ. We obtain performance on a par with what users have accepted from hand-optimized Datalog programs running on state-of-the-art Datalog engines, while we do not require the effort of manual index selection. Extensive experiments on large real Datalog programs demonstrate that our indexing scheme results in considerable speedups (up to 2x) and significantly less memory usage (up to 6x) compared with other automated index selections.

Rolling upgradeis a widely-used industry technique for updating software while a service provided by multiple instances of the software remains available. In cloud deployments of software, it is usual to implement the update step for rolling upgrade by replacing entire virtual machine instances. During the process of rolling upgrade, various failures may occur due to the complexity of software stack and the uncertainties of cloud platforms. Instance health checking and replacement are standard functionalities in most cloud infrastructures, though these create uncertainty in the duration of the whole upgrade procedure. In contrast, software and configuration errors are not usually detected by infrastructure functionalities, and if these happen, the entire rolling upgrade normally is unsuccessful and the system is left in an unsuitable state. In this paper, we propose an approach, named R2C, which innovates the stat of the art with our early error detection and predictability to increase the robustness of rolling upgrade on cloud platforms. We evaluate our techniques through real life testing in Amazon Web Service (AWS) and through a simulation.

Summary In this paper, we introduce the Rotating skip list, the fastest concurrent skip list to date. Existing concurrent data structures experience limited scalability with the growing core count for two main reasons: threads contend while accessing the same shared data, and they require off‐chip communication to synchronize. Our solution combines the rotation of a tree to maintain logarithmic complexity deterministically, a skip list structure to avoid the tree root bottleneck, and no locks to limit cache line bouncing. This combination requires us to trade usual skip list towers for wheels, a novel algorithmic design that favors spatial locality and allows for a constant‐time restructuring operation. We evaluate the performance of our skip list on AMD Opteron and Intel Xeon multicores, show that its rotations guarantee its balance and compare its performance against seven state‐of‐the‐art skip lists and trees using four different synchronisation techniques. The Rotating skip list shows an unprecedented peak performance of 200 Mops/second. Copyright © 2016 John Wiley & Sons, Ltd.

Databases can provide scalability by partitioning data across several servers. However, multipartition, multioperation transactional access is often expensive, employing coordination-intensive locking, validation, or scheduling mechanisms. Accordingly, many real-world systems avoid mechanisms that provide useful semantics for multipartition operations. This leads to incorrect behavior for a large class of applications including secondary indexing, foreign key enforcement, and materialized view maintenance. In this work, we identify a new isolation model—Read Atomic (RA) isolation—that matches the requirements of these use cases by ensuringatomic visibility: either all or none of each transaction’s updates are observed by other transactions. We present algorithms for Read Atomic Multipartition (RAMP) transactions that enforce atomic visibility while offering excellent scalability, guaranteed commit despite partial failures (viacoordination-free execution), and minimized communication between servers (viapartition independence). These RAMP transactions correctly mediate atomic visibility of updates and provide readers with snapshot access to database state by using limited multiversioning and by allowing clients to independently resolve nonatomic reads. We demonstrate that, in contrast with existing algorithms, RAMP transactions incur limited overhead—even under high contention—and scale linearly to 100 servers.

Rolling upgrade consists of upgrading progressively the servers of a distributed system to reduce service downtime.Upgrading a subset of servers requires a well-engineered cluster membership protocol to maintain, in the meantime, the availability of the system state. Existing cluster membership reconfigurations, like CoreOS etcd, rely on a primary not only for reconfiguration but also for storing information. At any moment, there can be at most one primary, whose replacement induces disruption. We propose Rollup, a non-disruptive rolling upgrade protocol with a fast consensus-based reconfiguration. Rollup relies on a candidate leader only for the reconfiguration and scalable biquorums for service requests. While Rollup implements a non-disruptive cluster membership protocol, it does not offer a full-fledged coordination service. We analyzed Rollup theoretically and experimentally on an isolated network of 26 physical machines and an Amazon EC2 cluster of 59 virtual machines. Our results show an 8-fold speedup compared to a rolling upgrade based on a primary for reconfiguration.

Several DBMS engines use Read Committed (RC) as a default isolation level, risking the loss of data integrity but allowing more concurrency. We propose ways to preanalyse (and then modify) the code of a set of applications, that will allow us to run at RC isolation and still guarantee that all executions are serializable. Our experiments show performance that is significantly higher than from traditional ways that ensure correctness by directly using stronger isolation mechanisms (two-phase locking or snapshot isolation) that might be available in the engine. The overhead of our approach compared to RC on unmodified application programs is typically only about 5-10%.

Concurrency control (CC) algorithms must trade off strictness for performance, with serializable schemes generally paying high cost---both in runtime overhead such as contention on lock tables, and in wasted efforts by aborting transactions---to prevent anomalies. We propose the serial safety net (SSN), a serializability-enforcing certifier for modern hardware with substantial core count and large main memory. SSN can be applied with minimal overhead on top of various CC schemes that offer higher performance but admit anomalies, e.g., snapshot isolation and read committed.

Restful APIs are widely adopted in designing components that are combined to form web information systems. The use of REST is growing with the inclusion of smart devices and the Internet of Things, within the scope of web information systems, along with large-scale distributed NoSQL data stores and other web-based and cloud-hosted services. There is an important subclass of web information systems and distributed applications which would benefit from stronger transactional support, as typically found in traditional enterprise systems. In this paper, we propose REST+T (REST with Transactions), a transactional Restful data access protocol and API that extends HTTP to provide multi-item transactional access to data and state information across heterogeneous systems. We describe a case study called Tora, where we provide access through REST+T to an existing key-value store (WiredTiger) that was intended for embedded operation.

Typical cloud computing systems provide highly scalable and fault-tolerant data stores that may sacrifice other features like general multi-item transaction support. Recently techniques to implement multi-item transactions in these types of systems have focused on transactions across homogeneous data stores. Since applications access data in heterogeneous storage systems for legacy or interoperability reasons, we propose an approach that enables multi-item transactions with snapshot isolation across multiple heterogeneous data stores using only a minimal set of commonly implemented features such as single item consistency, conditional updates, and the ability to store additional meta-data. We define an client-coordinated transaction commitment protocol that does not rely on a central coordinating infrastructure. The application can take advantage of the scalability and fault-tolerance characteristics of modern key-value stores and access existing data in them, and also have multi-item transactional access guarantees with little performance impact. We have implemented our design in a Java library called Cherry Garcia (CG), that supports data store abstractions to Windows Azure Storage (WAS), Google Cloud Storage (GCS) and our own high-performance key-value store called Tora.

The rise of data-intensive "Web 2.0" Internet services has led to a range of popular new programming frameworks that collectively embody the latest incarnation of the vision of Object-Relational Mapping (ORM) systems, albeit at unprecedented scale. In this work, we empirically investigate modern ORM-backed applications' use and disuse of database concurrency control mechanisms. Specifically, we focus our study on the common use of feral, or application-level, mechanisms for maintaining database integrity, which, across a range of ORM systems, often take the form of declarative correctness criteria, or invariants. We quantitatively analyze the use of these mechanisms in a range of open source applications written using the Ruby on Rails ORM and find that feral invariants are the most popular means of ensuring integrity (and, by usage, are over 37 times more popular than transactions). We evaluate which of these feral invariants actually ensure integrity (by usage, up to 86.9%) and which---due to concurrency errors and lack of database support---may lead to data corruption (the remainder), which we experimentally quantify. In light of these findings, we present recommendations for database system designers for better supporting these modern ORM programming patterns, thus eliminating their adverse effects on application integrity.

Rolling upgrade is a practical industry technique for online updating of software in distributed systems. This paper focuses on rolling upgrade of software versions in virtual machine instances on cloud computing platforms, when various failures may occur. An operator can choose the number of instances that are updated in one round and system environments to minimise completion time, availability degradation, and monetary cost for entire rolling upgrade, and hence this is a multi-objective optimisation problem. To predict completion time in the presence of failures, we offer a stochastic model that represents the dynamics of rolling upgrade. To reduce the computational effort of decision making for large scale complex systems, we propose a technique that can find a Pareto set quickly via an upper bound of the expected completion time. Then an optimum of the original problem can be chosen from this set of potential solutions. We validate our approach to minimise the objectives, through both experiments in Amazon Web Service (AWS) and simulations.

Since 1990's, Snapshot Isolation (SI) has been widely studied, and it was successfully deployed in commercial and open-source database engines. Berenson et al. showed that data consistency can be violated under SI. Recently, a new class of Serializable SI algorithms (SSI) has been proposed to achieve serializable execution while still allowing concurrency between reads and updates.

Databases can provide scalability by partitioning data across several servers. However, multi-partition, multi-operation transactional access is often expensive, employing coordination-intensive locking, validation, or scheduling mechanisms. Accordingly, many real-world systems avoid mechanisms that provide useful semantics for multi-partition operations. This leads to incorrect behavior for a large class of applications including secondary indexing, foreign key enforcement, and materialized view maintenance. In this work, we identify a new isolation model---Read Atomic (RA) isolation---that matches the requirements of these use cases by ensuring atomic visibility: either all or none of each transaction's updates are observed by other transactions. We present algorithms for Read Atomic Multi-Partition (RAMP) transactions that enforce atomic visibility while offering excellent scalability, guaranteed commit despite partial failures (via synchronization independence), and minimized communication between servers (via partition independence). These RAMP transactions correctly mediate atomic visibility of updates and provide readers with snapshot access to database state by using limited multi-versioning and by allowing clients to independently resolve non-atomic reads. We demonstrate that, in contrast with existing algorithms, RAMP transactions incur limited overhead---even under high contention---and scale linearly to 100 servers.

Latency unpredictability in a database system can come from many factors, such as load spikes in the workload, inter-query interactions from consolidation, or communication costs in cloud computing or geo-replication. High variance and high latency environments make developing interactive applications difficult, because transactions may take too long to complete, or fail unexpectedly. We propose Predictive Latency-Aware NEtworked Transactions (PLANET), a new transaction programming model and underlying system support to address this issue. The model exposes the internal progress of the transaction, provides opportunities for application callbacks, and incorporates commit likelihood prediction to enable good user experience even in the presence of significant transaction delays. The mechanisms underlying PLANET can be used for admission control, thus improving overall performance in high contention situations. In this paper, we present this new transaction programming model, demonstrate its expressiveness via several use cases, and evaluate its performance using a strongly consistent geo-replicated database across five data centers.

Minimizing coordination, or blocking communication between concurrently executing operations, is key to maximizing scalability, availability, and high performance in database systems. However, uninhibited coordination-free execution can compromise application correctness, or consistency. When is coordination necessary for correctness? The classic use of serializable transactions is sufficient to maintain correctness but is not necessary for all applications, sacrificing potential scalability. In this paper, we develop a formal framework, invariant confluence, that determines whether an application requires coordination for correct execution. By operating on application-level invariants over database states (e.g., integrity constraints), invariant confluence analysis provides a necessary and sufficient condition for safe, coordination-free execution. When programmers specify their application invariants, this analysis allows databases to coordinate only when anomalies that might violate invariants are possible. We analyze the invariant confluence of common invariants and operations from real-world database systems (i.e., integrity constraints) and applications and show that many are invariant confluent and therefore achievable without coordination. We apply these results to a proof-of-concept coordination-avoiding database prototype and demonstrate sizable performance gains compared to serializable execution, notably a 25-fold improvement over prior TPC-C New-Order performance on a 200 server cluster.

SUMMARY The technological advances in wireless sensor network (WSN) enable the development of complex applications including health monitoring, environmental sampling, and disaster area monitoring. WSN applications deploy battery‐powered sensors at remote locations for long periods. The development of energy‐efficient and complex WSN applications therefore requires in‐depth embedded systems programming skills that are normally not found in domain experts. So that this challenge can be overcome, programming environments for WSN need to offer a high degree of productivity, flexibility, and efficiency at the same time. In this work, we present Curracurrong, a development environment for WSNs that is based on expressing queries with stream programming. A query is represented as a stream graph consisting of stream operators and communication channels. Curracurrong provides an extensible stream operator library that adapts to a wide range of applications. It uses a novel placement algorithm that optimizes the energy consumption on sensor nodes. Through a case study, we demonstrate the productivity and flexibility of our system. We conduct experiments that evaluate the energy efficiency of our optimized operator placement algorithm. Copyright © 2012 John Wiley & Sons, Ltd.

Modern implementations of DBMS software are intended to take advantage of high core counts that are becoming common in high-end servers. However, we have observed that several database platforms, including MySQL, Shore-MT, and a commercial system, exhibit throughput collapse as load increases into oversaturation (where there are more request threads than cores), even for a workload with little or no logical contention for locks, such as a read-only workload. Our analysis of MySQL identifies latch contention within the lock manager as the bottleneck responsible for this collapse. We design a lock manager with reduced latching, implement it in MySQL, and show that it avoids the collapse and generally improves performance. Our efficient implementation of a lock manager is enabled by a staged allocation and deallocation of locks. Locks are preallocated in bulk, so that the lock manager only has to perform simple list manipulation operations during the acquire and release phases of a transaction. Deallocation of the lock data structures is also performed in bulk, which enables the use of fast implementations of lock acquisition and release as well as concurrent deadlock checking.

Replicating data across multiple data centers allows using data closer to the client, reducing latency for applications, and increases the availability in the event of a data center failure. MDCC (Multi-Data Center Consistency) is an optimistic commit protocol for geo-replicated transactions, that does not require a master or static partitioning, and is strongly consistent at a cost similar to eventually consistent protocols. MDCC takes advantage of Generalized Paxos for transaction processing and exploits commutative updates with value constraints in a quorum-based system. Our experiments show that MDCC outperforms existing synchronous transactional replication protocols, such as Megastore, by requiring only a single message round-trip in the normal operational case independent of the master-location and by scaling linearly with the number of machines as long as transaction conflict rates permit.

Modern implementations of DBMS software are intended to take advantage of high core counts that are becoming common in high-end servers. However, we have observed that several database platforms, including MySQL, Shore-MT, and a commercial system, exhibit throughput collapse as load increases, even for a workload with little or no logical contention for locks. Our analysis of MySQL identifies latch contention within the lock manager as the bottleneck responsible for this collapse.

To minimize network latency and remain online during server failures and network partitions, many modern distributed data storage systems eschew transactional functionality, which provides strong semantic guarantees for groups of multiple operations over multiple data items. In this work, we consider the problem of providing Highly Available Transactions (HATs): transactional guarantees that do not suffer unavailability during system partitions or incur high network latency. We introduce a taxonomy of highly available systems and analyze existing ACID isolation and distributed data consistency guarantees to identify which can and cannot be achieved in HAT systems. This unifies the literature on weak transactional isolation, replica consistency, and highly available systems. We analytically and experimentally quantify the availability and performance benefits of HATs---often two to three orders of magnitude over wide-area networks---and discuss their necessary semantic compromises.

Causal consistency is the strongest consistency model that is available in the presence of partitions and provides useful semantics for human-facing distributed services. Here, we expose its serious and inherent scalability limitations due to write propagation requirements and traditional dependency tracking mechanisms. As an alternative to classic potential causality, we advocate the use of explicit causality, or application-defined happens-before relations. Explicit causality, a subset of potential causality, tracks only relevant dependencies and reduces several of the potential dangers of causal consistency.

A database supporting multiple versions of records may use the versions to support queries of the past or to increase concurrency by enabling reads and writes to be concurrent. We introduce a new concurrency control approach that enables all SQL isolation levels including serializability to utilize multiple versions to increase concurrency while also supporting transaction time database functionality. The key insight is to manage a range of possible timestamps for each transaction that captures the impact of conflicts that have occurred. Using these ranges as constraints often permits concurrent access where lock based concurrency control would block. This can also allow blocking instead of some aborts that are common in earlier multi-version concurrency techniques. Also, timestamp ranges can be used to conservatively find deadlocks without graph based cycle detection. Thus, our multi-version support can enhance performance of current time data access via improved concurrency, while supporting transaction time functionality.

One major benefit claimed for cloud computing is elasticity: the cost to a consumer of computation can grow or shrink with the workload. This paper offers improved ways to quantify the elasticity concept, using data available to the consumer. We define a measure that reflects the financial penalty to a particular consumer, from under-provisioning (leading to unacceptable latency or unmet demand) or over-provisioning (paying more than necessary for the resources needed to support a workload). We have applied several workloads to a public cloud; from our experiments we extract insights into the characteristics of a platform that influence its elasticity. We explore the impact of the rules used to increase or decrease capacity.

One major obstacle to enterprise adoption of cloud technologies has been the lack of visibility into migration effort and cost. In this paper, we present a methodology, called Cloud Migration Point (CMP), for estimating the size of cloud migration projects, by recasting a well-known software size estimation model called Function Point (FP) into the context of cloud migration. We empirically evaluate our CMP model by performing a cross-validation on six different small-scale cloud migration projects and show that our size estimation model can be used as a reliable predictor for effort estimation. Furthermore, we prove that our CMP model satisfies the fundamental properties of a software size measure.

This paper presents a method that allows a replicated database system to provide a global isolation level stronger than the isolation level provided on each individual database replica. We propose a new multi-version concurrency control algorithm called, serializable generalized snapshot isolation (SGSI), that targets middleware replicated database systems. Each replica runs snapshot isolation locally and the replication middleware guarantees global one-copy serializability. We introduce novel techniques to provide a stronger global isolation level, namely readset extraction and enhanced certification that prevents read-write and write-write conflicts in a replicated setting. We prove the correctness of the proposed algorithm, and build a prototype replicated database system to evaluate SGSI performance experimentally. Extensive experiments with an 8 replica database system under the TPC-W workload mixes demonstrate the practicality and low overhead of the algorithm.

Snapshot Isolation (SI) is a popular concurrency control mechanism that has been implemented by many commercial and open-source platforms (e.g. Oracle, Postgre SQL, and MS SQL Server 2005). Unfortunately, SI can result in nonserializable execution, in which database integrity constraints can be violated. The literature reports some techniques to ensure that all executions are serializable when run in an engine that uses SI for concurrency control. These modify the application by introducing conflicting SQL statements. However, with each of these techniques the DBA has to make a choice among possible transactions to modify — and as we previously showed, making a bad choice of which transactions to modify can come with a hefty performance reduction. In this paper we propose a novel technique called ELM to introduce conflicts in a separate lock-manager object. Experiments with two platforms show that ELM has peak performance which is similar to SI, no matter which transactions are chosen for modification. That is, ELM is much less vulnerable from poor DBA choices than the previous techniques.

Choosing a weak isolation level such as Read Committed is understood as a trade-off, where less isolation means that higher performance is gained but there is an increased possibility that data integrity will be lost. Previously, one side of this trade-off has been carefully studied quantitatively -- there are well-known metrics for performance such as transactions per minute, standardized benchmarks that measure these in a controlled way, and analytic models that can predict how performance is influenced by system parameters like multiprogramming level. This paper contributes to quantifying the other aspect of the trade-off. We define a novel microbenchmark that measures how rapidly integrity violations are produced at different isolation levels, for a simple set of transactions. We explore how this rate is impacted by configuration factors such as multiprogramming level, or contention frequency. For the isolation levels in multi-version platforms (Snapshot Isolation and the multiversion variant of Read Committed), we offer a simple probabilistic model that predicts the rate of integrity violations in our microbenchmark from configuration parameters. We validate the predictive model against measurements from the microbenchmark. The model identifies a region of the configuration space where a surprising inversion occurs: for these parameter settings, more integrity violations happen with Snapshot Isolation than with multi-version Read Committed, even though the latter is considered a lower isolation level.

Many popular database management systems implement a multiversion concurrency control algorithm called snapshot isolation rather than providing full serializability based on locking. There are well-known anomalies permitted by snapshot isolation that can lead to violations of data consistency by interleaving transactions that would maintain consistency if run serially. Until now, the only way to prevent these anomalies was to modify the applications by introducing explicit locking or artificial update conflicts, following careful analysis of conflicts between all pairs of transactions. This article describes a modification to the concurrency control algorithm of a database management system that automatically detects and prevents snapshot isolation anomalies at runtime for arbitrary applications, thus providing serializable isolation. The new algorithm preserves the properties that make snapshot isolation attractive, including that readers do not block writers and vice versa. An implementation of the algorithm in a relational DBMS is described, along with a benchmark and performance study, showing that the throughput approaches that of snapshot isolation in most cases.

It is usually expected that performance is reduced by using stricter concurrency control, which reduces the risk of anomalies that can lead to data corruption. For example, the weak isolation level Read Committed allows anomalies that are prevented by two-phase locking (abbreviated 2PL), and because 2PL holds locks for longer than RC, it has lower throughput. We show that sometimes, guaranteed correctness can be obtained along with better throughput than RC, by use of the multiversion snapshot isolation mechanism along with modifications to application programs as proposed by Fekete et al. We investigate the conditions under which this effect occurs.

Several common DBMS engines use the multi- version concurrency control mechanism called Snapshot Isolation, even though application programs can experience non- serializable executions when run concurrently on such a platform. Several proposals exist for modifying the application programs, without changing their semantics, so that they are certain to execute serializably even on an engine that uses SI. We evaluate the performance impact of these proposals, and find that some have limited impact (only a few percent drop in throughput at a given multi-programming level) while others lead to much greater reduction in throughput of up-to 60% in high contention scenarios. We present experimental results for both an open- source and a commercial engine. We relate these to the theory, giving guidelines on which conflicts to introduce so as to ensure correctness with little impact on performance.

Concurrent programming was once the preserve of experts writing systems internals; but recently the growing importance of application servers, and the excellent support in Java and C# for thread handling, has brought threads and locking as topics that every software developer might experience, and therefore every computer science graduate ought to know. In this paper we report on several years of experience teaching this material in the early years of the curriculum. We focus on one aspect of multi-threaded code, namely how to write sensible thread-safe classes. We identify the learning outcomes we aim to deliver, and we discuss the main pedagogic difficulties students find. We present some examples that can help students avoid common erroneous views.

Many popular database management systems offer snapshot isolation rather than full serializability. There are well-known anomalies permitted by snapshot isolation that can lead to violations of data consistency by interleaving transactions that individually maintain consistency. Until now, the only way to prevent these anomalies was to modify the applications by introducing artificial locking or update conflicts, following careful analysis of conflicts between all pairs of transactions.

While the dominant approach to persistent storage in practice is to use a relational DBMS, there are some specialist applications that rely on object stores. The performance of these applications depends on the efficiency of the object store's concurrency control mechanism. Today's predominant concurrency control mechanism is strict two-phase object locking. In the 1980s, an interesting alternative was developed: commutativity-based semantic locking. In theory, it can outperform traditional locking schemes in certain scenarios with appropriate commutativity potential. In this paper, we study the real-world performance of different locking strategies in a particular industrial application from the telecommunications sector. We compare object-based locking and commutativity-based semantic locking. We found that, in this application, semantic locking performs equally to, but no better than, object locking in reasonable mixes of real- world transactions, and that it only outperforms in a deliberately contrived mix.

Among the problems facing designers of complex multi-participant Web services-based applications is dealing with the consequences of the lack of suitable isolation mechanisms. This deficiency means that concurrent applications can interfere with each other, resulting in race conditions and lost updates. This paper considers a proposed solution to this problem based on 'promises' and shows that this model can be implemented in practice. We consider implementation issues that need to be handled in promise-based systems and discuss a proof of concept prototype that supports promise-based isolation without requiring changes to existing applications and resources.

This paper discusses a novel implementation of a workflow engine that supports service-based applications. The applications are defined according to the GAT model, which is an event-based programming model using conditional guards to determine when both normal and exception-handling activities are to be executed. We propose implementation techniques for key features of GAT. These include implementing control flow based on the evaluation of guards, the management and distribution of events, and enforcing atomicity across the evaluation of guards and the execution of the corresponding activities. We have built an engine following this approach which uses available technologies to support translating GAT models into executable applications

The Web services and service-oriented architectures (SOA) vision by Helland, P. (2005) is about building large-scale distributed applications by composing coarse-grained autonomous services in a flexible architecture that can adapt to changing business requirements. These services interact by exchanging one-way messages through standardized message processing and transport protocols. This vision is being driven by economic imperatives for integration and automation across administrative and organizational boundaries. This paper presents a concise yet expressive model for service contracts to describe messaging behavior. The idea is simple: we use Boolean conditions to specify when a message can be sent and received, where the conditions refer only to other messages in the service contract - that is, conditions only refer to a service's externalized messaging state and not to internal state

Many applications, such as e-commerce, routinely use copies of data that are not in sync with the database due to heuristic caching strategies used to enhance performance. We study concurrency control for a transactional model that allows update transactions to read out-of-date copies. Each read operation carries a "freshness constraint" that specifies how fresh a copy must be in order to be read. We offer a definition of correctness for this model and present algorithms to ensure several of the most interesting freshness constraints. We outline a serializability-theoretic correctness proof and present the results of a detailed performance study.

Transaction management is an important topic in the database course. This remains true whether the subject has an application focus or a systems internals focus. All the standard textbooks use toy examples of transactions, expressed as sequences of simple operations such as reading or writing data items. In this paper we argue that the teacher should choose examples which are closer to the students' experiences in other topics of the course, that is, the transactions should be like programs with SQL statements. We discuss the requirements that must be considered in choosing useful examples, and we give a set of examples that we have constructed to meet many of these requirements.

Serializability is a key property for executions of OLTP systems; without this, integrity constraints on the data can be violated due to concurrent activity. Serializability can be guaranteed regardless of application logic, by using a serializable concurrency control mechanism such as strict two-phase locking (S2PL); however the reduction in concurrency from this is often too great, and so a DBMS offers the DBA the opportunity to use different concurrency control mechanisms for some transactions, if it is safe to do so. However, little theory has existed to decide when it is safe! In this paper, we discuss the problem of taking a collection of transactions, and allocating each to run at an appropriate isolation level (and thus use a particular concurrency control mechanism), while still ensuring that every execution will be conflict serializable. When each transaction can use either S2PL, or snapshot isolation, we characterize exactly the acceptable allocations, and provide a simple graph-based algorithm which determines the weakest acceptable allocation.

Snapshot Isolation (SI) is a multiversion concurrency control algorithm, first described in Berenson et al. [1995]. SI is attractive because it provides an isolation level that avoids many of the common concurrency anomalies, and has been implemented by Oracle and Microsoft SQL Server (with certain minor variations). SI does not guarantee serializability in all cases, but the TPC-C benchmark application [TPC-C], for example, executes under SI without serialization anomalies. All major database system products are delivered with default nonserializable isolation levels, often ones that encounter serialization anomalies more commonly than SI, and we suspect that numerous isolation errors occur each day at many large sites because of this, leading to corrupt data sometimes noted in data warehouse applications. The classical justification for lower isolation levels is that applications can be run under such levels to improve efficiency when they can be shown not to result in serious errors, but little or no guidance has been offered to application programmers and DBAs by vendors as to how to avoid such errors. This article develops a theory that characterizes when nonserializable executions of applications can occur under SI. Near the end of the article, we apply this theory to demonstrate that the TPC-C benchmark application has no serialization anomalies under SI, and then discuss how this demonstration can be generalized to other applications. We also present a discussion on how to modify the program logic of applications that are nonserializable under SI so that serializability will be guaranteed.

Server-side component technologies such as Enterprise JavaBeans (EJBs), .NET, and CORBA are commonly used in enterprise applications that have requirements for high performance and scalability. When designing such applications, architects must select suitable component technology platform and application architecture to provide the required performance. This is challenging as no methods or tools exist to predict application performance without building a significant prototype version for subsequent benchmarking. In this paper, we present an approach to predict the performance of component-based server-side applications during the design phase of software development. The approach constructs a quantitative performance model for a proposed application. The model requires inputs from an application-independent performance profile of the underlying component technology platform, and a design description of the application. The results from the model allow the architect to make early decisions between alternative application architectures in terms of their performance and scalability. We demonstrate the method using an EJB application and validate predictions from the model by implementing two different application architectures and measuring their performance on two different implementations of the EJB platform.

One important trend in enterprise-scale IT has been the increasing use of business-business integration (B2Bi) technologies to automate business processes that cross organizational boundaries, such as the interactions between partner companies along a supply chain. It is relatively easy to describe a pattern of interaction, or choreography, in the case where everything proceeds smoothly. However, the abnormal cases, such as where a process fails or a message is lost, are much more complicated, and risk introducing data and process inconsistencies into computer-based systems. Current B2Bi technologies do not supply an infrastructure that can provide reliability without considerable sophistication from the architects and developers. As a first step towards guiding architects to the design of B2Bi systems that maintain consistency despite failures, this paper describes a variety of types of failure that can arise in practice, based on a realistic e-procurement scenario. We describe these failures in terms of the different types of state that naturally occur within the distributed system. Understanding the types of failure that need to be handled, or prevented, is essential to an architect or developer who must design and write handlers for all the exceptions that can occur in their workflows.

An important problem in designing infrastructure to support business-to-business integration (B2Bi) is how to cancel a long-running interaction (either because the user has changed their mind, or in response to an unrecoverable failure). We review the fault-handling and compensation mechanism that is now used in most workflow products and business process modeling standards. We then use an e-procurement case-study to extract a set of requirements for an effective cancellation mechanism, and we show that the standard approach using fault-handling, and compensation transactions is not adequate to meet these requirements.

A typical object database manages concurrency control by instance locking, based on the identification of instance operations as "read" or "write". An alternative theory shows that additional concurrency can be obtained based on operation commutativity. Under commutativity theory, activities can be allowed concurrently as long as they commute, that is, the effect is the same in either order. In this paper, we study an extensive commercial application from a telecommunications domain, and determine how much concurrency is actually present for commutativity theory to use. Our study extends to identify not only the operations that commute, but the reasons for their commutativity as well. We separated the commutative operations into three categories: those that commute because both are read operations, those that commute because different fields are accessed, and those that commute for semantic reasons. By doing this in our analysis we were able to show a comparison in concurrency potential between commutative locking and the two other common locking protocols in existence: instance locking and attribute locking.

In recent years, the teaching of data structures has been revolutionised by object-oriented languages, especially Java, in which the concept of each Abstract Data Type is made explicit as an Interface. The existing texts, though, each use a single set of classes: sometimes a standard library such as Sun's SDK, but in other cases these form a library unique to the text. In contrast, this paper advocates an approach which seeks to prepare students for the common situation for software developers, who are asked to regularly adjust to a library they are unfamiliar with. The teaching we describe openly acknowledges the existence of many libraries. A single concept such as Stack is expressed in subtly different ways in each library; these differences are made explicit for the student. We also show examples of assessment tasks that can accompany the teaching.

This paper presents a curriculum consisting of a collection of subjects to prepare students for a career in "software development" while remaining within the scope normal for a major in a broad liberal arts degree. We describe the principles behind the construction of the curriculum, and contrast it with the more extensive "Software Engineering Body of Knowledge" appropriate in a professional Engineering degree.

A common approach to designing fault-tolerant distributed systems is to use a view-oriented process group communication service as a building block. An application that uses such a service often operates by a simple algorithm (such as a replicated state machine) for the duration of a view, but whenever the view changes, a complicated calculation is used to reconfigure the system. This reconfiguration typically involves exchange of state and merging of information from previously partitioned views. In this paper, we show how to automate the design of the reconfiguration mechanism in certain simple cases, where the reconfiguration treats all previous views symmetrically.

Group communication services are becoming accepted as effective building blocks for the construction of fault-tolerant distributed applications. Many specifications for group communication services have been proposed. However, there is still no agreement about what these specifications should say, especially in cases where the services are partitionable , i.e., where communication failures may lead to simultaneous creation of groups with disjoint memberships, such that each group is unware of the existence of any other group. In this paper, we present a new, succinct specification for a view-oriented partitionable group communication service. The service associates each message with a particular view of the group membership. All send and receive events for a message occur within the associated view. The service provides a total order on the messages within each view, and each processor receives a prefix of this order. Our specification separates safety requirements from performance and fault-tolerance requirements. The safety requirements are expressed by an abstract, global state machine . To present the performance and fault-tolerance requirements, we include failure-status input actions in the specification; we then give properties saying that consensus on the view and timely message delivery are guaranteed in an execution provided that the execution stabilizes to a situation in which the failure-status stops changing and corresponds to consistently partioned system. Because consensus is not required in every execution, the specification is not subject to the existing impossibility results for partionable systems. Our specification has a simple implementation, based on the membership algorithm of Christian and Schmuck. We show the utility of the specification by constructing an ordered-broadcast application, using an algorithm (based on algorithms of Amir, Dolev, Keidar, and others) that reconciles information derived from different instantiations of the group. The application manages the view-change activity to build a shared sequence of messages, i.e., the per-view total orders of the group service are combined to give a universal total order. We prove the correctness and analyze the performance and fault-tolerance of the resulting application.

Educational theory suggests that student learning is enhanced when students pay attention to their own learning. In this paper, we describe a range of innovative techniques that we use to encourage students to reflect on the state of their knowledge, and on the process by which they acquire it. Examples include providing web-based arrangements for students to practice assessing material based on the criteria we use in marking, and allocating marks in assessment for reflective writing.

View-oriented group communication services are widely used for fault-tolerant distributed computing.For applications involving coherent data, it is importaut to know when a process has a primary view of the current group membership, usually defined as a view containing a majority out of a static universe of processes.For high availability in a system where processes can join and leave routinely, some researchers have suggested def?.ning primary views dynamically, depending on having enough members in common with recent views.We present a new formal automaton specification, DVS, for the safety guarantees made by a practical group communication service providing a dynamic notion of primary view.We demonstrate the value of DVS by showing both how it can be implemented and how it can be used in an application.First, we present a distributed algorithm based on a group membership algorithm of Lotem, Keidar and Dolev; our version integrates communication with the membership service, uses iuformation from the application processes saying when a view has been prepared for computation by the application, and uses a static view-oriented service internally.We prove that this algorithm implements DVS.Second, we present an application algorithm that is a variant of an algorithm of Amir, Dolev, Keidar, Melliar-Smith and Moser, modified to use DVS instead of a static service.We prove that it implements a (non-group-oriented) totally-orderedbroadcast service.

This paper presents and proves correct a distributed algorithm that implements a sequentially consistent collection of shared read/update objects. This algorithm is a generalization of one used in the Orca shared object system. The algorithm caches objects in the local memory of processors according to application needs; each read operation accesses a single copy of the object, while each update accesses all copies. The algorithm uses broadcast communication when it sends messages to replicated copies of an object, and it uses point-to-point communication when a message is sent to a single copy, and when a reply is returned. Copies of all objects are kept consistent using a strategy based on sequence numbers for broadcasts. The algorithm is presented in two layers. The lower layer uses the given broadcast and point-to-point communication services, plus sequence numbers, to provide a new communication service called acontext multicast channel. The higher layer uses a context multicast channel to manage the object replication in a consistent fashion. Both layers and their combination are described and verified formally, using the I/O automation model for asynchronous concurrent systems.

Group communication services are becoming accepted as effective building blocks for the construction of fault-tolerant distributed applications. Many specifications for group communication services have been proposed. However, there is still no agreement about what these specifications should say, especially in cases where the services are partitionable, i.e., where communication failures may lead to simultaneous creation of groups with disjoint memberships, such that each group is unware of the existence of any other group. In this paper, we present a new, succinct specification for a view-oriented partitionable group communication service. The service associates each message with a particular view of the group membership. All send and receive events for a message occur within the associated view. The service provides a total order on the messages within each view, and each processor receives a prefix of this order. Our specification separates safety requirements from performance and fault-tolerance requirements. The safety requirements are expressed by an abstract, global state machine. To present the performance and fault-tolerance requirements, we include failure-status input actions in the specification; we then give properties saying that consensus on the view and timely message delivery are guaranteed in an execution provided that the execution stabilizes to a situation in which the failure-status stops changing and corresponds to consistently partioned system. Because consensus is not required in every execution, the specification is not subject to the existing impossibility results for partionable systems. Our specification has a simple implementation, based on the membership algorithm of Christian and Schmuck. We show the utility of the specification by constructing an ordered-broadcast application, using an algorithm (based on algorithms of Amir, Dolev, Keidar, and others) that reconciles information derived from different instantiations of the group. The application manages the view-change activity to build a shared sequence of messages, i.e., the per-view total orders of the group service are combined to give a universal total order. We prove the correctness and analyze the performance and fault-tolerance of the resulting application.

We present a new specification for distributed data services that trade-off immediate consistency guarantees for improved system availability and efficiency, while ensuring the long-term consistency of the data.An eventually-serializable data service maintains the operations requested in a partial order that gravitates over time towards a total order.It provides clear and unambiguous guarantees about the immediate and long-term behavior of the system.To demonstrate its utility, we present an algorithm, based on one of Ladin, Liskov, Shrira, and Ghemawat [12], that implements this specification.Our algorithm provides the interface of the abstract service, and generalizes their algorithm by allowing general operations and greater flexibility in specifying consistency requirements.We also describe how to use this specification as a building block for applications such as directory services.1

Traditional curricula have concentrated on teaching students the content of a subject; however, it has recently become apparent that effective education needs to include explicit instruction in many of the auxiliary skills and attitudes needed for the content to be useful. This applies just as much at advanced levels as at introductory ones, though the impact on teaching practice is not yet widespread. This paper describes an innovative module taught to students who are about to commence research, in which these students are given explicit guidance on how to judge the work of others (or their own work). The module is provided to undergraduates intending to perform an "Honours" research project in their final year; however, the material would also be relevant to students in a graduate program or senior seminar.

A recent trend has been to accompany Computer Science courses by "closed laboratories" where students carried out tasks with supervision and guidance. This paper presents a methodology for designing a complete sequence of laboratories to support the instruction in a course. The design considers both the technical concepts to be conveyed and the learning experiences through which students learn. We demonstrate the way the methodology has been used to design the lab sequence for a Pascal-based CS1 course.

A distributed algorithm that implements a sequentially consistent collection of shared read/update objects using a combination of broadcast and point-to-point communication is presented and proved correct. This algorithm is a generalization of one used in the Orca shared object system. The algorithm caches objects in the local memory of processors according to application needs; each read operation accesses a single copy of the object, while each update accesses all copies. Copies of all the objects are kept consistent using a strategy based on sequence numbers for broadcasts. The algorithm is presented in two layers. The lower layer uses the given broadcast and point-to-point communication services, plus sequence numbers, to provide a new communication service called a context multicast channel. The higher layer uses a context multicast channel to manage the object replication in a consistent fashion. Both layers and their combination are described and verified formally, using the I/O automaton model for asynchronous concurrent systems.

Universities have always claimed that as well as educating students in particular content, they have “developed the students' minds”. A current trend is asking instructors to justify this claim, by ensuring that students have “generic skills” that are useful in all fields. Examples include communication skills, flexibility to apply their understanding to new situations as they arise, problem-solving skills, ability to transfer concepts between domains, and capacity to evaluate alternatives and provide reasoned explanations for their choices. This paper describes a course which covers most of the material from a typical computer organization or systems programming course, but uses closed laboratories in ways that enhance the students' generic skills as well as their expertise in the technical material.

Many different formal methods provide mathematical models of reactive systems (those that interact with an environment to provide a service).There is disagreement on many details, but many methods use the transition

Layered communicationprotocols frequently implement a FIFO message fiacility cm top of an unrehable non-FIFO serwce such as that provided hy a packet-swltchmg network.This paper investigates the possibdity of Implementing a reliable message layer on top of an underlying layer that can low packets and deliver them out of order, with the addltlonzd restriction that the implementatmn uses only a fixed fimte number of different packets.A new formalism is presented to spcclfy communication layers and their properties, the notion of their implementation by 1/0 automata.and the properties of such implementations.An 1/0 automaton that Implements a rellable layer over an unreliable layer is presented In this implementation, tbe number ot packets needed to deliver each succeeding message increases permanently as additional packet-loss and reordering faults occur.A proof is gwen that no protocol can avoid such performance degradatmn.

article Free Access Share on Reasoning about programs: integrating verification and analysis of algorithms into the introductory programming course Author: Alan Fekete Department of Computer Science, University of Sydney, 2006, Australia Department of Computer Science, University of Sydney, 2006, AustraliaView Profile Authors Info & Claims ACM SIGCSE BulletinVolume 25Issue 1March 1993 pp 198–202https://doi.org/10.1145/169073.169410Online:01 March 1993Publication History 3citation105DownloadsMetricsTotal Citations3Total Downloads105Last 12 Months10Last 6 weeks4 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

An important function of communication networks is to implement reliable data transfer over an unreliable underlying network.Formal specifications are given for reliable and unreliable communication layers, in terms of 1/0 automata.Based on these specifications, it is proved that no reliable communication protocol can tolerate crashes of the processors on which the protocol runs.

This paper makes three contributions. First, we present a proof technique that offers system designers the same ease of reasoning about nested transaction systems as is given by the classical theory for systems without nesting, and yet can be used to verify that a system satisfies the robust “user view” definition of correctness of [10]. Second, as applications of the technique, we verify the correctness of Moss' read/write locking algorithm for nested transactions, and of an undo logging algorithm that has not previously been presented or proved for nested transaction systems. Third, we make explicit the assumptions used for this proof technique, assumptions that are usually made implicitly in the classical theory, and therefore we clarify the type of system for which the classical theory itself can reliably be used.

Article Free Access Share on Data link layer: two impossibility results Authors: Nancy A. Lynch Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MAView Profile , Yishay Mansour Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MAView Profile , Alan Fekete Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MAView Profile Authors Info & Claims PODC '88: Proceedings of the seventh annual ACM Symposium on Principles of distributed computingJanuary 1988 Pages 149–170https://doi.org/10.1145/62546.62572Published:01 January 1988Publication History 21citation530DownloadsMetricsTotal Citations21Total Downloads530Last 12 Months95Last 6 weeks8 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

Article Asynchronous approximate agreement Share on Author: A. D. Fekete Department of Mathematics, Harvard University, Cambridge, MA Department of Mathematics, Harvard University, Cambridge, MAView Profile Authors Info & Claims PODC '87: Proceedings of the sixth annual ACM Symposium on Principles of distributed computingDecember 1987 Pages 64–76https://doi.org/10.1145/41840.41846Online:01 December 1987Publication History 10citation282DownloadsMetricsTotal Citations10Total Downloads282Last 12 Months5Last 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

We give a clear yet rigorous correctness proof for Moss's algorithm for managing data in a nested transaction system. The algorithm, which is the basis of concurrency control and recovery in the Argus system, uses read- and write-locks and a stack of versions of each object to ensure the serializability and recoverability of transactions accessing the data. Our proof extends earlier work on exclusive locking to prove that Moss's algorithm generates serially correct executions in the presence of concurrency and transaction aborts. The key contribution is the identification of a simple property of cead operations, called transparency, that permits shared locks to be used for read operations.

Article Asymptotically optimal algorithms for approximate agreement Share on Author: A D Fekete Department of Mathematics, Harvard University, Cambridge, MA Department of Mathematics, Harvard University, Cambridge, MAView Profile Authors Info & Claims PODC '86: Proceedings of the fifth annual ACM symposium on Principles of distributed computingNovember 1986 Pages 73–87https://doi.org/10.1145/10590.10597Online:01 November 1986Publication History 27citation476DownloadsMetricsTotal Citations27Total Downloads476Last 12 Months10Last 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