Microsoft Research Blog

English

  1. How to Tell a Program from an Automobile 

    January 28, 1977 | Leslie Lamport

    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…

  2. Models of Light Reflection for Computer Synthesized Pictures 

    January 1, 1977 | Jim Blinn

    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…

  3. Storage allocation in typed languages 

    January 1, 1977 | Butler Lampson

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

  4. On the Glitch Phenomenon 

    November 5, 1976 | Leslie Lamport and Richard Palais

    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…

  5. Texture and Reflection in Computer Generated Images 

    October 1, 1976 | Jim Blinn

    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…

  6. Semi-conservative Reduction 

    August 9, 1976 | Yuri Gurevich

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

  7. The Decision Problem for Standard Classes 

    August 8, 1976 | Yuri Gurevich

    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.

  8. Relevance weighting of search terms 

    January 1, 1976 | Stephen Robertson and K. Sparck Jones

    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…

  9. Engineering a security kernel for Multics 

    October 1, 1975 | Mike Schroeder

    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…

  10. The protection of information in computer systems 

    September 1, 1975 | Mike Schroeder

    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…

  11. Multiple Byte Processing with Full-Word Instructions 

    August 8, 1975 | Leslie Lamport

    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…

  12. On Self-stabilizing Systems 

    December 5, 1974 | Leslie Lamport

    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…