Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 45 Issue 3, May 1998

Time to publication: a progress report
Joseph Y. Halpern
Pages: 379-380
DOI: 10.1145/278298.278301

Efficient descriptor-vector multiplications in stochastic automata networks
Paulo Fernandes, Brigitte Plateau, William J. Stewart
Pages: 381-414
DOI: 10.1145/278298.278303
This paper examines numerical issues in computing solutions to networks of stochastic automata. It is well-known that when the matrices that represent the automata contain only constant values, the cost of performing the operation basic to all...

Lower bounds for distributed coin-flipping and randomized consensus
James Aspnes
Pages: 415-450
DOI: 10.1145/278298.278304
We examine a class of collective coin-flipping games that arises from randomized distributed algorithms with halting failures. In these games, a sequence of local coin flips is generated, which must be combined...

Fault-tolerant wait-free shared objects
Prasad Jayanti, Tushar Deepak Chandra, Sam Toueg
Pages: 451-500
DOI: 10.1145/278298.278305
Wait-free implementations of shared objects tolerate the failure of processes, but not the failure of base objects from which they are implemented. We consider the problem of implementing shared objects that tolerate the failure of both...

Proof verification and the hardness of approximation problems
Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy
Pages: 501-555
DOI: 10.1145/278298.278306
We show that every language in NP has a probablistic verifier that checks membership proofs for it using logarithmic number of random bits and by examining a constant number of bits in the proof. If a string is in the language,...