Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 42 Issue 1, Jan. 1995

The complexity of logic-based abduction
Thomas Eiter, Georg Gottlob
Pages: 3-42
DOI: 10.1145/200836.200838
Abduction is an important form of nonmonotonic reasoning allowing one to find explanations for certain symptoms or manifestations. When the application domain is described by a logical theory, we speak about logic-based...

Reasoning about temporal relations: a maximal tractable subclass of Allen's interval algebra
Bernhard Nebel, Hans-Jürgen Bürckert
Pages: 43-66
DOI: 10.1145/200836.200848
We introduce a new subclass of Allen's interval algebra we call “ORD-Horn subclass,” which is a strict superset of the “pointisable subclass.” We prove that reasoning in the ORD-Horn subclass is a polynomial-time problem...

A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields
Paul B. Callahan, S. Rao Kosaraju
Pages: 67-90
DOI: 10.1145/200836.200853
We define the notion of a well-separated pair decomposition of points in d-dimensional space. We then develop efficient sequential and parallel algorithms for computing such a decomposition. We apply the...

Planar-adaptive routing: low-cost adaptive networks for multiprocessors
Andrew A. Chien, Jae H. Kim
Pages: 91-123
DOI: 10.1145/200836.200856
Network throughput can be increased by allowing multipath, adaptive routing. Adaptive routing allows more freedom in the paths taken by messages, spreading load over physical channels more evenly. The flexibility of adaptive routing introduces...

Sharing memory robustly in message-passing systems
Hagit Attiya, Amotz Bar-Noy, Danny Dolev
Pages: 124-142
DOI: 10.1145/200836.200869
Emulators that translate algorithms from the shared-memory model to two different message-passing models are presented. Both are achieved by implementing a wait-free, atomic, single-writer multi-reader register in unreliable, asynchronous...

Dynamic fault-tolerant clock synchronization
Danny Dolev, Joseph Y. Halpern, Barbara Simons, Ray Strong
Pages: 143-185
DOI: 10.1145/200836.200870
This paper gives two simple efficient distributed algorithms: one for keeping clocks in a network synchronized and one for allowing new processors to join the network with their clocks synchronized. Assuming a fault-tolerant authentication...

Constructing 1-writer multireader multivalued atomic variables from regular variables
S. Haldar, K. Vidyasankar
Pages: 186-203
DOI: 10.1145/200836.200871
A simple wait-free construction of 1-writer multireader multivalued atomic variable from multireader regular variables is presented in this paper. A key point of the construction is the use of an elegant forwarding technique to overcome the...

Bounds on the speedup and efficiency of partial synchronization in parallel processing systems
C. S. Chang, R. Nelson
Pages: 204-231
DOI: 10.1145/200836.200872
In this paper, we derive bounds on the speedup and efficiency of applications that schedule tasks on a set of parallel processors. We assume that the application runs an algorithm that consists of N iterations and before...

Bisimulation can't be traced
Bard Bloom, Sorin Istrail, Albert R. Meyer
Pages: 232-268
DOI: 10.1145/200836.200876
In the concurrent language CCS, two programs are considered the same if they are bisimilar. Several years and many researchers have demonstrated that the theory of bisimulation is mathematically appealing and useful in practice....

Designing programs that check their work
Manuel Blum, Sampath Kannan
Pages: 269-291
DOI: 10.1145/200836.200880
A program correctness checker is an algorithm for checking the output of a computation. That is, given a program and an instance on which the program is run, the checker certifies whether the output of the program on that...