Consider a database containing not only base relations but also stored derived relations (also called materialized or concrete views). When a base relation is updated, it may also be necessary to update some of the derived relations. This paper gives sufficient and necessary conditions for…
For some time I had been looking for a mutual exclusion algorithm that satisfied my complete list of desirable properties. I finally found one--the N!-bit algorithm described in this paper. The algorithm is wildly impractical, requiring N! bits of storage for N processors, but practicality…
It is shown that there is a unique configuration of toroidal magnetic surfaces which has the property that it corresponds to more than one plasma equilibrium and that this is the configuration ofisodynamic equilibria. These equilibria include toroidal minimum-B equilibria and the distinction between these…
Most computer scientists regard synchronization problems, such as the mutual exclusion problem, to be problems of mathematics. How can you use one class of mathematical objects, like atomic reads and writes, to implement some other mathematical object, like a mutual exclusion algorithm? I have always…
Soon after I arrived at SRC, I was approached by some people at WRL (Digital's Western Research Laboratory) who were building a multiprocessor computer. They wanted to avoid having to add synchronization instructions, so they wanted to know how efficiently mutual exclusion could be implemented…
This paper describes a file system for a programmer's workstation that has access both to a local disk and to remote file servers. The file system is designed to help programmers manage their local naming environments and share consistent versions of collections of software. It…
Maximum-likelihood estimates of the parameters of exponentially damped sinusoidal signals in noise can be found by using an iterative procedure based on Newton's method. The initial estimate is obtained by an improved linear-prediction method. The properties of the Newton estimates obtained from short data records…
This paper describes a cryptographic scheme for holding a secure secret ballot election in which all communication is public. Voters cast their votes electronically, suitably encrypted, and a “government” releases a tally and a proof of its correctness which can be verified by all.
This paper appeared in a workshop held in Colle-sur-Loup, in the south of France, in October, 1984. There is a long history of work on the semantics of programming languages. When people began studying concurrency in the 70s, they naturally wrote about the semantics of…
In this chapter we make a case for the monadic second-order logic (that is to say, for the extension of first-order logic allowing quantification over monadic predicates) as a good source of theories that are both expressive and manageable. We illustrate two powerful decidability techniques…
Define a tree to be any partial order satisfying the following requirement: if (y < x and z < x) then (y < z or y = z or y > z). The main result of the two papers [62, 63] is the decidability of…
The first announcement of the "new thesis", latern known as the Abstract State Machine thesis.
