Modern file systems assume the use of disk, a system-wide performance bottleneck for over a decade. Current disk caching and RAM file systems either impose high overhead to access memory content or fail to provide mechanisms to achieve data persistence across reboots.The Conquest file system is based on the observation that memory is becoming inexpensive, which enables all file system services to be delivered from memory, except for providing large storage capacity. Unlike caching, Conquest uses memory with battery backup as persistent storage, and provides specialized and separate data paths to memory and disk. Therefore, the memory data path contains no disk-related complexity. The disk data path consists of optimizations only for the specialized disk usage pattern.Compared to a memory-based file system, Conquest incurs little performance overhead. Compared to several disk-based file systems, Conquest achieves 1.3x to 19x faster memory performance, and 1.4x to 2.0x faster performance when exercising both memory and disk. Conquest realizes most of the benefits of persistent RAM at a fraction of the cost of a RAM-only solution. It also demonstrates that disk-related optimizations impose high overheads for accessing memory content in a memory-rich environment.

Rapid and widespread dissemination of security updates throughout the Internet will be invaluable for many purposes, including sending early-warning signals, updating certificate revocation lists, distributing new virus signatures, etc. Notifying a large number of machines securely, quickly, and reliably is challenging. Such a system must outpace the propagation of threats, handle complexities in a large-scale environment, deal with interruption attacks on dissemination, and also secure itself. Revere addresses these problems by building a large-scale, self-organizing, and resilient overlay network on top of the Internet. We discuss how to secure the dissemination procedure and the overlay network, considering possible attacks and countermeasures. We present experimental measurements of a prototype implementation of Revere gathered using a large-scale-oriented approach. These measurements suggest that Revere can deliver security updates at the required scale, speed and resiliency for a reasonable cost.

The rapid growth and increasing pervasiveness of wireless networks raises serious security concerns. Client devices will migrate between numerous diverse wireless environments, bringing with them software vulnerabilities and possibly malicious code. Techniques are needed to protect wireless client devices and the next generation wireless infrastructure. We propose QED, a new security model for wireless networks that enables wireless environments to quarantine devices and then analyze and potentially update or "decontaminate" client nodes. The QED paradigm is presented here, as well as the design of a practical prototype.

A number of mobile computing systems have used the technique of hoarding, which allows a mobile device to store a chosen subset of known files, to give disconnected users the illusion of a complete filesystem in the presence of limited storage. We undertook an extensive and detailed simulation study of the parameters of a well-known hoarding system, seer, in an attempt to discover the parameters that would produce the best performance. To our surprise, we discovered that the best parameter combinations were those that completely disabled seer's complex clustering methods, reverting the system instead to a modified form of LRU hoarding. We discuss the experiments and our results, and propose designs for future systems and directions for future research.

Summary form only given. The Conquest file system is designed to provide a transition from disk- to persistent-RAM-based storage. Initially, we assume 2 to 4 Gbytes of persistent RAM and the popular single-user desktop environment. Unlike other memory file systems, Conquest can incrementally assume more responsibility for in-core storage as memory prices decline. The Conquest approach realizes most of the benefits of persistent-RAM-based file systems before persistent RAM becomes cheaply abundant. Conquest also benefits from the removal of disks as the primary storage by identifying disk-related complexities and isolating them from the critical path where possible. The Conquest prototype is operational under Linux 2.4.2. It is POSIX compliant and supports both in-core and on-disk storage.

Many approaches have been used or proposed for providing security Ior inlormation dissemination over networks, including encryption, authentication, and digital signafures.These mechanisms do not, however, necessarily help ensure that a message is delivered at all.Attacks that try to destroy or intercept security messal~es require other mechanisms.Authenticated acknowledgements are sometimes useful for this purpose, but do not scale well.This paper discusses the use of redundancy to combat attempts to prevent intbrmation dissemination.Redundancy has been widely used in other areas, such as high availability data storage, file replication, and some faulttolerant systems.The se_curity problem has different characteristics that require different approaches to redundancy.We present one example of using redundancy to increase assurance of security updates delivery.

Optimistically replicated systems provide highly available data even when communication between data replicas is unreliable or unavailable. The high availability comes at the cost of allowing inconsistent accesses, since users can read and write old copies of data. Session guarantees have been used to reduce such inconsistencies. They preserve most of the availability benefits of optimistic systems. We generalize session guarantees to apply to persistent as well as distributed entities. We implement these guarantees, called view consistency, on Ficus an optimistically replicated file system. Our implementation enforces consistency on a per-file basis and does not require changes to individual applications. View consistency is enforced by clients accessing the data and thus requires minimal changes to the replicated data servers. We show that view consistency allows access to available and high performing data replicas and can be implemented efficiently. Experimental results show that the consistency overhead for clients ranges from 1% to 8% of application runtime for the benchmarks studied in the prototype system. The benefits of the system are an improvement in access times due to better replica selection and improved consistency guarantees over a purely optimistic system.

This research proposes and tests an approach to engineering distributed file systems that are aimed at wide-scale, Internet-based use. The premise is that replication is essential to deliver performance and availability, yet the traditional conservative replica consistency algorithms do not scale to this environment. Our Ficus replicated file system uses a single-copy availability, optimistic update policy with reconciliation algorithms that reliably detect concurrent updates and automatically restore the consistency of directory replicas. The system uses the peer-to-peer model in which all machines are architectural equals but still permits configuration in a client-server arrangement where appropriate. Ficus has been used for six years at several geographically scattered installations. This paper details and evaluates the use of optimistic replica consistency, automatic update conflict detection and repair, the peer-to-peer (as opposed to client-server) interaction model, and the stackable file system architecture in the design and construction of Ficus. The paper concludes with a number of lessons learned from the experience of designing, building, measuring, and living with an optimistically replicated file system. © 1998 John Wiley & Sons, Ltd.

A common problem facing mobile computing is &connected operation, or computing in the absence of a network.Hoarding eases disconnected operation by selecting a subset of the user's files forlocal storage.We describe a hoarding system that can operate without user intervention, by observing user activity and predicting future needs.The system calculates a new measure, semantic distance, between individual liles, and uses this to feed a clustering algorithm that chooses which files should be hoarded.A separatereplication system manages the actual transport of data; any of a number of replication systems may be used.We discuss practical problems encountered in the real world and present usage statistics showing that our system outperforms previous approaches by factors that can exceed 1O:l.

Stackable design of filing systems constructs sophisticated services from mukiple, independently developed layers.This approach has been advocated to address development problems from code re-use, to extensibility, to version management.Individual layers of such a system often need to cache data to improve performance orprovide desired functionality.Whenaccessto different layers isallowed, cache incoherencies can occur.Without a cache coherence solution, layer designers must either restrict layer access and flexibility or compromise the layered structure to avoid potential data corruption.Thevalue of modular designs such as stacking can be questioned without a suitable solution to this problem.This paper presents a general cache coherence architecture for stackable tiling, including a standard approach to data identifications a key component tolayered coherence protocols.We also present a detailed performance analysis of one implementation of stack cache-coherence, which suggests that very low overheads can be achieved in practice.

Filing services have experienced a number of innovations in recent years, but many of these promising ideas have failed to enter into broad use. One reason is that current filing environments present several barriers to new development. For example, file systems today typically stand alone instead of building on the work of others, and support of new filing services often requires changes that invalidate existing work. Stackable file-system design addresses these issues in several ways. Complex filing services are constructed from layer “building blocks,” each of which may be provided by independent parties. There are no syntactic constraints to layer order, and layers can occupy different address spaces, allowing very flexible layer configuration. Independent layer evolution and development are supported by an extensible interface bounding each layer. This paper discusses stackable layering in detail and presents design techniques it enables. We describe an implementation providing these facilities that exhibits very high performance. By lowering barriers to new filing design, stackable layering offers the potential of broad third-party file-system development not feasible today.

This paper presents a practical set of algorithms for maintaining the consistency of a replicated file system with an optimistic update policy. These algorithms permit a system which allows updates to an object so long as any copy is available; the algorithms then return the various copies to consistency at their first opportunity. These algorithms have been used to build the Ficus replicated file system.>

Shared memory is an effective and efficient paradigm for interprocess communication. We are concerned with software that makes use of shared memory in a single site system and its extension to a multimachine environment. Here we describe the design of a distributed shared memory (DSM) system called Mirage developed at UCLA. Mirage provides a form of network transparency to make network boundaries invisible for shared memory and is upward compatible with an existing interface to shared memory. We present the rationale behind our design decisions and important details of the implementation. Mirage's basic performance is examined by component timings, a worst case application, and a “representative” application. In some instances of page contention, the tuning parameter in our design improves application throughput. In other cases, thrashing is reduced and overall system performance improved using our tuning parameter.

Network transparency refers to the ability of a distributed system to hide machine boundaries from people and application programs; i.e. all resources are accessed in the same manner, independent of their locations. It is demonstrated that transparency across a long-haul network is both highly desirable and technically feasible. A case study of the transparent, distributed operating system Locus, extended to operate transparently across an internet system that includes long-haul links, is discussed at length. New protocols, distributed cache management, and process execution site selection are all used to achieve the results reported.

An approach to the architecture of distributed databases is presented, oriented around extensive embeddmg of database prinntives in the underlying distributed operating system.It is shown that this approach greatly reduces the effort required to provide high quality distributed database services.Substantial portions of this approach are implemented and are operational as extensions to the Locus distributed Unix operating system.TIns paper describes the approach, compares it with other work, argues why rt is attractive and what drawbacks are present, and lays out what has been done and what remains.

Atomic transactions are useful in distributed systems as a means of providing reliable operation in the face of hardware failures. Nested transactions are a generalization of traditional transactions in which transactions may be composed of other transactions. The programmer may initiate several transactions from within a transaction, and serializability of the transactions is guaranteed even if they are executed concurrently. In addition, transactions invoked from within a given transaction fail independently of their invoking transaction and of one another, allowing use of alternate transactions to accomplish the desired task in the event that the original should fail. Thus nested transactions are the basis for a general-purpose reliable programming environment in which transactions are modules which may be composed freely.

LOCUS is a distributed operating system which supports transparent access to data through a network wide filesystem, permits automatic replication of storage, supports transparent distributed process execution, supplies a number of high reliability functions such as nested transactions, and is upward compatible with Unix. Partitioned operation of subnet's and their dynamic merge is also supported.

Many distributed systems are now being developed to provide users with convenient access to data via some kind of communications network. In many cases it is desirable to keep the system functioning even when it is partitioned by network failures. A serious problem in this context is how one can support redundant copies of resources such as files (for the sake of reliability) while simultaneously monitoring their mutual consistency (the equality of multiple copies). This is difficult since network faiures can lead to inconsistency, and disrupt attempts at maintaining consistency. In fact, even the detection of inconsistent copies is a nontrivial problem. Naive methods either 1) compare the multiple copies entirely or 2) perform simple tests which will diagnose some consistent copies as inconsistent. Here a new approach, involving version vectors and origin points, is presented and shown to detect single file, multiple copy mutual inconsistency effectively. The approach has been used in the design of LOCUS, a local network operating system at UCLA.

LOCUS is a distributed operating system that provides a very high degree of network transparency while at the same time supporting high performance and automatic replication of storage. By network transparency we mean that at the system call interface there is no need to mention anything network related. Knowledge of the network and code to interact with foreign sites is below this interface and is thus hidden from both users and programs under normal conditions. LOCUS is application code compatible with Unix2, and performance compares favorably with standard, single system Unix. LOCUS runs on a high bandwidth, low delay local network. It is designed to permit both a significant degree of local autonomy for each site in the network while still providing a network-wide, location independent name structure. Atomic file operations and extensive synchronization are supported.

A locking protocol to coordinate access to a distributed database and to maintain system consistency throughout normal and abnormal conditions is presented. The proposed protocol is robust in the face of crashes of any participating site, as well as communication failures. Recovery from any number of failures during normal operation or any of the recovery stages is supported. Recovery is done in such a way that maximum forward progress is achieved by the recovery procedures. Integration of virtually any locking discipline including predicate lock methods is permitted by this protocol. The locking algorithm operates, and operates correctly, when the network is partitioned, either intentionally or by failure of communication lines. Each partition is able to continue with work local to it, and operation merges gracefully when the partitions are reconnected. A subroutine of the protocol, that assures reliable communication among sites, is shown to have better performance than two-phase commit methods. For many topologies of interest, the delay introduced by the overall protocol is not a direct function of the size of the network. The communications cost is shown to grow in a relatively slow, linear fashion with the number of sites participating in the transaction. An informal proof of the correctness of the algorithm is also presented in this paper. The algorithm has as its core a centralized locking protocol with distributed recovery procedures. A centralized controller with local appendages at each site coordinates all resource control, with requests initiated by application programs at any site. However, no site experiences undue load. Recovery is broken down into three disjoint mechanisms: for single node recovery, merge of partitions, and reconstruction of the centralized controller and tables. The disjointness of the mechanisms contributes to comprehensibility and ease of proof. The paper concludes with a proposal for an extension aimed at optimizing operation of the algorithm to adapt to highly skewed distributions of activity. The extension applies nicely to interconnected computer networks.

A principal problem with dynamic validation of transactions with respect to a set of integrity assertions is the cost associated with the evaluation of such assertions. Although several methods of dynamic validation of transactions have been proposed there has been little attempt to analyze and to compare the performance of different validation methods. In this paper we evaluate compile time, run time, postexecution time, and mixed (run time --- postexecution time) validation methods for two semantic integrity subsystem designs. In one case we assume that the arguments of all integrity assertions are stored in secondary slow access memory and in the second we assume that the database is partitioned so that some data used for transaction validation are stored in fast access form.

Data Secure Unix, a kernel structured operating system, was constructed as part of an ongoing effort at UCLA to develop procedures by which operating systems can be produced and shown secure. Program verification methods were extensively applied as a constructive means of demonstrating security enforcement.

A locking protocol to coordinate access to a distributed database and to maintain system consistency throughout normal and abnormal conditions is presented. The proposed protocol is robust in the face of crashes of any participating site, as well as communication failures. Recovery from any number of failures during normal operation or any of the recovery stages is supported. Recovery is done in such a way that maximum forward progress is achieved by the recovery procedures. Integration of virtually any locking discipline including predicate lock methods is permitted by this protocol. The locking algorithm operates, and operates correctly, when the network is partitioned, either intentionally or by failure of communication lines. Each partition is able to continue with work local to it, and operation merges gracefully when the partitions are reconnected.A subroutine of the protocol, that assures reliable communication among sites, is shown to have better performance than two-phase commit methods. For many topologies of interest, the delay introduced by the overall protocol is not a direct function of the size of the network. The communications cost is shown to grow in a relatively slow, linear fashion with the number of sites participating in the transaction. An informal proof of the correctness of the algorithm is also presented in this paper.The algorithm has as its core a centralized locking protocol with distributed recovery procedures. A centralized controller with local appendages at each site coordinates all resource control, with requests initiated by application programs at any site. However, no site experiences undue load. Recovery is broken down into three disjoint mechanisms: for single node recovery, merge of partitions, and reconstruction of the centralized controller and tables. The disjointness of the mechanisms contributes to comprehensibility and ease of proof.The paper concludes with a proposal for an extension aimed at optimizing operation of the algorithm to adapt to highly skewed distributions of activity. The extension applies nicely to interconnected computer networks.

Virtual machine systems have been implemented on a limited number of third generation computer systems, for example CP-67 on the IBM 360/67. The value of virtual machine techniques to ease the development of operating systems, to aid in program transferability, and to allow the concurrent running of disparate operating systems, test and diagnostic programs has been well recognized. However, from previous empirical studies, it is known that many third generation computer systems, e.g. the DEC PDP-10, cannot support a virtual machine system.