We propose a new paradigm for building scalable distributed systems. Our approach does not require dealing with message-passing protocols, a major complication in existing distributed systems. Instead, developers just design and manipulate data structures within our service called Sinfonia. Sinfonia keeps data for applications on a set of memory nodes, each exporting a linear address space. At the core of Sinfonia is a new minitransaction primitive that enables efficient and consistent access to data, while hiding the complexities that arise from concurrency and failures. Using Sinfonia, we implemented two very different and complex applications in a few months: a cluster file system and a group communication service. Our implementations perform well and scale to hundreds of machines.

We propose a new paradigm for building scalable distributed systems. Our approach does not require dealing with message-passing protocols -- a major complication in existing distributed systems. Instead, developers just design and manipulate data structures within our service called Sinfonia. Sinfonia keeps data for applications on a set of memory nodes, each exporting a linear address space. At the core of Sinfonia is a novel minitransaction primitive that enables efficient and consistent access to data, while hiding the complexities that arise from concurrency and failures. Using Sinfonia, we implemented two very different and complex applications in a few months: a cluster file system and a group communication service. Our implementations perform well and scale to hundreds of machines.

Ensuring performance isolation and differentiation among workloads that share a storage infrastructure is a basic requirement in consolidated data centers. Existing management tools rely on resource provisioning to meet performance goals; they require detailed knowledge of the system characteristics and the workloads. Provisioning is inherently slow to react to system and workload dynamics and, in the general case, it is not practical to provision for the worst case.We propose a software-only solution that ensures predictable performance for storage access. It is applicable to a wide range of storage systems and makes no assumptions about workload characteristics. We use an online feedback loop with an adaptive controller that throttles storage access requests to ensure that the available system throughput is shared among workloads according to their performance goals and their relative importance. The controller considers the system as a “black box” and adapts automatically to system and workload changes. The controller is distributed to ensure high availability under overload conditions, and it can be used for both block and file access protocols. The evaluation of Triage , our experimental prototype, demonstrates workload isolation and differentiation in an overloaded cluster file-system where workloads and system components are changing.

Data replication is used extensively in wide-area distributed systems to achieve low data-access latency. A large number of heuristics have been proposed to perform replica placement. Practical experience indicates that the choice of heuristic makes a big difference in terms of the cost of required infrastructure (e.g., storage capacity and network bandwidth), depending on system topology, workload and performance goals. We describe a method to assist system designers choose placement heuristics that meet their performance goals for the lowest possible infrastructure cost. Existing heuristics are classified according to a number of properties. The inherent cost (lower bound) for each class of heuristics is obtained for given system, workload and performance goals. The system designer compares different classes of heuristics on the basis of these lower bounds. Experimental results show that choosing a heuristic with the proposed methodology results in up to 7 times lower cost compared to using an "obvious " heuristic, such as caching.

Ensuring performance isolation and differentiation among workloads that share a storage infrastructure is a basic requirement in consolidated data centers. Existing management tools rely on resource provisioning to meet performance goals; they require detailed knowledge of the system characteristics and the workloads. Provisioning is inherently slow to react to system and workload dynamics, and in the general case, it is impossible to provision for the worst case. We propose a software-only solution that ensures predictable performance for storage access. It is applicable to a wide range of storage systems and makes no assumptions about workload characteristics. We use an on-line feedback loop with an adaptive controller that throttles storage access requests to ensure that the available system throughput is shared among workloads according to their performance goals and their relative importance. The controller considers the system as a "black box" and adapts automatically to system and workload changes. The controller is distributed to ensure high availability under overload conditions, and it can be used for both block and file access protocols. The evaluation of Triage, our experimental prototype, demonstrates workload isolation and differentiation, in an overloaded cluster file-system where workloads and system components are changing.

A number of ongoing research projects follow a partition-based approach to provide highly scalable distributed storage services. These systems maintain namespaces that reference objects distributed across multiple locations in the system. Typically, atomic commitment protocols, such as 2-phase commit, are used for updating the namespace, in order to guarantee its consistency even in the presence of failures. Atomic commitment protocols are known to impose a high overhead to failure-free execution. Furthermore, they use conservative recovery procedures and may considerably restrict the concurrency of overlapping operations in the system. This paper proposes a set of new protocols implementing the fundamental operations in a distributed namespace. The protocols impose a minimal overhead to failure-free execution. They are robust against both communication and host failures, and use aggressive recovery procedures to re-execute incomplete operations. The proposed protocols are compared with their 2-phase commit counterparts and are shown to outperform them in all critical performance factors: communication round-trips, synchronous I/O, operation concurrency.

Practical experience indicates that the definition of realworld workflow applications is a complex and error-prone process. Existing workflow management systems provide the means, in the best case, for very primitive syntactic verification, which is not enough to guarantee the overall correctness and robustness of workflow applications. The paper presents an approach for formal verification of workflow schemas (definitions). Workflow behaviour is modelled by means of an automata-based method, which facilitates exhaustive compositional reachability analysis. The workflow behaviour can then be analysed and checked for safety and liveness properties. The model generation and the analysis procedure are governed by well-defined rules that can be fully automated. Therefore, the approach is accessible by designers who are not experts in formal methods. 1.

Addresses the problem of replicated service provision in distributed systems. Existing systems that follow the state machine approach concentrate on the synchronization of the server replicas and do not consider the problem of client interaction with the server group. This paper analyzes client interaction and identifies a number of access protocols to meet a range of client requirements and system models. The paper demonstrates that protocols for the "open" group model-clients external to the group of servers-satisfy the requirements of the state machine approach, even when replication is transparent to the clients. Experimental performance results indicate that the "open" model is clearly desirable when the service is used by a large, dynamically changing set of clients, a situation which pertains to Internet service provision.

The paper addresses the problem of client-service interaction in the case of replicated service provision. Existing systems that follow the State Machine approach concentrate on the synchronisation of the server replicas and do not consider the problem of client interaction with the sewer group. Client interaction is analysed and a number of access protocols are proposed to meet a range of client requirements. The paper demonstrates that protocols for the "open" group model-clients external to the group of servers-satisfy the requirements of the State Machine approach, even when replication is transparent to the clients. Experimental performance results indicate that the "open" model is clearly desirable when the service is used by a large, dynamic set of clients.

The paper addresses the problem of providing highly available services in distributed systems. In particular, we examine the situation where a service may be used by a large continuously changing set of clients. The requirements for providing services in this environment are analysed and an architecture and partial implementation for a replicated server group meeting a range of client requirements is presented. The architecture facilitates the dynamic configuration management of the replicated server group, while maintaining the service. Dynamic configuration management is required in order to replace failed replicas, upgrade the server implementation, or change the availability characteristics of the service. The paper reports on initial implementation results.