**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...