Many geo-distributed services at web-scale companies still rely on databases (DBs) primarily optimized for single-site performance. At AT&T this is exemplified by services in the network control plane that rely on third-party software that uses DBs like MariaDB and PostgreSQL, which do not provide strict serializability across sites without a significant performance impact. Moreover, it is often impractical for these services to re-purpose their code to use newer DBs optimized for geo-distribution. In this paper, a novel drop-in solution for DB clustering across sites called Metric is presented that can be used by services without changing a single line of code. Metric leverages the single-site performance of an existing service's DB and combines it with a cross-site clustering solution based on an entry-consistent redo log that is specifically tailored for geo-distribution. Detailed correctness arguments are presented and extensive evaluations with various benchmarks show that Metric outperforms other solutions for the access patterns in our production use-cases where service replicas access different tables on different sites. In particular, Metric achieves up to 56% less latency and 5.2x higher throughput than MariaDB and PostgreSQL clustering, and up to 90% less latency and 26x higher throughput than CockroachDB and TiDB, systems that are designed to support geo-distribution.

Production networks are transitioning from the use of physical middleboxes to virtual network functions (VNFs), which makes it easy to construct highly-customized service chains of VNFs dynamically using software. Wide-area service chains are increasingly important given the emergence of heterogeneous execution platforms consisting of customer premise equipment (CPE), small edge cloud sites, and large centralized cloud data centers, since only part of the service chain can be deployed at the CPE and even the closest edge site may not always be able to process all the customers' traffic. Switchboard is a middleware for realizing and managing such an ecosystem of diverse VNFs and cloud platforms. It exploits principles from service-oriented architectures to treat VNFs as independent services, and provides a traffic routing platform shared by all VNFs. Moreover, Switchboard's global controller optimizes wide-area routes based on a holistic view of customer traffic as well as the resources available at VNFs and the underlying network. Switchboard globally optimized routes achieve up to 57% higher throughput and 49% lower latency than a distributed load balancing approach in a wide-area testbed. Its routing platform supports line-rate traffic with millions of concurrent flows.

The explosive growth of data due to the increasing adoption of cloud technologies in the enterprise has created a strong demand for more flexible, cost-effective, and scalable storage solutions. Many storage systems, however, are not well matched to the workloads they service due to the difficulty of configuring the storage system optimally a priori with only approximate knowledge of the workload characteristics. This paper shows how cloud-based orchestration can be leveraged to create flexible storage solutions that use continuous adaptation to tailor themselves to their target application workloads, and in doing so, provide superior performance, cost, and scalability over traditional fixed designs. To demonstrate this approach, we have built "SuperCell," a Ceph-based distributed storage solution with a recommendation engine for the storage configuration. SuperCell provides storage operators with real-time recommendations on how to reconfigure the storage system to optimize its performance, cost, and efficiency based on statistical storage modeling and data analysis of the actual workload. Using real cloud storage workloads, we experimentally demonstrate that SuperCell reduces the cost of storage systems by up to 48%, while meeting service level agreement (SLA) 99% of the time, a level that any static design fails to meet for the workloads.

A multi-site, distributed storage system deployment is frequently needed for disaster recovery. Traditional master-slave backup/restore solutions have their limitations and cannot meet the high data durability, system availability, and low latency required in many use cases. Software-defined storage (SDS) achieves flexibility, scalability, and cost-effectiveness through disaggregation of storage hardware from software and enables innovations in storage architectures. The open-source SDS Ceph solution can be used to build storage systems with high reliability using a disaster recovery (DR) configuration among multiple sites while maintaining cost-effectiveness. However, using multi-site erasure coding has the potential issue of longer read latency because of communication delays caused by data chunks distributed among multiple sites. This paper proposes location-conscious, multi-site erasure-coded Ceph storage that achieves both high reliability and lower read latency - even for sites that are geographically distant from each other. The investigation was conducted using a Ceph tool to confirm localities with the proposed Ceph CRUSH map, and experiments were conducted to evaluate I/O traffic to validate the proposed hypothesis. Our results show that the proposed location-conscious multi-site erasure-coded storage can be implemented in Ceph with both high reliability and low latency.

Load balancing is one of the most basic services needed by cloud applications. While today's clouds and load balancers provide highly customizable load distribution policies, they are forced out of necessity to ignore the impact of load balancing on the network. However, such network agnostic behavior can lead to inefficient utilization of cloud resources and poor performance, especially for upcoming network centric applications such as network function virtualization (NFV). But can network topology, a cloud property that is hidden from tenants, be made to effectively influence load balancing, a function that is intimately tied to per-tenant application structure that is largely invisible to the cloud? We answer that question in this paper by presenting Airfoil, a novel topology-aware distributed load balancer as a service (LBaaS) that takes network topology into consideration while providing cloud tenants with application-specific load balancing policies. By finding the best communication pattern with linear programming, the most efficient load balancing strategy is calculated without using any heuristics or approximations. We evaluate Airfoil over a range of scenarios from classical web applications to NFV pipelines, and show that it can decrease the network utilization of the most highly loaded network links by over 50%. For network constrained applications, such reductions imply a doubling of application capacity without any additional infrastructure.

A complex cloud application consists of virtual machines (VMs) running software such as web servers and load balancers, storage in the form of disk volumes, and network connections that enable communication between VMs and between VMs and disk volumes. The application is also associated with various requirements, including not only quantities such as the sizes of the VMs and disk volumes, but also quality of service (QoS) attributes such as throughput, latency, and reliability. This paper presents Ostro, an Open Stack-based scheduler that optimizes the utilization of data center resources, while satisfying the requirements of the cloud applications. The novelty of the approach realized by Ostro is that it makes holistic placement decisions, in which all the requirements of an application -- described using an application topology abstraction -- are considered jointly. Specific placement algorithms for application topologies are described including an estimate-based greedy algorithm and a time-bounded A algorithm. These algorithms can deal with complex topologies that have heterogeneous resource requirements, while still being scalable enough to handle the placement of hundreds of VMs and volumes across several thousands of host servers. The approach is evaluated using both extensive simulations and realistic experiments. These results show that Ostro significantly improves resource utilization when compared with naive approaches.

Accurate and up-to-date knowledge of how a cloud tenant's VMs utilize the underlying cloud infrastructure is essential for many cloud management tasks including tenant onboarding, optimized VM placement, performance optimization, and debugging. Unfortunately, existing solutions such as instrumentation at the hypervisors or standard networking protocols such as LLDP only provide a partial picture of cloud tenant's application structures and how they stress the underlying infrastructure. In this paper, we consider whether it is possible to use sFlow, a standardized mechanism for packet header sampling available in most commodity network switches, to extract such information in an accurate and scalable manner. We overcome the challenges posed by the purely passive and highly sampled nature of sFlow data, and describe a tool, sFinder, that automatically and continuously extracts such information. Our evaluation using sampled sFlow data from a real private cloud show that sFinder is accurate and efficient.

Organizations of all sizes are shifting their IT infrastructures to the cloud because of its cost efficiency and convenience. Because of the on-demand nature of the Infrastructure as a Service (IaaS) clouds, hundreds of thousands of virtual machines (VMs) may be deployed and terminated in a single large cloud data center each day. In this paper, we propose a content-based scheduling algorithm for the placement of VMs in data centers. We take advantage of the fact that it is possible to find identical disk blocks in different VM disk images with similar operating systems by scheduling VMs with high content similarity on the same hosts. That allows us to reduce the amount of data transferred when deploying a VM on a destination host. In this paper, we first present our study of content similarity between different VMs, based on a large set of VMs with different operating systems that represent the majority of popular operating systems in use today. Our analysis shows that content similarity between VMs with the same operating system and close version numbers (e.g., Ubuntu 12.04 vs. Ubuntu 11.10) can be as high as 60%. We also show that there is close to zero content similarity between VMs with different operating systems. Second, based on the above results, we designed a content-based scheduling algorithm that lowers the network traffic associated with transfer of VM disk images inside data centers. Our experimental results show that the amount of data transfer associated with deployment of VMs and transfer of virtual disk images can be lowered by more than 70%, resulting in significant savings in data center network utilization and congestion.

The problem of self-optimization and adaptation in the context of customizable systems is becoming increasingly important with the emergence of complex software systems and unpredictable execution environments. Here, a general framework for automatically deciding on when and how to adapt a system whenever it deviates from the desired behavior is presented. In this framework, the system's target behavior is described as a high-level policy that establishes goals for a set of performance indicators. The decision process is based on information provided independently for each component that describes the available adaptations, their impact on performance indicators, and any limitations or requirements. The technique consists of both offline and online phases. Offline, rules are generated specifying component adaptations that may help to achieve the established goals when a given change in the execution context occurs. Online, the corresponding rules are evaluated when a change occurs to choose which adaptations to perform. Experimental results using a prototype framework in the context of a web-based application demonstrate the effectiveness of this approach.

Automatic system monitoring and recovery has the potential to provide effective, low-cost ways to improve dependability in distributed software systems. However, automating recovery is challenging in practice because accurate fault diagnosis is hampered by monitoring tools and techniques that often have low fault coverage, poor fault localization, detection delays, and false positives. In this paper, we present a holistic model-based approach that overcomes these challenges and enables automatic recovery in distributed systems. To do so, it uses theoretically sound techniques including Bayesian estimation and Markov decision theory to provide controllers that choose good, if not optimal, recovery actions according to a user-defined optimization criteria. By combining monitoring and recovery, the approach realizes benefits that could not have been obtained by using them in isolation. We experimentally validate our framework by fault injection on realistic e-commerce systems.

Managing geographically dispersed deployments of complex multitier applications involves dealing with the substantial effects of network latency. However, the effects of network latency on an application's end-to-end performance can be far from obvious, thus making it difficult to predict the true impact of infrastructure changes such as network upgrades or server relocation on the users of an application. In this paper, we propose a new metric to quantify this impact called the link gradient. We develop a novel noise-resistant, nonintrusive technique to measure the link gradients in running systems without requiring knowledge of the system structure by using a combination of run-time delay injection and spectral analysis. We evaluate the intrusiveness and accuracy of our approach using micro-benchmarks and a deployment of two benchmark multitier Web applications on PlanetLab. Using these results, we show that link gradients can be used to accurately predict the impact of network latency changes on the end-to-end responsiveness of individual application transactions, even in new application configurations and without requiring a dedicated test environment.

Virtual machine technology enables agile system deployments in which software components can be cheaply moved, replicated, and allocated hardware resources in a controlled fashion. This paper examines how these facilities can be used to provide enhanced solutions to the classic problem of ensuring high availability while maintaining performance. By regenerating software components to restore the redundancy of a system whenever failures occur, we achieve improved availability compared to a system with a fixed redundancy level. Moreover, by smartly controlling component placement and resource allocation using information about application control flow and performance predictions from queuing models, we ensure that the resulting performance degradation is minimized. We consider an environment in which a collection of multitier enterprise applications operates across multiple hosts, racks, clusters, and data centers to maximize failure independence. Simulation results show that our proposed approach provides better availability and significantly lower degradation of system response times compared to traditional approaches.

Server consolidation based on virtualization is an important technique for improving power efficiency and resource utilization in cloud infrastructures. However, to ensure satisfactory performance on shared resources under changing application workloads, dynamic management of the resource pool via online adaptation is critical. The inherent tradeoffs between power and performance as well as between the cost of an adaptation and its benefits make such management challenging. In this paper, we present Mistral, a holistic controller framework that optimizes power consumption, performance benefits, and the transient costs incurred by various adaptations and the controller itself to maximize overall utility. Mistral can handle multiple distributed applications and large-scale infrastructures through a multi-level adaptation hierarchy and scalable optimization algorithm. We show that our approach outstrips other strategies that address the tradeoff between only two of the objectives (power, performance, and transient costs).

Geographically dispersed deployments of large and complex multitier enterprise applications introduce many challenges, including those involved in predicting the impact of network latency on end-to-end transaction response times. Here, a measurement-based approach to quantifying this impact using a new metric called the link gradient is presented. A non-intrusive technique for measuring the link gradient in running systems using delay injection and spectral analysis is presented, along with experimental results on PlanetLab that demonstrate that the link gradient can be used to predict end-to-end responsiveness, even in new and untested application configurations.

The ability of networked system software to adapt in a controlled manner to changes in the environment and requirements is crucial, but difficult to realize in complex systems with multiple interacting software layers/components. Typically, many components in a networked system implement adaptive behaviors and encapsulate their own adaptation logic (policies), making the whole system's adaptive behavior hard to analyze, coordinate, and test. This paper describes Cholla, a software architecture that separates the policy decisions of how and when adaptive components in networked systems react to their environment into separate centralized controllers that are constructed from composable rule sets. Centralizing policy decisions into controllers in Cholla facilitates the analysis, coordination, and testing of these policies, while the composable nature of these controllers allows them to be customized to changing user, application, and hardware demands. In addition to describing the architecture of Cholla, this paper also presents a Linux-based prototype implementation of this architecture that controls and coordinates adaptation policy decisions inside network protocols and multimedia applications. An experimental evaluation of this prototype demonstrates that Cholla's controller architecture enables component-based construction and customization of adaptation policies in networked systems, and that these policies can effectively control and coordinate adaptation.

This paper provides a technique, based on partially observable Markov decision processes (POMDPs), for building automatic recovery controllers to guide distributed system recovery in a way that provides provable assurances on the quality of the generated recovery actions even when the diagnostic information may be imprecise. Lower bounds on the cost of recovery are introduced and proved, and it is shown how the characteristics of the recovery process can be used to ensure that the lower bounds converge even on undiscounted models. The bounds used in an appropriate online controller provide it with provable termination properties. Simulation-based experimental results on a realistic e-commerce system demonstrate that the proposed bounds can be improved iteratively, and the resulting controller convincingly outperforms a controller that uses heuristics instead of bounds

Replication is a technique commonly used to increase the availability of services in distributed systems, including grid and Web services. While replication is relatively easy for services with fully deterministic behavior, grid and Web services often include nondeterministic operations. The traditional way to replicate such nondeterministic services is to use the primary-backup approach. While this is straightforward in synchronous systems with perfect failure detection, typical grid environments are not usually considered to be synchronous systems. This paper addresses the problem of replicating nondeterministic services by designing a protocol based on Paxos and proposing two performance optimizations suitable for replicated grid services. The first improves the performance in the case where some service operations do not change the service state, while the second optimizes grid service requests that use transactions. Evaluations done both on a local cluster and on Planet-Lab demonstrate that these optimizations significantly reduce the service response time and increase the throughput of replicated services

Media companies (and other organizations with large amounts of digital content) require prompt broadcast of extremely large files from a single source to a collection of geographically dispersed destinations. Due to the high cost of terrestrial networks of sufficient bandwidth, satellite networks are commonly used for such transfers. However, current satellite transfers rely on expensive error correction via forward error correction and whole-file retransmission. This paper presents a new, hybrid solution combining the advantages of satellite and terrestrial networks to provide cost-effective reliable file transfer. Specifically, we propose a new peer-to-peer scheme exploiting fast terrestrial networks and multiple receivers to recover from high loss rates (5% or more) in near real-time (latency < 400ms). This solution is efficient, robust under variable packet loss and connectivity, user tunable, scales well, and doubles bandwidth compared to existing approaches. The system has been validated via extensive simulations using a terrestrial network based on the AT&T common backbone core network

System call monitoring is a technique for detecting and controlling compromised applications by checking at runtime that each system call conforms to a policy that specifies the program's normal behavior. Here, we introduce a new approach to implementing system call monitoring based on authenticated system calls. An authenticated system call is a system call augmented with extra arguments that specify the policy for that call, and a cryptographic message authentication code that guarantees the integrity of the policy and the system call arguments. This extra information is used by the kernel to verify the system call. The version of the application in which regular system calls have been replaced by authenticated calls is generated automatically by an installer program that reads the application binary, uses static analysis to generate policies, and then rewrites the binary with the authenticated calls. This paper presents the approach, describes a prototype implementation based on Linux and the PLTO binary rewriting system, and gives experimental results suggesting that the approach is effective in protecting against compromised applications at modest cost

Grid middleware such as the Globus toolkit and grid standards such as the open grid services architecture (OGSA) are intended to be expressive enough for building distributed enterprise applications, yet their use in this context remains largely unexplored. Here, two specific issues related to the use of grid technology for Web application systems, an important class of enterprise applications is examined. The first is whether existing middleware can be used to move legacy Web applications to a grid platform, and if so, how; the second is whether such grid-enabling brings advantages in terms of additional functionality, enhanced performance, or simplified management. These issues are addressed by grid-enabling a sample J2EE Internet banking application and comparing its performance with the original version, and then designing a scalable software architecture that can use the dynamic resource allocation facilities of grids to handle fluctuating client demands. Initial performance studies suggest that the architecture can indeed scale in response to changes in client load, indicating that the application of grid technology in this context is potentially useful as a way to enhance the manageability of the overall system.

Grid computing infrastructures and applications are increasingly diverse with networks ranging from very high bandwidth optical networks to wireless networks and applications ranging from remote visualization to sensor data collection. For such environments, standard transport protocols such as TCP and UDP are not always sufficient or optimal given their fixed set of properties and their lack of flexibility. As an alternative, we present H-CTP, a high-performance configurable transport protocol that can be used to build customized transport services for a wide range of grid computing scenarios. H-CTP is based on an earlier configurable transport protocol called CTP, but with a collection of optimizations that meet the challenge of providing configurability while maintaining performance that meets the requirements of such demanding applications. This paper motivates the need for customizable transport in this area, presents the design of H-CTP, and gives results from performance studies that compare H-CTP with both CTP and TCP. These show, for example, that H-CTP is able to achieve throughput of over 900 Mbps across Gigabit links. Three diverse grid scenarios are used as example applications and for the H-CTP/TCP comparisons: remote visualization, fast message passing, and sensor grids.

System call monitoring is a technique for detecting and controlling compromised applications by checking at runtime that each system call conforms to a policy that specifies the program's normal behavior. A new approach to system call monitoring based on authenticated system calls is introduced. An authenticated system call is a system call augmented with extra arguments that specify the policy for that call and a cryptographic message authentication code (MAC) that guarantees the integrity of the policy and the system call arguments. This extra information is used by the kernel to verify the system call. The version of the application in which regular system calls have been replaced by authenticated calls is generated automatically by an installer program that reads the application binary, uses static analysis to generate policies, and then rewrites the binary with the authenticated calls. This paper presents the approach, describes a prototype implementation based on Linux and the PLTO binary rewriting system, and gives experimental results suggesting that the approach is effective in protecting against compromised applications at modest cost.

The past few years have seen an increasingly tight link between grid computing and Web services, with the latest standards defining a grid computing architecture as a set of services built using Web services standards and protocols. However, the reputation of these technologies (SOAP, XML, WSDL, HTTP) is that they are heavyweight and slow, something that is potentially a concern given the current and anticipated application mix for high performance grid architectures. This paper reports the results of a performance evaluation carried out on Globus 3.9.4, a reference implementation of the new GGF standards that are built on the Web services resource framework (WSRF). The evaluation approach combines low interference measurement (black box) techniques with more sophisticated sampling-based profiling (gray box) techniques. The results indicate possible opportunities for optimization, as well as provide useful input for the designers of grid services.

Automatic system monitoring and recovery has the potential to provide a low-cost solution for high availability. However, automating recovery is difficult in practice because of the challenge of accurate fault diagnosis in the presence of low coverage, poor localization ability, and false positives that are inherent in many widely used monitoring techniques. In this paper, we present a holistic model-based approach that overcomes these challenges and enables automatic recovery in distributed systems. To do so, it uses theoretically sound techniques including Bayesian estimation and Markov decision theory to provide controllers that choose good, if not optimal, recovery actions according to a user-defined optimization criteria. By combining monitoring and recovery, the approach realizes benefits that could not have been obtained by using them in isolation. In this paper, we present two recovery algorithms with complementary properties and trade-offs, and validate our algorithms (through simulation) by fault injection on a realistic e-commerce system.

The combination of grid technology and Web services has produced an attractive platform for deploying distributed applications: grid services, as represented by the Open Grid Services Infrastructure (OGSI) and its Globus toolkit implementation. As the use of grid services grows in popularity, tolerating failures becomes increasingly important. This work addresses the problem of building a reliable and highly-available grid service by replicating the service on two or more hosts using the primary-backup approach. The primary goal is to evaluate the ease and efficiency with which this can be done, by first designing a primary-backup protocol using OGSI, and then implementing it using Globus to evaluate performance implications and tradeoffs. We compared three implementations: one that makes heavy use of the notification interface defined in OGSI, one that uses standard grid service requests instead of notification, and one that uses low-level socket primitives. The overall conclusion is that, while the performance penalty of using Globus primitives - especially notification - for replica coordination can be significant, the OGSI model is suitable for building highly-available services and it makes the task of engineering such services easier.

Mobile service platforms are used to facilitate access to enterprise services such as email, product inventory, or design drawing databases by a wide range of mobile devices using a variety of access protocols. This paper presents a quality of service (QoS) architecture that allows flexible combinations of dependability attributes such as reliability, timeliness, and security to be enforced on a per service request basis. In addition to components that implement the underlying dependability techniques, the architecture includes policy components that evaluate a request's requirements and dynamically determine an appropriate execution strategy. The architecture has been integrated into an experimental version of iMobile, a mobile service platform being developed at AT&T. This paper describes the design and implementation of the architecture, and gives initial experimental results for the iMobile prototype.

Abstract Applications built on networked collections of computers are increasingly using distributed object platforms such as CORBA,Java Remote Method Invocation (RMI), and DCOM to standardize object interactions. With this increased use comes the increased need for enhanced quality of service (QoS) attributes related to fault tolerance, security, and timeliness. This paper describes an architecture called CQoS (configurable QoS) for implementing such enhancements in a transparent, highly customizable, and portable manner. CQoS consists of two parts: application‐ and platform‐dependent interceptors and generic QoS components. The generic QoS components are implemented using Cactus, a system for building highly configurable protocols and services in distributed systems. The CQoS architecture and the interfaces between the different components are described, together with implementations of QoS attributes using Cactus and interceptors for CORBA and Java RMI. Experimental results are given for a test application executing on a Linux cluster using Cactus/J, the Java implementation of Cactus. Compared with other approaches, CQoS emphasizes portability across different distributed object platforms, while the use of Cactus allows custom combinations of fault‐tolerance, security, and timeliness attributes to be realized on a per‐object basis in a straightforward way. Copyright © 2003 John Wiley & Sons, Ltd.

Survivable systems-that is, systems that can continue to provide service despite failures, intrusions, and other threats-are increasingly needed in a wide variety of civilian and military application areas. As a step toward realizing such systems, this paper advocates the use of redundancy and adaptation to build survivable services that can provide core functionality for implementing survivability in networked environments. An approach to building such services using these techniques is described and a concrete example involving a survivable communication service is given. This service is based on Cactus, a system for building highly configurable network protocols that offers the flexibility needed to easily add redundant and adaptive components. Initial performance results for a prototype implementation of the communication service built using Cactus/C2.1 running on Linux are also given.

Events are used as a fundamental abstraction in programs ranging from graphical user interfaces (GUIs) to systems for building customized network protocols. While providing a flexible structuring and execution paradigm, events have the potentially serious drawback of extra execution overhead due to the indirection between modules that raise events and those that handle them. This paper describes an approach to addressing this issue using static optimization techniques. This approach, which exploits the underlying predictability often exhibited by event-based programs, is based on first profiling the program to identify commonly occurring event sequences. A variety of techniques that use the resulting profile information are then applied to the program to reduce the overheads associated with such mechanisms as indirect function calls and argument marshaling. In addition to describing the overall approach, experimental results are given that demonstrate the effectiveness of the techniques. These results are from event-based programs written for X Windows, a system for building GUIs, and Cactus, a system for constructing highly configurable distributed services and network protocols.

Traditional distributed system services that provide guarantees related to confidentiality, integrity, and authenticity enhance security, but are not survivable since each attribute is implemented by a single method. This paper advocates the use of redundancy to increase survivability by using multiple methods to implement each security attribute and doing so in ways that can vary unpredictably. As a concrete example, the design and implementation of a highly configurable secure communication service called SecComm are presented. The service has been implemented using Cactus, a system for building highly configurable protocols and services for distributed systems. Initial performance results for a prototype implementation on Linux are also given.

Summary form only given. Our position is that the true potential of adaptation can only be realized if support is provided for more general solutions, including adaptations that span multiple hosts and multiple system components, and algorithmic adaptations that involve changing the underlying algorithms used by the system at runtime. Such a general solution must, however, address the difficult issues related to these types of adaptations. Adaptation by multiple related components, for example, must be coordinated so that these adaptations work together to implement consistent adaptation policies. Likewise, large-scale algorithmic adaptations need to be coordinated using graceful adaptation strategies in which as much normal processing as possible continues during the changeover. Here, we summarize our approach to addressing these problems in Cactus, a system for constructing highly-configurable distributed services and protocols.

Adaptive software that can react to changes in the execution environment or user requirements by switching algorithms at run time is powerful yet difficult to implement, especially in distributed systems. This paper describes a software architecture for constructing such adaptive software and a graceful adaptive protocol that allows adaptations to be made in a coordinated manner across hosts transparently to the application. A realization of the architecture based on Cactus, a system for constructing highly configurable distributed services and protocols, is also presented. The approach is illustrated by outlining examples of adaptive components from a group communication service.

The ability to configure transport protocols from collections of smaller software modules allows the characteristics of the protocol to be customized for a specific application or network technology. This paper describes an approach to building such customized protocols using Cactus, a system in which micro-protocols implementing individual attributes of transport can be combined into a composite protocol that realizes the desired overall functionality. In contrast with similar systems, Cactus supports non-hierarchical module composition and event-driven execution, both of which increase flexibility and allow finer-grain modules implementing orthogonal properties. To illustrate this approach, the design and implementation of a configurable transport protocol called CTP is presented. CTP allows customization of a number of properties including reliable transmission, congestion detection and control, jitter control, and message ordering. This suite of micro-protocols has been implemented using Cactus/C 2.0 on Red Hat Linux 6.2, with initial experimental results indicating that the ability to target the guarantees more precisely to the needs of applications can in fact result in better performance.

Abstract Network communication services that can be configured to customize functionality provide significant advantages over monolithic versions, but can be difficult to construct if the services must also provide real‐time guarantees on message delivery. This paper describes how practical issues related to the combination of configurability and real time have been addressed in real‐time dependable (RTD) channels, a communication abstraction that has been prototyped using the Cactus system. The architecture and implementation of RTD channels are described, including facilities for translating an application's quality of service requirements into configuration‐specific resource requirements, and an admission control architecture that uses system‐wide information to determine whether sufficient resources exist to create new channels. In addition, the results of experiments that demonstrate that the desired channel properties—including real‐time guarantees—are provided for various configurations are presented. Finally, practical problems and lessons learned from implementing RTD channels on the general‐purpose MK 7.3 Mach operating system are discussed. Copyright © 2001 John Wiley & Sons, Ltd.

Mobile computing systems present challenges for message routing, support for disconnected operation, and providing quality of service guarantees related to latency, bandwidth and jitter. While multiple approaches have been developed, existing systems typically support only a small set of solutions in each area. This paper describes the design of a collection of communication protocols that supports multiple solutions within a single integrated framework based on the Coyote system. These protocols are constructed by subdividing the required functionality into orthogonal functions and then implementing variants of these functions as fine-grain software modules called micro-protocols. A custom service is then realized by choosing micro-protocols based on functionality and configuring them together with a standard runtime system that implements an event-oriented execution model.

Communication services that provide enhanced Quality of Service (QoS) guarantees related to dependability and real time are important for many applications in distributed systems. This paper presents real-time dependable (RTD) channels, a communication-oriented abstraction that can be configured to meet the QoS requirements of a variety of distributed applications. This customization ability is based on using CactusRT, a system that supports the construction of middleware services out of software modules called micro-protocols. Each micro-protocol implements a different semantic property or property variant and interacts with other micro-protocols using an event-driven model supported by the CactusRT runtime system. In addition to RTD channels CactusRT and its implementation are described. This prototype executes on a cluster of Pentium PCs running the OpenGroup/RI MK 7.3 Mach real-time operating system and CORDS, a system for building network protocols based on the x-kernel.

The current technology of parallel and distributed systems allows users to exploit a variety of resources across networks. However, the support provided is often insufficient for computational scientists to simulate complicated real-world scenarios in which different kinds of scientific applications need to be combined to perform high fidelity simulations. As a result, users waste a large amount of time and effort developing custom techniques for performing semantic-level communication between heterogeneous scientific simulations. This paper describes a new middleware system that provides high-level transparency in the form of agents that automatically transfer and transform data between simulations that use different mathematical and physical modeling approaches. Based on a specification that correlates different discrete points in finite difference method (FDM), finite element method (FEM) or particle simulations, the agents provide a variety of techniques for semantically transforming the values associated with correlated points and automatically determine to which processes the values must be transferred. To facilitate use and minimize impact on user programs, the agent system includes three types of library calls that manage task identification, register different kinds of discrete points and construct a correlation table according to the specification, and transfer messages that incorporate extraction and transformation of the values on the correlated points. Another library specially optimized for parallel simulations that use a SPMD (Single Program Multiple Data stream) structure is also offered to control communication through the agents. A prototype system has been developed on the Hitachi SR2201 parallel machine as well as workstation clusters, and applied to several example applications. These include an advanced device simulation that combines quantum transport simulation with electric potential simulation, and a simulation of thermal flow resulting from high-frequency device operation that hybridizes molecular dynamics simulation with macroscopic continuum simulation. These combinations can be efficiently realized using the small number of library calls within the agent system together with additional routines that change the data formats of discrete points. The time overhead of the agent calculations is shown experimentally to agree closely with the theoretically-predicted values modeled as a function of the number of discrete points and domain decomposition in parallel simulations. This value becomes insignificant compared with that of the simulation processes for heterogeneous large-scale simulations.

A membership service is used to maintain information about which sites are functioning in a distributed system at any given time. Many such services have been defined, with each implementing a unique combination of properties that simplify the construction of higher levels of the system. Despite this wealth of possibilities, however, any given service typically realizes only one set of properties, which makes it difficult to tailor the service provided to the specific needs of the application. Here, a configurable membership service that addresses this problem is described. This service is based on decomposing membership into its constituent abstract properties and then implementing these properties as separate software modules called micro-protocols that can be configured together to produce a customized membership service. A prototype C++ implementation of the membership service for a simulated distributed environment is also described.

Communication-oriented abstractions such as atomic multicast, group RPC, and protocols for location-independent mobile computing can simplify the development of complex applications built on distributed systems. This article describes Coyote, a system that supports the construction of highly modular and configurable versions of such abstractions. Coyote extends the notion of protocol objects and hierarchical composition found in existing systems with support for finer-grain microprotocol objects and a nonhierarchical composition scheme for use within a single layer of a protocol stack. A customized service is constructed by selecting microprotocols based on their semantic guarantees and configuring them together with a standard runtime system to form a composite protocol implementing the service. This composite protocol is then composed hierarchically with other protocols to form a complete network subsystem. The overall approach is described and illustrated with examples of services that have been constructed using Coyote, including atomic multicast, group RPC, membership, and mobile computing protocols. A prototype implementation based on extending x -kernel version 3.2 running on Mach 3.0 with support for microprotocols is also presented, together with performance results from a suite of microprotocols from which over 60 variants of group RPC can be constructed.

Access control involves maintaining information about which users can access system resources and ensuring that access is restricted to authorized users. In wide-area networks such as the Internet, implementing access control is difficult, since resources may be replicated, the task of managing access rights may be distributed among multiple sites, and events such as host failures, host recoveries, and network partitions must be dealt with. This paper explores the problem of access control in such an environment, and in particular the inherent tradeoff between security, availability, and performance. Techniques for dealing with access control in the presence of partitions are presented and used as the basis for an algorithm that allows application control over these tradeoffs.

In scientific applications where parallel computation is used to model physical processes, enhancing the user's ability to monitor and control programs executing on remote parallel machines can improve the overall experimental process. Here, a simple approach to providing such facilities is presented in which a scientific visualization system and a remote parallel computation are incorporated into a single metacomputation using the Schooner software interconnection system. This scheme gives the user the ability to, for example, select dynamically the parallel platform to be used, monitor the progress of the computation, and modify parameters. To illustrate this approach, a series of experiments is described in which the AVS scientific visualization system and a parallel neural net code executing on either an Intel Paragon, Sequent Symmetry, or PVM-based Sun Sparcstation cluster are interconnected. These experiments demonstrate not just the feasibility of structuring parallel computations as part of a larger metacomputation using Schooner, but also that these benefits can be achieved with an adjustable cost that can be tuned to the specific needs of the application. © 1997 John Wiley & Sons, Ltd.

Current Remote Procedure Call (RPC) services implement a variety of semantics, with many of the differences related to how communication and server failures are handled. The list increases even more when considering group RPC, a variant of RPC often used for fault-tolerance where an invocation is sent to a group of servers rather than one. This paper presents an approach to constructing group RPC in which a single configurable system is used to build different variants of the service. The approach is based on implementing each property as a separate software module called a micro-protocol, and then configuring the micro-protocols needed to implement the desired service together using a software framework based on the x-kernel. The properties of point-to-point and group RPC are identified and classified, and the general execution model described. An example consisting of a modular implementation of a group RPC service is given to illustrate the approach. Dependency issues that restrict configurability are also addressed.

A membership service is used in a distributed system to maintain information about which sites are functioning and which have failed at any given time. Such services have proven to be fundamental for constructing distributed applications, with many example services and algorithms defined in the literature. Despite these efforts, however, little has been done on examining the abstract properties important to membership independent of a given service. Here, these properties are identified and characterized. Message ordering graphs are used to specify the effect of each property on the message flow as seen by the application, and dependency graphs are used to characterize the relationship between properties. These graphs help differentiate existing services, as well as facilitate the design of new services in which only those properties actually required by an application are included.>

New distributed computing applications are driving the development of more specialized protocols, as well as demanding greater control over the communication substrate. Here, a network subsystem that supports modular, fine-grained construction of high-level protocols such as atomic multicast and group RPC is described. The approach is based on extending the standard hierarchical model of the x-kernel with composite protocols in which micro-protocol objects are composed within a standard runtime framework. Each micro-protocol realizes a separate semantic property, leading to a highly modular and configurable implementation. In contrast with similar systems, this approach provides finer granularity and more flexible inter-object communication. The design and prototype implementation runing on Mach are described. Performance results are also given for a micro-protocol suite implementing variants of group RPC.

Good programming language support can simplify the task of writing fault-tolerant distributed software. Here, an approach to providing such support is described in which a general high-level distributed programming language is augmented with mechanisms for fault tolerance. Unlike approaches based on sequential languages or specialized languages oriented towards a given fault-tolerance technique, this approach gives the programmer a high level of abstraction, while still maintaining flexibility and execution efficiency. The paper first describes a programming model that captures the important characteristics that should be supported by a programming language of this type. It then presents a realization of this approach in the form of FT-SR, a programming language that augments the SR distributed programming language with features for replication, recovery, and failure notification. In addition to outlining these extensions, an example program consisting of a data manager and its associated stable storage is given. Finally, an implementation of the language that uses the x-kernel and runs standalone on a network of Sun workstations is discussed. The overall structure and several of the algorithms used in the runtime are interesting in their own right.>

Linda is a language for programming parallel applications whose most notable feature is a distributed shared memory called tuple space. While suitable for a wide variety of programs, one shortcoming of the language as commonly defined and implemented is a lack of support for writing programs that can tolerate failures in the underlying computing platform. This paper describes FT-Linda, a version of Linda that addresses this problem by providing two major enhancements that facilitate the writing of fault-tolerant applications: stable tuple spaces and atomic execution of tuple space operations. The former is a type of stable storage in which tuple values are guaranteed to persist across failures, while the latter allows collections of tuple operations to be executed in an all-or-nothing fashion despite failures and concurrency. The design of these enhancements is presented in detail and illustrated by examples drawn from both the Linda and fault-tolerance domains. An implementation of FT-Linda for a network of workstations is also described. The design is based on replicating the contents of stable tuple spaces to provide failure resilience and then updating the copies using atomic multicast. This strategy allows an efficient implementation in which only a single multicast message is needed for each atomic collection of tuple space operations.>

Abstract The Numerical Propulsion System Simulation (NPSS) project has been initiated by NASA to explore the use of computer simulation in the development of new aircraft propulsion technology. With this approach, each engine component is modeled by a separate computational code, with a simulation executive connecting the codes and modeling component interactions. Since each code potentially executes on a different machine in a network, a simulation run is a heterogeneous distributed program in which diverse software and hardware elements are incorporated into a single computation. In the paper a prototype simulation executive that supports this type of programming is described. The two components of this executive are the AVS scientific visualization system and the Schooner heterogeneous remote procedure call (RPC) facility. In addition, the match between Schooner's capabilities and the needs of NPSS is evaluated based on our experience with a collection of test codes. The basic conclusion is that, while Schooner fared well in general, it exhibited certain deficiencies that dictated changes in its design and implementation. This discussion not only documents the evolution of Schooner, but also serves to highlight the practical problems that can be encountered when dealing with heterogeneity and distribution in such applications.

The numerical propulsion system simulation (NPSS) project has been initiated by NASA to expand the use of computer simulation in the development of new aircraft engines. A major goal is to study interactions between engine components using multiple computational codes, each modeling a separate component and potentially executing on a different machine in a network. Thus, a simulation run is a heterogeneous distributed program controlled by a simulation executive. This paper describes a prototype executive composed of the AVS visualization system and the Schooner heterogeneous remote procedure call (RPC) facility. In addition, the match between Schooner's capabilities and the needs of NPSS is evaluated based on the authors experience with a collection of test codes. This discussion not only documents the evolution of Schooner, but also serves to highlight the practical problems that can be encountered when dealing with heterogeneity and distribution in such applications.>

Consul is a system designed to support the use of fault-tolerance techniques in the construction of fault-tolerant distributed systems structured according to the state machine approach. The way in which modularity has been used in the design and implementation of Consul is described. The approach makes it easy to configure a system customized to the needs of a specific application and facilitates the development of the individual components that make up Consul.>

Modularization is a well-known technique for simplifying complex software. An approach to modularizing fault-tolerant protocols such as reliable multicast and membership is described. The approach is based on implementing a protocol's individual properties as separate microprotocols and then combining selected microprotocols using an event-driven software framework. A system is constructed by composing these frameworks with traditional network protocols using standard hierarchical techniques. In addition to simplifying the software, this model helps clarify the dependencies among properties of fault-tolerant protocols and makes it possible to construct systems that are customized to the specifics of the application or underlying architecture. An example involving reliable group multicast is given, together with a description of a prototype implementation using the SR concurrent programming language.>

Abstract The use of modularity in the design and implementation of complex software simplifies the development process, as well as facilitating the construction of customized configurations. This paper describes our experience using modularity in Consul, a communication substrate used for constructing fault‐tolerant distributed programs. First, Consul is presented as a case study of how modularity is feasible in both the design and the implementation of such systems. Secondly, general lessons about modularity in fault‐tolerant systems based on our experience with Consul are given. Issues that are addressed include deciding how the system is divided into various modules, dealing with problems that result when protocols are combined, and ensuring that the underlying object infrastructure provides adequate support. The key observation is that the modularization process is most affected by dependencies between modules, both direct dependencies caused by one module explicitly using another's operation and indirect dependencies where one module is affected by another without direct interaction. Although our observations are based on designing and implementing Consul, the lessons are applicable to any fault‐tolerant distributed system.

The design of FT-SR, a programming language based on SR and oriented toward constructing fault-tolerant distributed systems, is presented. The language, which is based on the existing SR language, is unique in that it has been designed to support equally well any of the programming paradigms that have been developed for this type of system, including the object/action model, the restartable action paradigm, and the state machine approach. To do this, the language is designed to support the implementation of systems modeled as collections of fail-stop atomic objects. Such objects execute operations as atomic actions except when a failure or series of failures cause underlying implementation assumptions to be violated; in this case, notification is provided. An example program consisting of a data manager and its associated stable storage is given.>

Psync is an IPC protocol that explicitly preserves the partial order of messages exchanged among a set of processes. A description is given of how Psync can be used to implement replicated objects in the presence of network and host failures. Unlike conventional algorithms that depend on an underlying mechanism that totally orders messages for implementing replicated objects, the authors' approach exploits the partial order provided by Psync to achieve additional concurrency.>

When processes in a network communicate, the messages they exchange define a partial ordering of externally visible events. While the significance of this partial order in distributed computing is well understood, it has not been made an explicit part of the communication substrate upon which distributed programs are implemented. This paper describes a new interprocess communication mechanism, called Psync , that explicitly encodes this partial ordering with each message. The paper shows how Psync can be efficiently implemented on an unreliable communications network, and it demonstrates how conversations serve as an elegant foundation for ordering messages exchanged in a distributed computation and for recovering from processor failures.

Abstract The Mixed‐Language Programming (MLP) System is a simple system that facilitates construction of sequential programs in which procedures can be written in different programming languages to exploit heterogeneity in language functionality. In addition, MLP provides a simple remote procedure call (RPC) facility that allows heterogeneity in machine functionality to be exploited. To minimize implementation cost, the system does not solve all of the problems related to mixed‐language programming; rather, MLP is designed to handle common situations well. Among the unique aspects of MLP are its advanced facilities, which allow complex situations to be handled with user intervention; for example, these facilities allow arguments of a type not defined by a language to be used by procedures written in that language. This paper overviews the use of MLP and describes its implementation. In addition, two programs that have been written using the MLP system—a small database system and a collection of plot routines—are discussed. The system executes on a collection of Vaxes and Suns running Berkeley UNIX. Currently supported languages are C, Pascal and Icon.

Abstract This paper describes two mechanisms – reproduction sets and metafiles – that provide low‐cost, semi‐automatic file replication and location transparency facilities for an interconnected collection of machines running Berkeley Unix. A reproduction set is a collection of files that the system attempts to keep identical; this is done on a ‘best effort’ basis, with the system relying on the user to handle unusual situations. A metafile is a special file that contains symbolic pathnames of other files, each of which may be on any machine in the network; opening a metafile results in opening an available constituent file. Examples are given to illustrate the use of these mechanisms. Their implementation and performance are also described.

This paper describes the design of the Saguaro operating system for computers connected by a local-area network. Systems constructed on such an architecture have the potential advantages of concurrency and robustness. In Saguaro, these advantages are made available to the user through several mechanisms. One is channels, an interprocess communication and synchronization facility that allows the input and output of different commands to be connected to form general graphs of communicating processes. Two additional mechanisms are provided to support semitransparent file replication and access: reproduction sets and metafiles. A reproduction set is a collection of files that the system attempts to keep identical on a "best effort" basis. A metafile is a special file that contains symbolic pathnames of other files; when a metafile is opened, the system selects an available constituent file and opens it instead. The advantages of concurrency and robustness are also realized at the system level by the use of pools of server processes and decentralized allocation protocols. Saguaro also makes extensive use of a type system to describe user data such as files and to specify the types of arguments to commands and procedures. This enables the system to assist in type checking and leads to a user interface in which command-specific templates are available to facilitate command invocation.

An approach for facilitating mixed language programming in distributed systems is presented. It is based on adding a generic remote procedure call facility to each language, and the use of a type system to describe procedural interfaces, as well as data to be transferred between procedures. This type scheme also specifies a machine-independent representation for all data. By defining standard mappings for each programming language, the data conversions required for cross-langauge calls may be performed, automatically in most cases, by active agents that provide the interface between program components written in different languages. When necessary, explicit control of the conversation is possible. A prototype implementation of a system based on this approach has been constructed on a collection of machines running Berkeley UNIX®.

A technique is presented for estimating the performance of programs written for execution on fail-stop processors. It is based on modeling the program as a discrete-time Markov chain and then using z-transforms to derive a probability distribution for time to completion.

Inference rules are derived for proving partial correctness of concurrent programs that use message passing.These rules extend the notion of a satisfaction proof, first proposed for proving correctness of programs that use synchronous message-passing, to asynchronous message-passing, rendezvous, and remote procedures.Two types of asynchronous message-passing are considered: unreliable datagrams and reliable virtual circuits.The proof rules show how interference can arise and be controlled.

Fault-

Message passing provides a way for concurrently executing processes to communicate and synchronize. In this paper, we develop proof rules for asynchronous message-passing primitives (i.e. “send no-wait”). Two benefits accrue from this. The obvious one is that partial correctness proofs can be written for concurrent programs that use such primitives. This allows programs to be understood as predicate transformers, instead of by contemplating all possible execution interleavings. The second benefit is that the proof rules and their derivation shed light on how interference arises when message-passing operations are used and on how this interference can be controlled. This provides insight into programming techniques to eliminate interference in programs that involve asynchronous activity. Three safe uses of asynchronous message passing are described here: the transfer of values, the transfer of monotonic predicates, and the use of acknowledgments.