We develop a holistic framework for adaptively scheduling asynchronous requests in distributed file systems. The system is holistic in that it manages all resources, including network bandwidth, server I/O, server CPU, and client and server memory utilization. It accelerates, defers, or cancels asynchronous requests in order to improve application-perceived performance directly. We employ congestion pricing via online auctions to coordinate the use of system resources by the file system clients so that they can detect shortages and adapt their resource usage. We implement our modifications in the Congestion-Aware Network File System (CA-NFS), an extension to the ubiquitous network file system (NFS). Our experimental result shows that CA-NFS results in a 20% improvement in execution times when compared with NFS for a variety of workloads.

Building reliable storage systems becomes increasingly challenging as the complexity of modern storage systems continues to grow. Understanding storage failure characteristics is crucially important for designing and building a reliable storage system. While several recent studies have been conducted on understanding storage failures, almost all of them focus on the failure characteristics of one component—disks—and do not study other storage component failures. This article analyzes the failure characteristics of storage subsystems. More specifically, we analyzed the storage logs collected from about 39,000 storage systems commercially deployed at various customer sites. The dataset covers a period of 44 months and includes about 1,800,000 disks hosted in about 155,000 storage-shelf enclosures. Our study reveals many interesting findings, providing useful guidelines for designing reliable storage systems. Some of our major findings include: (1) In addition to disk failures that contribute to 20--55% of storage subsystem failures, other components such as physical interconnects and protocol stacks also account for a significant percentage of storage subsystem failures. (2) Each individual storage subsystem failure type, and storage subsystem failure as a whole, exhibits strong self-correlations. In addition, these failures exhibit “bursty” patterns. (3) Storage subsystems configured with redundant interconnects experience 30--40% lower failure rates than those with a single interconnect. (4) Spanning disks of a RAID group across multiple shelves provides a more resilient solution for storage subsystems than within a single shelf.

The Real-Time Message Passing Interface (MPI/RT) standard is the product of the work of many people working in an open community standards group over a period of over six years. The purpose of this archival publication is to preserve the significant knowledge and experience that was developed in real-time message-passing systems as a consequence of the research and development effort as well as in the specification of the standard. Interestingly, several implementations of MPI/RT (as well as comprehensive test suites) have been created in industry and academia over the period during which the standard was created. MPI/RT is likely to gain adoption interest over time, and this adoption may be driven by the promulgation of the standard including this publication. We expect that, when people are interested in understanding options for reliable, quality of service (QoS)-oriented parallel computing with message passing, MPI/RT will serve as a foundation for such a study, whether or not its complete formalism is accepted into other systems or standards. MPI/RT is an offshoot of MPI-1, and retains many of the communication patterns of MPI-1. However, MPI/RT has investigated issues of fine-grain concurrency and highest achievable performance in many ways that were evidently inappropriate for MPI-1 in the scientific computing space in which it resides, with its much broader audience. MPI/RT focuses on early-binding (planned transfer), concurrent message passing, while integrating multiple real-time models: time-based, event-driven, and priority-oriented channels. Group admission control and declarative (deferred early binding) semantics support the goal of hard-real-time for the message-passing component of computation. Importantly, MPI/RT emphasizes the decoupling of message transfer and process/thread scheduling as part of its contribution to parallel processing with QoS. Buffer management and state transition diagrams are also integral to the notion of streaming data into and out of processors in a way that is consistent with QoS, and friendly to zero-copy approaches to communication. MPI/RT has also made strides in the direction of a parallel middleware specification by emphasizing an object-oriented design for the application programmer interface (API) compared with an object-based API or ad hoc API. The advantages of these are plain in the standard, in that the functionality has useful polymorphic adaptations where needed. Furthermore, the concepts that derive from MPI-1 (such as collective operations) appear as objects in MPI/RT. This modification has allowed for the removal of certain constructs in MPI-1 (such as the communicator), in favor of a specification and implementation phase for objects that describe communication in MPI/RT. Overall, a cleaner, more extensible design exists, which does not utilize more resources per se than those which are needed to admit the required channels for a program. Both offline and online admission control is contemplated, and multiple modes are supported, albeit weakly. MPI/RT-1.1, the standard version described here, does not cover all possible real-time parallel programming possibilities. It is silent concerning process/thread scheduling, so, in some sense, still has strong aspects of ‘best effort’, in terms of process scheduling. Leaving process scheduling as an orthogonal concern was intentional, so that the best concepts in these areas would be used in concert with MPI/RT, rather than offering a monolith. Furthermore, MPI/RT-1.1 does not explicitly address mode changes (with guaranteed mode-change QoS) between sets of channels, with invariants and non-invariants among the resources consumed. This remains important work for the future. The object-oriented, resource-conscious approach of MPI/RT naturally extends to multiple modes. Work to realize this in a standard or in prototypes remains for future work, although it was discussed and prototyped extensively during standardization. It is interesting to consider whether the connection-oriented, but limited QoS and resource specification of MPI/RT leads to a more-scalable or less-scalable system environment than that posed by MPI and similar middleware. While connections themselves indicate that resources will be assigned per connection, only those connections that are program-mandated are actually built. By way of contrast, in MPI it is necessary to offer a virtual all-to-all communication topology, and introduce overheads associated with either the static realization of such a topology, or else the dynamic build-up/tear-down of connections in constrained environments seeking to scale. Events over the past six years involving the evolution of networking technology make MPI/RT as interesting as it was when started, and possibly of more ubiquitous application in the long term. Infiniband, Rapid I/O, 3GIO, and other System Area Network standards are likely to offer rudimentary QoS over time in real applications. Likewise, the production of massively concurrent supercomputers (104 nodes or more), is likely to drive the need for predictable message passing in the runtime aspects of such systems. These events are likely to cause the ideas and concepts defined in this standard to have impact in areas far broader than originally anticipated. Copyright © 2004 John Wiley & Sons, Ltd. Contents Preface Six 1 Introduction S1 1.1 General introduction S1 1.1.1 Parallel models S2 1.1.2 ‘Sidedness’ of communication S3 1.1.3 Real-time models and QoS S3 1.1.4 Ontogeny of an MPI/RT application S4 1.1.5 The MPI/RT API S6 1.2 Introduction for users S12 1.3 Introduction for implementors S13 1.3.1 The basics S13 1.3.2 The admission test S14 1.3.3 Other advice to implementors S15 1.4 Error checking and kinds of libraries S15 1.4.1 Erroneous programs S15 1.4.2 Conformance and kinds of libraries S16 1.4.3 Error reporting S17 1.4.4 String representation of error codes S18 1.5 Related work S18 1.5.1 Admission control and resource reservation S18 1.5.2 Access arbitration and transmission control S19 1.5.3 Early results S20 1.6 Summary S23 I Concepts and basic objects S25 2 MPI/RT objects S27 2.1 Overview S27 2.2 Behavior of objects in MPI/RT S32 2.3 Generic operations defined on all MPI/RT objects S33 2.4 Attributes: object decoration S37 2.4.1 Keyval object parameter accessors S41 2.4.2 Object attribute manipulation functions S42 2.5 Containers S44 2.5.1 Container constructors S45 2.5.2 Generic container operations S45 2.5.3 Set operations S47 2.5.4 Vector base operations S48 2.5.5 Container iterators S50 2.6 Groups S53 2.6.1 Group definition S54 2.6.2 Group management S54 2.7 Miscellaneous objects S56 2.7.1 MPIRT_TASK_ADDRESS S56 2.8 Summary S57 3 Dataspecs and types S65 3.1 Overview S65 3.2 Dataspecs S65 3.2.1 Operations on dataspec S65 3.3 Predefined MPI/RT types S66 3.3.1 MPIRT_BOOLEAN S67 3.3.2 MPIRT_STRING_NAME S68 3.3.3 MPIRT_INT64 S68 3.3.4 MPIRT_TIME_SPEC S71 3.3.5 MPIRT_ADDRESS S72 3.3.6 MPIRT_BUFITER_MODE S72 3.4 Summary S73 4 Event delivery abstraction and handlers S79 4.1 Introduction S79 4.2 Event delivery abstraction S79 4.2.1 Event naming S81 4.2.2 Common event delivery abstraction operations S83 4.2.3 Triggers S85 4.2.4 Event receptors S87 4.3 Handlers S94 4.3.1 Handler constructors S94 4.3.2 Light-weight handler functions S96 4.3.3 Handler accessors S98 4.4 Waiting for an event S100 4.5 Summary S101 5 Buffer management S109 5.1 Introduction S109 5.2 Buffer object S109 5.3 Buffer object functions S115 5.3.1 Variable length transfers S115 5.3.2 Variable buffer offsets S116 5.4 Buffer operations S117 5.4.1 Operations on buffer labels S117 5.4.2 Buffer-partitioning operations S118 5.5 Buffer iterator S121 5.6 Buffer iterator accessors S130 5.7 Bufiter modes S132 5.8 Summary S134 II Transfer mechanisms and advanced objects S139 6 Channel overview S141 6.1 Introduction S141 6.2 Common attribute operations for channels S143 6.3 Summary S146 7 Point-to-point channels S149 7.1 Introduction S149 7.2 Operations on the point-to-point channel object S149 7.3 Summary S151 8 Collective channels S153 8.1 Introduction S153 8.2 Broadcast collective channel S153 8.3 Gather operation channel S156 8.4 Scatter operation channel S160 8.5 Reduce operation channel S164 8.5.1 Predefined reduce operations S168 8.6 Barrier operation channel S169 8.7 All-to-all channel S170 8.8 Summary S172 9 Channel operations S181 9.1 Data transfers S181 9.1.1 Performance considerations S181 9.1.2 Channel states and transitions S182 9.1.3 Methods for single message transfer S188 9.1.4 Methods for multiple message transfers S190 9.2 Testing completion and determining the state of data transfers S191 9.2.1 Wait operation S192 9.2.2 Test operation S192 9.3 Summary S193 III Real-time programming models and QoS S195 10 QoS overview S197 10.1 Introduction S197 10.2 Time-driven real-time programming model S198 10.2.1 Scheduling message transfers S199 10.2.2 Schedulable time intervals S199 10.2.3 The MPI/RT time specification S200 10.3 Event-driven real-time programming model S200 10.3.1 Overview S201 10.3.2 Event triggers S202 10.3.3 Event receptors S204 10.4 Priority-driven real-time programming model S204 10.4.1 Channel priority S205 10.4.2 Process priority S206 10.5 Best-effort QoS programming model S206 11 QoS specification S207 11.1 Introduction S207 11.2 Channel QoS specification S207 11.2.1 Specification for time-driven channels S208 11.2.2 Relationship of time-based schedules for different channels S211 11.2.3 Specification for event-driven-with-priority channels S211 11.2.4 Specification for combined event and time-driven with priority channels S219 11.3 Handler QoS specification S225 11.4 Event-delivery abstraction's QoS specification S227 11.4.1 QoS for triggers S227 11.4.2 QoS for receptors S230 11.5 Summary S232 12 Committing objects and resource allocation S239 12.1 Commit operation S239 12.2 Summary S241 IV Environmental mechanisms and functionality S243 13 Initialization and termination S245 13.1 Initialization and termination of MPI/RT S245 13.2 Version information S247 13.3 Summary S248 14 Clocks S251 14.1 Synchronization of clocks S251 14.2 Description of the clocks S251 14.3 Clock synchronization parameters S252 14.3.1 The epoch S252 14.3.2 The MPIRT_TIME type S253 14.3.3 The synchronized time service S253 14.3.4 Parameters S253 14.4 Behavior of the time services S256 14.5 Timed waiting S256 14.6 Summary S257 15 Instrumentation S259 15.1 Introduction S259 15.2 MPI/RT metrics S260 15.3 MPI/RT probes S261 15.4 MPI/RT user metrics S265 15.5 Summary S270 V Appendices S273 A Return codes S275 A.1 Return codes S275 B Deprecated functionality S281 B.1 Functionality deprecated in MPI/RT-1.1 S281 B.1.1 MPIRT_ERR_COMMITTED_OBJECT S281 B.1.2 MPIRT_ERR_INITIALIZED S281 B.1.3 MPIRT_CSET_RETRIEVE_NEXT S281 B.1.4 MPIRT_ERR_ACTIVE_CHANNEL S282 Acknowledgments S283 Glossary S287 Bibliography S295 MPI/RT return code index S299 MPI/RT function index S303 MPI/RT entity index S319 Index S331 Preface PREFACE TO THE CURRENT STANDARD VERSION, MPI/RT-1.1 At the conclusion of MPI/RT-1.0, many of us participating and contributing to the standard recognized the need to continue to improve certain key features, in pursuit of a system with extremely low cost of portability, and to widen the applicability of MPI/RT. A restrained set of extensions have emerged in MPI/RT-1.1, from among a huge set of proposals, ideas, and concepts. While assiduously trying to avoid the ‘second system syndrome’, MPI/RT-1.1 works hard to fix small issues and make the standard easier to use, better, and more applicable. This document conflates the contributions of MPI/RT-1.0, the principal work, with the newly accepted developments of MPI/RT-1.1, plus errata and other improvements designed to keep this document as the main reference for understanding how to implement and use MPI/RT. A subset of the original participants in MPI/RT-1.0, together with some new participants, have built this standard extension, with the view that future extensions (whether termed MPI/RT-1.2 or MPI/RT-2) would come much later, after a period of two or more years of implementation and usage. While initial implementations and experience with MPI/RT-1.0 have driven MPI/RT-1.1 in part, much room remains for further implementation and experience in various application spaces. Historical perspective will of course assess the validity, efficacy, and overall impact of building application programmer interface (API) standards in the way that MPI/RT-1.0 and MPI/RT-1.1 have been done, namely, by a small group of dedicated individuals, supported by a larger group of interested participants from the application, user, and research communities of both private and public sectors. The shoe-string funding associated with MPI/RT over the last three years of its six-year life has actually energized, rather than diminished, the energy for such progress and success. What appears clear, however, is that a tremendous amount of useful computer science related to advanced systems programming of middleware with real-time has been captured in this standards document and its first extension, MPI/RT-1.1. This stable intermediate form will clearly play an important role in the future exploration of real-time middleware for scalable, parallel processing. The efforts of the MPI/RT Forum and its members over the past six years reflect the strong commitment, perseverance, and tireless efforts of its individual participants, for which the chairs offer their sincerest gratitude. Anthony Skjellum, Starkville, MS Arkady Kanevsky, Waltham, MA March 2001 PREFACE TO MPI/RT-1.0 In 1995, several researchers and practitioners became interested in advancing real-time extensions to the then existing Message Passing Interface (MPI) de facto standard and began meeting informally. Later, the group became a sanctioned subcommittee of the MPI-2 de facto standards body, which met regularly in Chicago. People involved with high-performance computing, distributed computing, message-passing systems, and real-time systems were all represented. Researchers and practitioners from industry, academia and defense laboratories were included. The MPI-2 Forum condoned this effort and allowed it to blossom as a Journal of Development activity, with a clear view that it would not formally be part of MPI-2, but nonetheless was a worthwhile working activity. This status was productive and helpful to the work because of the valuable proximity to many interested in messaging, without the compelling deadline faced by MPI-2. From a technical perspective, a lot of issues, approaches, requirements, and techniques evolved, and significant new ideas previously thought about were introduced into the discussion. These issues included provision of key concepts not available or readily addressable within the confines of MPI-1 [1] and MPI-2 [2]: channels, real-time models, predictability, greater support for thread interactions, early-binding strategies, and admission tests. The requirements posed by the subcommittee emerged as follows: achieve highest performance messaging and add the additional constraints of predictability and quality-of-service (QoS), with the additional capability to support relevant memory management to enhance the elimination of data copies and support for the ‘cut-through’ of data. These requirements drove us over time, sometimes systematically and sometimes ad hoc, to re-examine much of what was decided in earlier messaging systems and ultimately to evolve away from explicit upward or downward compatibility with MPI. The outcome of this effort is a ‘lower middleware’ standard called MPI/RT, which strives to offer extremely low cost of portability as compared with any native software architecture for messaging, while providing useful real-time notions of performance, predictability, and QoS. Other major decisions included the elimination of Fortran77 language bindings in favor of C++ language bindings and the thorough and continued use of object-oriented APIs and design methodologies to motivate and support the process. Positioning MPI as conceptually ‘higher middleware’ in the form of a layer on top of MPI/RT establishes a conceptual relationship between this work and the previous standard. In fact, we expect that MPI implementations may actually be layered over MPI/RT on systems where users require both notations, and this ‘layerability’ is mentioned in appropriate parts of the standard. With encouragement and support from DARPA, and from the strong commitment of many of the subcommittee participants, including people from the mainstream of MPI Forum participants, significant progress was made over the first 18 months. The group continued to meet and burgeoned into a full-scale de facto effort of its own after the conclusion of the MPI-2 standards effort. Early versions of this effort appear in the ‘Journal of Development’ of the MPI-2 standard, but the results presented in that snapshot are quite different from what we have ultimately accomplished. This three-year effort has led to quite a satisfactory messaging middleware specification and standard that we expect to see deployed by industry in real-time computing multicomputers and networks of workstations. The group is committed to extending the specification in a limited fashion in 1999 to support channel input/output (I/O), dynamic processes, and a few other features intentionally delayed at present. After that, sincere efforts to introduce MPI/RT to a formal standard body will be undertaken by us and others, in order to help assure its long-term acceptance. In order to facilitate of this we have explicitly all to the MPI standards within the document into in order to additional information of to while the main and of the document of on either MPI-1 or MPI-2 standard knowledge of MPI-1 or MPI-2 is needed to with MPI/RT. In this we issues where is or different decisions have been while on the other and without much from new to MPI/RT. part of this work, we have own Journal of Development that has been into two of is to be in the MPI/RT-1.1 in is ‘best results and issues out during the past years that we to A but not formally best document is a related outcome of this issues as to other and a subset of MPI/RT-1.1 in that other This other body of results remains valuable the community we are seeking to The complete specification for MPI/RT is presented in this 1 a overview of the standard for 2 the object-oriented design of MPI/RT and the objects in describe the basic the and buffer describe the data transfer real-time QoS issues and address the issues for MPI/RT programs such as synchronized and performance of interest to such as a of how to use a of MPI/RT, is by to of interest to implementors of MPI/RT is by to The features are by Arkady Kanevsky, MA Anthony Skjellum, Starkville, MS

MITRE's Evolvable Real-Time Command Control, and Communications (C3) project, funded under the Air Force Mission Oriented Investigation and Experimentation (MOIE) program attempts to develop an approach that would enable current real-time systems to evolve into the systems of the future. The project has chosen the Airborne Warning and Control System (AWACS) as an example to test the concepts and architectures to be developed. We discuss the requirements for the infrastructure for next generation complex real-time command and control systems. This discussion also includes an overview of the infrastructure requirements for each of the three architectures that we have considered.

Two self-stabilizing topology maintenance protocols for high-speed networks are presented. The protocols tolerate any number and kind of initial faults. The new protocols improve on previous protocols by their stabilization time (the amount of time following the last topology change required to notify every processor of the correct topology), by their utilization of limited switch bandwidth, and by their avoiding the use of unbounded sequence numbers. The first protocol stabilizes in O(log d) time in the worst case, where d is the diameter of the network. This protocol imposes a high bandwidth requirement on individual network nodes. The second, which is implemented by two software layers, reduces the processing load on individual nodes and stabilizes within O(d) time in the worst case and O(1) time when changes are infrequent.

This paper describes MITRE's Evolvable Real-Time Command, Control, and Communications (C3) systems initiative that attempts to develop an approach that would enable current real-time systems to evolve into the systems of the future. In particular, this article describes the infrastructure requirements that we have developed. We first provide an overview of the current real-time C3 systems and describe the systems of the future. Next, we describe some candidate architectures that we have examined for future systems. Then a detailed discussion of the requirements for the infrastructure are given. The main focus is on operating systems, data management systems, and communication systems requirements. The discussion is based on the candidate architectures that we have examined. The project has chosen Airborne Warning and Control System (AWACS) as an example to test out the concepts and architectures to be developed.

The WK-Recursive Network (WKRN) is a hierarchical interconnection network that is recursively defined and has excellent properties for scalable message-passing multicomputer systems. In this paper, we present efficient routing and broadcasting schemes in a WKRN. For efficient routing, we define the MP-graph between the source and destination nodes of the message. For efficient broadcasting, we define the EDHP-graph and the NDST-graph. The MP-graph can also be used for message routing in the presence of faulty nodes. Similarly, the EDHP-graph (the NDST-graph) can be used for message broadcast in the presence of faulty links (nodes). Fault-tolerant communication schemes using these graphs have the advantage that no information about the presence or location of faulty components is required. Moreover, the MP-graph and the NDSTgraph can be used under different fault models. We analyze the communication delays for message routing (broadcast) along MP-graphs (EDHP-graphs and NDST-graphs) under fault-free and faulty conditions.

We present two Hierarchical networks that use the WKR network as a basic module. The new net works retain the recursive structure of the WKR net work, at the same time have reduced diameter. Various properties of the new networks are discussed and are compared with those of other hierarchical networks.

In a multiuser message passing MIMD sys tem, substructure allocation is an important aspect of sys tem design. In this paper, we present four substructure al location algorithms for a multiuser WK-Recursive network. Two algorithms are bit-map based and two are tree based. The algorithms are compared using simulation.

We show that, for any fixed k, there exists an optimal O(n)-space compact representation of a k-connected graph G with n vertices, such that one can determine in O(1) time whether two vertices areconnectedbyk+l vertex-dkjoint paths, or are separated by k vertices/edges.Previously, the existence of such compact representations was known only for k <3.1 Summary of ResultsA fundamental issue for the fault-tolerance and reliabilityofnetworksis determining the existence of multiple disjoint paths connecting two nodes.In this paper we investigate the problem of constructing a compact representation of a graph so that one can test quickly for the existence of such paths.

Abstract We present a new algorithm based upon network flows for finding all minimum‐size separating vertex sets in an undirected and unweighted graph. The sequential implementation of our algorithm runs in Θ(Mn + C) = O(2kn3) time, where M is the number of minimum‐size separating vertex sets of the graph; n, the number of the vertices in the graph; m, the number of the edges in the graph; k, the connectivity of the graph, and C = kn min(k(m + n), A), where A is the complexity of the best maximum flow algorithm for unit networks. The parallel implementation runs either in O(k log n) deterministic time or in O(log2 n) randomized time using Θ(;M2n2 + knNα) = O(4k(n6/k2)) processors on a PRAM, where Nα is the number of processors needed for parallel matrix multiplication in O(log n) time on PRAM. © 1993 by John Wiley & Sons, Inc.

Given a graph G with n vertices and m edges, a k-connectivity query for vertices v' and v" of G asks whether there exist k disjoint paths between v' and v". The authors consider the problem of performing k-connectivity queries for k>

We present a new algorithm based on ear decomposition for testing vertex four-connectivity and for finding all separating triplets in a triconnected graph. The sequential implementation of our algorithm runs in O(n2) time and the parallel implementation runs in O(logn) time using O(n2) processors on a CRCW PRAM, where n is the number of vertices in the graph. This improves previous bounds for the problem for both the sequential and parallel cases. The sequential algorithm is optimal if the input is specified in adjacency matrix form, or if the input graph is dense.