Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 42 Issue 3, May 1995

On the minimality and global consistency of row-convex constraint networks
Peter van Beek, Rina Dechter
Pages: 543-561
DOI: 10.1145/210346.210347
Constraint networks have been shown to be useful in formulating such diverse problems as scene labeling, natural language parsing, and temporal reasoning. Given a constraint network, we often wish to (i) find a solution that satisfies the...

Expected deadlock time in a multiprocessing system
Kevin J. Compton, Chinya Ravishankar
Pages: 562-583
DOI: 10.1145/210346.210412
We consider multiprocessing systems where processes make independent, Poisson distributed resource requests with mean arrival time 1. We assume that resources are not released. It is shown that the expected deadlock time is never less than 1, no...

On the existence of equilibria in noncooperative optimal flow control
Yannis A. Korilis, Aurel A. Lazar
Pages: 584-613
DOI: 10.1145/210346.210415
The existence of Nash equilibria in noncooperative flow control in a general product-form network shared by K users is investigated. The performance objective of each user is to maximize its average throughput subject to an...

Deterministic on-line routing on area-universal networks
Paul Bay, Gianfranco Bilardi
Pages: 614-640
DOI: 10.1145/210346.210417
Two deterministic routing networks are presented: the pruned butterfly and the sorting fat-tree. Both networks are area-universal, that is, they can simulate any other routing network fitting in similar area...

An optimal service policy for buffer systems
Alexander Birman, H. Richard Gail, Sidney L. Hantler, Zvi Rosberg, Moshe Sidi
Pages: 641-657
DOI: 10.1145/210346.210422
Consider a switching component in a packet-switching network, where messages from several incoming channels arrive and are routed to appropriate outgoing ports according to a service policy. One requirement in the design of such a system is to...

Parametricity and local variables
P. W. O'Hearn, R. D. Tennent
Pages: 658-709
DOI: 10.1145/210346.210425
We propose that the phenomenon of local state may be understood in terms of Strachey's concept of parametric (i.e., uniform) polymorphism. The intuitive basis for our proposal is the following analogy: a non-local procedure is independent of...