Brown University, Providence, RI, USA
Nancy A. Lynch, Mark R. Tuttle
sixth annual ACM Symposium on Principles of distributed computing, 1987 – PODC
We introduce the input-output automaton, a simple but powerful model of computation in asynchronous distributed networks. With this model we are able to construct modular, hierarchical correctness proofs for distributed algorithms. We define this ...
tenth annual ACM symposium on Principles of distributed computing, 1991 – PODC
Burrows, Abadi, and Needham have proposed a logic for the analysis of authentication protocols. It is a logic of belief, with special constructs for expressing some of the central concepts used in authentication. The logic has revealed many subt ...
David B. Lomet, Mark R. Tuttle
VLDB'95, Proceedings of 21th International Conference on Very Large Data Bases, 1995 – VLDB
: This paper defines a framework for explaining redo recovery after a system crash. In this framework, an installation graph explains the order in which operations must be installed into the stable database if it is to remain recoverable. This ...
Algorithmica, vol. 3,1988 – Algorithmica
This work applies the theory of knowledge in distributed systems to the design of efficient fault-tolerant protocols. We define a large class of problems requiring coordinated, simultaneous action in synchronous systems, and give a method of ...
Joseph Y. Halpern, Yoram Moses, Mark R. Tuttle
Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, 1988 – STOC
While the intuition underlying a zero knowledge proof system [GMR85] is that no “knowledge” is leaked by the prover to the verifier, researchers are just beginning to analyze such proof systems in terms of formal notions of knowledge. In this ...
Joseph Y. Halpern, Mark R. Tuttle
Journal of the ACM, vol. 40,no. 4,1993 – JACM
What should it mean for an agent to know or believe an assertion is true with probability 9.99? Different papers [2, 6, 15] give different answers, choosing to use quite different probability spaces when computing the probability that an agent ...
Maurice Herlihy, Sergio Rajsbaum, Mark R. Tuttle
Seventeenth Annual ACM Symposium on Principles of Distributed Computing, 1998 – PODC
We take a significant step toward unifying the synchronous, semi-synchronous, and asynchronous message-passing models of distributed computation. The key idea is the concept of a pseudosphere, a new combinatorial structure in which each process from ...
Soma Chaudhuri, Maurice Herlihy, Nancy A. Lynch, Mark R. Tuttle
Journal of the ACM, vol. 47,no. 5,2000 – JACM
We prove tight bounds on the time needed to solve k-set agreement. In this problem, each processor starts with an arbitrary input value taken from a fixed set, and halts after choosing an output value. In every execution, at most k distinct output ...
Noga Alon, Chen Avin, Michal Koucký, Gady Kozma, Zvi Lotker, Mark R. Tuttle
SPAA 2008: Proceedings of the 20th Annual ACM Symposium on Parallel Algorithms and Architectures, 2008 – SPAA
We pose a new and intriguing question motivated by distributed computing regarding random walks on graphs: How long does it take for several independent random walks, starting from the same vertex, to cover an entire graph? We study the cover time - ...