**Lower bounds for orthogonal range searching: part II. The arithmetic model**

Bernard Chazelle

Pages: 439-463

DOI: 10.1145/79147.79149

Lower bounds on the complexity of orthogonal range searching in the
static case are established. Specifically, we consider the following
dominance search problem: Given a collection of
n weighted points in...

**A fast algorithm for optimal length-limited Huffman codes**

Lawrence L. Larmore, Daniel S. Hirschberg

Pages: 464-473

DOI: 10.1145/79147.79150

An O(nL)-time algorithm is introduced for constructing an optimal Huffman code for a weighted alphabet of size n, where each code string must have length no greater than L. The...

**On the equivalence of an Egd to a set of Fd's**

Marc H. Graham, Ke Wang

Pages: 474-490

DOI: 10.1145/79147.79151

The question “Is a given join dependency equivalent to some set of multivalued dependencies?” led to the development of acyclicity theory [1]. The central question of this paper is: “Is a given equality-generating dependency...

**Analysis of database performance with dynamic locking**

In Kyung Ryu, Alexander Thomasian

Pages: 491-523

DOI: 10.1145/79147.79152

A detailed model of a transaction processing system with dynamic locking is developed and analyzed. Transaction classes are distinguished on the basis of the number of data items accessed and the access mode (read-only/update). The performance...

**Renaming in an asynchronous environment**

Hagit Attiya, Amotz Bar-Noy, Danny Dolev, David Peleg, Rüdiger Reischuk

Pages: 524-548

DOI: 10.1145/79147.79158

This paper is concerned with the solvability of the problem of processor renaming in unreliable, completely asynchronous distributed systems. Fischer et al. prove in [8] that “nontrivial consensus” cannot be attained in such systems,...

**Knowledge and common knowledge in a distributed environment**

Joseph Y. Halpern, Yoram Moses

Pages: 549-587

DOI: 10.1145/79147.79161

Reasoning about knowledge seems to play a fundamental role in distributed systems. Indeed, such reasoning is a central part of the informal intuitive arguments used in the design of distributed protocols. Communication in a distributed system...

**Parallel asynchronous algorithms for discrete data**

Aydin Üresin, Michel Dubois

Pages: 588-606

DOI: 10.1145/79147.79162

Many problems in the area of symbolic computing can be solved by iterative algorithms. Implementations of these algorithms on multiprocessors can be synchronous or asynchronous. Asynchronous implementations are potentially more efficient because...

**Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length**

Ariel Orda, Raphael Rom

Pages: 607-625

DOI: 10.1145/79147.214078

In this paper the shortest-path problem in networks in which the delay (or weight) of the edges changes with time according to arbitrary functions is considered. Algorithms for finding the shortest path and minimum delay under various waiting...

**An efficient and fast parallel-connected component algorithm**

Yujie Han, Robert A. Wagner

Pages: 626-642

DOI: 10.1145/79147.214077

A parallel algorithm for computing the connected components of undirected graphs is presented. Shared memory computation models are assumed. For a graph of e edges and n nodes, the time complexity of the...

**Approximate mean value analysis algorithms for queuing networks**: existence, uniqueness, and convergence results

K. R. Pattipati, M. M. Kostreva, J. L. Teele

Pages: 643-673

DOI: 10.1145/79147.214074

This paper is concerned with the properties of nonlinear equations associated with the Scheweitzer-Bard (S-B) approximate mean value analysis (MVA) heuristic for closed product-form queuing networks. Three forms of nonlinear S-B approximate MVA...

**Nondeterministic linear-time tasks may require substantially nonlinear deterministic time in the case of sublinear work space**

Yuri Gurevich

Pages: 674-687

DOI: 10.1145/79147.214070

A technique is developed for establishing lower bounds on the computational complexity of certain natural problems. The results have the form of time-space trade-off and exhibit the power of nondeterminism. In particular, a form of the clique...