Alan Fekete, David Gupta, Victor Luchangco, Nancy Lynch, and Alex
Shvartsman. Eventually-Serializable Data Services. Theoretical
Computer Science, 220(1):113--156, June 1999. Special Issue on Distributed
Algorithms. .pdf
Jason Hickey, Nancy Lynch,
Robbert van Renesse. Specifications and Proofs for Ensemble Layers.
Fifth International Conference on Tools and Algorithms for the Construction
and Analysis of Systems (TACAS '99), Amsterdam, the Netherlands, March
1999. Springer-Verlag. .pdf
Nancy Lynch I/O Automaton
Models and Proofs for Shared-Key Communication Systems Technical
Report MIT/LCS/TR-789, Laboratory for Computer Science, Massachusetts Institute
of Technology, Cambridge, MA, August, 1999. .pdf
Nancy Lynch I/O Automaton
Models and Proofs for Shared-Key Communication Systems Proceedings of
the 12th IEEE Computer Security Foundations Workshop (CSFW'99), Mordana,
Italy, June 28-30, 1999. (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. High-Level Modeling and Analysis of an Air-Traffic Management System. In Frits W. Vaandrager and Jan H. van Schuppen, editors, Hybrid Systems: Computation and Control, Second International Workshop, HSCC'99, Berg en Dal, The Netherlands, March 29-31, 1999, volume 1569 of Lecture Notes in Computer Science, page 3, 1999. Springer. Abstract of invited talk.
Nancy Lynch I/O Automaton
Models and Proofs for Shared-Key Communication Systems Technical
Report MIT/LCS/TR-789, Laboratory for Computer Science, Massachusetts Institute
of Technology, Cambridge, MA, August, 1999. .pdf
Nancy Lynch, Nir Shavit, Alex Shvartsman, and Dan Touitou. Timing
conditions for linearizability in uniform counting networks. Theoretical
Computer Science, 220(1):67--91, June 1999. Special Issue on Distributed
Algorithms. .pdf.
Daniel Yates, Nancy Lynch, Victor Luchangco, and Margo Seltzer. I/O
Automaton Model of Operating System Primitives Masters thesis, Harvard
University and Massachusetts Institute of Technology, May 1999. .pdf
1998
Soma Chaudhuri, Maurice
Herlihy, Nancy A. Lynch,
and Mark R. Tuttle. Tight bounds for k-set agreement. Technical
Report 98/4, Digital Equipment Corporation, Cambridge Research Lab, Cambridge,
MA 02139, May, 1998..ps
Roberto De Prisco, Alan Fekete, Nancy Lynch, and Alex Shvartsman. A
Dynamic View-Oriented Group Communication Service. In Proceedings
of the 17th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed
Computing (PODC'98), Puerto Vallarta, June-July, 1998. 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. In Shay Kutten, editor, Distributed Computing, 12th International Symposium (DISC 1998), Andros, Greece, September 1998, volume 1499 of Lecture Notes in Computer Science, pages 258-272, 1998. Springer.
(Compressed Postscript
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 Institute of Technology, April 1984. .pdf
1983
Eshrat Arjomandi, Michael J. Fischer, and Nancy A. Lynch.
Efficiency of synchronous versus asynchronous distributed systems.
Journal of the ACM, 30(3):449--456, July 1983. pdf
Danny Dolev, Nancy A. Lynch, Shlomit S. Pinter, Eugene W. Stark,
and William E. Weihl. Reaching approximate agreement in the
presence of faults. In Proceedings of 3rd Symposium on
Reliability in Distributed Software and Database Systems, pages
145--154, October 1983. pdf
Michael Fischer, Nancy Lynch, James Burns, and Allan Borodin. The
colored ticket algorithm. Technical Memo MIT/LCS/TM-269, Laboratory
for Computer Science, Massachusetts Institute of Technology, August
1983. .pdf
Michael Fischer, Nancy Lynch, and Michael S. Paterson.
Impossibility of distributed consensus with one faulty process. In
Proceedings of the 2nd ACM Symposium on Principles of Database
Systems, pages 1--7, Atlanta, GA, March 1983. .pdf
Nancy Lynch and Michael Fischer. A technique for decomposing
algorithms which use a single shared variable. Journal of
Computer and System Sciences, 27(3):350--377, December 1983. .pdf
Nancy Lynch. Concurrency control for resilient nested
transactions. In Proceedings of the Second ACM SIGACT-SIGMOD
Symposium on Principles of Database Systems, pages 166--181,
Atlanta, Georgia, March 1983. .pdf
Nancy A. Lynch. Concurrency control for resilient nested
transactions. MIT Laboratory for Computer Science Technical
Report MIT/LCS/TR-285, Cambridge, MA 02139, February 1983. (Note,
same TR number was used in 1985; see .pdf)
Nancy Lynch. Multilevel atomicity--a correctness criterion for
database concurrency control. ACM Transactions on Database
Systems, 8(4):484--502, December 1983. .pdf
1982
James E. Burns, Paul Jackson, Nancy A. Lynch, Michael J. Fischer,
and Gary L. Peterson. Data requirements for implementation of
N-process mutual exclusion using a single shared variable.
Journal of the ACM, 29(1):183--205, January 1982. pdf
Danny Dolev, Michael J. Fischer, Rob Fowler, Nancy A. Lynch, and
H. Raymond Strong. An efficient algorithm for Byzantine agreement
without authentication. Information and Control,
52(3):257--274, March 1982. .pdf
Danny Dolev, Michael J. Fischer, Rob Fowler, Nancy A. Lynch, and
H. Raymond Strong. An efficient Byzantine agreement
without authentication. IBM Research Report RJ3428 (40914),
Computer Science, IBM Research Division, Yorktown Heights, NY, March
22, 1982. .pdf
Richard A. DeMillo, Nancy A. Lynch, and Michael J. Merritt.
Cryptographic protocols. In Proceedings of the Fourteenth
Annual ACM Symposium on Theory of Computing, pages 383--400, San
Francisco, California, May 1982. pdf
Michael J. Fischer, Nancy D. Griffeth, and Nancy A. Lynch. Global
states of a distributed system. IEEE Transactions on Software
Engineering, SE-8(3):198--202, May 1982. pdf
Michael J. Fischer and Nancy A. Lynch. A lower bound for the time
to assure interactive consistency. Information Processing
Letters, 14(4):183--186, June 1982. pdf
Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson.
Impossibility of distributed consensus with one faulty process.
Technical Report MIT/LCS/TR-282, Laboratory for Computer Science,
Massachusetts Institute of Technology, Cambridge, MA, 02139, September 1982.
pdf
Nancy Lynch, Michael Fischer, and Rob Fowler. A simple and efficient
Byzantine generals algorithm. In Proceedings of the 2nd
Symposium on Reliability in Distributed Software and Database
Systems, pages 46--52, Pittsburgh, PA, July 1982. pdf
Nancy Lynch, Michael Fischer, and Rob Fowler. A simple and efficient
Byzantine generals algorithm. Technical Report GIT-ICS-82/02,
School of Information and Computer Science, Georgia Institute of
Technology, February, 1982. pdf
Nancy Lynch. Accessibility of values as a determinant of relative
complexity of algebras. Journal of Computer and System
Sciences, 24(1):101--113, February 1982. pdf
Nancy Lynch. Multilevel atomicity--a correctness criterion for
database concurrency control. Technical Report MIT/LCS/TR-281,
Laboratory for Computer Science, Massachusetts Institute of
Technology, Cambridge, MA, 02139, August 1982. pdf
Nancy A. Lynch. Multilevel atomicity. In
Proceedings of the First ACM SIGACT-SIGMOD Symposium on Principles of
Database Systems, pages 63--69, Los Angeles, CA, March 1982. .pdf
1981
Eshrat Arjomandi, Michael J. Fischer, and Nancy A. Lynch. A
difference in efficiency between synchronous and asynchronous
systems. Technical Report GIT-ICS-81/07, School of Information and
Computer Science, Georgia Institute of Technology, June, 1981. .pdf
Allan Borodin, Michael J. Fischer, David G. Kirkpatrick, Nancy
A. Lynch, and Martin Tompa. A time-space tradeoff for sorting on
non-oblivious machines. Journal of Computer and System
Sciences, 22(3):351--364, June 1981. .pdf
A. Borodin, L. Guibas, N. Lynch, and A. Yao. Efficient
searching using partial ordering. Information Processing
Letters, 12(2):71--75, April 1981. .pdf
Michael J. Fischer, Leonidas Guibas, Nancy D. Griffeth, and Nancy
Lynch. Optimal placement of identical resources in a distributed network. In
Proceedings of the 2nd IEEE International Conference on Distributed Computing
Systems, pages 324--336, April 1981. .pdf
Michael Fischer, Nancy Griffeth, and Nancy Lynch. Global states of a
distributed system. In Proceedings of IEEE Symposium on
Reliability in Distributed Software and Database Systems, pages 33--38,
Pittsburgh, PA, July 1981. .pdf
Nancy Lynch. Multilevel atomicity--a correctness criterion for
database concurrency control. Technical Report GIT-ICS-81/05,
School of Information and Computer Science, Georgia Institute of
Technology, May, 1981. .pdf
Michael Fischer, Nancy Griffeth, and Nancy Lynch. Global states of a
distributed system. Technical Report
GIT-ICS-81/06, School of Information and Computer Science, Georgia
Institute of Technology, June, 1981. .pdf
Michael J. Fischer and Nancy A. Lynch. A lower bound for the time
to assure interactive consistency. Technical Report
GIT-ICS-81/13, School of Information and Computer Science, Georgia
Institute of Technology, September, 1981. .pdf
Nancy A. Lynch. Upper bounds for static resource allocation in a
distributed system. Journal of Computer and System
Sciences, 23(2):254--278, October 1981. .pdf
N. Lynch and E. K. Blum. Relative complexity of algebras.
Mathematical Systems Theory 14, pages 193--214, 1981. .pdf
Nancy A. Lynch and Michael J. Fischer. On describing the behavior
and implementation of distributed systems. Theoretical Computer
Science, 13(1):17--43, 1981. Special issue on Semantics of
Concurrent Computation. .pdf
1980
James Burns and Nancy A. Lynch. Mutual exclusion using indivisible
reads and writes. In Proceedings of the 18th Allerton
Conference on Communication, Control and Computing, pages 833--842,
Monticello, IL, October 1980. .pdf
Michael J. Fischer, Leonidas Guibas, Nancy D. Griffeth, and Nancy
Lynch. Optimal placement of identical resources in a distributed network.
Technical Report GIT-ICS-80/13, School of Information and Computer
Science, Georgia Institute of Technology, October, 1980. .pdf
Nancy A. Lynch. Fast allocation of nearby resources in a distributed
system. In Proceedings of the Twelfth Annual ACM Symposium on
Theory of Computing, pages 70--81, Los Angeles, CA., April 1980.
Chosen for submission to special issue of Journal of Computer and
System Sciences. pdf
Nancy A. Lynch and Michael J. Fischer. On describing the behavior
and implementation of distributed systems. Technical Report
GIT-ICS-79/03, School of Information and Computer Science, Georgia
Institute of Technology, March, 1980. Revised edition. pdf
Nancy Lynch and Michael Fischer. A technique for decomposing
algorithms which use a single shared variable. Technical Report
GIT-ICS-80/14, School of Information and Computer Science, Georgia
Institute of Technology, October, 1980. pdf
Nancy A. Lynch. Straight-line program length as a parameter for
complexity analysis. Journal of Computer and System
Sciences, 21(3):251--280, December 1980. .pdf
N. N. Lynch and E. K. Blum. Relative complexity of operations on
numeric and bit-string algebras. Mathematical Systems Theory
13, pages 187--207, 1980. .pdf
1979
Michael J. Fischer, Nancy A. Lynch, James E. Burns, and Allan Borodin.
Resource allocation with immunity to limited process failure.
In 20th Annual Symposium on Foundations of Computer Science,
pages 234--254, San Juan, Puerto Rico, October 1979. IEEE. pdf
There is also a long version dated April 1981.
N. N. Lynch and E. K. Blum.
A difference in expressive power between flowcharts and recursion
schemes.
Mathematical Systems Theory 12, pages 205--211, 1979. .pdf
Nancy Lynch and Michael Fischer.
On describing the behavior and implementation of distributed systems.
In G. Kahn, editor, Proceedings of 1979 Conference on Semantics
of Concurrent Computation, volume 70 of Lecture Notes in Computer
Science, pages 147--171. Springer-Verlag, 1979.
Chosen for submission to special issue of Theoretical Computer
Science. .pdf
1978
James E. Burns, Michael J. Fischer, Paul Jackson, Nancy A. Lynch, and G. L.
Peterson.
Shared data requirements for implementation of mutual exclusion using
a test-and-set primitive.
In Proceedings of the International Conference on Parallel
Processing, pages 79--87, Wayne State University, Detroit, MI.,
August 1978. .pdf
Nancy Lynch.
Straight-line program length as a parameter for complexity measures.
In Proceedings of Tenth Annual ACM Symposium on Theory of
Computing, pages 150--161, San Diego, CA, May 1978. pdf
N. Lynch and R. J. Lipton.
On structure preserving reductions.
SIAM Journal on Computing, 7(2):119--126, May 1978. .pdf
Nancy Lynch.
Log space machines with multiple oracle tapes.
Theoretical Computer Science, 6:25--39, 1978. .pdf
1977
Seymour Ginsburg and Nancy Lynch.
Derivation complexity in context-free grammar forms.
SIAM Journal on Computing, 6(1):123--138, March 1977. .pdf
N. A. Lynch and E. K. Blum.
Efficient reducibility between programming systems: Preliminary
report.
In Proceedings of 9th Annual ACM Symposium on Theory of
Computing, pages 228--238, Boulder, CO., May 1977. pdf
Nancy Lynch.
Log space recognition and translation of parenthesis languages.
Journal of the ACM, 24(4):583--590, October 1977. pdf
1976
Seymour Ginsburg and Nancy Lynch.
Size complexity in context-free grammar forms.
Journal of the ACM, 23(4):582--598, October 1976. pdf
Richard E. Ladner and Nancy A. Lynch.
Relativization of questions about log space computability.
Mathematical Systems Theory, 10:19--32, 1976. .pdf
Nancy Lynch.
Complexity-class encoding sets. Journal of
Computer and System Sciences, 13(1):100--118, August 1976. .pdf
Nancy Lynch, Albert Meyer, and Michael Fischer.
Relativization of the theory of computational complexity.
Transactions of the American Mathematical Society,
220:243--287, 1976.pdf
1975
Seymour Ginsburg and Nancy Lynch.
Comparative complexity of grammar forms.
In Proceedings of the Seventh Annual ACM Symposium on Theory of
Computing, pages 153--158, Albuquerque, NM, May 1975. pdf
Richard E. Ladner, Nancy A. Lynch, and Alan L. Selman.
A comparison of polynomial-time reducibilities.
Theoretical Computer Science, 1(2):103--123, 1975. .pdf
Nancy Lynch.
Helping: Several formalizations.
Journal of Symbolic Logic, 40(4):555--566, December 1975.
pdf
Nancy Lynch.
On reducibility to complex or sparse sets.
Journal of the ACM, 22(3):341--345, July 1975. pdf
1974
Richard Ladner, Nancy Lynch, and Alan Selman.
Comparison of polynomial-time reducibilities.
In Proceedings of the Sixth Annual ACM Symposium on Theory of
Computing, pages 110--121, Seattle, WA, April 1974. pdf
Nancy Lynch.
Approximations to the halting problem.
Journal of Computer and Systems Sciences, 9(2):143--150,
October 1974. .pdf
1973
Nancy Lynch, Albert Meyer, and Michael Fischer.
Sets that don't help.
In Proceedings of the Fifth Annual ACM Symposium on Theory of
Computing, pages 130--134, Austin, TX, April 1973. pdf
1972
Nancy A. Lynch. Relativization of the theory of computational
complexity. Ph.D. Thesis, Massachusetts Institute of Technology
Department of Mathematics, 1972. 