LYNCH, NANCY A. / Informatique / Chercheurs

Centre International de Recherche Scientifique

Chercheurs

Informatique / LYNCH, NANCY A.

lynchtheory.csail.mit.edu

Position

NEC Professor of Software Science and Engineering, Professor of Electrical Engineering and Computer Science, Massachusetts Institute of Technology.

Head of the Theory of Distributed Systems Group (TDS) research group in MIT\'s Computer Science and Artificial Intelligence Laboratory (CSAIL).

Thèmes de recherche

distributed computing, real-time computing, algorithms, lower bounds, formal modelling and verification.

For almost 30 years Professor Nancy Lynch has made major and lasting contributions to the theory of distributed computing. She has developed new distributed algorithms, created precise models for analyzing distributed processes, and discovered the limitations on what distributed algorithms can accomplish. Her celebrated result in 1982 with M.J. Fischer and M.S. Paterson on the impossibility of distributed agreement in the presence of stopping faults is fundamental in all of computer science. Her development, with M.R. Tuttle, F. Vaandrager, R. Segala, and D. Kaynar, of the I/O Automata mathematical system modeling frameworks brought needed rigor to the field.

Her influence extends to practitioners who have benefited from her courses and papers aimed at non-theory audiences, and her insights on distributed computation have influenced other fields of computing, including cryptography, distributed transactions, and hardware synchronization.

Prix et récompenses

2001 : Dijkstra Prize
2006 : Wijngaarden Prize
2007 : Knuth Prize

Publications

Submitted for Publication

Paul C. Attie and Nancy A. Lynch. Dynamic Input/Output Automata: a Formal and Compositional Model for Dynamic Systems. Submitted for publication. Also, Technical Report MIT-CSAIL-TR-2013-015, Computer Science and Artificial Intelligence Laboratory, Cambridge, MA 02139, July 2013.

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

To appear

Viveck R. Cadambe, Nancy Lynch, Muriel Medard, and Peter Musial. Coded Emulation of Shared Atomic Memory for Message Passing Architectures. To appear in The 13th IEEE International Symposium on Network Computing and Applications (IEEE NCA14), Cambridge, MA, August 2014.

Alejandro Cornejo, Anna Dornhaus, Nancy Lynch, and Radhika Nagpal. Task Allocation in Ant Colonies. To appear in Proceedings of the 28th International Symposium on Distributed Computing (DISC\'14), Austin, TX, October 2014.

2014

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

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

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.

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

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.

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.

2013

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

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.

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

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.

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.

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.

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, Montreal Canada, July 2013.

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.

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.

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.

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

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.

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

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.

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.

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.

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.

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.

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.

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.

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.

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.

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

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

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.

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.

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.

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.

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.

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.

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 .

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.

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.

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.

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.

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.

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.

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.

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.

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.

2009

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

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

2007

Paul Attie, Rachid Guerraoui, Petr Kouznetsov, Nancy Lynch, and Sergio Rajsbaum. The Impossibility of Boosting Distributed Service Resilience. Submitted for publication.

Ran Canetti, Ling Cheung, Nancy Lynch, and Olivier Pereira. On the Role of Scheduling in Simulation-Based Security. ePrint Report 2007/12, Cryptology ePrint archive, 2007.

Ran Canetti, Ling Cheung, Dilsun Kaynar, Moses Liskov, Nancy Lynch, Olivier Pereira, and Roberto Segala. Analyzing Security Protocols Using Time-Bounded Task-PIOAs. Submitted for journal publication, February 16, 2007.

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

Chryssis Georgiou, Nancy Lynch, Panayiotis Mavrommatis, and Joshua Tauber. Automated Implementation of Complex Distributed Algorithms Specified in the IOA Language. Submitted for publication, 2007.


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

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. 20th International Symposium on Distributed Computing (DISC 2006), Stockholm, Sweden, September 18-20, 2006. Invited paper.

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.

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.

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.

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.

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.

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.

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

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.

Constantinos Djouvas, Nancy D. Griffeth, and Nancy A. Lynch. Testing Self-Similar Networks MBT 2006: Second Workshop on Model Based Testing, Electronic Notes in Theoretical Computer Science, issue 4, volume 164, March 2006.

Rui Fan and Nancy Lynch. Gradient Clock Synchronization. Distributed Computing, volume 18, number 4, pages 255-266, March, 2006.

Rui Fan and Nancy Lynch. An $\\Omega(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, July 2006.

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

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.

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 (HSCC 06) Santa Barbara, CA, March 2006, volume 3927 of Lecture Notes in Computer Science, pages 476-490, 2006. Springer.

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. FM 2006: Formal Methods, International Symposium of Formal Methods Europe, Hamilton, Ontario Canada, August, 2006. Volume 4085 of Lecture Notes in Computer Science, pages 64-80, Springer, 2006.


2005

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

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.

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

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.

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.

Gregory Chockler, Nancy Lynch, Sayan Mitra, and Joshua Tauber. Proving Atomicity: An Assertional Approach DISC 2005: 19th International Symposium on Distributed Computing, Cracow, Poland, September 2005.

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), June 6, 2005, Columbus, Ohio, USA.

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.

Shlomi Dolev, Seth Gilbert, Limor Lahiani, Nancy Lynch, and Tina Nolte. Timed Virtual Stationary Automata for Mobile Networks. 9th International Conference on Principles of Distributed Systems (OPODIS 2005), Pisa, Italy, December 12-14, 2005.

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.

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.

Shlomi Dolev, Limor Lahiani, Nancy Lynch, and Tina Nolte. Self-Stabilizing Mobile Node Location Management and Message Routing. SSS 2005: Seventh International Symposium on Self-Stabilizing Systems, Barcelona, Spain, October 2005.

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.

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. Also, Technical Report MIT-LCS-TR-900a, CSAIL, Massachusetts Institute of Technology, Cambridge, MA, 2004.

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.

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.

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

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

Hongping Lim, Dilsun Kaynar, Nancy Lynch, and Sayan Mitra. Translating timed I/O automata specifications for theorem proving in PVS. Proceedings of International Conference on Formal Modelling and Analysis of Timed Systems (FORMATS\'05), Uppsala, Sweden, September 26 - 28, 2005.

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.

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

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

Joshua A. Tauber, Dilsun K. Kaynar, Nancy A. Lynch. Correctness of a Compiler for Distributed Algorithms. Submitted for publication, 2005.


2004

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

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.

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

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, July 25-28, 2004.

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

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. 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. Selected for special edition of Distributed Computing, (edited by Faith Fich), related to the DISC03 conference, 2004. Also, Technical Report MIT-LCS-TR-900a, CSAIL, Massachusetts Institute of Technology, Cambridge, MA, 2004.

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.

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.

Stephen Garland, Nancy Lynch, Joshua Tauber, and Mandana Vaziri. IOA User Guide and Reference Manual. Technical Report MIT-LCS-TR-961, MIT Computer Science and Artificial Intelligence Laboratory (CSAIL), Cambridge, MA, 2004.

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

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.

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. .ps Revised version to appear in Synthesis Lectures on Computer Science, Morgan Claypool Publishers, November 2005.

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.

Dilsun Kaynar, Nancy Lynch, Sayan Mitra, Christine Robson. Design for TIOA Modeling Language. Manuscript in progress, 2004.

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.

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

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

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.


2003

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

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

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

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.

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.

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.

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.

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.

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.

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.

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

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. Also, long version as Technical Report MIT-LCS-TR-907, MIT Laboratory for Computer Science, Cambridge, MA, and submitted for publication, 2005.

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

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

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.

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.

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.

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.

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), 4:(1-10), 2003.


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.

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.

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.

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.

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.

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

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.

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.

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

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.

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.

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.

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.

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.

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.


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.

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

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.

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.

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.

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

Ziv Bar-Joseph, Idit Keidar, Tal Anker, and Nancy Lynch: QoS Preserving Totally Ordered Multicast. 5th International Conference On Principles Of Distributed Systems (OPODIS), pages 143-162, Paris, France, December, 2000.

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

Ziv Bar-Joseph, Idit Keidar, and Nancy Lynch: A Fault-Tolerant Dynamic Atomic Broadcast Algorithm with QoS Guarantees. MIT Technical Technical Report, December 2000.

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.

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

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.

Idit Keidar, Roger Khazan, Nancy Lynch and Alex Shvartsman. An Inheritance-Based Technique for Building Simulation Proofs Incrementally. In the 22nd International Conference on Software Engineering (ICSE), pages 478-487, Limerick, Ireland, June 2000. Also, invited as a journal submission to ACM Transactions on Software Engineering and Methodology, 2000.

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.

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.

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.

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.

Mentions légales - Contact

Copyright © 2013 - www.cirs.info - Tous droits réservés