**Convexity algorithms in parallel coordinates**

Alfred Inselberg, Mordechai Reif, Tuval Chomut

Pages: 765-801

DOI: 10.1145/31846.32221

With a system of parallel coordinates, objects in RN can be represented with planar “graphs” (i.e., planar diagrams) for arbitrary N [21]. In...

**Randomized parallel communications on an extension of the omega network**

D. Mitra, R. A. Cieslak

Pages: 802-824

DOI: 10.1145/31846.42226

Parallel communication algorithms and networks are central to large-scale parallel computing and, also, data communications. This paper identifies adverse source-destination traffic patterns and proposes a scheme for obtaining relief by means of...

**Design and analysis of dynamic Huffman codes**

Jeffrey Scott Vitter

Pages: 825-845

DOI: 10.1145/31846.42227

A new one-pass algorithm for constructing dynamic Huffman codes is introduced and analyzed. We also analyze the one-pass algorithm due to Faller, Gallager, and Knuth. In each algorithm, both the sender and the receiver maintain equivalent...

**Multidimensional search trees that provide new types of memory reductions**

Dan E. Willard

Pages: 846-858

DOI: 10.1145/31846.42228

An orthogonal query that asks to aggregate the set of records in k-dimensional box regions is studied, and it is shown that space O(N((log N)/(log log...

**A weighted voting algorithm for replicated directories**

Joshua J. Bloch, Dean S. Daniels, Alfred Z. Spector

Pages: 859-909

DOI: 10.1145/31846.31847

Weighted voting is used as the basis for a replication technique for directories. This technique affords arbitrarily high data availability as well as high concurrency. Efficient algorithms are presented for all of the standard directory...

**An O(log n) expected rounds randomized byzantine generals protocol**

Gabriel Bracha

Pages: 910-920

DOI: 10.1145/31846.42229

Byzantine Generals protocols enable processes to broadcast messages reliably in the presence of faulty processes. These protocols are run in a system that consists of n processes, t of which are faulty. The...

**Lower bounds on communication complexity in distributed computer networks**

Prasoon Tiwari

Pages: 921-938

DOI: 10.1145/31846.32978

The main result of this paper is a general technique for determining lower bounds on the communication complexity of problems on various distributed computer networks. This general technique is derived by simulating the general network by a...

**On the discrepancy of GFSR pseudorandom numbers**

Shu Tezuka

Pages: 939-949

DOI: 10.1145/31846.31848

A new summation formula based on the orthogonal property of Walsh functions is devised. Using this formula, the k-dimensional discrepancy of the generalized feedback shift register (GFSR) pseudorandom numbers is derived. The...

**Parallel algorithms for minimum cuts and maximum flows in planar networks**

Donald B. Johnson

Pages: 950-967

DOI: 10.1145/31846.31849

Algorithms are given that compute maximum flows in planar directed networks either in O((log n)3) parallel time using O(n4) processors...

**A linear time algorithm for residue computation and a fast algorithm for division with a sparse divisor**

Michael Kaminski

Pages: 968-984

DOI: 10.1145/31846.31850

An algorithm is presented to compute the residue of a polynomial over a finite field of degree n modulo a polynomial of degree O(log n) in O(n) algebraic...

**Asymptotic expansions of the sojourn time distribution functions of jobs in closed, product-form queuing networks**

James McKenna

Pages: 985-1003

DOI: 10.1145/31846.31851

Striking progress has been made recently in obtaining expressions for the sojourn time distribution function (STDF) of a job at a c-server, first-come, first-serve (FCFS) center in a closed, product-form queuing network. These...

**Monotone versus positive**

Miklos Ajtai, Yuri Gurevich

Pages: 1004-1015

DOI: 10.1145/31846.31852

In connection with the least fixed point operator the following question was raised: Suppose that a first-order formula P(P) is (semantically) monotone in a predicate symbol P on finite...

**Correction to “An equivalence between relational database dependencies and a fragment of propositional logic”**

Y. Sagiv, C. Delobel, D. S. Parker, Jr., Ronald Fagin

Pages: 1016-1018

DOI: 10.1145/31846.31853

According to the definition of satisfaction of Boolean dependencies, Theorem 15 is not true for Boolean dependencies with negation. (A positive Boolean dependency is built using the Boolean connectives ⋏, ⋎, and...