Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 27 Issue 2, April 1980

New Algorithms for Bin Packing
Andrew Chi-Chih Yao
Pages: 207-227
DOI: 10.1145/322186.322187
In the bin-packing problem a list L of n numbers are to be packed into unit-capacity bins. For any algorithm S, let r(S) be the maximum ratio...

Reaching Agreement in the Presence of Faults
M. Pease, R. Shostak, L. Lamport
Pages: 228-234
DOI: 10.1145/322186.322188
The problem addressed here concerns a set of isolated processors, some unknown subset of which may be faulty, that communicate only by means of two-party messages. Each nonfaulty processor has a private value of information that must be...

Equality and Domain Closure in First-Order Databases
Raymond Reiter
Pages: 235-249
DOI: 10.1145/322186.322189
A class of first-order databases with no function signs is considered. A closed database DB is one for which the only existing individuals are those explicitly referred to in the formulas of DB. Formally, this is expressed by including in DB a...

An Algorithm for Inferring Multivalued Dependencies with an Application to Propositional Logic
Yehoshua Sagiv
Pages: 250-262
DOI: 10.1145/322186.322190
An algorithm is given for deciding whether a functional or a multivalued dependency &sgr; (with a right-hand side Y) is implied by a set of functional and multivalued dependencies &Sgr;. The running time of the...

Can Any Stationary Iteration Using Linear Information Be Globally Convergent?
G. W. Wasilkowski
Pages: 263-269
DOI: 10.1145/322186.322191
All known globally convergent iterations for the solution of a nonlinear operator equation ƒ(x) = 0 are either nonstationary or use nonlinear information. It is asked whether there exists a globally convergent stationary...

Testing Deadlock-Freedom of Computer Systems
Tiko Kameda
Pages: 270-280
DOI: 10.1145/322186.322192
The problem of determining whether it is possible for a set of “free-running” processes to become deadlocked is considered. It is assumed that any request by a process is immediately granted as long as there are enough free resource...

The Cycle Time Distribution of Exponential Cyclic Queues
We-Min Chow
Pages: 281-286
DOI: 10.1145/322186.322193
The cycle time distribution of a cyclic queue with two exponential servers is derived. Results show that when the population size N is large enough, the cycle time distribution is not sensitive to the ratio of service rates and...

A New Algorithm for Preemptive Scheduling of Trees
Teofilo F. Gonzalez, Donald B. Johnson
Pages: 287-312
DOI: 10.1145/322186.322194
An algorithm which schedules forests of n tasks on m identical processors in O(n log m) time, offline, is given. The schedules are optimal with respect to...

Mean-Value Analysis of Closed Multichain Queuing Networks
M. Reiser, S. S. Lavenberg
Pages: 313-322
DOI: 10.1145/322186.322195
It is shown that mean queue sizes, mean waiting times, and throughputs in closed multiple-chain queuing networks which have product-form solution can be computed recursively without computing product terms and normalization constants. The...

Queuing Network Models with State-Dependent Routing
Don Towsley
Pages: 323-337
DOI: 10.1145/322186.322196
A model of a closed queuing network within which customer routing between queues may depend on the state of the network is presented. The routing functions allowed may be rational functions of the queue lengths of various downstream queues which...

On the Correctness of Semantic-Syntax-Directed Translations
Ramachandran Krishnaswamy, Arthur B. Pyster
Pages: 338-355
DOI: 10.1145/322186.322197
The correctness of semantic-syntax-directed translators (SSDTs) is examined. SSDTs are a generalization of syntax-directed translators in which semantic information is employed to partially direct the translator. Sufficient conditions for an...

Fast Decision Procedures Based on Congruence Closure
Greg Nelson, Derek C. Oppen
Pages: 356-364
DOI: 10.1145/322186.322198
The notion of the congruence closure of a relation on a graph is defined and several algorithms for computing it are surveyed. A simple proof is given that the congruence closure algorithm provides a decision procedure for the...

A Syntactic Theory of Message Passing
Stephen A. Ward, Robert H. Halstead, Jr.
Pages: 365-383
DOI: 10.1145/322186.322199
Recent developments by Hewitt and others have stimulated interest in message-passing constructs as an alternative to the more conventional applicative semantics on which most current languages are based. The present work illuminates the...

Lower Bounds on Information Transfer in Distributed Computations
Harold Abelson
Pages: 384-392
DOI: 10.1145/322186.322200
Lower bounds on the interprocessor communication required for computing a differentiable real-valued function in a distributed network are derived. These bounds are independent of the network interconnection configuration, and they impose no...

GO Is Polynomial-Space Hard
David Lichtenstein, Michael Sipser
Pages: 393-401
DOI: 10.1145/322186.322201
It is shown that, given an arbitrary GO position on an n × n board, the problem of determining the winner is Pspace hard. New techniques are exploited to overcome the difficulties arising from the planar...

Corrigendum: `` Control System Model for Critically Timed Success''
Rainer Parchmann
Page: 402
DOI: 10.1145/322186.322202