Alpine is a file system that supports atomic transactions and is designed to operate as a service on a computer network. Alpine's primary purpose is to store files that represent databases. An important secondary goal is to store ordinary files representing documents, program modules, and the like. Unlike other file servers described in the literature, Alpine uses a log-based technique to implement atomic file update. Another unusual aspect of Alpine is that it performs all communication via a general-purpose remote procedure call facility. Both of these decisions have worked out well. This paper describes Alpine's design and implementation, and evaluates the system in light of our experience to date. Alpine is written in Cedar, a strongly typed modular programming language that includes garbage-collected storage. We report on using the Cedar language and programming environment to develop Alpine.

In this paper we explore the use of 2-3 trees to represent sorted lists. We analyze the worst-case cost of sequences of insertions and deletions in 2-3 trees under each of the following three assumptions: (i) only insertions are performed; (ii) only deletions are performed; (iii) deletions occur only at the small end of the list and insertions occur only away from the small end. Our analysis leads to a data structure for representing sorted lists when the access pattern exhibits a (perhaps time-varying) locality of reference. This structure has many of the properties of the representation proposed by Guibas, McCreight, Plass and Roberts [A new representation for linear lists, Proc. Ninth Annual Symposium on Theory of Computing, Boulder, CO, 1977, pp. 49–60], but it is substantially simpler and may be practical for lists of moderate size.

We prove an asymptotic lower bound of 3.52n nonscalar multiplications for (degree n – 1 by degree n – 1) polynomial multiplication in a model which allows only integers as scalars. Index Terms-Algebraic complexity, lower bound, polynomial multiplication.

An algonthm that merges sorted hsts represented as height-balanced binary trees 1s given If the hsts have lengths m and n (m _< n) then the merging procedure runs m O(m log(n/m)) steps, which is the same order as the lower bound on all companson-based algorithms for this problem

The collection of nodes nearest to the external nodes in a random height-balanced tree is analyzed. We determine the proportion of balanced nodes in this section of the tree, and find the average number of single and double rotations which occur at the minimum height during insertions. If $\bar B_n $ denotes the average number of balanced nodes in a random height-balanced tree with n internal nodes, we show that $\frac{{10}}{{21}} (n + 1) \leqq \bar B_n \leqq \frac{6}{7}(n + 1) - 1$ for $n \geqq 6$.

This paper describes a data structure which is useful for representing linear lists when the pattern of accesses to a list exhibits a (perhaps time-varying) locality of reference. The structure has many of the properties of the representation proposed by Guibas, McCreight, Plass, and Roberts [4], but is substantially simpler and may be practical for lists of moderate size. The analysis of our structure includes a general treatment of the worst-case node splitting caused by consecutive insertions into a 2-3 tree.

The binomial queue, a new data structure for implementing priority queues that can be efficiently merged, was recently discovered by Jean Vuillemin; we explore the properties of this structure in detail. New methods of representing binomial queues are given which reduce the storage overhead of the structure and increase the efficiency of operations on it. One of these representations allows any element of an unknown priority queue to be deleted in log time, using only two pointers per element of the queue. A complete analysis of the average time for insertion into and deletion from a binomial queue is performed. This analysis is based on the result that the distribution of keys in a random binomial queue is also the stationary distribution obtained after repeated insertions and deletions.

A notion of priority queue efficiency is defined, based on comparison counting. A good lower bound on the average and worst case number of comparisons is derived; several priority queue algorithms are exhibited which nearly attain the bound. It is shown that one of these algorithms, using binomial queues, can be characterized in a simple way based on the number and type of comparisons that it requires. The proof of this result involves an interesting problem on trees for which Huffman's construction gives a solution.