I wrote this brief note in January, 1977. It came about because I was struck by the use of the term program maintenance, which conjured up in my mind images of lubricating the branch statements and cleaning the pointers. So, I wrote this to make…
In the production of computer generated pictures of three-dimensional objects, one stage of the calculation is the determination of the intensity of a given object once its visibility has been established. This is typically done by modeling the surface as a perfect diffuser, sometimes with…
Several interfaces between a strongly typed language and a storage allocator or deallocator are defined. Using these interfaces, it is possible to program a wide variety of allocation and automatic deallocation strategies: boundary tag allocator, buddy system, reference counting, trace-and-mark garbage collection and many others.…
When I wrote [12], a colleague at Massachusetts Computer Associates pointed out that the concurrent reading and writing of a single register, assumed in the bakery algorithm, requires an arbiter--a device for making a binary decision based on inputs that may be changing. In the…
In 1974 Catmull developed a new algorithm for rendering images of bivariate surface patches. This paper describes extensions of this algorithm in the areas of texture simulation and lighting models. The parameterization of a patch defines a coordinate system which is used as a key…
Let L be the set of formulas of an ordinary version of the first order predicate calculus. The term "class" is used for "subset of L".
The classification of prefix-signature fragments of (first-order) predicate logic with equality, completed in [7], is extended to first-order logic with equality and functions. One case was solved (confirming a conjecture of this author) by Saharon Shelah.
This paper examines statistical techniques for exploiting relevance information to weight search terms. These techniques are presented as a natural extension of weighting methods using information about the distribution of index terms in documents in general. A series of relevance weighting functions is derived and…
This paper describes a research project to engineer a security kernel for Multics, a general-purpose, remotely accessed, multiuser computer system. The goals are to identify the minimum mechanism that must be correct to guarantee computer enforcement of desired constraints on information access, to simplify the…
This tutorial paper explores the mechanics of protecting computer-stored information from unauthorized use or modification. It concentrates on those architectural structures--whether hardware or software--that are necessary to support information protection. The paper develops in three main sections. Section I describes desired functions, design principles, and…
My algorithms for parallelizing loops, described in papers starting with [9], were rather inefficient. They could be sped up with parallel execution on an array processor like the Illiac-IV. But I realized one could do even better than the 64-times speedup provided by the Illiac's…
This note was written upon reading Dijkstra's classic paper "Self-stabilizing Systems in Spite of Distributed Control" that appeared in the November 1974 issue of CACM (see [58]). It generalizes one of the algorithms in Dijkstra's paper from a line of processes to an arbitrary tree…
