Merkle grids are a new data organization that replicates the functionality of Merkle trees while reducing their transmission and storage costs by up to 50 percent. All Merkle grids organize the objects whose conformity they monitor in a square array. They add row and column hashes to it such that (a) all row hashes contain the hash of the concatenation of the hashes of all the objects in their respective row and (b) all column hashes contain the hash of the concatenation of the hashes of all the objects in their respective column. In addition, a single signed master hash contains the hash of the concatenation of all row and column hashes. Extended Merkle grids add two auxiliary Merkle trees to speed up searches among both row hashes and column hashes. While both basic and extended Merkle grids perform authentication of all blocks better than Merkle trees, only extended Merkle grids can locate individual non-conforming objects or authenticate a single non-conforming object as fast as Merkle trees.

A Trusted Cloud Database System manages client-side encrypted cloud DBs. Queries may include encryption keys. The DBS decrypts/encrypts the data on-the-fly at the cloud. Plaintext is only in protected run-time variables. Stored data are by default probabilistically encrypted through AES. Any SQL queries are feasible, with negligible processing overhead and practical storage overhead. This is a major advance over the current alternative research proposals. We detail capabilities of a trusted DBS. We adapt SQL to client-side key management. Queries may remain usually almost as nonprocedural as now. A prototype implementation appears easy.

Magnetic disk capacities have grown over the last decades by a factor of at least ten thousand. While the minicomputer disk drives of the late eighties could only store 600 MB of data [5], 8TB or 10TB disk drives are common today. The same is not true for disk transfer rates: they are just one hundred times higher than those of the late eighties. As a result, copying the entire contents of a disk will take now considerably more time than thirty or forty years ago.

Stored data needs to be protected against device failure and irrecoverable sector read errors, yet doing so at exabyte scale can be challenging given the large number of failures that must be handled. We have developed RESAR (Robust, Efficient, Scalable, Autonomous, Reliable) storage, an approach to storage system redundancy that only uses XOR-based parity and employs a graph to lay out data and parity. The RESAR layout offers greater robustness and higher flexibility for repair at the same overhead as a declustered version of RAID 6. For instance, a RESAR-based layout with 16 data disklets per stripe has about 50 times lower probability of suffering data loss in the presence of a fixed number of failures than a corresponding RAID 6 organization. RESAR uses a layer of virtual storage elements to achieve better manageability, a broader potential for energy savings, as well as easier adoption of heterogeneous storage devices.

Commercial cloud systems allow massively parallel execution of a computing task for little money. We want to exploit this economic opportunity by solving classical problems in Operations Research through complete enumeration, especially if these problems can be expressed as integer programming problems. We propose and evaluate here a data structure, Scalable Virtual Distributed Hashing, that autonomously extends the computing task over as many nodes as are needed in order return a result within a time limit set by the user. Our data structure deals with varying and changing node capacities and the effects of node failures. It is modeled after Scalable Distributed Data Structures and Extendible Hashing in particular.

Archival data storage systems contain data that must be preserved over long periods of time but which are often unlikely to be accessed during their lifetime. The best strategy for such systems is to keep their disks powered-off unless they have to be powered up to access their contents, to reconstruct lost data, or to perform other disk maintenance tasks. Of all such tasks, reconstructing data after a disk failure is the one that is likely to have the highest energy footprint and the most impact on the overall power consumption of the array, because it typically involves powering up all the disks belonging to the same reliability stripe as the failed disk and keeping them running for considerable time at each occurrence. We investigate two two-failure tolerant disk layouts that have lower parity overhead than the number of disks read (and hence powered-on) for recovering data on lost drives would suggest. Our first organization is a flat XOR code that organizes the data disks into a rectangle with fewer rows than columns, and adds a simple parity disk to each row and column. Recovery from a disk failure proceeds by prefering columns when reconstructing lost data, and thereby has fewer reads than the parity overhead would normally suggest. Our second layout is based on the most basic pyramid code. We can view this layout as an example RAID Level 6 variant. In this variant, a stripe has a Q-parity calculated from the data disks in the stripe, but the data disks are also organized into smaller groups where each group has a separate P-parity calculated as the exclusive-or of the data disks in the group. We compare the two layouts by measuring their robustness to data loss, their one-year survival rate, and the expected number of number of disks that must be involved to recover from both single and multiple disk failures. Our results show that rectangular layouts are significantly more reliable than layouts based on the most basic Pyramid codes, but that they also require more disk accesses to recover from disk failures.

We present a disk array organization that can survive three simultaneous disk failures while only using exclusive-or operations to calculate the parities that generate this failure tolerance. The reliability of storage systems using magnetic disks depends on how prone individual disks are to failure. Unfortunately, disk failure rates are impossible to predict and it is well known that individual batches might be subject to much higher failure rates at some point during their lifetime. It is also known that many disk drive families, but not all, suffer a substantially higher failure rate at the beginning and some at the end of their economic lifespan. Our proposed organization can be built on top of a dense two-failure tolerant layout using only exclusive-or operations and with a ratio of parity to data disks of 2/k. If the disk failure rates are higher than expected, the new organization can be super-imposed on the existing two-failure tolerant organization by introducing (k+1)/2 new parity disks and (k+1)/2 new reliability stripes to yield a three-failure tolerant layout without moving any data or calculating any other parity but the new one. We derive the organization using a graph visualization and a construction by Lawless of factoring a complete graph into paths.

Disk failure rates vary so widely among different makes and models that designing storage solutions for the worst case scenario is a losing proposition. The approach we propose here is to design our storage solutions for the most probable case while incorporating in our design the option of adding extra redundancy when we find out that its disks are less reliable than expected. To illustrate our proposal, we show how to increase the reliability of existing two-dimensional disk arrays with n2data elements and 2n parity elements by adding n additional parity elements that will mirror the contents of half the existing parity elements. Our approach offers the three advantages of being easy to deploy, not affecting the complexity of parity calculations, and providing a five-year reliability of 99.999 percent in the face of catastrophic levels of data loss where the array would lose up to a quarter of its storage capacity in a year.

Proteus is an open-source simulation program that can predict the risk of data loss in many disk array configurations, among which, mirrored disks, all levels of RAID arrays and various two-dimensional RAID arrays. It characterizes each array by five numbers, namely, the size n of the array, the number nf of simultaneous disk failures the array will always tolerate without data loss, and the respective fractions f1, f2and f3of simultaneous failures of nf+ 1, nf+ 2 and nf+ 3 disks that will not result in a data loss. As with any simulation tool, Proteus imposes no restriction on the distributions of failure and repair events. Our measurements have shown a surprisingly good agreement with the results obtained through analytical techniques and no measurable difference between values obtained assuming deterministic repair times and those assuming exponential repair times.

We present a disk array architecture that does not require users to perform any maintenance tasks over the expected lifetime of the array. Preliminary results indicate that the key factor in the feasibility of our design is the failure rate of unused spare disks. As long as these rates remain negligible, zero maintenance disk arrays with at least 77 disks can provide a five-year reliability of five nines (99.999 percent) with a space overhead comparable to that of mirroring. If this is not the case, we would need between 64 and 70 percent extra spare disks to achieve the same five-year reliability, which would result in a higher space overhead.

We present a general method for estimating the risk of data loss in arbitrary two-dimensional RAID arrays where each data disk belongs to exactly two single-parity stripes. We start by representing each array organization by a graph where each parity stripe, and its associated parity disk, is represented by a node and each data disk by an edge. We then use this representation to identify and enumerate minimal sets of disk failures, say, triple failures, quadruple failures and so forth, that will cause a data loss. The overall probabilities that a given number n of disk failures will cause a data loss is then given by the ratio of the total number of fatal disk failures involving n disks over the total number of possible failures of n disks. To illustrate the power of our method, we apply it to two distinct, archival two-dimensional array organizations. The first, "square" organization is a traditional square layout where data disks are formed into a square and the parity stripes are formed by the rows and columns in the square. Hence a square layout organization with n^2 data disks will have 2n parity disks. The second, "complete" organization corresponds to a closer weave, where all parity stripes intersect and each intersection contains a parity disk. This organization with n parity disks will have n(n - 1)/2 data disks. Our results show that previous ad hoc estimates of the reliability of these arrays significantly underestimated their reliability by assuming that either all triple or all quadruple disk failures were fatal. We show that the two two-dimensional array organizations exhibit mean times to data loss and five-year survival rates that are very similar to those of a RAID Level 6 organization of much smaller capacity. Our complete organization is about 4.5 times and the square organization is about 8 times more reliable than a disk array with same storage capacity built from RAID level 6 stripes. We present a general method for estimating the risk of data loss in arbitrary two-dimensional RAID arrays where each data disk belongs to exactly two single-parity stripes. We start by representing each array organization by a graph where each parity stripe, and its associated parity disk, is represented by a node and each data disk by an edge. We then use this representation to identify and enumerate minimal sets of disk failures, say, triple failures, quadruple failures and so forth, that will cause a data loss. The overall probabilities that a given number n of disk failures will cause a data loss is then given by the ratio of the total number of fatal disk failures involving n disks over the total number of possible failures of n disks. To illustrate the power of our method, we apply it to two distinct, archival two-dimensional array organizations. The first, "square" organization is a traditional square layout where data disks are formed into a square and the parity stripes are formed by the rows and columns in the square. Hence a square layout organization with n^2 data disks will have 2n parity disks. The second, "complete" organization corresponds to a closer weave, where all parity stripes intersect and each intersection contains a parity disk. This organization with n parity disks will have n(n - 1)/2 data disks. Our results show that previous ad hoc estimates of the reliability of these arrays significantly underestimated their reliability by assuming that either all triple or all quadruple disk failures were fatal. We show that the two two-dimensional array organizations exhibit mean times to data loss and five-year survival rates that are very similar to those of a RAID Level 6 organization of much smaller capacity. Our complete organization is about 4.5 times and the square organization is about 8 times more reliable than a disk array with same storage capacity built from RAID level 6 stripes.

Linear Hashing is a widely used and efficient version of extensible hashing. A distributed version of Linear Hashing is LH$ast$ that stores key-indexed records on up to hundreds of thousands of sites in a distributed system. LH$ast$ implements the dictionary data structure efficiently since it does not use a central component for the key-based operations of insertion, deletion, actualization, and retrieval and for the scan operation. LH$ast$ allows a client or a server to commit an addressing error by sending a request to the wrong server. In this case, the server forwards to the correct server directly or in one more forward operation. We discuss here methods to avoid the double forward, which is rare but might breach quality of service guarantees. We compare our methods with LH$ast$ P2P that pushes information about changes in the file structure to clients, whether they are active or not.

We present a two-dimensional RAID architecture that is specifically tailored to the needs of archival storage systems. Our proposal starts with a fairly conventional two-dimensional RAID architecture where each disk belongs to exactly one horizontal and one vertical RAID level 4 stripe. Once the array has been populated, we add a superparity device that contains the exclusive OR of all the contents of all horizontal-or vertical-parity disks. The new organization tolerates all triple disk failures and nearly all quadruple and quintuple disk failures. As a result, it provides mean times to data loss (MTTDLs) more than a hundred times better than those of sets of RAID level 6 stripes with equal capacity and similar parity overhead.

Many modern storage systems use deduplication in order to compress data by avoiding storing the same data twice. Deduplication needs to use data stored in the past, but accessing information about all data stored can cause a severe bottleneck. Similarity based deduplication only accesses information on past data that is likely to be similar and thus more likely to yield good deduplication. We present an adaptive deduplication strategy that extends Extreme Binning and investigate theoretically and experimentally the effects of the additional bin accesses.

LH*RE is a new Scalable Distributed Data Structure (SDDS) for hash files stored in a cloud. The client-side symmetric encryption protects the data against the server-side disclosure. The encryption key(s) at the client are backed up in the file. The client may recover/ revoke any keys lost or stolen from its node. A trusted official can also do it on behalf of the client or of an authority, e.g., to imperatively access the data of a client missing or disabled. In contrast, with high assurance, e.g., 99%, the attacker of the cloud should not usually disclose any data, even if the intrusion succeeds over dozens or possibly thousands of servers for a larger file. Storage and primary key-based access performance of LH*RE should be about those of the well-known LH* SDDS. Two messages should typically suffice for a key-based search and four in the worst case, with the application data load factor of 70%, regardless of the file scale up. These features are among most efficient for a hash SDDS. LH*RE should be attractive with respect to the competition.

We propose Clasas (from the Castilian “Claves seguras” for “secure keys”), a key-store for distributed storage such in the Cloud. The security of Clasas derives from breaking keys into K shares and storing the key shares at many different sites. This provides both a probabilistic and a deterministic guarantee against an adversary trying to obtain keys. The probabilistic guarantee is based on a combinatorial explosion, which forces an adversary to subvert a very large portion of the storage sites for even a minute chance of obtaining a key. The deterministic guarantee stems from the use of LH* distributed linear hashing. Our use of the LH* addressing rules insures that no two key shares (belonging to the same key) are ever, even in transit, stored at the same site. Consequentially, an adversary has to subvert at least K sites. In addition, even an insider with extensive administrative privileges over many of the sites used for key storage is prevented from obtaining access to any key. Our key-store uses LH* or its scalable availability derivate, LH*RS to distribute key shares among a varying number of storage sites in a manner transparent to its users. While an adversary faces very high obstacles in obtaining a key, clients or authorized entities acting on their behalf can access keys with a very small number of messages, even if they do not know all sites where key shares are stored. This allows easy sharing of keys, rekeying, and key revocation.

If the data density of magnetic disks is to continue its current 30-50% annual growth, new recording techniques are required. Among the actively considered options, shingled writing is currently the most attractive one because it is the easiest to implement at the device level. Shingled write recording trades the inconvenience of the inability to update in-place for a much higher data density by a using a different write technique that overlaps the currently written track with the previous track. Random reads are still possible on such devices, but writes must be done largely sequentially. In this paper, we discuss possible changes to disk-based data structures that the adoption of shingled writing will require. We first explore disk structures that are optimized for large sequential writes with little or no sequential writing, even of metadata structures, while providing acceptable read performance. We also examine the usefulness of non-volatile RAM and the benefits of object-based interfaces in the context of shingled disks. Finally, through the analysis of recent device traces, we demonstrate the surprising stability of written device blocks, with general purpose workloads showing that more than 93% of device blocks remain unchanged over a day, and that for more specialized workloads less than 0.5% of a shingled-write disk's capacity would be needed to hold randomly updated blocks.

Disk scrubbing periodically scans the contents of a disk array to detect the presence of irrecoverable read errors and reconstitute the contents of the lost blocks using the built-in redundancy of the disk array. We address the issue of scheduling scrubbing runs in disk arrays that can tolerate two disk failures without incurring a data loss, and propose to start an urgent scrubbing run of the whole array whenever a disk failure is detected. Used alone or in combination with periodic scrubbing runs, these expedited runs can improve the mean time to data loss of disk arrays over a wide range of disk repair times. As a result, our technique eliminates the need for frequent scrubbing runs and the need to maintain spare disks and personnel on site to replace failed disks within a twenty-four hour interval.

AS-Index is a new index structure for exact string search in disk resident databases. It uses hashing, unlike known alternatives, whether baesd on trees or tries. It typically indexes every n-gram in the database, though non-dense indexing is possible. The hash function uses the algebraic signatures of n-grams. Use of hashing provides for constant index access time for arbitrarily long patterns, unlike other structures whose search cost is at best logarithmic. The storage overhead of AS-Index is basically 500 - 600%, similar to that ofalternatives or smaller. We show the index structure, our use of algebraic signatures and the search algorithm. We present the theoretical and experimental performance analysis. We compare the AS-Index to main alternatives. We conclude that AS-Index is an attractive structure and we indicate directions for future work.

Digital archives are growing rapidly, necessitating stronger reliability measures than RAID to avoid data loss from device failure. Mirroring, a popular solution, is too expensive over time. We present a compromise solution that uses multi-level redundancy coding to reduce the probability of data loss from multiple simultaneous device failures. This approach handles small-scale failures of one or two devices efficiently while still allowing the system to survive rare-event, larger-scale failures of four or more devices. In our approach, each disk is split into a set of fixed size disklets which are used to construct reliability stripes. To protect against rare event failures, reliability stripes are grouped into larger super-groups, each of which has a corresponding super-parity; super-parity is only used to recover data when disk failures overwhelm the redundancy in a single reliability stripe. Super-parity can be stored on a variety of devices such as NV-RAM and always-on disks to offset write bottlenecks while still keeping the number of active devices low. Our calculations of failure probabilities show that adding super-parity allows our system to absorb many more disk failures without data loss. Through discrete event simulation, we found that adding super-groups has a significant impact on mean time to data loss and that rebuilds are slow but not unmanageable. Finally, we showed that robustness against rare events can be achieved for a fraction of total system cost.

We investigate the impact of irrecoverable read errors--also known as bad blocks--on the MTTDL of mirrored disks, RAID level 5 arrays and RAID level 6 arrays. Our study is based on the data collected by Bairavasundaram et al. from a population of 1.53 million disks over a period of 32 months. Our study indicates that irrecoverable read errors can reduce the mean time to data loss (MTTDL) of the three arrays by up to 99 percent, effectively canceling most of the benefits of fast disk repairs. It also shows the benefits of frequent scrubbing scans that map out bad blocks thus preventing future irrecoverable read errors. As an example, once-a-month scrubbing scans were found to improve the MTTDL of the three arrays by at least 300 percent compared to once-a-year scrubbing scans.

For many storage providers, the cost of providing service calls exceeds the costs of the hardware being serviced. In this paper, we show that zero-maintenance, small disk arrays are too expensive, but that low-maintenance arrays are feasible and describe a possible implementation. Our evaluation technique replaces Mean Time to Data Loss with the lifespan. Our results also show the impact of the assumption of constant failure rates on the results of modeling

We propose the use of parity-based redundant data layouts of increasing reliability as a means to progressively harden data archives. We evaluate the reliability of two such layouts and demonstrate how moving to layouts of higher parity degree offers a mechanism to progressively and dramatically increase the reliability of a multi-device data store. Specifically we propose that a data archive can be migrated to progressively more reliable layouts as the data ages, trading limited (and likely unrealized) increases in update costs for increased reliability. Our parity-based schemes are drawn from SSPiRAL (Survivable Storage using Parity in Redundant Array Layouts) that offer capacity efficiency equivalent to a straightforward mirroring arrangement. Our analysis shows our proposed schemes would utilize no additional physical resources and result in improvements to mean time to data loss of four to seven orders of magnitude.

P2P storage systems must protect data against temporary unavailability and the effects of churn in order to become platforms for safe storage. This paper evaluates and compares redundancy techniques for P2P storage according to availability, accessibility, and maintainability using traces and theoretical results.

We propose increasing the survivability of data stored in two-dimensional RAID arrays by causing these arrays to reorganize themselves whenever they detect a disk failure. This reorganization will rebalance as much as possible the redundancy level of all stored data, thus reducing the potential impact of additional disk failures. It remains in effect until the failed disk gets repaired. We show how our technique can be applied to two-dimensional RAID arrays consisting of n2data disks and 2n parity disks and show how it can increase the mean time to data loss of the array by at least 200 percent as long as the reorganization process takes less than half the time it takes to replace a failed disk.

The emerging use of the Internet for remote storage and backup has led to the problem of verifying that storage sites in a distributed system indeed store the data; this must often be done in the absence of knowledge of what the data should be. We use m/n erasure-correcting coding to safeguard the stored data and use algebraic signatures hash functions with algebraic properties for verification. Our scheme primarily utilizes one such algebraic property: taking a signature of parity gives the same result as taking the parity of the signatures. To make our scheme collusionresistant, we blind data and parity by XORing them with a pseudo-random stream. Our scheme has three advantages over existing techniques. First, it uses only small messages for verification, an attractive property in a P2P setting where the storing peers often only have a small upstream pipe. Second, it allows verification of challenges across random data without the need for the challenger to compare against the original data. Third, it is highly resistant to coordinated attempts to undetectably modify data. These signature techniques are very fast, running at tens to hundreds of megabytes per second. Because of these properties, the use of algebraic signatures will permit the construction of large-scale distributed storage systems in which large amounts of storage can be verified with minimal network bandwidth.

Inter-file compression techniques store files as sets of references to data objects or chunks that can be shared among many files. While these techniques can achieve much better compression ratios than conventional intra-file compression methods such as Lempel-Ziv compression, they also reduce the reliability of the storage system because the loss of a few critical chunks can lead to the loss of many files. We show how to eliminate this problem by choosing for each chunk a replication level that is a function of the amount of data that would be lost if that chunk were lost. Experiments using actual archival data show that our technique can achieve significantly higher robustness than a conventional approach combining data mirroring and intra-file compression while requiring about half the storage space.

As an emerging nonvolatile secondary storage technology, MEMS-based storage exhibits several desirable properties including high performance, high storage volumic density, low power consumption, low entry cost, and small form factor. However, MEMS-based storage provides a limited amount of storage per device and is likely to be more expensive than magnetic disk. Systems designers will therefore need to make trade-offs to achieve well-balanced designs. We present an architecture in which MEMS devices are organized into MEMS storage enclosures with online spares. Such enclosures are proven to be highly reliable storage building bricks with no maintenance during their economic lifetimes. We also demonstrate the effectiveness of using MEMS as another layer in the storage hierarchy, bridging the cost and performance gap between MEMS storage and disk. We show that using MEMS as a disk cache can significantly improve system performance and cost-performance ratio.

As disk drives have dropped in price relative to tape, the desire for the convenience and speed of online access to large data repositories has, led to the deployment of petabyte-scale disk farms with thousands of disks. Unfortunately, the very large size of these repositories renders them vulnerable to previously rare failure modes such as multiple, unrelated disk failures leading to data loss. While some business models, such as free email servers, may be able to tolerate some occurrence of data loss, others, including premium online services and storage of simulation results at a national laboratory, cannot. This paper describes the effect of infant mortality on long-term failure rates of systems that must preserve their data for decades. Our failure models incorporate the well-known "bathtub curve," which reflects the higher failure rates of new disk drives, a lower, constant failure rate during the remainder of the design life span, and increased failure rates as components wear out. Large systems are vulnerable to the "cohort effect" that occurs when many disks are simultaneously replaced by new disks. Our more accurate disk models and simulations have yielded predictions of system lifetimes that are more pessimistic than existing models that assume a constant disk failure rate. Thus, larger system scale requires designers to take disk infant mortality into account.

Recent advances in large-capacity, low-cost storage devices have led to active research in design of large-scale storage systems built from commodity devices for supercomputing applications. Such storage systems, composed of thousands of storage devices, are required to provide high system bandwidth and petabyte-scale data storage. A robust network interconnection is essential to achieve high bandwidth, low latency, and reliable delivery during data transfers. However, failures, such as temporary link outages and node crashes, are inevitable. We discuss the impact of potential failures on network interconnections in very large-scale storage systems and analyze the trade-offs among several storage network topologies by simulations. Our results suggest that a good interconnect topology be essential to fault-tolerance of a petabyte-scale storage system.

LH* RS is a high-availability scalable distributed data structure (SDDS). An LH* RS file is hash partitioned over the distributed RAM of a multicomputer, for example, a network of PCs, and supports the unavailability of any k ≥ 1 of its server nodes. The value of k transparently grows with the file to offset the reliability decline. Only the number of the storage nodes potentially limits the file growth. The high-availability management uses a novel parity calculus that we have developed, based on Reed-Salomon erasure correcting coding. The resulting parity storage overhead is about the lowest possible. The parity encoding and decoding are faster than for any other candidate coding we are aware of. We present our scheme and its performance analysis, including experiments with a prototype implementation on Wintel PCs. The capabilities of LH* RS offer new perspectives to data intensive applications, including the emerging ones of grids and of P2P computing.

Signatures detect changes to data objects. Numerous schemes are in use, especially the cryptographically secure standards SHA-1. We propose a novel signature scheme which we call algebraic signatures. The scheme uses the Galois field calculations. Its major property is the sure detection of any changes up to a parameterized size. More precisely, we detect for sure any changes that do not exceed n-symbols for an n-symbol algebraic signature. This property is new for any known signature scheme. For larger changes, the collision probability is typically negligible, as for the other known schemes. We apply the algebraic signatures to the scalable distributed data structures (SDDS). We filter at the SDDS client node the updates that do not actually change the records. We also manage the concurrent updates to data stored in the SDDS RAM buckets at the server nodes. We further use the scheme for the fast disk backup of these buckets. We sign our objects with 4-byte signatures, instead of 20-byte standard SHA-1 signatures. Our algebraic calculus is then also about twice as fast.

LH*RS is a new high-availability Scalable Distributed Data Structure (SDDS). The data storage scheme and the search performance of LH*RS are basically these of LH*. LH*RS manages in addition the parity information to tolerate the unavailability of k ⪈ 1 server sites. The value of k scales with the file, to prevent the reliability decline. The parity calculus uses the Reed -Solomon Codes. The storage and access performance overheads to provide the high-availability are about the smallest possible. The scheme should prove attractive to data-intensive applications.

Declustered data organizations in disk arrays (RAIDs) achieve less-intrusive reconstruction of data after a disk failure. We present PDDL, a new data layout for declustered disk arrays. PDDL layouts exist for a large variety of disk array configurations with a distributed spare disk. PDDL declustered disk arrays have excellent run-time performance under light and heavy workloads. PDDL maximizes access parallelism in the most critical circumstances, namely during reconstruction of data on the spare disk. PDDL occurs minimum address translation overhead compared to all other proposed declustering layouts.

A disk array architecture that generalizes the RAID (redundant arrays of inexpensive disks) level V data organization while providing excellent storage utilization, response times, and fault tolerance is discussed. A key feature of the approach is that reliability groups can contain several check data disks beyond the single parity disk. RAID response times for fault-free and failure recovery operations are presented.>

The author present a file comparison scheme in which the signatures of individual pages are compared by means of a supersignature calculated from the individual page signature. A supersignature is obtained as a power series in a primitive root within the Galois field with 2/sup n/ elements. The coefficients are the signatures of the individual pages. With this scheme errors, such as missing, altered, or incorrectly placed pages, can be detected with the very probability, and an error diagnosis can be found if discrepancies are detected.>