Computer Science is a wonderful field with many interesting and important problems to work on. This is true today and was also true in the past; of course what is considered interesting changes as a field matures. In this talk I will discuss some of the problems that I found intriguing. In each case I will discuss the state of the field at the time I did this work to provide an historical context for my work and that of others doing related work. I will also discuss how I selected problems, what I brought to the table, and where the ideas for my solutions came from.

Abstract Modern distributed data management systems face a new challenge: how can autonomous, mutually distrusting parties cooperate safely and effectively? Addressing this challenge brings up familiar questions from classical distributed systems: how to combine multiple steps into a single atomic action, how to recover from failures, and how to synchronize concurrent access to data. Nevertheless, each of these issues requires rethinking when participants are autonomous and potentially adversarial. We propose the notion of a cross-chain deal, a new way to structure complex distributed computations that manage assets in an adversarial setting. Deals are inspired by classical atomic transactions, but are necessarily different, in important ways, to accommodate the decentralized and untrusting nature of the exchange. We describe novel safety and liveness properties, along with two alternative protocols for implementing cross-chain deals in a system of independent blockchain ledgers. One protocol, based on synchronous communication, is fully decentralized, while the other, based on semi-synchronous communication, requires a globally shared ledger. We also prove that some degree of centralization is required in the semi-synchronous communication model.

Optimistic concurrency control, or OCC, can achieve excellent performance on uncontended workloads for main-memory transactional databases. Contention causes OCC's performance to degrade, however, and recent concurrency control designs, such as hybrid OCC/locking systems and variations on multiversion concurrency control (MVCC), have claimed to outperform the best OCC systems. We evaluate several concurrency control designs under varying contention and varying workloads, including TPCC, and find that implementation choices unrelated to concurrency control may explain much of OCC's previously-reported degradation. When these implementation choices are made sensibly, OCC performance does not collapse on high-contention TPC-C. We also present two optimization techniques, commit-time updates and timestamp splitting , that can dramatically improve the high-contention performance of both OCC and MVCC. Though these techniques are known, we apply them in a new context and highlight their potency: when combined, they lead to performance gains of 3.4X for MVCC and 3.6X for OCC in a TPC-C workload.

This talk describes a new approach to implementing efficient concurrent programs that run on multicore computers. The approach is inspired by work on software transactional memory, and like that work aims to make it easier to write correct concurrent programs through the use of atomic transactions. A conventional STM tracks reads and writes of memory words, which can lead to high overhead. Our approach, called STO (software transactional objects), is based on data abstraction instead. Implementations of transactionaware datatypes can take advantage of datatype semantics to reduce bookkeeping, limit false conficts, and implement efficient concurrency control. This way we can provide both good performance and correctness based on modularity and encapsulation.

Modern distributed data management systems face a new challenge: how can autonomous, mutually-distrusting parties cooperate safely and effectively? Addressing this challenge brings up questions familiar from classical distributed systems: how to combine multiple steps into a single atomic action, how to recover from failures, and how to synchronize concurrent access to data. Nevertheless, each of these issues requires rethinking when participants are autonomous and potentially adversarial. We propose the notion of a cross-chain deal , a new way to structure complex distributed computations that manage assets in an adversarial setting. Deals are inspired by classical atomic transactions, but are necessarily different, in important ways, to accommodate the decentralized and untrusting nature of the exchange. We describe novel safety and liveness properties, along with two alternative protocols for implementing cross-chain deals in a system of independent blockchain ledgers. One protocol, based on synchronous communication, is fully decentralized, while the other, based on semi-synchronous communication, requires a globally shared ledger.

It is often possible to improve a concurrent system's performance by leveraging the semantics of its datatypes. We build a new software transactional memory (STM) around this observation. A conventional STM tracks read- and write-sets of memory words; even simple operations can generate large sets. Our STM, which we call STO, tracks abstract operations on transactional datatypes instead. Parts of the transactional commit protocol are delegated to these datatypes' implementations, which can use datatype semantics, and new commit protocol features, to reduce bookkeeping, limit false conflicts, and implement efficient concurrency control. We test these ideas on the STAMP benchmark suite for STM applications and on our own prior work, the Silo high-performance in-memory database, observing large performance improvements in both systems.

Unhandled exceptions crash programs, so a compile-time check that exceptions are handled should in principle make software more reliable. But designers of some recent languages have argued that the benefits of statically checked exceptions are not worth the costs. We introduce a new statically checked exception mechanism that addresses the problems with existing checked-exception mechanisms. In particular, it interacts well with higher-order functions and other design patterns. The key insight is that whether an exception should be treated as a "checked" exception is not a property of its type but rather of the context in which the exception propagates. Statically checked exceptions can "tunnel" through code that is oblivious to their presence, but the type system nevertheless checks that these exceptions are handled. Further, exceptions can be tunneled without being accidentally caught, by expanding the space of exception identifiers to identify the exception-handling context. The resulting mechanism is expressive and syntactically light, and can be implemented efficiently. We demonstrate the expressiveness of the mechanism using significant codebases and evaluate its performance. We have implemented this new exception mechanism as part of the new Genus programming language, but the mechanism could equally well be applied to other programming languages.

The support for generic programming in modern object-oriented programming languages is awkward and lacks desirable expressive power. We introduce an expressive genericity mechanism that adds expressive power and strengthens static checking, while remaining lightweight and simple in common use cases. Like type classes and concepts, the mechanism allows existing types to model type constraints retroactively. For expressive power, we expose models as named constructs that can be defined and selected explicitly to witness constraints; in common uses of genericity, however, types implicitly witness constraints without additional programmer effort. Models are integrated into the object-oriented style, with features like model generics, model-dependent types, model enrichment, model multimethods, constraint entailment, model inheritance, and existential quantification further extending expressive power in an object-oriented setting. We introduce the new genericity features and show that common generic programming idioms, including current generic libraries, can be expressed more precisely and concisely. The static semantics of the mechanism and a proof of a key decidability property can be found in an associated technical report.

Numerous sensitive databases are breached every year due to bugs in applications. These applications typically handle data for many users, and consequently, they have access to large amounts of confidential information.

Silo is a new in-memory database that achieves excellent performance and scalability on modern multicore machines. Silo was designed from the ground up to use system memory and caches efficiently. For instance, it avoids all centralized contention points, including that of centralized transaction ID assignment. Silo's key contribution is a commit protocol based on optimistic concurrency control that provides serializability while avoiding all shared-memory writes for records that were only read. Though this might seem to complicate the enforcement of a serial order, correct logging and recovery is provided by linking periodically-updated epochs with the commit protocol. Silo provides the same guarantees as any serializable database without unnecessary scalability bottlenecks or much additional latency. Silo achieves almost 700,000 transactions per second on a standard TPC-C workload mix on a 32-core machine, as well as near-linear scalability. Considered per core, this is several times higher than previously reported results.

Byzantine-fault-tolerant replication enhances the availability and reliability of Internet services that store critical state and preserve it despite attacks or software errors. However, existing Byzantine-fault-tolerant storage systems either assume a static set of replicas, or have limitations in how they handle reconfigurations (e.g., in terms of the scalability of the solutions or the consistency levels they provide). This can be problematic in long-lived, large-scale systems where system membership is likely to change during the system lifetime. In this paper, we present a complete solution for dynamically changing system membership in a large-scale Byzantine-fault-tolerant system. We present a service that tracks system membership and periodically notifies other system nodes of membership changes. The membership service runs mostly automatically, to avoid human configuration errors; is itself Byzantine-fault-tolerant and reconfigurable; and provides applications with a sequence of consistent views of the system membership. We demonstrate the utility of this membership service by using it in a novel distributed hash table called dBQS that provides atomic semantics even across changes in replica sets. dBQS is interesting in its own right because its storage algorithms extend existing Byzantine quorum protocols to handle changes in the replica set, and because it differs from previous DHTs by providing Byzantine fault tolerance and offering strong semantics. We implemented the membership service and dBQS. Our results show that the approach works well, in practice: the membership service is able to manage a large system and the cost to change the system membership is low.

This article describes MPSS, a new way to do proactive secret sharing. MPSS provides mobility : The group of nodes holding the shares of the secret can change at each resharing, which is essential in a long-lived system. MPSS additionally allows the number of tolerated faulty shareholders to change when the secret is moved so that the system can tolerate more (or fewer) corruptions; this allows reconfiguration on-the-fly to accommodate changes in the environment. MPSS includes an efficient protocol that is intended to be used in practice. The protocol is optimized for the common case of no or few failures, but degradation when there are more failures is modest. MPSS contains a step in which nodes accuse proposals made by other nodes; we show a novel way to handle these accusations when their verity cannot be known. We also present a way to produce accusations that can be verified without releasing keys of other nodes; verifiable accusations improve the performance of MPSS, and are a useful primitive independent of MPSS.

Most peer-to-peer lookup schemes keep a small amount of routing state per node, typically logarithmic in the number of overlay nodes. This design assumes that routing information at each member node must be kept small so that the bookkeeping required to respond to system membership changes is also small, given that aggressive membership dynamics are expected. As a consequence, lookups have high latency as each lookup requires contacting several nodes in sequence. In this paper, we question these assumptions by presenting a peer-to-peer routing algorithm with small lookup paths. Our algorithm, called ldquoOneHop,rdquo maintains full information about the system membership at each node, routing in a single hop whenever that information is up to date and in a small number of hops otherwise. We show how to disseminate information about membership changes quickly enough so that nodes maintain accurate complete membership information. We also present analytic bandwidth requirements for our scheme that demonstrate that it could be deployed in systems with hundreds of thousands of nodes and high churn. We validate our analytic model using a simulated environment and a real implementation. Our results confirm that OneHop is able to achieve high efficiency, usually reaching the correct node directly 99 percent of the time.

MPSS is a new way to do proactive secret sharing in asynchronous networks. MPSS provides mobility: The group of nodes holding the shares of the secret can change at each resharing, which is essential in a long-lived system. MPSS additionally allows the number of tolerated faulty shareholders to change when the secret is moved so that the system can tolerate more (or fewer) corruptions; this allows reconfiguration on the fly to accommodate changes in the environment.

We present a new approach for generating virtual coordinates that produces usable coordinates quickly and improves the routing performance of existing geographic routing algorithms. Starting from a set of initial coordinates derived from a set of elected perimeter nodes, greedy embedding spring coordinates (GSpring) detects possible dead ends and uses a modified spring relaxation algorithm to incrementally adjust virtual coordinates to increase the convexity of voids in the virtual routing topology. This reduces the probability that packets will end up in dead ends during greedy forwarding. The coordinates derived by GSpring achieve routing stretch that is up to 50% lower than that for NoGeo, the best existing algorithm for deriving virtual Euclidean coordinates for geographic routing. For realistic network topologies with obstacles, GSpring coordinates achieves from between 10 to 15% better routing stretch than actual physical coordinates.

This paper describes the design, implementation, and evaluation of areplication scheme to handle Byzantine faults in transaction processing database systems. The scheme compares answers from queries and updates on multiple replicas which are unmodified, off-the-shelf systems, to provide a single database that is Byzantine fault tolerant. The scheme works when the replicas are homogeneous, but it also allows heterogeneous replication in which replicas come from different vendors. Heterogeneous replicas reduce the impact of bugs and security compromises because they are implemented independently and are thus less likely to suffer correlated failures.

Byzantine quorum systems have been proposed that work properly even when up to f replicas fail arbitrarily. However, these systems are not so successful when confronted with Byzantine faulty clients. This paper presents novel protocols that provide atomic semantics despite Byzantine clients. Our protocols prevent Byzantine clients from interfering with good clients: bad clients cannot prevent good clients from completing reads and writes, and they cannot cause good clients to see inconsistencies. In addition we also prevent bad clients that have been removed from operation from leaving behind more than a bounded number of writes that could be done on their behalf by a colluder. Our protocols are designed to work in an asynchronous system like the Internet and they are highly efficient. We require 3f +1 replicas, and either two or three phases to do writes; reads normally complete in one phase and require no more than two phases, no matter what the bad clients are doing. We also present strong correctness conditions for systems with Byzantine clients that limit what can be done on behalf of bad clients once they leave the system. Furthermore we prove that our protocols are both safe (they meet those conditions) and live.

Existing geographic routing algorithms depend on the planarization of the network connectivity graph for correctness, and the planarization process gives rise to a well-defined notion of "faces". In this paper, we demonstrate that we can improve routing performance by storing a small amount of local face information at each node. We present a protocol, path vector exchange (PVEX), that maintains local face information at each node efficiently, and a new geographic routing algorithm, greedy path vector face routing (GPVFR), that achieves better routing performance in terms of both path stretch and hop stretch than existing geographic routing algorithms by exploiting available local face information. Our simulations demonstrate that GPVFR/PVEX achieves significantly reduced path and hop stretch than greedy perimeter stateless routing (GPSR) and somewhat better performance than greedy other adaptive face routing (GOAFR+) over a wide range of network topologies. The cost of this improved performance is a small amount of additional storage, and the bandwidth required for our algorithm is comparable to GPSR and GOAFR+ in quasi-static networks.

No abstract available.

Persistent object stores require a way to automatically upgrade persistent objects. Automatic upgrades are a challenge for such systems. Upgrades must be performed in a way that is efficient both in space and time, and that does not stop application access to the store. In addition, however, the approach must be modular: it must allow programmers to reason locally about the correctness of their upgrades similar to the way they would reason about regular code. This paper provides solutions to both problems. The paper first defines upgrade modularity conditions that any upgrade system must satisfy to support local reasoning about upgrades. The paper then describes a new approach for executing upgrades efficiently while satisfying the upgrade modularity conditions. The approach exploits object encapsulation properties in a novel way. The paper also describes a prototype implementation and shows that our upgrade system imposes only a small overhead on application performance.

Ownership types provide a statically enforceable way of specifying object encapsulation and enable local reasoning about program correctness in object-oriented languages. However, a type system that enforces strict object encapsulation is too constraining: it does not allow efficient implementation of important constructs like iterators. This paper argues that the right way to solve the problem is to allow objects of classes defined in the same module to have privileged access to each other's representations; we show how to do this for inner classes. This approach allows programmers to express constructs like iterators and yet supports local reasoning about the correctness of the classes, because a class and its inner classes together can be reasoned about as a module. The paper also sketches how we use our variant of ownership types to enable efficient software upgrades in persistent object stores.

Software errors are a major cause of outages and they are increasingly exploited in malicious attacks. Byzantine fault tolerance allows replicated systems to mask some software errors but it is expensive to deploy. This paper describes a replication technique, BASE, which uses abstraction to reduce the cost of Byzantine fault tolerance and to improve its ability to mask software errors. BASE reduces cost because it enables reuse of off-the-shelf service implementations. It improves availability because each replica can be repaired periodically using an abstract view of the state stored by correct replicas, and because each replica can run distinct or nondeterministic service implementations, which reduces the probability of common mode failures. We built an NFS service where each replica can run a different off-the-shelf file system implementation, and an object-oriented database where the replicas ran the same, nondeterministic implementation. These examples suggest that our technique can be used in practice---in both cases, the implementation required only a modest amount of new code, and our performance results indicate that the replicated services perform comparably to the implementations that they reuse.

Our growing reliance on online services accessible on the Internet demands highly available systems that provide correct service without interruptions. Software bugs, operator mistakes, and malicious attacks are a major cause of service interruptions and they can cause arbitrary behavior, that is, Byzantine faults. This article describes a new replication algorithm, BFT, that can be used to build highly available systems that tolerate Byzantine faults. BFT can be used in practice to implement real services: it performs well, it is safe in asynchronous environments such as the Internet, it incorporates mechanisms to defend against Byzantine-faulty clients, and it recovers replicas proactively. The recovery mechanism allows the algorithm to tolerate any number of faults over the lifetime of the system provided fewer than 1/3 of the replicas become faulty within a small window of vulnerability. BFT has been implemented as a generic program library with a simple interface. We used the library to implement the first Byzantine-fault-tolerant NFS file system, BFS. The BFT library and BFS perform well because the library incorporates several important optimizations, the most important of which is the use of symmetric cryptography to authenticate messages. The performance results show that BFS performs 2% faster to 24% slower than production implementations of the NFS protocol that are not replicated. This supports our claim that the BFT library can be used to build practical systems that tolerate Byzantine faults.

Byzantine fault tolerance is important because it can be used to implement highly-available systems that tolerate arbitrary behavior from faulty components. We present a detailed performance evaluation of BFT, a state-machine replication algorithm that tolerates Byzantine faults in asynchronous systems. Our results contradict the common belief that Byzantine fault tolerance is too slow to be used in practice, BFT performs well so that it can be used to implement real systems. We implemented a replicated NFS file system using BFT that performs 2% faster to 24% slower than production implementations of the NFS protocol that are not fault-tolerant.

Software errors are a major cause of outages and they are increasingly exploited in malicious attacks. Byzantine fault tolerance allows replicated systems to mask some software errors but it is expensive to deploy. The paper describes a replication technique, BFTA, which uses abstraction to reduce the cost of Byzantine fault tolerance and to improve its ability to mask software errors. BFTA reduces cost because it enables reuse of off-the-shelf service implementations. It improves availability because each replica can be repaired periodically using an abstract view of the state stored by correct replicas, and because each replica can run distinct or non-deterministic service implementations, which reduces the probability of common mode failures. We built an NFS service that allows each replica to run a different operating system. This example suggests that BFTA can be used in practice; the replicated file system required only a modest amount of new code, and preliminary performance results indicate that it performs comparably to the off-the-shelf implementations that it wraps.

Software errors are a major cause of outages and they are increasingly exploited in malicious attacks. Byzantine fault tolerance allows replicated systems to mask some software errors but it is expensive to deploy. This paper describes a replication technique, BASE, which uses abstraction to reduce the cost of Byzantine fault tolerance and to improve its ability to mask software errors. BASE reduces cost because it enables reuse of off-the-shelf service implementations. It improves availability because each replica can be repaired periodically using an abstract view of the state stored by correct replicas, and because each replica can run distinct or non-deterministic service implementations, which reduces the probability of common mode failures. We built an NFS service where each replica can run a different off-the-shelf file system implementation, and an object-oriented database where the replicas ran the same, non-deterministic implementation. These examples suggest that our technique can be used in practice --- in both cases, the implementation required only a modest amount of new code, and our performance results indicate that the replicated services perform comparably to the implementations that they reuse.

Commercial databases support different isolation levels to allow programmers to trade off consistency for a potential gain in performance. The isolation levels are defined in the current ANSI standard, but the definitions are ambiguous and revised definitions proposed to correct the problem are too constrained since they allow only pessimistic (locking) implementations. This paper presents new specifications for the ANSI levels. Our specifications are portable: they apply not only to locking implementations, but also to optimistic and multi-version concurrency control schemes. Furthermore, unlike earlier definitions, our new specifications handle predicates in a correct and flexible manner at all levels.

Stronger protection is needed for the confidentiality and integrity of data, because programs containing untrusted code are the rule rather than the exception. Information flow control allows the enforcement of end-to-end security policies, but has been difficult to put into practice. This article describes the decentralized label model, a new label model for control of information flow in systems with mutual distrust and decentralized authority. The model improves on existing multilevel security models by allowing users to declassify information in a decentralized way, and by improving support for fine-grained data sharing. It supports static program analysis of information flow, so that programs can be certified to permit only acceptable information flows, while largely avoiding the overhead of run-time checking. The article introduces the language Jif, an extension to Java that provides static checking of information flow using the decentralized label model.

The growing use of mobile code in downloaded applications and servlets has increased interest in robust mechanisms for ensuring privacy and secrecy. Information flow control is intended to directly address privacy and secrecy concerns, but most information flow models are too restrictive to be widely used. The decentralized label model is a new information flow model that extends traditional models with per-principal information flow policies and also permits a safe form of declassification. This paper extends this new model further, making it more flexible and expressive. We define a new formal semantics for decentralized labels and a corresponding new rule for relabeling data that is both sound and complete. We also show that these extensions preserve the ability to statically check information flow.

Cooperative caching is a promising technique to avoid the increasingly formidable disk bottleneck problem in distributed storage systems; it reduces the number of disk accesses by servicing client cache misses from the caches of other clients. However, existing cooperative caching techniques do not provide adequate support for fine grained sharing. We describe a new storage system architecture, split caching, and a new cache coherence protocol, fragment reconstruction, that combine cooperative caching with efficient support for fine grained sharing and transactions. We also present the results of performance studies that show that our scheme introduces little overhead over the basic cooperative caching mechanism and provides better performance when there is fine grained sharing.

This paper describes a new scheme for guaranteeing that transactions in a clientlserver system observe consistent state while they are running.Thescheme ispresented inconjunction with at'toptimistic concurrency control algorithm, but could also be used to prevent read-only transactions from conflicting with read/write transactions in a multi-version system.The scheme is lazy about the consistency it provides forruming transactions and also in the way it generates theconsistency information.Thepaper presents results of simulation experiments showing that the cost of the scheme is negligible.The scheme uses multipart timestamps to inform nodes about information they need to know.Today the utility of such schemes is limited beeause timestamp size is proportional to system size and therefore the schemes don't scale to very large systems.We show how to solve this problem.Our multipart timestamps are based on real rather thm logical clocks; we assume clocks in the system are loosely synchronized.Clocks allow us to keep multipart timestamps small with minimal impact on performance: we remove old information that is likely to be known while retaining recent information.Only performance and not correctness is affected if clocks get out of synch.

Systems that store objects at a large number of sites require fault-tolerant and timely garbage collection. A popular technique is to trace each site independently using inter-site references as roots. However, this fails to collect cyclic garbage spread across sites. We present an algorithm that collects cyclic garbage by involving only the sites containing it. Our algorithm is based on finding objects highly likely to be cyclic garbage and tracing backward from them to check if they are reachable from any root. We present efficient techniques that make conducting such traces practical. The algorithm collects all distributed cyclic garbage, is safe in the presence of concurrent mutations, and has low space and time overhead. 1 Introduction Emerging distributed systems will use objects stored at a large number of sites. The scale of such systems poses new challenges to reclaiming the storage of objects unreachable by applications. Such objects are known as garbage. A simple way to col...

Java offers the real possibility that most programs can be written in a type-safe language. However, for Java to be broadly useful, it needs additional expressive power. This paper extends Java in one area where more power is needed: support for parametric polymorphism, which allows the definition and implementation of generic abstractions. We discuss both the rationale for our design decisions and the impact of the extension on other parts of Java, including arrays and the class library. We also describe optional extensions to the Java virtual machine to allow parameterized bytecodes, and how to verify them efficiently. We have extended the Java bytecode interpreter to provide good performance for parameterized code in both execution speed and code size, without slowing down non-parameterized code.

We present new techniques for efficient garbage collection in a large persistent object store. The store is divided into partitions that are collected independently using information about inter-partition references. This information is maintained on disk so that it can be recovered after a crash. We use new techniques to organize and update this information while avoiding disk accesses. We also present a new global marking scheme to collect cyclic garbage across partitions. Global marking is piggybacked on partitioned collection; the result is an efficient scheme that preserves the localized nature of partitioned collection, yet is able to collect all garbage.

This paper presents HAC, a novel technique for managing the client cache in a distributed, persistent object storage system.I-k2 is a hybrid between page and object caching that combines the virtues of both while avoiding their disadvantages.,It achieves the low miss penalties of a page-caching system, but is able to perform well even when locality is poor, since it can discard pages while retaining their hot objects.It realizes the potentially lower miss rates of object-caching systems, yet avoids their problems of fragmentation and high overheads.Furthermore, HAC is adaptive: when locality is good it behaves like a page-caching system, while if locality is poor it behaves like an object-caching system.It is able to adjust the amount of cache space devoted to pages dynamically so that space in the cache can be used in the way that Fcst matches tbe needs of the application.The paper also presents results of experiments that indicate that HAC outperforms other object storage systems across a wide range of cache sizes and workloads; it performs substantially better on the expected workloads, which have low to moderate locality.Thus we show that our hybrid, adaptive approach is the cache management technique of choice for distributed, persistent object systems.This research was supported in

This paper presents a new model for controlling information flow in systems with mutual distrust and decentralized authority.The model allows users to share information with distrusted code (e.g., downloaded applets), yet still control how that code disseminates the shared information to others.The model improves on existing multilevel security models by allowing users to declassify information in a decentralized way, and by improving support for fine-grained data sharing.The paper also shows how static program analysis can be used to certify proper information flows in this model and to avoid most run-time information flow checks.

Thor is an object-oriented database system designed for use in a heterogeneous distributed environment. It provides highly-reliable and highly-available persistent storage for objects, and supports safe sharing of these objects by applications written in different programming languages.Safe heterogeneous sharing of long-lived objects requires encapsulation: the system must guarantee that applications interact with objects only by invoking methods. Although safety concerns are important, most object-oriented databases forgo safety to avoid paying the associated performance costs.This paper gives an overview of Thor's design and implementation. We focus on two areas that set Thor apart from other object-oriented databases. First, we discuss safe sharing and techniques for ensuring it; we also discuss ways of improving application performance without sacrificing safety. Second, we describe our approach to cache management at client machines, including a novel adaptive prefetching strategy.The paper presents performance results for Thor, on several OO7 benchmark traversals. The results show that adaptive prefetching is very effective, improving both the elapsed time of traversals and the amount of space used in the client cache. The results also show that the cost of safe sharing can be negligible; thus it is possible to have both safety and high performance.

All object-oriented languages provide support for subtype polymorphism, which allows the writing of generic code that works for families of related types. There is also a need, however, to write code that is generic across types that have no real family relationship. To satisfy this need a programming language must provide a mechanism for parametric polymorphism, allowing for types as parameters to routines and types. We show that to support modular programming and separate compilation there must be a mechanism for constraining the actual parameters of the routine or type. We describe a simple and powerful constraint mechanism and compare it with constraint mechanisms in other languages in terms of both ease of use and semantic expressiveness. We also discuss the interaction between subtype and parametric polymorphism: we discuss the subtype relations that can exist between instantiations of parameterized types, and which of those relations are useful and can be implemented efficiently. We illustrate our points using examples in Theta, a new object-oriented language, and we describe the time- and space-efficient implementation of parametric polymorphism used in Theta.

Distributedreference counting provides timely and fault-tolerant 'garbage collection in large distributed systems, but it fails to collect cyclic garbage distributed across nodes.A common proposal is to migrate all objects on a garbage cycle to a single node, where they can be collected by the local collector.However, existing schemes have practical problems due to umecessary migration of objects.We present solutions to these problems: our scheme avoids migration of live objects, batches objects to avoid a cascade of migration messages, and short-cuts the migration path to avoid multiple migrations.We use simple estimates to detect objects that are highly likely to be cyclic garbage and to select a node to which such objects are migrated.The scheme has low overhead, and it preserves the decentralized and fault-tolerant nature of distributed reference counting and migration.

This paper describes an efficient optimistic concurrency control scheme for use in distributed database systems in which objects are cached and manipulated at client machines while persistent storage and transactional support are provided by servers. The scheme provides both serializability and external consistency for committed transactions; it uses loosely synchronized clocks to achieve global serialization. It stores only a single version of each object, and avoids maintaining any concurrency control information on a per-object basis; instead, it tracks recent invalidations on a per-client basis, an approach that has low in-memory space overhead and no per-object disk overhead. In addition to its low space overheads, the scheme also performs well. The paper presents a simulation study that compares the scheme to adaptive callback locking, the best concurrency control scheme for client-server object-oriented database systems studied to date. The study shows that our scheme outperforms adaptive callback locking for low to moderate contention workloads, and scales better with the number of clients. For high contention workloads, optimism can result in a high abort rate; the scheme presented here is a first step toward a hybrid scheme that we expect to perform well across the full range of workloads.

No abstract available.

In many systems such as operating systems and databases it is important to run client code in a separate protection domain so that it cannot interfere with correct operation of the system. Clients communicate with the server by making cross domain calls, but these are expensive, often costing substantially more than running the call itself. This paper describes a new mechanism called batched futures that transparently batches possibly interrelated client calls. Batching makes domain crossings happen less often, thus substantially reducing the cost. We describe how the mechanism is implemented for the Thor object-oriented database system, and presents performance results showing the benefit of the mechanism on various benchmarks.

The use of hierarchy is an important component of object-oriented design. Hierarchy allows the use of type families, in which higher level supertypes capture the behavior that all of their subtypes have in common. For this methodology to be effective, it is necessary to have a clear understanding of how subtypes and supertypes are related. This paper takes the position that the relationship should ensure that any property proved about supertype objects also holds for its subtype objects. It presents two ways of defining the subtype relation, each of which meets this criterion, and each of which is easy for programmers to use. The subtype relation is based on the specifications of the sub- and supertypes; the paper presents a way of specifying types that makes it convenient to define the subtype relation. The paper also discusses the ramifications of this notion of subtyping on the design of type families.

Specifications are useful because they allow reasoning about objects without concern for their implementations.Type hierarchies are useful because they allow types that share common properties to be designed as a family.This paper is concerned with the interaction between specifications and type hierarchies.We present a way of specifying types, and show how some extra information, in addition to specifications of the objects' methods, is needed to support reasoning.We also provide a new way of showing that one type is a subtype of another.Our technique makes use of information in the types' specifications and works even in a very general computational environment in which possibly concurrent users share mutable objects.

A practical, fault-tolerant method for reclaiming inaccessible objects in a distributed heap is presented. The algorithm is general and does not require homogeneous components. It reclaims inaccessible objects in a timely fashion, including those that reside on inaccessible cycles. It allows each computer that contains parts of the heap to garbage collect independently according to its storage requirements, using whatever algorithm it chooses. A highly available service is used to store information about the intercomputer references. The computers containing parts of the heap communicate with the central service only periodically. By using the service the overhead at each node is minimized.>

To provide high availability for services such as mail or bulletin boards, data must be replicated. One way to guarantee consistency of replicated data is to force service operations to occur in the same order at all sites, but this approach is expensive. For some applications a weaker causal operation order can preserve consistency while providing better performance. This paper describes a new way of implementing causal operations. Our technique also supports two other kinds of operations: operations that are totally ordered with respect to one another and operations that are totally ordered with respect to all other operations. The method performs well in terms of response time, operation-processing capacity, amount of stored state, and number and size of messages; it does better than replication methods based on reliable multicast techniques.

Article Practical uses of synchronized clocks in distributed systems Share on Author: Barbara Liskov MIT Laboratory for Computer Science, Cambridge, MA MIT Laboratory for Computer Science, Cambridge, MAView Profile Authors Info & Claims PODC '91: Proceedings of the tenth annual ACM symposium on Principles of distributed computingJuly 1991 Pages 1–9https://doi.org/10.1145/112600.112601Online:01 July 1991Publication History 41citation1,440DownloadsMetricsTotal Citations41Total Downloads1,440Last 12 Months100Last 6 weeks10 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

This paper describes the design and implementation of the Harp file system. Harp is a replicated Unix file system accessible via the VFS interface. It provides highly available and reliable storage for files and guarantees that file operations are executed atomically in spite of concurrency and failures. It uses a novel variation of the primary copy replication technique that provides good performance because it allows us to trade disk accesses for network communication. Harp is intended to be used within a file service in a distributed network; in our current implementation, it is accessed via NFS. Preliminary performance results indicate that Harp provides equal or better response time and system capacity than an unreplicated implementation of NFS that uses Unix files directly.

This paper describes a new at-most-once message passing protocol that provides guaranteed detection of duplicate messages even when the receiver has no state stored for the sender. It also discusses how to use at-most-once messages to implement higher-level primitives such as at-once-remote procedure calls and sequenced bytestream protocols. Our performance measurements indicate that at-most-once RPCs can provide at the same cost as less desirable forms of RPCs that do not guarantee at-most-once execution. Our method is based on the assumption that clocks throughout the system are loosely synchronized. Modern clock synchronization protocols provide good bounds on clock skew with high probability; our method depends on the bound for performance but not for correctness.

To provide high availability for services such as mail or bulletin boards, data must be replicated.One way to guarantee consistency of replicated data is to force service operations to occur in the same order at all sites, but this approach is expensive.In this paper, we propose lazy replication as a way to preserve consistency by exploiting the semantics of the service's operations to relax the constraints on ordering.Three kinds of operations are supported: operations for which the clients define the required order dynamically during the execution.operations for which the service defines the order, and operations that must be globally ordered with respect to both client ordered and service ordered operations.The method performs well in terms of response time, amount of stored state, number of messages, and availability.It is especially well suited to applications in which most operations require only the client-defined order.

This paper describes a new message passing protocol that provides guaranteed detection of duplicate messages even when the receiver has no state stored for the sender. It also discusses how to use these messages to implement higher-level primitives such as at-most-once remote procedure calls and sequenced bytestream protocols, and describes an implementation of at-most-once RPCs using our method. Our performance measurements indicate that at-most-once RPCs can be provided at the same cost as less desirable RPCs that do not guarantee at-most-once execution. Our method is based on the assumption that clocks throughout the system are loosely synchronized. Modern clock synchronization protocols provide good bounds on clock skew with high probability; our method depends on the bound for performance but not for correctness.

Modern database systems use transactions to achieve a high degree of fault-tolerance. Many modern programming languages and systems provide garbage collected heap storage, which frees the programmer from the job of explicitly deallocating storage. In this paper we describe integrated garbage collection and recovery algorithms for managing a stable heap in which accessible objects survive both system crashes and media failures.

This paper deals with the integration of an efficient asynchronous remote procedure call mechanism into a programming language. It describes a new data type called a promise that was designed to support asynchronous calls. Promises allow a caller to run in parallel with a call and to pick up the results of the call, including any exceptions it raises, in a convenient and type-safe manner. The paper also discusses efficient composition of sequences of asynchronous calls to different locations in a network.

Article Viewstamped Replication: A New Primary Copy Method to Support Highly-Available Distributed Systems Share on Authors: Brian M. Oki Massachusetts Institute of Technology, Laboratory for Computer Science, Cambridge, MA Massachusetts Institute of Technology, Laboratory for Computer Science, Cambridge, MAView Profile , Barbara H. Liskov Massachusetts Institute of Technology, Laboratory for Computer Science, Cambridge, MA Massachusetts Institute of Technology, Laboratory for Computer Science, Cambridge, MAView Profile Authors Info & Claims PODC '88: Proceedings of the seventh annual ACM Symposium on Principles of distributed computingJanuary 1988 Pages 8–17https://doi.org/10.1145/62546.62549Online:01 January 1988Publication History 163citation2,063DownloadsMetricsTotal Citations163Total Downloads2,063Last 12 Months112Last 6 weeks17 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

Argus is a programming language and system developed to support the construction and execution of distributed programs. This paper describes the implementation of Argus, with particular emphasis on the way we implement atomic actions, because this is where Argus differs most from other implemented systems. The paper also discusses the performance of Argus. The cost of actions is quite reasonable, indicating that action systems like Argus are practical.

This paper describes two techniques that are only loosely related. The first is a method for constructing a highly available service for use in a distributed system. The service presents its clients with a consistent view of its state, but the view may contain old information. Clients can indicate how recent the information must be. The method can be used in any application in which the property of interest is stable: once the property becomes true, it remains true forever. The paper also describes a fault-tolerant garbage collection method for a distributed heap. The method is practical and efficient. Each computer that contains part of the heap does local garbage collection independently, using whatever algorithm it chooses, and without needing to communicate with the other computers that contain parts of the heap. The highly available central service is used to store information about inter.computer references. 1.

Modules in a distributed program are active, communicating entities. A language for distributed programs must choose a set of communication primitives and a structure for processes. This paper examines one possible choice: synchronous communication primitives (such as rendez-vous or remote procedure call) in combination with modules that encompass a fixed number of processes (such as Ada tasks or UNIX processes). An analysis of the concurrency requirements of distributed programs suggests that this combination imposes complex and indirect solutions to common problems and thus is poorly suited for applications such as distributed programs in which concurrency is important. To provide adequate expressive power, a language for distributed programs should abandon either synchronous communication primitives or the static process structure.

A major issue in many applications is how to preserve the consistency of data in the presence of concurrency and hardware failures. We suggest addressing this problem by implementing applications in terms of abstract data types with two properties: Their objects are atomic (they provide serializability and recoverability for activities using them) and resilient (they survive hardware failures with acceptably high probability). We define what it means for abstract data types to be atomic and resilient. We also discuss issues that arise in implementing such types, and describe a particular linguistic mechanism provided in the Argus programming language.

An overview is presented of an integrated programming language and system designed to support the construction and maintenance of distributed programs: programs in which modules reside and execute at communicating, but geographically distinct, nodes.The language is intended to support a class of applications concerned with the manipulation and preservation of long-lived, on-line, distributed data.The language addresses the writing of robust programs that survive hardware failures without loss of distributed information and that provide highly concurrent access to that information while preserving its consistency.Several new linguistic constructs are provided; among them are atomic actions, and modules called guardians that survive node failures.

This paper presents an overview of an integrated programming language and system designed to support the construction and maintenance of distributed programs: programs in which modules reside and execute at communicating, but geographically distinct, nodes. The language is intended to support a class of applications in which the manipulation and preservation of long-lived, on-line, distributed data is important. The language addresses the writing of robust programs that survive hardware failures without loss of distributed information and that provide highly concurrent access to that information while preserving its consistency. Several new linguistic constructs are provided; among them are atomic actions, and modules called guardians that survive node failures.

data types have proved to be a useful technique for structuring systems.In large systems it is sometimes useful to have different regions of the system use different representations for the abstract data values.A technique is described for communicating abstract values between such regions.The method was developed for use in constructing distributed systems, where the regions exist at different computers and the values are communicated over a network.The method defines a call-by-value semantics; it is also useful in nondistributed systems wherever call by value is the desired semantics.An important example of such a use is a repository, such as a file system, for storing longlived data.

Technological advances have made it possible to construct systems from collections of computers connected by a network. At present, however, there is little support for the construction and execution of software to run on such a system. Our research concerns the development of an integrated language/system whose goal is to provide the needed support. This paper discusses a number of issues that must be addressed in such a language. The major focus of our work and this paper is support for the construction of robust software that survives node, network, and media failures.

Distributed programs that run on nodes of a network are now technologically feasible, and are well-suited to the needs of organizations. However, our knowledge about how to construct such programs is limited. This paper discusses primitives that support the construction of distributed programs. Attention is focussed on primitives in two major areas: modularity and communication. The issues underlying the selection of the primitives are discussed, especially the issue of providing robust behavior, and various candidates are analyzed. The primitives will ultimately be provided as part of a programming language that will be used to experiment with construction of distributed programs.

For programs to be reliable and fault tolerant, each program module must be defined to behave reasonably under a wide variety of circumstances. An exception handling mechanism supports the construction of such modules. This paper descnbes an exception handling mechanism developed as part of the CLU programming language. The CLU mechanism is based on a simple model of exception handling that leads to well-structured programs. It is engineered for ease of use and enhanced program readability. This paper discusses the various models of exception handUlng, the syntax and semantics of the CLU mechanism, and methods of implementing the mechanism and integrating it in debugging and production environments.

Controlled sharing of information is needed for many applications. Access-control mechanisms exist in operating systems to provide such controlled sharing. However, programming languages currently do not support such a facility. This paper illustrates how an access-control facility could be incorporated in a programming language. The mechanism described is suitable for incorporation in object-oriented languages that permit the definition of abstract data types, and is defmed in a way that enables compile-time checking of access control.

Discusses the importance of formal specifications and surveys a number of promising specification techniques. The role of formal specifications both in proofs of program correctness and in programming methodologies leading to programs which are correct by construction, is explained. Some criteria are established for evaluating the practical potential of specification techniques. The importance of providing specifications at the right level of abstraction is discussed, and a particularly interesting class of specification techniques, those used to construct specifications of data abstractions, is identified. A number of specification techniques for describing data abstractions are surveyed and evaluated with respect to the criteria.

The Venus Operating System is an experimental multiprogramming system which supports five or six concurrent users on a small computer. The system was produced to test the effect of machine architecture on complexity of software. The system is defined by a combination of micro-programs and software. The microprogram defines a machine with some unusual architectural features; the software exploits these features to define the operating system as simply as possible. In this paper the development of the system is described, with particular emphasis on the principles which guided the design.