To appear
Daniel Liberzon, Nancy Lynch, and Sayan Mitra.
Verifying Average Dwell Time of Hybrid Systems. To appear in ACM Transactions in Embedded Computing Systems, 2008. .pdf
2008
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. CONCUR 2008: 19th International Conference on Concurrency Theory, Toronto, Canada, August 2008. .pdf.
R. Canetti, L. Cheung, D. Kaynar, M. Liskov, N. Lynch, O. Pereira, and R. Segala. Analyzing Security Protocol Using Time-Bounded Task-PIOAs. Journal of Discrete Event Dynamic Systems (DEDS), volume 18, number 1, 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, 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. . Available online.
Alex 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.
Seth Gilbert, Nancy Lynch, Sayan Mitra, and Tina Nolte. Self-Stabilizing Mobile Robot Formations with Virtual Nodes.
Proceedings of the Symposium on Stabilization, Safety and Security of Distributed Systems (SSS), Detroit, Michigan, November, 2008. .pdf
Seth Gilbert, Nancy Lynch, Sayan Mitra, and Tina Nolte. Self-Stabilizing Robot Formations Over Unreliable Networks. Submitted for journal publication.
Seth Gilbert, Nancy Lynch, and Alex Shvartsman. RAMBO: A Robust, Reconfigurable Atomic Memory service for Dynamic Networks. Submitted for journal publication. .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.
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
Jiang Wu, Nancy Griffeth, Nancy Lynch, Calvin Newport, Mike Spindel, and Ralph Droms. Using Virtual Infrastructure to Adapt Wireline Protocols to MANET. Submitted for publication.
2007
Paul Attie, Rachid Guerraoui, Petr Kouznetsov, Nancy Lynch, and Sergio Rajsbuam. The Impossibility of Boosting Distributed Service Resilience. Submitted for journal publication, Janauary, 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.
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/12, 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, Venice, Italy, 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.
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). .pdf
Rui Fan, Ralph Droms, Nancy Griffeth, and Nancy Lynch. The DHCP
Failover Protocol: A Formal Perspective. 27th IFIP WG 6.1 International Conference on Formal Methods for
Networked and Distributed Systems (FORTE 2007), Tallinn, Estonia, June 26-29, 2007. .pdf
Rachid Guerraoui, Maurice Herlihy, Petr Kouznetsov, Nancy Lynch,
and Calvin Newport. On the weakest failure detector ever.
Proceedings of the Twenty-Sixth Annual ACM Symposium on the Principles
of Distributed Computing (PODC), Portland, Oregon, August 2007. .pdf
Xavier Koegler (supervised by Nancy Lynch). Around the Tempo Toolset Userguide. March 20th-August 31st, 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 implementation relations for Probabilistic I/O Automata. Electronic Notes in Theoretical Computer Science, 174(8):71-93, 2007. .pdf
Sayan Mitra and Nancy Lynch. Trace-based semantics of Probabilistic timed I/O automata.
Hybrid Systems: Computation and Control (HSCC 2007), Pisa, Italy,
April 3-5, 2007, volume 4416 of Lecture Notes in Computer Science. Springer, 2007. .pdf
Tina Nolte and Nancy Lynch. Self-stabilization and Virtual Node Layer
Emulations. Proceedings of SSS 2007: Ninth International Symposium on
Stabilization, Safety, and Security of Distributed Systems, Paris, France,
November 2007. .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. Hybrid Systems: Computation and Control (HSCC 2007), Pisa, Italy,
April 3-5, 2007. .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, 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. 20th
International Symposium on Distributed Computing (DISC 2006),
Stockholm, Sweden, September 18-20, 2006. 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 Probabilistic PIOA: Parallel Composition via
Distributed Scheduling. Theoretical Computer Science, volume 365, issues 1-2, pages 83-108, 10 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 MBT 2006: Second Workshop on
Model Based Testing, Electronic Notes in Theoretical Computer
Science, issue 4, volume 164, March 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, July 2006. .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 (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.
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. .pdf
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. .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. .ps
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. .html
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
DISC 2005: 19th International Symposium on Distributed Computing,
Cracow, Poland, September 2005. .pdf
Gregory Chockler, Murat Demirbas, Seth Gilbert, Nancy Lynch, Calvin
Newport, and Tina Nolte. Reconciling the Theory and Practice of (Un)Reliable Wireless Broadcast.
Proceedings of the 4th International
Workshop on Assurance in Distributed Systems and Networks (ADSN 2005),
June 6, 2005, Columbus, Ohio, USA. .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.
Principles of Distributed systems: 9th International Conference on
Principles of Distributed Systems (OPODIS 2005), volume 3974 of Lecture Notes in Computer Science, pages 130-145, 2006, Springer. Also, Technical Report MIT-LCS-TR-979a, MIT CSAIL, Cambridge, MA 02139, August 2005.
.ps
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.
Self-Stabilizing Systems: Seventh International Symposium on Self
Stabilizing Systems (SSS 2005), Barcelona, Spain, October 26-27,
2005, volume 3764 of {\em 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. .ps
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. .ps
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. .ps
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. .ps
Stephen Garland, Dilsun Kaynar, Nancy Lynch, Joshua Tauber, and
Mandana Vaziri. TIOA Tutorial. May 22, 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.
Proceedings of International Conference on Formal
Modelling and Analysis of Timed Systems (FORMATS'05), Uppsala,
Sweden, September 26 - 28, 2005. .pdf
Nancy Lynch, Sayan Mitra, and Tina Nolte. Motion Coordination Using
Virtual Nodes. CDC-ECC 2005: Forty-Fourth IEEE Conference on
Decision and Control and European Control Conference, Seville,
Spain, December 2005. Invited paper. .pdf
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, 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. .pdf
Ling Cheung, Nancy Lynch, Roberto Segala, and Frits Vaandrager.
Switched Probabilistic I/O Automata. Nijmegen Institute for
Computing and Information Sciences (NIII) Technical Report NIII-R0437,
Catholic University of Nijmegen, Nijmegen, The Netherlands, September 2004.
.ps
Murat Demirbas, Anish Arora, Tina Nolte, and Nancy Lynch. A
Hierarchy-based Fault-local Stabilizing Algorithm for Tracking in
Sensor Networks. In Teruo Higashino,
editor, Principles of Distributed Systems: OPODIS 2004: 8th
International Conference on Principles of Distributed Systems, Grenoble, France, December 15-17, 2004,
volume 3544 of Lecture Notes in Computer Science, pages 299-315,
2005. Springer. .pdf.
Murat Demirbas, Anish Arora, Tina Nolte, and Nancy Lynch. Brief
Announcement: STALK: A Self-Stabilizing Hierarchical Tracking Service
for Sensor Networks. Proceedings of the 23rd Annual ACM SIGACT-SIGOPS
Symposium on Principles of Distributed Computing (PODC 2004), page 378, St. John's, Newfoundland, Canada, July 25-28, 2004. .ps
Shlomi Dolev, Seth Gilbert, Nancy A. Lynch, Elad Schiller, Alex
A. Shvartsman, and Jennifer L. Welch. Virtual Mobile Nodes for
Mobile Ad Hoc Networks. 18th International
Symposium on Distributed Computing (DISC04), Trippenhuis, Amsterdam, the
Netherlands, October 4-7, 2004. .ps
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. .ps
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. .ps
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. .ps
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. .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.
Also, submitted for publication. .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, 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. .ps
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. Postscript
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. .pdf
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. .pdf
Shlomi Dolev, Seth Gilbert, Nancy Lynch, Alex Shvartsman, and Jennifer Welch.
GeoQuorums: Implementing atomic memory in ad hoc networks. Technical Report MIT-LCS-TR-900, MIT
Laboratory for Computer Science, Cambridge, MA, 02139, 2003. .ps
Rui Fan and Nancy Lynch. Efficient Replication of Large Data
Objects. Distributed Computing (DISC 2003: 17th International Symposium on Distributed
Computing, Sorrento, Italy, October, 2003), volume 2848 of Lecture
Notes in Computer Science, pages 75-91, Springer-Verlag, 2003. .pdf
Rui Fan 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
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. .ps
Dilsun K. Kaynar, Nancy Lynch, Roberto Segala, and Frits Vaandrager.
Timed I/O Automata: A Mathematical Framework for Modeling and
Analyzing Real-Time Systems. RTSS 2003: The 24th
IEEE International Real-Time Systems Symposium, Cancun, Mexico, pages 166-177,
December, 2003. .ps
Dilsun K. Kaynar, Nancy Lynch, Roberto Segala, and Frits Vaandrager.
The Theory of Timed I/O Automata. Technical Report
MIT-LCS-TR-917, MIT Laboratory for Computer Science, Cambridge, MA, 2003. .ps
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, 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
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. .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..ps (Long version below).
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. .ps
Toh Ne Win, Michael D. Ernst, Stephen J. Garland, Dilsun K. Kaynar,
and Nancy Lynch. Using simulated execution in verifying
distributed algorithms. In L.D. Zuck, P.C. Attie, A. Cortesi,
S. Mukhopadhyay, editors, Verification, Model Checking, and
Abstract Interpretation (Proceedings of 4th International Conference, VMCAI 2003, NewYork, NY, USA, January
9-11, 2003), volume 2575 of Lecture Notes in Computer Science,
pages 283-297, Springer-Verlag, 2003. .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), 4:(1-10), 2003. .ps
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. .ps
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. .ps
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. .ps
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. Abstract/Paper.
Seth Gilbert and Nancy Lynch. Brewer's conjecture and the
feasibility of consistent, available, partition-tolerant web
services. Sigact News, 33(2), June 2002. .ps
Dilsun Kirli Kaynar, Anna Chefter, Laura Dean, Stephen J. Garland,
Nancy A. Lynch, Toh Ne Win, and Antonio Ramirez-Robredo.
Simulating Nondeterministic Systems at Multiple Levels of
Abstraction. In Tools Day held in conjunction with CONCUR'02, Brno, Czech
Republic, August 2002. .ps
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. ps
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. .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.
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.
Nancy Lynch and Alex Shvartsman. RAMBO: A Reconfigurable Atomic
Memory Service for Dynamic Networks. Technical Report MIT-LCS-TR-856,
MIT Laboratory for Computer Science, Cambridge, MA, 2002. .ps
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. Postscript
Elizabeth Borowsky, Eli Gafni, Nancy Lynch, and Sergio Rajsbaum.
The BG Distributed Simulation Algorithm.
Distributed Computing, 14:127-146, 2001. ps.
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. Postscript.
Carolos
Livadas, Idit
Keidar, and Nancy A. Lynch. Designing a Caching-Based Reliable
Multicast Protocol. Proceedings of the International Conference on
Dependable Systems and Networks (DSN'01), Fast Abstracts Supplement,
pages B44-B45, Gothenburg, Sweden, July 2001. [Abstract/Postscript]
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. pdf,
abstract.
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. Postscript
Ziv Bar-Joseph, Idit Keidar, Tal Anker, and Nancy Lynch. QoS
Preserving Totally Ordered Multicast. MIT Technical Report
MIT-LCS-TR-796, January 2000. Postscript
Ziv Bar-Joseph, Idit Keidar, and Nancy Lynch:
A Fault-Tolerant Dynamic Atomic Broadcast Algorithm with QoS Guarantees.
MIT Technical Technical Report, December 2000. Postscript
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. Abstract/Postscript
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. Postscript.
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. Abstract
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. Postscript
Anna Pogosyants, Roberto Segala, and Nancy Lynch.
Verification of the randomized consensus algorithm of Aspnes and
Herlihy: a case study. Distributed Computing,
13(3):155-186, 2000. .pdf
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. Abstract/Paper.
Alan Fekete, Nancy Lynch, and Alex Shvartsman. Specifying and Using a Partitionable Group Communication
Service. MIT Laboratory for Computer Science,
Cambridge, MA Technical Memo MIT/LCS/TM-570b, June 1999.
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. ps
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. (Compressed
Postscript)
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.
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. (Abstract/Paper).
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. Abstract
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.
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. Thesis
(compressed .ps)
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.Compressed
Postscript
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. Abstract/Paper
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.
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).
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. .ps
Roger Khazan, Alan Fekete, and Nancy Lynch. Multicast Group Communication
as a Base for a Load-Balancing Replicated Data Service. 12th International
Symposium on Distributed Computing (DISC98), September 1998. (Compressed
Postscript
500K)
Carolos Livadas and
Nancy A. Lynch. Formal
Verification of Safety-Critical Hybrid Systems. In S. Sastry and
T.A. Henzinger, editors, Hybrid Systems: Computation and Control (First
International Workshop, HSCC'98, Berkeley, CA, USA, April, 1998), number
1386 in Lecture Notes in Computer Science, pages 253--272. Springer Verlag,
1998. (Abstract/Postscript)
John Lygeros and Nancy Lynch. Strings of vehicles: Modeling and safety
conditions. In S. Sastry and T.A. Henzinger, editors, Hybrid Systems:
Computation and Control (First International Workshop, HSCC'98, Berkeley,
CA, USA, April, 1998), number 1386 in Lecture Notes in Computer Science,
pages 273--288. Springer Verlag, 1998. Postscript
Dahlia Malkhi, Mike Reiter, and Nancy Lynch. A correctness condition
for memory shared by Byzantine processes, 1998. Manuscript.
Roberto Segala, Rainer Gawlick, Jorgen Sogaard-Andersen, and Nancy Lynch.
Liveness in timed and untimed systems. Information and Computation,
141(2):119--171, March 1998. Postscript
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. (Abstract/Postscript)
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. (Abstract/Postscript)
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.
(Abstract/Postscript)
Roberto De Prisco. Revisiting
the Paxos algorithm. Master of Science Thesis, Department of Electrical
Engineering and Computer Science, Massachusetts Institute of Technology,
June 1997. Also, Technical Report MIT/LCS/TR-717, Laboratory for Computer
Science, Massachusetts Institute of Technology. (Abstract/Postscript)
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. (Abstract/Postscript)
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. (Abstract/Postscript)
Also, Technical Memo MIT/LCS/TM-570, Laboratory for Computer Science,
Massachusetts Institute of Technology, October 1997. (Compressed
Postscript)
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. (Summary/Postscript)
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 (Abstract/Postscript)
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.
Also, Technical Memo MIT/LCS/TM-555, Laboratory for Computer Science, Massachusetts
Institute of Technology. (Abstract/Postscript)
Mandana Vaziri and Nancy Lynch. Proving correctness of a controller
algorithm for the RAID level 5 system. Technical Memo MIT/LCS/TM-576,
Laboratory for Computer Science, Massachusetts Institute of Technology,
545 Technology Square, Cambridge, MA 02139, December 1997. .ps
1996
Michael S. Branicky,
Ekaterina Dolginova,
and Nancy Lynch. A Toolbox
for Proving and Maintaining Hybrid Specifications. In Panos J. Antsaklis,
editor, Hybrid Systems IV (HS'96, Cornell University, Ithaca, NY, October
12-16, 1996), volume 1273 of Lecture Notes in Computer Science. Springer-Verlag
1996. (Abstract/Postscript)
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. (Abstract/Postscript)
Nancy Lynch. Distributed
Algorithms. Morgan Kaufmann Publishers, San Mateo, CA, 1996. (Summary/Table
of Contents) To order, please contact Morgan
Kaufmann Publishers.
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. (Abstract/Postscript)
Nancy Lynch. Modelling
and verification of automated transit systems, using timed automata, invariants
and simulations. In R. Alur, T. Henzinger, and E. Sontag, editors,
Hybrid Systems III: Verification and Control (DIMACS/SYCON Workshop on
Verification and Control of Hybrid Systems, New Brunswick, New Jersey,
October 1995), volume 1066 of Lecture Notes in Computer Science, pages
449-463. Springer-Verlag 1996. (Abstract/Postscript)
Nancy Lynch and Sergio
Rajsbaum. On the Borowsky-Gafni Simulation Algorithm. Proceedings
of ISTCS 1996: The Fourth Israel Symposium on Theory of Computing and Systems,
pages 4-15, Jerusalem, Israel, June 1996. Also, Proceedings of the Fifteenth
Annual ACM Symposium on Principles of Distributed Computing, page 57, Philadelphia,
PA, May 1996. (Abstract/Postscript).
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. (Abstract/Postscript)
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. (Abstract/Postscript)
Nancy Lynch and Frits
Vaandrager. Forward and backward simulations -- Part II: Timing-Based
systems. Information and Computation, 128(1):1-25, July
1996.(Abstract/Postscript).
Nancy Lynch and Frits
Vaandrager. Action Transducers and Timed Automata. Formal
Aspects of Computing, 8(5):499-538, 1996. .ps
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. (Abstract/Postscript)
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. (Abstract/Postscript)
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. (Abstract/Postscript)
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). .ps
Alan Fekete, Nancy Lynch, and William Weihl. Hybrid atomicity for nested
transactions. Theoretical Computer Science B (Logic, semantics and theory
of programming), 149(1):151--178, September 1995. Special issue of TCS
devoted to ICDT '92. .pdf
Alan Fekete, Frans Kaashoek and Nancy
Lynch. Implementing Sequentially-Consistent Shared Objects Using
Group and Point-to-Point Communication . In the 15th International
Conference on Distributed Computing Systems (ICDCS95), pages 439-449, Vancouver,
Canada, May/June 1995, IEEE. (Abstract/Postscript).
Also, Technical Report MIT/LCS/TM-518, Laboratory for Computer Science,
Massachusetts Institute of Technology, June 1995. (Abstract/Postscript)
John Kleinberg,
Hagit Attiya and
Nancy Lynch. Trade-offs
between Message Delivery and Quiesce Times in Connection Management Protocols.
Proceedings of the Third Israel Symposium on Theory of Computing and
Systems, pages 258-267, Tel-Aviv, Israel, January 1995. (Abstract/Paper)
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. (Abstract/Postscript).
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. .ps.
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. (Abstract/Postscript).
Nancy Lynch, Roberto Segala, Frits Vaandrager, and
H. B. Weinberg. Hybrid I/O Automata. Technical Memo
MIT/LCS/TM-544, Laboratory for Computer Science, Massachusetts
Institute of Technology, Cambridge, MA, December 1995. (Abstract/Postscript)
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. .ps
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. Abstract/Postscript
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. (Abstract/Postscript)
Nancy Lynch and H.B.
Weinberg. Proving Correctness of a Vehicle Maneuver:
Deceleration In the Second European Workshop on Real-Time and
Hybrid Systems, Grenoble, France, June 1995.(Compressed
Postscript)
Roberto Segala and Nancy Lynch. Probabilistic simulations for probabilistic
processes. Nordic Journal of Computing, 2(2):250--273, August 1995.
.ps
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. (Abstract/Postscript)
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. (Abstract/Postscript)
Also, Technical Memo MIT/LCS/TM-511, Laboratory for Computer Science,
Massachusetts Institute of Technology, November 1994. (Abstract/Postscript)
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. (Abstract/Postscript)
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.
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. (Compressed
Postscript)
Nancy Lynch, Michael
Merritt, William Weihl, and Alan Fekete. Atomic Transactions. Morgan
Kaufmann Publishers, 1994. (Abstract/Table
of Contents)
Nancy Lynch, Isaac
Saias, and Roberto Segala.
Proving Time Bounds for Randomized Distributed Algorithms. Proceedings
of the 13th Annual ACM Symposium on the Principles of Distributed Computing,
pages 314--323, Los Angeles, CA, August 1994. (Abstract/Postscript).
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. .ps
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.
(Superceded by MIT-LCS-TM-480c) .ps
Roberto Segala and Nancy
Lynch. Probabilistic simulations for probabilistic processes.
In Bengt Jonsson and Joachim Parrow, editors, 5th International Conference
on Concurrency Theory (CONCUR'94, Uppsala, Sweden, August 1994), volume
836 of Lecture Notes in Computer Science, pages 481-496. Springer-Verlag
1994. (Abstract/Postscript)
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).
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. (Abstract/Postscript)
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. .ps
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.(Compressed
Postscript)
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. (Compressed
Postscript)
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 Sogaard-Andersen, Nancy A. Lynch, and Butler Lampson. Correctness
of communication protocols: A case study.s Technical Memo MIT/LCS/TR-589,
Laboratory for Computer Science, Massachusetts Institute of Technology,
Cambridge, MA, 02139, November 1993. .ps
Joergen F. Soegaard-Andersen, Stephen J. Garland, John V. Guttag, Nancy
A. Lynch, and Anna
Pogosyants. Computer-Assisted Simulation Proofs. In Costas
Courcoubetis, 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. (Abstract/Postscript).
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. (Abstract/Postscript).
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 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) .ps
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.
Nancy Lynch and Frits
Vaandrager. Forward and backward simulations for timing-based systems.
In J. W. de Bakker, W. P. de Roever, C. Huizing, and G. Rozenberg, editors,
Proceedings of Real-Time: Theory in Practice (REX Workshop, Mook, The Netherlands,
June 1991), volume 600 of Lecture Notes in Computer Science, pages 397-446.
Springer-Verlag 1992. (Abstract/Postscript)
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.
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.
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 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.
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.
Nancy Lynch and Isaac Saias. An analysis of Rabin's randomized mutual
exclusion algorithm: Preliminary report. Technical Memo MIT/LCS/TM-462,
Laboratory for Computer Science, Massachusetts Institute of Technology,
December 1991. .pdf
Nancy Lynch and Frits Vaandrager. Forward and backward simulations
for timing-based systems. Technical Memo MIT/LCS/TM-458, Laboratory
for Computer Science, Massachusetts Institute of Technology, Cambridge,
MA, 02139, November 1991. .pdf
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 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.
.compressed
.ps
Nancy Lynch and Hagit Attiya. Using mappings to prove timing properties.
In Proceedings of the Ninth Annual ACM Symposium on Principles of Distributed
Computing, Quebec, Canada, August 1990. pdf Expanded version in earlier Technical
memo, TM412.d.
Nancy A. Lynch. Multivalued possibilities mappings. In J.W. de
Bakker, W.P. de Roever, and G. Rozenberg, editors, Stepwise Refinement
of Distributed Systems: Models, Formalisms, Correctness (REX Workshop,
Mook, The Netherlands, May/June 1989), volume 430 of Lecture Notes in Computer
Science, pages 519--543. Springer-Verlag, 1990. .pdf
Nancy Lynch. Multivalued possibilities mappings. Technical
Memo MIT/LCS/TM-422, Laboratory for Computer Science, Massachusetts Institute
of Technology, Cambridge, MA, 02139, August 1990. .pdf
B. Simons, Jennifer L. Welch, and Nancy Lynch. An overview of
clock synchronization. In B. Simons and A. Spector, editors,
Fault-tolerant Distributed Computing (Proceedings of of the Asilomar
Workshop on Fault-Tolerant Distributed Computing, March, 1986),
volume 448 of Lecture Notes in Computer Science, pages 84-96,
1990. Springer-Verlag. .pdf
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.
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.
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.
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.
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. Also, Technical Memo MIT/LCS/TM-373, Laboratory for Computer
Science, Massachusetts Institute of Technology. (Abstract/Postscript)
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
A. Fekete, N. Lynch, and L. Shrira.
A modular proof of correctness for a network synchronizer.
In J. van Leeuwen, editor, Distributed Algorithms (2nd
International Workshop, Amsterdam, The Netherlands, July 1987), volume 312
of Lecture Notes in Computer Science, pages 219--256. Springer-Verlag,
1988. .pdf
Alan Fekete, Nancy Lynch, Michael Merritt, and William Weihl.
Commutativity-based locking for nested transactions.
Technical Memo MIT/LCS/TM-370, Laboratory for Computer Science,
Massachusetts Institute of Technology, Cambridge, MA, 02139, August
1988. .pdf
H. Garcia-Molina, B. Kogan, and N. 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
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.
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.
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
H. Garcia-Molina, B. Kogan, and N. 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. (Abstract/Postscript)
S. K. Sarin and Nancy Lynch.
Discarding obsolete information in a replicated database system.
IEEE Transactions on Software Engineering, SE-13(1):39--47,
January 1987. .pdf
1986
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
H. Garcia-Molina, N. Lynch, B. Blaustein, C. Kaufman, S. Sarin, and
O. Schmueli.
Notes on a reliable broadcast protocol. Technical Memorandum
CCA-85-08, Computer Corporation of America, Cambridge, MA, December
1985. pdf
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
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 Inst
