Matthew Hennessy, Robin Milner
Since a nondeterministic and concurrent program may, in general, communicate repeatedly with its environment, its meaning cannot be presented naturally as an input/output function (as is often done in the denotational approach to semantics). In this ...
Leslie Lamport, P. Michael Melliar-Smith
Algorithms are described for maintaining clock synchrony in a distributed multiprocess system where each process has its own clock. These algorithms work in the presence of arbitrary clock or process failures, including “two-faced clocks” that ...
Dorit S. Hochba, Wolfgang Maass
A unified and powerful approach is presented for devising polynomial approximation schemes for many strongly NP-complete problems. Such schemes consist of families of approximation algorithms for each desired performance bound on the relative error ...
Byzantine Agreement has become increasingly important in establishing distributed properties when errors may exist in the systems. Recent polynomial algorithms for reaching Byzantine Agreement provide us with feasible solutions for obtaining ...
Jeffrey C. Lagarias, Andrew M. Odlyzko
The subset sum problem is to decide whether or not the 0-l integer programming problem &Sgr;ni=l aixi = M, ∀I, xI = 0 or 1, has a solution, where the ai and M are given positive integers. This problem is NP-complete, and the difficulty of ...
Two new marking algorithms for AND/OR graphs called CF and CS are presented. For admissible heuristics CS is not needed, and CF is shown to be preferable to the marking algorithms of Martelli and Montanari. When the heuristic is not admissible, the ...
Lengauer and Tarjan proved that the number of black and white pebbles needed to pebble the root of a tree is at least half the number of black pebbles needed to pebble the root. This result is extended to a larger class of acyclic directed graphs ...
Three different approaches to heuristic search in networks are analyzed. In the first approach, as formulated initially by Hart, Nilsson, and Raphael, and later modified by Martelli, the basic idea is to choose for expansion that node for which the ...
Shimon Even, Alan L. Selman, Yacov Yacobi
Nancy Lynch proved that if a decision problem A is not solvable in polynomial time, then there exists an infinite recursive subset X of its domain on which the decision is almost everywhere complex. In this paper, general theorems of this kind that ...
An aggregative technique to obtain an improved approximation of the equilibrium vector of a Markov chain with a nearly completely decomposable transition matrix is presented. The technique is demonstrated on a model of a multiprogrammed computer ...