Home page
Running
Flying
Soaring
Family
Music

Mark R. Tuttle
Principal Engineer

Strategic CAD Lab
Intel Corporation
77 Reed Road
Hudson, MA 01749
(978) 553-3305
tuttle@acm.org

8 Melanie Lane
Arlington, MA 02474
(781) 648-1106
mrtuttle@alum.mit.edu

Experience:

Education:
PhD, Massachusetts Institute of Technology, 1989
MS, Massachusetts Institute of Technology, 1987
BS, University of Nebraska-Lincoln, 1984

Research Interests:
Distributed and parallel systems, fault-tolerance and reliability, specification and verification, algorithms, theory.

Refereed conferences and workshops:

  1. Ariel Cohen, John W. O'Leary, Amir Pnueli, Mark R. Tuttle, Lenore D. Zuck. Verifying Correctness of Transactional Memories. In Proceedings of the 7th International Conference on Formal Methods in Computer-Aided Design (FMCAD), November 2007.

  2. Zvi Lotker, Boaz Patt-Shamir, and Mark R. Tuttle. Publish and perish: Definition and analysis of an n-person publication impact game. In Proceedings of the 18th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pages 11-18, August 2006.

  3. Zvi Lotker, Boaz Patt-Shamir, and Mark Tuttle. Brief Announcement: Timing games and shared memory. In Proceedings of the 19th International Symposium on Distributed Computing (DISC), pages 507-508, September 2005. (ps, pdf, tex)

  4. Baruch Awerbuch, Yossi Azar, Zvi Lotker, Boaz Patt-Shamir, and Mark Tuttle. Collaborate with strangers to find own preferences. In Proceedings of the 17th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pages 263-269, July 2005. (ps, pdf)

  5. Baruch Awerbuch, Boaz Patt-Shamir, David Peleg, and Mark Tuttle. Adaptive collabortion in peer-to-peer systems. In Proceedings of the 25th IEEE International Conference on Distributed Computing Systems (ICDCS), pages 71-80, June 2005. (ps, pdf, tex)

  6. Baruch Awerbuch, Boaz Patt-Shamir, David Peleg, and Mark Tuttle. Improved recommendation systems. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1174-1183, January 2005. (ps, pdf, tex)

  7. Maurice Herlihy, Sergio Rajsbaum, and Mark Tuttle. An axiomatic approach to computing the connectivity of synchronous and asynchronous systems. In Proceedings of the Sixth Workshop on Geometric and Topological Methods in Concurrency and Distributed Computing (GETCO), Electronic Notes in Theoretical Computer Science. Elsevier, October 2004. (ps, pdf, tex, slides)

  8. Baruch Awerbuch, Boaz Patt-Shamir, David Peleg, and Mark Tuttle. Collaboration of untrusting peers with changing interests. In Proceedings of the 5th ACM Conference on Electronic Commerce (EC), pages 112-119, May 2004. (ps, pdf, tex)

  9. Sandip Ray, John Matthews, and Mark Tuttle. Certifying compositional model checking algorithms in ACL2. In Proceedings of the 4th International Workshop on the ACL2 Theorem Prover and Its Applications (ACL2), July 2003. (ps, pdf)

  10. David Lomet and Mark Tuttle. A theory of redo recovery. In Proceedings of the ACM SIGMOD International Conference on Management of Data, pages 397-406. ACM, June 2003. (ps, pdf, tex, slides)

  11. Leslie Lamport, John Matthews, Mark Tuttle, and Yuan Yu. Specifying and verifying systems with TLA+. In Proceedings of the Tenth ACM SIGOPS European Workshop: Can we really depend on an OS?, pages 45-48, September 2002. (ps, pdf)

  12. Maurice Herlihy, Sergio Rajsbaum, and Mark Tuttle. A new synchronous lower bound for set agreement. In Proceedings of the 15th International Conference on Distributed Computing (DISC), volume 2180 of Lecture Notes in Computer Science, pages 136-150. Springer-Verlag, October 2001. (ps, pdf, tex)

  13. Maurice Herlihy, Sergio Rajsbaum, and Mark Tuttle. An overview of synchronous message-passing and topology. In Proceedings of the Workshop on Geometry and Topology in Concurrency Theory (GETCO), volume NS-00-3 of Basic Research in Computer Science Notes Series. Department of Computer Science, University of Aarhus, August 2000. (ps, pdf, tex)

  14. Homayoon Akhiani, Damien Doligez, Paul Harter, Leslie Lamport, Joshua Scheid, Mark Tuttle, and Yuan Yu. Cache coherence verification with TLA+. In Proceedings of the World Congress On Formal Methods In The Development Of Computing Systems, FM'99, Industrial Panel, volume 1709 of Lecture Notes in Computer Science, page 1871, September 1999. (ps, pdf, tex, slides)

  15. David B. Lomet and Mark R. Tuttle. Logical logging to extend recovery to new domains. In Alex Delis, Christos Faloutsos, and Shahram Ghandeharizadeh, editors, Proceedings of the ACM SIGMOD International Conference on Management of Data, pages 73-84. ACM, June 1999. (ps, pdf)

  16. Maurice Herlihy, Sergio Rajsbaum, and Mark R. Tuttle. Unifying synchronous and asynchronous message-passing models. In Proceedings of the 17th Annual ACM Symposium on Principles of Distributed Computing, pages 133-142. ACM, June 1998. (ps, pdf)

  17. David Lomet and Mark R. Tuttle. Redo recovery after system crashes. In Umesh Dayal, Peter Gray, and Shojiro Nishio, editors, Proceedings of the 21st International Conference on Very Large Data Bases, pages 457-468. Morgan Kaufmann, September 1995.  (ps, pdf)

  18. Soma Chaudhuri and Mark R. Tuttle. Fast increment registers. In Gerard Tel and Paul Vitanyi, editors, Proceedings of the 8th International Workshop on Distributed Algorithms, volume 857 of Lecture Notes in Computer Science, pages 74-88. Springer-Verlag, Berlin, October 1994. (ps, pdf)

  19. Soma Chaudhuri, Maurice Herlihy, Nancy Lynch, and Mark R. Tuttle. A tight lower bound for k-set agreement. In Proceedings of the 34th IEEE Symposium on Foundations of Computer Science, pages 206-215. IEEE, November 1993. (ps, pdf)

  20. Soma Chaudhuri, Maurice Herlihy, Nancy Lynch, and Mark R. Tuttle. A tight lower bound for processor coordination. In Proceedings of the 3rd International Workshop on Responsive Computer Systems, pages 4-15, September 1993. (ps, pdf)

  21. Martín Abadi and Mark R. Tuttle. A semantics for a logic of authentication. In Proceedings of the 10th Annual ACM Symposium on Principles of Distributed Computing, pages 201-216. ACM, August 1991. (ps, pdf)

  22. Michael Merritt, Francesmary Modugno, and Mark R. Tuttle. Time-constrained automata. In J. C. M. Baeten and J. F. Groote, editors, Proceedings of the Second International Conference on Concurrency Theory (Concur'91), volume 527 of Lecture Notes in Computer Science, pages 408-423. Springer-Verlag, Berlin, August 1991. (ps, pdf)

  23. Gil Neiger and Mark R. Tuttle. Common knowledge and consistent simultaneous coordination. In J. van Leeuwen and N. Santoro, editors, Proceedings of the 4th International Workshop on Distributed Algorithms, volume 486 of Lecture Notes in Computer Science, pages 334-352. Springer-Verlag, September 1990. (ps, pdf)

  24. Maurice P. Herlihy and Mark R. Tuttle. Wait-free computation in message-passing systems. In Proceedings of the 9th Annual ACM Symposium on Principles of Distributed Computing, pages 347-362. ACM, August 1990.
    25. (ps, pdf)

  25. Joseph Y. Halpern and Mark R. Tuttle. Knowledge, probability, and adversaries. In Proceedings of the 8th Annual ACM Symposium on Principles of Distributed Computing, pages 103-118. ACM, August 1989. (ps, pdf)

  26. Joseph Y. Halpern, Yoram Moses, and Mark R. Tuttle. A knowledge-based analysis of zero knowledge. In Proceedings of the 20th ACM Symposium on Theory of Computing, pages 132-147. ACM, May 1988. (ps, pdf)

  27. Nancy A. Lynch and Mark R. Tuttle. Hierarchical correctness proofs for distributed algorithms. In Proceedings of the 6th Annual ACM Symposium on Principles of Distributed Computing, pages 137-151. ACM, August 1987. (ps, pdf)

  28. Yoram Moses and Mark R. Tuttle. Programming simultaneous actions using common knowledge. In Proceedings of the 27th IEEE Symposium on Foundations of Computer Science, pages 208-221. IEEE, October 1986. (ps, pdf)

Refereed journals:

  1. Zvi Lotker, Boaz Patt-Shamir and Mark R. Tuttle. A game of timing and visibility. Games and Economic Behavior, to appear, 2007.

  2. Baruch Awerbuch, Yossi Azar, Zvi Lotker, Boaz Patt-Shamir, and Mark Tuttle. Collaborate with strangers to find own preferences. Theory of Computing Systems, 42(1):27-41, January 2008, DOI 10.1007/s00224-007-9016-7.

  3. Rajeev Joshi, Leslie Lamport, John Matthews, Serdar Tasiran, Mark Tuttle, and Yuan Yu. Checking cache-coherence protocols with TLA+. Formal Methods in System Design: Special Issue on Industrial Applications, 22(2):125-131, March 2003.
    4. (ps, pdf, tex)

  4. Maurice Herlihy, Sergio Rajsbaum, and Mark Tuttle. An overview of synchronous message-passing and topology. Electronic Notes in Theoretical Computer Science, 39(2), 2001.

  5. Soma Chaudhuri, Maurice Herlihy, Nancy Lynch, and Mark R. Tuttle. Tight bounds for k-set agreement. Journal of the ACM, September 2000. (ps, pdf)

  6. Soma Chaudhuri, Maurice Herlihy, and Mark R. Tuttle. Wait-free implementations in message-passing systems. Theoretical Computer Science, 220(1):211-245, June 1999. (ps, pdf)

  7. Joseph Y. Halpern and Mark R. Tuttle. Knowledge, probability, and adversaries. Journal of the ACM, 40(4):917-962, September 1993. (ps, pdf)

  8. Gil Neiger and Mark R. Tuttle. Common knowledge and consistent simultaneous coordination. Distributed Computing, 6(3):181-192, 1993. (ps, pdf)

  9. Nancy A. Lynch and Mark R. Tuttle. An introduction to input/output automata. CWI-Quarterly, 2(3):219-246, September 1989. Also available as MIT Technical Memo MIT/LCS/TM-373. (ps, pdf)

  10. Yoram Moses and Mark R. Tuttle. Programming simultaneous actions using common knowledge. Algorithmica, 3(1):121-169, 1988. (ps, pdf)

Book chapters:

  1. David Lomet and Mark R. Tuttle. Redo recovery after system crashes. In Vijay Kumar and Meichun Hsu, editors, Recovery Mechanisms in Database Systems, pages 101-124. Prentice Hall, Upper Saddle River, New Jersey, 1999.

Reports:

  1. Soma Chaudhuri, Maurice Herlihy, Nancy Lynch, and Mark R. Tuttle. Tight bounds for k-set agreement. Technical Report 98/4, DEC Cambridge Research Lab, May 1998. (ps, pdf)

  2. Soma Chaudhuri, Maurice Herlihy, and Mark R. Tuttle. Wait-free implementations in message-passing systems. Technical Report 98/5, DEC Cambridge Research Lab, May 1998. (ps, pdf)

Theses:

  1. Mark R. Tuttle. Hierarchical correctness proofs for distributed algorithms. Master's thesis, Massachusetts Institute of Technology, Laboratory for Computer Science, April 1987. Available as MIT Technical Report MIT/LCS/TR-387. (gzip ps, ps, pdf)

  2. Mark R. Tuttle. Knowledge and Distributed Computation. PhD thesis, Massachusetts Institute of Technology, Laboratory for Computer Science, May 1990. Available as MIT Technical Report MIT/LCS/TR-477. (gzip ps, ps, pdf)

Other:

  1. Leslie Lamport, Mark Tuttle, and Yuan Yu. The wildfire verification challenge problem. July 2000.

  2. Homayoon Akhiani, Damien Doligez, Paul Harter, Leslie Lamport, Joshua Scheid, Mark Tuttle, and Yuan Yu. TLA+ verification of cache coherence protocols. February 1999. (ps, pdf, tex)

  3. Hagit Attiya and Mark R. Tuttle. Bounds for slotted l-exclusion. Technical memo, MIT, February 1989.

  4. Mark R. Tuttle. A game-theoretic characterization of eventual common knowledge. Technical memo, MIT, October 1988

Patents:

  1. Baruch Awerbuch, Boaz Patt-Shamir, David Peleg, Mark Tuttle. Improved recommendation systems. Application pending, December 2004.

  2. Eytan Adar, Boaz Patt-Shamir, Mark Tuttle. Collaborative web searches. Application pending, December 2004.

  3. David B. Lomet and Mark R. Tuttle. Database Computer System Using Logical Logging to Extend Recovery. Application pending, April 1999.

Invited Talks:

  1. Analyzing Cache Coherence with TLA+. Workshop on Formal Specification and Verification Methods for Shared Memory Systems at International Conference on Formal Methods in Computer-Aided Design (FMCAD), October 2000.

  2. Using TLA+ at COMPAQ. TLA+ User Group Meeting at World Congress On Formal Methods In The Development Of Computing Systems (FM), September, 1999.

  3. Unifying synchronous and asynchronous message-passing models. Computer Science Colloquium series, Brown University, March 1999.

  4. Lower bounds for agreement. Mathematics and Statistics Colloquium series, University of Nebraska-Lincoln, May 1997.

  5. A tight lower bound for k-set agreement. Computer Science Colloquium series, Dartmouth University, January 1995.

  6. Build models, not logics. Panel, Computer Security Foundations Workshop, June 1993.

  7. How fast are wait-free concurrent objects? POCS Seminar Series, MIT Laboratory for Computer Science, April 1993.

Awards:

  1. Certificate of Recognition, Digital Equipment Corporation, Wildfire Verification Project, April 1998

  2. Young Alumni Achievement Award, University of Nebraska-Lincoln, May 1997

  3. National champion, ACM National Scholastic Programming Competition, University of Nebraska-Lincoln team, 1983
  Last modified February 02, 2008.