TDS Publications

Please note: Papers can also be found by browsing the TDS group pages

2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996 1995 1994 1993 1992 1991 1990

1989 1988 1987 1986 1985 1984 1983 1982 1981 1980

Complete list of papers authored by Nancy Lynch from 1971-present.

Submitted for Publication

Reuven Bar-Yehuda, Keren Censor-Hillel, Mohsen Ghaffari, and Gregory Schwartzman. Distributed Approximation of Maximum Independent Set and Maximum Matching. Submitted for publication, 2016.

Keren Censor-Hillel, Erez Kantor, Nancy Lynch and Merav Parter. Computing in Additive Networks with Bounded-Information Codes. Submitted for journal publication, 2016.

Benjamin Dissler, Stephan Holzer and Roger Wattenhofer. Distributed Local Multi-Aggregation and Centrality Approximation. Submitted for publication, 2015.

Mohsen Ghaffari, Hsin-Hao Su, and Fabian Kuhn. Generalizing the Congested Clique. Submitted for publication, 2016.

Magnus Halldorsson, Stephan Holzer, Pradipta Mitra and Roger Wattenhofer. The Power of Oblivious Wireless Power. Submitted for journal publication, 2015.

Mohsen Ghaffari, Fabian Kuhn, and Hsin-Hao Su. Generalizing the Congested Clique. Submitted for publication, 2016.

Stephan Holzer, Thomas Locher, Yvonne Anne Pignolet and Roger Wattenhofer. Deterministic Multi-Channel Information Exchange. Submitted for journal publication, 2014.

Stephan Holzer and Nancy Lynch. Brief Announcement - Beeping a Maximal Independent Set Fast. Submitted for publication, 2016.

Stephan Holzer and Evangelia Anna Markatou. Brief Announcement - Leader Election in the SINR Model with Stopping Failures. Submitted for publication, 2016.

Kishori Konwar, Nancy Lynch, Muriel Medard and Prakash Narayana Moorthy. RADON: Repairable Atomic Data Object in Networks. Submitted for publication, 2016. arXiv:1605.05717.

Christoph Lenzen, Nancy Lynch, Calvin Newport, and Tsvetomira Radeva. Searching without Communicating: Tradeoffs Between Performance and Selection Complexity. Submitted for publication, 2016.

Christoph Lenzen, Boaz Patt-Shamir, and David Peleg. Distributed Distance Computation and Routing with Small Messages. Submited for publication, 2015.

Cameron Musco and Christopher Musco. Provably Useful Kernel Matrix Approximation in Linear Time. Submitted for publication, 2016. See https://arxiv.org/pdf/1605.07583.pdf

To appear

Viveck R. Cadambe, Nancy Lynch, Muriel Medard and Peter Musial. A Coded Shared Atomic Memory Algorithm for Message Passing Architectures. To appear in Distributed Computing.

Michael Cohen, Cameron Musco, and Christopher Musco. Input Sparsity Time Low-Rank Approximation via Ridge Leverage Score Sampling. To appear in Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, Barcelona, Spain (SODA'17). See https://arxiv.org/abs/1511.07263.

Mohsen Ghaffari. Improved Distributed Algorithms for Fundamental Graph Problems. Ph.D. Thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA, February 2017. .pdf

Mohsen Ghaffari and Hsin-Hao Su. Distributed Degree Splitting, Edge Coloring, and Orientations. To appear in ACM-SIAM Symposium on Discrete Algorithms (SODA 2017) Barcelona, Spain, January 2017.

Mohsen Ghaffari, David Karger, and Debmalya Panigrahi. Random Contractions and Sampling for Hypergraph and Hedge Connectivity. To appear in ACM-SIAM Symposium on Discrete Algorithms (SODA 2017) Barcelona, Spain, January 2017.

Nancy Lynch, Cameron Musco, and Merav Parter. Computational Tradeoffs in Biological Neural Networks: Self-Stabilizing Winner-Take-All Networks. To appear in Innovations in Theoretical Computer Science (ITCS'17), Berkeley, CA, January 2017. See arXiv 1610.02084.

2016

James Aspnes, Hagit Attiya, Keren Censor-Hillel, and Danny Hendler. Lower Bounds for Restricted-Use Objects. SIAM Journal on Computing, 45(3):734-762, 2016. Earlier version in Proceedings of the 24th Symposium on Parallelism in Algorithms and Architectures (SPAA), Pittsburgh, PA, pages 172-181, June 2012. .pdf ACM Copyright

Paul C. Attie and Nancy A. Lynch. Dynamic Input/Output Automata: a Formal and Compositional Model for Dynamic Systems. Information and Computation, volume 249, pages 28-75, August 2016. Accepted.pdf ElsevierAcceptedManuscript.pdf. Also, Arxiv 1604.06030. Earlier version in Technical Report MIT-CSAIL-TR-2013-015, Computer Science and Artificial Intelligence Laboratory, Cambridge, MA 02139, July 2013. .pdf

Viveck R. Cadambe, Zhiying Wang, and Nancy Lynch. Information-Theoretic Lower Bounds on the Storage Cost of Shared Memory Emulation. Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), Chicago, Illinois, pages 305-313, July 2016.

Michael B. Cohen, Cameron Musco, and Jakub Pachocki. Online Row Sampling. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) 2016, Paris, France, September 2016. See http://arxiv.org/abs/1604.05448

Benjamin Dissler, Stephan Holzer and Roger Wattenhofer. Distributed Local Multi-Aggregation and Centrality Approximation. Preprint arXiv:1605.06882. .pdf

Benjamin Dissler, Stephan Holzer and Roger Wattenhofer. Poster: Fast Computation of Shortest Paths and Central Nodes in Large Scale Graphs. Annual MIT CSAIL Alliance Program Meeting, May 2016.

Roy Frostig, Cameron Musco, Christopher Musco, and Aaron Sidford. Principal Component Projection Without Principal Component Analysis. International Conference on Machine Learning (ICML 2016), New York, NY, June 2016. See http://arxiv.org/abs/1602.06872.

Mohsen Ghaffari and Calvin Newport. How to Discreetly Spread a Rumor in a Crowd. 30th International Symposium on Distributed Computing (DISC 2016), Paris, France, September 2016.

Mohsen Ghaffari. An Improved Distributed Algorithm for Maximal Independent Set. ACM-SIAM Symposium on Discrete Algorithms (SODA 2016), Arlington, VA, pages 270-277, January 2016. Best Paper Award and Best Student Paper Award. .pdf. Preprint arXiv:1506.05093v2, 2015. .pdf

Mohsen Ghaffari and Bernhard Haeupler. Distributed Algorithms for Planar Networks I: Planar Embedding. Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), Chicago, Illinois, pages 29-38, July 2016. .pdf

Mohsen Ghaffari and Bernhard Haeupler. Distributed Algorithms for Planar Networks II: Low-Congestion Shortcuts, MST, and Min-Cut. ACM-SIAM Symposium on Discrete Algorithms (SODA 2016), Arlington, VA, pages 202-219, January 2016. .pdf

Mohsen Ghaffari and Calvin Newport. Leader Election in Unreliable Radio Networks. International Colloquium on Automata, Languages, and Programming (ICALP), Rome Italy, July 2016. .pdf

Mohsen Ghaffari and Merav Parter. A Polylogarithmic Gossip Algorithm for Plurality Consensus. Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), Chicago, Illinois, pages 117-126, July 2016. .pdf

Mohsen Ghaffari and Merav Parter. MST in Log-Star Rounds of Congested Clique. Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), Chicago, Illinois, pages 19-28, July 2016. .pdf

Mohsen Ghaffari and Merav Parter. Near-Optimal Distributed Algorithms for Fault-Tolerant Tree Structures. ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), Asilomar State Beach, California, pages 387-396, July 2016. .pdf

David G. Harris, Johannes Schneider, and Hsin-Hao Su. Distributed (A+1)-coloring in Sublogarithmic Rounds. Proceedings of the 48th Annual Symposium on the Theory of Computing (STOC 2016), Cambridge, MA, pages 465-478, June 2016. .pdf Also, http://arxiv.org/pdf/1603.01486v1.pdf

Elad Hazan, Daniel Garber, Chi Jin, Sham M. Kakade, Cameron Musco, Praneeth Netrapalli, and Aaron Sidford. Robust Shift-and-Invert Preconditioning: Faster and More Sample Efficient Algorithms for Eigenvector Computation. International Conference on Machine Learning (ICML 2016), New York, NY, June 2016. .pdf

Erez Kantor, Zvi Lotker, Merav Parter, and David Peleg. Fault Tolerant Logical Network Structures. Bulletin of the EATCS, 118, 2016.

Erez Kantor and David Peleg. Efficient $k$-shot Broadcasting in Radio Networks. Journal of Discrete Applied Mathematics, 202:79-94, 2016.

Kishori M Konwar, N. Prakash, Erez Kantor, Muriel Medard, Nancy Lynch, and Alexander A. Schwarzmann. Storage-Optimized Data-Atomic Algorithms for Handling Erasures and Errors in Distributed Storage Systems. 30th IEEE International Parallel & Distributed Processing Symposium (IPDPS), pages 720-729, May 2016. See arXiv:1605.01748.

Christoph Lenzen and Roger Wattenhofer. Tight Bounds for Parallel Randomized Load Balancing. Distributed Computing, 29(2):127-142, 2016. .pdf

Cameron Musco, Hsin-Hao Su, and Nancy Lynch. Ant-Inspired Density Estimation via Random Walks. Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), Chicago, Illinois, pages 469-478, July 2016. See http://arxiv.org/abs/1603.02981

Cameron Musco, Hsin-Hao Su, and Nancy Lynch. Ant-Inspired Density Estimation via Random Walks (Extended Abstract). 4th Workshop on Biological Distributed Algorithms, Chicago, IL, July 2016. .pdf

2015

James Aspnes, Hagit Attiya, Keren Censor-Hillel, and Faith Ellen. Limited-use atomic snapshots with polylogarithmic step complexity. Journal of the ACM, 62(1), February 2015. .pdf

Pierre Bertrand and Christoph Lenzen. The 1-2-3-Toolkit for Building Your Own Balls-into-Bins Algorithm. Meeting on Algorithm Engineering and Experiments (ALENEX), San Diego, CA, pages 44-54, January 2015. .pdf

Keren Censor-Hillel, Erez Kantor, Nancy Lynch and Merav Parter. Computing in Additive Networks with Bounded-Information Codes. In Yoram Moses, editor, Distributed Computing: 29th International Symposium (DISC 2015), Tokyo Japan, October 2015, volume 9363 of Lecture Notes in Computer Science, pages 405-519, 2015. Springer.

Keren Censor-Hillel, Bernhard Haeupler, Nancy Lynch, and Muriel Medard. Bounded-Contention Coding for the Additive Network Model. Distributed Computing, 28(5):297-308, 2015. Earlier version appeared as title "Bounded-Contention Coding for Wireless Networks in the in High SNR Regime" in Marcos K. Aguilera, editor, Distributed Computing: Proceedings of the 26th International Symposium (DISC 2012), Salvador, Brazil, October 2012, volume 7611 of Lecture Notes in Computer Science, pages 91-105, 2012. Springer. .pdf ArXiv submission, available at http://arxiv.org/abs/1208.6125, and MIT Technical Report MIT-CSAIL-TR-2012-026, Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA 02139, August 2012. .pdf

Keren Censor-Hillel, Mohsen Ghaffari, George Giakkoupis, Bernhard Haeupler, and Fabian Kuhn. Tight Bounds on Vertex Connectivity under Vertex Sampling. ACM-SIAM Symposium on Discrete Algorithms (SODA), San Diego, CA, pages 2006-2018, January 2015. .pdf

Michael B. Cohen, Sam Elder, Cameron Musco, Christopher Musco, and Madalina Persu. Dimensionality Reduction for k-Means Clustering and Low Rank Approximation. Proceedings of the 47th Annual Symposium on the Theory of Computing (STOC 2015), Portland, OR, June 2015. .pdf

Michael B. Cohen, Yin Tat Lee, Cameron Musco, Christopher Musco, Richard Peng, and Aaron Sidford. Uniform Sampling For Matrix Approximation. 6th Innovations in Theoretical Computer Science (ITCS), Rehovot, Israel, pages 181-190, January 2015. Link to paper.

Mohsen Ghaffari, Cameron Musco, Tsvetomira Radeva, Nancy Lynch. Distributed House-Hunting in Ant Colonies. ACM Symposium on Principles of Distributed Computing (PODC 2015), Donostia-San Sebastian, Spain, pages 57-66, July 2015. .pdf Also, arXIV:1505.03799.

Mohsen Ghaffari. Near-Optimal Scheduling of Distributed Algorithms. ACM Symposium on Principles of Distributed Computing (PODC 2015), Donostia-San Sebastian, Spain, pages 3-12, July 2015. Best Student Paper Award at PODC'15. .pdf

Mohsen Ghaffari, Andreas Karrenbauer, Fabian Kuhn, and Christoph Lenzen. Near-Optimal Distributed Maximum Flow. ACM Symposium on Principles of Distributed Computing (PODC 2015), Donostia-San Sebastian, Spain, pages 81-90, July 2015. .pdf

Mohsen Ghaffari and Rajan Udwani. Brief Announcement: Distributed Single-Source Reachability. ACM Symposium on Principles of Distributed Computing (PODC 2015), Donostia-San Sebastian, Spain, pages 163-165, July 2015. .pdf

Magnus Halldorsson, Stephan Holzer and Nancy Lynch. A Local Broadcast Layer for the SINR Network Model. ACM Symposium on Principles of Distributed Computing (PODC 2015), Donostia-San Sebastian, Spain, pages 129-138, July 2015. .pdf. ArXiV report available at http://www.arxiv.org/abs/1505.04514.

Stephan Holzer and Nathan Pinsker. Computing Distances and Shortest Paths in the Congested Clique. 19th International Conference on Principles of Distributed Systems (OPODIS), Rennes, France, December 2015. .pdf 1412.3445v2.pdf

Stephan Holzer and Nathan Pinsker. Poster:Computing Distances and Shortest Paths in the Congested Clique. Distributed Computing: 29th International Symposium (DISC 2015), Tokyo Japan, October 2015.

Erez Kantor, Zvi Lotker, Merav Parter and David Peleg. Nonuniform SINR+Voronoi Diagrams are Effectively Uniform. In Yoram Moses, editor, Distributed Computing: 29th International Symposium (DISC 2015), Tokyo Japan, October 2015, volume 9363 of Lecture Notes in Computer Science, pages 588-601, 2015. Springer.

Erez Kantor, Zvi Lotker, Merav Parter and David Peleg. The Topology of Wireless Communication. Journal of the ACM, 62(5):37, 2015.

Erez Kantor, Zvi Lotker, Merav Parter and David Peleg. The Minimum Principle of SINR: A Useful Discretization Tool for Wireless Communication. 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2015), Berkeley, CA, pages 330-349, October 2015.

Erez Kantor and Shay Kutten. Optimal competitiveness for the Rectilinear Steiner Arborescence problem. In Magnus M. Halldorsson, Kazuo Iwama, Naoki Kobayashi, and Bettina Speckmann, editors, Automata, Languages, and Programming - 42nd International Colloquium (ICALP 2015) Part II, Kyoto, Japan, July 2015 volume 9135 of Lecture Notes in Computer Science, pages 675-687, 2015. Springer. .pdf Also, ArXiv: 1504.08265.

Majid Khabbazian. Near-optimal multi-version codes. In Proceedings of the 53rd Annual Allerton Conference on Communication, Control and Computing, October 2015. .pdf

Christoph Lenzen, Philipp Sommer, and Roger Wattenhofer. PulseSync: An Efficient and Scalable Clock Synchronization Protocol. IEEE/ACM Transactions on Networking, 23(3):717-727, June 2015. .pdf

Nancy Lynch, Tsvetomira Radeva, and Hsin-Hao Su. Brief Announcement: A Distributed Task Allocation in Ant Colonies. 29th International Symposium on Distributed Computing (DISC 2015), Tokyo, Japan, October 2015.

Nancy Lynch and Calvin Newport. A (Truly) Local Broadcast Layer for Unreliable Radio Networks. ACM Symposium on Principles of Distributed Computing (PODC 2015), Donostia-San Sebastian, Spain, pages 109-118, July 2015. .pdf

Nancy Lynch and Calvin Newport. A (Truly) Local Broadcast Layer for Unreliable Radio Networks. Technical Report MIT-CSAIL-TR-016, Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA 02139, May 2015. .pdf

Nancy Lynch and Srikanth Sastry. Consensus using Asynchronous Failure Detectors. Technical Report MIT-CSAIL-TR-2015-006, Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA, 02139, March, 2015 .pdf and ArXiV report link http://arxiv.org/abs/1502.02538.

Cameron Musco and Christopher Musco. Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decomposition. 29th Annual Conference on Neural Information Processing Systems (NIPS), Montreal, Canada, December 2015. Link

Casey O'Brien. Solving ANTS with Loneliness Detection and Constant Memory. Masters of Engineering, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA 02139, September 2015. .pdf Simulation of the Algorithm

Zhiying Wang and Viveck R. Cadambe. Multi-Version Coding - An Information Theoretic Perspective of Consistent Distributed Storage. Report on arxiv.org, available online at http://arxiv.org/abs/1506.00684.

2014

Dan Alistarh, James Aspnes, Keren Censor-Hillel, Seth Gilbert, and Rachid Guerraoui. Tight bounds for asynchronous renaming. Journal of the ACM, 61(3):18.1-18.52, May 2014. .pdf

Noga Alon, Mohsen Ghaffari, Bernhard Haeupler, and Majid Khabbazian. Broadcast throughput in Radio Networks: Routing vs. Network Coding. Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2014), Portland, Oregon, pages 1831-1843, January 2014. .pdf

Pierre Bertrand and Christoph Lenzen. Brief Announcement: The 1-2-3-Toolkit for Building Your Own Balls-into-Bins Algorithm. In Fabian Kuhn, editor, Distributed Computing - 28th Symposium (DISC 2014), Austin, TX, October 2014,, volume 8784 of Lecture Notes in Computer Science, page 557, 2014. Springer. .pdf Also, CoRR abs/1407.8433, 2014.

Giuseppe Bianchi, Lorenzo Bracciale, Keren Censor-Hillel, Andrea Lincoln, and Muriel Medard. The one-out-of-k retrieval problem and Linear Network Coding. 4th International Castle Meeting on Coding Theory and Applications (ICMCTA 2014), Castle of Palmela, Portugal, September 2014. .pdf

Viveck R. Cadambe, Nancy Lynch, Muriel Medard, and Peter Musial. A Coded Shared Atomic Memory Algorithm for Message Passing Architectures. The 13th IEEE International Symposium on Network Computing and Applications (IEEE NCA14), Cambridge, MA, pages 253-260, August 2014. Best Paper Award. .pdf

Viveck R. Cadambe, Nancy Lynch, Muriel Medard, and Peter Musial. A Coded Shared Atomic Memory Algorithm for Message Passing Architectures. Technical Report MIT-CSAIL-TR-2014-015, Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA 02139, August 2014. .pdf Also available as arXiv:1407.4167, July 2014. .pdf

Keren Censor Hillel, Mohsen Ghaffari, and Fabian Kuhn. Distributed Connectivity Decomposition. Proceedings of the 33nd Annual ACM Symposium on Principles of Distributed Computing (PODC'14), Paris, France, pages 156-165, July 2014. Best Student Paper Award. .pdf

Keren Censor-Hillel, Seth Gilbert, Fabian Kuhn, Nancy Lynch and Calvin Newport. Structuring Unreliable Radio Networks. Distributed Computing, 27(1):1-19, February 2014. .pdf

Keren Censor-Hillel, Mohsen Ghaffari, Fabian Kuhn. A New Perspective on Vertex Connectivity. Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2014), Portland, Oregon, pages 546-561, January 2014. .pdf

Hyun Chul Chung, Srikanth Sastry, and Jennifer L. Welch. Stabilizing Dining with Failure Locality 1. In Mainak Chatterjee, Jian-Nong Cao, Kishore Kothapalli, Sergio Rajsbaum, editors, Distributed Computing and Networking - 15th International Conference (ICDCN 2014), Coimbatore, India, January 2014, volume 8314 of Lecture Notes in Computer Science, pages 532-537, 2014. Springer. .pdf

Alejandro Cornejo, Anna Dornhaus, Nancy Lynch, and Radhika Nagpal. Task Allocation in Ant Colonies. In Fabian Kuhn, editor, Distributed Computing: 28th International Symposium on Distributed Computing (DISC'14), Austin, TX, October 2014, volume 8784 of Lecture Notes in Computer Science, pages 46-60, 2014. Springer. .pdf

Danny Dolev, Matthias Fuegger, Christoph Lenzen, and Ulrich Schmid. Fault-tolerant Algorithms for Tick-Generation in Asynchronous Logic: Robust Pulse Generation. Journal of the ACM, 61(5):860-900, August 2014. .pdf

Danny Dolev, Matthias Fuegger, Christoph Lenzen, Markus Posch, Ulrich Schmid, and Andreas Steininger. Rigorously Modeling Self-Stabilizing Fault-Tolerant Circuits: An Ultra-Robust Clocking Scheme for Systems-on-Chip. Journal of Computer and System Sciences, 80(4):860-900, 2014. .pdf

Yuval Emek, Stephan Holzer, Roger Wattenhofer. The Power of a Leader in the Stone Age. 2nd Workshop on Biological Distributed Algorithms (BDA'14), Austin, TX, October 2014.

Mohsen Ghaffari and Bernhard Haeupler. Optimal Error Rates for Interactive Coding II: Efficiency and List Decoding. IEEE Symposium on Foundations of Computer Science (FOCS), Philadelphia, PA, October 2014. .pdf

Mohsen Ghaffari and Christoph Lenzen. Near-Optimal Distributed Tree Embedding. In Fabian Kuhn, editor, Distributed Computing - 28th International Symposium (DISC'14), Austin, TX, October 2014, volume 8784 of Lecture Notes in Computer Science, pages 197-211, 2014. Springer. .pdf

Mohsen Ghaffari and Bernhard Haeupler. Brief Announcement: Near-Optimal BFS Computation in Radio Networks. Proceedings of the 33nd Annual ACM Symposium on Principles of Distributed Computing (PODC'14), Paris, France, July 2014. .pdf

Mohsen Ghaffari and Bernhard Haeupler, and Madhu Sudan. Optimal Error Rates for Interactive Coding I: Adaptivity and Other Settings. Proceedings of the 46th Annual Symposium on the Theory of Computing (STOC 2014), New York, NY, pages 794-803, May 31-June 3, 2014. .pdf

Mohsen Ghaffari, Erez Kantor, Nancy Lynch, and Calvin Newport. Multi-Message Broadcast with Abstract MAC Layers and Unreliable Links. Proceedings of the 33nd Annual ACM Symposium on Principles of Distributed Computing (PODC'14), Paris, France, pages 56-65, July 2014. .pdf

Mohsen Ghaffari, Erez Kantor, Nancy A. Lynch and Calvin C. Newport. Multi-Message Broadcasting with Abstract MAC Layers and Unreliable Links. CoRR abs/1405.1671, 2014. .pdf

Mohsen Ghaffari. Near-Optimal Distributed Approximation of Minimum-Weight Connected Dominating Set. In Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, Elias Koutsoupias, editors, Automata, Languages, and Programming - 41st International Colloquium (ICALP'14), Copenhagen, Denmark, July 2014, volume 8573 of Lecture Notes in Computer Science, pages 483-494, 2014. Springer. Best Student Paper Award. .pdf

Miikka Hilke, Christoph Lenzen and Jukka Suomela. Brief Announcement: Local Approximability of Minimum Dominating Set on Planar Graphs. Proceedings of the 33nd Annual ACM Symposium on Principles of Distributed Computing (PODC'14), Paris, France, July 2014. .pdf

Alexandra Hochuli, Stephan Holzer and Roger Wattenhofer. Efficient Approximation of Minimum Routing Cost Trees. In Magnus M. Halldorsson, editor, Proceedings of the 21st International Colloquium on Structural Information and Communication Complexity (SIROCCO'14), Hida Takayama, Japan, July 2014, volume 8576 of Lecture Notes in Computer Science, pages 121-136, 2014. Springer. .pdf

Stephan Holzer. Distance Computation, Information Dissemination, and Wireless Capacity in Networks. In Roger Wattenhofer, editor, volume 19 in the Series in Distributed Computing, pages 1-247, 2014. Hartung-Gorre.

Stephan Holzer, Sebastian Kohler and Roger Wattenhofer. Brief Announcement: k-Selection and Sorting in the SINR Model. In Fabian Kuhn, editor, Distributed Computing - 28th International Symposium (DISC'14), Austin, TX, October 2014, volume 8784 of Lecture Notes in Computer Science, page 559, 2014. Springer. .pdf

Stephan Holzer and Nathan Pinsker. Approximation of Distances and Shortest Paths in the Broadcast Congest Clique. CoRR abs/1412.3445, December 2014. .pdf

Stephan Holzer, David Peleg, Liam Roditty and Roger Wattenhofer. Brief Announcement: Distributed 3/2-Approximation of the Diameter. In Fabian Kuhn, editor, Distributed Computing - 28th International Symposium (DISC'14), Austin, TX, October 2014, volume 8784 of Lecture Notes in Computer Science, page 562, 2014. Springer. .pdf

Erez Kantor and Shay Kutten. Optimal competitiveness for Symmetric Rectilinear Steiner Arborescence and related problems. In Javier Esparza and Pierre Fraigniaud and Thore Husfeldt and Elias Koutsoupias, editors, Automata, Languages, and Programming - 41st International Colloquium (ICALP'14), Copenhagen, Denmark, July 2014, volume 8573 of Lecture Notes in Computer Science, pages 520-531, 2014. Springer. .pdf

Michael Kapralov, Yin Tat Lee, Cameron Musco, Christopher Musco, and Aaron Sidford. Single Pass Spectral Sparsification in Dynamic Streams. Proceedings of the 55th Annual Symposium on Foundations of Computer Science (FOCS'14), Philadelphia, PA, October 2014. .pdf

Majid Khabbazian, Dariusz Kowalski, Fabian Kuhn, and Nancy Lynch. Decomposing Broadcast Algorithms Using Abstract MAC Layers. Ad Hoc Networks, volume 12, pages 219-242, 2014. Elsevier. .pdf

Christoph Lenzen and Boaz Patt-Shamir. Improved Distributed Steiner Forest Construction (Extended Abstract). Proceedings of the 33nd Annual ACM Symposium on Principles of Distributed Computing (PODC'14), Paris, France, pages 262-271, July 2014. .pdf

Christoph Lenzen, Nancy Lynch, Calvin Newport, and Tsvetomira Radeva. Trade-offs between Selection Complexity and Performance when Searching the Plane without Communication. Proceedings of the 33nd Annual ACM Symposium on Principles of Distributed Computing (PODC'14), Paris, France, pages 252-261, July 2014. .pdf

Zhiying Wang, Viveck Cadambe. On multi-version coding for distributed storage. In Proceedings of the 52nd Annual Allerton Conference on Communication, Control and Computing, Monticello, IL, pages 569-575, October, 2014. .pdf

Zhiying Wang and Viveck Cadambe. Multi-Version Coding in Distributed Storage. Proceedings of 2014 IEEE International Symposium on Information Theory (ISIT), Honolulu, USA, pages 871-875, June, 2014. .pdf Also, Preprint.

2013

Yehuda Afek, Noga Alon, Ziv Bar-Joseph, Alejandro Cornejo, Bernhard Haeupler, and Fabian Kuhn. Beeping a Maximal Independent Set. Distributed Computing, 26(4):195-208, 2013. Special issue for DISC 2011. .pdf

James Aspnes and Keren Censor-Hillel. Atomic snapshots in expected $O(\log^³n)$ steps using randomized helping. In Yehuda Afek, editor, 27th International Symposium on DIStributed Computing (DISC'13), Jerusalem Israel, October 2013, volume 8205 of Lecture Notes in Computer Science, pages 254-268, 2013. Springer. .pdf

Viveck R. Cadambe, Nancy Lynch, Muriel Medard, and Peter Musial. Coded Emulation of Shared Atomic Memory for Message Passage Architectures. Technical Report MIT-CSAIL-TR-2013-016, Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA 02139. Also, submitted for publication. .pdf

Ran Canetti, Ling Cheung, Dilsun Kaynar, Moses Liskov, Nancy Lynch, Olivier Pereira, and Roberto Segala. Task-Structured Probabilistic I/O Automata. Technical Report MIT-CSAIL-TR-2013-006, Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA, April 2013. This paper was completed in May 2009. .pdf

Israel Cidon, Erez Kantor and Shay Kutten. Prudent Opportunistic Cognitive Radio Access Protocols. In Yehuda Afek, editor, 27th International Symposium on DIStributed Computing (DISC'13), Jerusalem Israel, October 2013, volume 8205 of Lecture Notes in Computer Science, pages 462-476, 2013. Springer. .pdf

Alejandro Cornejo, Calvin Newport, Subha Gollakota, Jayanthi Rao, and T.J. Giuli. Prioritized Gossip in Vehicular Networks. Ad-Hoc Networks, 11(1):397-409, 2013. Elsevier. .pdf

Alejandro Cornejo, Nancy Lynch, and Srikanth Sastry. Asynchronous Failure Detectors. Technical Report, MIT-CSAIL-TR-2013-025, Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, October 2013. This report supersedes MIT-CSAIL-TR-2013-002 (below). .pdf

Alejandro Cornejo, Nancy Lynch, and Srikanth Sastry. Asynchronous Failure Detectors. Technical Report, MIT-CSAIL-TR-2013-002, Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, January 2013. .pdf. This report has been superseded by MIT-CSAIL-TR-2013-025 (above).

Sebastian Daum, Mohsen Ghaffari, Seth Gilbert, Fabian Kuhn and Calvin Newport. Maximal Independent Sets in Multichannel Radio Networks. Proceedings of the 32nd Annual ACM Symposium on Principles of Distributed Computing (PODC'13), Montreal Canada, pages 335-344, July 2013. .pdf

Danny Dolev, Janne H. Korhonen, Christoph Lenzen, Joel Rybicki, and Jukka Suomela. Synchronous Counting and Computational Algorithm Design. In Teruo Higashino and Yoshiaki Katayama and Toshimitsu Masuzawa and Maria Potop-Butucaru and Masafumi Yamashita, editor, 15th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2013), Osaka, Japan, November 2013, volume 8255 of Lecture Notes in Computer Science, pages 237-250, 2013. Springer. .pdf

Danny Dolev and Christoph Lenzen. Brief Announcement: Communication-Efficient Byzantine Consensus Without a Common Clock. In Yehuda Afek, editor, 27th International Symposium on DIStributed Computing (DISC'13), Jerusalem Israel, October 2013, volume 8205 of Lecture Notes in Computer Science, page 569, 2013. Springer. .pdf

Danny Dolev and Christoph Lenzen. Early-Deciding Consensus is Expensive. Proceedings of the 32nd Annual ACM Symposium on Principles of Distributed Computing (PODC'13), Montreal Canada, July 2013. .pdf

Danny Dolev, Matthias Fuegger, Christoph Lenzen, Martin Perner and Ulrich Schmid. HEX: Scaling Honeycombs is Easier than Scaling Clock Trees. Proceedings of the 25th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA'13), Montreal, Canada, July 2013. .pdf

Matthias Fuegger, Markus Hofstaetter, Christoph Lenzen, and Ulrich Schmid. Efficient Construction of Global Time in SoC's Despite Arbitrary Faults. Proceedings of the 16th Euromicro Conference on Digital System Design (DSD), Santander, Spain, September 2013. .pdf

Mohsen Ghaffari and Bernhard Haeupler. Optimal Error Rates for Interactive Coding II: Efficiency and List Decoding. Manuscript, 2013.

Mohsen Ghaffari and Fabian Kuhn. Distributed Minimum Cut Approximation. In Yehuda Afek, editor, 27th International Symposium on DIStributed Computing (DISC'13), Jerusalem, Israel, October 2013, volume 8205 of Lecture Notes in Computer Science, pages 1-15, 2013. Springer. Best Paper Award. .pdf

Mohsen Ghaffari, Nancy Lynch, and Calvin Newport. The Cost of Radio Network Broadcast for Different Models of Unreliable Links. Proceedings of the 32nd Annual ACM Symposium on Principles of Distributed Computing (PODC'13), Montreal Canada, pages 345-354, July 2013. .pdf

Mohsen Ghaffari, Bernhard Haeupler and Majid Khabbazian. Randomized Broadcast in Radio Networks with Collision Detection. Proceedings of the 32nd Annual ACM Symposium on Principles of Distributed Computing (PODC'13), Montreal Canada, pages 325-334, July 2013. .pdf

Mohsen Ghaffari and Bernhard Haeupler. Fast Structuring of Radio Networks for Multi-Message Communications. In Yehuda Afek, editor, 27th International Symposium on DIStributed Computing (DISC'13), Jerusalem Israel, October 2013, volume 8205 of Lecture Notes in Computer Science, pages 492-506, 2013. Springer. .pdf

Mohsen Ghaffari. Bounds on Contention Management in Radio Networks. Masters thesis, Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA, February 2013. .pdf

Mohsen Ghaffari and Bernhard Haeupler. Near Optimal Leader Election in Multi-Hop Radio Networks. Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA'13), New Orleans, Louisiana, pages 748-766, January, 2013. .pdf

Rebecca Ingram, Tsvetomira Radeva, Patrick Shields, Saira Viqar, Jennifer. E. Walter, and Jennifer L. Welch. A Leader Election Algorithm for Dynamic Networks with Causal Clocks. Distributed Computing, 26(2):75-97, 2013. .pdf

Christoph Lenzen. Optimal Deterministic Routing, and Sorting on the Congested Clique. Proceedings of the 32nd Annual ACM Symposium on Principles of Distributed Computing (PODC'13), Montreal Canada, July 2013. .pdf

Christoph Lenzen and David Peleg. Efficient Distributed Source Detection with Limited Bandwidth. Proceedings of the 32nd Annual ACM Symposium on Principles of Distributed Computing (PODC'13), Montreal Canada, July 2013. .pdf

Christoph Lenzen, Yvonne-Anne Pignolet, and Roger Wattenhofer. Distributed Minimum Dominating Set Approximations in Restricted Families of Graphs. Distributed Computing, 26(2):119-137, 2013. .pdf

Christoph Lenzen and Boaz Patt-Shamir. Fast Routing Table Construction Using Small Messages. Proceedings of the 45th Symposium on the Theory of Computing (STOC), Palo Alto, California, pages 381-390, June 2013. .pdf

Christoph Lenzen, Martin Perner, Ulrich Schmid, and Martin Sigl. Byzantine Self-Stabilizing Clock Distribution with HEX: Implementation, Simulation, Clock Multiplication. Sixth International Conference on Dependability (DEPEND 2013), Barcelona, Spain, August 2013. .pdf

Christoph Lenzen and Tsvetomira Radeva. The Power of Phermones in Ant Foraging. 1st Workshop on Biological Distributed Algorithms (BDA), Jerusalem, Israel, October 2013. .pdf

Rotem Oshman and Nir Shavit. The SkipTrie: Low-Depth Concurrent Search without Rebalancing. Proceedings of the 32nd Annual ACM Symposium on Principles of Distributed Computing (PODC'13), Montreal Canada, July 2013. .pdf

Tsvetomira Radeva. Properties of Link Reversal Algorithms for Routing and Leader Election. Masters thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA, June 2013. .pdf

Srikanth Sastry, Tsvetomira Radeva, Jianer Chen, and Jennifer L. Welch. Reliable Networks With Unreliable Sensors. Pervasive and Mobile Computing, 9(2):311-323, 2013. .pdf

2012

James Aspnes, Hagit Attiya, and Keren Censor-Hillel. Polylogarithmic Concurrent Data Structures from Monotone Circuits. Journal of the ACM, 59(1):2:1-2:24, February 2012. .pdf

James Aspnes, Hagit Attiya, Keren Censor-Hillel, and Danny Hendler. Lower Bounds for Restricted-Use Objects. Proceedings of the 24th Symposium on Parallelism in Algorithms and Architectures (SPAA), Pittsburgh, PA, pages 172-181, June 2012. .pdf ACM Copyright

James Aspnes, Hagit Attiya, Keren Censor-Hillel, and Faith Ellen. Faster than Optimal Snapshots (for a While). Proceedings of the 31st Annual ACM Symposiumon Distributed Computing, Madeira, Portugal, pages 375-384, July, 2012. .pdf ACM Copyright

Keren Censor-Hillel, Bernhard Haeupler, Nancy Lynch, and Muriel Medard. Bounded-Contention Coding for Wireless Networks in the High SNR Regime. In Marcos K. Aguilera, editor, Distributed Computing: Proceedings of the 26th International Symposium (DISC 2012), Salvador, Brazil, October 2012, volume 7611 of Lecture Notes in Computer Science, pages 91-105, 2012. Springer. .pdf

Keren Censor-Hillel, Bernhard Haeupler, Nancy Lynch, and Muriel Medard. Bounded-Contention Coding for Wireless Networks in the High SNR Regime. Technical Report MIT-CSAIL-TR-2012-026, Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA 02139, August 2012. .pdf ArXiv submission available at http://arxiv.org/abs/1208.6125.

Keren Censor-Hillel and Hadas Shachnai. Fast Information Spreading in Graphs with Large Weak Conductance. SIAM Journal on Computing, 41(6): 1451-1465, 2012. .pdf

Keren Censor-Hillel, Bernhard Haeupler, Jonathan A. Kelner, and Petar Maymounkov. Global Computation in a Poorly Connected World: Fast Rumor Spreading with No Dependence on Conductance. Proceedings of the 44th ACM Symposium on Theory of Computing (STOC 2012), New York, NY, pages 961-970, May 2012. .pdf ACM Copyright

Alejandro Cornejo. Local Distributed Algorithms for Multi-Robot Systems. Ph.D. thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, September 2012. .pdf

Alejandro Cornejo, Seth Gilbert and Calvin Newport. Aggregation in Dynamic Networks. Proceedings of the 31st Annual ACM Symposium on Distributed Computing, Madeira, Portugal, pages 195-204, July, 2012. .pdf ACM Copyright

Alejandro Cornejo, Andrew J. Lynch, Elizabeth Fudge, Siegfried Bilstein, Majid Khabbazian, and James McLurkin. Scale-Free Coordinates for Multi-Robot Systems with Bearing-only Sensors. Workshop on the Algorithmic Foundations of Robotics (WAFR), Cambridge, MA, June 2012. .pdf

Alejandro Cornejo, Nancy Lynch and Srikanth Sastry. Asynchronous Failure Detectors. Proceedings of the 31st Annual ACM Symposium on Distributed Computing, Madeira, Portugal, pages 243-252, July 2012. .pdf .ACM copyright

Andrew Drucker, Fabian Kuhn and Rotem Oshman. The Communication Complexity of Distributed Task Allocation. Proceedings of the 31st Annual ACM Symposium on Distributed Computing, Madeira, Portugal, pages 67-76, July 2012. .pdf .ACM copyright

Mohsen Ghaffari, Bernhard Haeupler, Nancy Lynch, Calvin Newport. Bounds on Contention Management in Radio Networks. In Marcos K. Aguilera, editor, Distributed Computing: 26th International Symposium (DISC 2012), Salvador, Brazil, October, 2012, volume 7611 of Lecture Notes in Computer Science, pages 223-237, 2012. Springer. .pdf

Mohsen Ghaffari, Seth Gilbert, Calvin Newport, Henry Tan. Optimal Broadcast in Shared Spectrum Radio Networks. In Roberto Baldoni, Paola Flocchini, and Binoy Ravindran, editors, Proceedings of the 16th International Conference On Principles Of DIstributed Systems (OPODIS'12), Rome, Italy, December 2012, volume 7702 of Lecture Notes in Computer Science,pages 181-195, 2012. Springer. .pdf

Mohsen Ghaffari, Nancy Lynch, and Srikanth Sastry. Leader Election Using Loneliness Detection. Distributed Computing, 25(6): 427-450, 2012. Special issue for DISC 2011. .pdf

Seth Gilbert and Nancy A. Lynch. Perspectives on the CAP Theorem. Computer, 45(2):30-35, 2012. IEEE. .pdf

Alexander W. Heinisch, Jean-Christophe Lapeyre, and Peter M. Musial. There is no 'I' in Consensus. Manuscript, 2012.

Majid Khabbazian, Ian Blake and Vijay Bhargava. Local Broadcast Algorithms in Wireless Ad Hoc Networks: Reducing the Number of Transmissions. IEEE Transactions on Mobile Computing, 11(3):402-413, March 2012. .pdf

Peter M. Musial. From Formal Methods to Executable Code. Technical Report MIT-CSAIL-TR-2012-027, Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA, September 2012. .pdf

Peter M. Musial. From Formal Methods to Executable Code. Languages for Distributed Algorithms (LADA) Workshop, January 2012. Invited paper. .pdf

Nancy Lynch, Tsvetomira Radeva, and Srikanth Sastry. Asynchronous Leader Election and MIS Using Abstract MAC Layer. Proceedings of FOMC 2012 (8th ACM International Workshop on the Foundations of Mobile Computing), Madeira, Portugal, page 3, July 2012. .pdf ACM Copyright

Rotem Oshman. Distributed Computation in Wireless and Dynamic Networks. Ph.D. thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA 02139, September 2012. .pdf

Scott M. Pike, Srikanth Sastry, and Jennifer L. Welch. Failure Detectors Encapsulate Fairness. Distributed Computing, 25(4):313-333, 2012. .pdf

Srikanth Sastry, Jennifer Welch, and Josef Widder. Wait-Free Stabilizing Dining Using Regular Registers. Proceedings of the 16th International Conference On Principles Of DIstributed Systems, Rome, Italy, December 2012. .pdf

2011

Yehuda Afek, Noga Alon, Ziv Bar-Joseph, Alejandro Cornejo, Bernhard Haeupler and Fabian Kuhn. Beeping a Maximal Independent Set. In David Peleg, editor, Distributed Computing: 25th International Symposium on DIStributed Computing (DISC), Rome, Italy, September 2011, volume 6950 of Lecture Notes in Computer Science, pages 32-50, 2011. Springer. .pdf

Dan Alistarh, James Aspnes, Keren Censor-Hillel, Seth Gilbert and Morteza Zadimoghaddam. Optimal-Time Adaptive Tight Renaming, with Applications to Counting. In Proceedings of the 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, San Jose, California, June 6-8, 2011. .pdf

Paul Attie, Rachid Guerraoui, Petr Kouznetsov, Nancy Lynch, and Sergio Rajsbuam. The Impossibility of Boosting Distributed Service Resilience. Information and Computation, 209(6):927-950, June 2011. .pdf

Chen Avin, Michael Borokhovich, Keren Censor-Hillel and Zvi Lotker. Order Optimal Information Spreading Using Algebraic Gossip. In Proceedings of the 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, San Jose, California, June 6-8, 2011. .pdf

Yossi Azar, Aviv Nisgav and Boaz Patt-Shamir. Recommender Systems With Non-Binary Grades. In Proceedings of the 23rd ACM Symposium on Parallel Algorithms and Architectures (SPAA), June 2011. .pdf

Zvika Brakerski and Boaz Patt-Shamir. Distributed Discovery of Large Near-Cliques. Distributed Computing, 24(2):79-89, 2011. .pdf

Keren Censor-Hillel, Seth Gilbert, Fabian Kuhn, Nancy Lynch and Calvin Newport. Structuring Unreliable Radio Networks. In Proceedings of the 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, San Jose, California, June 6-8, 2011. .pdf

Keren Censor-Hillel, Seth Gilbert, Fabian Kuhn, Nancy Lynch and Calvin Newport. Structuring Unreliable Radio Networks. Technical Report MIT-CSAIL-TR-2011-053, Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA, December, 2011. .pdf

Keren Censor-Hillel and Hadas Shachnai. Fast Information Spreading in Graphs with Large Weak Conductance. Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2011), San Francisco, CA, January, 2011. .pdf

Shlomi Dolev, Seth Gilbert, Majid Khabbazian and Calvin Newport. Leveraging channel diversity to gain efficiency and robustness for wireless broadcast. In David Peleg, editor, Distributed Computing: 25th International Symposium on DIStributed Computing (DISC), Rome, Italy, September 2011, volume 6950 of Lecture Notes in Computer Science, pages 252-267, 2011. Springer. .pdf

Mohsen Ghaffari, Nancy Lynch, and Srikanth Sastry. Leader Election Using Loneliness Detection. Technical Report MIT-CSAIL-TR-2011-045, Computer Science and Artificial and Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA, October 2011. .pdf

Mohsen Ghaffari, Nancy Lynch, and Srikanth Sastry. Leader Election Using Loneliness Detection. In David Peleg, editor, Distributed Computing: 25th International Symposium on DIStributed Computing (DISC 2011), Rome, Italy, September 2011, volume 6950 of Lecture Notes in Computer Science, pages 268-282, 2011. Springer. .pdf

Magnus M. Halldorsson, Boaz Patt-Shamir and Dror Rawitz. Online Scheduling with Interval Conflicts. 28th Int. Symp. on Theoretical Aspects of Computer Science (STACS), Tu Dortmund, Germany, March 2011. .pdf

Majid Khabbazian and Dariusz Kowalski. Time-efficient randomized multiple-message broadcast in radio networks. In Proceedings of the 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, San Jose, California, pages 373-380, June 6-8, 2011. .pdf

Majid Khabbazian, Fabian Kuhn, Nancy Lynch, Muriel Medard, and Ali ParandehGheibi. MAC Design for Analog Network Coding. In FOMC 2011: The Seventh ACM SIGACT/SIGMOBILE International Workshop on Foundations of Mobile Computing, San Jose, CA, pages 42-51, June 2011. .pdf

Majid Khabbazian, Dariusz Kowalski, Fabian Kuhn, and Nancy Lynch. Decomposing Broadcast Algorithms Using Abstract MAC Layers. Technical Report MIT-CSAIL-TR-2011-010, Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambrige, MA, February 2011. .pdf

Fabian Kuhn, Thomas Locher, and Rotem Oshman. Gradient Clock Synchronization in Dynamic Networks. Theory of Computing Systems, 49(4):781-816, July 2011. Special issue of SPAA'09. .pdf

Fabian Kuhn, Nancy Lynch, and Calvin Newport. The Abstract MAC Layer. Distributed Computing, 24(3):187-206, 2011. Special issue for DISC 2009: 23rd International Symposium on Distributed Computing. .pdf

Fabian Kuhn and Rotem Oshman. The Complexity of Data Aggregation in Directed Networks. In David Peleg, editor, Distributed Computing: 25th International Symposium on Distributed Computing (DISC 2011), Rome, Italy, September 2011, volume 6950 of Lecture Notes in Computer Science, pages 416-431, 2011. Springer. .pdf

Fabian Kuhn, Yoram Moses and Rotem Oshman. Coordinated Consensus in Dynamic Networks. In Proceedings of the 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, San Jose, California, pages 1-10, June 6-8, 2011. .pdf

Nancy A. Lynch, Stephen J. Garland, Dilsun Kaynar, Laurent Michel, and Alex Shvartsman. The Tempo Language User Guide and Reference Manual, October 2011. .pdf

Yishay Mansour, Boaz Patt-Shamir and Dror Rawitz. Competitive Router Scheduling with Structured Data. Proceedings of the 9th International Workshop on Approximation and Online Algorithms (WAOA 2011), Saarbrucken, Germany, September 2011. .pdf

Yishay Mansour, Boaz Patt-Shamir and Dror Rawitz. Overflow Management with Multipart Packets. 30th IEEE INFOCOM, April 2011. .pdf

Thomas Moscibroda and Rotem Oshman. Resilience of Mutual Exclusion Algorithms to Transient Memory Faults. In Proceedings of the 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, San Jose, California, June 6-8, 2011. .pdf

Calvin Newport and Nancy Lynch. Modeling Radio Networks. Distributed Computing, 24(2):101-118, October, 2011. .pdf

Aviv Nisgav and Boaz Patt-Shamir. Finding Similar Users in Social Networks. Theory of Computing Systems, 49(4):720-838, 2011. Special issue devoted to selected papers from SPAA 2009. .pdf

Aviv Nisgav and Boaz Patt-Shamir. Improved Collaborative Filtering. In T. Asano, S-I. Nakano, Y. Okamoto, O. Watanabe, editors, Algorithms and Computation - 22nd International Symposium (ISAAC 2011), Yokohama, Japan, December 2011, volume 7074 of Lecture Notes in Computer Science, pages 425-434, 2011. Springer. .pdf

Boaz Patt-Shamir and Dror Rawitz. Video Distribution Under Multiple Constraints. Theoretical Computer Science, 412(29):3717-3730, 2011. .pdf

Boaz Patt-Shamir and Marat Teplitsky. The Round Complexity of Distributed Sorting. In Proceedings of the 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, San Jose, California, June 6-8, 2011. .pdf

Tsvetomira Radeva and Nancy Lynch. Brief Announcement: Partial Reversal Acyclicity. In Proceedings of the 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC), San Jose, California, pages 353-354, June 6-8, 2011. .pdf

Tsvetomira Radeva and Nancy Lynch. Partial Reversal Acyclicity. Technical Report MIT-CSAIL-TR-2011-022, Computer Science and Artificial and Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA, April 2011. .pdf

Mikhail Volkov, Alejandro Cornejo, Daniela Rus and Nancy Lynch. Environment Characterization for Non-Recontaminating Frontier-Based Robotic Exploration. 4th International Conference on Principles and Practice of Multi-Agent Systems (PRIMA 2011), Wollongong, Australia, November 2011. Best Student Paper Award. .pdf

Jiang Wu. A Simulation Study on using the Virtual Node Layer to Implement Efficient and Reliable MANET Protocols. Ph.D. thesis, The City University of New York, Department of Computer Science, 2011. .pdf

Jiang Wu, Nancy Griffeth, Nancy Lynch, and Calvin Newport. Engineering the Virtual Node Layer for Reactive MANET Routing. Proceedings of the 10th International Symposium on Network Computing and Applications (NCA11), Cambridge, MA, August 2011. .pdf

2010

Dan Alistarh, Seth Gilbert, Rachid Guerraoui, Zarko Milosevic and Calvin Newport. Securing Every Bit: Authenticated Broadcast in Radio Networks. Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), Santorini, Greece, pages 50-59, June 2010. .pdf

Hagit Attiya and Keren Censor-Hillel. Lower Bounds for Randomized Consensus under a Weak Adversary. SIAM Journal on Computing, 39(8):3885-3904, December 2010. .pdf

Alejandro Cornejo and Fabian Kuhn. Deploying Wireless Networks with Beeps. In N. Lynch, A. Shvartsman, editors, Distributed Computing: Proceedings of the 24th International Symposium on Distributed Computing (DISC 2010), Cambridge, MA, September 2010., volume 6343 of Lecture Notes in Computer Science, pages 148-162, 2010. Springer. .pdf

Alejandro Cornejo and Nancy Lynch. Reliably Detecting Connectivity Using Local Graph Traits. In Principles of Distributed Systems (OPODIS 2010), Tozeur, Tunisia, December 2010, volume 6490 of Lecture Notes in Computer Science, pages 87-102, 2010. Springer. .pdf

Alejandro Cornejo and Nancy Lynch. Fault-Tolerance Through k-Connectivity, IEEE International Conference on Robotics and Automation (ICRA 2010): Workshop on Network Science and System Issues in Multi-Robot Autonomy, Anchorage, Alaska, May 2010. .pdf

Alejandro Cornejo and Calvin Newport. Prioritized Gossip in Vehicular Networks. Proceedings of Sixth ACM SIGACT/SIGMOBILE International Workshop on Foundations of Mobile Computing (DIALM-POMC 2010), Cambridge, MA, pages 53-62, September, 2010. .pdf

Alejandro Cornejo, Saira Viqar and Jennifer Welch. Reliable Neighbor Discovery for Mobile Ad Hoc Networks. Proceedings of Sixth ACM SIGACT/SIGMOBILE International Workshop on Foundations of Mobile Computing (DIALM-POMC 2010), Cambridge, MA, pages 63-72, September, 2010. .pdf

S. Dolev, S. Gilbert, M. Khabbazian and C. Newport. Broadcasting in Radio Networks with Multiple Channels. Manuscript, 2010.

Seth Gilbert, Nancy Lynch, and Alex Shvartsman. RAMBO: A Robust, Reconfigurable Atomic Memory Service for Dynamic Networks. Distributed Computing, 23(4):225-272, December 2010. .pdf. This is a slightly corrected version of the journal version, .pdf. The changes are explained in the following errata sheet .pdf

Dilsun Kaynar, Nancy Lynch, Roberto Segala, and Frits Vaandrager. The Theory of Timed I/O Automata. Synthesis Lectures on Computer Science, Morgan Claypool Publishers, 2010. Second Edition. .pdf

Majid Khabbazian, Dariusz Kowalski, Fabian Kuhn, and Nancy Lynch. Decomposing Broadcast Algorithms Using Abstract MAC Layers. Proceedings of Sixth ACM SIGACT/SIGMOBILE International Workshop on Foundations of Mobile Computing (DIALM-POMC 2010), Cambridge, MA, pages 13-22, September, 2010. .pdf

Majid Khabbazian, Dariusz Kowalski, Fabian Kuhn, and Nancy Lynch. The Cost of Global Broadcast using Abstract MAC Layers. Technical Report MIT-CSAIL-TR-2010-005, MIT Computer Science and Artificial Intelligence Laboratory, Cambridge, MA, February 9, 2010. .pdf

Majid Khabbazian, Fabian Kuhn, Nancy Lynch, Muriel Medard, and Ali ParandehGheibi. MAC Design for Analog Network Coding. Technical Report MIT-CSAIL-TR-2010-036, MIT Computer Science and Artificial Intelligence Laboratory, Cambridge, MA, July, 2010. .pdf

Fabian Kuhn, Christoph Lenzen, Thomas Locher, and Rotem Oshman. Optimal Gradient Clock Synchronization in Dynamic Networks. Proceedings of the 29th ACM Symposium on Principles of Distributed Computing, Zurich, Switzerland, pages 430-439, July 2010. .pdf

Fabian Kuhn, Nancy Lynch, and Calvin Newport. The Abstract MAC Layer. Technical Report MIT-CSAIL-TR-2010-040, Computer Science and Artificial Intelligence Laboratory, Cambridge, MA, August 2010. .pdf

Fabian Kuhn, Nancy Lynch, Calvin Newport, Rotem Oshman, Andrea Richa. Broadcasting in Unreliable Radio Networks. Proceedings of the 29th ACM Symposium on Principles of Distributed Computing, Zurich, Switzerland, pages 336-345, July 2010. .pdf

Fabian Kuhn, Nancy Lynch, Calvin Newport, Rotem Oshman, and Andrea Richa. Broadcasting in Unreliable Radio Networks. Technical Report MIT-CSAIL-TR-2010-029, MIT Computer Science and Artificial Intelligence Laboratory, Cambridge, MA, June 2010. .pdf

Fabian Kuhn, Nancy Lynch and Rotem Oshman. Distributed Computation in Dynamic Networks. Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC 2010), pages 513-522, Cambridge, MA, June 2010. .pdf

Shinya Umeno and Nancy Lynch. Automated Formal Verification of the DHCP Failover Protocol Using Timeout Order Abstraction. Proceedings of 15th IEEE International Conference on Engineering of Complex Computer Systems (ICECCS 2010), Oxford, UK, March 22-26 2010. .pdf

2009

Gregory Chockler, Seth Gilbert, Vincent C. Gramoli, Peter M. Musial, and Alex A. Shvartsman. Reconfigurable Distributed Storage for Dynamic Networks. Journal of Parallel and Distributed Computing, 69(1):100-116, January 2009. .pdf

Alejandro Cornejo, Fabian Kuhn, Ruy Ley-Wild, and Nancy Lynch. Keeping mobile robot swarms connected. In Idit Keidar, editor, Distributed Computing, DISC 2009: 23rd International Symposium on Distributed Computing, Elche/Elx, Spain, September 23-25 2009, volume 5805 of Lecture Notes in Computer Science, pages 496-511, 2009. Springer. .pdf Also, Extended version is Technical Report MIT-CSAIL-TR-2009-027, MIT CSAIL, Cambridge, MA, June 2009. .pdf

Alejandro Cornejo, Nancy Lynch, Saira Viqar, Jennifer Welch. A Neighbor Discovery Service Using an Abstract MAC Layer. Forty-Seventh Annual Allerton Conference, Champaign-Urbana, IL, October, 2009. Invited paper. .pdf

Alejandro Cornejo and Nancy Lynch. Brief Announcement: Minimum Spanning Trees and Cone-Based Topology Control. Proceedings of the 28th Annual ACM Symposium on Principles of Distributed Computing, Calgary, Canada, August 2009. .pdf

Shlomi Dolev, Seth Gilbert, Rachid Guerraoui, Fabian Kuhn and Calvin Newport. The Wireless Synchronization Problem. Proceedings of the ACM Symposium on the Principles of Distributed Computing (PODC), Calgary, Alberta, Canada, August 2009. .pdf

Shlomi Dolev, Seth Gilbert, Dariusz Kowalski, Fabian Kuhn, Nancy Lynch, Calvin Newport. Reliable Distributed Computing on Unreliable Radio Channels. The MobiHoc S3 Student Workshop, New Orleans, LA, May 2009. Invited paper. .pdf

Chryssis Georgiou, Nancy Lynch, Panayiotis Mavrommatis, and Joshua Tauber. Automated Implementation of Complex Distributed Algorithms Specified in the IOA Language. International Journal on Software Tools for Technology Transfer (STTT), 11(2):153-171, 2009. Springer. .pdf

Seth Gilbert, Rachid Guerraoui, Darek Kowalski, and Calvin Newport. Interference-Resilient Information Exchange. In Proceedings of the IEEE Conference on Computer Communications (INFOCOM), Rio de Janeiro, Brazil, April 19-25, 2009. .pdf

Seth Gilbert, Rachid Guerraoui, and Calvin Newport. Of Malicious Motes and Suspicious Sensors: On the Efficiency of Malicious Interference in Wireless Networks. Theoretical Computer Science,410(6-7):546-569, February 28, 2009. .pdf.

Seth Gilbert, Nancy Lynch, Sayan Mitra, and Tina Nolte. Self-Stabilizing Robot Formations Over Unreliable Networks. ACM Transactions on Autonomous and Adaptive Systems, 4(3):17.2-17.27, July 2009. .pdf

Rachid Guerraoui, Maurice Herlihy, Petr Kouznetsov, Nancy Lynch, and Calvin Newport. On the Weakest Failure Detector Ever. Distributed Computing, 21(5):353-366, February 2009. Special Issue PODC 2007. .pdf

Fabian Kuhn. Weak Graph Colorings: Distributed Algorithms and Applications. Proceedings of the 21st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), Calgary, Alberta, Canada, August 2009. .pdf

Fabian Kuhn. Local Multicoloring Algorithms: Computing a Nearly-Optimal TDMA Schedule in Constant Time. Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS), Freiburg, Germany, February 2009. .pdf

Fabian Kuhn, Thomas Locher, and Rotem Oshman. Gradient Clock Synchronization in Dynamic Networks. Proceedings of the 21st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), Calgary, Alberta, Canada, August 2009. .pdf

Fabian Kuhn, Nancy Lynch, and Calvin Newport. The Abstract MAC Layer. In I. Keidar, editor, Distributed Computing: DISC 2009: 23rd International Symposium on Distributed Computing, Elche/Elx, Spain, September 23-25, 2009, volume 5805 of Lecture Notes in Computer Science, pages 48-62, 2009. Springer. .pdf

Fabian Kuhn, Nancy Lynch and Calvin Newport. Brief Announcement: Hardness of Broadcasting in Wireless Networks with Unreliable Communication. Proceedings of the ACM Symposium on the Principles of Distributed Computing (PODC), Calgary, Alberta, Canada, August 2009. .pdf

Fabian Kuhn, Nancy Lynch, and Calvin Newport. The Abstract MAC Layer. Technical Report MIT-CSAIL-TR-2009-021, MIT CSAIL, Cambridge, MA, 02139, May 11, 2009. .pdf. Earlier version as MIT-CSAIL-TR-2009-009, MIT CSAIL, Cambridge, MA, February 20, 2009.

Fabian Kuhn, Nancy Lynch, and Rotem Oshman. Distributed Computation in Dynamic Networks. Technical Report MIT-CSAIL-TR-2009-058, MIT Computer Science and Artificial Intelligence Laboratory, Cambridge, MA, November 2009. .pdf.

Fabian Kuhn and Rotem Oshman. Gradient clock synchronization using reference broadcasts. In Principles of Dsitributed Systems (Proceedings of the 13th International Conference on Principle of DIstributed Systems (OPODIS), Nimes, France, December 2009, volume 5923 of Lecture Notes in Computer Science, pages 204-218, 2009. Springer. .pdf

Calvin Newport. Distributed Computation on Unreliable Radio Channels. Ph.D. thesis, MIT Department of Electrical Engineering and Computer Science, Cambridge, MA, September 2009. .pdf

Calvin Newport and Nancy Lynch. Modeling Radio Networks. In Mario Bravetti, Gianluigi Zavattaro, editors, CONCUR 2009 - Concurrency Theory, Proceedings of the 20th International Conference, Bologna, Italy, September, 2009, volume 5710 of Lecture Notes in Computer Science, pages 481-495, 2009. Springer. .pdf

Calvin Newport and Nancy Lynch. Modeling Radio Networks. Technical Report MIT-CSAIL-TR-2009-023, MIT Computer Science and Artificial Intelligence Laboratory, Cambridge, MA, June 4, 2009. .pdf

Tina Nolte. Virtual Stationary Timed Automata for Mobile Networks. Ph.D Thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA, February, 2009. .pdf

Tina Nolte, Shlomi Dolev, Limor Lahiani, and Nancy Lynch. Self-Stabilizing Message Routing in Mobile ad hoc Networks. Technical Report MIT-CSAIL-TR-2009-003, MIT CSAIL, Cambridge, MA, January 2009. Closely based on chapters 12-14 of Tina Nolte's MIT PhD thesis, 2009. .pdf

Rotem Oshman. An Automata-Theoretic Dynamic Completeness Criterion for Bounded Model-Checking. 10th International Conference on Verification, Model Checking, and Abstract Interpretation (VMCAI'09), Savannah, GA, January 2009. .pdf

Venugopalan Ramasubramanian, Dahlia Malkhi, Fabian Kuhn, Mahesh Balakrishnan, Archit Gupta, Adityla Akella. On the Treeness of Internet Latency and Bandwith. Proceedings of SIGMETRICS/Performance, Seattle, WA, June 2009. .pdf

Shinya Umeno. Machine-Assisted Parameter Synthesis of the Biphase Mark Protocol Using Event Order Abstraction. 7th International Conference on Formal Modelling and Analysis of Timed Systems (FORMATS 2009), Budapest, Hungry, September 13-16, 2009. .pdf

Shinya Umeno and Nancy Lynch. Timeout Order Abstraction for Time-Parametric Verification of Loosely Synchronized Real-Time Distributed Systems. Proceedings of the 2nd Workshop on Compositional Theory and Technology for Real-Time Embedded Systems (CTRS 2009), Washington, D.C., December 1, 2009, (Co-located with RTSS 2009). .pdf

Jiang Wu, Nancy Griffeth, Nancy Lynch, Calvin Newport, and Ralph Droms. Simulating Fixed Virtual Nodes for Adapting Wireline Protocols to MANET. The 8th IEEE International Symposium on Network Computing and Applications (IEEE NCA09), July 9, 2009. .pdf Best Paper Award.

2008

Myla Archer, Hongping Lim, Nancy Lynch, Sayan Mitra, and Shinya Umeno. Specifying and proving properties of timed I/O automata using Tempo. Journal of Design Automation for Embedded Systems, 2(1-2):139-170, June 2008. Springer. .pdf

Ran Canetti, Ling Cheung, Dilsun Kaynar, Nancy Lynch, and Olivier Pereira. Modeling Computational Security in Long-Lived Systems, Version 2. Technical Report MIT-CSAIL-TR-2008-068, Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA, November 2008. .pdf

R. Canetti, L. Cheung, D. Kaynar, M. Liskov, N. Lynch, O. Pereira, and R. Segala. Analyzing Security Protocols Using Time-Bounded Task-PIOAs. Journal of Discrete Event Dynamic Systems (DEDS), 18(1):111-159, March 2008. (Appears online February 2008). Springer. .pdf

Ran Canetti, Ling Cheung, Dilsun Kaynar, Nancy Lynch, and Olivier Pereira. Modeling Computational Security in Long-Lived Systems. In Franck van Breugel, Marsha Chechik, editors, CONCUR 2008 - Concurrency Theory: 19th International Conference, Toronto, Canada, August, 2008, volume 5201 of Lecture Notes in Computer Science, pages 114-130, 2008. Springer. Available as Cryptology ePrint Archive as report 2007/406. .pdf.

Gregory Chockler, Seth Gilbert, and Nancy Lynch. Virtual Infrastructure for Collision-Prone Wireless Networks. Proceedings of the 27th Symposium on Principles of Distributed Computing (PODC), pages 233-242, Toronto, Canada, August 2008. .pdf

Gregory Chockler, Murat Demirbas, Seth Gilbert, Nancy Lynch, Calvin Newport, and Tina Nolte. Consensus and collision detectors in radio networks. Distributed Computing, 21(1):55-84, June 2008. .pdf

Alejandro Cornejo, Nancy Lynch. Connectivity Service for Mobile Ad-Hoc Networks. Spatial Computing Workshop at 2nd IEEE International Conference on Self-Adaptive and Self-Organizing Systems, Venice, Italy, October 2008. .pdf

Shlomi Dolev, Seth Gilbert, Rachid Guerraoui, and Calvin Newport. Secure Communication over Radio Channels. Proceeding of the 27th Symposium on Principles of Distributed Computing (PODC), Toronto, Canada, August 2008. .pdf

Rui Fan. Lower Bounds in Distributed Computing. Ph.D Thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA, February 2008. .pdf

Seth Gilbert, Nancy Lynch, Sayan Mitra, and Tina Nolte. Self-Stabilizing Mobile Robot Formations with Virtual Nodes. In Sandeep S. Kulkarni, Andre Schiper, editors, Stabilization, Safety and Security of Distributed Systems: Proceedings of the 10th Symposium (SSS 2008), Detroit, Michigan, November 2008, volume 5340 of Lecture Notes in Computer Science, pages 188-202, 2008. Springer. .pdf

R. Grosu, X. Huang, N. Lynch, S.A. Smolka. Model Checking TIOA. Technical Report CS-CL-08-02,Department of Computer Science, Stony Brook University, Stony Brook, NY, USA, 2008.

Rachid Guerraoui and Nancy A. Lynch. A general characterization of indulgence. ACM Transactions on Autonomous and Adaptive Systems (TAAS), 3(4), November 2008. .pdf

Daniel Liberzon, Nancy Lynch, and Sayan Mitra. Verifying Average Dwell Time of Hybrid Systems. ACM Transactions in Embedded Computing Systems 8(1):1-37, 2008. .pdf

Nancy Lynch, Laurent Michel, and Alexander Shvartsman. Tempo: A Toolkit for The Timed Input/Output Automata Formalism. First International Conference on Simulation Tools and Techniques for Communications, Networks, and Systems (SIMUTools 2008), Industrial Track: Simulation Works. Conference Proc. CD, paper 3105, 8 pages, Marseille, France, March 4-7, 2008. .pdf

Mike Spindel. Simulation and Evaluation of the Reactive Virtual Node Layer. Master of Engineering Thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA, May 2008. .pdf

Shinya Umeno. Event order abstraction for parametric real-time system verification. International Conference on Embedded Software (EMSOFT 2008), Atlanta, Georgia, pages 1-10, October 2008. .pdf

Shinya Umeno. Event Order Abstraction for Parametric Real-Time System Verification. Technical Report MIT-CSAIL-TR-2008-048, Massachusetts Institute of Technology, Cambridge MA, 2008. .pdf

Shinya Umeno. Event order abstraction for parametric timed verification . Second Workshop on Event-Based Semantics, St. Louis MO, USA. April 21, 2008. .pdf

2007

Matthew D. Brown. Air Traffic Control Using Virtual Stationary Automata. Master of Engineering Thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA, September 2007. .pdf

Matthew Brown, Seth Gilbert, Nancy Lynch, Calvin Newport, Tina Nolte, and Michael Spindel. The Virtual Node Layer: A Programming Abstraction for Wireless Sensor Networks. ACM SIGBED Review, 4(3), July 2007. .pdf

Matthew Brown, Seth Gilbert, Nancy Lynch, Calvin Newport, Tina Nolte, and Michael Spindel. The Virtual Node Layer: A Programming Abstraction for Wireless Sensor Networks. Proceedings of the the International Workshop on Wireless Sensor Network Architecture (WWSNA), Cambridge, MA, April, 2007. .pdf

Ran Canetti, Ling Cheung, Dilsun Kaynar, Nancy Lynch, and Olivier Pereira. Modeling Computational Security in Long-Lived Systems. Cryptology ePrint Archive Report 2007/406. .pdf.

Ran Canetti, Ling Cheung, Dilsun Kaynar, Nancy Lynch, and Olivier Pereira. Compositional Security for Task-PIOAs. Proceedings of the 20th IEEE Computer Security Foundations Symposium (CSF 2007), Venice, Italy, pages 125-139, July 2007. .pdf

Ran Canetti, Ling Cheung, Nancy Lynch, and Olivier Pereira. On the Role of Scheduling in Simulation-Based Security. 7th International Workshop on Issues in the Theory of Security (WITS'07), Braga, Portugal, March 2007. Also, ePrint Report 2007/102, Cryptology ePrint archive, 2007. .pdf

Ran Canetti, Ling Cheung, Dilsun Kaynar, Moses Liskov, Nancy Lynch, Olivier Pereira, and Roberto Segala. Using Task-Structured Probabilistic I/O Automata to Analyze an Oblivious Transfer Protocol. Technical Report MIT-CSAIL-TR-2007-011, CSAIL, Massachusetts Institute of Technology, Cambridge, MA, February 16, 2007. (Earlier version is MIT-CSAIL-TR-2006-047). .pdf

Ling Cheung, Joseph A. Cooley, Roger Khazan, and Calvin Newport. Collusion-Resistant Group Key Management Using Attribute-Based Encryption. Proceedings of 1st International Workshop on Group-Oriented Cryptographic Protocols, Wroclaw, Poland, July 2007. .pdf

Ling Cheung and Calvin Newport. Provably Secure Ciphertext Policy ABE. Proceedings of the 14th ACM Conference on Computer and Communications Security (CCS), Alexandria, VA, October, 2007. Also, ePrint Report 2007/183, Cryptology ePrint archive, 2007. .pdf

Ling Cheung, Sayan Mitra and Olivier Pereira. Verifying Statistical Zero Knowledge with Approximate Implementations. Cryptology ePrint Archive Report 2007/195. .pdf

Shlomi Dolev, Seth Gilbert, Rachid Guerraoui, and Calvin Newport. Gossiping in a Multi-Channel Radio Network: An Oblivious Approach to Coping with Malicious Interference. In Andrzej Pelc, editor Proceedings of the 21th International Symposium on Distributed Computing (DISC 2007), Lemesos, Cyprus, September, 2007, volume 4731 of Lecture Notes in Computer Science, pages 208-222, 2007. Springer. .pdf

Rui Fan, Ralph Droms, Nancy Griffeth, and Nancy Lynch. The DHCP Failover Protocol: A Formal Perspective. In John Derrick, Juri Vain, editors, 27th IFIP WG 6.1 International Conference on Formal Methods for Networked and Distributed Systems (FORTE 2007), Tallinn, Estonia, June 26-29, 2007, volume 4574 of Lecture Notes in Computer Science, pages 211-226, 2007. Springer. .pdf

Seth Gilbert. Virtual Infrastructure for Wireless Ad Hoc Networks. Ph.D Thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA 02139, 2007. .pdf

Radu Grosu, Sayan Mitra, Pei Ye, Scott Smolka, Emilia Entcheva, and I. O. Ramakrishnan. Learning cycle-linear hybrid automata of excitable cell models. In Hybrid Systems: Computation and Control (HSCC 07), volume 4416 of Lecture Notes in Computer Science, pages 245-258, April 2007. .pdf

Rachid Guerraoui, Maurice Herlihy, Petr Kouznetsov, Nancy Lynch, and Calvin Newport. On the weakest failure detector ever. Proceedings of the Twenty-Sixth Annual ACM Symposium on the Principles of Distributed Computing (PODC), Portland, Oregon, pages 235-243, August 2007. .pdf

Xavier Koegler (supervised by Nancy Lynch). Around the Tempo Toolset Userguide. March 20th-August 31st, 2007. .pdf

Carolos Livadas and Nancy A. Lynch. A Reliable Broadcast Scheme for Sensor Networks. Technical Report MIT-LCS-TR-915, MIT Computer Science and Artificial Intelligence Laboratory, Cambridge, MA, February 2007 (Revision of earlier version dated August 2003). .pdf

Nancy A. Lynch. DISC 20th Anniversary, Invited Talk: My Early Days in Distributed Computing Theory: 1979-1982. In Andrzej Pelc, editor, Distributed Computing, 21st International Symposium, DISC 2007, Lemesos, Cyprus, September 24-26, 2007, volume 4731 of Lecture Notes in Computer Science, page 505, 2007. Springer. .pdf

Nancy A. Lynch. Distributed computing theory: algorithms, impossibility results, models, and proofs. Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC 2007), San Diego, California, page 247, June 11-13, 2007. .pdf

Nancy Lynch, Roberto Segala, and Frits Vaandrager. Observing Branching Structure through Probabilistic Contexts. Siam Journal on Computing, 37(4):977-1013, September 2007. .pdf

Sayan Mitra. A Verification Framework for Ordinary and Probabilistic Hybrid Systems. Ph.D Thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA, September 2007. .pdf

Sayan Mitra and Nancy Lynch. Proving approximate implementation relations for Probabilistic I/O Automata. Electronic Notes in Theoretical Computer Science, 174(8):71-93, 2007. .pdf

Sayan Mitra and Nancy Lynch. Trace-based semantics of Probabilistic timed I/O automata. Hybrid Systems: Computation and Control (HSCC 2007), Pisa, Italy, April 3-5, 2007, volume 4416 of Lecture Notes in Computer Science, pages 718-722, 2007. Springer. .pdf

Tina Nolte and Nancy Lynch. Self-stabilization and Virtual Node Layer Emulations. In Toshimitsu Masuzawa, Sebastien Tixeuil, editors, Stabilization, Safety, and Security of Distributed Systems, 9th International Symposium (SSS 2007), Paris, France, November 2007, volume 4838 of Lecture Notes in Computer Science, pages 394-408, 2007. Springer. .pdf

Tina Nolte and Nancy Lynch. A Virtual Node-Based Tracking Algorithm for Mobile Networks. International Conference on Distributed Computing Systems (ICDCS 2007), Toronto, Canada, June, 2007. .pdf

Shinya Umeno and Nancy Lynch. Safety Verification of an Aircraft Landing Protocol: A Refinement Approach. In Alberto Bemporad, Antonio Bicchi, Giorgio C. Buttazzo, editors, Hybrid Systems: Computation and Control (HSCC 2007), Pisa, Italy, April 3-5, 2007, volume 4416 of Lecture Notes in Computer Science, pages 557-572, 2007. Springer. .pdf

2006

Myla Archer, Hongping Lim, Nancy Lynch, Sayan Mitra and Shinya Umeno. Specifying and Proving Properties of Timed I/O Automata in the TIOA Toolkit. Fourth ACM-IEEE International Conference on Formal Methods and Models for Codesign (MEMOCODE'06), Napa Valley, California, pages 129-138, July, 2006. .pdf

Paul Attie. On the Refinement of Liveness Properties of Distributed Systems. Manuscript, 2006. pdf

Michael A. Bender, Jeremy T. Fineman, and Seth Gilbert. Contention Resolution with Heterogeneous Job Sizes. Proceedings of the 14th Annual European Symposium on Algorithms, September, 2006. .pdf

Ran Canetti, Ling Cheung, Dilsun Kaynar, Moses Liskov, Nancy Lynch, Olivier Pereira, and Roberto Segala. Time-bounded Task-PIOAs: A Framework for Analyzing Security Protocols. In Shlomi Dolev, editor, Distributed Computing, 20th International Symposium on Distributed Computing (DISC 2006), Stockholm, Sweden, September 2006, volume 4167 of Lecture Notes in Computer Science, pages 238-253, 2006. Springer. Invited paper. .pdf

Ran Canetti, Ling Cheung, Dilsun Kaynar, Moses Liskov, Nancy Lynch, Olivier Pereira, and Roberto Segala. Task-Structured Probabilistic I/O Automata. Technical Report MIT-CSAIL-TR-2006-060, CSAIL, Massachusetts Institute of Technology, Cambridge, MA, August, 2006..pdf

Ran Canetti, Ling Cheung, Dilsun Kaynar, Moses Liskov, Nancy Lynch, Olivier Pereira, and Roberto Segala. Task-Structured Probabilistic I/O Automata. Proceedings the 8th International Workshop on Discrete Event Systems (WODES'06), Ann Arbor, Michigan, July, 2006. .pdf

Ran Canetti, Ling Cheung, Dilsun Kaynar, Moses Liskov, Nancy Lynch, Olivier Pereira, and Roberto Segala. Using Task-Structured Probabilistic I/O Automata to Analyze Cryptographic Protocols. In V. Cortier, S. Kremer, editors, Workshop on Formal and Computational Cryptography - FCC 2006, pages 34--39, July 2006. .pdf

Ran Canetti, Ling Cheung, Dilsun Kaynar, Moses Liskov, Nancy Lynch, Olivier Pereira, and Roberto Segala. Using Task-Structured Probabilistic I/O Automata to Analyze an Oblivious Transfer Protocol. Technical Report MIT-CSAIL-TR-2006-047, CSAIL, Massachusetts Institute of Technology, Cambridge, MA, June 19, 2006. (Latest version is MIT-CSAIL-TR-2007-011). .pdf

Ran Canetti, Ling Cheung, Dilsun Kaynar, Moses Liskov, Nancy Lynch, Olivier Pereira, and Roberto Segala. Using Probabilistic I/O Automata to Analyze an Oblivious Transfer Protocol. Technical Report MIT-CSAIL-TR-2006-046, CSAIL, Massachusetts Institute of Technology, Cambridge, MA, January 10, 2006. .pdf

Ran Canetti, Ling Cheung, Dilsun Kaynar, Moses Liskov, Nancy Lynch, Olivier Pereira, and Roberto Segala. Task-Structured Probabilistic I/O Automata. Technical Report MIT-CSAIL-TR-2006-023, CSAIL, Massachusetts Institute of Technology, Cambridge, MA, March, 2006. .pdf

Ran Canetti, Ling Cheung, Dilsun Kaynar, Moses Liskov, Nancy Lynch, Olivier Pereira, and Roberto Segala. Using Task-Structured Probabilistic I/O Automata to Analyze an Oblivious Transfer Protocol. Technical Report MIT-CSAIL-TR-2006-019, CSAIL, Massachusetts Institute of Technology, Cambridge, MA, March, 2006. .pdf

Ling Cheung, Nancy Lynch, Roberto Segala, and Frits Vaandrager. Switched Probabilistic PIOA: Parallel Composition via Distributed Scheduling. Theoretical Computer Science, 365(1-2):83-108, November 2006. .pdf

Gregory Chockler, Seth Gilbert, and Boaz Patt-Shamir. Communication-Efficient Probabilistic Quorum Systems. Proceedings of the IEEE International Workshop on Foundations and Algorithms for Wireless Networking (FAWN), March 29-31, 2006. .pdf

Constantinos Djouvas, Nancy D. Griffeth, and Nancy A. Lynch. Testing Self-Similar Networks Electronic Notes in Theoretical Computer Science, Proceedings of the Second Workshop on Model Based Testing (MBT 2006), 164(4):67-82, October 2006. .pdf

Rui Fan and Nancy Lynch. Gradient Clock Synchronization. Distributed Computing, 18(4):255-266, March, 2006. .pdf.

Rui Fan and Nancy Lynch. An Ω (n log n) Lower Bound on the Cost of Mutual Exclusion. Proceedings of the Twenty-Fifth Annual Symposium on Principles of Distributed Computing (PODC'06), Denver, Colorado, pages 275-284, July 2006. .pdf

Seth Gilbert, Rachid Guerraoui, and Calvin Newport. Of Malicious Motes and Suspicious Sensors: On the Efficiency of Malicious Interference in Wireless Networks. In Alexander Shvartsman, editor, Proceedings of the 10th International Conference On Principles Of Distributed Systems (OPODIS), Bordeaux, France, December 12-15, 2006, volume 4305 of Lecture Notes in Computer Science, pages 215-229, 2006. Springer. .pdf

Seth Gilbert, Rachid Guerraoui, and Calvin Newport. Of Malicious Motes and Suspicious Sensors. Technical Report MIT-CSAIL-TR-2006-026, CSAIL, Massachusetts Institute of Technology, Cambridge, MA, April 2006. .pdf

Rachid Guerraoui and Nancy Lynch. A General Characterization of Indulgence. In Ajoy Kumar Datta, Maria Gradinariu, editors, Stabilization, Safety, and Security of Distributed Systems, 8th International Symposium (SSS 2006), Dallas, TX, November 17-19, 2006, volume 4280 of Lecture Notes in Computer Science, pages 16-34, 2006. Springer. .pdf

Dilsun K. Kaynar, Nancy Lynch, Roberto Segala, and Frits Vaandrager. The Theory of Timed I/O Automata. Synthesis Lectures on Computer Science, Morgan Claypool Publishers, 2006. Revised and shortened version of Technical Report MIT-LCS-TR-917a (from 2004). .pdf

K. Konwar, P.M. Musial, N.C. Nicolau, and A.A. Shvartsman. Implementing Atomic Data through Indirect Learning in Dynamic Networks. Technical Report MIT-CSAIL-TR-2006-070, Computer Science and Artificial Intelligence Laboratory, Massahusetts instute of Technology, Cambridge, MA, October 2006. .pdf

Matthew Lepinski, David Liben-Nowell, Seth Gilbert, and April Rasala Lehman. Playing Games in Many Possible Worlds. Proceedings of the Seventh ACM Conference on Electronic Commerce, June, 2006. .pdf

Hongping Lim. Translating Timed I/O Automata Specifications for Theorem Proving in PVS. Masters thesis, MIT Department of Electrical Engineering and Computer Science, Cambridge, MA, February 2006. .pdf

Sayan Mitra and Nancy Lynch. Approximate simulations for task-structured probabilistic I/O automata. LICS workshop on Probabilistic Automata and Logics (PAul06), Seattle, WA, August 2006. .pdf

Sayan Mitra, Daniel Liberzon, and Nancy Lynch. Verifying average dwell time by solving optimization problems. In Ashish Tiwari and Joao P. Hespanha, editors, Hybrid Systems: Computation and Control,9th International Workshop (HSCC 06) Santa Barbara, CA, March 2006, volume 3927 of Lecture Notes in Computer Science, pages 476-490, 2006. Springer. .pdf

Calvin Newport. Consensus and Collision Detectors in Wireless Ad Hoc Networks. Masters Thesis, MIT Department of Electrical Engineering and Computer Science, Cambridge, MA, June 2006. .pdf

Shinya Umeno and Nancy Lynch. Proving safety properties of an aircraft landing protocol using I/O Automata and the PVS theorem prover: a case study. In Jayadev Misra, Tobias Nipkow, Emil Sekerinski, editors, FM 2006: Formal Methods, 14th International Symposium of Formal Methods, Hamilton, Ontario Canada, August, 2006, volume 4085 of Lecture Notes in Computer Science, pages 64-80, 2006. Springer. .pdf

Shinya Umeno. Proving safety properties of an aircraft landing protocol using timed anduntimed I/O automata: a case study. Masters Thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA, October 2006. .pdf

2005

Paul Attie and Hana Chockler. Efficiently Verifiable Conditions for Deadlock-freedom of Large Concurrent Programs. Proceedings of the Sixth International Conference on Verification, Model Checking and Abstract Interpretation, Paris, France, January 2005. .pdf

Paul Attie, Rachid Guerraoui, Petr Kouznetsov, Nancy Lynch, and Sergio Rajsbaum. The Impossibility of Boosting Distributed Service Resilience. 25th IEEE International Conference on Distributed Computing Systems (ICDCS 2005), Columbus, OH, pages 39-48, June 6-10, 2005. .pdf

Paul Attie, Rachid Guerraoui, Petr Kouznetsov, Nancy Lynch, and Sergio Rajsbaum. Impossibility of boosting distributed service resilience. Technical Report MIT-LCS-TR-982, Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA, February 2005. .pdf

Michael Bender, Jeremy Fineman, Seth Gilbert, and Bradley Kuszmaul. Concurrent Cache-Oblivious B-Trees. 17th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2005), Las Vegas, Nevada, July 2005. .pdf

Ran Canetti, Ling Cheung, Dilsun Kaynar, Moses Liskov, Nancy Lynch, Olivier Pereira, and Roberto Segala. Using Probabilistic I/O Automata to Analyze an Oblivious Transfer Protocol.ePrint Report 2005/452, Cryptology ePrint Archive, 2005. .pdf

Ran Canetti, Ling Cheung, Dilsun Kaynar, Moses Liskov, Nancy Lynch, Olivier Pereira, and Roberto Segala. Using Probabilistic I/O Automata to Improve the Analysis of Cryptographic Protocols. In ERCIM News, 63: 40-41, October 2005. .pdf

Ran Canetti, Ling Cheung, Dilsun Kaynar, Moses Liskov, Nancy Lynch, Olivier Pereira, and Roberto Segala. Using Probabilistic I/O Automata to Analyze an Oblivious Transfer Protocol. Technical Report CSAIL-TR-2005-055, MIT CSAIL, Cambridge, MA, August 2005. .pdf

Gregory Chockler and Dahlia Malkhi. Active Disk Paxos with infinitely many processes. Distributed Computing, volume 18, number 1, pages 73-84, July 2005. .pdf

Gregory Chockler, Nancy Lynch, Sayan Mitra, and Joshua Tauber. Proving Atomicity: An Assertional Approach In Pierre Fraigniaud, editor, Distributed Computing, 19th International Conference (DISC 2006), Cracow, Poland, September 2005, volume 3724 of Lecture Notes in Computer Science, pages 152-168, 2005. Springer. .pdf

G. Chockler, M. Demirbas, S. Gilbert, and C. Newport. A Middleware Framework for Robust Applications in Wireless Ad Hoc Networks. Allerton Conference 2005: Forty-Third Annual Allerton Conference on Communication, Control, and Computing, September 2005. .pdf

Gregory Chockler, Murat Demirbas, Seth Gilbert, Nancy Lynch, Calvin Newport, and Tina Nolte. Reconciling the Theory and Practice of (Un)Reliable Wireless Broadcast. Proceedings of the 4th International Workshop on Assurance in Distributed Systems and Networks (ADSN 2005), Columbus, Ohio, pages 42-48, June 2005. .pdf

Gregory Chockler, Murat Demirbas, Seth Gilbert, Calvin Newport, and Tina Nolte. Consensus and Collision Detectors in Wireless Ad Hoc Networks. Twenty-Fourth Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC 2005), Las Vegas, Nevada, pages 197-206, July 2005. .pdf

Gregory Chockler, Seth Gilbert, Vincent Gramoli, Peter Musial, and Alexander Shvartsman. Reconfigurable Distributed Storage for Dynamic Networks. In James H. Anderson, Giuseppe Prencipe, Roger Watenhofer, editors, Principles of Distributed systems: 9th International Conference on Principles of Distributed Systems (OPODIS 2005), Pisa, Italy, December 2005, volume 3974 of Lecture Notes in Computer Science, pages 351-365, 2006. Springer. .pdf

Gregory Chockler, Nancy Lynch, Sayan Mitra, and Joshua Tauber. Proving Atomicity: An Assertional Approach. Technical Report MIT-CSAIL-TR-2005-048 (and MIT-LCS-TR-995), MIT CSAIL, Cambridge, MA, July 2005. .pdf

Shlomi Dolev, Limor Lahiani, Nancy Lynch, and Tina Nolte. Self-Stabilizing Mobile Node Location Management and Message Routing. In Ted Herman, Sebastien Tixeuil, editors, Self-Stabilizing Systems: Seventh International Symposium on Self Stabilizing Systems (SSS 2005), Barcelona, Spain, October 26-27, 2005, volume 3764 of Lecture Notes in Computer Science, pages 96-112, 2005. Springer. Also, Technical Report MIT-LCS-TR-999, MIT Computer Science and Artificial Intelligence Laboratory, Cambridge, MA, August 2005. .pdf

Shlomi Dolev, Seth Gilbert, Limor Lahiani, Nancy Lynch, and Tina Nolte. Timed Virtual Stationary Automata for Mobile Networks. In James H. Anderson, Giuseppe Prencipe, Roger Watenhofer, editors, Principles of Distributed systems: 9th International Conference on Principles of Distributed Systems (OPODIS 2005), volume 3974 of Lecture Notes in Computer Science, pages 130-145, 2006, Springer. Also, Technical Report MIT-LCS-TR-979a, MIT CSAIL, Cambridge, MA 02139, August 2005. .pdf

Shlomi Dolev, Seth Gilbert, Limor Lahiani, Nancy Lynch, and Tina Nolte. Timed Virtual Stationary Automata for Mobile Networks. Allerton Conference 2005: Forty-Third Annual Allerton Conference on Communication, Control, and Computing, September 2005. Invited paper. .pdf

Shlomi Dolev, Seth Gilbert, Nancy A. Lynch, Alex A. Shvartsman, and Jennifer L. Welch. GeoQuorums: Implementing Atomic Memory in Mobile Ad Hoc Networks. Distributed Computing, Special Issue DISC03, 18(2):125-155, 2005. .pdf Also, Technical Report MIT-LCS-TR-900a, CSAIL, Massachusetts Institute of Technology, Cambridge, MA, 2004. .ps

Shlomi Dolev, Seth Gilbert, Elad Schiller, Alex A. Shvartsman, and Jennifer Welch. Autonomous Virtual Mobile Nodes. DIAL-M-POMC 2005: Third Annual ACM/SIGMOBILE International Workshop on Foundation of Mobile Computing, Cologne, Germany, September 2, 2005. .pdf

Shlomi Dolev, Seth Gilbert, Elad Schiller, Alex Shvartsman, Jennifer Welch. Brief Announcement: Autonomous Virtual Mobile Nodes. 17th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2005), Las Vegas, Nevada, July 2005. .ps

Shlomi Dolev, Limor Lahiani, Seth Gilbert, Nancy Lynch, Tina Nolte. Brief Announcement: Virtual Stationary Automata for Mobile Networks. Proceedings of the 24th Annual ACM Symposium on Principles of Distributed Computing (PODC'05), Las Vegas, Nevada, July, 2005. .pdf

Shlomi Dolev, Seth Gilbert, Limor Lahiani, Nancy Lynch, and Tina Nolte. Timed Virtual Stationary Automata for Mobile Networks. Techncial Report MIT-LCS-TR-979a, MIT CSAIL, Cambridge, MA, August 2005. .pdf

Shlomi Dolev, Seth Gilbert, Elad Schiller, Alex Shvartsman, and Jennifer Welch. Autonomous Virtual Mobile Nodes. Technical Report MIT-LCS-TR-992, MIT CSAIL, Cambridge, MA, June 2005. .pdf

Shlomi Dolev, Seth Gilbert, Limor Lahiani, Nancy Lynch, and Tina Nolte. Virtual Stationary Automata for Mobile Networks (Extended Abstract) Technical Report MIT-LCS-TR-979, MIT CSAIL, Cambridge, MA 02139, January 2005. .pdf

Shlomi Dolev, Limor Lahiani, Nancy Lynch, and Tina Nolte. Self-Stabilizing Mobile Node Location Management and Message Routing. Technical Report MIT-LCS-TR-999, MIT Computer Science and Artificial Intelligence Laboratory, Cambridge, MA, August 2005. .pdf

Stephen Garland. TIOA User Guide and Reference Manual. September 15, 2005. .pdf

Stephen Garland, Dilsun Kaynar, Nancy Lynch, Joshua Tauber, and Mandana Vaziri. TIOA Tutorial. May 22, 2005. .pdf

Chryssis Georgiou, Nancy Lynch, Panayiotis Mavrommatis and Joshua Tauber. Automated Implementation of Complex Distributed Algorithms Specified in the IOA Language. Proceedings of the ISCA 18th International Conference on Parallel and Distributed Computing Systems, Las Vegas, Nevada, 128-134, September, 2005. .pdf

Dilsun Kaynar, Nancy Lynch, Sayan Mitra, and Stephen Garland. The TIOA Language. Version 0.21, May 22, 2005. .pdf

Ben Leong, Sayan Mitra, and Barbara Liskov. Path vector face routing: Geographic routing with local face information. Proceedings of 13th IEEE International Conference on Network Protocols (ICNP'05 ), November 6-9, 2005, Boston, Massachusetts, USA. .pdf

Hongping Lim, Dilsun Kaynar, Nancy Lynch, and Sayan Mitra. Translating timed I/O automata specifications for theorem proving in PVS. In Paul Pettersson, Wang Yi, editors, Formal Modeling and Analysis of Timed Systems, Third International Conference (FORMATS 2005), Uppsala, Sweden, September 26-28, volume 3829 of Lecture Notes in Computer Science, pages 17-31, 2005. Springer. .pdf

Nancy Lynch. A Three-Level Analysis of a Simple Acceleration Maneuver, with Uncertainties. In Aurel Cornell and Dan Ionescu, editors, Real-Time Systems: Modeling, Design, and Applications, volume 8 of AMAST Series in Computing, World Scientific Publishing Company, 2005. .pdf

Nancy Lynch, Sayan Mitra, and Tina Nolte. Motion coordination using virtual nodes. Technical Report MIT-LCS-TR-986, MIT CSAIL, Cambridge, MA, April 2005. .pdf

Nancy Lynch, Sayan Mitra, and Tina Nolte. Motion Coordination Using Virtual Nodes. CDC-ECC 2005: Forty-Fourth IEEE Conference on Decision and Control and European Control Conference, Seville, Spain, December 2005. Invited paper. .pdf

Sayan Mitra and Myla Archer. PVS Strategies for proving abstraction properties automata. In Electronic Notes in Theoretical Computer Science, volume 125(2), 2005, pages 45-65. .pdf

Sayan Mitra and Daniel Liberzon. Stability of Hybrid Automata with Average Dwell Time: An Invariant Approach. Proceedings of the 43rd Conference on Decision and Control (CDC 2004), Paradise Island, Bahamas, December, 2004. .pdf

Athicha Muthitacharoen, Seth Gilbert, and Robert Morris. Etna: A Fault-tolerant Algorithm for Atomic Mutable DHT Data. Technical Report MIT-CSAIL-TR-2005-044, MIT CSAIL, Cambridge, MA, June 2005. .pdf

Joshua A. Tauber. Verifiable Compilation of I/O Automata without Global Synchronization. Ph.D Thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA 02139, February, 2005. .pdf

2004

Ittai Abraham, Gregory Chockler, Idit Keidar and Dahlia Malkhi. Byzantine Disk Paxos: Optimal Resilience with Byzantine Shared Memory. Proceedings of the 23rd Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC 2004), St. John's, Newfoundland, Canada, pages 226-235, July 2004. © ACM, (2004). This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in the Proceedings of the Twenty-Third Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC 2004). .pdf

P.C. Attie, A. Arora, and E.A. Emerson. ACM Transactions on Programming Languages and Systems (TOPLAS), vol. 26, no. 1, pp 125-185, January 2004. Extended abstract appears in ACM Symposium on the Principles of Distributed Computing (PODC) 1998. .pdf

Jacob Beal and Seth Gilbert. RamboNodes for the Metropolitan Ad Hoc Network. Proceedings of the Workshop on Dependability in Wireless Ad Hoc Networks and Sensor Networks, part of the International Conference on Dependable Systems and Networks, Florence, Italy, June-July, 2004. .ps Also, AI Memo: AIM-2003-027.

Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, Charles E. Leiserson. On-the-Fly Maintenance of Series-Parallel Relationships in Fork-Join Multithreaded Programs. Sixteenth ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2004), Barcelona, Spain, pages 133-144, June 27-30, 2004..ps

Ling Cheung, Nancy Lynch, Roberto Segala, and Frits Vaandrager. Switched Probabilistic I/O Automata. In Z. Liu and K. Araki, editors, Theoretical Aspects of Computing, First International Colloquium (ICTAC2004),Guiyang, China, September 2004, volume 3407 of Lecture Notes in Computer Science, pages 494-510, Springer-Verlag, 2005. .pdf

Ling Cheung, Nancy Lynch, Roberto Segala, and Frits Vaandrager. Switched Probabilistic I/O Automata. Nijmegen Institute for Computing and Information Sciences (NIII) Technical Report NIII-R0437, Catholic University of Nijmegen, Nijmegen, The Netherlands, September 2004. .ps

G. Chockler and D. Malkhi. Light-Weight Leases for Storage-Centric Coordination. Technical Report MIT-LCS-TR-934, MIT Laboratory for Computer Science, January, 2004. Revised April 2004. .ps

Gregory Chockler, Idit Keidar and Dahlia Malkhi. Optimal Resilience Wait-Free Storage from Byzantine Components: Inherent Costs and Solutions. FuDiCo II: S.O.S. Survivability: Obstacles and Solutions. 2nd Bertinoro Workshop on Future Directions in Distributed Computing, 23-25 June 2004 University of Bologna Residential Center Bertinoro (Forli), Italy..pdf

Murat Demirbas, Anish Arora, Tina Nolte, and Nancy Lynch. A Hierarchy-based Fault-local Stabilizing Algorithm for Tracking in Sensor Networks. In Teruo Higashino, editor, Principles of Distributed Systems: OPODIS 2004: 8th International Conference on Principles of Distributed Systems, Grenoble, France, December 15-17, 2004, volume 3544 of Lecture Notes in Computer Science, pages 299-315, 2005. Springer. .pdf.

Murat Demirbas, Anish Arora, Tina Nolte, and Nancy Lynch. Brief Announcement: STALK: A Self-Stabilizing Hierarchical Tracking Service for Sensor Networks. Proceedings of the 23rd Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC 2004), St. John's, Newfoundland, Canada, page 378, July 25-28, 2004. .ps

Shlomi Dolev, Seth Gilbert, Nancy A. Lynch, Elad Schiller, Alex A. Shvartsman, and Jennifer L. Welch. Virtual Mobile Nodes for Mobile Ad Hoc Networks. In Rachid Guerraoui, editor, DISC 2004 (18th International Symposium on Distributed Computing, Trippenhuis, Amsterdam, the Netherlands, October, 2004), volume 3274 of Lecture Notes in Computer Science, pages 230-244, Springer, December, 2004. .ps

Shlomi Dolev, Seth Gilbert, Nancy Lynch, Elad Schiller, Alex Shvartsman, Jennifer Welch. Brief Announcement: Virtual Mobile Nodes for Mobile Ad Hoc Networks. Proceedings of the 23rd Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC 2004), St. John's, Newfoundland, Canada, page 385, July 25-28, 2004. .pdf Also, Technical Report MIT-LCS-TR-937, MIT CSAIL, Cambridge, MA, 2004.

Shlomi Dolev, Seth Gilbert, Nancy A. Lynch, Alex A. Shvartsman, and Jennifer L. Welch. GeoQuorums: Implementing Atomic Memory in Ad Hoc Networks. Technical Report MIT-LCS-TR-900a, CSAIL, Massachusetts Institute of Technology, Cambridge, MA, 2004. .pdf

Rui Fan, Indraneel Chakraborty, and Nancy Lynch. Clock Synchronization for Wireless Networks. In Teruo Higashino, editor, Principles of Distributed Systems: OPODIS 2004: 8th International Conference on Principles of Distributed Systems, Grenoble, France, December 15-17, 2004, volume 3544 of Lecture Notes in Computer Science, pages 400-414, 2005. Springer. .pdf

Chryssis Georgiou, Peter M. Musial, and Alexander A. Shvartsman. Long-Lived Rambo: Trading Knowledge for Communication. Rastislav Kralovic, Ondrej Sykora (Eds.): Structural Information and Communication Complexity, 11th International Colloquium, SIROCCO 2004, Smolenice Castle, Slowakia, June 21-23, 2004, volume 3104 of Lecture Notes in Computer Science, pages 185-196, Springer 2004. .pdf

Chryssis Georgiou, Peter M. Musial, and Alexander A. Shvartsman. Long-Lived Rambo: Trading Knowledge for Communication. Technical Report MIT-LCS-TR-943, MIT CSAIL, Cambridge, MA, April 2004. .pdf

Rui Fan and Nancy Lynch. Gradient Clock Synchronization. Proceedings of the Twenty-Third Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC 2004)), St. John's, Newfoundland, Canada, pages 320-327, July 25-58, 2004. Best Student Paper Award. .pdf

Rui Fan, Indraneel Chakraborty, and Nancy Lynch. Clock Synchronization for Wireless Networks. In Teruo Higashino, editor, Principles of Distributed Systems: OPODIS 2004: 8th International Conference on Principles of Distributed Systems, Grenoble, France, December 15-17, 2004, volume 3544 of Lecture Notes in Computer Science, pages 400-414, 2005. Springer. .pdf

Stephen Garland, Nancy Lynch, Joshua Tauber, and Mandana Vaziri. IOA User Guide and Reference Manual. Technical Report MIT-LCS-TR-961, MIT CSAIL, July 2004.

Ch. Georgiou, A. Russell and A. Shvartsman. The Complexity of Synchronous Iterative Do-All with Crashes. Distributed Computing, 17(1):47-63, 2004. .pdf

Chryssis Georgiou, Panayiotis Mavrommatis and Joshua A. Tauber. Implementing Asynchronous Distributed Systems Using the IOA Toolkit. MIT CSAIL Technical Report MIT-LCS-TR-966, Cambridge, MA, November 2004. .pdf

Seth Gilbert and Gregory Malewicz. The Quorum Deployment Problem. In Teruo Higashino, editor, OPODIS 2004: 8th International Conference on Principles of Distributed Systems, Grenoble, France, December 15-17, 2004, volume 3544 of Lecture Notes in Computer Science, pages 316-333, 2004. Springer. .pdf Also, full version in MIT CSAIL Technical Report MIT-LCS-TR-972, October 2004. .pdf

Seth Gilbert, Nancy Lynch, and Alex Shvartsman. RAMBO II: Implementing atomic memory in dynamic networks, using an aggressive reconfiguration strategy. Technical Report MIT-CSAIL-TR-890, CSAIL, Massachusetts Institute Technology, Cambridge, MA, 2004. .pdf

Dilsun K. Kaynar, Nancy Lynch, Roberto Segala, and Frits Vaandrager. The Theory of Timed I/O Automata. Technical Report MIT-LCS-TR-917a, MIT Laboratory for Computer Science, Cambridge, MA, November, 2004. .pdf Revised version Synthesis Lectures on Computer Science, Morgan Claypool Publishers, November 2005.

Dilsun K. Kaynar and Nancy A. Lynch. Decomposing Verification of Timed I/O Automata. Formal Techniques, Modelling and Analysis of Timed and Fault Tolerant Systems: Joint International Conferences on Formal Modeling and Analysis of Timed Systems, FORMATS 2004, and Format Technicques in Real-Time and Fault-Tolerant Systems, FTRTFT 2004, Grenoble, France, September 22-24, 2004, volume 3253 of Lecture Notes in Computer Science, pages 84-101, Springer-Verlag, 2004. .pdf Also, on the Springer website.

Dilsun Kaynar, Nancy Lynch, and Sayan Mitra. Specifying and Proving Timing Properties with TIOA Tools. 25th IEEE International Real-Time Systems Symposium, Work in Progress Session (RTSS 2004 WIP), December 5-8 2004, Lisbon, Portugal. .pdf

Carl Livadas and Idit Keidar. Caching-Enhanced Scalable Reliable Multicast. International Conference on Dependable Systems and Networks (DSN), June-July 2004. .pdf

Nancy Lynch and Ion Stoica. MultiChord: A resilient namespace management algorithm. Technical Memo MIT-LCS-TR-936, CSAIL, Massachusetts Institute of Technology, Cambridge, MA 2004. .ps

Nancy Lynch, Roberto Segala, and Frits Vaandrager. Compositionality for Probabilistic Automata. Technical Report MIT-LCS-TR-907, Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA, November 2004. .ps

Catherine Matlon. A specification and verification of Intermittent Global Order Broadcast. Master of Engineering in Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA, May 2004. .pdf

Sayan Mitra and Myla Archer. Reusable PVS Proof Strategies for Proving Abstraction Properties of I/O Automata. STRATEGIES 2004, IJCAR Workshop on Strategies in Automated Deduction, Cork Ireland, July 2004. .pdf

Sayan Mitra and Jesse Rabek. Energy Efficient Connected Clusters for Mobile Ad Hoc Networks. MED-HOC-NET 2004, Third Annual Mediterranean Ad Hoc Networking Workshop, Bodrum, Turkey, June 2004. .ps

P.M. Musial and A.A. Shvartsman. Implementing a Reconfigurable Atomic Memory Service for Dynamic Networks. In Proceedings of the 18'th International Parallel and Distributed Processing Symposium (IPDPS'04) --- FTPDS WS, Santa Fe, New Mexico, pages 208-215, April, 2004. .pdf

Christine Margaret Robson. TIOA and UPPAAL. Masters of Engineering Thesis, MIT Department of Electrical Engineering and Computer Science, Cambridge, MA, May 2004. .ps

Toh Ne Win, Michael Ernst, Stephen Garland, Dilsun Kirli, and Nancy Lynch. Using simulated execution in verifying distributed algorithms. International Journal on Software Tools for Technology Transfer (STTT), 6(1):67-76, July 2004. .pdf

A. Russell and A. Shvartsman. Distributed Computation Meets Design Theory: Local Scheduling for Disconnected Cooperation. Current Trends in Theoretical Computer Science: The Challenge of the New Century, vol. 1: Algorithms and Complexity, pp. 315-336, World Scientific, 2004. .ps

Joshua A. Tauber and Nancy A. Lynch and Michael J. Tsai. Compiling IOA without Global Synchronization. Proceedings of the 3rd IEEE International Symposium on Network Computing and Applications (IEEE NCA04), Cambridge, MA, pages 121-130, August 2004. .pdf

Joshua A. Tauber and Stephen J. Garland. Definition and Expansion of Composite Automata in IOA. MIT CSAIL Technical Report MIT-LCS-TR-959, July 2004. .pdf

Mandana Vaziri, Joshua A. Tauber, Michael J. Tsai, and Nancy Lynch. Systematic Removal of Nondeterminism for Code Generation in I/O Automata. MIT CSAIL Technical Report MIT-LCS-TR-960, July 2004. .ps

2003

Paul C. Attie. On the Implementation Complexity of Specifications of Concurrent Programs. Distributed Computing (DISC 2003: 17th International Symposium on Distributed Computing, Sorrento, Italy, October 2003), volume 2848 of Lecture Notes in Computer Science, pages 151-165, Springer-Verlag, 2003. .pdf

Paul C. Attie and Nancy A. Lynch. Dynamic Input/Output Automata: a Formal Model for Dynamic Systems. Technical Report MIT-LCS-TR-902, MIT Laboratory for Computer Science, Cambridge, MA, 02139, July 2003 and Technical Report, College of Computer Science, Northeastern University, July 2003. Latest version is dated November 2003 .pdf

Omar Bakr. Performance Evaluation of Distributed Algorithms over the Internet. Master of Engineering in Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA, February 2003. .pdf

Murat Demirbas, Anish Arora, Tina Nolte, and Nancy Lynch. Stalk: A Self-Stabilizing Hierarchical Tracking Service for Sensor Networks Technical Report OSU-CISRC-4/03-TR19, Ohio State University, April 2003. .pdf

Shlomi Dolev, Seth Gilbert, Nancy Lynch, Alex Shvartsman, and Jennifer Welch. GeoQuorums: Implementing Atomic Memory in Ad Hoc Networks. In Faith Fich, editor, Distributed Computing (DISC 2003: 17th International Symposium on Distributed Computing, Sorrento, Italy, October, 2003), volume 2848 of Lecture Notes in Computer Science, pages 306-320, Springer-Verlag, 2003. .pdf

Shlomi Dolev, Seth Gilbert, Nancy Lynch, Alex Shvartsman, and Jennifer Welch. GeoQuorums: Implementing atomic memory in ad hoc networks. Technical Report MIT-LCS-TR-900, MIT Laboratory for Computer Science, Cambridge, MA, 02139, 2003. .ps

Rui Fan and Nancy Lynch. Efficient Replication of Large Data Objects. Distributed Computing (DISC 2003: 17th International Symposium on Distributed Computing, Sorrento, Italy, October, 2003), volume 2848 of Lecture Notes in Computer Science, pages 75-91, Springer-Verlag, 2003. .pdf

Rui Fan. Efficient Replication of Large Data Objects. Masters Thesis, MIT Department of Electrical Engineering and Computer Science, Cambridge, MA, February 2003. .pdf

Rui Fan and Nancy Lynch. Efficient replication of large data objects. Proceedings of the Twenty-Second Annual ACM Symposium on Principles of Distributed Computing, Boston, Massachusetts, page 335, July 2003. .pdf

Rui Fan and Sayan Mitra. General fault tolerant data structures. Manuscript, 2003.

Stephen J. Garland, Nancy A. Lynch, Joshua A. Tauber, and Mandana Vaziri. IOA User Guide and Reference Manual. MIT Computer Science and Artificial Intelligence Laboratory, Cambridge, Massachusetts, August 14, 2003. .pdf

Ch. Georgiou. Cooperative Distributed Computing in the Presence of Quantified Adversity. Ph.D. thesis, University of Connecticut, 2003. .ps

Ch. Georgiou, A. Russell and A. Shvartsman. Work-Competitive Scheduling for Cooperative Computing with Dynamic Groups. The Thirty-Fifth Annual ACM Symposium on Theory of Computing (STOC'2003), pages 251-258, San Diego, CA, June 2003. .pdf

Ch. Georgiou and A.A. Shvartsman. Cooperative Computing with Fragmentable and Mergeable Groups. Journal of Discrete Algorithms, volume 1 (2), pp. 211-235, 2003..ps

Seth Gilbert. RAMBO II: Rapidly Reconfigurable Atomic Memory for Dynamic Networks. Masters Thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA, August 2003. .ps

Seth Gilbert, Nancy Lynch, and Alex Shvartsman. RAMBO II: Rapidly Reconfigurable Atomic Memory for Dynamic Networks. Proceedings of the International Conference on Dependable Systems and Networks (DSN), San Francisco, CA, pages 259-268, June 22nd - 25th, 2003. .pdf

Vida Uyen Ha. Verification of an Attitude Control System. Bachelor of Science and Master of Engineering, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA, May 2003. .doc

Mohammad Taghi Hajiaghayi, Nicole Immorlica, and Vahab S. Mirrokni. Power optimization in fault-tolerant topology control algorithms for wireless multi-hop networks. MOBICOM 2003: Proceedings of the Ninth Annual ACM International Conference on Mobile Computing and Networking, pages 300-312, San Diego, CA, September 2003. .ps

Dilsun K. Kaynar, Nancy Lynch, Roberto Segala, and Frits Vaandrager. Timed I/O Automata: A Mathematical Framework for Modeling and Analyzing Real-Time Systems. RTSS 2003: The 24th IEEE International Real-Time Systems Symposium, Cancun, Mexico, pages 166-177, December, 2003. IEEE Computer Society. .ps (Full version available as Technical Report MIT/LCS/TR-917. .ps)

Dilsun K. Kaynar, Nancy Lynch, Roberto Segala, and Frits Vaandrager. The Theory of Timed I/O Automata. Technical Report MIT-LCS-TR-917, MIT Laboratory for Computer Science, Cambridge, MA, 2003. .ps

Idit Keidar and Sergio Rajsbaum. A Simple Proof of the Uniform Consensus Synchronous Lower Bound. Information Processing Letters (IPL), 85(1):47-52, January 2003. .pdf

Roger Khazan and Nancy Lynch. An Algorithm for an Intermittently Atomic Data Service Based on Group Communication. Proceedings of the International Workshop on Large-Scale Group Communication, Florence, Italy, pages 25-30, October 2003. .pdf

D. Kowalski, M. Momenzadeh, and A.A. Shvartsman. Emulating Shared-Memory Do-All Algorithms in Asynchronous Message-Passing Systems. In Marina Papatriantafilou and Phillippe Hunel,editors, Principles of Distributed Systems, 7th International Conference (OPODIS 2003), La Martinique, France, December 2003, volume 3144 of Lecture Notes in Computer Science, pages 210-222, 2004. Springer. .pdf

Carolos Livadas. Formally Modeling, Analyzing, and Designing Network Protocols---A Case Study on Retransmission-Based Reliable Multicast --Protocols. Ph.D Thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA, July 2003. .ps

Nancy Lynch. Some Perspectives on PODC. Distributed Computing, 16(1):71-74, 2003. .pdf

Nancy Lynch. Working with Mike on Distributed Computing Theory, 1978-1992.Proceedings of the Twenty-Second Annual ACM Symposium on Principles of Distributed Computing (PODC'03), page 11, Boston, MA, July 2003. .pdf

Nancy Lynch. Input/Output Automata: Basic, Timed, Hybrid, Probabilistic, Dynamic, ... In Roberto Amadio and Denis Lugiez, editors, CONCUR 2003 - Concurrency Theory, 14th International Conference on Concurrency Theory, Marseille, France, September, 2003, volume 2761 of Lecture Notes in Computer Science, pages 191-192, Springer-Verlag, 2003. .pdf

Nancy Lynch, Roberto Segala, and Frits Vaandrager. Compositionality for Probabilistic Automata. In Roberto Amadio and Denis Lugiez, editors, CONCUR 2003 - Concurrency Theory (14th International Conference on Concurrency Theory, Marseille, France, September, 2003), volume 2761 of Lecture Notes in Computer Science, pages 208-221, Springer-Verlag, 2003. .pdf

Nancy Lynch, Roberto Segala, and Frits Vaandrager. Hybrid I/O Automata. Information and Computation, 185(1):105-157, August 2003. Also, Technical Report MIT-LCS-TR-827d, MIT Laboratory for Computer Science, Cambridge, MA 02139, January 13, 2003.

G. Malewicz. Distributed Scheduling for Disconnected Cooperation. Ph.D. thesis, University of Connecticut, 2003. .pdf

Sayan Mitra, Yong Wang, Nancy Lynch, and Eric Feron. Safety Verification of Model Helicopter Controller using Hybrid Input/Output Automata. O. Maler, A. Pnueli, editors, Hybrid Systems: Computation and Control (6th International Workshop, HSCC'03, Prague, the Czech Republic April 3-5, 2003), volume 2623 of Lecture Notes in Computer Science, pages 343-358, Springer-Verlag, 2003..pdf

Sayan Mitra, Yong Wang, Nancy Lynch, and Eric Feron. Application of Hybrid I/O Automata in Safety Verification of Pitch Controller for Model Helicopter System. Technical Report MIT-LCS-TR-880, MIT Laboratory for Computer Science, Cambridge, MA 02139, January 2003. .pdf

Sayan Mitra and Myla Archer. Developing Strategies for Specialized Theorem Proving about Untimed, Timed, and Hybrid I/O Automata. In STRATA 2003, Design and Application of Strategies/Tactics in Higher Order Logics, Rome, Italy, September, 2003. .ps

M. Momenzadeh. Emulating Shared-Memory Do-All in Asynchronous Message Passing Systems. Masters thesis, University of Connecticut, 2003.

Toh Ne Win. Theorem-Proving Distributed Algorithms with Dynamic Analysis. Master of Engineering in Computer Science and Engineering, MIT Department of Electrical Engineering, Cambridge, MA, May 2003. .ps

Toh Ne Win, Michael D. Ernst, Stephen J. Garland, Dilsun K. Kaynar, and Nancy Lynch. Using simulated execution in verifying distributed algorithms. In L.D. Zuck, P.C. Attie, A. Cortesi, S. Mukhopadhyay, editors, Verification, Model Checking, and Abstract Interpretation, Proceedings of 4th International Conference, (VMCAI 2003), New York, NY, USA, January 9-11, 2003, volume 2575 of Lecture Notes in Computer Science, pages 283-297, Springer-Verlag, 2003. .ps

Edward Solovey. Simulation of Composite I/O Automata. Masters of Engineering Thesis, MIT Department of Electrical Engineering and Computer Science, Cambridge, MA, August 2003. .ps

2002

P. C. Attie. Wait-free Byzantine Consensus. Information Processing Letters, vol. 83, no. 4, pp. 221-227, August 2002. .pdf

Paul Attie, Nancy Lynch, and Sergio Rajsbaum. Boosting Fault-Tolerance in Asynchronous Message Passing Systems is Impossible. Technical Report MIT-LCS-TR-877, MIT Laboratory for Computer Science, Cambridge, MA, December 2002. .pdf

Mohsen Bahramgiri, Mohammad Taghi Hajiaghayi, and Vahab S. Mirrokni. Fault-tolerant and 3-Dimensional distributed topology control algorithms in wireless multi-hop networks. Proceedings of the 11th IEEE International Conference on Computer Communications and Networks (IC3N), pages 392-398, October 14-16, 2002, Miami, Floria. .pdf Also, MIT Technical Report MIT-LCS-TR-862, Cambridge, MA 02139, 2002.

Omar Bakr and Idit Keidar. Evaluating the Running Time of a Communication Round over the Internet. Proceedings of the 21st ACM Symposium on Principles of Distributed Computing (PODC '02), Monterey, CA, USA, pages 243-252, July 2002. .pdf

Ziv Bar-Joseph and Idit Keidar and Nancy Lynch. Early-Delivery Dynamic Atomic Broadcast. In D. Malkhi, editor, Distributed Computing (Proceedings of the 16th International Symposium on DIStributed Computing (DISC) October 2002, Toulouse, France), volume 2508 of Lecture Notes in Computer Science, pages 1-16, 2002. Springer-Verlag. .pdf

Ziv Bar-Joseph, Idit Keidar, and Nancy Lynch. Early-Delivery Dynamic Atomic Broadcast. Technical Report MIT-LCS-TR-840, MIT Laboratory for Computer Science, Cambridge, MA, April 2002. .pdf

Andrej Bogdanov, Stephen Garland, and Nancy A. Lynch. Mechanical Translation of I/O Automaton Specifications into First-Order Logic. In Doron Peled, Moshe Y. Vardi, editors, Formal Techniques for Networked and Distributed Systems - FORTE 2002 (Proceedings of the 22nd IFIP WG 6.1 International Conference, Houston, Texas, USA, November 11-14, 2002), volume 2529 of Lecture Notes in Computer Science, pages 364-368, Springer 2002. .pdf

Roberto De Prisco, Alan Fekete, Nancy Lynch, and Alex Shvartsman. A Dynamic Primary Configuration Group Communication Service. Technical Memo MIT-LCS-TR-873, MIT Laboratory for Computer Science, Cambridge, MA, November 2002. .pdf.

Matthias Fitzi, Daniel Gottesman, Martin Hirt, Thomas Holenstein, and Adam Smith. Detectable Byzantine Agreement Secure Against Faulty Majorities. In Proceedings of the Twenty-First ACM Symposium on Principles of Distributed Computing (PODC 2002), Monterey, CA, July, 2002. .pdf

Seth Gilbert and Nancy Lynch. Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services. SIGACT News, 33(2):58-51, June 2002. .ps

Dilsun Kirli Kaynar, Anna Chefter, Laura Dean, Stephen J. Garland, Nancy A. Lynch, Toh Ne Win, and Antonio Ramirez-Robredo. Simulating Nondeterministic Systems at Multiple Levels of Abstraction. In Tools Day held in conjunction with CONCUR'02, Brno, Czech Republic, August 2002. .pdf

Dilsun Kirli Kaynar, Anna Chefter, Laura Dean, Stephen Garland, Nancy Lynch, Toh Ne Win, and Antonio Ramirez-Robredo. The IOA Simulator. Technical Report MIT-LCS-TR-843, MIT Laboratory for Computer Science, Cambridge, MA, July 2002. pdf

Idit Keidar. Challenges in Evaluating Distributed Algorithms. FuDiCo 2002: Proceedings of the International Workshop on Future Directions in Distributed Computing (FuDiCo 2002), June 2002, Bertinoro, Italy. pdf

I. Keidar and K. Marzullo. The Need for Realistic Failure Models in Protocol Design. Position paper in the 4th International Survivability Workshop (ISW) 2001/2002, March 2002. .pdf

Idit Keidar, Roger Khazan, Nancy Lynch and Alex Shvartsman. An Inheritance-Based Technique for Building Simulation Proofs Incrementally. ACM Transactions on Software Engineering and Methodology (TOSEM), 11(1):63-91, January 2002. Conference version in ICSE, 2000, pages 478-487. .pdf

Idit Keidar and Roger Khazan. A virtually synchronous group multicast algorithm for WANs: Formal approach. SIAM Journal on Computing,32(1):78-130, 2002. .pdf

Roger Khazan. Formal Design and Analysis of a New Virtually Synchronous Group Communication Service for Wide Area Networks. Ph.D Thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA, May 2002.

Carolos Livadas and Nancy A. Lynch. A Formal Venture into Reliable Multicast Territory. In Doron Peled, Moshe Y. Vardi, editors, Formal Techniques for Networked and Distributed Systems - FORTE 2002 (Proceedings of the 22nd IFIP WG 6.1 International Conference, Houston, Texas, USA, November 11-14, 2002), volume 2529 of Lecture Notes in Computer Science, pages 146-161, Springer 2002. .pdf Also, full version as Technical Report MIT-LCS-TR-868, MIT Laboratory for Computer Science, Cambridge, MA, November 2002. .pdf

Carolos Livadas and Nancy A. Lynch. A Formal Venture into Reliable Multicast Territory. Technical Report MIT-LCS-TR-868, MIT Laboratory for Computer Science, Cambridge, MA, November 2002. .pdf

Carolos Livadas and Idit Keidar. The Case for Exploiting Packet Loss Locality in Multicast Loss Recovery. Technical Report MIT/LCS/TR-867, MIT Laboratory for Computer Science, Cambridge, MA, Oct. 2002. .pdf

Nancy Lynch, Dahlia Malkhi, David Ratajczak. Atomic Data Access in Content Addressable Networks. In P. Druschel, F. Kaashoek, and A. Rowstron, editors, Peer-to-Peer Systems (First International Workshop on Peer-to-Peer Computing, Cambridge, MA, March 2002), volume 2429 of Lecture Notes in Computer Science, pages 295-305, Springer, 2002. .pdf

Nancy Lynch and Alex Shvartsman. Communication and Data Sharing for Dynamic Distributed Systems. In A. Schiper, A.A. Shvartsman, H. Weatherspoon, B.Y. Zhao, editors, Future Directions in Distributed Computing: Research and Position Papers (FuDiCo 2002: Proceedings of the International Workshop on Future Directions in Distributed Computing, Bertinoro,Italy, June 2002), volume 2584 of Lecture Notes in Computer Science, pages 62-67, Springer-Verlag, 2003. .pdf

Nancy Lynch and Alex Shvartsman. RAMBO: A Reconfigurable Atomic Memory Service for Dynamic Networks. In D. Malkhi, editor, Distributed Computing (Proceedings of the 16th International Symposium on DIStributed Computing (DISC) October 2002, Toulouse, France), volume 2508 of Lecture Notes in Computer Science, pages 173-190, 2002. Springer-Verlag. .pdf Also, Technical Report MIT Laboratory for Computer Science, Technical Report MIT-LCS-TR-856, Cambridge, MA, 2002. .ps

Nancy Lynch and Alex Shvartsman. RAMBO: A Reconfigurable Atomic Memory Service for Dynamic Networks. Technical Report MIT-LCS-TR-856, MIT Laboratory for Computer Science, Cambridge, MA, 2002. .ps

Michael J. Tsai. Code Generation for the IOA Language. Master of Engineering Thesis, Massachusetts Institute of Technology, Cambridge, MA, June 2002. Abstract and .pdf

Yoshinobu Kawabe and Ken Mano. Verifying the Nepi network programming system with IOA-Toolkit. Proceedings of the 9th Workshop on Foundations of Software Engineering (FOSE '02), 2002. In Japanese.

2001

P.C. Attie and E.A. Emerson. Synthesis of concurrent systems for an atomic read/write model of computation. ACM Transactions on Programming Languages and Systems, vol. 23, no. 2, pp. 187-242, March 2001. .pdf. Extended abstract appears in ACM Symposium on the Principles of Distributed Computing (PODC) 1996.

Paul C. Attie and Nancy A. Lynch. Dynamic Input/Output Automata: a Formal Model for Dynamic Systems. In K. G. Larsen and M. Nielsen, editors, CONCUR 2001 - Concurrency Theory: 12th International Conference on Concurrency Theory, Aaalborg, Denmark, August 20-25, 2001, Proceedings, volume 2154 of Lecture Notes in Computer Science, pages 137-151, 2001. Springer-Verlag. .pdf

Paul C. Attie and Nancy A. Lynch. Brief Announcement: Dynamic Input/Output Automata: a Formal Model for Dynamic Systems. Proceedings of the Twentieth ACM Annual Symposium on Principles of Distributed Computing, Newport, RI, pages 314-316, 2001. .pdf

Andrej Bogdanov. Formal verification of simulations between I/O automata. Master of Engineering thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA, September 2001. pdf.

Elizabeth Borowsky, Eli Gafni, Nancy Lynch, and Sergio Rajsbaum. The BG Distributed Simulation Algorithm. Distributed Computing, 14(3):127-146, 2001. pdf.

Bogdan S. Chlebus, Roberto De Prisco, and Alex A. Shvartsman. Performing tasks on synchronous restartable message-passing processors. Distributed Computing, 14:49-64, 2001. .pdf

Gregory V. Chockler, Idit Keidar, and Roman Vitenberg. Group Communication Specifications: A Comprehensive Study. ACM Computing Surveys, 33(4):1-43, December 2001. .pdf

Laura G. Dean. Improved Simulation of Input/Output Automata. Master of Engineering Thesis, Massachusetts Institute of Technology, Cambridge, MA, September 2001.

Alan Fekete and Idit Keidar: A Framework for Highly Available Services Based on Group Communication. IEEE International Workshop on Applied Reliable Group Communication (WARGC), pages 57-62, held in conjunction with ICDCS 2001, April 2001. .pdf

Alan Fekete, Nancy Lynch, and Alex Shvartsman. Specifying and Using a Partitionable Group Communication Service. ACM Transactions on Computer Systems, 19(2):171-216, May 2001. .pdf

Stephen J. Garland and Nancy A. Lynch and Mandana Vaziri. IOA: A Language for Specifying, Programming and Validating Distributed Systems. User and Reference Manual. Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA 02139, October 2001. .pdf

Kyle Ingols and Idit Keidar: Availability Study of Dynamic Voting Algorithms. 21st IEEE International Conference on Distributed Computing Systems (ICDCS), pages 247-254, April 2001. Previous version: MIT Technical Memorandum MIT-LCS-TM-611, November 2000. .pdf

Idit Keidar, Roger Khazan, Nancy Lynch, and Alex Shvartsman. An Inheritance-Based Technique for Building Simulation Proofs Incrementally. Proceedings of the 22nd International Conference on Software Engineering (ICSE,) Limerick, Ireland, pages 478-487, June 2000. .pdf.

Idit Keidar and Sergio Rajsbaum. On the Cost of Fault-Tolerant Consensus When There Are No Faults - A Tutorial. MIT Technical Report MIT-LCS-TR-821, May 24 2001. Preliminary version in SIGACT News 32(2), Distributed Computing column, pages 45-63, June 2001 (published in May 15th). .pdf. SIGACT News Archive Page

Idit Keidar. Group Communication. Manuscript, 2001. pdf

Carolos Livadas, Idit Keidar, and Nancy A. Lynch. Designing a Caching-Based Reliable Multicast Protocol. Proceedings of the International Conference on Dependable Systems and Networks (DSN'01), Fast Abstracts Supplement, pages B44-B45, Gothenburg, Sweden, July 2001. Abstract/Paper

Victor Luchangco. Memory Consistency Models for High Performance Distributed Computing. Ph.D Thesis, Massachusetts Institute of Technology, Cambridge, Massachusetts, September 2001.

Nancy Lynch, Roberto Segala, and Frits Vaandrager. Hybrid I/O Automata Revisited. In Maria Domenica Di Benedetto and Alberto Sangiovanni-Vincentelli, editors Hybrid Systems: Computation and Control. Fourth International Workshop (HSCC'01, Rome, Italy, March 2001, volume 2034 of Lecture Notes in Computer Science, pages 403-417, 2001. Springer-Verlag. .pdf. Long version is Technical Report MIT/LCS/TR-827, MIT Laboratory for Computer Science, July 2001.

Michael J. Tsai. Abstract Data Types (ADTs) for IOA Code Generation. Manuscript, September 2001.

2000

Tadashi Araragi, Paul Attie, Idit Keidar, Kiyoshi Kogure, Victor Luchangco, Nancy Lynch, and Ken Mano. On Formal Modeling of Agent Computations.In J.L. Rash, C.A. Rouff, W. Truszkowski, D. Gordon, M.G. Hinchey, editors, Formal Approaches to Agent-Based Systems (First International Workshop on Formal Approaches to Agent-Based System (FAABS 2000), Greenbelt, Maryland, April, 2000), volume 1871 of Lecture Notes in Artificial Intelligence, pages 48-62, Springer-Verlag, 2000.pdf,

Ziv Bar-Joseph, Idit Keidar, Tal Anker, and Nancy Lynch: Totally Ordered Multicast with Bounded Delays and Variable Rates. In Frank Butelle, editor, Proceedings of the 4th International Conference on Principles Of Distributed Systems (OPODIS), Paris France, pages 143-162, Studia Informatica Universalis series, December 2000. Suger, Saint-Denis, rue Catulienne. .pdf

Ziv Bar-Joseph, Idit Keidar, Tal Anker, and Nancy Lynch. QoS Preserving Totally Ordered Multicast. MIT Technical Report MIT-LCS-TR-796, January 2000. .pdf

Soma Chaudhuri, Maurice Herlihy, Nancy A. Lynch, and Mark R. Tuttle. Tight Bounds for k-Set Agreement. Journal of the ACM, pages 47(5):912-943, September, 2000. .pdf

G. Della-Libera and N. Shavit. Reactive Diffracting Trees. Journal of Parallel and Distributed Computing, 60(7):853-890, 2000. .pdf A preliminary version appeared in Proc. of the 9th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), Newport, RI, pages 24-32, 1997.

Roberto DePrisco, Butler Lampson, and Nancy Lynch. Fundamental Study: Revisiting the PAXOS algorithm. Theoretical Computer Science, 243:35-91, 2000. Elsevier Science B.V. PDF

Buckhard Englert and Alexander A. Shvartsman. Graceful Quorum Reconfiguration in a Robust Emulation of Shared Memory. International Conference on Distributed Computer Systems (ICDCS'2000), pages 454-463, 2000. PDF

Stephen J. Garland and Nancy A. Lynch. Using I/O Automata for Developing Distributed Systems. In Gary T. Leavens and Murali Sitaraman, editors, Foundations of Component-Based Systems, pages 285-312, Cambridge University Press, 2000. .pdf

Chryssis Georgiou and Alex A. Shvartsman. Cooperative Computing with Fragmentable and Mergeable Groups. Technical Report MIT/LCS/TR-802, Laboratory for Computer Science, Massachusetts Institute of Technology, 2000. Postscript

Kyle W. Ingols. Availability Study of Dynamic Voting Algorithms. M.Eng. thesis, MIT Department of Electrical Engineering and Computer Science, Cambridge, MA, May 5, 2000. .pdf

Idit Keidar and Danny Dolev. Totally Ordered Broadcast in the Face of Network Partitions. Exploiting Group Communication for Replication in Partitionable Networks. Chapter 3 of Dependable Network Computing, D. Avresky Editor, pages 51-75, Kluwer Academic Publications, January 2000. .pdf

Idit Keidar and Roger Khazan. A Client-Server Approach to Virtually Synchronous Group Multicast: Specifications and Algorithms. IEEE 20th International Conference on Distributed Computing Systems (ICDCS), pages 344-355, Taipei, Taiwan, April 2000. .pdf

Idit Keidar, Roger Khazan, Nancy Lynch and Alex Shvartsman. An Inheritance-Based Technique for Building Simulation Proofs Incrementally. ACM Transactions on Software Engineering and Methodology (TOSEM), 11(1):1-29, January 2002. Conference version in ICSE, 2000, pages 478-487. Postscript

I. Keidar, J. Sussman, K. Marzullo, and D. Dolev. A Client-Server Oriented Algorithm for Virtually Synchronous Group Membership in WANs. IEEE 20th International Conference on Distributed Computing Systems (ICDCS), pages 356-365, Taipei, Taiwan, April 2000. .pdf.

Carolos Livadas, John Lygeros, and Nancy A. Lynch. High-Level Modeling and Analysis of TCAS. Proceedings of IEEE, Special Issue on Hybrid Systems: Theory & Applications, 88(7):926-948, July 2000. .pdf

John Lygeros and Nancy Lynch. Conditions for Safe Deceleration of Strings of Vehicles. California PATH Research Report UCB-ITS-PRR-2000-2, California PATH Program, Institute of Transportation Studies, University of California, Berkeley, January 2000. .pdf

Gregory Malewicz, Alexander Russell, and Alex Shvartsman. Distributed Cooperation in the Absence of Communication. Technical Report MIT-LCS-TR-804, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA. Postscript

Anna Pogosyants, Roberto Segala, and Nancy Lynch. Verification of the randomized consensus algorithm of Aspnes and Herlihy: a case study. Distributed Computing, 13(3):155-186, 2000. .pdf

J. Antonio Ramirez-Robredo. Paired Simulation of I/O Automata. Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA, September, 2000. .pdf

Igor Tarashchanskiy. Virtual Synchrony Semantics: Client-Server Implementation. Masters thesis. MIT Department of Electrical Engineering and Computer Science, Cambridge, MA, September, 2000. .pdf

1999

Tal Anker, Danny Dolev and Idit Keidar. Fault Tolerant Video-on-Demand Services. In the 19th International Conference on Distributed Computing Systems (ICDCS), pages 244-252. June 1999. .pdf

Oleg Cheiner and Alex Shvartsman. Implementing an eventually-serializable data service as a distributed system building block. In M. Mavronicolas, M. Merritt, and N. Shavit, editors, Networks in Distributed Computing, volume 45 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 43--72. American Mathematical Society, 1999. .ps

Roberto DePrisco. On Building Blocks for Distributed Systems. Ph.D thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA 02139, December 1999. .pdf

Roberto De Prisco, Alan Fekete, Nancy Lynch, and Alex Shvartsman. A Dynamic Primary Configuration Group Communication Service. In Prasad Jayanti, editor, Distributed Computing, Proceedings of DISC'99 - 13th International Symposium on Distributed Computing, Bratislava, Slovak Republic, September 1999, volume 1693 of Lecture Notes in Computer Science, pages 64-78, 1999. Springer-Verlag-Heidelberg. .pdf.

Shlomi Dolev and Roberto Segala and Alex Shvartsman. Dynamic Load Balancing with Group Communication 6th International Colloquium on Structural Information and Communication Complexity (SIROCCO'99). .pdf.

Alan Fekete, Nancy Lynch, and Alex Shvartsman. Specifying and Using a Partitionable Group Communication Service. Technical Memo MIT/LCS/TM-570b, MIT Laboratory for Computer Science, Cambridge, MA, June 1999. .pdf

Alan Fekete, David Gupta, Victor Luchangco, Nancy Lynch, and Alex Shvartsman. Eventually-Serializable Data Services. Theoretical Computer Science, 220(1):113--156, June 1999. Special Issue on Distributed Algorithms. pdf

Jason Hickey, Nancy Lynch, and Robbert van Renesse. Specifications and Proofs for Ensemble Layers. Fifth International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS '99), Amsterdam, the Netherlands, March 1999. Springer-Verlag. .pdf

Henrik Ejersbo Jensen. Abstraction-Based Verification of Distributed Systems. Ph.D thesis, Department of Computer Science, Institute for Electronic Systems, Aalborg University, Aalborg, Denmark, June 1999. R-99-5005. .pdf

Idit Keidar, Jeremy Sussman, Keith Marzullo and Danny Dolev. A Client-Server Oriented Algorithm for Virtually Synchronous Group Membership in WANs. MIT Technical Memorandum MIT-LCS-TM-593, June 1999. .pdf Also: University of California, San Diego, Technical Report CS99-623.

Idit Keidar and Roger Khazan. A Client-Server Approach to Virtually Synchronous Group Multicast: Specifications, Algorithms, and Proofs. MIT Technical Report MIT-LCS-TR-794, November 1999. .pdf

Carolos Livadas, John Lygeros, and Nancy A. Lynch. High-Level Modeling and Analysis of TCAS. Proceedings of the 20th IEEE Real-Time Systems Symposium, pages 115-125, Phoenix, Arizona, December, 1999. .pdf

Nancy Lynch. High-Level Modeling and Analysis of an Air-Traffic Management System. In Frits W. Vaandrager and Jan H. van Schuppen, editors, Hybrid Systems: Computation and Control, Second International Workshop, HSCC'99, Berg en Dal, The Netherlands, March 29-31, 1999, volume 1569 of Lecture Notes in Computer Science, page 3, 1999. Springer. Invited talk. .pdf

Nancy Lynch I/O Automaton Models and Proofs for Shared-Key Communication Systems Technical Report MIT/LCS/TR-789, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, August, 1999. .pdf

Nancy Lynch. I/O Automaton Models and Proofs for Shared-Key Communication Systems Proceedings of the 12th IEEE Computer Security Foundations Workshop (CSFW'99), Mordana, Italy, June 28-30, 1999. .pdf.

Nancy Lynch, Nir Shavit, Alex Shvartsman, and Dan Touitou. Timing conditions for linearizability in uniform counting networks. Theoretical Computer Science, 220(1):67--91, June 1999. Special Issue on Distributed Algorithms. .pdf.

Jeremy Sussman, Idit Keidar and Keith Marzullo. Optimistic Virtual Synchrony. MIT Technical Report MIT-LCS-TR-792, November 1999. .pdf

Roman Vitenberg, Idit Keidar, Gregory V. Chockler and Danny Dolev. Group Communication Specifications: A Comprehensive Study. MIT Technical Report MIT-LCS-TR-790, September 1999. .pdf

Daniel Yates, Nancy Lynch, Victor Luchangco, and Margo Seltzer. I/O Automaton Model of Operating System Primitives Bachelors Thesis, Harvard University, May 1999. .pdf

1998

Soma Chaudhuri, Maurice Herlihy, Nancy A. Lynch, and Mark R. Tuttle. Tight bounds for k-set agreement Technical Report 98/4, Digital Equipment Corporation, Cambridge Research Lab, Cambridge, MA 02139, May, 1998..ps

Anna E. Chefter. A Simulator for the IOA Language Master of Engineering and Bachelor of Science in Computer Science and Engineering Massachusetts Institute of Technology, Cambridge, MA, May 1998. .pdf

Oleg Cheiner and Alex A. Shvartsman. Implementation of an eventually serializable data service. In Proceedings of the 17th Annual ACM Symposium on the Principles of Distributed Computing, Puerta Vallarta, Mexico, June 1998. (Short paper). .ps

Roberto De Prisco, Alan Fekete, Nancy Lynch, and Alex Shvartsman Dynamic View-Oriented Group Communication Service. In Proceedings of the 17th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC'98), Puerto Vallarta, June-July, 1998. .pdf

Ekaterina Dolginova. Safety verification of automated car maneuvers. Master of Engineering, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA 02139, May 1998. Postscript.

Shlomi Dolev, Roberto Segala, and Alex Shvartsman. Dynamic load balancing with group communication. Technical Memo MIT/LCS/TM-588, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, 1998. .ps

Alan Fekete, Frans Kaashoek and Nancy Lynch. Implementing Sequentially-Consistent Shared Objects Using Group and Point-to-Point Communication . Journal of the ACM, 45(1):35-69, January, 1998. .ps

Matteo Frigo and Victor Luchangco. Computation-centric memory models. In ACM Symposium on Parallel Algorithms and Architectures (SPAA'98), pages 240--249, Puerto Vallarta, Mexico, June-July 1998. .pdf

Stephen J. Garland and Nancy A. Lynch. The IOA Language and Toolset: Support for Designing, Analyzing, and Building Distributed Systems. Technical Report MIT/LCS/TR-762, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, August 1998 (original version: September 25, 1997). .pdf

Stephen J. Garland and Nancy A. Lynch. The IOA language and toolset: Support for mathematics-based distributed programming, 1998. Manuscript.

Henrik Jensen and Nancy Lynch. A proof of Burns N-Process mutual exclusion algorithm using abstraction. In Bernhard Steffen, editor, Tools and Algorithms for the Construction and Analysis of Systems (TACAS'98, Lisbon, Portugal, April 1998), volume 1384 of Lecture Notes in Computer Science, pages 409--423. Springer, 1998. .pdf

Roger Khazan. Group Communication as a Base for a Load-Balancing Replicated Data Service. Masters thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA 02139, May 1998. .pdf

Roger Khazan, Alan Fekete, and Nancy Lynch. Multicast Group Communication as a Base for a Load-Balancing Replicated Data Service. In Shay Kutten, editor, Distributed Computing, 12th International Symposium (DISC 1998), Andros, Greece, September 1998, volume 1499 of Lecture Notes in Computer Science, pages 258-272, 1998. Springer. .pdf

Carolos Livadas and Nancy A. Lynch. Formal Verification of Safety-Critical Hybrid Systems. In S. Sastry and T.A. Henzinger, editors, Hybrid Systems: Computation and Control (First International Workshop, HSCC'98, Berkeley, CA, USA, April, 1998), number 1386 in Lecture Notes in Computer Science, pages 253--272. Springer Verlag, 1998. .pdf(Complete version in Masters Thesis and Technical Report MIT-LCS-TR-730.)

John Lygeros and Nancy Lynch. Strings of vehicles: Modeling and safety conditions. In S. Sastry and T.A. Henzinger, editors, Hybrid Systems: Computation and Control (First International Workshop, HSCC'98, Berkeley, CA, USA, April, 1998), number 1386 in Lecture Notes in Computer Science, pages 273--288. Springer Verlag, 1998. Postscript

Dahlia Malkhi, Mike Reiter, and Nancy Lynch. A correctness condition for memory shared by Byzantine processes, 1998. Manuscript.

Roberto Segala, Rainer Gawlick, Jorgen Sogaard-Andersen, and Nancy Lynch. Liveness in timed and untimed systems. Information and Computation, 141(2):119--171, March 1998. .pdf

Roberto Segala. Hybrid I/O automata for the compositional analysis of hybrid systems. In Book of Abstracts of the conference of Mathematical Theory for Networks and Systems (MTNS), Padova, Italy, July 1998.

Nir Shavit and Asaph Zemach. Combining funnels: A new twist on an old tale. In Proceedings of the 17th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, pages 61--70, Puerto Vallarta, Mexico, June-July 1998. .pdf

N. Shavit, E. Upfal, and A. Zemach. A steady state analysis of diffracting trees. Theory of Computing Systems (formerly Mathematical Systems Theory), 31(4):403--423, July/August 1998. Special issue: ACM Symposium on Parallel Algorithms and Architectures. .pdf

Mark Smith. Reliable message delivery and conditionally-fast transactions are not possible without accurate clocks. In Proceedings of the 17th Annual ACM Symposium on the Principles of Distributed Computing, pages 163--171, Puerto Vallarta, Mexico, June 1998. .pdf

Mandana Vaziri and Gerard Holzmann. Automatic generation of invariants in spin. In 4th International Workshop on SPIN, pages 129--139, Paris, France, November 1998. pdf

Mandana Vaziri. Translating IOA to Promela, September 1998. Manuscript.

Mandana Vaziri, Nancy Lynch, and Jeannette Wing. Proving correctness of a controller algorithm for the RAID level 5 system. Digest of papers from the Twenty-Eighth Annual International Symposium on Fault-Tolerant Computing, pages 16-25, Munich, Germany, June 1998. pdf

1997

Y. Afek, B. Awerbuch, E. Gafni, Y. Mansour, A. Rosen, and N. Shavit. Slide: the key to polynomial end-to-end communication. Journal of Algorithms, 22:158--186, 1997. .pdf

Elizabeth Borowsky, Eli Gafni, Nancy Lynch, and Sergio Rajsbaum. The BG Distributed Simulation Algorithm. Technical Memo MIT/LCS/TM-573, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA 02139, December, 1997. .pdf

Michael S. Branicky, Ekaterina Dolginova, and Nancy Lynch. A Toolbox for Proving and Maintaining Hybrid Specifications. In Panos J. Antsaklis et al, editor, Hybrid Systems IV (HS'96, Cornell University, Ithaca, NY, October 12-16, 1996), volume 1273 of Lecture Notes in Computer Science, pages 18-30. Springer-Verlag 1997. .pdf

Oleg Cheiner. Implementation and Evaluation of an Eventually-Serializable Data Service. Master of Engineering Thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, September 1997. .pdf

Bogdan Chlebus, Roberto De Prisco, and Alex Shvartsman. Performing Tasks on Restartable Message-Passing Processors. In Marios Mavronicolas and Philippas Tsigas, editors, Proceedings of 11th International Workshop on Distributed Algorithms (WDAG'97, Saarbrucken, Germany, September 1997), volume 1320 of Lecture Notes in Computer Science, pages 96-110. Springer-Verlag 1997. .pdf

Darren Cofer, John Maloney, Rosa Weber, George Pappas, Shankar Sastry, John Lygeros, and Nancy Lynch. Formal specification and analysis of the center-TRACON automation systems (CTAS). Final Report SST-C97-002, Honeywell Technology Center, September 30 1997. Prepared for Langley Research Center and NEXTOR: FAA Center of Excellence in Aviation Operations Research.

Giovanni Della Libera and Nir Shavit. Reactive diffracting trees. In Proceedings of the 9th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), Newport, Rhode Island, June 1997. .pdf

Roberto De Prisco, Butler Lampson, and Nancy Lynch. Revisiting the Paxos algorithm. In Marios Mavronicolas and Philippas Tsigas, editors, Proceedings of 11th International Workshop on Distributed Algorithms (WDAG'97, Saarbrucken, Germany, September 1997), volume 1320 of Lecture Notes in Computer Science, pages 111-125. Springer-Verlag 1997. .pdf

Roberto De Prisco. Revisiting the Paxos algorithm. Master of Science Thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, June 1997. Also, Technical Report MIT/LCS/TR-717, Laboratory for Computer Science, Massachusetts Institute of Technology. .ps

Danny Dolev and Nir Shavit. Bounded concurrent time stamping. SIAM Journal on Computing, 26(2):418--455, April 1997. .pdf

Ekaterina Dolginova and Nancy Lynch. Safety Verification for Automated Platoon Maneuvers: A Case Study. In International Workshop on Hybrid and Real-Time Systems (HART'97, Grenoble, France, March 26-28, 1997), volume 1201 of Lecture Notes in Computer Science, pages 154-170. Springer-Verlag 1997. .pdf

Alan Fekete, Nancy Lynch, and Alex Shvartsman. Specifying and Using a Partitionable Group Communication Service. Proceedings of the Sixteenth Annual ACM Symposium on Principles of Distributed Computing (PODC'97, Santa Barbara, CA), pages 53-62, August 1997. .pdf Also, Technical Memo MIT/LCS/TM-570, Laboratory for Computer Science, Massachusetts Institute of Technology, October 1997. .pdf

Datta N. Godbole and John Lygeros. Tools for Safety throughput analysis of automated highway systems. In Proceedings of the American Control Conference, Albuquerque, New Mexico, June 1997. 1997. .pdf

Gunnar Hoest and Nir Shavit. Towards a Topological Characterization of Asynchronous Complexity Proceedings of the Sixteenth Annual ACM Symposium on Principles of Distributed Computing, pages 199-208, Santa Barbara, CA, August 1997..pdf

Gunnar Hoest. Towards a topological characterization of complexity in asynchronous, distributed systems. Master's thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA 02139, September 1997. .pdf

Paris Christos Kanellakis, Alex Allister Shvartsman. Fault-Tolerant Parallel Computation. Kluwer Academic Publishers, Boston, MA, 1997. Information

Carolos Livadas. Formal Verification of Safety-Critical Hybrid Systems, Master of Engineering Thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, September 1997. Abstract/Thesis. Also, Technical Report MIT/LCS/TR-730, Laboratory for Computer Science, Massachusetts Institute of Technology, September 1997. .pdf

Victor Luchangco. Precedence-Based Memory Models. In Marios Mavronicolas and Philippas Tsigas, editors, Proceedings of 11th International Workshop on Distributed Algorithms (WDAG'97, Saarbrucken, Germany, September 1997), volume 1320 of Lecture Notes in Computer Science. Springer-Verlag 1997. .pdf

John Lygeros, Claire Tomlin, and Shankar Sastry. Multi objective hybrid controller synthesis. In International Workshop on Hybrid and Real-Time Systems (HART'97), Grenoble, France, March 1997. .pdf

John Lygeros, Claire Tomlin, and Shankar Sastry. Multi-objective hybrid controller synthesis. In 36th IEEE Conference on Decision and Control, San Diego, California, December 1997.

John Lygeros and Nancy Lynch. On the Formal Verification of the TCAS Conflict Resolution Algorithms. Proceedings of the 36th IEEE Conference on Decision and Control, San Diego, CA, December 1997. .pdf

Nancy Lynch and lex Shvartsman. Robust emulation of shared memory using dynamic quorum-acknowledged broadcasts. Twenty-Seventh Annual International Symposium on Fault-Tolerant Computing (FTCS'97), pages 272-281, Seattle, Washington, USA, June 1997. IEEE .pdf

George Pappas, Shankar Sastry, John Lygeros, and Nancy Lynch. Modeling, specification, and safety analysis of CTAS. Final report, University of California, September 30 1997. Prepared for Langley Research Center and NEXTOR: FAA Center of Excellence in Aviation Operations Research.

George Pappas, Claire Tomlin, John Lygeros, Datta Godbole, and Shankar Sastry. A next generation architecture for air traffic management systems. In Proceedings of the 36th IEEE Conference on Decision and Control, pages 2405-2410, San Diego, CA, December 1997. Extended abstract.

Anna Pogosyants, Roberto Segala, and Nancy Lynch. Verification of the Randomized Consensus Algorithm of Aspnes and Herlihy: a Case Study. In Marios Mavronicolas and Philippas Tsigas, editors, Proceedings of 11th International Workshop on Distributed Algorithms (WDAG'97, Saarbrucken, Germany, September 1997), volume 1320 of Lecture Notes in Computer Science, pages 111-125. Springer-Verlag 1997. .pdf Also, Technical Memo MIT/LCS/TM-555, Laboratory for Computer Science, Massachusetts Institute of Technology. .pdf

Roberto Segala. Compositional verification of randomized distributed algorithms. In COMPOS, 1997. Invited talk.

Roberto Segala. Quiescence, fairness, testing and the notion of implementation. Information and Computation, 130(2):194--210, November 1997. .pdf

Nir Shavit and Dan Touitou. Elimination Trees and the Construction of Pools and Stacks. Theory of Computing Systems (formerly Mathematical Systems Theory), volume 30, pages 645-670, 1997. .pdf

N. Shavit and D. Touitou. Software transactional memory. Distributed Computing, 10(2):99--116, February 1997. .pdf

Mark Smith. Formal Verification of TCP and T/TCP. Ph.D thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA 02139, September 1997. .pdf

Mandana Vaziri and Nancy Lynch. Proving correctness of a controller algorithm for the RAID level 5 system. Technical Memo MIT/LCS/TM-576, Laboratory for Computer Science, Massachusetts Institute of Technology, 545 Technology Square, Cambridge, MA 02139, December 1997. .ps

1996

S. Abiteboul, G. M. Kuper, H. G. Mairson, A. A. Shvartsman, and M. Y. Vardi. In memoriam: Paris C. Kanellakis, a technical obituary. ACM Computing Surveys, March 1996.

Hagit Attiya, Amir Herzberg, and Sergio Rajsbaum. Optimal clock synchronization under different delay assumptions. SIAM Journal on Computing, 25(2): 369-389, April 1996. .pdf

Baruch Awerbuch, Boaz Patt-Shamir, and George Varghese. Self-stabilizing end-to-end communication. Journal of High Speed Networks, 5(4):365--381, 1996.

Jonathan F. Buss, Paris C. Kanellakis, Prabhakar L. Ragde, and Alex A. Shvartsman. Parallel Algorithms with Processor Failures and Delays. Journal of Algorithms, Volume 10, pages 45-86, January 1996.

Giovanni Della-Libera. Dynamic Diffracting Trees. Master of Engineering Thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, July 1996. .pdf

Alan Fekete, David Gupta, Victor Luchangco, Nancy Lynch, and Alex Shvartsman. Eventually-serializable data services. In Proceedings of the Fifteenth Annual ACM Symposium on Principles of Distributed Computing, pages 300--309, Philadelphia, PA, May 1996. .pdf

H. Galeana-Sanchez and S. Rajsbaum. Cycle pancyclism in tournaments II. Graphs and Combinatorics, 12:9--16, 1996.

Rainer Gawlick, Charles Kalmanek, and K. G. Ramakrishnan. On-line routing for permanent virtual circuits. Computer Communications, 19:235--244, 1996.

Constance Heitmeyer and Nancy Lynch. Formal verification of real-time systems using timed automata. In Constance Heitmeyer and Dino Mandrioli, editors, Formal Methods for Real-Time Computing, Trends in Software, chapter 4, pages 83--106. John Wiley & Sons Ltd, April 1996.

Maurice Herlihy, Nir Shavit, and Orli Waarts. Linearizable counting networks. Distributed Computing, (9):193--203, 1996.

Gunter Leeb and Nancy Lynch. Proving Safety Properties of the Steam Boiler Controller. In Jean-Raymond Abrial, Egon Boerger, and Hans Langmaack, editors, Proceedings of Formal Methods for Industrial Applications: Specifying and Programming the Steam Boiler Control, volume 11654 of Lecture Notes in Computer Science, Springer-Verlag 1996. Abstract/.pdf

Nancy Lynch. Distributed Algorithms. Morgan Kaufmann Publishers, San Mateo, CA, 1996. (Summary/Tableof Contents/Ordering Information)

Nancy Lynch. A Three-Level Analysis of a Simple Acceleration Maneuver, with Uncertainties. Proceedings of the Third AMAST Workshop on Real-Time Systems, pages 1-22, Salt Lake City, Utah, March 1996. .pdf

Nancy Lynch. Modelling and verification of automated transit systems, using timed automata, invariants and simulations. In R. Alur, T. Henzinger, and E. Sontag, editors, Hybrid Systems III: Verification and Control (DIMACS/SYCON Workshop on Verification and Control of Hybrid Systems, New Brunswick, New Jersey, October 1995), volume 1066 of Lecture Notes in Computer Science, pages 449-463. Springer-Verlag 1996. Abstract/.pdf

Nancy Lynch and Sergio Rajsbaum. On the Borowsky-Gafni Simulation Algorithm. Proceedings of ISTCS 1996: The Fourth Israel Symposium on Theory of Computing and Systems, pages 4-15, Jerusalem, Israel, June 1996. Also, Proceedings of the Fifteenth Annual ACM Symposium on Principles of Distributed Computing, page 57, Philadelphia, PA, May 1996. Abstract/.pdf.

Nancy Lynch, Nir Shavit, Alex Shvartsman, and Dan Touitou. Counting networks are practically linearizable. In Proceedings of the Fifteenth Annual ACM Symposium on Principles of Distributed Computing, pages 280-289, Philadelphia, PA, May 1996. .pdf

Nancy Lynch, Roberto Segala, Frits Vaandrage and H. B. Weinberg. Hybrid I/O Automata. In R. Alur, T. Henzinger, and E. Sontag, editors, Hybrid Systems III: Verification and Control (DIMACS/SYCON Workshop on Verification and Control of Hybrid Systems, New Brunswick, New Jersey, October 1995), volume 1066 of Lecture Notes in Computer Science, pages 496-510. Springer-Verlag 1996. .pdf

Nancy Lynch and Frits Vaandrager. Forward and backward simulations -- Part II: Timing-Based systems. Information and Computation, 128(1):1-25, July 1996.Abstract/.pdf.

Nancy Lynch and Frits Vaandrager. Action Transducers and Timed Automata Formal Aspects of Computing, 8(5):499-538, 1996. .pdf

Tsvetomir P. Petrov, Anya Pogosyants, Victor Luchangco, Stephen J. Garland, and Nancy A. Lynch. Computer-Assisted Verification of an Algorithm for Concurrent Timestamps. In Reinhard Gotzhein and Jan Bredereke, editors, Formal Description Techniques IX: Theory, Applications, and Tools (FORTE/PSTV'96: Joint International Conference on Formal Description Techniques for Distributed Systems and Communication Protocols, and Protocol Specification, Testing, and Verification, Kaiserslautern, Germany, October 1996), pages 29--44. Chapman & Hall, 1996. .pdf

Nir Shavit and Dan Touitou. Sofware transactional memory. Technical Memo MIT/LCS/TM-675, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA 02139, 1996.

Nir Shavit and Asaph Zemach. Diffracting Trees. ACM Transactions on Computer Systems, 14(4):385-428, November 1996. .pdf

Nir Shavit, Eli Upfal, and Asaph Zemach. A Steady State Analysis of Diffracting Trees. Proceedings of the 8th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA'96, Padua, Italy), pages 33-41, June 1996. .pdf

Mark Smith. Formal verification of communication protocols. In 6th Annual MIT Student Workshop on Computing Technology, pages 30--1, 30--2, Salem, MA, August 1996.

Mark Smith. Formal verification of Communication Protocols. In Reinhard Gotzhein and Jan Bredereke, editors, Formal Description Techniques IX: Theory, Applications, and Tools (FORTE/PSTV'96): Joint International Conference on Formal Description Techniques for Distributed Systems and Communication Protocols, and Protocol Specification, Testing, and Verification, Kaiserslautern, Germany, October 1996, pages 129-144. Chapman & Hall, 1996. .pdf

George Varghese and Nancy A. Lynch. A tradeoff between safety and liveness for randomized coordinated attack. Information and Computation, 128(1):57--71, July 1996. .pdf

Mandana Vaziri. Proving correctness of a controller algorithm for the RAID level 5 system. Master's thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA 02139, August 1996. .pdf

H. B. Weinberg. Correctness of Vehicle Control Systems: A Case Study. Master of Science Thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, February 1996. Also, Technical Report MIT/LCS/TR-685, Laboratory for Computer Science, Massachusetts Institute of Technology. Abstract/.pdf

H. B. Weinberg and Nancy Lynch. Correctness of Vehicle Control Systems - A Case Study. Proceedings of the 17th IEEE Real-Time Systems Symposium, pages 62-72, Washington, D. C., December, 1996. Abstract/.pdf

H. B. Weinberg, Nancy Lynch, and Norman Delisle. Verification of Automated Vehicle Protection Systems. In R. Alur, T. Henzinger, and E. Sontag, editors, Hybrid Systems III: Verification and Control (DIMACS/SYCON Workshop on Verification and Control of Hybrid Systems, New Brunswick, New Jersey, October 1995), volume 1066 of Lecture Notes in Computer Science, pages 101-113. Springer-Verlag 1996. .pdf

1995

Hagit Attiya, Amotz Bar-Noy, and Danny Dolev. Sharing memory robustly in message-passing systems. Journal of the ACM, 42(1):124--142, January 1995.

Hagit Attiya and Sergio Rajsbaum. A combinatorial framework for wait-free computability. Technical Report 95/3, Digital Equipment Corporation, Cambridge Research Lab, Cambridge, MA 02139, March 1995.

Soma Chaudhuri, Maurice Herlihy, Nancy A. Lynch, and Mark R. Tuttle. A tight lower bound for processor coordination. In Donald S. Fussell and Miroslaw Malek, editors, Responsive Computer Systems: Steps Toward Fault-Tolerant Real-Time Systems, chapter 1, pages 1--18. Kluwer Academic Publishers, Boston, MA, 1995. Selected papers from the Second International Workshop on Responsive Computer Systems Lincoln, New Hampshire, September 28-30, 1993). .pdf

A. Charny, G. Leeb, and M. Clarke. Some observations on source behavior 5 of the traffic management specification. Research Report AF-TM-95-0976R1, Digital Equipment Corporation, Littleton, Massachusetts, August 1995. Presented at ATM Forum Traffic Management.

R. De Nicola and R. Segala. A process algebraic view of I/O automata. Theoretical Computer Science, 138:391--423, March 1995. Also, Rapporto Tecnico N. SI-92/05, Universita ``La Sapienza'', Rome.

Alan Fekete, Nancy Lynch, and William Weihl. Hybrid atomicity for nested transactions. Theoretical Computer Science B (Logic, semantics and theory of programming), 149(1):151--178, September 1995. Special issue of TCS devoted to ICDT '92. .pdf

Alan Fekete, Frans Kaashoek and Nancy Lynch. Implementing Sequentially-Consistent Shared Objects Using Group and Point-to-Point Communication . In the 15th International Conference on Distributed Computing Systems (ICDCS95), pages 439-449, Vancouver, Canada, May/June 1995, IEEE. Abstract/.pdf. Also, Technical Report MIT/LCS/TM-518, Laboratory for Computer Science, Massachusetts Institute of Technology, June 1995. Abstract/.pdf

H. Galeana-Sanchez and S. Rajsbaum. Cycle pancyclism in tournaments I. Graphs and Combinatorics, 11:233--243, 1995.

Rainer Gawlick. Admission Control and Routing: Theory and Practice Ph.D. Thesis, Department of Electrical Engineering and Computer Schence, Laboratory for Computer Science, Massachusetts Institute of Technology, June 1995. Also, Technical Report MIT/LCS/TR-679, Laboratory for Computer Science, Massachusetts Institute of Technology. .pdf

Rainer Gawlick, Charles Kalmanek, and K. G. Ramakrishnan. On-line routing for permanent virtual circuits. Proceedings of IEEE INFOCOM 95: Fourteenth Annual Joint Conference of the IEEE Computer and Communication Societies, pages 278-288, Boston, Massachusetts, April 1995.

Maurice Herlihy and Sergio Rajsbaum. Algebraic spans. In Proceedings of the Fourteenth Annual ACM Symposium on Principles of Distributed Computing, pages 90--99, Ottawa, Ontario, Canada, August 1995.

M. Herlihy, B. H. Lim, and N. Shavit. Scalable concurrent counting. ACM Transactions on Computer Systems, 13(4):343--364, 1995.

Paris Christos Kanellakis, Dimitrios Michailidis, and Alex A. Shvartsman. Controlling Memory Access in Efficient Fault-Tolerant Parallel Algorithms. Nordic Journal of Computing, Volume 2, pages 146-180, 1995.

John Kleinberg, Hagit Attiya and Nancy Lynch. Trade-offs between Message Delivery and Quiesce Times in Connection Management Protocols. Proceedings of the Third Israel Symposium on Theory of Computing and Systems, pages 258-267, Tel-Aviv, Israel, January 1995. .pdf

Victor Luchangco. Using Simulation Techniques to Prove Timing Properties. Master of Science Thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, June 1995. .pdf

Victor Luchangco, Ekrem Soylemez, Stephen Garland, and Nancy Lynch. Verifying timing properties of concurrent algorithms. In Dieter Hogrefe and Stefan Leue, editors, Formal Description Techniques VII: Proceedings of the 7th IFIP WG6.1 International Conference on Formal Description Techniques (FORTE'94, Berne, Switzerland, October 1994), pages 259--273. Chapman and Hall, 1995. forte94.pdf.

Nancy Lynch. Proving performance properties (even probabilistic ones). In Dieter Hogrefe and Stefan Leue, editors, Formal Description Techniques VII: Proceedings of the 7th IFIP WG6.1 International Conference on Formal Description Techniques (FORTE'94), pages 3--20. Chapman and Hall, 1995. Invited talk. .pdf.

Nancy Lynch. Simulation techniques for proving properties of real-time systems. In Sang H. Son, editor, Advances in Real-Time Systems, chapter 13, pages 299--332. Prentice Hall, Inc., Englewood Cliffs, NJ, 1995.

Nancy Lynch. Modelling and verification of automated transit systems, using timed automata, invariants and simulations. Technical Memo MIT/LCS/TM-545, Laboratory for Computer Science, Massachusetts Institute of Technology, December 1995. .pdf.

Nancy Lynch, Roberto Segala, Frits Vaandrager, and H. B. Weinberg. Hybrid I/O Automata. Technical Memo MIT/LCS/TM-544, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, December 1995.Abstract/.pdf

Nancy Lynch and Roberto Segala. A comparison of simulation techniques and algebraic techniques for verifying concurrent systems. Formal Aspects of Computing, 7(3):231--265, 1995. .pdf

Nancy Lynch and Frits Vaandrager. Action Transducers and Timed Automata Laboratory for Computer Science, Massachusetts Institute of Technology Technical Memo MIT/LCS/TM-480.c, July, 1995. .pdf

Nancy Lynch and Frits Vaandrager. Forward and backward simulations -- Part II: Timing-Based systems. Technical Memo MIT/LCS/TM-487.c., Laboratory for Computer Science, Massachusetts Institute of Technology, April 1995. .pdf

Nancy Lynch and Frits Vaandrager. Forward and backward simulations -- Part I: Untimed systems. Information and Computation, 121(2), pages 214-233, September 1995. Also, Technical Memo MIT/LCS/TM-486.b (with minor revisions), Laboratory for Computer Science, Massachusetts Institute of Technology. .pdf

Nancy Lynch and H.B. Weinberg. Proving Correctness of a Vehicle Maneuver: Deceleration In the Second European Workshop on Real-Time and Hybrid Systems, Grenoble, France, June 1995. .pdf

Yishay Mansour and Boaz Patt-Shamir. Many-to-one packet routing on grids. In Proceedings of the Twenty-Seventh Annual ACM Symposium on the Theory of Computing, pages 258--267, Las Vegas, Nevada, May/June 1995.

Anya Pogosyants. Formal Verification of Randomized Distributed Systems. Ph.D thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA 02139, 1995. (Not completed).

Anna Pogosyants and Roberto Segala. Formal Verification of Timed Properties for Randomized Distributed Algorithms. Proceedings of the Fourteenth Annual ACM Symposium on Principles of Distributed Computing, pages 174-183, Ottawa, Ontario, Canada, August 1995. .pdf

Yaron Riany, Nir Shavit, and Dan Touitou. Towards a practical snapshot algorithm. In Proceedings of ISTCS 1995: The Third Israel Symposium on the Theory of Computing Systems, pages 121--129, Tel-Aviv, Israel, January 1995. IEEE. Later version in Theoretical Computer Science, 269(1-2,):163-201, October 2001. .pdf

Roberto Segala. Modeling and Verification of Randomized Distributed Real-Time Systems. Ph.D. Thesis, Department of Electrical Engineering and Computer Schence, Massachusetts Institute of Technology, May 1995. Also, Technical Report MIT/LCS/TR-676, Laboratory for Computer Science, Massachusetts Institute of Technology. .pdf

Roberto Segala. A Compositional Trace-Based Semantics for Probabilistic Automata. In Insup Lee and Scott A. Smolka, editors, CONCUR'95: Concurrency Theory (6th International Conference, Philadelphia, Pennsylvania, August 1995), volume 962 of Lecture Notes in Computer Science, pages 234-248. Springer-Verlag 1995. Abstract/.pdf

Roberto Segala and Nancy Lynch. Probabilistic simulations for probabilistic processes. Nordic Journal of Computing, 2(2):250--273, August 1995. .pdf

Nir Shavit and Dan Touitou. Software transactional memory. Proceedings of the Fourteenth Annual ACM Symposium on Principles of Distributed Computing, pages 204--213, Ottawa, Ontario, Canada, August 1995. .pdf

Nir Shavit and Dan Touitou. Elimination Trees and the Construction of Pools and Stacks. (Preliminary version) Proceedings of 7th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA'95), Santa Barbara, California), pages 54-63, July 1995. .pdf

Alex Shvartsman. Integrating distributed multimedia systems and interactive television networks. In SPIE Conf. on Integration of Large Scale Media Delivery Systems, volume 2615, pages 142--153, Philadelphia, October 1995. .pdf

Alex A. Shvartsman and C. Strutt. A framework for distributed object management and generic applications. Manuscript.

1994

Yehuda Afek, Hagit Attiya, Alan Fekete, Michael Fischer, Nancy Lynch, Yishay Mansour, Da-Wei Wang, and Lenore Zuck. Reliable communication over unreliable channels. Journal of the ACM, 41(6):1267--1297, November 1994. .pdf

Sudhanshu Aggarwal. Time Optimal Self-Stabilizing Spanning Tree Algorithms. Technical Report MIT/LCS/TR-632, Laboratory for Computer Science, Massachusetts Institute of Technology, May 1994. Masters Thesis. Abstract/.pdf.

Sudhanshu Aggarwal, Juan Garay, and Amir Herberg. Adaptive video on demand (abstract). In Proceedings of the 13th Annual ACM Symposium on Principles of Distributed Computing, page 402, Los Angeles, CA, August 1994.

James Aspnes, Maurice Herlihy, and Nir Shavit. Counting Networks. Journal of ACM, 41(5):1020-1048, September 1994. .pdf

Hagit Attiya, Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. Bounds on the time to reach agreement in the presence of timing uncertainty. Journal of the ACM, 41(1):122--152, January 1994. .pdf

Hagit Attiya, Nancy Lynch, and Nir Shavit. Are wait-free algorithms fast? Journal of the ACM, 41(4):725--763, July 1994. .pdf

Hagit Attiya and Nancy A. Lynch. Time bounds for real-time process control in the presence of timing uncertainty. Information and Computation, 110(1):183--232, April 1994. .pdf

Hagit Attiya, Amir Herzberg, and Sergio Rajsbaum. Optimal clock synchronization under different delay assumptions. Technical Memo MIT/LCS/TM-504, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, April 1994. .pdf

Baruch Awerbuch, Lenore Cowen, and Mark Smith. Efficient Asynchronous Distributed Symmetry Breaking. Proceedings of the 26th Annual ACM Symposium on Theory of Computing, pages 214-223, May 1994. .pdf

Baruch Awerbuch, Rainer Gawlick, Tom Leighton, and Yuval Rabani. On-line admission control and circuit routing for high performance computation and communication. In 35th Annual Symposium on Foundations of Computer Science, pages 412--423, Santa Fe, New Mexico, November 1994. IEEE.

Baruch Awerbuch, Boaz Patt-Shamir, and George Varghese. Self-stabilization by local checking and global reset. In Proceedings of the 8th International Workshop on Distributed Algorithms (WDAG'94), volume 857 of Lecture Notes in Computer Science, pages 326--339, Terschelling, The Netherlands, September 1994.

Baruch Awerbuch, Boaz Patt-Shamir, and George Varghese. Bounding the unbounded. In Proceedings of the 13th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM '94), pages 776--783, Toronto, Ontario, June 1994.

Soma Chaudhuri and Mark Tuttle. Fast increment registers. In Proceedings of the Eighth International Workshop on Distributed Algorithms, Lecture Notes in Computer Science. Springer-Verlag, 1994.

Soma Chaudhuri and Jennifer Welch. Bounds on the costs of multivalued register implementations. SIAM Journal on Computing, 23(2):335--354, April 1994.

J. Garofalakis, S. Rajsbaum, P. Spirakis, and B. Tampakas. Tentative and definite distributed computations: An optimistic approach to network synchronization. Theoretical Computer Science, 128:63--74, 1994. Special Issue on Dependable Parallel Computing.

Rainer Gawlick, Roberto Segala, Joergen Soegaard-Andersen, and Nancy Lynch. Liveness in Timed and Untimed Systems. In Serge Abiteboul and Eli Shamir, editors, Proceedings of the 21st International Colloquim on Automata, Languages and Programming (ICALP'94, Jerusalem, Israel, July 1994), volume 820 of Lecture Notes in Computer Science, pages 166-177, Springer-Verlag 1994. .pdf

Michel Goemans, Nancy Lynch, and Isaac Saias. Upper and lower bounds on the number of faults a system can withstand without repairs. In Fourth International Working Conference on Dependable Computing for Critical Applications, pages 260--269, San Diego, CA, USA, January 1994. .pdf

Kenneth J. Goldman and Nancy Lynch. Quorum consensus in nested transaction systems. ACM Transactions on Database Systems, 19(4):537--585, December 1994. .pdf

Connie Heitmeyer and Nancy Lynch. The Generalized Railroad Crossing: A Case Study in Formal Verification of Real-Time System. Proceedings of the 15th IEEE Real-Time Systems Symposium, pages 120--131, San Juan, Puerto Rico, December 1994. IEEE Computer Society Press. .pdf Also, Technical Memo MIT/LCS/TM-511, Laboratory for Computer Science, Massachusetts Institute of Technology, November 1994. .pdf

Maurice Herlihy and Sergio Rajsbaum. Set consensus using arbitrary objects. In Thirteenth Annual ACM Symposium on the Principles of Distributed Computing, pages 324--333, Los Angeles, CA, August 1994.

Maurice Herlihy and Nir Shavit A Simple Constructive Computatability Theorem for Wait-Free Computation. Proceedings of the Twenty-sixth Annual ACM Symposium on Theory of Computing (STOC'94, Montreal, Quebec, Canada), pages 243-262, May 1994..pdf

Paris Christos Kanellakis, Alex Allister Shvartsman. Fault-Tolerance and Efficiency in Massively Parallel Algorithms.Kluwer Academic Publishers, Boston, MA, 1994.

Gunter Leeb. A user interface for homenet. IEEE Transactions on Consumer Electronics, 40(4):897 ff., November 1994.

Nancy Lynch. Simulation techniques for proving properties of real-time systems. In J. W. de Bakker, W. P. de Roever, and G. Rozenberg, editors, A Decade of Concurrency: Reflections and Perspectives (REX School/Symposium, Noordwijkerhout, The Netherlands, June 1993), volume 803 of Lecture Notes in Computer Science, pages 375--424. Springer-Verlag, 1994. .pdf

Nancy Lynch. Atomic Transactions for Multiprocessor Programming: A Formal Approach. In Guy E. Blelloch and K. Mani Chandy and Suresh Jagannathan, editors Specification of Parallel Algorithms: DIMACS Workshop, Discrete Mathematics and Theoretical Computer Science, volume 18 of Discrete Mathematics and Theoretical Computer Science, pages 125-142, Princeton, NJ, May 1994, American Mathematical Society. .pdf

Atomic Transactions. Morgan Kaufmann Publishers, 1994. Abstract/Table of Contents

Nancy Lynch, Isaac Saias, and Roberto Segala. Proving Time Bounds for Randomized Distributed Algorithms. Proceedings of the 13th Annual ACM Symposium on the Principles of Distributed Computing, pages 314--323, Los Angeles, CA, August 1994. .pdf.

Nancy Lynch and Frits Vaandrager. Forward and Backward Simulations --- Part I: Untimed Systems. MIT Technical Memo MIT/LCS/TM-486.b, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, August 1994. .pdf

Nancy Lynch and Frits Vaandrager. Action transducers and timed automata. Technical Memo MIT/LCS/TM-480b, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, 02139, October 1994. (Superseded by MIT-LCS-TM-480c) .pdf

Boaz Patt-Shamir. A Theory of Clock Synchronization. Ph.D thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA 02139, October 1994. Also, Technical Report MIT/LCS/TR-680, Laboratory for Computer Science, Massachusetts Institute of Technology. .pdf

Boaz Patt-Shamir and Sergio Rajsbaum. A theory of clock synchronization. In Proceedings of the Twenty-sixth Annual ACM Symposium on Theory of Computing, pages 810--819, Montreal, Canada, May 1994.

S. Rajsbaum and M. Sidi. On the performance of synchronized programs in distributed networks with random processing times and transmission delays. IEEE Transactions on Parallel and Distributed Systems, 5(9):939--950, September 1994.

Sergio Rajsbaum. Upper and lower bounds for stochastic marked graphs. Information Processing Letters, 49:291--295, 1994.

Alain Isaac Saias. Randomness versus Non-Determinism in Distributed Computing. Ph.D thesis, MIT Mathematics Department, October 1994. Also, Technical Report MIT/LCS/TR-651, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA. .pdf

Roberto Segala and Nancy Lynch. Probabilistic simulations for probabilistic processes. In Bengt Jonsson and Joachim Parrow, editors, 5th International Conference on Concurrency Theory (CONCUR'94, Uppsala, Sweden, August 1994), volume 836 of Lecture Notes in Computer Science, pages 481-496. Springer-Verlag 1994. Abstract/.pdf

Nir Shavit, and Asaph Zemach. Diffracting Trees. Proceedings of the Sixth Annual Symposium on Parallel Algorithms and Architectures (SPAA'94, Cape May, New Jersey), pages 167-176, June 1994.

Ekrem Soylemez. Automatic verification of the timing properties of MMT automata. Master's thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA 02139, February 1994. .pdf

1993

Yehuda Afek, Hagit Attiya, Danny Dolev, Eli Gafni, Michael Merritt, and Nir Shavit. Atomic snapshots of shared memory. Journal of the ACM, 40(4):873--890, September 1993.

Sudhanshu Aggarwal and Shay Kutten. Time optimal self stabilizing spanning tree algorithms. In R.K. Shyamasundar, editor, 13th International Conference on Foundations of Software Technology and Theoretical Computer Science, volume 761 of Lecture Notes in Computer Science, pages 400--410, Bombay, India., December 1993. Springer-Verlag.

James Aspnes, Maurice Herlihy, and Nir Shavit. Counting Networks. Technical Report CRL 93/11, Digital Equipment Corporation, Cambridge Research Lab, August 1993.

Hagit Attiya, Amir Herzberg, and Sergio Rajsbaum. Optimal clock synchronization under different delay assumptions. In Proceedings of the Twelfth Annual ACM Symposium on the Principles of Distributed Computing, pages 109--120, Ithaca, NY, August 1993.

Hagit Attiya, Soma Chaudhuri, Roy Friedman, and Jennifer Welch. Shared memory consistency conditions for non-sequential execution: Definitions and programming strategies. In 5th Annual ACM Symposium on Parallel Algorithms and Architectures, pages 241--250, July 1993. A detailed version appears as Technical Report LPCR 9302, Laboratory for Parallel Computing Research, Department of Computer Science, The Technion, 1993.

Baruch Awerbuch, Shay Kutten, Yishay Mansour, Boaz Patt-Shamir, and George Varghese. Time optimal self-stabilizing synchronization. In Proceedings of the Twenty-fifth Annual ACM Symposium on Theory of Computing, pages 652--661, May 1993.

James E. Burns and Nancy A. Lynch. Bounds on shared memory for mutual exclusion. Information and Computation, 107(2):171--184, December 1993. pdf

Soma Chaudhuri. More choices allow more faults: Set consensus problems in totally asynchronous systems. Information and Computation, 105(1):132--158, July 1993.

Soma Chaudhuri, Maurice Herlihy, Nancy A. Lynch, and Mark R. Tuttle. A tight lower bound for k-set agreement. In 34th Annual Symposium on Foundations of Computer Science, pages 206--215, Palo Alto, California, November 1993. IEEE. .pdf

Soma Chaudhuri, Rainer Gawlick, and Nancy Lynch. Designing algorithms for distributed systems with partially synchronized clocks. In Proceedings of the Twelfth Annual ACM Symposium on Principles of Distributed Computing, pages 121--132, Ithaca, New York, August 1993. .pdf

Ranjan Das and Alan Fekete. Modular reasoning about open systems: A case study of distributed commit. In Proceedings of Seventh International Workshop on Software Specification and Design, pages 30--39, Los Angeles, CA, December 1993.

Harish Devarajan, Alan Fekete, Nancy Lynch, and Liuba Shrira. Correctness proof for a network synchronizer. Technical Report MIT/LCS/TR-588, (Harish Devarajan Masters thesis). .pdf

Harish Devarajan. Correctness proof for a network synchronizer. Master's thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA 02139, May 1993. Also, Technical Report MIT/LCS/TR-588, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA 02139, December 1993. .pdf

Alan Fekete, Nancy Lynch, Yishay Mansour, and John Spinelli. The impossibility of implementing reliable communication in the face of crashes. Journal of the ACM, 40(5):1087--1107, November 1993. .pdf

Faith Fich, Maurice Herlihy, and Nir Shavit. On the complexity of randomized synchronization. In Proceedings of the Twelth Annual ACM Symposium on Principles of Distributed Systems, Ithaca, NY, August 1993.

Rainer Gawlick, Roberto Segala, J\orgen S\ogaard-Andersen, and Nancy Lynch. Liveness in timed and untimed systems. Technical Report MIT/LCS/TR-587, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, 02139, December 1993. .pdf

Maurice P. Herlihy and Nir Shavit. The asynchronous computability theorem for t-resilient tasks. In Proceedings of the Twenty-fifth Annual ACM Symposium on Theory of Computing, pages 111--120, San Diego, California, May 1993.

Shay Kutten, Rafail Ostrovsky, and Boaz Patt-Shamir. The Las-Vegas processor identity problem (how and when to be unique). In Proceedings of the Second Israel Symposium on Theory of Computing and Systems, June 1993.

Butler W. Lampson, Nancy A. Lynch, and Joergen F. Soegaard-Andersen. Correctness of at-most-once message delivery protocols. In Richard L. Tenney, Paul D. Amer, and M. Umit Uyar, editors, Formal Description Techniques, VI (Proceedings of the IFIP TC6/WG6.1 Sixth International Conference on Formal Description Techniques --- FORTE'93, Boston, MA, October 1993), pages 385--400. North-Holland, 1994. .ps

Nancy Lynch. Simulation techniques for proving properties of real-time systems. Technical Memo MIT/LCS/TM-494, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, November 1993. .pdf

Nancy Lynch and Frits Vaandrager. Forward and backward simulations --- Part II: Timing-based systems. Technical Memo MIT/LCS/TM-487b, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA 02139, April 1993. .pdf (Note: Later version in MIT-LCS-TM-487c, 1995. .pdf)

Nancy Lynch and Boaz Patt-Shamir. Distributed algorithms. MIT/LCS/RSS 20, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA 02139, 1993. Lecture notes for 6.852.

Nancy Lynch and Frits Vaandrager. Forward and backward simulations --- Part I: Untimed systems. Technical Memo MIT/LCS/TM-486, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, 02139, May 1993. .pdf

Nancy Lynch and Roberto Segala. A comparison of simulation techniques and algebraic techniques for verifying concurrent systems. Technical Memo MIT/LCS/TM-499, Laboratory for Computer Science, Massachusetts Institute Technology, December 1993. .pdf

Nancy Lynch and Roberto Segala. A comparison between simulation techniques and algebraic techniques for verifying concurrent systems. In NAPAW Proceedings of the North American Process Algebra Workshop, Department of Computer Science, Cornell University, Ithaca, NY, August 1993. .pdf

Yishay Mansour and Boaz Patt-Shamir. Greedy packet scheduling on shortest paths. Journal of Algorithms, 14(3):449--465, March 1993.

Boaz Patt-Shamir and David Peleg. Time-space tradeoffs for set operations. Theoretical Computer Science, 110:99--129, 1993.

Roberto Segala. Quiescence, fairness, testing and the notion of implementation. In Eike Best, editor, Proceedings of 4th International Conference on Concurrency Theory (CONCUR'93, Hildesheim, Germany, August 1993), volume 715 of Lecture Notes in Computer Science, pages 324-338. Springer-Verlag 1993. .pdf

Mark A. Smith. Fast wait-free symmetry breaking in distributed systems. Master's thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA 02139, May 1993. .pdf

Joergen Sogaard-Andersen, Nancy A. Lynch, and Butler Lampson. Correctness of communication protocols: A case study.s Technical Memo MIT/LCS/TR-589, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, 02139, November 1993. Abstract/.pdf

Joergen F. Soegaard-Andersen, Stephen J. Garland, John V. Guttag, Nancy A. Lynch, and Anna Pogosyants. Computer-Assisted Simulation Proofs. In Costas Courcoubetis, editor, Computer-Aided Verification: 5th International Conference, (CAV'93, Elounda, Greece, June/July 1993), volume 697 of Lecture Notes in Computer Science, pages 305-319. Springer-Verlag 1993. .pdf.

Joergen Soegaard-Andersen, Nancy Lynch, and Butler Lampson. Correctness of communication protocols: A case study. Technical Report MIT/LCS/TR-589, Laboratory for Computer Science, Massachusetts Institute Technology, November 1993. .pdf.

George Varghese. Self-stabilization by local checking and correction. Technical Report MIT/LCS/TR-583, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA 02139, October 1993. .pdf

Jennifer Welch and Nancy Lynch. A modular Drinking Philosophers algorithm. Distributed Computing, 6(4):233--244, July 1993. .pdf

1992

Yehuda Afek, Hagit Attiya, Alan Fekete, Michael Fischer, Nancy Lynch, Yishay Mansour, Da-Wei Wang, and Lenore Zuck. Reliable communication over unreliable channels. Technical Memo MIT/LCS/TM-447, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, 02139, October 1992. .pdf

L. Aceto, B. Bloom, and F.W. Vaandrager. Turning SOS rules into equations. In Proceedings of the 7th Annual Symposium on Logic in Computer Science, 1992.

Hagit Attiya, Cynthia Dwork, Nancy A. Lynch, and Larry J. Stockmeyer. Bounds on the time to reach agreement in the presence of timing uncertainty. Technical Memo MIT/LCS/TM-435.b, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA 02139, November 1992.

Baruch Awerbuch, Boaz Patt-Shamir, David Peleg, and Michael Saks. Adapting to asynchronous dynamic networks with polylogarithmic overhead. In Proceedings of the Twenty-fourth Annual ACM Symposium on Theory of Computing, pages 557--570, Victoria, British Columbia, May 1992.

Soma Chaudhuri. More choices allow more faults: Set consensus problems in totally asynchronous systems. Technical Memo MIT/LCS/TM-475, Laboratory for Computer Science, Massachusetts Institute of of Technology, November 1992. .pdf

Ranjan Das. A formalization of distributed commit in data-processing systems. Bachelors Thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA 02139, June 1992.

Alan Fekete, Nancy Lynch, and William Weihl. Hybrid atomicity for nested transactions. In Database Theory - ICDT'92, Fourth International Conference, volume 646 of Lecture Notes in Computer Science, pages 216--230, Berlin, Germany, October 1992. Springer-Verlag. .pdf

Alan Fekete, Nancy Lynch, Yishay Mansour, and John Spinelli. The impossibility of implementing reliable communication in the face of crashes. Technical Memo MIT/LCS/TM-355.d, Massachusetts Institute of Technology, Laboratory for Computer Science, Cambridge, MA 02139, April 1992. .pdf

Alan Fekete, Nancy Lynch, and William Weihl. Hybrid atomicity for nested transactions. Technical Memo MIT/LCS/TM-476, Laboratory for Computer Science, Massachusetts Institute of Technology, October 1992. .pdf

Michael J. Fischer, Leoindas Guibas, Nancy D. Griffeth, and Nancy A. Lynch. Optimal placement of identical resources in a tree. Information and Computation, 91(1), January 1992. .pdf

Rainer Gawlick. Bounded concurrent time-stamping made simple. Master's thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, June 1992. Also, Technical Report MIT/LCS/TR-556, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA 02139, October 1992. .pdf

Rainer Gawlick, Nancy Lynch, and Nir Shavit. Concurrent time-stamping made simple. In D. Dolev, Z. Galil, and M. Rodeh, editors, Theory of Computing and Systems (ISTCS'92, Israel Symposium, Haifa, Israel, May 1992), volume 601 of Lecture Notes in Computer Science, pages 171--185. Springer-Verlag, 1992. (Later version) .pdf

Maurice Herlihy, Nancy Lynch, Michael Merritt, and William Weihl. On the correctness of orphan management algorithms. Journal of the ACM, 39(4):881--930, October 1992. .pdf

Butler Lampson, Nancy Lynch, and Joergen Soegaard-Andersen. At-most-once message delivery: A case study in algorithm verification. In W. R. Cleaveland, editor, CONCUR'92 (Third International Conference on Concurrency Theory, Stony Brook, NY, USA, August 1992), volume 630 of Lecture Notes in Computer Science, pages 317--324. Springer-Verlag, 1992. Invited talk. .pdf

Nancy Lynch and Nir Shavit. Timing-based mutual exclusion. In Proceedings of the Real-Time Systems Symposium, pages 2--11, Phoenix, Arizona, December 1992. IEEE. .pdf

Nancy Lynch and Hagit Attiya. Using mappings to prove timing properties. Technical Memo MIT/LCS/TM-412.e, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, 02139, April 1992. .pdf

Nancy Lynch and Isaac Saias. Distributed Algorithms. Fall 1990 Lecture Notes for 6.852. MIT/LCS/RSS 16, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA 02139, February 1992. .pdf

Nancy A. Lynch and Hagit Attiya. Using mappings to prove timing properties. Distributed Computing, 6(2):121--139, September 1992. .pdf

Nancy Lynch and Frits Vaandrager. Forward and backward simulations for timing-based systems. In J. W. de Bakker, W. P. de Roever, C. Huizing, and G. Rozenberg, editors, Proceedings of Real-Time: Theory in Practice (REX Workshop, Mook, The Netherlands, June 1991), volume 600 of Lecture Notes in Computer Science, pages 397-446. Springer-Verlag 1992. .pdf

S. Ponzio and R. Strong. Semisynchrony and real time. In Proceedings of the Sixth International Workshop on Distributed Algorithms (WDAG), Lecture Notes in Computer Science, Haifa, Israel, November 1992. Springer-Verlag.

Stephen Ponzio. Bounds on the time to detect failures using bounded-capacity message links. In Proceedings of the Real-time Systems Symposium, pages 236--245, Phoenix, Arizona, December 1992. IEEE.

Isaac Saias. Proving probabilistic correctness statements: the case of Rabin's algorithm for mutual exclusion. In 11th Annual Symposium on Principles of Distributed Systems, pages 263--274, Vancouver, B.C., Canada, August 1992. .pdf

Roberto Segala. A process algebraic view of I/O automata. Masters Thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, May 1992. Also, Technical Memo MIT/LCS/TR-557, Laboratory for Computer Science, Massachusetts Institute of Technology, October 1992. .pdf

Frits Vaandrager and Nancy Lynch. Action transducers and timed automata. In W. R. Cleaveland, editor, CONCUR'92 (Third International Conference on Concurrency Theory, Stony Brook, NY, USA, August 1992), volume 630 of Lecture Notes in Computer Science, pages 436--455. Springer-Verlag,1992. .pdf

Frits Vaandrager and Nancy Lynch. Action transducers and timed automata. Technical Memo MIT/LCS/TM-480, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, 02139, November 1992. Superseded by 480.b and 480.c. Abstract/.pdf

George Varghese and Nancy A. Lynch. A tradeoff between safety and liveness for randomized coordinated attack protocols. In Proceedings of the Eleventh Annual ACM Symposium on Principles of Distributed Computing, pages 241--250, Vancouver, British Columbia, Canada, August 1992. .pdf

George Varghese. Self-Stabilization by Local Checking and Correction. Ph.D thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA 02139, October 1992. Also, MIT/LCS/TR-583. .pdf

Jennifer Welch and Nancy Lynch. A modular drinking philosophers algorithm. Technical Memo MIT/LCS/TM-417.b, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, October, 1992.

1991

James Aspnes, Maurice Herlihy, and Nir Shavit. Counting Networks and Multi-Processor Coordination. Proceedings of the 23rd Annual ACM Symposium on Theory of Computing (STOC'91, New Orleans, Louisiana), pages 348-358, May 1991.

James Aspnes, Maurice Herlihy, and Nir Shavit. Counting networks. Technical Memo MIT/LCS/TM-451, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA 02139, June 1991. .pdf

Hagit Attiya, Nancy Lynch, and Nir Shavit. Are wait-free algorithms fast? Technical Memo MIT/LCS/TM-442, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, 02139, March 1991. .pdf

Hagit Attiya and Jennifer Welch. Sequential consistency versus linearizability. In Proceedings of the 3rd ACM Symposium on Parallel Algorithms and Architectures (SPAA3), 1991.

H. Attiya and J.L. Welch. Sequential consistency versus linearizability.Technical Report #674, Technion - Israel Institute of Technology, Department of Computer Science, Haifa, Israel, October 1991.

Hagit Attiya, Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. Bounds on the time to reach agreement in the presence of timing uncertainty. In Proceedings of the Twenty-third Annual ACM Symposium on Theory of Computing, pages 359--369, New Orleans, Louisiana, May 1991, and in Real-time Systems Newsletter, 7(1/2):4--16, Winter/Spring 1991. .pdf

Hagit Attiya, Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. Bounds on the time to reach agreement in the presence of timing uncertainty. Real-time Systems Newsletter, 7(1/2):4--16, Winter/Spring 1991.

Hagit Attiya and Nancy Lynch. Theory of real-time systems - project survey. In Andre M. Van Tilborg and Gary M. Koob, editors, Foundations of Real-Time Computing: Formal Specifications and Methods, chapter 5, pages 111--138. Kluwer Academic Publishers, 1991. Office of Naval Research Workshop, October, 1990. .pdf

Hagit Attiya and Nancy Lynch. Time bounds for real-time process control in the presence of timing uncertainty. Technical Memo MIT/LCS/TM-403.b, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, 02139, November 1991. .pdf

Hagit Attiya and Marc Snir. Better computing on the anonymous ring. Journal of Algorithms, 12:204--238, June 1991.

Baruch Awerbuch and George Varghese. Distributed program checking: a paradigm for building self-stabilizing distributed protocols. In 32nd Symposium on Foundations of Computer Science, pages 258--267, San Juan, PR, October 1991. IEEE.

Baruch Awerbuch, Boaz Patt-Shamir, and George Varghese. Self-stabilization by local checking and correction. In 32nd Symposium on Foundations of Computer Science, pages 268--277, San Juan, PR, October 1991. IEEE.

Alan Fekete, Nancy Lynch, Yishay Mansour, and John Spinelli. The Impossibility of Implementing Reliable Communication in the Face of Crashes. Technical Memo MIT/LCS/TM-355.c, Massachusetts Institute of Technology, Laboratory for Computer Science, September 1991. Later version is MIT-LCS-TM-355.d, 1992.

Kenneth J. Goldman. Highly concurrent logically synchronous multicast. Distributed Computing, 6(4):189--207, 1991.

Maurice Herlihy, Nir Shavit, and Orli Waarts. Low contention linearizable counting. In Proceedings of the 32nd Annual Symposium on the Foundations of Computer Science (FOCS), pages 526--535, San Juan, Puerto Rico, October 1991. IEEE. Detailed version with empirical results appeared as Technical Memo MIT/LCS/TM-459, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, 02139, November 1991. .pdf

Nancy Lynch and Hagit Attiya. Using Mappings to Prove Timing Properties. Technical Memo MIT/LCS/TM-412.d Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA 02139, October 1991. Superseded by MIT/LCS-TM-412.e, April 1992. .pdf

Nancy Lynch and Isaac Saias. An analysis of Rabin's randomized mutual exclusion algorithm: Preliminary report. Technical Memo MIT/LCS/TM-462, Laboratory for Computer Science, Massachusetts Institute of Technology, December 1991. .pdf

Nancy Lynch and Frits Vaandrager. Forward and backward simulations for timing-based systems. Technical Memo MIT/LCS/TM-458, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, 02139, November 1991. .pdf

Yishay Mansour and Boaz Patt-Shamir. Greedy packet scheduling on shortest paths. In Proceedings of the Tenth Annual ACM Symposium on Principles of Distributed Computing, Montreal, Canada, August 1991.

Stephen J. Ponzio. The real-time cost of timing uncertainty: Consensus and failure detection. (Masters Thesis) Technical Report MIT/LCS/TR-518, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA 02139, October 1991. .pdf

Stephen Ponzio. Consensus in the presence of timing uncertainty: Omission and Byzantine failures. In Proceedings of the Tenth Annual ACM Symposium on Principles of Distributed Computing, pages 125--138, Montreal, Quebec, Canada, August 1991.

M. Saks, N. Shavit, and H. Woll. Optimal time randomized consensus -- making resilient algorithms fast in practice. In Proceedings of the 2nd ACM Symposium on Discrete Algorithms (SODA), pages 351--362, San Francisco, January 1991.

F. W. Vaandrager. On the relationship between process algebra and input/output automata (extended abstract). In 6th Annual Symposium on Logic in Computer Science, pages 387--398, Amsterdam, 1991. IEEE Computer Society Press.

F. W. Vaandrager. Determinism > (Event Structure Isomorphism = Step Sequence Equivalence). Theoretical Computer Science, 79:275--294, 1991.

1990

Yehuda Afek, Hagit Attiya, Danny Dolev, Eli Gafni, Michael Merritt, and Nir Shavit. Atomic snapshots of shared memory. In Proceedings of the Ninth Annual ACM Symposium on Principles of Distributed Computing, Quebec, Canada, August 1990.

Yehuda Afek, Hagit Attiya, Danny Dolev, Eli Gafni, Michael Merritt, and Nir Shavit. Atomic snapshots of shared memory. Technical Memo MIT/LCS/TM-429, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, 02139, May 1990. .pdf

Hagit Attiya, Amotz Bar-Noy, and Danny Dolev. Sharing memory robustly in message-passing systems. In Proceedings of the Ninth Annual ACM Symposium on Principles of Distributed Computing, Quebec, Canada, August 1990.

Hagit Attiya, Amotz Bar-Noy, and Danny Dolev. Sharing memory robustly in message-passing systems. Technical Memo MIT/LCS/TM-423, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, 02139, February 1990. .pdf

Hagit Attiya, Amotz Bar-Noy, Danny Dolev, David Peleg, and Rudiger Reischuk. Renaming in an asynchronous environment. Journal of the ACM, 37(3):524--548, July 1990.

Hagit Attiya, Cynthia Dwork, Nancy A. Lynch, and Larry J. Stockmeyer. Bounds on the time to reach agreement in the presence of timing uncertainty. Technical Memo MIT/LCS/TM-435, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA 02139, November 1990. .pdf

Hagit Attiya, Nancy Lynch, and Nir Shavit. Are wait-free algorithms fast? In 31st Annual Symposium on Foundations of Computer Science, volume 1, pages 55--64. IEEE, October 1990. .pdf

R. De Nicola and F.W. Vaandrager. Three logics for branching bisimulation. Appeared as CWI Report CS-R9012,Amersterdam, 1990.

R. De Nicola and F. W. Vaandrager. Action versus state based logics for transition systems. In I. Guessarian, editor, Semantics of Systems of Concurrent Processes, Proceedings LITP Spring School on Theoretical Computer Science, volume 469 of Lecture Notes in Computer Science, pages 407--419, La Roche Posay, France, 1990. Springer-Verlag.

A. D. Fekete. Asymptotically optimal algorithms for approximate agreement. Distributed Computing, 4(1):9--29, March 1990.

Alan Fekete, Nancy Lynch, Michael Merritt, and William Weihl. Commutativity-based locking for nested transactions. Journal of Computer and System Sciences, 41(1):65--156, August 1990. .pdf

Alan Fekete, Nancy Lynch, Michael Merritt, and William Weihl. Commutativity-based locking for nested transactions. In John Rosenberg and David Koch, editors, Persistent Object Systems, Newcastle, Australia (Proceedings of the 3rd International Workshop on Persistent Object Systems, January 1989), pages 319-340, Workshops in Computing, Springer-Verlag, 1990. .pdf

Alan Fekete and Nancy Lynch. The need for headers: an impossibility result for communication over unreliable channels. In G. Goos and J. Hartmanis, editors, CONCUR '90, Theories of Concurrency: Unification and Extension, volume 458 of Lecture Notes in Computer Science, pages 199--216. Springer-Verlag, August 1990. .pdf

Alan Fekete and Nancy Lynch. The need for headers: an impossibility result for communication over unreliable channels. Technical Memo MIT/LCS/TM-428, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, 02139, May 1990. .pdf

Alan Fekete, Nancy Lynch, and William Weihl. A serialization graph construction for nested transactions. In Proceedings of the Ninth Annual ACM Symposium on Principles of Database Systems, pages 94--108, Nashville, TN, April 1990. .pdf

Alan Fekete and Nancy Lynch and William Weihl. A Serialization Graph Construction for Nested Transactions. Technical Memo MIT/LCS/TM-421, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA 02139, February 1990. .pdf

Michael J. Fischer, Nancy A. Lynch, and Michael Merritt. Easy impossibility proofs for distributed consensus problems.In B. Simons and A. Spector, editors, Fault-tolerant Distributed Computing (Proceedings of of the Asilomar Workshop on Fault-Tolerant Distributed Computing, March, 1986), volume 448 of Lecture Notes in Computer Science, pages 147-170, 1990. Springer-Verlag. pdf

Kennth J. Goldman and Nancy A. Lynch. Modelling shared state in a shared action model. In Proceedings of the 5th Annual IEEE Symposium on Logic in Computer Science, pages 450--463, Philadelphia, Pennyslvania, June 1990. pdf

Kenneth J. Goldman and Nancy Lynch. Modelling shared state in a shared action model. Technical Memo MIT/LCS/TM-427, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, 02139, March 1990. pdf

Kenneth J. Goldman. Distributed algorithm simulation using input/output automata. Ph.D thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA, July 1990. Technical Report MIT/LCS/TR-490, Cambridge, MA, September 1990. .pdf

Aparna Mini Gupta. I/O automaton based simulation of selected distributed algorithms. Bachelor Thesis, MIT Dept. of Electrical Engineering and Computer Science, June, 1990. .pdf

Joseph Y. Halpern and Yoram Moses. Knowledge and common knowledge in a distributed environment. Journal of the ACM, 37(3):549--587, 1990.

Leslie Lamport and Nancy Lynch. Distributed computing: Models and methods. In Jan Van Leeuwen, editor, Formal Models and Semantics, volume B of Handbook of Theoretical Computer Science, chapter 18, pages 1157--1199. Elsevier Science Publishers B. V. and MIT Press, 1990. .pdf

John Leo. Dynamic process creation in a static model. Master's thesis, Department of Electrical Engineering and Computer Science, Cambridge, MA 02139, May 1990. .pdf

Nancy Lynch and Hagit Attiya. Using mappings to prove timing properties. In Proceedings of the Ninth Annual ACM Symposium on Principles of Distributed Computing, Quebec, Canada, August 1990. pdf Expanded version in earlier Technical memo, TM412.d.

Nancy A. Lynch. Multivalued possibilities mappings. In J.W. de Bakker, W.P. de Roever, and G. Rozenberg, editors, Stepwise Refinement of Distributed Systems: Models, Formalisms, Correctness (REX Workshop, Mook, The Netherlands, May/June 1989), volume 430 of Lecture Notes in Computer Science, pages 519--543. Springer-Verlag, 1990. .pdf

Nancy Lynch. Multivalued possibilities mappings. Technical Memo MIT/LCS/TM-422, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, 02139, August 1990. .pdf

B. Simons, Jennifer L. Welch, and Nancy Lynch. An overview of clock synchronization. In B. Simons and A. Spector, editors, Fault-tolerant Distributed Computing (Proceedings of of the Asilomar Workshop on Fault-Tolerant Distributed Computing, March, 1986), volume 448 of Lecture Notes in Computer Science, pages 84-96, 1990. Springer-Verlag. .pdf

Ken Streeter. A partitioned computation machine. Master's thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA 02139, August 1990. .pdf

Greg Troxel. A hierarchical proof of an algorithm for deadlock recovery in a system using remote procedure calls. Master's thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA 02139, January 1990. Technical Report MIT/LCS/TR-474, Cambridge, MA 02139, 1990. .pdf

Mark R. Tuttle. Knowledge and distributed computation. Technical Memo MIT/LCS/TR-477, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, 02139, 1990. .pdf

1989

Hagit Attiya, Danny Dolev, and Nir Shavit. Bounded polynomial randomized consensus. In Proceedings of the Eighth Annual ACM Symposium on Principles of Distributed Computing, pages 281--293, Edmonton, Alberta, Canada, August 1989.

Hagit Attiya, Danny Dolev, and Nir Shavit. Bounded polynomial randomized consensus. Technical Memo MIT-LCS-TM-392, MIT Laboratory for Computer Science, Cambridge, MA 02139, June 1989. pdf

Hagit Attiya and Nancy Lynch. Time bounds for real-time process control in the presence of timing uncertainty. In Proceedings of the 10th IEEE Real-Time Systems Symposium, pages 268-284, Santa Monica, CA, December 1989. pdf

Hagit Attiya and Nancy Lynch. Time bounds for real-time process control in the presence of timing uncertainty. Technical Memo MIT/LCS/TM-403, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, 02139, July 1989. .pdf

Hagit Attiya and Mark Tuttle. Bounds for slotted $ell-exclusion$. Unpublished manuscript, February 1989.

Christopher P. Colby. Correctness Proofs of the Peterson-Fischer Mutual Exclusion Algorithms. Technical Memo MIT/LCS/TM-399, Laboratory for Computer Science, Massachusetts Institute of Technology Cambridge, MA, June 1989. Bachelors thesis. .pdf

Danny Dolev and Nir Shavit. Bounded concurrent time-stamp systems are constructible. In Proceedings of the Twenty-first Annual ACM Symposium on Theory of Computing, pages 454--466, Seattle, Washington, May 1989. .pdf

Danny Dolev and Nir Shavit. Bounded concurrent time-stamp systems are constructible. Technical Memo MIT/LCS/TM-393, Laboratory for Computer Science, Massachusetts Institute of Technology Cambridge, MA, June 1989. .pdf

Alan Fekete, Nancy Lynch, Yishay Mansour, and John Spinelli. The Data link layer: The impossibility of implementing reliable communication in the face of crashes. Technical Memo MIT/LCS/TM-355.b, Massachusetts Institute of Technology, Laboratory for Computer Science, Cambridge, MA 02139, August 1989. Later version is MIT-LCS-TM-355.d, 1992.

Alan Fekete, Nancy Lynch, Michael Merritt, and William Weihl. Commutativity-based locking for nested transactions. Technical Memo MIT/LCS/TM-370.b, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, 02139, 1989. .pdf

Michael J. Fischer, Nancy A. Lynch, James E. Burns, and Allan Borodin. Distributed FIFO allocation of identical resources using small shared space. ACM Transactions on Programming Languages and Systems, 11(1):90--114, January 1989. pdf

Kenneth J. Goldman. Highly concurrent logically synchronous multicast. In Proceedings of the 3rd International Workshop on Distributed Algorithms, volume 392 of Lecture Notes in Computer Science, Nice, France, September 1989. Springer-Verlag.

Kenneth J. Goldman. Highly concurrent logically synchronous multicast. Technical Memo MIT/LCS/TM-401, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, July 1989. .pdf

Kenneth J. Goldman. Paralation views: Abstractions for efficient scientific computing on the connection machine. Technical Memo MIT/LCS/TM-398, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, August 1989. .pdf

Joseph Halpern and Mark Tuttle. Knowledge, probability, and adversaries. In Proceedings of the Eighth Annual ACM Symposium on Principles of Distributed Computing, pages 103--118, August 1989. Also, IBM Research Report RJ 7045, September 1989.

Maurice Herlihy, Nancy Lynch, Michael Merritt, and William Weihl. On the correctness of orphan management algorithms. Technical Memo MIT/LCS/TM-406, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA 02139, August 1989. pdf

Leslie Lamport and Nancy Lynch. Chapter on distributed computing. Technical Memo MIT/LCS/TM-384, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, 02139, February 1989. pdf

Nancy Lynch. A hundred impossiblility proofs for distributed computing. In Proceedings of the Eighth Annual ACM Symposium on Principles of Distributed Computing, Edmonton, Alberta, Canada, August 1989. PDF

Nancy Lynch. A hundred impossiblility proofs for distributed computing. Technical Memo MIT/LCS/TM-394, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, 02139, 1989. PDF

Nancy Lynch and Hagit Attiya. Using mappings to prove timing properties. Technical Memo MIT/LCS/TM-412.b, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, 02139, December 1989. .pdf

Nancy Lynch and Kenneth J. Goldman. Distributed algorithms. MIT/LCS/RSS 5, Laboratory for Computer Science, Massachusetts Institute of Technology, 1989. Lecture notes for 6.852. .pdf

Nancy Lynch and Eugene Stark. A proof of the Kahn principle for Input/Output automata. Information and Computation, 82(1):81--92, July 1989. .pdf

Nancy Lynch and Mark Tuttle. An introduction to Input/Output automata. CWI-Quarterly, 2(3):219--246, September 1989. Centrum voor Wiskunde en Informatica, Amsterdam, The Netherlands. .pdf Also, Technical Memo MIT/LCS/TM-373, Laboratory for Computer Science, Massachusetts Institute of Technology. .pdf

Magda F. Nour. An Automata-Theoretic Model for Unity. Technical Memo MIT/LCS/TM-400, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA 02139, June 1989. Bachelors thesis. .pdf

Mark R. Tuttle. Knowlege and Distributed Computation. Ph.D thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technolgy, September 1989. .pdf

Jennifer Welch and Nancy Lynch. Synthesis of efficient drinking philosophers algorithms. Technical Memo MIT/LCS/TM-417, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, November, 1989. .pdf

1988

James Aspnes, Alan Fekete, Nancy Lynch, Michael Merritt, and William Weihl. A theory of timestamp-based concurrency control for nested transactions. In Proceedings of 14th International Conference on Very Large Data Bases, pages 431--444, Los Angeles, CA., August 1988. .pdf

Bard Bloom. Constructing two-writer registers. IEEE Transactions on Computers, 37(12):1506--1514, December 1988.

Brian A. Coan. A compiler that increases the fault-tolerance of asynchronous protocols. IEEE Transactions on Computers, (Special Issue on Parallel and Distributed Algorithms), 37(12):1541--1553, December 1988.

Brian Coan and Jennifer Lundelius. Transaction commit in a realistic timing model. Technical Memo MIT/LCS/TM-360, Laboratory for Computer Science, Massachuetts Institute of Technology, Cambridge, MA, June 1988. .pdf

Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. Consensus in the presence of partial synchrony. Journal of the ACM, 35(2):288--323, April 1988. .pdf

A. Fekete, N. Lynch, and L. Shrira. A modular proof of correctness for a network synchronizer. In J. van Leeuwen, editor, Distributed Algorithms (2nd International Workshop, Amsterdam, The Netherlands, July 1987), volume 312 of Lecture Notes in Computer Science, pages 219--256. Springer-Verlag, 1988. .pdf

Alan Fekete, Nancy Lynch, Michael Merritt, and William Weihl. Commutativity-based locking for nested transactions. Technical Memo MIT/LCS/TM-370, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, 02139, August 1988. Superseded by MIT/LCS/TM-370b..pdf

Hector Garcia-Molina, Boris Kogan, and Nancy Lynch. Reliable broadcast in networks with nonprogrammable servers. In 8th International Conference on Distributed Computing Systems, pages 428-437, San Jose, CA, June 1988. pdf

Nancy Lynch, Yishay Mansour, and Alan Fekete. The data link layer: Two impossibility results. Technical Memo MIT/LCS/TM-355, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, 02139, May 1988. pdf (Later version is MIT-LCS-TM-355.d, 1992.)

Joseph Halpern, Yoram Moses, and Mark Tuttle. A knowledge-based analysis of zero knowledge. In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, pages 132--147, May 1988.

Nancy Lynch. Modelling real-time systems. In Foundations of Real-Time Computing Research Initiative, Fall Church, Virginia, November 1988. Office of Naval Research Kickoff Workshop. pdf

Nancy Lynch. I/O Automata: A model for discrete event systems. In 22nd Annual Conference on Information Sciences and Systems, pages 29-38, Princeton University, Princeton, N.J., March 1988. pdf

Nancy Lynch. I/O Automata: A model for discrete event systems. Technical Memo MIT/LCS/TM-351, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, 02139, March 1988. pdf

Nancy Lynch, Yishay Mansour, and Alan Fekete. The data link layer: Two impossibility results. In Proceedings of the Seventh Annual ACM Symposium on Principles of Distributed Computing, pages 149--170, Toronto, Ontario, Canada, August 1988. .pdf

Nancy Lynch, Michael Merritt, William Weihl, and Alan Fekete. A theory of atomic transactions. In M. Gyssens, J. Paredaens, D. Van Gucht, editors ICDT'88 (Proceedings of the 2nd International Conference on Database Theory, Bruges, Belgium, August/September 1988), volume 326 of Lecture Notes in Computer Science, pages 41--71, Springer-Verlag, 1988. .pdf

Nancy Lynch, Michael Merritt, William Weihl, and Alan Fekete. A theory of atomic transactions. Technical Memo MIT/LCS/TM-362, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, 02139, June 1988. .pdf

Nancy Lynch and Michael Merritt. Introduction to the theory of nested transactions. Theoretical Computer Science, 62(1,2):123--186, December 1988. .pdf

Nancy Lynch and Eugene Stark. A proof of the Kahn principle for Input/Output automata. Technical Memo MIT/LCS/TM-349, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, 02139, January 1988. .pdf

Nancy Lynch and Mark Tuttle. An introduction to Input/Output automata. Technical Memo MIT/LCS/TM-373, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, 02139, November 1988. .pdf

Yoram Moses and Mark R. Tuttle. Programming simultaneous actions using common knowledge. Algorithmica, 3(1):121--169, 1988. Special Issue on Parallel and Distributed Computing, Part 1.

Sape Mullender and Paul M.B. Vitanyi. Distributed match-making. Algorithmica, 3:367--391, 1988. Special issue on Distributed Computing.

Russel Schaffer. On the correctness of atomic multi-writer registers. Technical Memo MIT/LCS/TM-364, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, 02139, June 1988. (Revised January 1989). .pdf

Russel W. Schaffer. Peterson-Burns multi-writer, multi-reader atomic register algorithm. Bachelor's Thesis, June 1988, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA 02139. .pdf

Barbara Simons, Jennifer Lundelius Welch, and Nancy Lynch. An overview of clock synchronization. Research Report RJ 6505 (63306), IBM Research Division, Yorktown Heights, New York, October 1988. .pdf

E. W. Stark. Proving entailment between conceptual state specifications. Theoretical Computer Science, 56(1):135--154, January 1988.

Mark R. Tuttle. A game-theoretic characterization of eventual common knowledge. Unpublished manuscript., October 1988.

P.M.B. Vitanyi. Locality, communication and interconnect length in multicomputers. SIAM Journal on Computing, 17:659--672, 1988.

Jennifer Lundelius Welch and Nancy Lynch. A new fault-tolerant algorithm for clock synchronization. Information and Computation, 77(1):1--36, April 1988. .pdf

Jennifer Lundelius Welch. Simulating Synchronous Processors. Technical Memo MIT/LCS/TM-359, MIT Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, June 1988. .pdf

Jennifer Lundelius Welch. Topics in Distributed Computing: The Impact of Partial Synchrony, and Modular Decomposition of Algorithms. Ph.D thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA 02139, March 1988. .pdf

Jennifer Lundelius Welch, Leslie Lamport, and Nancy Lynch. A lattice-structured proof technique applied to a minimum spanning tree algorithm. In Proceedings of the Seventh Annual ACM Symposium on Principles of Distributed Computing, pages 28--43, Toronto, Ontario, Canada, August 1988. .pdf

Jennifer Lundelius Welch, Leslie Lamport, and Nancy Lynch. A lattice-structured proof technique applied to a minimum spanning tree algorithm. Technical Memo MIT/LCS/TM-361, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, 02139, June 1988. .pdf

1987

James Aspnes. Timestamp ordering and nested transactions. Master's thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA 02139, May 1987. .pdf

Bard Bloom. Constructing two-writer atomic registers. In Proceedings of the Sixth Annual ACM Symposium on Principles of Distributed Computing, pages 249--259, Vancouver, British Columbia, Canada, August 1987.

James E. Burns and Nancy A. Lynch. The Byzantine firing squad problem. Advances in Computing Research, 4:147--161, 1987. .pdf

Brian A. Coan. Achieving Consensus in Fault-Tolerant Distributed Computer Systems: Protocols, Lower Bounds, and Simulations. Ph.D thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA 02139, June 1987. .pdf

Anthony P. DiPesa Jr. Real-time extensions to a relational database. Master's thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA 02139, June 1987. .pdf

Danny Dolev, Cynthia Dwork, and Larry Stockmeyer. On the minimal synchronism needed for distributed consensus. Journal of the ACM, 34(1):77--97, January 1987.

Alan Fekete. Topics in Distributed Algorithms. Ph.D thesis, Department of Mathematics, Harvard University, Cambridge, MA, August 1987.

Alan Fekete. Asynchronous approximate agreement. In Proceedings of the Sixth Annual ACM Symposium on Principles of Distributed Computing, pages 64--76, August 1987.

Alan Fekete. Approximate agreement. Technical Memo MIT/LCS/TM-342, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA 02139, September 1987. .pdf

Alan Fekete, Nancy Lynch, Michael Merritt, and William Weihl. Nested transactions and read/write locking. In Proceedings of the 6th ACM Symposium on Principle of Database Systems, pages 97--111, San Diego, California, March 1987. .pdf

Alan Fekete, Nancy Lynch, Michael Merritt, and William Weihl. Nested transactions and read/write locking. Technical Memo MIT/LCS/TM-324, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, 02139, April 1987. .pdf

Alan Fekete, Nancy Lynch, Michael Merritt, and William Weihl. Nested transactions, conflict-based locking and dynamic atomicity. Technical Memo MIT/LCS/TM-340, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA 02139, September 1987. .pdf

Alan Fekete, Nancy Lynch, and Luiba Shrira. A modular proof of correctness for a network synchronizer. Technical Memo MIT/LCS/TM-341, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, 02139, September 1987. .pdf

Greg N. Frederickson and Nancy A. Lynch. Electing a leader in a synchronous ring. Journal of the ACM, 34(1):98--115, January 1987. .pdf

Hector Garcia-Molina, Boris Kogan, and Nancy Lynch. Reliable broadcast in networks with nonprogrammable servers. Technical Report CS-TR-123-87, Princeton University, November 1987. .pdf

Kenneth J. Goldman and Nancy Lynch. Quorum consensus in nested transaction. In Proceedings of the Sixth Annual ACM Symposium on Principles of Distributed Computing, pages 27--41, August 1987. .pdf

Kenneth J. Goldman. Data replication in nested transaction systems. Masters Thesis. Technical Report MIT/LCS/TR-390, MIT Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, May 1987..pdf

Maurice Herlihy, Nancy Lynch, Michael Merritt, and William Weihl. On the correctness of orphan elimination algorithms. Technical Memo MIT/LCS/TM-329, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, 02139, May 1987. .pdf

Maurice Herlihy, Nancy Lynch, Michael Merritt, and William Weihl. On the correctness of orphan elimination algorithms. In 17th IEEE Symposium on Fault-Tolerant Computing, pages 8--13, 1987. .pdf

Nancy A. Lynch and Mark R. Tuttle. Hierarchical correctness proofs for distributed algorithms. In Proceedings of the Sixth Annual ACM Symposium on Principles of Distributed Computing, pages 137--151, Vancouver, British Columbia, Canada, August 1987. .pdf

Nancy A. Lynch and Mark R. Tuttle. Hierarchical correctness proofs for distributed algorithms. Master of Science Thesis, Dept. of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, April 1987. Also, Technical Report MIT/LCS/TR-387, Laboratory for Computer Science, Massachusetts Institute of Technology. Abstract/.pdf

Yoram Moses and Mark R. Tuttle. Programming simultaneous actions using common knowledge. Technical Report MIT/LCS/TR-369, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA 02139, February 1987. .pdf

S. K. Sarin and Nancy Lynch. Discarding obsolete information in a replicated database system. IEEE Transactions on Software Engineering, SE-13(1):39--47, January 1987. .pdf

1986

Christopher W. Clifton. Dynamic load balancing. Master's thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA 02139, June 1986. .pdf

Brian Coan and Cynthia Dwork. Simultaneity is harder than agreement. In Proceedings of the 5th Symposium on Reliability in Distributed Software and Database Systems, pages 141--150, Los Angeles, CA, January 1986.

Brian A. Coan. A communication-efficient canonical form for fault-tolerant distributed protocols. In Proceedings of the Fifth Annual ACM Symposium on Principles of Distributed Computing, pages 63--72, Calgary, Alberta, Canada, August 1986.

B. Coan, B. Oki, and E. Kolodner. Limitations on database availability when networks partition. In Proceedings of the 5th Annual ACM Symposium on Principles of Distributed Computing, pages 187--194, Calgary, Alberta, Canada, August 1986. Also, Programming Methodology Group Memo 49, MIT Laboratory for Computer Science, Cambridge, MA 02139.

Brian Coan and Jennifer Welch. Transaction commit in a realistic fault model. In Proceedings of the Fifth Annual ACM Symposium on Principles of Distributed Computing, pages 40--51, Calgary, Alberta, Canada, August 1986.

Danny Dolev, Nancy A. Lynch, Shlomit S. Pinter, Eugene W. Stark, and William E. Weihl. Reaching approximate agreement in the presence of faults. Journal of the ACM, 33(3):499--516, July 1986. pdf

Cynthia Dwork and Yoram Moses. Knowledge and Common Knowledge in a Byzantine Environment: Crash Failures. Technical Memo, MIT/LCS/TM-300, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, July 1986. pdf

Cynthia Dwork and Yoram Moses. Knowledge and common knowledge in a Byzantine Environment I: Crash failures. In Proceedings of Conference on Theoretical Aspects of Reasoning about Knowledge, 1986.

Alan Fekete. Asymptotically optimal algorithms for approximate agreement. In Proceedings of the Fifth Annual ACM Symposium on Principles of Distributed Computing, pages 73--87, Calgary, Alberta, Canada, August 1986.

Michael J. Fischer, Nancy A. Lynch, and Michael Merritt. Easy impossibility proofs for distributed consensus problems. Distributed Computing, 1(1):26--39, January 1986. pdf

Maurice Herlihy, Nancy Lynch, Michael Merritt, and William Weihl. On the correctness of orphan elimination algorithms. Programming Methodology Group Memo 50, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, December 1986. pdf

Paris C. Kanellakis, Stavros S. Cosmadakis, and Nicolas Spyratos. Partition semantics for relations. Journal of Computer and System Sciences, 33(2):203-233, October 1986.

E. Kranakis and P.M.B. Vitanyi. Distributed control in computer networks and cross-sections of multidimensional bodies. Technical Memo MIT/LCS/TM-304, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA 02139, March 1986.

M. Li, L. Longpre, and P.M.B. Vitanyi. The power of the queue. In Structure in Complexity Theory Conference, pages 219--233, Berlin, April 1986. Spring Verlag.

M. Li, L. Longpre, and P.M.B. Vitanyi. The power of the queue. Technical Memo MIT/LCS/TM-303, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, 02139, April 1986.

Nancy Lynch, Barbara Blaustein, and Michael Siegel. Correctness conditions for highly available replicated databases. In Proceedings of the Fifth Annual ACM Symposium on Principles of Distributed Computing, pages 11--28, Calgary, Alberta, Canada, August 1986. .pdf

Nancy Lynch, Barbara Blaustein, and Michael Siegel. Correctness conditions for highly available replicated databases. Technical Report MIT/LCS/TR-364, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, 02139, June 1986. .pdf

Nancy A. Lynch, Nancy D. Griffeth, Michael J. Fischer, and Leonidas J. Guibas. Probabilistic analysis of a network resource allocation algorithm. Information and Computation, 68(1-3):47--85, January-February-March 1986. .pdf (Note, abstract in AMS Workshop on Probabilistic Algorithms, June 1985).

Nancy Lynch and Michael Merritt. Introduction to the theory of nested transactions. In Giorgio Ausiello and Paolo Atzeni, editors, ICDT'86 (Proceedings of the International Conference on Database Theory, Rome, Italy, September 1986), volume 243 of Lecture Notes in Computer Science, pages 278-305, 1986. Springer-Verlag. .pdf

Nancy Lynch and Michael Merritt. Introduction to the theory of nested transactions. Technical Memo MIT/LCS/TM-367, Laboratory for Computer Science, Massachusetts Institute of of Technology, July 1986. pdf

Nancy A. Lynch. Concurrency control for resilient nested transactions. Advances in Computing Research, 3:335--373, 1986. .pdf

Yoram Moses and Mark R. Tuttle. Programming simultaneous actions using common knowledge. In Proceedings of the 27th Annual Symposium on Foundations of Computer Science, pages 208--221, Toronto, Ontario, Canada, October 1986.

Sape J. Mullender and Paul M.B. Vitanyi. Distributed match-making for processes in computer networks. In Proceedings of the Fourth Annual ACM Symposium on Principles of Distributed Computing, pages 261--271, Minaki, Ontario, Canada, August 1985. Also, CWI Report CS-R8513. Reprinted in Operating Systems Review, 1986.

Eugene W. Stark. Proving entailment between conceptual state specifications. In Proceedings of the 1986 European Symposium on Programming, volume 213 of Lecture Notes in Computer Science, pages 197--209, Saarbrucken, West Germany, March 1986. Springer-Verlag.

Paul Vitanyi. Non-sequential computation and laws of nature. In Proceedings of Aegean Workshop on Computing, VLSI Algorithms and Architectures(2nd International Workshop on Parallel Processing and VLSI), 1986.

Paul Vitanyi. Non-sequential computation and laws of nature. Technical Memo MIT/LCS/TM-306, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, 02139, May 1986.

Paul M.B. Vitanyi. Archirithmics or algotecture? Mathematics and Computer Science II, 4:139--161, 1986. CWI Monographs, M. Hazewinkel, J.K. Lenstra and L.G.L.T. Meertens, Eds., North-Holland.

1985

Baruch Awerbuch and Robert G. Gallager. Distributed BFS algorithms. In 26th Annual Symposium on Foundations of Computer Science. IEEE, October 1985.

Baruch Awerbuch. Complexity of network synchronization. Journal of the ACM, 32(4):804--823, October 1985.

Baruch Awerbuch. A new distributed depth-first-search algorithm. Information Processing Letters, 20:147--150, April 1985.

James Burns and Nancy Lynch. The Byzantine firing squad problem. Technical Memo MIT/LCS/TM-275, Laboratory for Computer Science, Massachusetts Institute of of Technology, Cambridge, MA, 02139, April 1985. pdf

Benny Chor and Brian A. Coan. A simple and efficient randomized Byzantine agreement algorithm. IEEE Transactions on Software Engineering, SE-11(6):531--539, June 1985. Reprinted from IEEE 1984 Proceedings of the Fourth Symposium on Reliability in Distributed Software and Database Systems.

Benny Chor, Michael Merritt, and David B. Shmoys. Simple constant-time consensus protocols in realistic failure models. In Proceedings of the Fourth Annual ACM Symposium on Principles of Distributed Computing, pages 152--162, 1985. pdf

Brian Coan, Danny Dolev, Cynthia Dwork, and Larry Stockmeyer. The distributed firing squad problem. In Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing, pages 335--345, Providence, Rhode Island, May 1985. pdf

Nachum Dershowitz and Shmuel Zaks. Patterns in trees. Technical Memo MIT/LCS/TM-271, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, January 1985. pdf

Danny Dolev, Nancy A. Lynch, Shlomit S. Pinter, Eugene W. Stark, and William E. Weihl. Reaching Approximate Agreement in the Presence of Faults Technical Memo MIT/LCS/TM-251, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, October 1985. .pdf

Danny Dolev, Nancy A. Lynch, Shlomit S. Pinter, Eugene W. Stark, and William E. Weihl. Reaching approximate agreement in the presence of faults. Technical Memo MIT/LCS/TM-276, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge MA 02139, February 1985. .pdf

Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. Consensus in the presence of partial synchrony. Technical Memo MIT/LCS/TM-270, Laboratory for Computer Science, Massachusetts Institute of Technology, October 1985. Revision of MIT/LCS/TM-270 (October 1984). .pdf

Michael J. Fischer, Nancy D. Griffeth, Leonidas J. Guibas, and Nancy A. Lynch. Probabilistic analysis of a network resource allocation algorithm. Technical Memo MIT/LCS/TM-278, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, 02139, April 1985. .pdf

Michael Fischer, Nancy Lynch, James Burns, and Allan Borodin. Distributed FIFO allocation of identical resources using small shared space. Technical Memo MIT/LCS/TM-290, Laboratory for Computer Science, Massachusetts Institute of Technology, June 1985. .pdf

Michael Fischer, Nancy Lynch, and Michael Merritt. Easy impossibility proofs for distributed consensus problems. In Proceedings of the Fourth Annual ACM Symposium on Principles of Distributed Computing, pages 59--70, August 1985. pdf

Michael Fischer, Nancy Lynch, and Michael Merritt. Easy impossibility proofs for distributed consensus problems. Technical Memo MIT/LCS/TM-279, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, 02139, June 1985. pdf

Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson. Impossibility of distributed consensus with one faulty process. Journal of the ACM, 32(2):374--382, April 1985. pdf

Greg N. Frederickson and Nancy Lynch. Electing a leader in a synchronous ring. Technical Memo MIT/LCS/TM-277, Laboratory for Computer Science, Massachusetts Institute of of Technology, Cambridge, MA 02139, July 1985. Earlier version dated March, 1985 entitled ``A General Lower Bound for Electing a Leader in a Ring''. pdf

Hector Garcia-Molina, Nancy Lynch, B. Blaustein, C. Kaufman, S. Sarin, and O. Schmueli. Notes on a reliable broadcast protocol. Technical Memorandum CCA-85-08, Computer Corporation of America, Cambridge, MA, December 1985. pdf

Paris .C. Kanellakis and Stavros S. Cosmadakis. Equational theories and database constraints. In Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing, May 1985.

Paris C. Kanellakis and Stavros S. Cosmadakis. Two applications of equational theories to database theory. In Proceedings of First International Conference on Rewriting Techniques and Applications, May 1985.

Paris C. Kanellakis, Stavros S. Cosmadakis, and Nicolas Spyratos. Partition semantics for relations. In Proceedings of the Fourth Annual ACM Symposium on Principles of Distributed Computing, May 1985.

Paris C. Kanellakis, Kenneth J. Goldman, Sally A. Goldman, and Stanley B. Zdonik. ISIS: Interface for a semantic information system. In Proceedings of ACM SIGMOD, May 1985.

Paris C. Kanellakis and Christos H. Papadimitriou. The complexity of distributed concurrency control. SIAM Journal on Computing, 14(1):52--75, February 1985.

Paris C. Kanellakis and Scott .A. Smolka. On the analysis of cooperation and antagonism in networks of communicating processes. In Proceedings of the Fourth Annual ACM Symposium on Principles of Distributed Computing, August 1985.

Nancy A. Lynch. Concurrency control for resilient nested transactions. Technical Report MIT/LCS/TR-285, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA 02139, October 1985. .pdf

Nancy Lynch and Greg N. Frederickson. Electing a leader in a synchronous ring. Technical Memo MIT/LCS/TM-277, Laboratory for Computer Science, Massachusetts Institute of of Technology, Cambridge, MA 02139, July 1985. Note earlier version dated March, 1985 entitled ``A General Lower Bound for Electing a Leader in a Ring''. pdf

Everett Norcross McKay. A methodology for software implemented transient error recovery in spacecraft computation. SB/SM thesis, MIT, Department of Electrical Engineering and Computer Science, Cambridge, MA, January 1985. pdf

Sape J. Mullender and Paul M.B. Vitanyi. Distributed match-making for processes in computer networks. In Proceedings of the Fourth Annual ACM Symposium on Principles of Distributed Computing, pages 261--271, Minaki, Ontario, Canada, August 1985. Also, CWI Report CS-R8513. Reprinted in Operating Systems Review, 1986. .pdf

Eugene W. Stark. A proof technique for rely/guarantee properties. In Proceedings of the 5th Conference on Foundations of Software Technology and Theoretical Computer Science, volume 206 of Lecture Notes in Computer Science, pages 369--391, New Delhi, India, December 1985. Springer-Verlag. .pdf

1984

Benny Chor and Brian A. Coan. A simple and efficient randomized Byzantine agreement algorithm. Technical Memo MIT/LCS/TM-266, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA 02139, August 1984. .pdf

Brian A. Coan and Russell Turpin. Extending Binary Byzantine Agreement to Multivalued Byzantine agreement. Technical Memo MIT/LCS/TR-315, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, 02139, April 1984. .pdf

Cynthia Dwork, Paris C. Kanellakis, and John C. Mitchell. On the sequential nature of unification. Technical Memo MIT/LCS/TM-257, Massachusetts Institute of Technology, Cambridge, MA 02139, March 1984. .pdf

C. Dwork, P. Kanellakis, and J. Mitchell. On the sequential nature of unification. Journal of Logic Programming, 1(1), pages 35-50, 1984. .pdf

Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. Consensus in the presence of partial synchrony. Proceedings of the Third Annual ACM Symposium on Principles of Distributed Computing (PODC), Vancouver, B.C., Canada, pages 103-118, August 1984. .pdf

Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. Consensus in the presence of partial synchrony(preliminary version). Technical Memo MIT/LCS/TM-270, Laboratory for Computer Science, Massachusetts Institute of Technology, October 1984. Revised MIT/LCS/TM-270 (See October 1985). .pdf

Cynthia Dwork and Dale Skeen. Patterns of communication in consensus protocols. In Proceedings of the Third Annual ACM Symposium on Principles of Distributed Computing, pages 143-153, Vancouver, BC, Canada, August 1984. .pdf

N. Dershowitz and S. Zaks. Patterns in trees. In Proceedings of the 9th Colloquium on Trees in Algebra and Programming, Bordeaux, France, March 1984.

Greg N. Frederickson and Nancy Lynch. The impact of synchronous communication on the problem of electing a leader in a ring. In Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing, pages 493--503, April 1984. .pdf

Joseph Y. Halpern and Yoram Moses. Knowledge and common knowledge in a distributed environment. Proceedings of the 3rd ACM Symposium on Principles of Distributed Computing, pages 50-61, Vancouver, BC, Canada, August 1984. Preliminary version. .pdf

Jennifer Lundelius. Synchronizing Clocks in a Distributed System. Masters thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA 02139. Technical Report MIT/LCS/TR-335, Cambridge, MA, August 1984. .pdf

Jennifer Lundelius and Nancy Lynch. An upper and lower bound for clock synchronization. Information and Control, 62(2-3):190--204, August/September 1984. .pdf

Jennifer Lundelius and Nancy Lynch. A new fault-tolerant algorithm for clock synchronization. In Proceedings of the Third Annual ACM Symposium on Principles of Distributed Computing, pages 75--88, Vancouver, B.C., Canada, August 1984. .pdf

Jennifer Lundelius and Nancy Lynch. A new fault-tolerant algorithm for clock synchronization. Technical Memo MIT/LCS/TM-265, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, 02139, July 1984. .pdf

Nancy Lynch and Greg N. Frederickson. The impact of synchronous communication on the problem of electing a leader in a ring. Technical Memo MIT/LCS/TM-259, Laboratory for Computer Science, Massachusetts Institute of Technology, April 1984. .pdf

Michael Merritt. Elections in the presence of faults. In Proceedings of the Third Annual ACM Symposium on Principles of Distributed Computing, pages 134--142, Vancouver, B.C., Canada, August 1984. .pdf

M. Merritt and J. Mitchell. A distributed algorithm for deadlock detection and resolution. In Proceedings of the Third Annual ACM Symposium on Principles of Distributed Computing, pages 282--284, Vancouver, B.C., Canada, August 1984. .pdf

Neil Joseph Savasta II. Implementation of a compiler-compiler. Bachelor's Thesis, June 1984, Massachusetts Institute of Technology. .pdf

E. W. Stark. Foundations of a Theory of Specification for Distributed Systems. Ph.D thesis, Massachusetts Institute of Technology, Laboratory for Computer Science, Cambridge, MA 02139, August 1984. Technical Report MIT/LCS/TR-342, Massachusetts Institute of Technology, Laboratory for Computer Science, Cambridge, MA 02139, August 1984. .pdf

Russell Turpin and Brian A. Coan. Extending binary Byzantine agreement to multivalued Byzantine agreement. Information Processing Letters, 18(2):73--76, February 1984. .pdf

Shmuel Zaks. Optimal Distributed Algorithms for Sorting and Ranking. Technical Report MIT-LCS-TM-261, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, May 1984..pdf

1983

Baruch Awerbuch and Shimon Even. A formal approach to a communication-network protocol; broadcast as a case study. Technical Report TR-284, Electrical Engineering Department, Technion-I.I.T., Haifa, June 1983. pdf

Eshrat Arjomandi, Michael J. Fischer, and Nancy A. Lynch. Efficiency of synchronous versus asynchronous distributed systems. Journal of the ACM, 30(3):449--456, July 1983. pdf

Danny Dolev, Cynthia Dwork, and Larry Stockmeyer. On the minimal synchronism needed for distributed consensus. In 24th Annual Symposium on Foundations of Computer Science, pages 393--402, Tucson, Arizona, 1983. pdf

Danny Dolev, Nancy A. Lynch, Shlomit S. Pinter, Eugene W. Stark, and William E. Weihl. Reaching approximate agreement in the presence of faults. In Proceedings of 3rd Symposium on Reliability in Distributed Software and Database Systems, pages d 145--154, October 1983. pdf

Danny Dolev and Nancy A. Lynch and Shlomit S. Pinter and Eugene W. Stark and William E. Weihl. Reaching Approximate Agreement in the Presence of Faults, Technical Memo MIT/LCS/TM-251, Massachusetts Institute of Technology, Laboratory for Computer Science, Cambridge, MA 02139, December 1983. pdf

Cynthia Dwork and Dale Skeen. The inherent cost of nonblocking commitment. In Proceedings of the Second Annual ACM Symposium on Principles of Distributed Computing, pages 1--11, Montreal, Quebec, Canada, August 1983. pdf

Michael Fischer, Nancy Lynch, James Burns, and Allan Borodin. The colored ticket algorithm. Technical Memo MIT/LCS/TM-269, Laboratory for Computer Science, Massachusetts Institute of Technology, August 1983. .pdf

Michael Fischer, Nancy Lynch, and Michael S. Paterson. Impossibility of distributed consensus with one faulty process. In Proceedings of the 2nd ACM Symposium on Principles of Database Systems, pages 1--7, Atlanta, GA, March 1983. .pdf

J. Goree. Internal consistency of a distributed transaction system with orphan detection. Master's thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA 02139, January 1983. Technical Memo MIT/LCS/TR-286, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, 1983. .pdf

Nancy Lynch and Michael Fischer. A technique for decomposing algorithms which use a single shared variable. Journal of Computer and System Sciences, 27(3):350--377, December 1983. .pdf

Nancy Lynch. Concurrency control for resilient nested transactions. In Proceedings of the Second ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, pages 166--181, Atlanta, Georgia, March 1983. .pdf

Nancy A. Lynch. Concurrency control for resilient nested transactions. MIT Laboratory for Computer Science Technical Report MIT/LCS/TR-285, Cambridge, MA 02139, February 1983. (Note, same TR number was used in 1985). .pdf

Nancy Lynch. Multilevel atomicity--a correctness criterion for database concurrency control. ACM Transactions on Database Systems, 8(4):484--502, December 1983. .pdf

1982

James E. Burns, Paul Jackson, Nancy A. Lynch, Michael J. Fischer, and Gary L. Peterson. Data requirements for implementation of N-process mutual exclusion using a single shared variable. Journal of the ACM, 29(1):183--205, January 1982.pdf

Danny Dolev, Michael J. Fischer, Rob Fowler, Nancy A. Lynch, and H. Raymond Strong. An efficient algorithm for Byzantine agreement without authentication. Information and Control, 52(3):257--274, March 1982. .pdf

Danny Dolev, Michael J. Fischer, Rob Fowler, Nancy A. Lynch, and H. Raymond Strong. An efficient Byzantine agreement without authentication. IBM Research Report RJ3428 (40914), Computer Science, IBM Research Division, Yorktown Heights, NY, March 22, 1982. .pdf

Richard A. DeMillo, Nancy A. Lynch, and Michael J. Merritt. Cryptographic protocols. In Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing, pages 383--400, San Francisco, California, May 1982. pdf

Michael J. Fischer, Nancy D. Griffeth, and Nancy A. Lynch. Global states of a distributed system. IEEE Transactions on Software Engineering, SE-8(3):198--202, May 1982..pdf

Michael J. Fischer and Nancy A. Lynch. A lower bound for the time to assure interactive consistency. Information Processing Letters, 14(4):183--186, June 1982. .pdf

Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson. Impossibility of distributed consensus with one faulty process. Technical Report MIT/LCS/TR-282, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, 02139, September 1982. pdf

Nancy Lynch, Michael Fischer, and Rob Fowler. A simple and efficient Byzantine generals algorithm. In Proceedings of the 2nd Symposium on Reliability in Distributed Software and Database Systems, pages 46--52, Pittsburgh, PA, July 1982. .pdf

Nancy Lynch, Michael Fischer, and Rob Fowler. A simple and efficient Byzantine generals algorithm. Technical Report GIT-ICS-82/02, School of Information and Computer Science, Georgia Institute of Technology, February, 1982. pdf

Nancy Lynch. Accessibility of values as a determinant of relative complexity of algebras. Journal of Computer and System Sciences, 24(1):101--113, February 1982. pdf

Nancy Lynch. Multilevel atomicity--a correctness criterion for database concurrency control. Technical Report MIT/LCS/TR-281, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, 02139, August 1982. pdf

Nancy A. Lynch. Multilevel atomicity. In Proceedings of the First ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, pages 63--69, Los Angeles, CA, March 1982. .pdf

1981

Eshrat Arjomandi, Michael J. Fischer, and Nancy A. Lynch. A difference in efficiency between synchronous and asynchronous systems. Technical Report GIT-ICS-81/07, School of Information and Computer Science, Georgia Institute of Technology, June, 1981. .pdf

Allan Borodin, Michael J. Fischer, David G. Kirkpatrick, Nancy A. Lynch, and Martin Tompa. A time-space tradeoff for sorting on non-oblivious machines. Journal of Computer and System Sciences, 22(3):351--364, June 1981. .pdf

A. Borodin, L. Guibas, N. Lynch, and A. Yao. Efficient searching using partial ordering. Information Processing Letters, 12(2):71--75, April 1981. .pdf

Michael J. Fischer, Leonidas Guibas, Nancy D. Griffeth, and Nancy Lynch. Optimal placement of identical resources in a distributed network. In Proceedings of the 2nd IEEE International Conference on Distributed Computing Systems, pages 324--336, April 1981. .pdf

Michael Fischer, Nancy Griffeth, and Nancy Lynch. Global states of a distributed system. In Proceedings of IEEE Symposium on Reliability in Distributed Software and Database Systems, pages 33--38, Pittsburgh, PA, July 1981. .pdf

Nancy Lynch. Multilevel atomicity--a correctness criterion for database concurrency control. Technical Report GIT-ICS-81/05, School of Information and Computer Science, Georgia Institute of Technology, May, 1981. .pdf

Michael Fischer, Nancy Griffeth, and Nancy Lynch. Global states of a distributed system. Technical Report GIT-ICS-81/06, School of Information and Computer Science, Georgia Institute of Technology, June, 1981. .pdf

Michael J. Fischer and Nancy A. Lynch. A lower bound for the time to assure interactive consistency. Technical Report GIT-ICS-81/13, School of Information and Computer Science, Georgia Institute of Technology, September, 1981. .pdf

Nancy A. Lynch. Upper bounds for static resource allocation in a distributed system. Journal of Computer and System Sciences, 23(2):254--278, October 1981. .pdf

Nancy Lynch and Edward K. Blum. Relative complexity of algebras. Mathematical Systems Theory 14, pages 193--214, 1981. .pdf

Nancy A. Lynch and Michael J. Fischer. On describing the behavior and implementation of distributed systems. Theoretical Computer Science, 13(1):17--43, 1981. Special issue on Semantics of Concurrent Computation. .pdf

1980

James Burns and Nancy A. Lynch. Mutual exclusion using indivisible reads and writes. In Proceedings of the 18th Allerton Conference on Communication, Control and Computing, pages 833--842, Monticello, IL, October 1980. .pdf

Michael J. Fischer, Leonidas Guibas, Nancy D. Griffeth, and Nancy Lynch. Optimal placement of identical resources in a distributed network. Technical Report GIT-ICS-80/13, School of Information and Computer Science, Georgia Institute of Technology, October, 1980. .pdf

Nancy A. Lynch. Fast allocation of nearby resources in a distributed system. In Proceedings of the Twelfth Annual ACM Symposium on Theory of Computing, pages 70--81, Los Angeles, CA., April 1980. Chosen for submission to special issue of Journal Computer and System Sciences.pdf

Nancy A. Lynch and Michael J. Fischer. On describing the behavior and implementation of distributed systems. Technical Report GIT-ICS-79/03, School of Information and Computer Science, Georgia Institute of Technology, March, 1980. Revised edition. pdf

Nancy Lynch and Michael Fischer. A technique for decomposing algorithms which use a single shared variable. Technical Report GIT-ICS-80/14, School of Information and Computer Science, Georgia Institute of Technology, October, 1980. pdf

Nancy A. Lynch. Straight-line program length as a parameter for complexity analysis. Journal of Computer and System Sciences, 21(3):251--280, December 1980. .pdf

Nancy A. Lynch and Edward K. Blum. Relative complexity of operations on numeric and bit-string algebras. Mathematical Systems Theory 13, pages 187--207, 1980. .pdf

TOC / CSAIL / MIT