It has long been accepted that, in documentary information retrieval, we can seldom expect to find a document or documents that match the initial statement of a query precisely in every detail. Some documents may be found which match the query to a greater or…
Use of encryption to achieve authenticated communication in computer networks is discussed. Example protocols are presented for the establishment of authenticated connections, for the management of authenticated mail, and for signature verification and document integrity guarantee. Both conventional and public-key encryption algorithms are considered as…
This paper presents the first concurrent garbage collection algorithm--that is, an algorithm in which the collector operates concurrently with the process that creates the garbage. The paper is fairly well known; its history is not. I received an early version of the paper from Dijkstra,…
When it became clear that computers were going to be flying commercial aircraft, NASA began funding research to figure out how to make them reliable enough for the task. Part of that effort was the SIFT project at SRI. This project was perhaps most notable…
Formal database semantics has concentrated on dependency constraints, such as functional and multivalued dependencies, and on normal forms for relations. Unfortunately, much of this work has been inaccessible to researchers outside this field, due to the unfamiliar formalism in which the work is couched. In…
In [27], I introduced the idea of implementing any distributed system by using an algorithm to implement an arbitrary state machine in a distributed system. However, the algorithm in [27] assumed that processors never fail and all messages are delivered. This paper gives a fault-tolerant…
Jim Gray once told me that he had heard two different opinions of this paper: that it's trivial and that it's brilliant. I can't argue with the former, and I am disinclined to argue with the latter. The origin of this paper was the note…
The CAP filing system [Needham and Birrell 1977] is able to produce garbage or 'lost objects' on disc, because its directory structure is a general naming network containing, in principle, cyclic substructures. Such substructures may become inaccessible as a result of deletion of capabilities or…
The title says it all. This one-page note is as relevant today as when I wrote it. Replace "describing the solution" by "writing the program" and it becomes a practical recipe for improving software.
Computer generated shaded images have reached an impressive degree of realism with the current state of the art. They are not so realistic, however, that they would fool many people into believing they are real. One problem is that the surfaces tend to look artificial…
This paper presents a scan line algorithm for drawing pictures of parametrically defined surfaces. A scan line algorithm is characterized by the order in which it generates the picture elements of the image. These are generated left to right, top to bottom in much the…
