ACM DL

Journal of the ACM (JACM)

Menu

Search Issue
enter search term and/or author name

Archive


Journal of the ACM (JACM), Volume 34 Issue 4, Oct. 1987

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