Professor Nancy Lynch's Publications

Professor Nancy Lynch's Publications

Submitted for Publication

Sabrina Drammis, Karthik Srinivasan, Nancy Lynch, and Robert Ajemian. Building the Dual Graph of the Activation Regions in a Deep Neural Network: What it Means for Interpretability. Submitted for publication, 2025.

Noble Harasha and Nancy Lynch. Nanobot Algorithms for Treatment of Diffuse Cancer. Submitted for publication, 2025.

Nancy Lynch and Mark Tuttle. An Introduction to Input/Output Automata, republished after 36 years. Submitted for publication, 2025.

To Appear

Noble Harasha, Cristina Gava, Nancy Lynch, Claudia Contini, and Frederik Mallmann-Trenn. Modeling Feasible Locomotion of Nanobots for Cancer Detection and Treatment. To appear in the Proceedings of the National Academy of Sciences, 2025.

2025

Noble Harasha and Nancy Lynch. Nanobot Algorithms for Treatment of Diffuse Cancer. arXiv:2509.06893, September 2025.

Noble Harasha, Cristina Gava, Nancy Lynch, Claudia Contini, and Frederik Mallmann-Trenn. Modeling Feasible Locomotion of Nanobots for Cancer Detection and Treatment. arXiv:2507.12400, July 2025.

Nancy Lynch. Multi-Neuron Representations of Hierarchical Concepts in Spiking Neural Networks. arXiv:2401.04628v3, March 2025.

Nancy Lynch. Using Single-Neuron Representations for Hierarchical Concepts as Abstractions of Multi-Neuron Representations. arXiv:2406.07297v2, March 2025.

Nancy Lynch. Building a Theory of Distributed Systems: Work by Nancy Lynch and Collaborators. arXiv:2502.20468, February 27, 2025.

Mien Brabeeba Wang, Nancy Lynch and Michael Halassa. Coordinating Control and Planning for Navigation on Simplicial Complex Attractors. 22nd Annual Computational and Systems Neuroscience Conference (COSYNE 2025), Montreal, Canada, March 2025. Poster

Mien Brabeeba Wang, Nancy Lynch, Michael Halassa. The neural basis for uncertainty processing in hierarchical decision making. Nature Communications, 16, Article number 9096, 2025. Publishers site.

2024

Adithya Balachandran, Noble Harasha, and Nancy Lynch. Swarm Algorithms for Dynamic Task Allocation in Unknown Environments. SuperUROP Writeup, May 2024. .pdf

Adithya Balachandran, Noble Harasha, and Nancy Lynch. Swarm Algorithms for Dynamic Task Allocation in Unknown Environments. arXiv:2409.09550, September 2024.

Sabrina Drammis, Nancy Lynch, Alexander Friedman. The functional role of the striatum as an action evaluation circuit: a network-level theory. 10th Workshop on Biological Distributed Algorithms (BDA), Nantes, France, June, 2024.

Sabrina Drammis, Bowen Zheng, Karthik Srinivasan, Robert C. Berwick, Nancy A. Lynch, Robert Ajemian. Parallel Algorithms for Exact Enumeration of Deep Neural Network Activation Regions. arXiv:2403.00860, February 29, 2024.

Noble Harasha, Cristina Gava, Nancy Lynch, Claudia Contini, Frederik Mallmann-Trenn. Modeling Feasible Locomotion of Nanobots for Cancer Detection and Treatment. 10th Workshop on Biological Distributed Algorithms (BDA), Nantes, France, June, 2024. .pdf

Nancy Lynch. Abstraction in Neural Networks. arXiv:2408.02125, August 2024.

Nancy Lynch. Using Single-Neuron Representations for Hierarchical Concepts as Abstractions of Multi-Neuron Representations. arXiv:2406.07297, April 2024.

Nancy Lynch. Multi-Neuron Representations of Hierarchical Concepts in Spiking Neural Networks. arXiv:2401.04628v2, April 2024.

Nancy Lynch. Multi-Neuron Representations of Hierarchical Concepts in Spiking Neural Networks. arXiv:2401.04628, January 2024. Errata.

Nancy Lynch and Frederik Mallmann-Trenn. Learning Hierarchically Structured Concepts. arXiv:1909.04559v6, February 2024.

Mien Brabeeba Wang, Nancy Lynch and Michael Halassa. Theory and model of thalamocortical processing in decision making under uncertainty. Thalamocortical Interactions Gordon Research Conference 2024, Ventura, California, February 2024. Abstract, Poster.

Mien Brabeeba Wang, Nancy Lynch, and Michael Halassa. Computational Insights into Schizophrenia: Linking Hyperactive D2 Receptors with Belief Updating Impairments. 10th Workshop on Biological Distributed Algorithms (BDA), Nantes, France, June 2024. .pdf

Mien Brabeeba Wang, Nancy Lynch, Michael Halassa. Coglink networks reveal computational mechanisms of uncertainty management and its perturbation in schizophrenia. Neuroscience 2024, Chicago, IL, October 2024. Poster

2023

Grace Cai, Noble Harasha, and Nancy Lynch. A Comparison of New Swarm Task Allocation Algorithms in Unknown Environments with Varying Task Density. Proceedings of the 22nd International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2023), London, United Kingdom, May 29 June 2, 2023. .pdf Also, arXiv:2212.00844v3, February 2023.

Grace Cai, Noble Harasha, and Nancy Lynch. A Comparison of New Swarm Task Allocation Algorithms in Unknown Environments with Varying Task Density. arXiv:2212.00844v3, February 2023.

Matteo Castellani, Emily Toomey, Andres E. Lombo, Jesus Lares, Marco Colangelo, Chi-Ning Chou, Ken Segall, Nancy Lynch, and Karl K. Berggren. A Superconducting Platform for Energy-efficient Spiking Neural Networks. Poster Session. MIT AI Hardware Program 2023 Symposium, Cambridge, MA, April 2023. .pdf

Zhi Wei Gan, Grace Cai, Noble Harasha, Nancy Lynch, and Julian Shun. ParSwarm: A C++ Framework for Evaluating Distributed Algorithms for Robot Swarms. Advanced tools, programming languages, and PLatforms for Implementing and Evaluating algorithms for Distributed systems (APPLIED Workshop),, Orlando, Florida, June 2023. .pdf

Nancy Lynch and Frederik Mallmann-Trenn. Learning Hierarchically-Structured Concepts II: Overlapping Concepts, and Networks With Feedback. Invited Paper. 30th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2023), Alcala de Henares, Spain, June 2023. Also, arXiv:2304.09540, April 2023.

Nancy Lynch and Frederik Mallmann-Trenn. Learning Hierarchically-Structured Concepts II: Overlapping Concepts, and Networks With Feedback. arXiv:2304.09540, April 2023.

Nancy Lynch and Frederik Mallmann-Trenn. Learning Hierarchically-Structured Concepts II: Overlapping Concepts, and Networks With Feedback. arXiv:2304.09540v2, July 2023.

Mien Brabeeba Wang, Nancy Lynch, and Michael Halassa. The contribution of distributional activities of dopamine in the exploration. 9th workshop on Biological Distributed Algorithms (BDA), Orlando, Florida, June 2023. .pdf

2022

Grace Cai and Nancy Lynch. A Geometry-Sensitive Quorum Sensing Algorithm for the Best-of-N Site Selection Problem. Thirteenth International Conference on Swarm Intelligence (ANTS 2022), Malaga, Spain, November 2022. .pdf Also, arXiv:2206.00587, June 2022.

Grace Cai and Nancy Lynch. A Geometry-Sensitive Quorum Sensing Algorithm for the Best-of-N Site Selection Problem. arXiv: 2206.00587, June 2022.

Grace Cai, Noble Harasha, and Nancy Lynch. A Comparison of New Swarm Task Allocation Algorithms in Unknown Environments with Varying Task Density. arXiv:2212.00844v2, December 2022.

Andres E. Lombo, Jesus E. Lares, Matteo Castellani, Chi-Ning Chou, Nancy Lynch, Karl K. Berggren. A Superconducting Nanowire-based Architecture for Neuromorphic Computing. Neuromorphic Computing and Engineering, 2(3), September 2022. .pdf Selected as a Highlight of NCE for 2022. Also, arXiv:2112.08928v2, August 2022.

Andres E. Lombo, Jesus E. Lares, Matteo Castellani, Chi-Ning Chou, Nancy Lynch, Karl K. Berggren. A Superconducting Nanowire-based Architecture for Neuromorphic Computing. arXiv:2112.08928v2, August 2022. Software Repository

Nancy Lynch. State Machines. August 2022. Chapter from MIT's course notes for two Discrete Math courses, 6.120 and 6.120A. .pdf

Nancy Lynch. Symbolic Knowledge Structures and Intuitive Knowledge Structures. arXiv:2206.02932, June 2022.

Nancy Lynch and Cameron Musco. A Basic Compositional Model for Spiking Neural Networks. In Jansen, N., Stoelinga, M., van den Bos, P., editors, A Journey from Process Algebra via Timed Automata to Model Learning: Essays Dedicated to Frits Vaandrager on the Occasion of His 60th Birthday, September 2022, volume 13560 of Lecture Notes in Computer Science, Springer, 2022. Springer Link. Also, arXiv: 1808.03884v3, October 2022.

Nancy Lynch and Cameron Musco. A Basic Compositional Model for Spiking Neural Networks. arXiv: 1808.03884v3, October 2022.

Keith Murray, Brabeeba Wang, and Nancy Lynch. Emergence of direction-selective retinal cell types in task-optimized deep learning models Journal of Computational Biology,, 29(4):370-381, April 2022. .pdf Publisher site

Nicolas Nicolau, Viveck Cadambe, N. Prakash, Andria Trigeorgi, Kishori M. Konwar, Muriel Medard, and Nancy Lynch. ARES: Adaptive, Reconfigurable, Erasure coded, Atomic Storage. ACM Transactions on Storage, 18(4), November 2022. .pdf

Emily Zhang, Jiajia Zhao, Nancy Lynch. An Upper and Lower Bound for the Convergence Time of House-Hunting in Temnothorax Ant Colonies. Journal of Computational Biology, 29(4):344-357, April 2022. .pdf Publisher site

Jiajia Zhao, Nancy Lynch, and Stephen C. Pratt. The Power of Population Effect in Temnothorax Ants House-Hunting: A Computational Modeling Approach. Journal of Computational Biology, published online, January 2022. .pdf

2021

Viveck R. Cadambe, Nicolas C. Nicolaou, Kishori M. Konwar, N. Prakash, Nancy A. Lynch, and Muriel Medard. ARES: Adaptive, Reconfigurable, Erasure coded, atomic Storage. arXiv:1805.03727v2, May 2021.

Grace Cai, Wendy Wu, Wayne Zhao, Jiajia Zhao, and Nancy Lynch. A Spatially-Dependent Probabilistic Model for House-Hunting in Ant Colonies. arXiv:2106.06867, June 2021.

Kishori Konwar, Wyatt Lloyd, Haonan Lu, and Nancy Lynch. SNOW Revisited: Understanding When Ideal READ Transactions Are Possible. arXiv 1811.10577v2, May, 2021

Kishori Konwar, Wyatt Lloyd, Haonan Lu, and Nancy Lynch. SNOW Revisited: Understanding When IdealREAD Transactions Are Possible 35th IEEE International Parallel and Distributed Processing Symposium (IPDPS), Portland, Oregon USA, pages 922-931, May 17-21, 2021. .pdf

Jesus Lares. Simulating superconducting nanowire neuron networks with Python and SPICE. Super-UROP paper, June, 2021.

Andres E. Lombo, Jesus E. Lares, Matteo Castellani, Chi-Ning Chou, Nancy Lynch, Karl K. Berggren. A Superconducting Nanowire-based Architecture for Neuromorphic Computing. arXiv:2112.08928v1, December, 2021.

Nancy Lynch and Frederik Mallmann-Trenn. Learning Hierarchically Structured Concepts. Neural Networks, 143:798-817, November 2021. .pdf Errata. Also, arxiv:1909.04559v5, September 2021.

Nancy Lynch and Frederik Mallmann-Trenn. Learning Hierarchically Structured Concepts. arxiv:1909.04559v5, September 2021.

Nancy Lynch and Frederik Mallmann-Trenn. Learning Hierarchically Structured Concepts. arxiv:1909.04559v4, January 2021.

Nancy Lynch and Cameron Musco. A Basic Compositional Model for Spiking Neural Networks. arxiv:1808.03884v2, April 2021. Also, submitted for journal publication. Abbreviated version submitted for conference publication.

Keith Murray, Brabeeba Wang, and Nancy Lynch. Task-Optimized Retinal-Inspired CNN Converges to Biologically-Plausible Functionality. 8th Workshop on Biological Distributed Algorithms (BDA), July 2021. .pdf

Keith T. Murray, Brabeeba Wang, and Nancy Lynch. Task-optimized retina-inspired CNN converges to biologically-plausible functionality. MIT Super-UROP paper, June 2021. .pdf

Jiajia Zhao, Lili Su, Nancy Lynch. Lack of Quorum Sensing Leads to Failure of Consensus in Temnothorax Ant Emigration. In Colette Johnen, Elad Michael Schiller, Stefan Schmid, editors, 23rd International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2021), Virtual Event, volume 13046 of Lecture Notes in Computer Science, pages 209-228, November, 2021. .pdf

Emily Zhang, Jiajia Zhao, Nancy Lynch. A Model and Analysis of House-Hunting in Ant Colonies. 8th Workshop on Biological Distributed Algorithms (BDA), July 2021. .pdf

Emily Y. Zhang, Jiajia Zhao, and Nancy Lynch. A Distributed Consensus Model for House-Hunting in Temnothorax Ant Colonies. MIT Super-UROP paper, June 2021. .pdf

Jiajia Zhao, Nancy Lynch, and Stephen C. Pratt. The Power of Social Information in Ant-Colony House-Hunting: A Computational Modeling Approach. 8th Workshop on Biological Distributed Algorithms (BDA), July 2021. .pdf

Jiajia Zhao, Nancy Lynch, and Stephen C. Pratt. The Power of Social Information in Ant-Colony House-Hunting: A Computational Modeling Approach. bioRxiv doi: https://doi.org/10.1101/2020.10.07.328047, April 2021. Also, Journal of Computational Biology, published online January 2022. .pdf

2020

Bertie Ancona, Ayesha Bajwa, Nancy Lynch and Frederik Mallmann-Trenn. How to Color a French Flag: Biologically Inspired Algorithms for Scale-Invariant Patterning. Proceedings of the Latin American Theoretical Informatics Symposium (LATIN 2020), Sao Paulo, Brazil, May 2020. .pdf

Anna R. Dornhaus, Nancy A. Lynch, Frederik Mallmann-Trenn, Dominik Pajak, and Tsvetomira Radeva. Self-Stabilizing Task Allocation in Spite of Noise. 32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), Philadelphia, PA, July 2020. .pdf

Seth Gilbert, Nancy Lynch, Calvin Newport, and Dominik Pajak. On Simple Back Off in Unreliable Radio Networks. Theoretical Computer Science,, 806(2):489-508, February 2020. .pdf

Magnus M. Halldorsson, Stephan Holzer, Evangelia Anna Markatou, and Nancy Lynch. Leader Election in SINR Model with Arbitrary Power Control. Theoretical Computer Science, 811(2):21-28, April 2020. .pdf Published online January 23, 2019.

Yael Hitron, Nancy Lynch, Cameron Musco, and Merav Parter. Random Sketching, Clustering, and Short-Term Memory in Spiking Neural Networks. 11th Innovations in Theoretical Computer Science (ITCS 2020), Seattle, Washington, January 2020. .pdf

Nancy Lynch and Frederik Mallmann-Trenn. Learning Hierarchically Structured Concepts. arxiv:1909.04559v2, February 2020.

Nancy Lynch and Frederik Mallmann-Trenn. Learning Hierarchically Structured Concepts. arxiv:1909.04559v3, September 2020.

Emily Toomey, Ken Segall, Matteo Castellani, Marco Colangelo, Nancy Lynch, and Karl K. Berggren. A superconducting nanowire spiking element for neural networks, Nano Letters, October 2020. DOI 10.1021/acs.nanolett.0c03057. ACS Articles on Request. Also, arXiv:2007:15101, July 2020.

Emily Toomey, Ken Segall, Matteo Castellani, Marco Colangelo, Nancy Lynch, and Karl K. Berggren. A superconducting nanowire spiking element for neural networks, arXiv:2007:15101, July 2020.

Brabeeba Wang and Nancy Lynch. Integrating Temporal Information to Spatial Information in a Neural Circuit. arXiv:1903.01217v3, June 2020.

Jiajia Zhao, Nancy Lynch, and Stephen C. Pratt. A Comprehensive and Predictive Agent-based Model for Collective House-Hunting in Ant Colonies. bioRxiv doi: https://doi.org/10.1101/2020.10.07.328047, October 2020.

2019

Alberto Ancona, Ayesha Bajwa, Nancy A. Lynch, and Frederik Mallmann-Trenn. How to Color a French Flag-Biologically Inspired Algorithms for Scale-Invariant Patterning. In Keren Censor-Hillel, Michele Flammini, editors, Proceedings of the 26th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2019), L'Aquila, Italy, July 2019, volume 11639 of Lecture Notes in Computer Science, pages 327-331, Springer 2019. .pdf

Alberto Ancona, Ayesha Bajwa, Nancy A. Lynch, and Frederik Mallmann-Trenn. How to Color a French Flag-Biologically Inspired Algorithms for Scale-Invariant Patterning. 7th Workshop on Biological Distributed Algorithms (BDA), Toronto, Canada, July 2019. Also, arXiv:1905.00342, May 2019.

Alberto Ancona, Ayesha Bajwa, Nancy A. Lynch, and Frederik Mallmann-Trenn. How to Color a French Flag-Biologically Inspired Algorithms for Scale-Invariant Patterning. arXiv:1905.00342, May 2019.

Viveck R. Cadambe, Nicolas C. Nicolaou, Kishori M. Konwar, N. Prakash, Nancy A. Lynch, and Muriel Medard. ARES: Adaptive, Reconfigurable, Erasure coded, atomic Storage. 39th IEEE International Conference on Distributed Computing Systems (ICDCS 2019), Dallas, Texas, July 2019. .pdf. Also, arXiv:1805.03727v1, May 2018.

Anna Dornhaus, Nicole Leitner, Nancy Lynch, Frederik Mallmann-Trenn, and Dominik Pajak. Remember the Past and Forget Thresholds. 7th Workshop on Biological Distributed Algorithms (BDA), Toronto, Canada, July 2019. .pdf

Kishori Konwar, N. Prakash, Muriel Medard, and Nancy Lynch. Fast Lean Erasure-coded Atomic Memory Object. 23rd International Conference On Principles Of Distributed Systems (OPODIS 2019), Neuchatel, Switzerland, December 2019. .pdf Publisher site

Nancy Lynch, Cameron Musco, and Merav Parter. Winner-Take-All Computation in Spiking Neural Networks. arXiv:1904.12591, April 2019.

Nancy Lynch and Frederik Mallmann-Trenn. Learning of Hierarchically Structured Concepts. New version in progress, 2019. See arxiv:1909.04559v1, September 2019.

Cameron Musco, Hsin-Hao Su, and Nancy Lynch. Ant-Inspired Density Estimation via Random Walks. ArXv:1603.02981, v2, January 2019.

Lili Su, Chia-Jung Chang, Nancy Lynch. Spike-Based Winner-Take-All Computation: Fundamental Limits and Order-Optimal Circuits. Neural Computation,, 31(12), December 2019 published online. .pdf Journal version Also, arXiv:1904.10399.

Lili Su, Martin Zubeldia, and Nancy Lynch. Collaboratively Learning the Best Option on Graphs, Using Bounded Local Memory. ACM SIGMETRICS 2019, Phoenix, Arizona, June 2019. .pdf Also, arXiv:1811.03968v3, December 2018.

Lili Su, Chia-Jung Chang and Nancy Lynch. Spike-Based Winner-Take-All Computation: Fundamental Limits and Order-Optimal Circuits. 7th Workshop on Biological Distributed Algorithms (BDA), Toronto, Canada, July 2019. .pdf

Lili Su, Chia-Jung Chang, Nancy Lynch. Spike-Based Winner-Take-All Computation: Fundamental Limits and Order-Optimal Circuits. arXiv:1904.10399, April, 2019.

Lili Su, Martin Zubeldia, and Nancy Lynch. Collaboratively Learning the Best Option on Graphs, Using Bounded Local Memory. POMACS, 3(1):11:1-11:32, 2019. .pdf

Mien Brabeeba Wang and Nancy Lynch. Integrating Temporal Information to Spatial Information in a Neural Circuit. 7th Workshop on Biological Distributed Algorithms (BDA), Toronto, Canada, July 2019. .pdf

Brabeeba Wang and Nancy Lynch. Brief Announcement: Integrating Temporal Information to Spatial Information in a Neural Circuit. 33rd International Symposium on Distributed Computing (DISC), Budapest, Hungary, October 2019. .pdf

Brabeeba Wang and Nancy Lynch. Integrating Temporal Information to Spatial Information in a Neural Circuit. arXiv:1903.01217v2, July 2019.

2018

Ran Canetti, Ling Cheung, Dilsun Kaynar, Moses Liskov, Nancy Lynch, Olivier Pereira, and Roberto Segala. Task-Structured Probabilistic I/O Automata. Journal of Computer and System Sciences, volume 94, pages 63-97, 2018. .pdf

Viveck R. Cadambe, Nicolas C. Nicolaou, Kishori M. Konwar, N. Prakash, Nancy A. Lynch, and Muriel Medard. ARES: Adaptive, Reconfigurable, Erasure coded, atomic Storage. arXiv:1805.03727v1, May 2018.

Anna R. Dornhaus, Nancy A. Lynch, Frederik Mallmann-Trenn, Dominik Pajak, and Tsvetomira Radeva. Self-Stabilizing Task Allocation In Spite of Noise. 6th Workshop on Biological Distributed Algorithms (BDA), London, UK, July, 2018. .pdf

Anna R. Dornhaus, Nancy A. Lynch, Frederik Mallmann-Trenn, Dominik Pajak, and Tsvetomira Radeva. Self-Stabilizing Task Allocation In Spite of Noise. arxiv 1805.03691v2, May 2018.

Seth Gilbert, Nancy Lynch, Calvin Newport, and Dominik Pajak. On Simple Back-Off in Unreliable Radio Networks. The 22nd International Conference on Principles of Distributed Systems (OPODIS 2018), Hong Kong, December 2018. .pdf Best Paper Award.

Seth Gilbert, Nancy A. Lynch, Calvin Newport, and Dominik Pajak. On Simple Back-Off in Unreliable Radio Networks. arxiv 1803.02216v1, March 2018.

Seth Gilbert, Nancy A. Lynch, Calvin Newport, and Dominik Pajak. On Simple Back-Off in Unreliable Radio Networks. arxiv 1803.02216v2, May 2018.

Seth Gilbert, Nancy A. Lynch, Calvin Newport, and Dominik Pajak. On Simple Back-Off in Unreliable Radio Networks. arxiv 1803.02216v3, December 2018.

Seth Gilbert, Nancy A. Lynch, Calvin Newport, and Dominik Pajak. Brief Announcement: On Simple Back-Off in Unreliable Radio Networks. 32nd International Symposium on Distributed Computing (DISC 2018), New Orleans, LA, October 2018. .pdf

Kishori Konwar, Wyatt Lloyd, Haonan Lu, and Nancy Lynch. The SNOW Theorem Revisited. arXiv 1811.10577v1, November 2018.

Nancy Lynch and Cameron Musco. A Basic Compositional Model for Spiking Neural Networks. arXiv:1808.03884v1, August 2018.

Lili Su, Martin Zubeldia, and Nancy Lynch. Collaboratively Learning the Best Option on Graphs, Using Bounded Local Memory. arXiv:1811.03968v3, December 2018.

Lili Su, Martin Zubeldia, and Nancy Lynch. Collaboratively Learning the Best Option, Using Bounded Memory. arXiv:1802.08159v2, March 2018.

Lili Su, Martin Zubeldia, and Nancy Lynch. Collaboratively Learning the Best Option, Using Bounded Memory. arXiv:1802.08159v3, November 2018.

2017

Viveck R. Cadambe, Nancy Lynch, Muriel Medard and Peter Musial. A Coded Shared Atomic Memory Algorithm for Message Passing Architectures. Distributed Computing, 30(1):49-73, February 2017. .pdf

Magnus Halldorsson, Fabian Kuhn, Nancy lynch, and Calvin Newport. An Efficient communication Abstraction for Dense Wireless Networks. 31st International Symposium on Distributed Computing (DISC 2017), Vienna Austria, October, 2017. .pdf

Stephan Holzer and Nancy Lynch. Beeping a Maximal Independent Set Fast. arXiv:1704.07133, April 2017. Slightly revised version, May 8th, 2017 .pdf

Kishori M Konwar, N. Prakash, Muriel Medard and Nancy Lynch. A Layered Architecture for Erasure-Coded Consistent Distributed Storage. ACM Symposium on the Principles of Distributed Computing (PODC 2017), Washington, DC, July 2017. .pdf

Christoph Lenzen, Nancy Lynch, Calvin Newport, and Tsvetomira Radeva. Searching without Communicating: Tradeoffs Between Performance and Selection Complexity. Distributed Computing, 30(3):169-191, 2017. .pdf

Nancy Lynch, Cameron Musco, and Merav Parter. Neuro-RAM Unit with Applications to Similarity Testing and Compression in Spiking Neural Networks. 31st International Symposium on Distributed Computing (DISC 2017), Vienna Austria, October 2017. arXiv:1706.01382v2, August 2017.

Cameron Musco, and Hsin-Hao Su, and Nancy A. Lynch. Ant-Inspired Density Estimation via Random Walks. Proceedings of the National Academy of Sciences, 114(40):10534-10541, October, 2017. Final submission version .pdf PNAS version.

Nancy Lynch, Cameron Musco, and Merav Parter. Neuro-RAM Unit with Applications to Similarity Testing and Compression in Spiking Neural Networks. arXiv:1706.01382v2, August 2017.

Nancy Lynch, Cameron Musco, and Merav Parter. Spiking Neural Networks: An Algorithmic Perspective. 5th Workshop on Biological Distributed Algorithms (BDA 2017), Washington, DC, July 2017. .pdf

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

Tsvetomira Radeva, Anna Dornhaus, Nancy Lynch, Radhika Nagpal, and Hsin-Hao Su. Costs of task allocation with local feedback: effects of colony size and extra workers in social insects and other multi-agent systems. PLOS Computational Biology, 13(12):e1005904, December 2017. .pdf. Also, https://doi.org/10.1371/journal.pcbi.1005904

Tsvetomira Radeva, Cameron Musco, and Nancy Lynch. New Perspectives on Algorithmic Robustness Inspired by Ant Colony House-Hunting. 5th Workshop on Biological Distributed Algorithms (BDA 2017), Washington, DC, July 2017. .pdf

Hsin-Hao Su, Lili Su, Anna Dornhaus, and Nancy Lynch. Ant-Inspired Dynamic Task Allocation via Gossiping. In Paul G. Spirakis, Philippas Tsigas, 19th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2017), Boston, MA, November 2017, volume 10616 of Lecture Notes in Computer Science, pages 157-171, Springer 2017. .pdf

Hsin-Hao Su, Lili Su, Anna Dornhaus, and Nancy Lynch. Ant-Inspired Dynamic Task Allocation via Gossiping. 5th Workshop on Biological Distributed Algorithms (BDA 2017), Washington, DC, July 2017. (Short-version) .pdf

2016

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, April 2016. Earlier version in Technical Report MIT-CSAIL-TR-2013-015, Computer Science and Artificial Intelligence Laboratory, Cambridge, MA 02139, July 2013. .pdf

Paul C. Attie and Nancy A. Lynch. Dynamic Input/Output Automata: a Formal and Compositional Model for Dynamic Systems. arxiv:1604.06030, April 2016.

Stephan Holzer and Nancy Lynch. Brief Announcement - Beeping a Maximal Independent Set Fast. 30th International Symposium on Distributed Computing (DISC 2016), Paris, France, September 2016. .pdf

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), May 2016. .pdf Also, arXiv:1605.01748, May 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. arXiv:1605.01748, May 2016.

Kishori Konwar, Nancy Lynch, Muriel Medard and Prakash Narayana Moorthy. RADON: Repairable Atomic Data Object in Networks. Proceedings of the 20th International Conference on Principles of Distributed Systems (OPODIS 2016), Madrid, Spain, December 2016. .pdf Also, arXiv:1605.05717v2, November 2016.

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

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

Nancy Lynch, Cameron Musco, and Merav Parter. Computational Tradeoffs in Biological Neural Networks: Self-Stabilizing Winner-Take-All Networks. arXiv 1610.02084, October 2016.

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

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. .pdf Also, arxiv.org/abs/1603.02981v1, March 2016.

Cameron Musco, Hsin-Hao Su, and Nancy Lynch. Ant-Inspired Density Estimation via Random Walks. arxiv 1603.02981v1, March 2016.

Zhiying Wang, Viveck R. Cadambe 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, July 2016. .pdf Also, arXiv:1605.06844v2, May 2016.

Zhiying Wang, Viveck R. Cadambe and Nancy Lynch. Information-Theoretic Lower Bounds on the Storage Cost of Shared Memory Emulation. arXiv:1605.06844v2, May 2016.

2015

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. .pdf Also, arXiv:1508.03660, August 2015.

Keren Censor-Hillel, Erez Kantor, Nancy Lynch and Merav Parter. Computing in Additive Networks with Bounded-Information Codes. arXiv:1508.03660, August 2015.

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. .pdf 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 arxiv.org/pdf/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

Anna Dornhaus, 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. .pdf

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, May 2015.

Mohsen Ghaffari, Cameron Musco, Tsvetomira Radeva, Nancy Lynch. Distributed House-Hunting in Ant Colonies. arXiv:1505.03799, May 2015.

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 109-118, July 2015. .pdf. Also, arxiv:1505.04514, May 2015.

Magnus Halldorsson, Stephan Holzer and Nancy Lynch. A Local Broadcast Layer for the SINR Network Model. arxiv:1505.04514, May 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:1502.02538v2, February 2015.

Nancy Lynch and Srikanth Sastry. Consensus using Asynchronous Failure Detectors. arxiv:1502.02538v2, February 2015.

2014

Viveck R. Cadambe, Nancy Lynch, Muriel Medard, and Peter Musial. Coded Emulation of Shared Atomic Memory for Message Passing Architectures. The 13th IEEE International Symposium on Network Computing and Applications (IEEE NCA14), Cambridge, MA, 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, arXiv:1407.4167, July 2014.

Viveck R. Cadambe, Nancy Lynch, Muriel Medard, and Peter Musial. A Coded Shared Atomic Memory Algorithm for Message Passing Architectures. arXiv:1407.4167, July 2014.

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

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

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. arxiv:1405.1671, May 2014.

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, 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

2013

Dan Alistarh, Alejandro Cornejo, Mohsen Ghaffari, and Nancy Lynch. Firefly Synchronization with Asynchronous Wake-up. First Workshop on Biological Distributed Algorithms (BDA 2013), Jerusalem, Israel, October 2013. .pdf slides

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. .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

Keren Censor-Hillel, Bernhard Haeupler, Nancy Lynch, and Muriel Medard. Bounded-Contention Coding for Wireless Networks in the High SNR Regime. Submitted for journal publication. Earlier version 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, Seth Gilbert, Fabian Kuhn, Nancy Lynch and Calvin Newport. Structuring Unreliable Radio Networks. Submitted for journal publication. Earlier version in Proceedings of the 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, San Jose, California, June 6-8, 2011. .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).

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, pages 345-354, Montreal Canada, July 2013. .pdf

2012

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 arxiv.org/abs/1208.6125, August 2012.

Keren Censor-Hillel, Bernhard Haeupler, Nancy Lynch, and Muriel Medard. Bounded-Contention Coding for Wireless Networks in the High SNR Regime. arxiv.org/abs/1208.6125, August 2012.

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

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

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

Mohsen Ghaffari, Bernhard Haeupler, Nancy Lynch, and 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

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

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

2011

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

Keren Censor-Hillel, Seth Gilbert, Fabian Kuhn, Nancy Lynch and Calvin Newport. Structuring Unreliable Radio Networks. 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

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

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

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

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

Fabian Kuhn, Nancy Lynch, and Calvin Newport. The Abstract MAC Layer. Distributed Computing, 24(3):187-206, 2011. Special issue from DISC 2009 23rd International Symposium on Distributed Computing. .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

Calvin Newport and Nancy Lynch. Modeling Radio Networks. Distributed Computing, 24(2):101-118, October, 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, 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

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 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

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

Disun 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, 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 and Rotem Oshman. Distributed Computation in Dynamic Networks. Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC 2010), Cambridge, MA, pages 513-522, June 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

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

Alejandro Cornejo, Nancy Lynch, Saira Viqar, Jennifer Welch. Neighbor Discovery in Mobile Ad Hoc Networks 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

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

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, 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, 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, Nancy Lynch, and Calvin Newport. The Abstract MAC Layer. In I. Keidar, editor, Distributed Computing: 23rd International Symposium on Distributed Computing (DISC 2009), Elche/Elx, Spain, September 23-25, 2009.. volume 5805 of Lecture Notes in Computer Science, pages 48-62, 2010. 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.

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, 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

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. Best Paper Award..pdf.

2008

Myla Archer, Hongpong 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

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

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

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.

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. (Appeared online February 2008). Springer. .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), Toronto, Canada, pages 233-242, 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

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

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

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

2007

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, 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, 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, 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

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

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

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 and Nancy Lynch. Proving approximate implementations 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 for 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. Springer, 2007. .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

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, 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

Ling Cheung, Nancy Lynch, Roberto Segala, and Frits Vaandrager. Switched PIOA: Parallel Composition via Distributed Scheduling. Theoretical Computer Science, 365(1-2):83-108, November 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

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, volume 18, number 4, pages 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

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

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

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

2005

Paul Attie, Rachid Guerraoui, Petr Kouznetsov, Nancy Lynch, and Sergio Rajsbaum. The Impossibility of Boosting Distributed Service Resilience. 25th 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

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.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, 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

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, Nancy Lynch, Sayan Mitra, and Joshua Tauber. Proving Atomicity: An Assertional Approach. Technical Report MIT-LCS-TR-995, MIT CSAIL, Cambridge, MA, July 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), Pisa, Italy, December 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, 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, page 323, July, 2005. .pdf

Shlomi Dolev, Limor Lahiani, Nancy Lynch, and Tina Nolte. Self-Stabilizing Mobile Node Location Management and Message Routing. 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. Virtual Stationary Automata for Mobile Networks (Extended Abstract) Technical Report MIT-LCS-TR-979, MIT CSAIL, Cambridge, MA 02139, January 2005. .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. .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, 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, 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

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. Using Virtual Nodes to Coordinate the Motion of Mobile Nodes. CDC-ECC 2005: Forty-Fourth IEEE Conference on Decision and Control and European Control Conference, Seville, Spain, December 2005. Invited paper. .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

2004

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. .pdf .ps

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, 8th International Conference on Principles of Distributed Systems (OPODIS 2004), 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), page 378, St. John's, Newfoundland, Canada, page 378, July 25-28, 2004. .pdf .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. .pdf .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 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

Seth Gilbert, Nancy Lynch, and Alex Shvartsman. RAMBO II: Rapidly Reconfigurable atomic memory for dynamic networks. 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 .ps 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

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

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. .pdf .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. .pdf .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

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. .pdf .ps

2003

Paul C. Attie and Nancy A. Lynch. Dynamic Input/Output Automata: a Formal and Compositional 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

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. Distributed Computing, 17th International Symposium on Distributed Computing (DISC 2003), 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. .pdf .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 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

Stephen Garland, Nancy Lynch, Joshua Tauber, and Mandana Vaziri. IOA User Guide and Reference Manual. Technical Report MIT-LCS-TR-961, MIT Laboratory for Computer Science, Cambridge, MA, August 14, 2003. .pdf

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

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. .pdf .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. .pdf .ps

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

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 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. .pdf Also, Technical Report MIT-LCS-TR-827d, MIT Laboratory for Computer Science, Cambridge, MA 02139, January 13, 2003.

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

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

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), NewYork, NY, USA, January 9-11, 2003, volume 2575 of Lecture Notes in Computer Science, pages 283-297, Springer-Verlag, 2003. .pdf .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

2002

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, 02139, December 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.

Roberto De Prisco, Nancy Lynch, Alexander Shvartsman, Nicole Immorlica, and Toh Ne Win. A Formal Treatment of Lamport's Paxos Algorithm. Manuscript, October 2002. .pdf

Seth Gilbert and Nancy Lynch. Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services. SIGACT News, 33(2):48-51, June 2002. .pdf .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, 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

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

Nancy Lynch, Dahlia Malkhi, David Ratajczak. Atomic Data Access in Distributed Hash Tables. 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. 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. .pdf .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. .pdf .ps

Nancy Lynch and Alex Shvartsman. Communication and Data Sharing for Dynamic Distributed Systems. In A. Schiper et al, editors, Future Directions in Distributed Computing, Research and Position Papers, volume 2584 of Lecture Notes in Computer Science, pages 62-67, Springer-Verlag, 2003. (Originally in FuDiCo 2002: Proceedings of the International Workshop on Future Directions in Distributed Computing, Bertinoro, Italy, editors, Ozalp Babaoglu, Ken Birman, and Keith Marzullo, pages 29-32, June 2002. .pdf

2001

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

Elizabeth Borowsky, Eli Gafni, Nancy Lynch, and Sergio Rajsbaum. The BG Distributed Simulation Algorithm. Distributed Computing, 14(3):127-146, 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, January 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. .pdf

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.

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

Ziv Bar-Joseph, Idit Keidar, and Nancy Lynch: A Fault-Tolerant Dynamic Atomic Broadcast Algorithm with QoS Guarantees. MIT Technical Technical Report, December 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

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

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

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), pages 478-487, Limerick, Ireland, June 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

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 .ps

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

1999

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.

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, 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

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. 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. 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, 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.

Daniel Yates, Nancy Lynch, Victor Luchangco, and Margo Seltzer. I/O Automaton Model of Operating System Primitives Masters thesis, Harvard University and Massachusetts Institute of Technology, 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. .pdf .ps

Roberto De Prisco, Alan Fekete, Nancy Lynch, and Alex Shvartsman. A 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

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. .pdf .ps

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, 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), volume 1386 of 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), volume 1386 of Lecture Notes in Computer Science, pages 273--288. Springer Verlag, 1998. .pdf .ps

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

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

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. Also, submitted for journal publication. .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

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.

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

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

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 Alex 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.

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

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. .pdf .ps

1996

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

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 and Sons Ltd, April 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. (full) .pdf (short) .pdf

Nancy Lynch. Distributed Algorithms. Morgan Kaufmann Publishers, San Mateo, CA, 1996. Publisher site ACM Digital Library Errata for fourth printing

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. .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. .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 Vaandrager, 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..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

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

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. .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

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

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 Proceedings of the 15th International Conference on Distributed Computing Systems (ICDCS95), pages 439-449, Vancouver, Canada, May/June 1995, IEEE. .pdf. Also, Technical Report MIT/LCS/TM-518, Laboratory for Computer Science, Massachusetts Institute of Technology, June 1995. .pdf

Jon 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, 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. .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. .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 (Note: Later version in MIT-LCS-TM-487c, 1995.)

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 Second European Workshop on Real-Time and Hybrid Systems, Grenoble, France, June 1995. .pdf

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

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

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

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

Butler Lampson, Nancy Lynch, and Joergen Soegaard-Andersen. Correctness of At-Most-Once Message Delivery Protocols, In R. L. Tenney, et al., 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), IFIP Transactions C, pages 385-400. North Holland 1994. .pdf .ps

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

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

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. .pdf Won the Test of Time Award at 31st International Conference on Concurrency Theory (CONCUR 2020), September 2020.

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, 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

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, 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

Rainer Gawlick, Roberto Segala, Joergen Soegaard-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

Nancy Lynch, Michael Merritt, William Weihl, and Alan Fekete. Atomic Transactions. Morgan Kaufmann Publishers, 1993. Publisher site.

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

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

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.

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

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.

Alan Fekete, Nancy Lynch, and William Weihl. Hybrid atomicity for nested transactions. In Joachim Biskup, Richard Hul, editors, 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, 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 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

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. Superceded by 480.b and 480.c.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

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. .pdf

1991

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, 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

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.

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. Later version in .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 Part II: timing-based systems. Technical Memo MIT/LCS/TM-458, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, 02139, November 1991..pdf

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

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 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

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

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. Later version in .pdf

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

Barbara 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

1989

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

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

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 Later version .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. Submitted version .pdf Publisher's version

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

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

Alan Fekete, Nancy Lynch, and Liuba 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.)

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

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

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, 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 E. Burns and Nancy A. Lynch. The Byzantine firing squad problem. Advances in Computing Research, 4:147--161, 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

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. .pdf

Sunil 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

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

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

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

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

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

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. Revised. .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, Barbara Blaustein, Charles Kaufman, Sunil Sarin, and Oded Schmueli. Notes on a reliable broadcast protocol. Technical Memorandum CCA-85-08, Computer Corporation of America, Cambridge, MA, December 1985. pdf

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

1984

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

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

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

1983

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, 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 145--154, October 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

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; see .pdf)

Nancy Lynch. Multilevel atomicity--a new 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 new 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

Allan Borodin, Leonidas Guibas, Nancy Lynch, and Andrew 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 new 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 of 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

1979

Allan Borodin, Michael J. Fischer, David G. Kirkpatrick, Nancy Lynch, and Martin Tompa. A time-space tradeoff for sorting on non-oblivious machines. 20th Annual Symposium on Foundations of Computer Science, pages 319-327, San Juan, Puerto Rico, October 1979. .pdf

Michael J. Fischer, Nancy A. Lynch, James E. Burns, and Allan Borodin. Resource allocation with immunity to limited process failure. In 20th Annual Symposium on Foundations of Computer Science, pages 234--254, San Juan, Puerto Rico, October 1979. IEEE. pdf There is also a long version dated April 1981.

Nancy Lynch and Edward K. Blum. A difference in expressive power between flowcharts and recursion schemes. Mathematical Systems Theory 12, pages 205--211, 1979. .pdf

Nancy Lynch and Michael Fischer. On describing the behavior and implementation of distributed systems. In G. Kahn, editor, Proceedings of 1979 Conference on Semantics of Concurrent Computation, volume 70 of Lecture Notes in Computer Science, pages 147--171. Springer-Verlag, 1979. Chosen for submission to special issue of Theoretical Computer Science. .pdf Also appears as: Nancy A. Lynch and Michael J. Fischer. On Describing the Behavior and Implementation of Distributed Systems. Georgia Tech Technical Report GIT-ICS-79/03, May, 1979. Also issued by the Department of Computer Science, University of Washington, as TR 79-06-02.

1978

James E. Burns, Michael J. Fischer, Paul Jackson, Nancy A. Lynch, and Gary L. Peterson. Shared data requirements for implementation of mutual exclusion using a test-and-set primitive. In Proceedings of the International Conference on Parallel Processing, pages 79--87, Wayne State University, Detroit, MI., August 1978. .pdf

Nancy Lynch. Straight-line program length as a parameter for complexity measures. In Proceedings of Tenth Annual ACM Symposium on Theory of Computing, pages 150--161, San Diego, CA, May 1978. pdf

Nancy Lynch and Richard J. Lipton. On structure preserving reductions. SIAM Journal on Computing, 7(2):119--126, May 1978. .pdf

Nancy Lynch. Log space machines with multiple oracle tapes. Theoretical Computer Science, 6(1):25--39, 1978. .pdf

1977

Seymour Ginsburg and Nancy Lynch. Derivation complexity in context-free grammar forms. SIAM Journal on Computing, 6(1):123--138, March 1977. .pdf

Nancy A. Lynch and Edward K. Blum. Efficient reducibility between programming systems: Preliminary report. In Proceedings of 9th Annual ACM Symposium on Theory of Computing, pages 228--238, Boulder, CO., May 1977. pdf

Nancy Lynch. Log space recognition and translation of parenthesis languages. Journal of the ACM, 24(4):583--590, October 1977. pdf

1976

Seymour Ginsburg and Nancy Lynch. Size complexity in context-free grammar forms. Journal of the ACM, 23(4):582--598, October 1976. pdf

Richard E. Ladner and Nancy A. Lynch. Relativization of questions about log space computability. Mathematical Systems Theory, 10:19--32, 1976. .pdf

Nancy Lynch. Complexity-class encoding sets. Journal of Computer and System Sciences, 13(1):100--118, August 1976. .pdf

Nancy Lynch, Albert Meyer, and Michael Fischer. Relativization of the theory of computational complexity. Transactions of the American Mathematical Society, 220:243--287, 1976.pdf

1975

Seymour Ginsburg and Nancy Lynch. Comparative complexity of grammar forms. In Proceedings of the Seventh Annual ACM Symposium on Theory of Computing, pages 153--158, Albuquerque, NM, May 1975. pdf

Richard E. Ladner, Nancy A. Lynch, and Alan L. Selman. A comparison of polynomial-time reducibilities. Theoretical Computer Science, 1(2):103--123, 1975. .pdf

Nancy Lynch. Helping: Several formalizations. Journal of Symbolic Logic, 40(4):555--566, December 1975. pdf

Nancy Lynch. On reducibility to complex or sparse sets. Journal of the ACM, 22(3):341--345, July 1975. pdf

1974

Richard Ladner, Nancy Lynch, and Alan Selman. Comparison of polynomial-time reducibilities. In Proceedings of the Sixth Annual ACM Symposium on Theory of Computing, pages 110--121, Seattle, WA, April 1974. pdf

Nancy Lynch. Approximations to the halting problem. Journal of Computer and Systems Sciences, 9(2):143--150, October 1974. .pdf

1973

Nancy Lynch, Albert Meyer, and Michael Fischer. Sets that don't help. In Proceedings of the Fifth Annual ACM Symposium on Theory of Computing, pages 130--134, Austin, TX, April 1973. pdf

1972

Nancy A. Lynch. Relativization of the theory of computational complexity. Ph.D. Thesis, Massachusetts Institute of Technology Department of Mathematics, 1972. pdf Also, Technical Report MIT-LCS-TR-099, Project MAC, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, June 1972. pdf

Nancy A. Lynch, Albert R. Meyer, and Michael J. Fischer. Priority arguments in complexity theory. Abstract 24, Recursive Function Theory Newsletter 2, pages 7--10, July 1972. University of California, Berkeley. typed .pdf, and original scanned version.

1971

Nancy Lynch. A universally-helped recursive set. Courant Institute, New York City (1971).

TOC / CSAIL / MIT Accessibility