Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 47 Issue 2, March 2000

Eavesdropping games: a graph-theoretic approach to privacy in distributed systems
Matthew Franklin, Zvi Galil, Moti Yung
Pages: 225-243
DOI: 10.1145/333979.333980
We initiate a graph-theoretic study of privacy in distributed environments with mobile eavesdroppers ("bugs"). For two privacy tasks—distributed database maintenance and message transmission—a computationally unbounded adversary...

The fault span of crash failures
George Varghese, Mahesh Jayaram
Pages: 244-293
DOI: 10.1145/333979.333982
A crashing network protocol is an asynchronous protocol whose memory does not survive crashes. We show that a crashing network protocol that works over unreliable links can be driven to arbitrary global states, where each node...

An O(log(n)4/3) space algorithm for (s, t) connectivity in undirected graphs
Roy Armoni, Amnon Ta-Shma, Avi Widgerson, Shiyu Zhou
Pages: 294-311
DOI: 10.1145/333979.333984
We present a deterministic algorithm that computes st-connectivity in undirected graphs using O(log 4/3n) space. This improves the previous...

An automata-theoretic approach to branching-time model checking
Orna Kupferman, Moshe Y. Vardi, Pierre Wolper
Pages: 312-360
DOI: 10.1145/333979.333987
Translating linear temporal logic formulas to automata has proven to be an effective approach for implementing linear-time model-checking, and for obtaining many extensions and improvements to this verification method. On the other hand, for...

Making abstract interpretations complete
Roberto Giacobazzi, Francesco Ranzato, Francesca Scozzari
Pages: 361-416
DOI: 10.1145/333979.333989
Completeness is an ideal, although uncommon, feature of abstract interpretations, formalizing the intuition that, relatively to the properties encoded by the underlying abstract domains, there is no loss of information accumulated in abstract...