Marshall C. Pease, Robert E. Shostak, Leslie Lamport
The problem addressed here concerns a set of isolated processors, some unknown subset of which may be faulty, that communicate only by means of two-party messages. Each nonfaulty processor has a private value of information that must be communicated ...
Martin Reiser, Stephen S. Lavenberg
It is shown that mean queue sizes, mean waiting times, and throughputs in closed multiple-chain queuing networks which have product-form solution can be computed recursively without computing product terms and normalization constants. The resulting ...
The notion of the congruence closure of a relation on a graph is defined and several algorithms for computing it are surveyed. A simple proof is given that the congruence closure algorithm provides a decision procedure for the quantifier-free theory ...
A class of first-order databases with no function signs is considered. A closed database DB is one for which the only existing individuals are those explicitly referred to in the formulas of DB. Formally, this is expressed by including in DB a domain ...
An algorithm is given for deciding whether a functional or a multivalued dependency &sgr; (with a right-hand side Y) is implied by a set of functional and multivalued dependencies &Sgr;. The running time of the algorithm is O(| Y ...
Stephen A. Ward, Robert H. Halstead Jr
Recent developments by Hewitt and others have stimulated interest in message-passing constructs as an alternative to the more conventional applicative semantics on which most current languages are based. The present work illuminates the distinction ...
David Lichtenstein, Michael Sipser
It is shown that, given an arbitrary GO position on an n × n board, the problem of determining the winner is Pspace hard. New techniques are exploited to overcome the difficulties arising from the planar nature of board games. In particular, it is ...
In the bin-packing problem a list L of n numbers are to be packed into unit-capacity bins. For any algorithm S, let r(S) be the maximum ratio S(L)/L* for large L*, where S(L) denotes the number of bins used by S and L* denotes the minimum number ...
A model of a closed queuing network within which customer routing between queues may depend on the state of the network is presented. The routing functions allowed may be rational functions of the queue lengths of various downstream queues which ...
The problem of determining whether it is possible for a set of “free-running” processes to become deadlocked is considered. It is assumed that any request by a process is immediately granted as long as there are enough free resource units to ...