Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 34 Issue 1, Jan. 1987

Intersection of convex objects in two and three dimensions
B. Chazelle, D. P. Dobkin
Pages: 1-27
DOI: 10.1145/7531.24036
One of the basic geometric operations involves determining whether a pair of convex objects intersect. This problem is well understood in a model of computation in which the objects are given as input and their intersection is returned as...

Dynamic functional dependencies and database aging
Victor Vianu
Pages: 28-59
DOI: 10.1145/7531.7918
A simple extension of the relational model is introduced to study the effects of dynamic constraints on database evolution. Both static and dynamic constraints are used in conjunction with the model. The static constraints considered here are...

A logarithmic time sort for linear size networks
John H. Reif, Leslie G. Valiant
Pages: 60-76
DOI: 10.1145/7531.7532
A randomized algorithm that sorts on an N node network with constant valence in O(log N) time is given. More particularly, the algorithm sorts N items on an...

On the minimal synchronism needed for distributed consensus
Danny Dolev, Cynthia Dwork, Larry Stockmeyer
Pages: 77-97
DOI: 10.1145/7531.7533
Reaching agreement is a primitive of distributed computing. Whereas this poses no problem in an ideal, failure-free environment, it imposes certain constraints on the capabilities of an actual system: A system is viable only if it permits the...

Electing a leader in a synchronous ring
Greg N. Frederickson, Nancy A. Lynch
Pages: 98-115
DOI: 10.1145/7531.7919
The problem of electing a leader in a synchronous ring of n processors is considered. Both positive and negative results are obtained. On the one hand, if processor IDS are chosen from some countable set, then there is an...

How to share memory in a distributed system
Eli Upfal, Avi Wigderson
Pages: 116-127
DOI: 10.1145/7531.7926
The power of shared-memory in models of parallel computation is studied, and a novel distributed data structure that eliminates the need for shared memory without significantly increasing the run time of the parallel computation is described....

On the Church-Rosser property for the direct sum of term rewriting systems
Yoshihito Toyama
Pages: 128-143
DOI: 10.1145/7531.7534
The direct sum of two term rewriting systems is the union of systems having disjoint sets of function symbols. It is shown that if two term rewriting systems both have the Chruch-Rosser property, then the direct sum of these systems also has...

Using dual approximation algorithms for scheduling problems theoretical and practical results
Dorit S. Hochbaum, David B. Shmoys
Pages: 144-162
DOI: 10.1145/7531.7535
The problem of scheduling a set of n jobs on m identical machines so as to minimize the makespan time is perhaps the most well-studied problem in the theory of approximation algorithms for NP-hard optimization...

Simultaneous WRITES of parallel random access machines do not help to compute simple arithmetic functions
Rüdiger Reischuk
Pages: 163-178
DOI: 10.1145/7531.22944
The ability of the strongest parallel random access machine model WRAM is investigated. In this model different processors may simultaneously try to write into the same cell of the common memory. It has been shown that a parallel RAM without...

Analysis of a composite performance reliability measure for fault-tolerant systems
Lorenzo Donatiello, Balakrishna R. Iyer
Pages: 179-199
DOI: 10.1145/7531.7536
Today's concomitant needs for higher computing power and reliability has increased the relevance of multiple-processor fault-tolerant systems. Multiple functional units improve the raw performance (throughput, response time, etc.) of the system,...

Slowing down sorting networks to obtain faster sorting algorithms
Richard Cole
Pages: 200-208
DOI: 10.1145/7531.7537
Megiddo introduced a technique for using a parallel algorithm for one problem to construct an efficient serial algorithm for a second problem. This paper provides a general method that trims a factor of O(log n)...

Hard examples for resolution
Alasdair Urquhart
Pages: 209-219
DOI: 10.1145/7531.8928
Exponential lower bounds are proved for the length-of-resolution refutations of sets of disjunctions constructed from expander graphs, using the method of Tseitin. Since these sets of clauses encode biconditionals, they have short...