The pressing demand to deploy software updates without stopping running programs has fostered much research on live update systems in the past decades. Prior solutions, however, either make strong assumptions on the nature of the update or require extensive and error-prone manual effort, factors which discourage the adoption of live update. This paper presentsMutable Checkpoint-Restart(MCR), a new live update solution for generic (multiprocess and multithreaded) server programs written in C. Compared to prior solutions, MCR can support arbitrary software updates and automate most of the common live update operations. The key idea is to allow the running version to safely reach a quiescent state and then allow the new version to restart as similarly to a fresh program initialization as possible, relying on existing code paths to automatically restore the old program threads and reinitialize a relevant portion of the program data structures. To transfer the remaining data structures, MCR relies on a combination of precise and conservative garbage collection techniques to trace all the global pointers and apply the required state transformations on the fly. Experimental results on popular server programs (Apache httpd,nginx,OpenSSHandvsftpd) confirm that our techniques can effectively automate problems previously deemed difficult at the cost of negligible performance overhead (2 percent on average) and moderate memory overhead (3.9$\times$on average, without optimizations).

Operating systems provide a wide range of services, which are crucial for the increasingly high reliability and scalability demands of modern applications. Providing both reliability and scalability at the same time is hard. Commodity OS architectures simply lack the design abstractions to do so for demanding core OS services such as the network stack. For reliability and scalability guarantees, they rely almost exclusively on ensuring a high-quality implementation, rather than a reliable and scalable design. This results in complex error recovery paths and hard-to-maintain synchronization code.

Much research has gone into making operating systems more amenable to recovery and more resilient to crashes. Traditional solutions rely on partitioning the operating system (OS) to contain the effects of crashes within compartments and facilitate modular recovery. However, state dependencies among the compartments hinder recovery that is globally consistent. Such recovery typically requires expensive runtime dependency tracking which results in high performance overhead, highcomplexity and a large Reliable Computing Base (RCB). We propose a lightweight strategy that limits recovery to cases where we can statically and conservatively prove that compartment recovery leads to a globally consistent state - trading recoverable surface for a simpler and smaller RCB with lower performance overhead and maintenance cost. We present OSIRIS, a research OS design prototype that demonstrates efficient and consistent crash recovery. Our evaluation shows that OSIRIS effectively recovers from important classes of real-world software bugs with a modest RCB and low overheads.

When software fault injection is used, faults are typically inserted at the binary or source level. The former is fast but provides poor fault accuracy while the latter cannot scale to large code bases because the program must be rebuilt for each experiment. Alternatives that avoid rebuilding incur large run-time overheads by applying fault injection decisions at run-time. HSFI, our new design, injects faults with all context information from the source level and applies fault injection decisions efficiently on the binary. It places markers in the original code that can be recognized after code generation. We implemented a tool according to the new design and evaluated the time taken per fault injection experiment when using operating systems as targets. We can perform experiments more quickly than other source-based approaches, achieving performance that come close to that of binary-level fault injection while retaining the benefits of source-level fault injection.

Debugging long-lived latent software bugs that manifest themselves only long after their introduction in the system is hard. Even state-of-the-artrecord/replay debugging techniques are of limited use to identify the rootcause of long-lived latent bugs in general and event-driven bugs in particular. We propose DeLorean, a new end-to-end solution for time-travelling debugging based on fast memory checkpointing. Our design trades off replay guarantees with efficient support for history-aware debug queries (or time-travelling introspection) and provides novel analysis tools to diagnose event-driven latent software bugs. DeLorean imposes low run-time performance and memory overhead while preserving in memory as much history information as possible by deduplicating and/or compressing the collected data. We evaluate DeLorean byextensive experimentation, exploring the performance-memory tradeoffs in different configurations and comparing our results against state-of-the-art solutions. We show that DeLorean can efficiently support high-frequency checkpoints and store millions of them in memory.

Memory check pointing is a pivotal technique in systems reliability, with applications ranging from crash recovery to replay debugging. Unfortunately, many traditional memory check pointing use-cases require high-frequency checkpoints, something for which existing application-level solutions are not well-suited. The problem is that they incur either substantial run-time performance overhead, or poor memory usage guarantees. As a result, their application in practice is hampered. This paper presents Lightweight Memory Check pointing (LMC), a new user-level memory check pointing technique that combines low performance overhead with strong memory usage guarantees for high check pointing frequencies. To this end, LMC relies on compiler-based instrumentation to shadow the entire memory address space of the running program and incrementally checkpoint modified memory bytes in a LMC-maintained shadow state. Our evaluation on popular server applications demonstrates the viability of our approach in practice, confirming that LMC imposes low performance overhead with strictly bounded memory usage at runtime.

High-frequency memory checkpointing is an important technique in several application domains, such as automatic error recovery (where frequent checkpoints allow the system to transparently mask failures) and application debugging (where frequent checkpoints enable fast and accurate time-traveling support). Unfortunately, existing (typically incremental) checkpointing frameworks incur substantial performance overhead in high-frequency memory checkpointing applications, thus discouraging their adoption in practice.

The pressing demand to deploy software updates without stopping running programs has fostered much research on live update systems in the past decades. Prior solutions, however, either make strong assumptions on the nature of the update or require extensive and error-prone manual effort, factors which discourage live update adoption.

In recent times, two virtualization approaches have become dominant: hardware-level and operating system-level virtualization. They differ by where they draw the virtualization boundary between the virtualizing and the virtualized part of the system, resulting in vastly different properties. We argue that these two approaches are extremes in a continuum, and that boundaries in between the extremes may combine several good properties of both. We propose abstractions to make up one such new virtualization boundary, which combines hardware-level flexibility with OS-level resource sharing. We implement and evaluate a first prototype.

Increasingly many systems have to run all the time with no downtime allowed. Consider, for example, systems controlling electric power plants and e-banking servers. Nevertheless, security patches and a constant stream of new operating system versions need to be deployed without stopping running programs. These factors naturally lead to a pressing demand for live update---upgrading all or parts of the operating system without rebooting. Unfortunately, existing solutions require significant manual intervention and thus work reliably only for small operating system patches.

Despite the growing attention to security concerns and advances in code verification tools, many memory errors still escape testing and plague production applications with security vulnerabilities. We present RCORE, an efficient dynamic program monitoring infrastructure to perform automated security vulnerability monitoring. Our approach is to perform extensive static analysis at compile time to automatically index program state invariants (PSIs). At runtime, our novel dynamic analysis continuously inspects the program state and produces a report when PSI violations are found. Our technique retrofits existing applications and is designed for both offline and production runs. To avoid slowing down production applications, we can perform our dynamic analysis on idle cores to detect suspicious behavior in the background. The alerts raised by our analysis are symptoms of memory corruption or other-potentially exploitable-dangerous behavior. Our experimental evaluation confirms that RCORE can report on several classes of vulnerabilities with very low overhead.

As enterprises shift from using direct-attached storage to network-based storage for housing primary data, flash-based, host-side caching has gained momentum as the primary latency reduction technique. In this paper, we make the case for integration of flash caching algorithms at the file level, as opposed to the conventional block-level integration. In doing so, we will show how our extensions to Loris, a reliable, file-oriented storage stack, transform it into a framework for designing layout-independent, file-level caching systems. Using our Loris prototype, we demonstrate the effectiveness of Loris-based, file-level flash caching systems over their block-level counterparts, and investigate the effect of various write and allocation policies on the overall performance.

Several multilevel storage systems have been designed over the past few years that utilize RAM and flash-based SSDs in concert to cache data resident in HDD-based primary storage. The low cost/GB and non-volatility of SSDs relative to RAM have encouraged storage system designers to adopt inclusivity (between RAM and SSD) in the caching hierarchy. However, in light of recent changes in hardware landscape, we believe that in the future, multilevel caches are invariably going to be hybrid caches where 1) all/most levels are physically collocated 2) the levels differ substantially only with respect to performance and not storage density, and 3) all levels are persistent. In this paper, we will investigate the design tradeoffs involved in building exclusive, persistent, direct-attached, multilevel storage caches. In doing so, we will first present a comparative evaluation of various techniques that have been proposed to achieve exclusivity in distributed storage caches in the context of a direct-attached, hybrid cache, and show the potential performance benefits of maintaining exclusivity. We will then investigate extensions to these demand-based, read-only data caching algorithms in order to address two issues specific to direct-attached hybrid caches, namely, handling writes and managing SSD lifetime.

Fault injection is a pivotal technique in dependability benchmarking. Unfortunately, existing general-purpose fault injection tools either inject faults in predetermined memory locations or resort to random injection, approaches that generally result in poor fault coverage and controllability guarantees. This makes it difficult to reproduce or compare experiments across different systems or workloads. This paper presents EDFI, a new tool for dependable general-purpose fault injection experiments. EDFI combines static and dynamic program instrumentation to perform execution-driven fault injection, a technique which allows realistic software faults to be injected in a controlled way as the target system executes. Our instrumentation strategy guarantees a predetermined fault load distribution during the entirety of the experiment, independently of the particular system or workload considered. Our evaluation confirms that EDFI significantly improves the precision and controllability of prior tools, at the cost of only modest memory and performance overhead during fault-free execution.

In this paper, we describe the emerging concept of namespace modules: operating system components that are responsible for constructing a hierarchical file system namespace based on one or more individual underlying file objects. We show that the likely presence of software bugs in such modules calls for the ability to recover from crashes, but that the current state of the art falls short of the desired behavior. We then introduce a crash recovery solution that is based on transactions, and detail the requirements for a system to implement this solution. We apply our solution to two different use cases: the primary namespace module for a storage stack, and an extension module that exposes the contents of scientific data files. Our evaluation shows that the transaction system has low overhead and significantly adds to the robustness of the namespace modules.

For many years, multiserver1operating systems have been demonstrating, by their design, high dependability and reliability. However, the design has inherent performance implications which were not easy to overcome. Until now the context switching and kernel involvement in the message passing was the performance bottleneck for such systems to get broader acceptance beyond niche domains. In contrast to other areas of software development where fitting the software to the parallelism is difficult, the new multicore hardware is a great match for the multiserver systems. We can run individual servers on different cores. This opens more room for further decomposition of the existing servers and thus improving dependability and live-updatability. We discuss in general the implications for the multiserver systems design and cover in detail the implementation and evaluation of a more dependable networking stack. We split the single stack into multiple servers which run on dedicated cores and communicate without kernel involvement. We think that the performance problems that have dogged multiserver operating systems since their inception should be reconsidered: it is possible to make multiserver systems fast on multicores.

Over the past few years, hybrid storage architectures that use high-performance SSDs in concert with high-density HDDs have received significant interest from both industry and academia, due to their capability to improve performance while reducing capital and operating costs. These hybrid architectures differ in their approach to integrating SSDs into the traditional HDD-based storage stack. Of several such possible integrations, two have seen widespread adoption: Caching and Dynamic Storage Tiering. Although the effectiveness of these architectures under certain workloads is well understood, a systematic side-by-side analysis of these approaches remains difficult due to the range of design alternatives and configuration parameters involved. Such a study is required now more than ever to be able to design effective hybrid storage solutions for deployment in increasingly virtualized modern storage installations that blend several workloads into a single stream. In this paper, we first present our extensions to the Loris storage stack that transform it into a framework for designing hybrid storage systems. We then illustrate the flexibility of the framework by designing several Caching and DST-based hybrid systems. Following this, we present a systematic side-by-side analysis of these systems under a range of individual workload types and offer insights into the advantages and disadvantages of each architecture. Finally, we discuss the ramifications of our findings on the design of future hybrid storage systems in the light of recent changes in hardware landscape and application workloads.

In this paper, we look at two important failure classes in the storage stack: system crashes, where the whole system shuts down unexpectedly, and process crashes, where a part of the storage stack software fails due to an implementation bug. We investigate these two problems in the context of the Loris storage stack. We show how restoring metadata consistency can provide a common first step for recovery from both types of crashes. In addition, we present fine-grained and corruption-resistant data resynchronization as the second step for system crash recovery, and an in-memory roll-forward log that can provide strong guarantees as the second step for process crash recovery in a microkernel setting. We implement our findings in our Loris prototype, and implement a new crash-resistant on-device layout as part of our proof of concept. The evaluation shows that our approach provides increased reliability at a reasonable performance cost.

Traditional file systems made it possible for administrators to create file volumes, on a one-file-volume-per-disk basis. With the advent of RAID algorithms and their integration at the block level, this “one file volume per disk” bond forced administrators to create a single, shared file volume across all users to maximize storage efficiency, thereby complicating administration. To simplify administration, and to introduce new functionalities, file volume virtualization support was added at the block level. This new virtualization engine is commonly referred to as the volume manager, and the resulting arrangement, with volume managers operating below file systems, has been referred to as the traditional storage stack. In this paper, we present several problems associated with the compatibility-driven integration of file volume virtualization at the block level. In earlier work, we presented Loris, a reliable, modular storage stack, that solved several problems with the traditional storage stack by design. In this paper, we extend Loris to support file volume virtualization. In doing so, we first present “File pools”, our novel storage model to simplify storage administration, and support efficient file volume virtualization. Following this, we will describe how our single unified virtualization infrastructure, with a modular division of labor, is used to support several new functionalities like (1) instantaneous snapshoting of both files and file volumes, (2) efficient snapshot deletion through information sharing, and (3) open-close versioning of files. We then present “Version directories,” our unified interface for browsing file history information. Finally, we will evaluate the infrastructure, and provide an in-depth comparison of our approach with other competing approaches.

With the amount of data increasing at an alarming rate, domain-specific user-level metadata management systems have emerged in several application areas to compensate for the shortcomings of file systems. Such systems provide domain-specific storage formats for performance-optimized metadata storage, search-based access interfaces for enabling declarative queries, and type-specific indexing structures for performing scalable search over metadata. In this paper, we highlight several issues that plague these user-level systems. We then show how integrating metadata management into the Loris stack solves all these problems by design. In doing so, we show how the Loris stack provides a modular framework for implementing domain-specific solutions by presenting the design of our own Loris-based metadata management system that provides 1) LSM-tree-based metadata storage, 2) an indexing infrastructure that uses LSM-trees for maintaining real-time attribute indices, and 3) scalable metadata querying using an attribute-based query language.

The arrangement of file systems and volume management/RAID systems, together commonly referred to as the storage stack, has remained the same for several decades, despite significant changes in hardware, software and usage scenarios. In this paper, we evaluate the traditional storage stack along three dimensions: reliability, heterogeneity and flexibility. We highlight several major problems with the traditional stack. We then present Loris, our redesign of the storage stack, and we evaluate several aspects of Loris.

After the voting debacle in the Florida Presidential election of 2000 with its now-fabled hanging chads and pregnant chads, many voting jurisdictions turned to electronic voting machines. This transition has had at least as many problems as punch-card systems and added the additional one of making recounts impossible. As a result, many jurisdictions have gone back to paper ballots in despair. We believe that electronic voting can have many benefits including accessibility and usability but requires regarding voting as a system of which the voting machine is only a (small) part. In this paper we describe all the components of an electronic voting system that is practical and difficult to tamper with. We emphasize the importance of systems aspects, defense in depth, and being paranoiac.

This work explores the principles and practice of isolating low-level device drivers in order to improve OS dependability. In particular, we explore the operations drivers can perform and how fault propagation in the event a bug is triggered can be prevented. We have prototyped our ideas in an open-source multiserver OS (MINIX 3) that isolates drivers by strictly enforcing least authority and iteratively refined our isolation techniques using a pragmatic approach based on extensive software-implemented fault-injection (SWIFI) testing. In the end, out of 3,400,000 common faults injected randomly into 4 different Ethernet drivers using both programmed I/O and DMA, no fault was able to break our protection mechanisms and crash the OS. In total, we experienced only one hang, but this appears to be caused by buggy hardware.

In this paper we present Trishul-UCON (T-UCON), a DRM system based on the UCON_ABC model. T-UCON is designed to be capable of enforcing not only application-specific policies, as any existing software-based DRM solution does, but also DRM policies across applications. This is achieved by binding the DRM policy only to the content it protects with no relations to the application(s) which will use this content. Furthermore, to guarantee that the policy is continuously enforced, we designed T-UCON as a JVM-based middleware that mediates the usage requests of any Java application to the protected content. Each request is granted or denied according to the content policy. We illustrate the unique features of T-UCON by using typical examples of DRM policies such as the pay-per-use and the use only N times scenarios. Preliminary results on the overhead of our solution are also provided.

As the sale of digital content is moving more and more online, the content providers are beginning to realize that bandwidth infrastructures are not easily scalable. The emergence of peer-to-peer content delivery networks present these providers with a way to overcome this limitation. However, such networks have so far been ad-hoc in nature. One of the main reason for this has been the lack of incentives for end users to contribute their bandwidth to the network. In this paper we present the design and implementation of a peer-to-peer protocol named Floodgate that provides a micropayment based incentive for peers to contribute their bandwidth. Floodgate implements an optimistic fair exchange protocol and is designed to be resilient against targeted attacks. Performance measurements, including those conducted over the PlanetLab infrastructure, show that Floodgate's security and cryptographic overheads are low when compared against the standard BitTorrent implementation.

Multiserver operating systems have great potential to improve dependability, but, paradoxically, are paired with inherently more complex interprocess communication (IPC). Several projects have attempted to run drivers and extensions in isolated protection domains, but a systematic way to deal with IPC threats posed by untrusted parties is not yet available in the literature. IPC is fundamental to the dependability of multiserver systems.In this paper, we present a classification of IPC threats in multiserver systems with unreliable and hostile senders and receivers, such as resource exhaustion, spoofing, and unauthorized access. We also introduce an extended asymmetric trust model, describing two new IPC vulnerabilities relating to caller blockage. Based on our classification of IPC threats we present the IPC defense mechanisms and architecture of MINIX 3.

Studies have shown that device drivers and extensions contain 3-7 times more bugs than other operating system code and thus are more likely to fail. Therefore, we present a failure-resilient operating system design that can recover from dead drivers and other critical components - primarily through monitoring and replacing malfunctioning components on the fly - transparent to applications and without user intervention. This paper focuses on the post-mortem recovery procedure. We explain the working of our defect detection mechanism, the policy-driven recovery procedure, and post-restart reintegration of the components. Furthermore, we discuss the concrete steps taken to recover from network, block device, and character device driver failures. Finally, we evaluate our design using performance measurements, software fault-injection experiments, and an analysis of the reengineering effort.

The research area of very large scale wireless sensor networks made of low-cost sensors is gaining a lot of interest as witnessed by the large number of published papers. The security aspects of such networks are addressed as well, and in particular many security papers investigating the security aspects of such networks make important assumptions about the capabilities of low-cost sensors. Consequently, the techniques proposed in the current literature to provide security properties for this low-cost wireless sensor networks are heavily shaped by such assumptions. In this position paper, we challenge such assumptions by presenting the results of an experiment we conducted using sensors representative of low cost units. And we show that the same security properties can be better provided using techniques based on application-specific knowledge, heuristics and statistical tests. Finally, we show that one of the most highly cited application scenarios to motivate such techniques, the air-dropped sensor network, is likely to be more a myth than a realistic scenario for low-cost sensors.

RFID systems as a whole are often treated with suspicion, but the input data received from individual RFID tags is implicitly trusted. RFID attacks are currently conceived as properly formatted but fake RFID data; however no one expects an RFID tag to send a SQL injection attack or a buffer overflow. This paper is meant to serve as a warning that data from RFID tags can be used to exploit back-end software systems. RFID middleware writers must therefore build appropriate checks (bounds checking, special character filtering, etc.), to prevent RFID middleware from suffering all of the well-known vulnerabilities experienced by the Internet. Furthermore, as a proof of concept, this paper presents the first self-replicating RFID virus. This virus uses RFID tags as a vector to compromise backend RFID middleware systems, via a SQL injection attack

The Globe Distribution Network (GDN) is an application for the efficient, worldwide distribution of freely redistributable software packages. Distribution is made efficient by encapsulating the software into special distributed objects which efficiently replicate themselves near to the downloading clients. The Globe Distribution Network takes a novel, optimistic approach to stop the illegal distribution of copyrighted and illicit material via the network. Instead of having moderators check the packages at upload time, illegal content is removed and its uploader's access to the network permanently revoked only when the violation is discovered. Other protective measures defend the GDN against internal and external attacks to its availability. By exploiting the replication of the software and using fault-tolerant server software, the Globe Distribution Network achieves high availability. A prototype implementation of the GDN is available from http://www.cs.vu.nl/globe/.

No abstract available.

This paper describes a security architecture allowing digital rights management in home networks consisting of consumer electronic devices. The idea is to allow devices to establish dynamic groups, so called "Authorized Domains", where legally acquired copyrighted content can seamlessly move from device to device. This greatly improves the end-user experience, preserves "fair use" expectations, and enables the development of new business models by content providers. Key to our design is a hybrid compliance checking and group establishment protocol, based on pre-distributed symmetric keys, with minimal reliance on public key cryptographic operations. Our architecture does not require continuous network connectivity between devices, and allows for efficient and flexible key updating and revocation.

Digital rights management systems allow copyrighted content to be commercialized in digital format without the risk of revenue loss due to piracy. Making such systems secure is no easy task, given that content needs to be protected while accessed through electronic devices in the hands of potentially malicious end-users; in this context, intrusion tolerance becomes a very useful system property. In this paper we point out a limitation shared by all current DRM architectures, namely their weakness in reacting to possible device compromise and confining the damage caused by such a compromise. As a solution, we propose a paradigm shift - moving from the original DRM system model where all devices are equally trustworthy and have discretionary control over all protected content, to a new model where information flow is controlled through a multi-level security policy that differentiates between devices based on their tamper-resistance properties. We show that besides improved intrusion-tolerance, supporting such policies has other advantages, such as the ability to define more flexible business models for supplying content. We also show that for a given DRM architecture, the type authentication protocol used when accepting new devices in the system has a big impact on how well multi-level security policies can be supported, and that a number of protocols currently being considered are not very well suited for this job.

A common way to protect objects in distributed systems is to issue authorization certificates to users, which they present to gain access. In some situations a way is needed to revoke existing certificates. Current methods, such as having a master revocation list, have been designed to work efficiently with identity certificates, and to not take into account the delegation of certificate-issuing rights required when implementing complex administrative hierarchies for large distributed applications. In this paper we present a novel mechanism for revoking authorization certificates based on clustering users and servers, and present arguments showing that it is more efficient than other methods. We also discuss a way for probabilistically auditing the use of the revocation mechanism proposed to reduce the chances of any component behaving maliciously.

Large-scale distributed systems present numerous security problems not present in local systems. We present a general security architecture for a large-scale object-based distributed system. Its main features include ways for servers to authenticate clients, clients to authenticate servers, new secure servers to be instantiated without manual intervention, and ways to restrict which client can perform which operation on which object. All of these features are done in a platform- and application-independent way, so the results are quite general. The basic idea behind the scheme is to have each object owner issue cryptographically sealed certificates to users to prove which operations they may request and to servers to prove which operations they are authorized to execute. These certificates are used to ensure secure binding and secure method invocation. The paper discusses the required certificates and security protocols for using them.

To improve the scalability of the Web, it is common practice to apply caching and replication techniques. Numerous strategies for placing and maintaining multiple copies of Web documents at several sites have been proposed. These approaches essentially apply a global strategy by which a single family of protocols is used to choose replication sites and keep copies mutually consistent. We propose a more flexible approach by allowing each distributed document to have its own associated strategy. We propose a method for assigning an optimal strategy to each document separately and prove that it generates a family of optimal results. Using trace-based simulations, we show that optimal assignments clearly outperform any global strategy. We have designed an architecture for supporting documents that can dynamically select their optimal strategy and evaluate its feasibility.

In this paper we present work in progress on a worldwide, scalable multi-agent system, based on a paradigm of hyperlinked rooms. The framework offers facilities for managing distribution, security and mobility aspects for both active elements (agents) and passive elements (objects) in the system. Our framework offers separation of logical concepts from physical representation, distribution support, mobility support, and a security architecture.

The Globe Distribution Network (GDN) is an application for worldwide distribution of freely redistributable software packages. The GDN takes a novel, optimistic approach to stop the illegal distribution of copyrighted and illicit material via the network. Instead of having moderators check the software archives at upload time, illegal content is removed and its uploader's access to the network permanently revoked only when the content is discovered. An important feature of the GDN is that the objects containing the software can run on untrustworthy servers. A first version of the GDN has been implemented and has been running since October 2000 across four European sites.

A location service tracks and locates objects. Such a service should provide efficient means for updating and looking up an object's address, especially for those that are mobile. However, current location services have limited scalability due to poor exploitation of locality and ineffective caching. An important aspect of efficient caching in the presence of mobility is to identify boundaries of the region within which a mobile object usually remains. Caching a reference to such a region rather than to the object itself ensures that the cached entry remains stable. Identifying a region requires dynamically taking migration patterns into account. This paper describes a scalable location service that efficiently supports tracking mobile objects, partly by dynamically adapting to the mobile behavior of each object separately.

Despite the extensive use of caching techniques, the Web is overloaded. While the caching techniques currently used help some, it would be better to use different caching and replication strategies for different Web pages, depending on their characteristics. We propose a framework in which such strategies can be devised independently per Web document. A Web document is constructed as a worldwide, scalable distributed Web object. Depending on the coherence requirements for that document, the most appropriate caching or replication strategy can subsequently be implemented and encapsulated by the Web object. Coherence requirements are formulated from two different perspectives: that of the Web object, and that of clients using the Web object. We have developed a prototype in Java to demonstrate the feasibility of implementing different strategies for different Web objects.

We describe the algorithmic design of a worldwide location service for distributed objects. A distributed object can reside at multiple locations at the same time, and offers a set of addresses to allow client processes to contact it. Objects may be highly mobile like, for example, software agents or Web applets. The proposed location service supports regular updates of an object's set of contact addresses, as well as efficient look-up operations. Our design is based on a worldwide distributed search tree in which addresses are stored at different levels, depending on the migration pattern of the object. By exploiting an object's relative stability with respect to a region, combined with the use of pointer caches, look-up operations can be made highly efficient.

The Amoeba group communication system has two unique aspects: (1) it uses a sequencer-based protocol with negative acknowledgements for achieving a total order on all group messages; and (2) users choose the degree of fault tolerance they desire. This paper reports on our design decisions in retrospect, the performance of the Amoeba group system, and our experiences using the system. We conclude that sequencer-based group protocols achieve high performance (comparable to Amoeba's fast remote procedure call implementation), that the scalability of our sequencer-based protocols is limited by message processing time, and that the flexibility and modularity of user-level implementations of protocols is likely to outweigh the potential performance loss.

We describe the design of an extensible kernel, called Paramecium. This kernel uses an object-based software architecture which together with instance naming, late binding and explicit overrides enables easy reconfiguration. Determining which components reside in the kernel protection domain is up to the user. A certification authority or one of its delegates certifies which components are trustworthy and therefore permitted to run in the kernel protection domain. These delegates may include validation programs, correctness provers, and system administrators. The main advantage of certifications is that it can handle trust and sharing in a non-cooperative environment.

Abstract Two kinds of parallel computers exist: those with shared memory and those without. The former are difficult to build but easy to program. The latter are easy to build but difficult to program. In this paper we present a hybrid model that combines the best properties of each by simulating a restricted object‐based shared memory on machines that do not share physical memory. In this model, objects can be replicated on multiple machines. An operation that does not change an object can then be done locally, without any network traffic. Update operations can be done using the reliable broadcast protocol described in the paper. We have constructed a prototype system, designed and implemented a new programming language for it, and programmed various applications using it. The model, algorithms, language, applications and performance will be discussed.

Building the hardware for a high-performance distributed computer system is a lot easier than building its software. The authors describe a model for programming distributed systems based on abstract data types that can be replicated on all machines that need them. Read operations are done locally, without requiring network traffic. Writes can be done using a reliable broadcast algorithm if the hardware supports broadcasting; otherwise, a point-to-point protocol is used. The authors have built such a system based on the Amoeba microkernel, and implemented a language, Orca, on top of it. For Orca applications that have a high ratio of reads to writes, they measure good speedups on a system with 16 processors.>

Group communication is an important paradigm for building distributed applications. The authors discuss a fault-tolerant distributed directory service based on group communication, and compare it with the previous design and implementation based on remote procedure call (RPC). The group directory service uses an active replication scheme and, when triplicated, can handle 627 lookup operations per second and 88 update operations per second (using nonvolatile RAM). This performance is better than the performance for the RPC implementation and it is even better than the performance for directory operations under SunOS, which does not provide any fault tolerance at all. The conclusion is that the implementation using group communication is simpler and has better performance than the one based on remote procedure call, supporting the claim that a distributed operating system should provide both remote procedure call and group communication.>

Most modern network protocols give adequate support for traditional applications such as file transfer and remote login. Distributed applications, however, have different requirements (e.g., efficient at-most-once remote procedure call even in the face of processor failures). Instead of using ad hoc protocols to meet each of the new requirements, we have designed a new protocol, called the Fast Local Internet Protocol (FLIP), that provides a clean and simple integrated approach to these new requirements. FLIP is an unreliable message protocol that provides both point-to-point communication and multicast communication, and requires almost no network management. Furthermore, by using FLIP we have simplified higher-level protocols such as remote procedure call and group communication, and enhanced support for process migration and security. A prototype implementation of FLIP has been built as part of the new kernel for the Amoeba distributed operating system, and is in daily use. Measurements of its performance are presented.

Abstract Most methods for programming loosely coupled systems are based on message‐passing. Recently, however, methods have emerged based on ‘virtually’ sharing data. These methods simplify distributed programming, but are hard to implement efficiently, as loosely coupled systems do not contain physical shared memory. We introduce a new model,the shared data‐object model, that eases the implementation of parallel applications on loosely coupled systems, but can still be implemented efficiently. In our model, shared data are encapsulated in passive data‐objects, which are variables of user‐defined abstract data types. To speed up access to shared data, data‐objects are replicated. This ability to replicate objects is a significant difference with other object‐based models (e.g. Emerald and Amber). Also, by replicating logical objects rather than physical pages, our model has many advantages over shared virtual memory systems. This paper discusses the design choices involved in replicating objects and their effect on performance. Important issues are: how to maintain consistency among different copies of an object; how to implement changes to objects; which strategy for object replication to use. We have implemented several options to determine which ones are the most efficient.

Abstract Two paradigms for distributed shared memory on loosely‐coupled computing systems are compared: the shared data‐object model as used in Orca, a programming language specially designed for loosely‐coupled computing systems, and the shared virtual memory model. For both paradigms two systems are described, one using only point‐to‐point messages, the other using broadcasting as well. The two paradigms and their implementations are described briefly. Their performances are compared on four applications: the travelling‐salesman problem, alpha‐beta search, matrix multiplication and the all‐pairs shortest‐paths problem. Measurements were obtained on a system consisting of 10 MC68020 processors connected by an Ethernet. For comparison purposes, the applications have also been run on a system with physical shared memory. In addition, the paper gives measurements for the first two applications above when remote procedure call is used as the communication mechanism. The measurements show that both paradigms can be used efficiently for programming large‐grain parallel applications, with significant speed‐ups. The structured shared data‐object model achieves the highest speed‐ups and is easiest to program and to debug.

A detailed description is given of the Orca language design and the design choices are discussed. Orca is intended for applications programmers rather than systems programmers. This is reflected in its design goals to provide a simple, easy-to-use language that is type-secure and provides clean semantics. Three example parallel applications in Orca, one of which is described in detail, are discussed. One of the existing implementations, which is based on reliable broadcasting, is described. Performance measurements of this system are given for three parallel applications. The measurements show that significant speedups can be obtained for all three applications. The authors compare Orca with several related languages and systems.>

Primitives for broadcast communication that have been integrated with the Amoeba distributed operating system are introduced. The semantics of the broadcast primitives are simple and easy to understand, but are still powerful. The proposed primitives, for example, guarantee global ordering of broadcast messages. The proposed primitives are also efficient: a reliable broadcast can be done in just slightly more than two messages, so the performance is comparable to a remote procedure call. In addition, the primitives are flexible; user applications can, for example, trade performance against fault-tolerance.>

The Bullet server is a file server that outperforms traditional file servers by more than a factor of three. It achieves high throughput and low delay by a software design radically different from that of file servers currently in use. Whereas files are normally stored as a sequence of disk blocks, each Bullet server file is stored contiguously, both on disk and in the server's random access memory cache. Furthermore, it uses the concept of an immutable file to improve performance, to enable caching, and to provide a clean semantic model to the user. The authors describe the design and implementation of the Bullet server in detail, present measurements of its performance, and compare this performance to that of the SUN file server running on the same hardware.>

Abstract Amoeba is a capability‐based distributed operating system designed for high‐performance interactions between clients and servers using the well‐known RPC model. The paper starts out by describing the architecture of the Amoeba system, which is typified by specialized components such as workstations, several services, a processor pool, and gateways that connect other Amoeba systems transparently over wide‐area networks. Next the RPC interface is described. The paper presents performance measurements of the Amoeba RPC on unloaded and loaded systems. The time to perform the simplest RPC between two user processes has been measured to be 1‐4 ms. Compared to SUN 3/50's RPC, Amoeba has one ninth of the delay, and over three times the throughput. Finally we describe the Amoeba file server. The Amoeba file server is so fast that it is limited by the communication bandwidth. To the best of our knowledge this is the fastest file server yet reported in the literature for this class of hardware.

A mechanism called voting with ghosts (VWG) is proposed for maintaining consistency of replicated data. VWG is an improvement of the weighted voting (WV) algorithm; it performs as well as the available copies (AC) algorithm, but unlike AC, works correctly in the face of network partitioning. A detailed description of the VWG method is given, and it is analyzed in the presence of node crashes and network partitions. Its performance is compared with that of WV and AC.>

It is shown how a highly compact representation of binary trees can be used as the basis of two access methods for dynamic files, called BDS-trees and S-trees, respectively. Both these methods preserve key-order and offer easy and efficient sequential access. They are different in the way the compact binary trees are used for searching. With a BDS-tree the search is a digital search using binary digits. Although the S-tree search is performed on a bit-by-bit basis as well, it will appear to be slightly different. Actually, with S-trees the compact binary trees are used to represent separators at low storage costs. As a result, the fan-out, and thus performance, of a B-tree can be improved by using within each index page an S-tree for representing separators efficiently.

Fifth generation computer systems will use large numbers of processors to achieve high performance.In this paper a capability-based operating system designed for this environment is discussed.Capability-based operating systems have traditionally required large, complex kernels to manage the use of capabilities.In our proposal, capability management is done entirely by user programs without giving up any of the protection aspects normally associated with capabilities.The basic idea is to use one-way functions and encryption to protect sensitive information.Various aspects of the proposed system are discussed.

Article Free Access Share on A distributed file service based on optimistic concurrency control Authors: Sape J. Mullender Centre for Mathematics and Computer Science, Amsterdam Centre for Mathematics and Computer Science, AmsterdamView Profile , Andrew S. Tanenbaum Vrije Universiteit, Amsterdam Vrije Universiteit, AmsterdamView Profile Authors Info & Claims SOSP '85: Proceedings of the tenth ACM symposium on Operating systems principlesDecember 1985 Pages 51–62https://doi.org/10.1145/323647.323634Online:01 December 1985Publication History 39citation680DownloadsMetricsTotal Citations39Total Downloads680Last 12 Months34Last 6 weeks3 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

Abstract An efficient disk organization is proposed. The basic idea is to store the first part of the file in the index (inode) block, instead of just storing pointers there. Empirical data are presented to show that this method offers better performance under certain circumstances than traditional methods.

Many portable compilers generate an intermediate code that is subsequently translated into the target machine's assembly language.In this paper a stack-machine-based intermediate code suitable for algebraic languages (e.g., PASCAL, C, FORTRAN) and most byte-addressed mini-and microcomputers is described.A table-driven peephole optimizer that improves this intermediate code is then discussed in detail and compared with other local optimization methods.Measurements show an improvement of about 15 percent, depending on the precise metric used.

PASCAL and ALGOL 68 language features are critically examined, compared and contrasted with each other. The emphasis is on the differences between the two languages, primarily in the areas of data types and statement types. Shortcomings in both languages are pointed out.

Abstract The areas in which programs are most unlikely to be portable are discussed. Attention is paid to programming languages, operating systems, file systems, I/O device characteristics, machine architecture and documentation. Pitfalls are indicated and in some cases solutions are suggested.

A method for quickly producing compilers for high level languages is described. The technique consists of feeding a description of the language to be translated to a general-purpose macro processor. Used in this way, the macro processor functions as a compiler-compiler, providing automatic parsing, lexical scanning, symbol table operations, and handling of syntactic errors. A complete syntactic and semantic description of a WHILE statement (except for Boolean expression processing) is given in only seven lines, as an example. A system programming language implemented by this method is discussed in order to illustrate the main ideas. The compiler produced for this language is compared to other compilers produced by conventional methods.

Abstract A set of programs running under a multiprogramming batch operating system on the CDC 6600 which provide remote users with a time sharing service is described. The basis for the system is the ability of a user program to create job control statements during execution, thereby tricking the operating system into treating it as an ordinary batch job. The text editor and the interactive debugging facilities are described. The performance of the system, known as the People's Time Sharing System (PTSS), and user reaction to it are also described.