A novel extension to binary-tree table organization suitable for external storage providing successful searches for nearly full tables requiring less than two accesses is presented. The generalizes the "efficient ordering of hash tables" effort presented in 1979. Both the experimental and analytical results demonstrate the reductions possible. This method places no restrictions on the the table configuration parameters and requires no additional space per bucket. The insertion runtime is larger slightly than for ordinary external double hashing.

We present B a novel data layout method for tolerating multiple disk failures within disk arrays. In a disk array with 2n disks, B tolerates at most 2(n - 1) simultaneous failures; reconstruction work is spread over the surviving disks using only exclusive-or operations. The data layout is based upon B array-codes; our approach provides an efficient software implementation. B utilizes the minimal amount of redundant storage space. Our detailed performance comparison with RAID-5 and EVENODD shows B read operations to be very competitive especially in the presence of failures; B write operations are more expensive than RAID-5 and EVENODD write operations. In the presence of failures, the performance gradually degrades as the number of failures increases.

We present a novel data organization for disk arrays-segmented information dispersal(SID). SID provides protection against disk failures while ensuring that the reconstruction of the missing data requires only relatively small contiguous accesses to the available disks. SID has a number of properties that make it an attractive solution for fault-tolerant video servers. Under fault-free conditions, SID performs as well as RAID 5 and organizations based on balanced incomplete block designs (BIBD). Under failure, SID performs much better than RAID 5 since it significantly reduces the size of the disk accesses performed by the reconstruction process. SID also performs much better than BIBD by ensuring the contiguity of the reconstruction accesses. Contiguity is a very significant factor for video retrieval workloads, as we demonstrate. We present SID data organizations with a concise representation which enables the reconstruction process to efficiently locate the needed video and check data.

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.

This paper investigates the placement of data and parity on redundant disk arrays. Declustered organizations have been traditionally used to achieve fast reconstruction of a failed disk's contents. In previous work, Holland and Gibson identified six desirable properties for ideal layouts; however no declustered layout satisfying all properties has been published in the literature. We present a complete, constructive characterization of the collection of ideal declustered layouts possessing all six properties. Given that ideal layouts exist only for a limited set of configurations, we also present two novel layout families. PRIME and RELPR can tolerate multiple failures in a wide variety of configurations with slight deviations from the ideal. Our simulation studies show that the new layouts provide excellent parallel access performance and reduced incremental loads during degraded operation, when compared with previously published layouts. For large accesses and under high loads, response times for the new layouts are typically smaller than those of previously published declustered layouts by a factor of 2.5.

We present DATUM, a novel method for tolerating multiple disk failures in disk arrays. DATUM is the first known method that can mask any given number of failures, requires an optimal amount of redundant storage space, and spreads reconstruction accesses uniformly over disks in the presence of failures without needing large layout tables in controller memory. Our approach is based on information dispersal, a coding technique that admits an efficient hardware implementation. As the method does not restrict the configuration parameters of the disk array, many existing RAID organizations are particular cases of DATUM. A detailed performance comparison with two other approaches shows that DATUM'S response times are similar to those of the best competitor when two or less disks fail, and that the performance degrades gracefully when more than two disks fail.

Article Segmented information dispersal (SID) for efficient reconstruction in fault-tolerant video servers Share on Authors: Ariel Cohen Gemini Storage Systems Laboratory, Department of Computer Science & Engineering, University of California, San Diego, La Jolla, CA Gemini Storage Systems Laboratory, Department of Computer Science & Engineering, University of California, San Diego, La Jolla, CAView Profile , Walter A. Burkhard Gemini Storage Systems Laboratory, Department of Computer Science & Engineering, University of California, San Diego, La Jolla, CA Gemini Storage Systems Laboratory, Department of Computer Science & Engineering, University of California, San Diego, La Jolla, CAView Profile Authors Info & Claims MULTIMEDIA '96: Proceedings of the fourth ACM international conference on MultimediaFebruary 1997 Pages 277–286https://doi.org/10.1145/244130.244228Online:01 February 1997Publication History 9citation232DownloadsMetricsTotal Citations9Total Downloads232Last 12 Months1Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

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.>

The authors propose and prove a distributed algorithm for detection and resolution of resource deadlocks in object-oriented distributed systems. In particular, the algorithm can be used in conjunction with concurrency control algorithms which are based on the semantic lock model. The algorithm greatly reduces message traffic by properly identifying and eliminating redundant messages. It is shown that both its worst and average time complexities are O(n*e), where n is the number of nodes and e is the number of edges in the waits-for graph. After deadlock resolution, the algorithm leaves information in the system concerning dependence relations of currently running transactions. This information will preclude the wasteful retransmission of messages and reduce the delay in detecting future deadlocks.>

A distributed algorithm is proposed for detection and resolution of resource deadlocks in object-oriented distributed systems. The algorithm can be used in conjunction with concurrency control algorithms that are based on the semantic lock model. To drastically reduce message traffic, the algorithm properly identifies and eliminates redundant messages. It is shown that its worst and average time complexities are O(ne), where e is the number of edges in the waits-for graph and n is the number of vertices.>

We propose a distributed algorithm for detection and resolution of resource deadlocks in object-oriented distributed systems. The algorithm proposed is shown to detect and resolve all O(n1) cycles present in the worst case waits-for-graph (WFG) with n vertices by transmitting O(n3) messages of small constant size. Its average time complexity has been shown to be O(ne), where e is the number of edges in the WFG After deadlock resolution, the algorithm leaves information in the system concerning dependence relations of running transactions. This information will preclude the wasteful retransmission of messages and reduce the delay in detecting future deadlocks.

The Gemini system is a replicated file system test-bed designed for local area networks and is built using ordinary host UNIX machines. Gemini was designed as a means to empirically test consistency and recovery schemes for replicated files in a distributed environment. A principle objective is to protect files against a fixed number of host and network failures while maintaining consistent data. Gemini replicated files are implemented as several copies of ordinary files that reside on distinct hosts. We present the Gemini system test-bed design and discuss three consistency and recovery schemes: voting with witnesses, dynamic voting, and semi-synchronous control. Empirical and analytic performance results are presented.

A file maintenance model, called the multiple random access storage units model, is introduced. Storage units can be accessed simultaneously, and the parallel processing of an associative query is achieved by distributing data evenly among the storage units. Maximum parallelism is obtained when data satisfying an associative query are evenly distributed for every possible query. An allocation scheme called M -cycle allocation is proposed to maintain large files of data on multiple random access storage units. The allocation scheme provides an efficient and straightforward indexing over multidimensional key spaces and supports the parallel processing of orthogonal range queries. Our analysis shows that M -cycle allocation achieves the near-optimum parallelism for processing the orthogonal range queries. Moreover, there is no duplication of records and no increase in insertion/deletion cost.

No abstract available.

Article Free Access Share on Index maintenance for non-uniform record distributions Author: Walter A. Burkhard University of California, San Diego, La Jolla, California University of California, San Diego, La Jolla, CaliforniaSearch about this author Authors Info & Claims PODS '84: Proceedings of the 3rd ACM SIGACT-SIGMOD symposium on Principles of database systemsApril 1984Pages 173–179https://doi.org/10.1145/588011.588036Published:02 April 1984Publication History 8citation219DownloadsMetricsTotal Citations8Total Downloads219Last 12 Months8Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

A new interpolation-based order preserving hashing algorithm suitable for on-line maintenance of large dynamic external files under sequences of four kinds of operations insertion, update, deletion, and orthogonal range query is proposed. The scheme, an adaptation of linear hashing, requires no index or address directory structure and utilizes O(n) space for files containing n records, all of the benefits of linear hashing are inherited by this new scheme. File implementations yielding average successful search lengths much less than 2 and average unsuccessful search lengths much less than 4 for individual records are obtainable, the actual storage required is controllable by the implementor.

File designs suitable for retrieval from a file of k -field records when queries may be partially specified are examined. Storage redundancy is introduced to obtain improved worst-case and average-case performances. The resulting storage schemes are appropriate for replicated distributed database environments; it is possible to improve the overall average and worst-case behavior for query response as well as provide an environment with very high reliability. Within practical systems it will be possible to improve the query response time performance as well as reliability over comparable systems without replication.

Data base designs for retrieval from a file of k-letter records when queries may be only partially specified are examined. A family of data base designs referred to as the H αβκ PMF-trie designs which yield a data structure with good worst case and average case performances and requires an amount of storage space essentially equal to that required of the records themselves is introduced. The analysis of the designs including bounds on the worst case performance and an explicit expression for the average performance is presented. Previously known families of PMF-trie designs are seen to be special cases within the H αβκ family.

File designs suitable for retrieval from a file of k -letter words when queries may be only partially specified are examined. A new class of partial match file designs (called PMF designs) based upon hash coding and trie search algorithms which provide good worst-case performance is introduced. Upper bounds on the worst-case performance of these designs are given along with examples of files achieving the bound. Other instances of PMF designs are known to have better worst-case performances. The implementation of the file designs with associated retrieval algorithms is considered. The amount of storage required is essentially that required of the records themselves.

Tnis paper is concernd with information retrieval based upon secondary keys; that is, keys which cannot in general uniquely identify a record, but can indicate certain attributes of the associated record. Partial-match retrieval deals with accessing and reading those records of a data base which match the user's query albeit the query is only partially specified. For example, suppose that 'the data base consists of the binary words 1010, 1110, 0011, 1101, 0010, 1111. The response to query 1**0 where * is a don't know symbol is the set of records with keys 1010 or 1110 while the response to query 1101 is the set of records with key 1101.

A scatter table search technique incorporating methods of the quadratic quotient search as well as the full table quadratic search is presented. The advantages of both techniques are retained. For table sizes a prime of the form 4j + 3, the full table quadratic quotient search can access the entire scatter table via a computationally simple technique. Both primary and secondary clustering are avoided as well. Simulation results are presented for several of the search techniques.

Efficient, nonrecursive algorithms are given for postorder, symmetric order, and preorder traversals of binary trees. In particular, the algorithms require only a fixed amount of space independent of tree size. The binary trees are implemented as an ordered natural implementation with no extra flag fields. The traversal algorithms each run in time proportional to the tree size. Proofs of correctness for the three algorithms are presented.

The study of computational complexity is continued under the additional requirement that the Turing machines operate in real time. The work reported here is motivated by that of Rabin [R] which asks implicitly about the computational power of n tape vs n+1 tape real time Turing machines and that of Hartmanis [H] who attempts a complexity measure for Turing machines in terms of reversals.