To appear
Seth Gilbert, Nancy Lynch, and Alex Shvartsman. RAMBO: A Robust, Reconfigurable Atomic Memory Service for Dynamic Networks. To appear in Distributed Computing. .pdf
Fabian Kuhn and Rotem Oshman. Gradient Clock Synchronization using
Reference Broadcasts. In Proceedings of the 13th International Conference on Principle Of DIstributed Systems (OPODIS), Nimes, France, December 2009. To appear.
2009
Paul Attie, Rachid Guerraoui, Petr Kouznetsov, Nancy Lynch, and Sergio Rajsbuam. The Impossibility of Boosting Distributed Service Resilience. Submitted for journal publication, September 2009. .pdf
Gregory Chockler, Seth Gilbert, Vincent C. Gramoli, Peter M.
Musial, and Alex A. Shvartsman. Reconfigurable Distributed Storage
for Dynamic Networks. Journal of Parallel and
Distributed Computing, 69(1):100-116, January 2009. ScienceDirect
Alejandro Cornejo, Nancy Lynch, Saira Viqar, Jennifer Welch.
A Neighbor Discovery Service Using an Abstract MAC Layer. Forty-Seventh Annual Allerton Conference, Champaign-Urbana, IL, October, 2009. Invited paper.
Alex Cornejo, Fabian Kuhn, Ruy Ley-Wild, and Nancy Lynch. Keeping Mobile Robot Swarms Connected. DISC 2009: 23rd
International Symposium on Distributed Computing, Elche/Elx,
Spain, September 23-25, 2009. Extended version is Technical Report MIT-CSAIL-TR-2009-027, MIT CSAIL, Cambridge, MA, June 2009. .pdf
Alejandro Cornejo and Nancy Lynch. Minimum Spanning Trees and
Cone-Based Topology Control. Proceedings of the 28th Annual ACM
Symposium on Principles of Distributed Computing, Calgary, Canada,
August 2009. .pdf
Shlomi Dolev, Seth Gilbert, Rachid Guerraoui, Fabian Kuhn and Calvin
Newport. The Wireless Synchronization Problem. Proceedings of
the ACM Symposium on the Principles of Distributed Computing
(PODC), Calgary, Alberta, Canada, August 2009. .pdf
Shlomi Dolev, Seth Gilbert, Dariusz Kowalski, Fabian Kuhn, Nancy
Lynch, Calvin Newport. Reliable Distributed Computing on Unreliable
Radio Channels. The MobiHoc S3 Student Workshop, New Orleans, LA,
May 2009. Invited paper. .pdf
Chryssis Georgiou, Nancy Lynch, Panayiotis Mavrommatis, and Joshua
Tauber.
Automated Implementation of Complex Distributed Algorithms
Specified in the IOA Language.
International Journal on Software Tools for Technology Transfer (STTT), 11(2):153-171, 2009. Springer. Springer link.
Seth Gilbert, Nancy Lynch, Sayan Mitra, and Tina Nolte. Self-Stabilizing Robot Formations Over Unreliable Networks. ACM Transactions on Autonomous and Adaptive Systems, 4(3):17.2-17.27, July 2009. .pdf
Seth Gilbert, Rachid Guerraoui, Darek Kowalski, and Calvin Newport. Interference-Resilient Information Exchange. In Proceedings of the IEEE Conference on Computer Communications (INFOCOM), Rio de Janeiro, Brazil, April 19-25, 2009. InfoScience. .pdf
Seth Gilbert, Rachid Guerraoui, and Calvin Newport.
Of Malicious Motes and Suspicious Sensors: On the Efficiency of Malicious Interference in Wireless Networks. Theoretical Computer Science,410(6-7):546-569, February 28, 2009. ScienceDirect.
Rachid Guerraoui, Maurice Herlihy, Petr Kuznetsov, Nancy Lynch, and Calvin Newport. On the Weakest Failure Detector Ever. Distributed Computing, 21(5):353-366, February 2009. Special Issue . Springer Link. .pdf
Fabian Kuhn, Nancy Lynch, and Calvin Newport. The Abstract MAC Layer. DISC 2009: 23rd International Symposium on Distributed
Computing, Elche/Elx, Spain, September 23-25, 2009. .pdf
Fabian Kuhn. Weak Graph Colorings: Distributed Algorithms and
Applications. Proceedings of the 21st ACM Symposium on Parallelism in
Algorithms and Architectures (SPAA), Calgary, Alberta, Canada, August
2009.
Fabian Kuhn, Thomas Locher, and Rotem Oshman. Gradient Clock
Synchronization in Dynamic Networks. Proceedings of the 21st ACM Symposium
on Parallelism in Algorithms and Architectures (SPAA), Calgary,
Alberta, Canada, August 2009. .pdf
Fabian Kuhn, Nancy Lynch, and Rotem Oshman.
Distributed Computation in Dynamic Networks.
Technical Report MIT-CSAIL-TR-2009-058, MIT Computer Science and Artificial Intelligence Laboratory, Cambridge, MA, November 2009. .pdf
Fabian Kuhn. Local Multicoloring Algorithms: Computing a
Nearly-Optimal TDMA Schedule in Constant Time. Proceedings of the
Symposium on Theoretical Aspects of Computer Science (STACS),
Freiburg, Germany, February 2009.
Fabian Kuhn, Nancy Lynch and Calvin Newport. Brief Announcement:
Hardness of Broadcasting in Wireless Networks with Unreliable
Communication. Proceedings of the ACM Symposium on the
Principles of Distributed Computing (PODC), Calgary, Alberta,
Canada, August 2009. .pdf
Fabian Kuhn, Nancy Lynch, and Calvin Newport. The Abstract MAC Layer.
Technical Report MIT-CSAIL-TR-2009-021, MIT CSAIL, Cambridge, MA, 02139, May 11, 2009. .pdf.
Earlier version as MIT-CSAIL-TR-2009-009, MIT CSAIL, Cambridge, MA, February 20, 2009.
Calvin Newport and Nancy Lynch. Modeling Radio Networks. In Mario Bravetti, Gianluigi Zavattaro, editors, CONCUR 2009 - Concurrency Theory, Proceedings of the 20th International Conference, Bologna, Italy, September, 2009, volume 5710 of Lecture Notes in Computer Science, pages 481-495,
2009. Springer. .pdf
Calvin Newport and Nancy Lynch. Modeling Radio Networks. Technical Report MIT-CSAIL-TR-2009-023, MIT Computer Science and Artificial Intelligence Laboratory, Cambridge, MA, June 4, 2009. .pdf
Calvin Newport. Distributed Computation on Unreliable Radio Channels. Ph.D. thesis, MIT Department of Electrical Engineering and Computer Science, Cambridge, MA, September 2009.
Tina Nolte. Virtual Stationary Timed Automata for Mobile Networks. Ph.D Thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA, February, 2009. .pdf Warning to the Reader
Tina Nolte, Shlomi Dolev, Limor Lahiani, and Nancy Lynch.
Self-Stabilizing Message Routing in Mobile ad hoc Networks.
Technical Report MIT-CSAIL-TR-2009-003, MIT CSAIL, Cambridge, MA,
January 2009. Closely based on chapters 12-14 of Tina Nolte's MIT PhD thesis, 2009. .pdf
Rotem Oshman. An Automata-Theoretic Dynamic Completeness Criterion for Bounded Model-Checking. 10th International Conference on Verification, Model Checking, and Abstract Interpretation (VMCAI'09), Savannah, GA, January 2009. Springerlink
Venugopalan Ramasubramanian, Dahlia Malkhi, Fabian Kuhn, Mahesh
Balakrishnan, Archit Gupta, Adityla Akella. On the Treeness of
Internet Latency and Bandwith. Proceedings of SIGMETRICS/Performance,
Seattle, WA, June 2009.
Shinya Umeno. Machine-Assisted Parameter Synthesis of the Biphase
Mark Protocol Using Event Order Abstraction. 7th
International Conference on Formal Modelling and Analysis of Timed
Systems (FORMATS 2009), Budapest, Hungry, September 13-16, 2009. .pdf
Shinya Umeno. Timeout Order Abstraction for
Time-Parametric Verification of
Loosely Synchronized Real-Time Distributed Systems. Submitted for publication.
Jiang Wu, Nancy Griffeth, Nancy Lynch, Calvin Newport, and Ralph Droms. Simulating Fixed Virtual Nodes for Adapting Wireline Protocols to MANET. The 8th IEEE International Symposium on Network Computing and Applications (IEEE NCA09), July 9, 2009. .pdf Best Paper Award.
2008
Myla Archer, Hongpong Lim, Nancy Lynch, Sayan Mitra, and Shinya Umeno.
Specifying and proving properties of timed I/O automata using Tempo.
Journal of Design Automation for Embedded Systems, 2(1-2):139-170, June 2008. Springer. .pdf
Ran Canetti, Ling Cheung, Dilsun Kaynar, Nancy Lynch, and Olivier Pereira.
Modeling Computational Security in Long-Lived Systems, Version 2. Technical Report MIT-CSAIL-TR-2008-068, Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA, November 2008. .pdf
R. Canetti, L. Cheung, D. Kaynar, M. Liskov, N. Lynch, O. Pereira, and R. Segala. Analyzing Security Protocol Using Time-Bounded Task-PIOAs. Journal of Discrete Event Dynamic Systems (DEDS), 18(1):111-159, March 2008. (Appears online February 2008). Springer. .pdf
Ran Canetti, Ling Cheung, Dilsun Kaynar, Nancy Lynch, and Olivier Pereira.
Modeling Computational Security in Long-Lived Systems.
In Franck van Breugel, Marsha Chechik, editors, CONCUR 2008 - Concurrency Theory: 19th International Conference, Toronto, Canada, August, 2008, volume 5201 of Lecture Notes in Computer Science, pages 114-130, 2008. Springer. Available as Cryptology ePrint Archive as report 2007/406.
.pdf.
Gregory Chockler, Seth Gilbert, and Nancy Lynch. Virtual Infrastructure for Collision-Prone Wireless Networks.
Proceedings of the 27th Symposium on Principles of Distributed Computing (PODC), pages 233-242, Toronto, Canada, August 2008. .pdf
Gregory Chockler, Murat Demirbas, Seth Gilbert, Nancy Lynch, Calvin Newport, and Tina Nolte. Consensus and collision detectors in radio networks. Distributed Computing, 21(1):55-84, June 2008. 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. .pdf
Shlomi Dolev, Seth Gilbert, Rachid Guerraoui, and Calvin Newport. Secure Communication over Radio Channels. Proceeding of the 27th
Symposium on Principles of Distributed Computing (PODC), Toronto, Canada, August 2008. .pdf
Rui Fan. Lower Bounds in Distributed Computing. Ph.D Thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA, February 2008. .pdf
Seth Gilbert, Nancy Lynch, Sayan Mitra, and Tina Nolte.
Self-Stabilizing Mobile Robot Formations with Virtual Nodes.
In Sandeep S. Kulkarni, Andre Schiper, editors, Stabilization, Safety and Security of Distributed Systems: Proceedings of the 10th Symposium (SSS 2008), Detroit, Michigan, November 2008, volume 5340 of Lecture Notes in Computer Science, pages 188-202, 2008. Springer. .pdf
R. Grosu, X. Huang, N. Lynch, S.A. Smolka. Model Checking TIOA.
Technical Report CS-CL-08-02,Department of Computer Science, Stony Brook
University, Stony Brook, NY, USA, 2008.
Rachid Guerraoui and Nancy A. Lynch.
A general characterization of indulgence.
ACM Transactions on Autonomous and Adaptive Systems (TAAS), 3(4), November 2008.
Daniel Liberzon, Nancy Lynch, and Sayan Mitra.
Verifying Average Dwell Time of Hybrid Systems. ACM Transactions in Embedded Computing Systems 8(1):1-37, 2008. .pdf
Nancy Lynch, Laurent Michel, and Alexander Shvartsman. Tempo: A Toolkit for The Timed Input/Output Automata Formalism. First International Conference on Simulation Tools and Techniques for Communications, Networks, and Systems (SIMUTools 2008), Industrial Track: Simulation Works. Conference Proc. CD, paper 3105, 8 pages, Marseille, France, March 4-7, 2008. .pdf
Mike Spindel. Simulation and Evaluation of the Reactive Virtual Node Layer.
Master of Engineering Thesis, Department of Electrical
Engineering and Computer Science, Massachusetts Institute of
Technology, Cambridge, MA, May 2008. .pdf
Shinya Umeno. Event order abstraction for parametric real-time system verification. International Conference on Embedded Software (EMSOFT 2008), Atlanta, Georgia, pages 1-10, October 2008. .pdf
Shinya Umeno. Event Order Abstraction for Parametric Real-Time System
Verification. Technical Report MIT-CSAIL-TR-2008-048, Massachusetts Institute of Technology, Cambridge MA, 2008. .pdf
Shinya Umeno. Event order abstraction for parametric timed verification
. Second Workshop on Event-Based Semantics,
St. Louis MO, USA. April 21, 2008. .pdf
2007
Matthew D. Brown. Air Traffic Control Using Virtual Stationary Automata. Master of Engineering Thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA, September 2007. .pdf
Matthew Brown, Seth Gilbert, Nancy Lynch, Calvin Newport, Tina
Nolte, and Michael Spindel. The Virtual Node Layer: A Programming
Abstraction for Wireless Sensor Networks. ACM SIGBED Review, 4(3), July 2007. Also, Proceedings of the
the International Workshop on Wireless Sensor Network Architecture
(WWSNA), Cambridge, MA, April, 2007. .pdf
Ran Canetti, Ling Cheung, Dilsun Kaynar, Nancy Lynch, and Olivier Pereira.
Modeling Computational Security in Long-Lived Systems. Cryptology ePrint Archive Report 2007/406. .pdf.
Ran Canetti, Ling Cheung, Dilsun Kaynar, Nancy Lynch, and Olivier
Pereira. Compositional Security for Task-PIOAs. Proceedings of the 20th IEEE Computer Security Foundations
Symposium (CSF 2007), Venice, Italy, pages 125-139, July 2007. .pdf
Ran Canetti, Ling Cheung, Nancy Lynch, and Olivier Pereira.
On the Role of Scheduling in Simulation-Based Security.
7th International Workshop on Issues in the Theory of Security (WITS'07),
Braga, Portugal, March 2007. Also, ePrint Report 2007/12, Cryptology
ePrint archive, 2007. .pdf
Ran Canetti, Ling Cheung, Dilsun Kaynar, Moses Liskov, Nancy Lynch,
Olivier Pereira, and Roberto Segala. Using Task-Structured
Probabilistic I/O Automata to Analyze an Oblivious Transfer Protocol.
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
Ling Cheung, Joseph A. Cooley, Roger Khazan, and Calvin Newport.
Collusion-Resistant Group Key Management Using Attribute-Based
Encryption. Proceedings of 1st International Workshop on
Group-Oriented Cryptographic Protocols, Wroclaw, Poland, July 2007. .pdf
Ling Cheung and Calvin Newport.
Provably Secure Ciphertext Policy ABE.
Proceedings of the 14th ACM Conference on Computer and Communications
Security (CCS), Alexandria, VA, October, 2007. Also, ePrint Report 2007/183, Cryptology ePrint archive, 2007. .pdf
Ling Cheung, Sayan Mitra and Olivier Pereira. Verifying Statistical
Zero Knowledge with Approximate Implementations. Cryptology ePrint Archive Report 2007/195. .pdf
Shlomi Dolev, Seth Gilbert, Rachid Guerraoui, and Calvin Newport. Gossiping in a Multi-Channel Radio Network: An Oblivious Approach to
Coping with Malicious Interference. In Andrzej Pelc, editor Proceedings of the 21th International Symposium on Distributed
Computing (DISC 2007), Lemesos, Cyprus, September, 2007, volume 4731 of Lecture Notes in Computer Science, pages 208-222, 2007. Springer. .pdf
Rui Fan, Ralph Droms, Nancy Griffeth, and Nancy Lynch. The DHCP
Failover Protocol: A Formal Perspective. In John Derrick, Juri Vain, editors, 27th IFIP WG 6.1 International Conference on Formal Methods for
Networked and Distributed Systems (FORTE 2007), Tallinn, Estonia, June 26-29, 2007, volume 4574 of Lecture Notes in Computer Science,
pages 211-226, 2007. Springer. .pdf
Seth Gilbert. Virtual Infrastructure for Wireless Ad Hoc
Networks. Ph.D Thesis, Department of Electrical Engineering and Computer Science,
Massachusetts Institute of Technology, Cambridge, MA 02139, 2007. .pdf
Radu Grosu, Sayan Mitra, Pei Ye, Scott Smolka, Emilia Entcheva, and I. O. Ramakrishnan. Learning cycle-linear hybrid automata of excitable cell models. In Hybrid Systems: Computation and Control (HSCC 07), volume 4416 of Lecture Notes in Computer Science, pages 245-258, April 2007. .pdf
Rachid Guerraoui, Maurice Herlihy, Petr Kouznetsov, Nancy Lynch, and Calvin Newport. On the weakest failure detector ever. Proceedings of the Twenty-Sixth Annual ACM Symposium on the Principles
of Distributed Computing (PODC), Portland, Oregon, pages 235-243, August 2007. .pdf
Xavier Koegler (supervised by Nancy Lynch). Around the Tempo Toolset Userguide. March 20th-August 31st, 2007. .pdf
Carolos Livadas and Nancy A. Lynch. A Reliable Broadcast Scheme
for Sensor Networks. Technical Report MIT-LCS-TR-915, MIT Computer Science and
Artificial Intelligence Laboratory, Cambridge, MA, February 2007
(Revision of earlier version dated August 2003). .pdf
Nancy A. Lynch. DISC 20th Anniversary, Invited Talk: My Early Days in Distributed Computing Theory: 1979-1982. In Andrzej Pelc, editor, Distributed Computing, 21st International Symposium, DISC 2007, Lemesos, Cyprus, September 24-26, 2007, volume 4731 of Lecture Notes in Computer Science, page 505, 2007. Springer.
Nancy A. Lynch. Distributed computing theory: algorithms, impossibility results, models, and proofs. Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC 2007), San Diego, California, page 247, June 11-13, 2007.
Nancy Lynch, Roberto Segala, and Frits Vaandrager.
Observing Branching Structure through Probabilistic Contexts. Siam
Journal on Computing, 37(4):977-1013, September 2007. .pdf
Sayan Mitra. A Verification Framework for Ordinary and
Probabilistic Hybrid Systems. Ph.D Thesis, Department of
Electrical Engineering and Computer Science, Massachusetts Institute
of Technology, Cambridge, MA, September 2007. .pdf
Sayan Mitra and Nancy Lynch. Proving approximate implementation relations for Probabilistic I/O Automata. Electronic Notes in Theoretical Computer Science, 174(8):71-93, 2007. .pdf
Sayan Mitra and Nancy Lynch. Trace-based semantics of Probabilistic timed I/O automata.
Hybrid Systems: Computation and Control (HSCC 2007), Pisa, Italy,
April 3-5, 2007, volume 4416 of Lecture Notes in Computer Science, pages 718-722, 2007. Springer. .pdf
Tina Nolte and Nancy Lynch. Self-stabilization and Virtual Node Layer
Emulations. In Toshimitsu Masuzawa, Sebastien Tixeuil, editors, Stabilization, Safety, and Security of Distributed Systems, 9th International Symposium (SSS 2007), Paris, France, November 2007, volume 4838 of Lecture Notes in Computer Science, pages 394-408, 2007. Springer.
.pdf
Tina Nolte and Nancy Lynch. A Virtual Node-Based Tracking Algorithm for
Mobile Networks. International Conference on
Distributed Computing Systems (ICDCS 2007), Toronto, Canada, June, 2007. .pdf
Shinya Umeno and Nancy Lynch. Safety Verification of an Aircraft
Landing Protocol: A Refinement Approach. In Alberto Bemporad, Antonio Bicchi, Giorgio C. Buttazzo, editors, Hybrid Systems: Computation and Control (HSCC 2007), Pisa, Italy, April 3-5, 2007, volume 4416 of Lecture Notes in Computer Science, pages 557-572, 2007. Springer. .pdf
2006
Myla Archer, HongPing Lim, Nancy Lynch, Sayan Mitra and Shinya
Umeno. Specifying and Proving Properties of Timed I/O Automata in the TIOA
Toolkit. Fourth ACM-IEEE International
Conference on Formal Methods and Models for Codesign (MEMOCODE'06),
Napa Valley, California, pages 129-138, July, 2006
. .pdf
Paul Attie. On the Refinement of Liveness Properties of
Distributed Systems. Manuscript, 2006. pdf
Michael A. Bender, Jeremy T. Fineman, and Seth Gilbert.
Contention Resolution with Heterogeneous Job Sizes. Proceedings of the 14th Annual European Symposium on Algorithms,
September, 2006. .pdf
Ran Canetti, Ling Cheung, Dilsun Kaynar, Moses Liskov, Nancy Lynch,
Olivier Pereira, and Roberto Segala. Time-bounded Task-PIOAs: A
Framework for Analyzing Security Protocols. In Shlomi Dolev, editor, Distributed Computing, 20th International Symposium on Distributed Computing (DISC 2006), Stockholm, Sweden, September 2006, volume 4167 of Lecture Notes in Computer Science, pages 238-253, 2006. Springer. Invited paper.
.pdf
Ran Canetti, Ling Cheung, Dilsun Kaynar, Moses Liskov, Nancy Lynch,
Olivier Pereira, and Roberto Segala. Task-Structured Probabilistic
I/O Automata. Technical Report MIT-CSAIL-TR-2006-060, CSAIL,
Massachusetts Institute of Technology, Cambridge, MA, August, 2006..pdf
Ran Canetti, Ling Cheung, Dilsun Kaynar, Moses Liskov, Nancy Lynch,
Olivier Pereira, and Roberto Segala.
Task-Structured Probabilistic I/O Automata.
Proceedings the 8th International Workshop on Discrete
Event Systems (WODES'06), Ann Arbor, Michigan, July, 2006. .pdf
Ran Canetti, Ling Cheung, Dilsun Kaynar, Moses Liskov, Nancy Lynch,
Olivier Pereira, and Roberto Segala. Using Task-Structured Probabilistic
I/O Automata to Analyze Cryptographic Protocols. In V. Cortier,
S. Kremer, editors, Workshop on Formal and Computational
Cryptography - FCC 2006, pages 34--39, July 2006. .pdf
Ran Canetti, Ling Cheung, Dilsun Kaynar, Moses Liskov, Nancy Lynch,
Olivier Pereira, and Roberto Segala. Using Task-Structured
Probabilistic I/O Automata to Analyze an Oblivious Transfer Protocol.
Technical Report MIT-CSAIL-TR-2006-047, CSAIL, Massachusetts Institute of
Technology, Cambridge, MA, June 19, 2006. (Latest version is
MIT-CSAIL-TR-2007-011). .pdf
Ran Canetti, Ling Cheung, Dilsun Kaynar, Moses Liskov, Nancy Lynch,
Olivier Pereira, and Roberto Segala. Using Probabilistic I/O
Automata to Analyze an Oblivious Transfer Protocol. Technical
Report MIT-CSAIL-TR-2006-046, CSAIL, Massachusetts Institute of
Technology, Cambridge, MA, January 10, 2006. .pdf
Ran Canetti, Ling Cheung, Dilsun Kaynar, Moses Liskov, Nancy Lynch,
Olivier Pereira, and Roberto Segala. Task-Structured Probabilistic
I/O Automata. Technical Report MIT-CSAIL-TR-2006-023, CSAIL,
Massachusetts Institute of Technology, Cambridge, MA, March, 2006. .pdf
Ran Canetti, Ling Cheung, Dilsun Kaynar, Moses Liskov, Nancy Lynch,
Olivier Pereira, and Roberto Segala. Using Task-Structured
Probabilistic I/O Automata to Analyze an Oblivious Transfer
Protocol. Technical Report MIT-CSAIL-TR-2006-019, CSAIL, Massachusetts Institute of
Technology, Cambridge, MA, March, 2006. .pdf
Ling Cheung, Nancy Lynch, Roberto Segala, and Frits Vaandrager.
Switched Probabilistic PIOA: Parallel Composition via
Distributed Scheduling. Theoretical Computer Science, 365(1-2):83-108, November 2006.
.pdf
Gregory Chockler, Seth Gilbert, and Boaz Patt-Shamir. Communication-Efficient
Probabilistic Quorum Systems. Proceedings of the IEEE International
Workshop on Foundations and Algorithms for Wireless Networking (FAWN),
March 29-31, 2006. .pdf
Constantinos Djouvas, Nancy D. Griffeth, and Nancy A. Lynch.
Testing Self-Similar Networks Electronic Notes in
Theoretical Computer Science, Proceedings of the Second Workshop on
Model Based Testing (MBT 2006), 164(4):67-82, October 2006. .pdf
Rui Fan and Nancy Lynch. Gradient Clock Synchronization.
Distributed Computing, 18(4):255-266, March, 2006. .pdf.
Rui Fan and Nancy Lynch. An Ω (n log n) Lower Bound on the Cost of Mutual Exclusion. Proceedings of the
Twenty-Fifth Annual Symposium on Principles of Distributed Computing
(PODC'06), Denver, Colorado, pages 275-284, July 2006. .pdf
Seth Gilbert, Rachid Guerraoui, and Calvin Newport. Of
Malicious Motes and Suspicious Sensors: On the Efficiency of Malicious
Interference in Wireless Networks. Proceedings
of the 10th International Conference On Principles Of Distributed
Systems (OPODIS), Bordeaux, France, December 12-15, 2006.
Seth Gilbert, Rachid Guerraoui, and Calvin Newport. Of
Malicious Motes and Suspicious Sensors. Technical Report
MIT-CSAIL-TR-2006-026, CSAIL, Massachusetts Institute of Technology,
Cambridge, MA, April 2006. .pdf
Rachid Guerraoui and Nancy Lynch. A General Characterization of
Indulgence. In Ajoy Kumar Datta, Maria Gradinariu, editors,
Stabilization, Safety, and Security of Distributed Systems, 8th
International Symposium (SSS 2006), Dallas, TX, November 17-19,
2006, volume 4280 of Lecture Notes in Computer Science,
pages 16-34, 2006. Springer.
Dilsun K. Kaynar, Nancy Lynch, Roberto Segala, and Frits Vaandrager.
The Theory of Timed I/O Automata.Synthesis Lectures on Computer Science, Morgan Claypool
Publishers, 2006. Revised and shortened version
of Technical Report MIT-LCS-TR-917a (from 2004). .pdf
K. Konwar, P.M. Musial, N.C. Nicolau, and A.A. Shvartsman.
Implementing Atomic Data through Indirect Learning in Dynamic
Networks. Technical Report MIT-CSAIL-TR-2006-070, Computer
Science and Artificial Intelligence Laboratory, Massahusetts instute
of Technology, Cambridge, MA, October 2006. .pdf
Matthew Lepinski, David Liben-Nowell, Seth Gilbert, and April Rasala
Lehman. Playing Games in Many Possible Worlds. Proceedings
of the Seventh ACM Conference on Electronic Commerce, June, 2006.
.ps
Sayan Mitra and Nancy Lynch. Approximate simulations for
task-structured probabilistic I/O automata.
LICS workshop on Probabilistic Automata and Logics
(PAul06), Seattle, WA, August 2006. .pdf
Sayan Mitra, Daniel Liberzon, and Nancy Lynch. Verifying average
dwell time by solving optimization problems. In Ashish Tiwari and
Joao P. Hespanha, editors, Hybrid Systems: Computation and
Control,9th International Workshop (HSCC 06) Santa Barbara, CA, March 2006, volume 3927
of Lecture Notes in Computer Science, pages 476-490, 2006. Springer. .pdf
Calvin Newport. Consensus and Collision Detectors in Wireless
Ad Hoc Networks. Masters Thesis, MIT Department of Electrical
Engineering and Computer Science, Cambridge, MA, June 2006. .ps
Shinya Umeno and Nancy Lynch.
Proving safety properties of an aircraft landing protocol
using I/O Automata and the PVS theorem prover: a case study.
In Jayadev Misra, Tobias Nipkow, Emil Sekerinski, editors, FM 2006: Formal Methods, 14th International Symposium of Formal Methods, Hamilton, Ontario Canada, August, 2006, volume 4085 of
Lecture Notes in Computer Science, pages 64-80, 2006. Springer. .pdf
Shinya Umeno. Proving safety properties of an aircraft landing
protocol using timed anduntimed I/O automata: a case study.
Masters Thesis, Department of Electrical Engineering and Computer
Science, Massachusetts Institute of Technology, Cambridge, MA, October
2006. .pdf
2005
Paul Attie and Hana Chockler.
Efficiently Verifiable Conditions for Deadlock-freedom of
Large Concurrent Programs. Proceedings of the Sixth
International Conference on Verification, Model Checking and Abstract
Interpretation, Paris, France, January 2005. .pdf
Paul Attie, Rachid Guerraoui, Petr Kouznetsov, Nancy Lynch, and Sergio
Rajsbaum. The Impossibility of Boosting Distributed Service
Resilience. 25th IEEE International Conference on
Distributed Computing Systems (ICDCS 2005), Columbus, OH, pages
39-48, June 6-10, 2005. .pdf
Paul Attie, Rachid Guerraoui, Petr Kouznetsov, Nancy Lynch, and Sergio
Rajsbaum. Impossibility of boosting distributed service resilience.
Technical Report MIT-LCS-TR-982, Computer Science and Artificial
Intelligence Laboratory, Massachusetts Institute of Technology,
Cambridge, MA, February 2005. .ps
Michael Bender, Jeremy Fineman, Seth Gilbert, and Bradley Kuszmaul.
Concurrent Cache-Oblivious B-Trees. 17th ACM Symposium on Parallelism in Algorithms
and Architectures (SPAA 2005), Las Vegas, Nevada, July 2005. .pdf
Ran Canetti, Ling Cheung, Dilsun Kaynar, Moses Liskov,
Nancy Lynch, Olivier Pereira, and Roberto Segala.
Using Probabilistic I/O Automata to Analyze an Oblivious Transfer
Protocol.ePrint Report 2005/452, Cryptology ePrint Archive, 2005.
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 and Dahlia Malkhi.
Active Disk Paxos with infinitely many processes.
Distributed Computing, volume 18, number 1, pages 73-84,
July 2005. .ps
Gregory Chockler, Nancy Lynch, Sayan Mitra, and Joshua
Tauber. Proving Atomicity: An Assertional Approach In Pierre Fraigniaud, editor, Distributed Computing, 19th International Conference (DISC 2006), Cracow, Poland, September 2005, volume 3724 of Lecture Notes in Computer Science, pages 152-168, 2005. Springer.
.pdf
G. Chockler, M. Demirbas, S. Gilbert, and C. Newport. A Middleware Framework for Robust Applications in Wireless Ad Hoc
Networks. Allerton Conference 2005: Forty-Third Annual Allerton Conference on
Communication, Control, and Computing, September 2005. .pdf
Gregory Chockler, Murat Demirbas, Seth Gilbert, Nancy Lynch, Calvin
Newport, and Tina Nolte. Reconciling the Theory and Practice of (Un)Reliable Wireless Broadcast.
Proceedings of the 4th International
Workshop on Assurance in Distributed Systems and Networks (ADSN 2005),
Columbus, Ohio, pages 42-48, June 2005. .pdf
Gregory Chockler, Murat Demirbas, Seth Gilbert, Calvin Newport, and Tina
Nolte. Consensus and Collision Detectors in Wireless Ad Hoc
Networks. Twenty-Fourth Annual ACM
SIGACT-SIGOPS Symposium on Principles of Distributed Computing
(PODC 2005), Las Vegas, Nevada, pages 197-206, July 2005. .pdf
Gregory Chockler, Seth Gilbert, Vincent Gramoli, Peter Musial, and
Alexander Shvartsman. Reconfigurable Distributed Storage for
Dynamic Networks. In James H. Anderson, Giuseppe Prencipe, Roger
Watenhofer, editors, Principles of Distributed systems: 9th
International Conference on Principles of Distributed Systems (OPODIS
2005), Pisa, Italy, December 2005, volume 3974 of Lecture Notes in Computer Science, pages 351-365, 2006. Springer. .pdf
Gregory Chockler, Nancy Lynch, Sayan Mitra, and Joshua
Tauber. Proving Atomicity: An Assertional Approach. Technical
Report MIT-CSAIL-TR-2005-048 (and MIT-LCS-TR-995), MIT CSAIL, Cambridge, MA, July 2005. .pdf
Shlomi Dolev, Limor Lahiani, Nancy Lynch, and Tina Nolte.
Self-Stabilizing Mobile Node Location Management and Message Routing.
In Ted Herman, Sebastien Tixeuil, editors, Self-Stabilizing Systems: Seventh International Symposium on Self
Stabilizing Systems (SSS 2005), Barcelona, Spain, October 26-27,
2005, volume 3764 of Lecture Notes in Computer Science, pages 96-112, 2005. Springer. Also, Technical Report MIT-LCS-TR-999, MIT Computer Science and Artificial Intelligence Laboratory, Cambridge, MA, August 2005. .pdf
Shlomi Dolev, Seth Gilbert, Limor Lahiani, Nancy Lynch, and Tina Nolte.
Timed Virtual Stationary Automata for Mobile Networks. In James H. Anderson, Giuseppe Prencipe, Roger Watenhofer, editors,
Principles of Distributed systems: 9th International Conference on
Principles of Distributed Systems (OPODIS 2005), volume 3974 of Lecture Notes in Computer Science, pages 130-145, 2006, Springer. Also, Technical Report MIT-LCS-TR-979a, MIT CSAIL, Cambridge, MA 02139, August 2005.
.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, 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, Elad Schiller, Alex A. Shvartsman, and
Jennifer Welch. Autonomous Virtual Mobile Nodes.
DIAL-M-POMC 2005: Third Annual ACM/SIGMOBILE International Workshop on
Foundation of Mobile Computing, Cologne, Germany, September 2,
2005. .pdf
Shlomi Dolev, Seth Gilbert, Elad Schiller, Alex Shvartsman, Jennifer
Welch. Brief Announcement: Autonomous Virtual Mobile Nodes.
17th ACM Symposium on Parallelism in Algorithms
and Architectures (SPAA 2005), Las Vegas, Nevada, July 2005. .ps
Shlomi Dolev, Limor Lahiani, Seth Gilbert, Nancy Lynch, Tina Nolte.
Brief Announcement: Virtual Stationary Automata for Mobile Networks.
Proceedings of the 24th Annual ACM Symposium on
Principles of Distributed Computing (PODC'05), Las Vegas, Nevada,
July, 2005. .pdf
Shlomi Dolev, Seth Gilbert, Limor Lahiani, Nancy Lynch, and Tina
Nolte. Timed Virtual Stationary Automata for Mobile Networks.
Techncial Report MIT-LCS-TR-979a, MIT CSAIL, Cambridge, MA, August
2005. .ps
Shlomi Dolev, Seth Gilbert, Elad Schiller, Alex Shvartsman, and
Jennifer Welch. Autonomous Virtual Mobile Nodes. Technical Report
MIT-LCS-TR-992, MIT CSAIL, Cambridge, MA, June 2005. .pdf
Shlomi Dolev, Seth Gilbert, Limor Lahiani, Nancy Lynch,
and Tina Nolte.
Virtual Stationary Automata for Mobile Networks (Extended
Abstract) Technical Report MIT-LCS-TR-979, MIT CSAIL, Cambridge,
MA 02139, January 2005. .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. TIOA User Guide and Reference Manual. September 15,
2005. .pdf
Stephen Garland, Dilsun Kaynar, Nancy Lynch, Joshua Tauber, and
Mandana Vaziri. TIOA Tutorial. May 22, 2005. .pdf
Chryssis Georgiou, Nancy Lynch, Panayiotis Mavrommatis and Joshua
Tauber. Automated Implementation of Complex Distributed Algorithms
Specified in the IOA Language. Proceedings of the ISCA 18th International Conference on Parallel and Distributed Computing Systems, Las Vegas, Nevada, 128-134, September, 2005.
Dilsun Kaynar, Nancy Lynch, Sayan Mitra, and Stephen Garland.
The TIOA Language. Version 0.21, May 22, 2005. .pdf
Ben Leong, Sayan Mitra, and Barbara Liskov. Path vector face routing:
Geographic routing with local face information.
Proceedings of 13th IEEE International Conference
on Network Protocols (ICNP'05 ), November
6-9, 2005, Boston, Massachusetts, USA. .pdf
Hongping Lim, Dilsun Kaynar, Nancy Lynch, and Sayan Mitra.
Translating timed I/O automata specifications for theorem proving
in PVS. In Paul Pettersson, Wang Yi, editors, Formal Modeling
and Analysis of Timed Systems, Third International Conference (FORMATS
2005), Uppsala, Sweden, September 26-28, volume 3829 of Lecture
Notes in Computer Science, pages 17-31, 2005. Springer. .pdf
Nancy Lynch. A Three-Level
Analysis of a Simple Acceleration Maneuver, with Uncertainties. In Aurel Cornell and Dan Ionescu, editors, Real-Time
Systems: Modeling, Design, and Applications, volume 8 of AMAST
Series in Computing, World Scientific Publishing Company, 2005. Abstract
and Postscript
Nancy Lynch, Sayan Mitra, and Tina Nolte. Motion coordination
using virtual nodes. Technical Report MIT-LCS-TR-986, MIT CSAIL, Cambridge, MA,
April 2005. .pdf
Nancy Lynch, Sayan Mitra, and Tina Nolte. Motion Coordination Using
Virtual Nodes. CDC-ECC 2005: Forty-Fourth IEEE Conference on
Decision and Control and European Control Conference, Seville,
Spain, December 2005. Invited paper. .pdf
Sayan Mitra and Myla Archer. PVS Strategies for proving abstraction
properties automata.
In Electronic Notes in Theoretical Computer Science, volume 125(2),
2005, pages 45-65. .ps
Sayan Mitra and Daniel Liberzon.
Stability of Hybrid Automata with Average Dwell Time: An Invariant
Approach. Proceedings of the 43rd Conference on
Decision and Control (CDC 2004), Paradise Island, Bahamas, December, 2004.
.pdf
Athicha Muthitacharoen, Seth Gilbert, and Robert Morris.
Etna: A Fault-tolerant Algorithm for Atomic Mutable DHT Data.
Technical Report MIT-CSAIL-TR-2005-044, MIT CSAIL, Cambridge, MA, June
2005. .pdf
Joshua A. Tauber. Verifiable Compilation of I/O Automata
without Global Synchronization. Ph.D Thesis,
Department of Electrical Engineering and Computer Science,
Massachusetts Institute of Technology, Cambridge, MA 02139, February,
2005. .pdf
2004
Ittai Abraham, Gregory Chockler, Idit Keidar and Dahlia Malkhi.
Byzantine Disk Paxos: Optimal Resilience with Byzantine Shared
Memory. Proceedings of the 23rd Annual ACM
SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC
2004), St. John's, Newfoundland, Canada, pages 226-235, July 2004.
© ACM, (2004). This is the author's version of the work. It is posted
here by permission of ACM for your personal use. Not for
redistribution. The definitive version was published in the
Proceedings of the Twenty-Third Annual ACM SIGACT-SIGOPS Symposium on
Principles of Distributed Computing (PODC 2004). .pdf
P.C. Attie, A. Arora, and E.A. Emerson.
ACM Transactions on Programming Languages and Systems (TOPLAS),
vol. 26, no. 1, pp 125-185, January 2004.
Extended abstract appears in ACM Symposium on the Principles of
Distributed Computing (PODC) 1998. .pdf
Jacob Beal and Seth Gilbert. RamboNodes for the Metropolitan Ad
Hoc Network. Proceedings of the Workshop on Dependability in
Wireless Ad Hoc Networks and Sensor Networks, part of the
International Conference on Dependable Systems and Networks,
Florence, Italy, June-July, 2004. .ps
Also, AI Memo: AIM-2003-027.
Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, Charles E. Leiserson.
On-the-Fly Maintenance of Series-Parallel Relationships in Fork-Join
Multithreaded Programs. Sixteenth ACM
Symposium on Parallelism in Algorithms and Architectures (SPAA 2004), Barcelona,
Spain, pages 133-144, June 27-30, 2004..ps
Ling Cheung, Nancy Lynch, Roberto Segala, and Frits Vaandrager.
Switched Probabilistic I/O Automata. In Z. Liu and K. Araki,
editors, Theoretical Aspects of Computing, First International Colloquium (ICTAC2004),Guiyang, China, September 2004,
volume 3407 of Lecture Notes in Computer Science, pages
494-510, Springer-Verlag, 2005. .pdf
Ling Cheung, Nancy Lynch, Roberto Segala, and Frits Vaandrager.
Switched Probabilistic I/O Automata. Nijmegen Institute for
Computing and Information Sciences (NIII) Technical Report NIII-R0437,
Catholic University of Nijmegen, Nijmegen, The Netherlands, September 2004.
.ps
G. Chockler and D. Malkhi.
Light-Weight Leases for Storage-Centric Coordination.
Technical Report MIT-LCS-TR-934, MIT Laboratory for Computer Science,
January, 2004. Revised April 2004. .ps
Gregory Chockler, Idit Keidar and Dahlia Malkhi. Optimal Resilience Wait-Free Storage from Byzantine Components: Inherent
Costs and Solutions. FuDiCo II: S.O.S. Survivability: Obstacles and Solutions. 2nd Bertinoro
Workshop on Future Directions in Distributed Computing, 23-25 June 2004
University of Bologna Residential Center Bertinoro (Forli), Italy..pdf
Murat Demirbas, Anish Arora, Tina Nolte, and Nancy Lynch. A
Hierarchy-based Fault-local Stabilizing Algorithm for Tracking in
Sensor Networks. In Teruo Higashino,
editor, Principles of Distributed Systems: OPODIS 2004: 8th
International Conference on Principles of Distributed Systems, Grenoble, France, December 15-17, 2004,
volume 3544 of Lecture Notes in Computer Science, pages 299-315,
2005. Springer. .pdf.
Murat Demirbas, Anish Arora, Tina Nolte, and Nancy Lynch. Brief
Announcement: STALK: A Self-Stabilizing Hierarchical Tracking Service
for Sensor Networks. Proceedings of the 23rd Annual ACM SIGACT-SIGOPS
Symposium on Principles of Distributed Computing (PODC 2004),
St. John's, Newfoundland, Canada, page 378, July 25-28, 2004. .ps
Shlomi Dolev, Seth Gilbert, Nancy A. Lynch, Elad Schiller, Alex
A. Shvartsman, and Jennifer L. Welch. Virtual Mobile Nodes for
Mobile Ad Hoc Networks. In Rachid Guerraoui, editor, DISC 2004 (18th International
Symposium on Distributed Computing, Trippenhuis, Amsterdam, the
Netherlands, October, 2004), volume 3274 of Lecture Notes in
Computer Science, pages 230-244, Springer, December, 2004. .ps
Shlomi Dolev, Seth Gilbert, Nancy Lynch, Elad Schiller, Alex
Shvartsman, Jennifer Welch. Brief Announcement: Virtual Mobile
Nodes for Mobile Ad Hoc Networks. Proceedings of the 23rd Annual ACM SIGACT-SIGOPS
Symposium on Principles of Distributed Computing (PODC 2004),
St. John's, Newfoundland, Canada, page 385, July 25-28, 2004. .pdf
Also, Technical
Report MIT-LCS-TR-937, MIT CSAIL, Cambridge, MA, 2004.
Shlomi Dolev, Seth Gilbert, Nancy A. Lynch, Alex A. Shvartsman, and
Jennifer L. Welch. GeoQuorums: Implementing Atomic Memory in Ad
Hoc Networks. Technical Report MIT-LCS-TR-900a,
CSAIL, Massachusetts Institute of Technology, Cambridge, MA, 2004. .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. .pdf
Chryssis Georgiou, Peter M. Musial, and Alexander A. Shvartsman.
Long-Lived Rambo: Trading Knowledge for Communication.
Rastislav Kralovic, Ondrej Sykora (Eds.): Structural Information and
Communication Complexity, 11th International Colloquium, SIROCCO
2004, Smolenice Castle, Slowakia, June 21-23, 2004, volume 3104 of
Lecture Notes in Computer Science, pages 185-196, Springer 2004.
Chryssis Georgiou, Peter M. Musial, and Alexander A. Shvartsman.
Long-Lived Rambo: Trading Knowledge for Communication.
Technical Report MIT-LCS-TR-943, MIT CSAIL, Cambridge, MA, April
2004. .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
Stephen Garland, Nancy Lynch, Joshua Tauber, and Mandana Vaziri.
IOA User Guide and Reference Manual.
Technical Report MIT-LCS-TR-961, MIT CSAIL, July 2004.
Ch. Georgiou, A. Russell and A. Shvartsman.
The Complexity of Synchronous Iterative Do-All with Crashes.
Distributed Computing, Volume 17, No. 1, pages 47-63, 2004.
.pdf
Chryssis Georgiou, Panayiotis Mavrommatis and Joshua A.
Tauber. Implementing Asynchronous Distributed Systems Using the IOA
Toolkit. MIT CSAIL Technical Report MIT-LCS-TR-966, Cambridge,
MA, November 2004. .ps
Seth Gilbert and Gregory Malewicz. The Quorum Deployment Problem.
OPODIS 2004: 8th International Conference on
Principles of Distributed Systems, Grenoble, France, December
15-17, 2004. .ps
Also, full version in MIT CSAIL Technical Report MIT-LCS-TR-972,
October 2004. .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
Dilsun K. Kaynar, Nancy Lynch, Roberto Segala, and Frits Vaandrager.
The Theory of Timed I/O Automata. Technical Report
MIT-LCS-TR-917a, MIT Laboratory for Computer Science, Cambridge, MA,
November, 2004. .ps
Revised version Synthesis Lectures on Computer Science, Morgan Claypool Publishers, November 2005.
Dilsun K. Kaynar and Nancy A. Lynch. Decomposing Verification
of Timed I/O Automata. Formal Techniques, Modelling and
Analysis of Timed and Fault Tolerant Systems: Joint International
Conferences on Formal Modeling and Analysis of Timed Systems, FORMATS
2004, and Format Technicques in Real-Time and Fault-Tolerant Systems,
FTRTFT 2004, Grenoble, France, September 22-24, 2004, volume 3253 of
Lecture Notes in Computer Science, pages 84-101, Springer-Verlag, 2004. .ps
Also, on the Springer website.
Dilsun Kaynar, Nancy Lynch, and Sayan Mitra.
Specifying and Proving Timing Properties with TIOA Tools.
25th IEEE International Real-Time Systems
Symposium, Work in Progress Session (RTSS 2004 WIP), December 5-8
2004, Lisbon, Portugal. .ps
Carl Livadas and Idit Keidar.
Caching-Enhanced Scalable Reliable Multicast.
International Conference on Dependable Systems
and Networks (DSN), June-July 2004. .pdf
Nancy Lynch and Ion Stoica. MultiChord: A resilient namespace management
algorithm. Technical Memo MIT-LCS-TR-936, CSAIL,
Massachusetts Institute of Technology, Cambridge, MA 2004. .ps
Nancy Lynch, Roberto Segala, and Frits Vaandrager.
Compositionality for Probabilistic Automata.
Technical Report MIT-LCS-TR-907, Computer Science and Artificial Intelligence
Laboratory, Massachusetts Institute of Technology, Cambridge, MA,
November 2004. .ps
Catherine Matlon. A specification and verification of
Intermittent Global Order Broadcast. Master of Engineering in
Electrical Engineering and Computer Science, Massachusetts Institute
of Technology, Cambridge, MA, May 2004. .pdf
Sayan Mitra and Myla Archer.
Reusable PVS Proof Strategies for Proving Abstraction Properties of
I/O Automata. STRATEGIES 2004, IJCAR Workshop on Strategies in
Automated Deduction, Cork Ireland, July 2004. .pdf
Sayan Mitra and Jesse Rabek.
Energy Efficient Connected Clusters for Mobile Ad Hoc Networks.
MED-HOC-NET 2004, Third Annual Mediterranean
Ad Hoc Networking Workshop, Bodrum, Turkey, June 2004. .ps
P.M. Musial and A.A. Shvartsman. Implementing a Reconfigurable
Atomic Memory Service for Dynamic Networks. In Proceedings
of the 18'th International Parallel and Distributed Processing Symposium
(IPDPS'04) --- FTPDS WS, Santa Fe, New Mexico, pages 208-215, April, 2004. .pdf
Christine Margaret Robson. TIOA and UPPAAL.
Masters of Engineering Thesis, MIT Department of Electrical
Engineering and Computer Science, Cambridge, MA, May 2004. .ps
A. Russell and A. Shvartsman.
Distributed Computation Meets Design Theory: Local Scheduling for
Disconnected Cooperation. Current Trends in Theoretical Computer Science:
The Challenge of the New Century, vol. 1: Algorithms and Complexity,
pp. 315-336, World Scientific, 2004. .ps
Joshua A. Tauber and Nancy A. Lynch and Michael J. Tsai.
Compiling IOA without Global Synchronization.
Proceedings of the 3rd IEEE International Symposium on
Network Computing and Applications (IEEE NCA04), Cambridge, MA, pages 121-130, August
2004. .pdf
Joshua A. Tauber and Stephen J. Garland. Definition and
Expansion of Composite Automata in IOA. MIT CSAIL Technical
Report MIT-LCS-TR-959, July 2004. .pdf
Mandana Vaziri, Joshua A. Tauber, Michael J. Tsai, and Nancy Lynch.
Systematic Removal of Nondeterminism for Code Generation in I/O
Automata. MIT CSAIL Technical Report MIT-LCS-TR-960,
July 2004. .ps
2003
Paul C. Attie. On the Implementation Complexity of Specifications of
Concurrent Programs. Distributed Computing (DISC 2003: 17th International Symposium on
Distributed Computing, Sorrento, Italy, October 2003), volume 2848 of
Lecture Notes in Computer Science, pages 151-165, Springer-Verlag, 2003. .pdf
Paul C. Attie and Nancy A. Lynch. Dynamic Input/Output Automata: a
Formal Model for Dynamic Systems. Technical Report
MIT-LCS-TR-902, MIT Laboratory for Computer Science, Cambridge, MA,
02139, July 2003 and Technical Report, College of
Computer Science, Northeastern University, July 2003. Postscript
Omar Bakr. Performance Evaluation of Distributed Algorithms over the
Internet. Master of Engineering in Electrical Engineering and
Computer Science, Massachusetts Institute of Technology, Cambridge,
MA, February 2003. .pdf
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.
In Faith Fich, editor, Distributed Computing (DISC 2003: 17th International Symposium on Distributed
Computing, Sorrento, Italy, October, 2003), volume 2848 of Lecture
Notes in Computer Science, pages 306-320, Springer-Verlag, 2003. .pdf
Shlomi Dolev, Seth Gilbert, Nancy Lynch, Alex Shvartsman, and Jennifer Welch.
GeoQuorums: Implementing atomic memory in ad hoc networks.
Technical Report MIT-LCS-TR-900, MIT Laboratory for Computer Science,
Cambridge, MA, 02139, 2003. .ps
Rui Fan and Nancy Lynch. Efficient Replication of Large Data
Objects. Distributed Computing (DISC 2003: 17th International Symposium on Distributed
Computing, Sorrento, Italy, October, 2003), volume 2848 of Lecture
Notes in Computer Science, pages 75-91, Springer-Verlag, 2003. .pdf
Rui Fan. Efficient Replication of Large Data Objects. Masters
Thesis, MIT Department of Electrical Engineering and Computer Science,
Cambridge, MA, February 2003. .ps
Rui Fan and Nancy Lynch. Efficient replication of large data
objects. Proceedings of the Twenty-Second Annual ACM Symposium on
Principles of Distributed Computing, Boston, Massachusetts, page
335, July 2003. .pdf
Rui Fan and Sayan Mitra. General fault tolerant data structures.
Manuscript, 2003.
Ch. Georgiou. Cooperative Distributed Computing in the
Presence of Quantified Adversity. Ph.D. thesis, University of
Connecticut, 2003. .ps
Ch. Georgiou, A. Russell and A. Shvartsman. Work-Competitive
Scheduling for Cooperative Computing with Dynamic Groups.
The Thirty-Fifth Annual ACM Symposium on Theory of Computing
(STOC'2003), pages 251-258, San Diego, CA, June 2003. .pdf
Ch. Georgiou and A.A. Shvartsman. Cooperative Computing with
Fragmentable and Mergeable Groups. Journal of Discrete
Algorithms, volume 1 (2), pp. 211-235, 2003..ps
Seth Gilbert. RAMBO II: Rapidly Reconfigurable Atomic Memory for
Dynamic Networks. Masters Thesis, Department of Electrical Engineering and Computer
Science, Massachusetts Institute of Technology, Cambridge, MA, August
2003. .ps
Seth Gilbert, Nancy Lynch, and Alex Shvartsman.
RAMBO II: Rapidly Reconfigurable Atomic Memory for Dynamic
Networks.
Proceedings of the International Conference on Dependable Systems
and Networks (DSN), San Francisco, CA, pages 259-268, June 22nd - 25th, 2003. .pdf
Vida Uyen Ha. Verification of an Attitude Control System. Bachelor
of Science and Master of Engineering, Department of Electrical
Engineering and Computer Science, Massachusetts Institute of
Technology, Cambridge, MA, May 2003. .doc
Mohammad Taghi Hajiaghayi, Nicole Immorlica, and Vahab S. Mirrokni.
Power optimization in fault-tolerant topology control algorithms
for wireless multi-hop networks. MOBICOM 2003: Proceedings of
the Ninth Annual ACM International Conference on Mobile Computing and
Networking, pages 300-312, San Diego, CA, September 2003. .ps
Dilsun K. Kaynar, Nancy Lynch, Roberto Segala, and Frits Vaandrager.
Timed I/O Automata: A Mathematical Framework for Modeling and
Analyzing Real-Time Systems. RTSS 2003: The 24th
IEEE International Real-Time Systems Symposium, Cancun, Mexico, pages
166-177, December, 2003. IEEE Computer Society. .ps
(Full version available as Technical Report MIT/LCS/TR-917.)
Dilsun K. Kaynar, Nancy Lynch, Roberto Segala, and Frits Vaandrager.
The Theory of Timed I/O Automata. Technical Report
MIT-LCS-TR-917, MIT Laboratory for Computer Science, Cambridge, MA, 2003. .ps
Idit Keidar and Sergio Rajsbaum.
A Simple Proof of the Uniform Consensus Synchronous Lower Bound.
Information Processing Letters (IPL), 85(1):47-52, January
2003. .pdf
Roger Khazan and Nancy Lynch. An Algorithm for an
Intermittently Atomic Data Service Based on Group Communication.
Proceedings of the International Workshop on Large-Scale Group Communication,
Florence, Italy, pages 25-30, October 2003. .pdf
D. Kowalski, M. Momenzadeh, and A.A. Shvartsman.
Emulating Shared-Memory Do-All Algorithms in Asynchronous
Message-Passing Systems. In Marina Papatriantafilou and Phillippe Hunel,editors,
Principles of Distributed Systems, 7th International Conference (OPODIS 2003), La Martinique, France, December 2003, volume 3144 of Lecture Notes in Computer Science, pages 210-222, 2004. Springer.
Carolos Livadas. Formally Modeling, Analyzing, and Designing Network
Protocols---A Case Study on Retransmission-Based Reliable Multicast --Protocols. Ph.D Thesis, Department of Electrical Engineering and
Computer Science, Massachusetts Institute of Technology, Cambridge,
MA, July 2003. .ps
Nancy Lynch. Some Perspectives on PODC. Distributed
Computing, 16(1):71-74, 2003. .pdf
Nancy Lynch. Working with Mike on Distributed Computing Theory,
1978-1992.Proceedings of the Twenty-Second Annual ACM Symposium on
Principles of Distributed Computing (PODC'03), page 11, Boston, MA, July
2003.
.pdf
Nancy Lynch. Input/Output Automata: Basic, Timed, Hybrid, Probabilistic, Dynamic, ... In Roberto Amadio and Denis Lugiez, editors, CONCUR
2003 - Concurrency Theory, 14th International Conference on
Concurrency Theory, Marseille, France, September, 2003, volume
2761 of Lecture Notes in Computer Science, pages 191-192,
Springer-Verlag, 2003.
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.
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.
G. Malewicz. Distributed Scheduling for Disconnected
Cooperation. Ph.D. thesis, University of Connecticut, 2003. .pdf
Sayan Mitra, Yong Wang, Nancy Lynch, and Eric Feron.
Safety Verification of Model Helicopter Controller using Hybrid
Input/Output Automata. O. Maler, A. Pnueli, editors, Hybrid
Systems: Computation and Control (6th International Workshop,
HSCC'03, Prague, the Czech Republic April 3-5, 2003), volume 2623 of
Lecture Notes in Computer Science, pages 343-358, Springer-Verlag, 2003..pdf (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. .pdf
Sayan Mitra and Myla Archer.
Developing Strategies for Specialized Theorem Proving about Untimed, Timed, and Hybrid I/O Automata.
In STRATA 2003, Design and Application of Strategies/Tactics in
Higher Order Logics, Rome, Italy, September, 2003. .ps
M. Momenzadeh. Emulating Shared-Memory Do-All in Asynchronous
Message Passing Systems.
Masters thesis, University of Connecticut, 2003.
Toh Ne Win. Theorem-Proving Distributed Algorithms with Dynamic
Analysis. Master of Engineering in Computer Science and Engineering,
MIT Department of Electrical Engineering, Cambridge, MA, May 2003. .ps
Toh Ne Win, Michael D. Ernst, Stephen J. Garland, Dilsun K. Kaynar,
and Nancy Lynch. Using simulated execution in verifying
distributed algorithms. In L.D. Zuck, P.C. Attie, A. Cortesi,
S. Mukhopadhyay, editors, Verification, Model Checking, and
Abstract Interpretation, Proceedings of 4th International Conference,
(VMCAI 2003), New York, NY, USA, January
9-11, 2003, volume 2575 of Lecture Notes in Computer Science,
pages 283-297, Springer-Verlag, 2003. .ps
Toh Ne Win, Michael Ernst, Stephen Garland, Dilsun Kirli, and Nancy Lynch.
Using simulated execution in verifying distributed algorithms.
International Journal on Software Tools for Technology Transfer
(STTT), 6(1):67-76, July 2004.
Edward Solovey. Simulation of Composite I/O Automata.
Masters of Engineering Thesis, MIT Department of Electrical
Engineering and Computer Science, Cambridge, MA, August 2003. .ps
2002
P. C. Attie. Wait-free Byzantine Consensus.
Information Processing Letters, vol. 83, no. 4, pp. 221-227,
August 2002. .pdf
Paul Attie, Nancy Lynch, and Sergio Rajsbaum.
Boosting Fault-Tolerance in Asynchronous Message Passing Systems is
Impossible. Technical Report MIT-LCS-TR-877, MIT Laboratory for Computer
Science, Cambridge, MA, December 2002. .pdf
Mohsen Bahramgiri, Mohammad Taghi Hajiaghayi, and Vahab S. Mirrokni.
Fault-tolerant and 3-Dimensional distributed topology control
algorithms in wireless multi-hop networks. Proceedings of the
11th IEEE International Conference on Computer Communications and
Networks (IC3N), pages 392-398, October 14-16, 2002, Miami,
Floria. .pdf
Also, MIT Technical Report MIT-LCS-TR-862, Cambridge, MA 02139, 2002.
Omar Bakr and Idit Keidar. Evaluating the Running Time of a
Communication Round over the Internet. Proceedings of the 21st ACM Symposium on Principles of Distributed Computing (PODC '02),
Monterey, CA, USA, pages 243-252, July 2002. .pdf
Ziv Bar-Joseph and Idit Keidar and Nancy Lynch.
Early-Delivery Dynamic Atomic Broadcast. In D. Malkhi,
editor, Distributed Computing (Proceedings of the
16th International Symposium on DIStributed Computing (DISC) October 2002,
Toulouse, France), volume 2508 of Lecture Notes in Computer
Science, pages 1-16, 2002. Springer-Verlag. .pdf
Ziv Bar-Joseph, Idit Keidar, and Nancy Lynch. Early-Delivery
Dynamic Atomic Broadcast. Technical Report MIT-LCS-TR-840, MIT
Laboratory for Computer Science, Cambridge, MA, April 2002. .pdf
Andrej Bogdanov, Stephen Garland, and Nancy A. Lynch.
Mechanical Translation of I/O Automaton Specifications into
First-Order Logic. In Doron Peled, Moshe Y. Vardi, editors,
Formal Techniques for Networked and Distributed Systems - FORTE 2002
(Proceedings of the 22nd IFIP WG 6.1 International Conference,
Houston, Texas, USA,
November 11-14, 2002), volume 2529 of Lecture
Notes in Computer Science, pages 364-368, Springer 2002. .pdf
Roberto De Prisco, Alan Fekete, Nancy Lynch, and Alex Shvartsman. A
Dynamic Primary Configuration Group Communication Service.
Technical Memo MIT-LCS-TR-873, MIT Laboratory for Computer Science,
Cambridge, MA, November 2002. Abstract/Paper.
Matthias Fitzi, Daniel Gottesman, Martin Hirt, Thomas Holenstein, and
Adam Smith. Detectable Byzantine Agreement Secure Against Faulty
Majorities. In Proceedings of the Twenty-First ACM Symposium on
Principles of Distributed Computing (PODC 2002), Monterey, CA, July,
2002. .pdf
Seth Gilbert and Nancy Lynch. Brewer's conjecture and the
feasibility of consistent, available, partition-tolerant web
services. SIGACT News, 33(2):58-51, June 2002. .ps
SIGACT News Archive Page
Dilsun Kirli Kaynar, Anna Chefter, Laura Dean, Stephen J. Garland,
Nancy A. Lynch, Toh Ne Win, and Antonio Ramirez-Robredo.
Simulating Nondeterministic Systems at Multiple Levels of
Abstraction. In Tools Day held in conjunction with CONCUR'02, Brno, Czech
Republic, August 2002. .pdf
Dilsun Kirli Kaynar, Anna Chefter, Laura Dean, Stephen Garland,
Nancy Lynch, Toh Ne Win, and Antonio Ramirez-Robredo. The IOA Simulator. Technical Report
MIT-LCS-TR-843, MIT Laboratory for Computer Science, Cambridge, MA,
July 2002. pdf
Idit Keidar. Challenges in Evaluating Distributed Algorithms.
FuDiCo 2002: Proceedings of the International Workshop on Future Directions in
Distributed Computing (FuDiCo 2002), June 2002, Bertinoro, Italy. pdf
I. Keidar and K. Marzullo. The Need for Realistic Failure Models in
Protocol Design. Position paper in the 4th International Survivability Workshop (ISW)
2001/2002, March 2002. .pdf
Idit Keidar, Roger Khazan, Nancy Lynch and Alex Shvartsman.
An Inheritance-Based Technique for Building Simulation Proofs
Incrementally.
ACM Transactions on Software Engineering and
Methodology (TOSEM), 11(1):63-91, January 2002. Conference
version in ICSE, 2000, pages 478-487. .pdf
Idit Keidar and Roger Khazan.
A virtually synchronous group multicast algorithm for WANs: Formal
approach. SIAM Journal on Computing,32(1):78-130, 2002. .pdf
Roger Khazan. Formal Design and Analysis of a New Virtually
Synchronous Group Communication Service for Wide Area Networks.
Ph.D
Thesis, Department of Electrical Engineering and Computer Science,
Massachusetts Institute of Technology, Cambridge, MA, May 2002.
Carolos Livadas and Nancy A. Lynch. A Formal Venture into Reliable
Multicast Territory. In Doron Peled, Moshe Y. Vardi, editors,
Formal Techniques for Networked and Distributed Systems - FORTE 2002
(Proceedings of the 22nd IFIP WG 6.1 International Conference,
Houston, Texas, USA, November 11-14, 2002), volume 2529 of Lecture
Notes in Computer Science, pages 146-161, Springer 2002. .pdf
Also, full version as Technical Report MIT-LCS-TR-868, MIT
Laboratory for Computer Science, Cambridge, MA, November 2002.
Carolos Livadas and Nancy A. Lynch. A Formal Venture into Reliable
Multicast Territory. Technical Report MIT-LCS-TR-868, MIT
Laboratory for Computer Science, Cambridge, MA, November 2002. .pdf
Carolos Livadas and Idit Keidar. The Case for Exploiting Packet Loss
Locality in Multicast Loss Recovery. Technical Report MIT/LCS/TR-867,
MIT Laboratory for Computer Science, Cambridge, MA, Oct. 2002. .pdf
Nancy Lynch, Dahlia Malkhi, David Ratajczak. Atomic Data Access in
Content Addressable Networks. In
P. Druschel, F. Kaashoek, and A. Rowstron, editors, Peer-to-Peer
Systems (First International Workshop on
Peer-to-Peer Computing, Cambridge, MA, March 2002), volume 2429 of
Lecture Notes in Computer Science, pages 295-305, Springer, 2002.
.pdf
Nancy Lynch and Alex Shvartsman. Communication and Data Sharing
for Dynamic Distributed Systems. In A. Schiper,
A.A. Shvartsman, H. Weatherspoon, B.Y. Zhao, editors, Future
Directions in Distributed Computing: Research and Position Papers (FuDiCo 2002: Proceedings of
the International Workshop on Future Directions in Distributed
Computing, Bertinoro,Italy, June 2002), volume 2584 of Lecture Notes
in Computer Science, pages 62-67, Springer-Verlag, 2003.
.pdf
Nancy Lynch and Alex Shvartsman. RAMBO: A Reconfigurable
Atomic Memory Service for Dynamic Networks. In D. Malkhi,
editor, Distributed Computing (Proceedings of the
16th International Symposium on DIStributed Computing (DISC) October 2002,
Toulouse, France), volume 2508 of Lecture Notes in Computer
Science, pages 173-190, 2002. Springer-Verlag. .pdf Also,
Technical Report MIT
Laboratory for Computer Science, Technical Report MIT-LCS-TR-856,
Cambridge, MA, 2002. .ps
Nancy Lynch and Alex Shvartsman. RAMBO: A Reconfigurable Atomic
Memory Service for Dynamic Networks. Technical Report MIT-LCS-TR-856,
MIT Laboratory for Computer Science, Cambridge, MA, 2002. .ps
Michael J. Tsai. Code Generation for the IOA Language. Master of Engineering Thesis, Massachusetts Institute of
Technology, Cambridge, MA, June 2002. Abstract
and .pdf
Yoshinobu Kawabe and Ken Mano. Verifying the Nepi network programming
system with IOA-Toolkit. Proceedings of the 9th Workshop on
Foundations of Software Engineering (FOSE '02), 2002. In Japanese.
2001
P.C. Attie and E.A. Emerson. Synthesis of concurrent systems for
an atomic read/write model of computation.
ACM Transactions on Programming Languages and Systems,
vol. 23, no. 2, pp. 187-242, March 2001. .pdf.
Extended abstract appears in ACM Symposium on the Principles of Distributed Computing
(PODC) 1996.
Paul C. Attie and Nancy A. Lynch. Dynamic Input/Output Automata: a
Formal Model for Dynamic Systems.
In K. G. Larsen and M. Nielsen, editors, CONCUR 2001 - Concurrency
Theory: 12th International Conference on Concurrency Theory,
Aaalborg, Denmark, August 20-25, 2001, Proceedings, volume 2154 of
Lecture Notes in Computer Science, pages 137-151, 2001.
Springer-Verlag. Postscript Also, in {\em Proceedings of the Twentieth ACM Annual Symposium on Principles of Distributed Computing}, Newport, RI, pages 314-316, 2001.
Andrej Bogdanov. Formal verification of simulations between
I/O automata. Master of Engineering thesis, Department of Electrical Engineering
and Computer Science, Massachusetts Institute of Technology,
Cambridge, MA, September 2001. pdf.
Elizabeth Borowsky, Eli Gafni, Nancy Lynch, and Sergio Rajsbaum.
The BG Distributed Simulation Algorithm.
Distributed Computing, 14(3):127-146, 2001. pdf.
Bogdan S. Chlebus, Roberto De Prisco, and Alex A. Shvartsman.
Performing tasks on synchronous restartable message-passing
processors. Distributed Computing, 14:49-64, 2001. .pdf
Gregory V. Chockler, Idit Keidar, and Roman Vitenberg. Group
Communication Specifications: A Comprehensive Study. ACM
Computing Surveys, 33(4):1-43, December 2001. .pdf
Laura G. Dean. Improved Simulation of Input/Output Automata. Master of Engineering Thesis,
Massachusetts Institute of Technology, Cambridge, MA, September 2001.
Alan Fekete and Idit Keidar:
A Framework for Highly Available Services Based on Group
Communication. IEEE International Workshop on Applied
Reliable Group Communication (WARGC), pages 57-62, held in conjunction with ICDCS 2001, April 2001. Postscript
Alan Fekete, Nancy Lynch, and Alex Shvartsman. Specifying and Using a Partitionable Group Communication
Service. ACM Transactions on Computer Systems, 19(2):171-216, May 2001. .pdf
Stephen J. Garland and Nancy A. Lynch and Mandana Vaziri. IOA: A
Language for Specifying, Programming and Validating Distributed Systems.
User and Reference Manual. Laboratory for Computer Science, Massachusetts
Institute of Technology, Cambridge, MA 02139, October 2001. Postscript.
Kyle Ingols and Idit Keidar:
Availability Study of Dynamic Voting Algorithms.
21st IEEE International Conference on Distributed Computing
Systems (ICDCS), pages 247-254, April 2001.
Previous version: MIT Technical Memorandum MIT-LCS-TM-611,
November 2000. Postscript
Idit Keidar and Sergio Rajsbaum.
On the Cost of Fault-Tolerant Consensus When There Are No Faults -
A Tutorial.
MIT Technical Report MIT-LCS-TR-821, May 24 2001.
Preliminary version in SIGACT News 32(2), Distributed Computing
column, pages 45-63, June 2001 (published in May 15th).
Abstract/Paper. SIGACT News Archive Page
Idit Keidar. Group Communication. Manuscript, 2001.
pdf
Carolos
Livadas, Idit
Keidar, and Nancy A. Lynch. Designing a Caching-Based Reliable
Multicast Protocol. Proceedings of the International Conference on
Dependable Systems and Networks (DSN'01), Fast Abstracts Supplement,
pages B44-B45, Gothenburg, Sweden, July 2001. [Abstract/Postscript]
Victor Luchangco. Memory Consistency Models for High Performance
Distributed Computing. Ph.D Thesis, Massachusetts Institute of
Technology, Cambridge, Massachusetts, September 2001.
Nancy Lynch, Roberto Segala, and Frits Vaandrager. Hybrid I/O
Automata Revisited. In Maria Domenica Di Benedetto and Alberto
Sangiovanni-Vincentelli, editors Hybrid Systems: Computation and
Control. Fourth International Workshop (HSCC'01, Rome, Italy, March
2001, volume 2034 of Lecture Notes in Computer Science,
pages 403-417, 2001. Springer-Verlag. .pdf.
Long version is Technical Report MIT/LCS/TR-827, MIT Laboratory for
Computer Science, July 2001.
Michael J. Tsai. Abstract Data Types (ADTs) for IOA Code Generation.
Manuscript, September 2001.
2000
Tadashi Araragi, Paul Attie, Idit Keidar, Kiyoshi Kogure,
Victor Luchangco, Nancy Lynch, and Ken Mano.
On Formal Modeling of Agent Computations.
In J.L. Rash, C.A. Rouff, W. Truszkowski, D. Gordon,
M.G. Hinchey, editors, Formal Approaches to Agent-Based Systems
(First International Workshop on Formal Approaches to Agent-Based
System (FAABS 2000), Greenbelt, Maryland, April, 2000), volume 1871
of Lecture Notes in Artificial Intelligence, pages 48-62,
Springer-Verlag, 2000.
pdf,
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
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
Buckhard Englert and Alexander A. Shvartsman. Graceful Quorum
Reconfiguration in a Robust Emulation of Shared Memory.
International Conference on Distributed Computer Systems (ICDCS'2000),
pages 454-463, 2000. PDF
Stephen J. Garland and Nancy A. Lynch. Using
I/O Automata for Developing Distributed Systems. In Gary T. Leavens and Murali Sitaraman, editors,
Foundations of Component-Based Systems, pages 285-312, Cambridge
University Press, 2000. Abstract/Postscript
Chryssis Georgiou and Alex A. Shvartsman. Cooperative Computing
with Fragmentable and Mergeable Groups. Technical Report
MIT/LCS/TR-802, Laboratory for Computer
Science, Massachusetts Institute of Technology, 2000. Postscript
Kyle W. Ingols. Availability Study of Dynamic Voting Algorithms.
M.Eng. thesis, MIT Department of Electrical Engineering and Computer
Science, Cambridge, MA, May 5, 2000. .pdf
Idit Keidar and Danny Dolev. Totally Ordered Broadcast in the Face of
Network Partitions. Exploiting Group Communication for Replication in
Partitionable Networks. Chapter 3 of Dependable Network Computing,
D. Avresky Editor, pages 51-75, Kluwer Academic Publications, January 2000. Postscript
Idit Keidar and Roger Khazan. A Client-Server Approach to Virtually
Synchronous Group Multicast: Specifications and Algorithms.
IEEE 20th International Conference on
Distributed Computing Systems (ICDCS), pages 344-355, Taipei,
Taiwan, April 2000.
Abstract
(technical report version).
Idit Keidar, Roger Khazan, Nancy Lynch and Alex Shvartsman.
An Inheritance-Based Technique for Building Simulation Proofs
Incrementally.
ACM Transactions on Software Engineering and
Methodology (TOSEM), 11(1):1-29, January 2002. Conference
version in ICSE, 2000, pages 478-487. Postscript
I. Keidar, J. Sussman, K. Marzullo, and D. Dolev. A
Client-Server Oriented Algorithm for Virtually Synchronous Group Membership in WANs.
IEEE 20th International Conference on
Distributed Computing Systems (ICDCS), pages 356-365, Taipei,
Taiwan, April 2000.
Abstract
(technical report version).
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.
Gregory Malewicz, Alexander Russell, and Alex Shvartsman.
Distributed Cooperation in the Absence of Communication.
Technical Report MIT-LCS-TR-804, Laboratory for Computer Science,
Massachusetts Institute of Technology, Cambridge, MA. Postscript
Anna Pogosyants, Roberto Segala, and Nancy Lynch.
Verification of the randomized consensus algorithm of Aspnes and
Herlihy: a case study. Distributed Computing,
13(3):155-186, 2000. .pdf
J. Antonio Ramirez-Robredo. Paired Simulation of I/O Automata.
Masters thesis. Department of Electrical Engineering and Computer
Science, Massachusetts Institute of Technology, Cambridge, MA, September,
2000.
Igor Tarashchanskiy. Virtual Synchrony Semantics: Client-Server
Implementation. Masters thesis. MIT Department of Electrical
Engineering and Computer Science, Cambridge, MA, September, 2000. .pdf
1999
Tal Anker, Danny Dolev and Idit Keidar. Fault Tolerant Video-on-Demand
Services. In the 19th International Conference on Distributed Computing
Systems (ICDCS), pages 244-252. June 1999. Postscript
Oleg Cheiner and Alex Shvartsman. Implementing an eventually-serializable
data service as a distributed system building block. In M. Mavronicolas,
M. Merritt, and N. Shavit, editors, Networks in Distributed Computing,
volume 45 of DIMACS Series in Discrete Mathematics and Theoretical Computer
Science, pages 43--72. American Mathematical Society, 1999.
.ps
Roberto DePrisco. On Building Blocks for Distributed Systems.
Ph.D thesis, Department of Electrical Engineering and Computer Science,
Massachusetts Institute of Technology, Cambridge, MA 02139, December
1999. .pdf
Roberto De Prisco, Alan Fekete, Nancy Lynch, and Alex Shvartsman. A
Dynamic Primary Configuration Group Communication Service. In Prasad
Jayanti, editor, Distributed Computing, Proceedings of DISC'99 - 13th International
Symposium on Distributed Computing, Bratislava, Slovak Republic, September
1999, volume 1693 of Lecture Notes in Computer Science, pages 64-78, 1999. Springer-Verlag-Heidelberg. Abstract/Paper.
Shlomi Dolev and Roberto Segala and Alex Shvartsman. Dynamic Load
Balancing with Group Communication 6th International Colloquium
on Structural Information and Communication Complexity
(SIROCCO'99). .pdf.
Alan Fekete, Nancy Lynch, and Alex Shvartsman. Specifying and Using a Partitionable Group Communication
Service. Technical Memo MIT/LCS/TM-570b, MIT Laboratory for Computer Science, Cambridge, MA, June 1999. .pdf
Alan Fekete, David Gupta, Victor Luchangco, Nancy Lynch, and Alex
Shvartsman. Eventually-Serializable Data Services. Theoretical
Computer Science, 220(1):113--156, June 1999. Special Issue on Distributed
Algorithms. pdf
Jason Hickey, Nancy Lynch,
Robbert van Renesse. Specifications and Proofs for Ensemble Layers.
Fifth International Conference on Tools and Algorithms for the Construction
and Analysis of Systems (TACAS '99), Amsterdam, the Netherlands, March
1999. Springer-Verlag. .pdf
Henrik Ejersbo Jensen. Abstraction-Based Verification of Distributed
Systems. Ph.D thesis, Department of Computer Science, Institute
for Electronic Systems, Aalborg University, Aalborg, Denmark, June 1999.
R-99-5005. .pdf
Idit Keidar, Jeremy Sussman, Keith Marzullo and Danny Dolev.
A Client-Server Oriented Algorithm for Virtually
Synchronous Group Membership in WANs.
MIT Technical Memorandum MIT-LCS-TM-593, June 1999. .pdf
Also: University of California, San Diego, Technical Report CS99-623.
Idit Keidar and Roger Khazan. A Client-Server Approach to
Virtually Synchronous Group Multicast: Specifications, Algorithms,
and Proofs. MIT Technical Report MIT-LCS-TR-794, November 1999. .pdf
Carolos Livadas,
John Lygeros, and Nancy A. Lynch.
High-Level Modeling and Analysis of TCAS. Proceedings
of the 20th IEEE Real-Time Systems Symposium, pages 115-125, Phoenix, Arizona, December,
1999. 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 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).
Nancy Lynch, Nir Shavit, Alex Shvartsman, and Dan Touitou. Timing
conditions for linearizability in uniform counting networks. Theoretical
Computer Science, 220(1):67--91, June 1999. Special Issue on Distributed
Algorithms. .pdf.
Jeremy Sussman, Idit Keidar and Keith Marzullo. Optimistic Virtual
Synchrony. MIT Technical Report MIT-LCS-TR-792, November 1999.
.pdf
Roman Vitenberg, Idit Keidar, Gregory V. Chockler and Danny Dolev. Group
Communication Specifications: A Comprehensive Study. MIT Technical
Report MIT-LCS-TR-790, September 1999. .pdf
Daniel Yates, Nancy Lynch, Victor Luchangco, and Margo Seltzer. I/O
Automaton Model of Operating System Primitives Bachelors Thesis, Harvard
University, May 1999. .pdf
1998
Soma Chaudhuri, Maurice
Herlihy, Nancy A. Lynch,
and Mark R. Tuttle. Tight bounds for k-set agreement Technical
Report 98/4, Digital Equipment Corporation, Cambridge Research Lab, Cambridge,
MA 02139, May, 1998..ps
Anna E. Chefter.
A Simulator for the IOA Language Master of Engineering and Bachelor
of Science in Computer Science and Engineering .ps
Massachusetts Institute of Technology, Cambridge, MA, May 1998.
Oleg Cheiner and Alex A. Shvartsman. Implementation of an eventually
serializable data service. In Proceedings of the 17th Annual ACM
Symposium on the Principles of Distributed Computing, Puerta Vallarta,
Mexico, June 1998. (Short paper). .ps
Roberto De Prisco, Alan Fekete, Nancy Lynch, and Alex Shvartsman Dynamic View-Oriented Group Communication Service. In Proceedings
of the 17th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed
Computing (PODC'98), Puerto Vallarta, June-July, 1998. Abstract/Paper
Ekaterina Dolginova. Safety verification of automated car maneuvers.
Master of Engineering, Department of Electrical Engineering and Computer Science,
Massachusetts Institute of Technology, Cambridge, MA 02139, May
1998. Postscript.
Shlomi Dolev, Roberto Segala, and Alex Shvartsman. Dynamic load balancing
with group communication. Technical Memo MIT/LCS/TM-588, Laboratory
for Computer Science, Massachusetts Institute of Technology, Cambridge,
MA, 1998. .ps
Alan Fekete, Frans Kaashoek and Nancy
Lynch. Implementing Sequentially-Consistent Shared Objects Using
Group and Point-to-Point Communication . Journal
of the ACM, 45(1):35-69, January, 1998.
Matteo Frigo and Victor Luchangco. Computation-centric memory models.
In ACM Symposium on Parallel Algorithms and Architectures (SPAA'98),
pages 240--249, Puerto Vallarta, Mexico, June-July 1998. .ps
Stephen J. Garland
and Nancy A. Lynch. The
IOA Language and Toolset: Support for Designing, Analyzing, and Building
Distributed Systems. Technical
Report MIT/LCS/TR-762, Laboratory for Computer Science, Massachusetts
Institute of Technology, Cambridge, MA, August 1998 (original version:
September 25, 1997).
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. Postscript
Roger Khazan. Group Communication as a Base for a Load-Balancing
Replicated Data Service. Masters thesis, Department of Electrical
Engineering and Computer Science, Massachusetts Institute of Technology,
Cambridge, MA 02139, May 1998. (Compressed
Postscript
1.35M)
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
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
Roberto Segala. Hybrid I/O automata for the compositional analysis
of hybrid systems. In Book of Abstracts of the conference of Mathematical
Theory for Networks and Systems (MTNS), Padova, Italy, July 1998. An extended
version was submitted for publication in the conference proceedings.
Nir Shavit and Asaph Zemach. Combining funnels: A new twist on an
old tale. In Proceedings of the 17th Annual ACM SIGACT-SIGOPS Symposium
on Principles of Distributed Computing, pages 61--70, Puerto Vallarta,
Mexico, June-July 1998. .pdf
N. Shavit, E. Upfal, and A. Zemach. A steady state analysis of diffracting
trees. Theory of Computing Systems (formerly Mathematical Systems
Theory), 31(4):403--423, July/August 1998. Special issue: ACM Symposium
on Parallel Algorithms and Architectures. .ps
Mark Smith. Reliable message delivery and conditionally-fast transactions
are not possible without accurate clocks. In Proceedings of the
17th Annual ACM Symposium on the Principles of Distributed Computing, pages
163--171, Puerto Vallarta, Mexico, June 1998. .pdf
Mandana Vaziri and Gerard Holzmann. Automatic generation of invariants
in spin. In 4th International Workshop on SPIN, pages 129--139,
Paris, France, November 1998. ps
Mandana Vaziri. Translating IOA to Promela, September 1998. Manuscript.
Mandana Vaziri, Nancy Lynch, and Jeannette Wing. Proving correctness of a controller
algorithm for the RAID level 5 system. Digest of papers from
the Twenty-Eighth Annual International Symposium on Fault-Tolerant
Computing, pages 16-25, Munich, Germany, June 1998. pdf
1997
Y. Afek, B. Awerbuch, E. Gafni, Y. Mansour, A. Rosen, and N. Shavit.
Slide: the key to polynomial end-to-end communication. Journal
of Algorithms, 22:158--186, 1997.
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)
Oleg Cheiner. Implementation
and Evaluation of an Eventually-Serializable Data Service. Master
of Engineering Thesis, Department of Electrical Engineering and Computer
Science, Massachusetts Institute of Technology, September 1997.
Bogdan Chlebus, Roberto
De Prisco, and Alex Shvartsman.
Performing Tasks on Restartable Message-Passing Processors. In
Marios Mavronicolas and Philippas Tsigas, editors, Proceedings of 11th
International Workshop on Distributed Algorithms (WDAG'97, Saarbrucken,
Germany, September 1997), volume 1320 of Lecture Notes in Computer Science,
pages 96-110. Springer-Verlag 1997. (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.
Giovanni Della Libera and Nir Shavit. Reactive diffracting trees. In
Proceedings of the 9th Annual ACM Symposium on Parallel Algorithms and
Architectures (SPAA), Newport, Rhode Island, June 1997.
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)
Danny Dolev and Nir Shavit. Bounded concurrent time stamping. SIAM
Journal on Computing, 26(2):418--455, April 1997.
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)
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.
Datta N. Godbole and John Lygeros. Safety and throughput evaluation
of automated highway systems. In 1997 American Control Conference, June
1997.
Gunnar Hoest and Nir
Shavit Towards a Topological Characterization of Asynchronous Complexity
Proceedings of the Sixteenth Annual ACM Symposium on Principles of Distributed
Computing, pages 199-208, Santa Barbara, CA, August 1997.
(Abstract/Postscript)
Gunnar Hoest. Towards a topological characterization of complexity in
asynchronous, distributed systems. Master's thesis, Department of Electrical
Engineering and Computer Science, Massachusetts Institute of Technology,
Cambridge, MA 02139, September 1997. .ps
Paris Christos Kanellakis, Alex
Allister Shvartsman. Fault-Tolerant Parallel Computation. Kluwer
Academic Publishers, Boston, MA, 1997. (Abstract/Information)
Carolos Livadas, Formal
Verification of Safety-Critical Hybrid Systems, Master of Engineering
Thesis, Department of Electrical Engineering and Computer Science, Massachusetts
Institute of Technology, September 1997. (Abstract/Postscript)
Also, Technical Report MIT/LCS/TR-730, Laboratory for Computer Science,
Massachusetts Institute of Technology, September 1997.
Victor Luchangco.
Precedence-Based Memory Models. In Marios Mavronicolas and Philippas
Tsigas, editors, Proceedings of 11th International Workshop on Distributed
Algorithms (WDAG'97, Saarbrucken, Germany, September 1997), volume 1320
of Lecture Notes in Computer Science. Springer-Verlag 1997. (Abstract/Postscript)
John Lygeros, Claire Tomlin, and Shankar Sastry. Multi objective
hybrid controller synthesis. In International Workshop on Hybrid
and Real-Time Systems (HART'97), Grenoble, France, March 1997.
John Lygeros, Claire Tomlin, and Shankar Sastry. Multi-objective
hybrid controller synthesis. In 36th IEEE Conference on Decision
and Control, San Diego, California, December 1997.
John Lygeros
and Nancy Lynch. On the
Formal Verification of the TCAS Conflict Resolution Algorithms. Proceedings
of the 36th IEEE Conference on Decision and Control, San Diego, CA, December
1997. (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.
George Pappas, Claire Tomlin, John Lygeros, Datta Godbole, and Shankar
Sastry. A next generation architecture for air traffic management systems.
In 36th IEEE Conference on Decision and Control, San Diego, CA, December
1997. Extended abstract.
Anna Pogosyants,
Roberto Segala, and Nancy
Lynch.Verification of the Randomized Consensus Algorithm of Aspnes
and Herlihy: a Case Study. In Marios Mavronicolas and Philippas
Tsigas, editors, Proceedings of 11th International Workshop on Distributed
Algorithms (WDAG'97, Saarbrucken, Germany, September 1997), volume 1320
of Lecture Notes in Computer Science, pages 111-125. Springer-Verlag 1997.
Also, Technical Memo MIT/LCS/TM-555, Laboratory for Computer Science, Massachusetts
Institute of Technology. (Abstract/Postscript)
Roberto Segala. Compositional verification of randomized distributed
algorithms. In COMPOS, 1997. Invited talk.
Roberto Segala. Quiescence, fairness, testing and the notion of implementation.
Information and Computation, 130(2):194--210, November 1997.
Nir Shavit, and Dan
Touitou. Elimination Trees and the Construction of Pools and Stacks.Theory
of Computing Systems (formerly Mathematical Systems Theory), volume 30,
pages 645-670, 1997. (Postscript)
N. Shavit and D. Touitou. Software transactional memory. Distributed
Computing, 10(2):99--116, February 1997.
Mark Smith. Formal Verification of TCP and T/TCP. Ph.D thesis, Department
of Electrical Engineering and Computer Science, Massachusetts Institute
of Technology, Cambridge, MA 02139, September 1997. .ps
Mandana Vaziri and Nancy Lynch. Proving correctness of a controller
algorithm for the RAID level 5 system. Technical Memo MIT/LCS/TM-576,
Laboratory for Computer Science, Massachusetts Institute of Technology,
545 Technology Square, Cambridge, MA 02139, December 1997. .ps
1996
S. Abiteboul, G. M. Kuper, H. G. Mairson, A. A. Shvartsman, and M. Y.
Vardi. In memoriam: Paris C. Kanellakis, a technical obituary. ACM Computing
Surveys, March 1996.
Hagit Attiya, Amir Herzberg, and Sergio Rajsbaum. Optimal clock synchronization
under different delay assumptions. SIAM Journal on Computing, April 1996.
Baruch Awerbuch, Boaz Patt-Shamir, and George Varghese. Self-stabilizing
end-to-end communication. Journal of High Speed Networks, 5(4):365--381,
1996.
Jonathan F. Buss, Paris C. Kanellakis, Prabhakar L. Ragde, and Alex
A. Shvartsman. Parallel Algorithms with Processor Failures and Delays.
Journal of Algorithms, Volume 10, pages 45-86, January 1996. (Abstract/Postscript)
Giovanni Della-Libera.
Dynamic Diffracting Trees. Master of Engineering Thesis, Department
of Electrical Engineering and Computer Science, Massachusetts Institute
of Technology, July 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
H. Galeana-Sanchez and S. Rajsbaum. Cycle pancyclism in tournaments
II. Graphs and Combinatorics, 12:9--16, 1996.
Rainer Gawlick, Charles Kalmanek, and K. G. Ramakrishnan. On-line routing
for permanent virtual circuits. Computer Communications, 19:235--244,
1996.
Constance Heitmeyer and Nancy Lynch. Formal verification of real-time
systems using timed automata. In Constance Heitmeyer and Dino Mandrioli,
editors, Formal Methods for Real-Time Computing, Trends in Software,
chapter 4, pages 83--106. John Wiley & Sons Ltd, April 1996.
Maurice Herlihy, Nir Shavit, and Orli Waarts. Linearizable counting
networks. Distributed Computing, (9):193--203, 1996.
Gunter Leeb and Nancy
Lynch. Proving Safety Properties of the Steam Boiler Controller.
In Jean-Raymond Abrial, Egon Boerger, and Hans Langmaack, editors, Proceedings
of Formal Methods for Industrial Applications: Specifying and Programming
the Steam Boiler Control, volume 11654 of Lecture Notes in Computer Science,
Springer-Verlag 1996. (Abstract/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)
Nir Shavit and Dan Touitou. Sofware transactional memory. Technical
Memo MIT/LCS/TM-675, Laboratory for Computer Science, Massachusetts Institute
of Technology, Cambridge, MA 02139, 1996.
Nir Shavit, and Asaph
Zemach. Diffracting Trees. ACM Transactions on Computer Systems,
14(4):385-428, November 1996. (Postscript)
Nir Shavit, Eli Upfal,
and Asaph Zemach. A Steady State Analysis of Diffracting Trees.
Proceedings of the 8th Annual ACM Symposium on Parallel Algorithms and
Architectures (SPAA'96, Padua, Italy), pages 33-41, June 1996. (Postscript)
Mark Smith. Formal verification of communication protocols. In 6th
Annual MIT Student Workshop on Computing Technology, pages 30--1, 30--2,
Salem, MA, August 1996.
Mark Smith. Formal
verification of Communication Protocols. In Reinhard Gotzhein and
Jan Bredereke, editors, Formal Description Techniques IX: Theory, Applications,
and Tools (FORTE/PSTV'96): Joint International Conference on Formal Description
Techniques for Distributed Systems and Communication Protocols, and Protocol
Specification, Testing, and Verification, Kaiserslautern, Germany, October
1996, pages 129-144. Chapman & Hall, 1996. (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
Mandana Vaziri. Proving correctness of a controller algorithm for the
RAID level 5 system. Master's thesis, Department of Electrical Engineering
and Computer Science, Massachusetts Institute of Technology, Cambridge,
MA 02139, August 1996.
H. B. Weinberg. Correctness of Vehicle Control Systems: A Case
Study. Master of Science Thesis, Department of Electrical
Engineering and Computer Science, Massachusetts Institute of
Technology, February 1996. Also, Technical Report MIT/LCS/TR-685,
Laboratory for Computer Science, Massachusetts Institute of
Technology. (Abstract/Postscript)
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
Hagit Attiya, Amotz Bar-Noy, and Danny Dolev. Sharing memory robustly
in message-passing systems. Journal of the ACM, 42(1):124--142,
January 1995.
Hagit Attiya and Sergio Rajsbaum. A combinatorial framework for wait-free
computability. Technical Report 95/3, Digital Equipment Corporation,
Cambridge Research Lab, Cambridge, MA 02139, March 1995.
Soma Chaudhuri, Maurice Herlihy, Nancy A. Lynch, and Mark R. Tuttle.
A tight lower bound for processor coordination. In Donald S. Fussell and
Miroslaw Malek, editors, Responsive Computer Systems: Steps Toward Fault-Tolerant
Real-Time Systems, chapter 1, pages 1--18. Kluwer Academic Publishers,
Boston, MA, 1995. Selected papers from the Second International Workshop
on Responsive Computer Systems Lincoln, New Hampshire, September 28-30,
1993). .ps
A. Charny, G. Leeb, and M. Clarke. Some observations on source behavior
5 of the traffic management specification. Research Report AF-TM-95-0976R1,
Digital Equipment Corporation, Littleton, Massachusetts, August 1995. Presented
at ATM Forum Traffic Management.
R. De Nicola and R. Segala. A process algebraic view of I/O automata.
Theoretical Computer Science, 138:391--423, March 1995. Also, Rapporto
Tecnico N. SI-92/05, Universita ``La Sapienza'', Rome.
Alan Fekete, Nancy Lynch, and William Weihl. Hybrid atomicity for nested
transactions. Theoretical Computer Science B (Logic, semantics and theory
of programming), 149(1):151--178, September 1995. Special issue of TCS
devoted to ICDT '92. .pdf
Alan Fekete, Frans Kaashoek and Nancy
Lynch. Implementing Sequentially-Consistent Shared Objects Using
Group and Point-to-Point Communication . In the 15th International
Conference on Distributed Computing Systems (ICDCS95), pages 439-449, Vancouver,
Canada, May/June 1995, IEEE. (Abstract/Postscript).
Also, Technical Report MIT/LCS/TM-518, Laboratory for Computer Science,
Massachusetts Institute of Technology, June 1995. (Abstract/Postscript)
H. Galeana-Sanchez and S. Rajsbaum. Cycle pancyclism in tournaments
I. Graphs and Combinatorics, 11:233--243, 1995.
Rainer Gawlick. Admission Control and Routing: Theory and Practice
Ph.D. Thesis, Department of Electrical Engineering and Computer Schence,
Laboratory for Computer Science, Massachusetts Institute of Technology,
June 1995. Also, Technical Report MIT/LCS/TR-679, Laboratory for Computer
Science, Massachusetts Institute of Technology. (Abstract/Postscript)
Rainer Gawlick, Charles Kalmanek, and K. G. Ramakrishnan. On-line routing
for permanent virtual circuits. Proceedings of IEEE INFOCOM 95: Fourteenth
Annual Joint Conference of the IEEE Computer and Communication Societies,
pages 278-288, Boston, Massachusetts, April 1995.
Maurice Herlihy and Sergio Rajsbaum. Algebraic spans. In Proceedings
of the Fourteenth Annual ACM Symposium on Principles of Distributed Computing,
pages 90--99, Ottawa, Ontario, Canada, August 1995.
M. Herlihy, B. H. Lim, and N. Shavit. Scalable concurrent counting.
ACM Transactions on Computer Systems, 13(4):343--364, 1995.
Paris Christos Kanellakis, Dimitrios Michailidis, and Alex
A. Shvartsman. Controlling Memory Access in Efficient Fault-Tolerant
Parallel Algorithms. Nordic Journal of Computing, Volume 2, pages
146-180, 1995. (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.
Using Simulation Techniques to Prove Timing Properties. Master
of Science Thesis, Department of Electrical Engineering and Computer Science,
Massachusetts Institute of Technology, June 1995. (Abstract/Postscript)
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.
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
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)
Yishay Mansour and Boaz Patt-Shamir. Many-to-one packet routing
on grids.
In Proceedings of the Twenty-Seventh Annual ACM Symposium on the Theory
of Computing, pages 258--267, Las Vegas, Nevada, May/June 1995.
Anya Pogosyants. Formal Verification of Randomized Distributed Systems.
Ph.D thesis, Department of Electrical Engineering and Computer Science,
Massachusetts Institute of Technology, Cambridge, MA 02139, 1995. (Not
completed).
Anna Pogosyants
and Roberto Segala. Formal
Verification of Timed Properties for Randomized Distributed Algorithms.
Proceedings of the Fourteenth Annual ACM Symposium on Principles of
Distributed Computing, pages 174-183, Ottawa, Ontario, Canada, August 1995.
(Abstract/Postscript)
Yaron Riany, Nir Shavit, and Dan Touitou. Towards a practical snapshot
algorithm. In Proceedings of ISTCS 1995: The Third Israel Symposium
on the Theory of Computing Systems, pages 121--129, Tel-Aviv, Israel, January
1995. IEEE.
Roberto Segala. Modeling
and Verification of Randomized Distributed Real-Time Systems. Ph.D.
Thesis, Department of Electrical Engineering and Computer Schence, Massachusetts
Institute of Technology, May 1995. Also, Technical Report MIT/LCS/TR-676,
Laboratory for Computer Science, Massachusetts Institute of Technology.
(Abstract/Postscript)
Roberto Segala. A
Compositional Trace-Based Semantics for Probabilistic Automata. In
Insup Lee and Scott A. Smolka, editors, CONCUR'95: Concurrency Theory (6th
International Conference, Philadelphia, Pennsylvania, August 1995), volume
962 of Lecture Notes in Computer Science, pages 234-248. Springer-Verlag
1995. (Abstract/Postscript)
Roberto Segala and Nancy Lynch. Probabilistic simulations for probabilistic
processes. Nordic Journal of Computing, 2(2):250--273, August 1995.
.ps
Nir Shavit and Dan Touitou. Software transactional memory. Proceedings
of the Fourteenth Annual ACM Symposium on Principles of Distributed Computing,
pages 204--213, Ottawa, Ontario, Canada, August 1995.
Nir Shavit, and Dan
Touitou. Elimination Trees and the Construction of Pools and Stacks.
Proceedings of 7th Annual ACM Symposium on Parallel Algorithms and Architectures
(SPAA'95, Santa Barbara, California), pages 54-63, July 1995.
Alex Shvartsman. Integrating distributed multimedia systems and
interactive television networks. In SPIE Conf. on Integration
of Large Scale Media Delivery Systems, volume 2615, pages 142--153,
Philadelphia, October 1995. (Abstract/Postscript)
Alex
A. Shvartsman and C. Strutt. A framework for distributed object management
and generic applications. Manuscript. (Abstract/Postscript)
July 1995.
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
Sonu Aggarwal.Time Optimal
Self-Stabilizing Spanning Tree Algorithms. Technical Report MIT/LCS/TR-632,
Laboratory for Computer Science, Massachusetts Institute of Technology,
May 1994. Masters Thesis. (Abstract/Paper).
Sudhanshu Aggarwal, Juan Garay, and Amir Herberg. Adaptive video
on demand (abstract). In Proceedings of the 13th Annual ACM Symposium
on Principles of Distributed Computing, page 402, Los Angeles, CA, August
1994.
James
Aspnes, Maurice
Herlihy, and Nir Shavit.
Counting Networks. Journal of ACM, 41(5):1020-1048,
September 1994.
(Postscript).
Hagit Attiya, Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer.
Bounds on the time to reach agreement in the presence of timing
uncertainty. Journal of the ACM, 41(1):122--152, January 1994.
.pdf
Hagit Attiya, Nancy Lynch, and Nir Shavit. Are wait-free algorithms
fast? Journal of the ACM, 41(4):725--763, July 1994. .pdf
Hagit Attiya and Nancy A. Lynch. Time bounds for real-time process control
in the presence of timing uncertainty. Information and Computation,
110(1):183--232, April 1994. .pdf
Hagit Attiya, Amir Herzberg, and Sergio Rajsbaum. Optimal clock synchronization
under different delay assumptions. Technical Memo MIT/LCS/TM-504, Laboratory
for Computer Science, Massachusetts Institute of Technology, Cambridge,
MA, April 1994.
Baruch Awerbuch,
Lenore Cowen, and Mark
Smith. Efficient Asynchronous Distributed Symmetry Breaking.
Proceedings of the 26th Annual ACM Symposium on Theory of Computing,
pages 214-223, May 1994. (Abstract/Postscript)
Baruch Awerbuch, Rainer Gawlick, Tom Leighton, and Yuval Rabani. On-line
admission control and circuit routing for high performance computation
and communication. In 35th Annual Symposium on Foundations of Computer
Science, pages 412--423, Santa Fe, New Mexico, November 1994. IEEE.
Baruch Awerbuch, Boaz Patt-Shamir, and George Varghese. Self-stabilization
by local checking and global reset. In Proceedings of the 8th International
Workshop on Distributed Algorithms (WDAG'94), volume 857 of Lecture Notes
in Computer Science, pages 326--339, Terschelling, The Netherlands, September
1994.
Baruch Awerbuch, Boaz Patt-Shamir, and George Varghese. Bounding the
unbounded. In Proceedings of the 13th Annual Joint Conference of the
IEEE Computer and Communications Societies (INFOCOM '94), pages 776--783,
Toronto, Ontario, June 1994.
Soma Chaudhuri and Mark Tuttle. Fast increment registers. In
Proceedings of the Eighth International Workshop on Distributed Algorithms,
Lecture Notes in Computer Science. Springer-Verlag, 1994.
Soma Chaudhuri and Jennifer Welch. Bounds on the costs of multivalued
register implementations. SIAM Journal on Computing, 23(2):335--354,
April 1994.
J. Garofalakis, S. Rajsbaum, P. Spirakis, and B. Tampakas. Tentative
and definite distributed computations: An optimistic approach to network
synchronization. Theoretical Computer Science, 128:63--74, 1994. Special
Issue on Dependable Parallel Computing.
Rainer Gawlick, Roberto
Segala, Joergen Soegaard-Andersen, and Nancy
Lynch. Liveness in Timed and Untimed Systems. In Serge Abiteboul
and Eli Shamir, editors, Proceedings of the 21st International Colloquim
on Automata, Languages and Programming (ICALP'94, Jerusalem, Israel, July
1994), volume 820 of Lecture Notes in Computer Science, pages 166-177,
Springer-Verlag 1994. (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)
Maurice Herlihy and Sergio Rajsbaum. Set consensus using
arbitrary objects.
In Thirteenth Annual ACM Symposium on the Principles of Distributed
Computing, pages 324--333, Los Angeles, CA, August 1994.
Maurice Herlihy
and Nir Shavit A Simple
Constructive Computatability Theorem for Wait-Free Computation. Proceedings
of the Twenty-sixth Annual ACM Symposium on Theory of Computing (STOC'94,
Montreal, Quebec, Canada), pages 243-262, May 1994.(Postscript)
Paris Christos Kanellakis, Alex
Allister Shvartsman. Fault-Tolerance and Efficiency in Massively
Parallel Algorithms.Kluwer Academic Publishers, Boston, MA, 1994.
(Abstract)
Gunter Leeb. A user interface for homenet. IEEE Transactions on Consumer
Electronics, 40(4):897 ff., November 1994.
Nancy Lynch. Simulation techniques for proving properties of real-time
systems. In J. W. de Bakker, W. P. de Roever, and G. Rozenberg, editors,
A Decade of Concurrency: Reflections and Perspectives (REX School/Symposium,
Noordwijkerhout, The Netherlands, June 1993), volume 803 of Lecture Notes
in Computer Science, pages 375--424. Springer-Verlag, 1994.
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
Boaz Patt-Shamir. A Theory of Clock Synchronization. Ph.D thesis,
Department of Electrical Engineering and Computer Science, Massachusetts
Institute of Technology, Cambridge, MA 02139, October 1994. Also, Technical
Report MIT/LCS/TR-680, Laboratory for Computer Science, Massachusetts Institute
of Technology.
Boaz Patt-Shamir and Sergio Rajsbaum. A theory of clock synchronization.
In Proceedings of the Twenty-sixth Annual ACM Symposium on Theory of
Computing, pages 810--819, Montreal, Canada, May 1994.
S. Rajsbaum and M. Sidi. On the performance of synchronized programs
in distributed networks with random processing times and transmission delays.
IEEE Transactions on Parallel and Distributed Systems, 5(9):939--950,
September 1994.
Sergio Rajsbaum. Upper and lower bounds for stochastic marked graphs.
Information Processing Letters, 49:291--295, 1994.
Alain Isaac Saias. Randomness versus Non-Determinism in Distributed
Computing. Ph.D thesis, MIT Mathematics Department, October 1994. Also,
Technical Report MIT/LCS/TR-651, Laboratory for Computer Science, Massachusetts
Institute of Technology, Cambridge, MA.
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)
Nir Shavit, and Asaph
Zemach. Diffracting Trees. Proceedings of the Sixth Annual Symposium
on Parallel Algorithms and Architectures (SPAA'94, Cape May, New Jersey),
pages 167-176, June 1994.
Ekrem Soylemez. Automatic verification of the timing properties of MMT
automata. Master's thesis, Department of Electrical Engineering and
Computer Science, Massachusetts Institute of Technology, Cambridge, MA
02139, February 1994.
1993
Yehuda Afek, Hagit Attiya, Danny Dolev, Eli Gafni, Michael Merritt,
and Nir Shavit. Atomic snapshots of shared memory. Journal of
the ACM, 40(4):873--890, September 1993.
Sudhanshu Aggarwal and Shay Kutten. Time optimal self stabilizing
spanning tree algorithms. In R.K. Shyamasundar, editor, 13th International
Conference on Foundations of Software Technology and Theoretical Computer
Science, volume 761 of Lecture Notes in Computer Science, pages 400--410,
Bombay, India., December 1993. Springer-Verlag.
James Aspnes, Maurice Herlihy, and Nir Shavit. Counting
Networks. Technical Report CRL 93/11, Digital Equipment
Corporation, Cambridge Research Lab, August 1993.
Hagit Attiya, Amir Herzberg, and Sergio Rajsbaum. Optimal clock synchronization
under different delay assumptions. In Proceedings of the Twelfth Annual
ACM Symposium on the Principles of Distributed Computing, pages 109--120,
Ithaca, NY, August 1993.
Hagit Attiya, Soma Chaudhuri, Roy Friedman, and Jennifer Welch. Shared
memory consistency conditions for non-sequential execution: Definitions
and programming strategies. In 5th Annual ACM Symposium on Parallel
Algorithms and Architectures, pages 241--250, July 1993. A detailed version
appears as Technical Report LPCR 9302, Laboratory for Parallel Computing
Research, Department of Computer Science, The Technion, 1993.
Baruch Awerbuch, Shay Kutten, Yishay Mansour, Boaz Patt-Shamir, and
George Varghese. Time optimal self-stabilizing synchronization.
In Proceedings of the Twenty-fifth Annual ACM Symposium on Theory of
Computing, pages 652--661, May 1993.
James E. Burns and Nancy A. Lynch. Bounds on shared memory for mutual
exclusion. Information and Computation, 107(2):171--184, December
1993. pdf
Soma Chaudhuri. More choices allow more faults: Set
consensus problems in totally asynchronous systems. Information
and Computation, 105(1):132--158, July 1993.
Soma Chaudhuri, Maurice Herlihy, Nancy A. Lynch, and Mark R. Tuttle.
A tight lower bound for k-set agreement. In 34th Annual
Symposium on Foundations of Computer Science, pages 206--215, Palo Alto,
California, November 1993. IEEE. .pdf
Soma Chaudhuri, Rainer Gawlick, and Nancy Lynch. Designing algorithms
for distributed systems with partially synchronized clocks. In Proceedings
of the Twelfth Annual ACM Symposium on Principles of Distributed Computing,
pages 121--132, Ithaca, New York, August 1993. .pdf
Ranjan Das and Alan Fekete. Modular reasoning about open systems:
A case study of distributed commit. In Proceedings of Seventh International
Workshop on Software Specification and Design, pages 30--39, Los Angeles,
CA, December 1993.
Harish Devarajan, Alan Fekete, Nancy Lynch, and Liuba Shrira. Correctness
proof for a network synchronizer. Technical Report MIT/LCS/TR-588,
(Harish Devarajan Masters thesis).
Harish Devarajan. A correctness proof for a network synchronizer.
Master's thesis, Department of Electrical Engineering and Computer Science,
Massachusetts Institute of Technology, Cambridge, MA 02139, May
1993. Also, Technical Report MIT/LCS/TR-588, Laboratory for Computer
Science, Massachusetts Institute of Technology, Cambridge, MA 02139,
December 1993.
Alan Fekete, Nancy Lynch, Yishay Mansour, and John Spinelli. The
impossibility of implementing reliable communication in the face of crashes.
Journal of the ACM, 40(5):1087--1107, November 1993. .pdf
Faith Fich, Maurice Herlihy, and Nir Shavit. On the complexity of
randomized synchronization. In Proceedings of the Twelth Annual
ACM Symposium on Principles of Distributed Systems, Ithaca, NY, August
1993.
Rainer Gawlick, Roberto Segala, J\orgen S\ogaard-Andersen, and Nancy
Lynch. Liveness in timed and untimed systems. Technical Report
MIT/LCS/TR-587, Laboratory for Computer Science, Massachusetts Institute
of Technology, Cambridge, MA, 02139, December 1993. (Abstract/Postscript)
Maurice P. Herlihy and Nir Shavit. The asynchronous computability
theorem for t-resilient tasks. In Proceedings of the Twenty-fifth
Annual ACM Symposium on Theory of Computing, pages 111--120, San Diego,
California, May 1993.
Shay Kutten, Rafail Ostrovsky, and Boaz Patt-Shamir. The Las-Vegas
processor identity problem (how and when to be unique). In Proceedings
of the Second Israel Symposium on Theory of Computing and Systems, June
1993.
Butler W. Lampson, Nancy A. Lynch, and Joergen F. Soegaard-Andersen.
Correctness of at-most-once message delivery protocols. In Richard
L. Tenney, Paul D. Amer, and M. Umit Uyar, editors, Formal Description
Techniques, VI (Proceedings of the IFIP TC6/WG6.1 Sixth International Conference
on Formal Description Techniques --- FORTE'93, Boston, MA, October 1993),
pages 385--400. North-Holland, 1994. (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) (Note: Later version in MIT-LCS-TM-487c, 1995.)
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
Yishay Mansour and Boaz Patt-Shamir. Greedy packet scheduling on
shortest paths. Journal of Algorithms, 14(3):449--465, March 1993.
Boaz Patt-Shamir and David Peleg. Time-space tradeoffs for set operations.
Theoretical Computer Science, 110:99--129, 1993.
Roberto Segala. Quiescence,
fairness, testing and the notion of implementation. In Eike Best,
editor, Proceedings of 4th International Conference on Concurrency Theory
(CONCUR'93, Hildesheim, Germany, August 1993), volume 715 of Lecture Notes
in Computer Science, pages 324-338. Springer-Verlag 1993. (Compressed
Postscript)
Mark A. Smith. Fast wait-free symmetry breaking in distributed
systems. Master's thesis, Department of Electrical Engineering and
Computer Science, Massachusetts Institute of Technology, Cambridge, MA
02139, May 1993.
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).
George Varghese. Self-stabilization by local checking and correction.
Technical Report MIT/LCS/TR-583, Laboratory for Computer Science, Massachusetts
Institute of Technology, Cambridge, MA 02139, October 1993.
Jennifer Welch and Nancy Lynch. A modular Drinking Philosophers algorithm.
Distributed Computing, 6(4):233--244, July 1993. .pdf
1992
Yehuda Afek, Hagit Attiya, Alan Fekete, Michael Fischer, Nancy Lynch,
Yishay Mansour, Da-Wei Wang, and Lenore Zuck. Reliable communication
over unreliable channels. Technical Memo MIT/LCS/TM-447, Laboratory
for Computer Science, Massachusetts Institute of Technology, Cambridge,
MA, 02139, October 1992. .pdf
L. Aceto, B. Bloom, and F.W. Vaandrager. Turning SOS rules into equations.
In Proceedings of the 7th Annual Symposium on Logic in Computer Science,
1992.
Hagit Attiya, Cynthia Dwork, Nancy A. Lynch, and Larry J. Stockmeyer.
Bounds on the time to reach agreement in the presence of timing uncertainty.
Technical Memo MIT/LCS/TM-435.b, Laboratory for Computer Science, Massachusetts
Institute of Technology, Cambridge, MA 02139, November 1992.
Baruch Awerbuch, Boaz Patt-Shamir, David Peleg, and Michael Saks. Adapting
to asynchronous dynamic networks with polylogarithmic overhead. In
Proceedings of the Twenty-fourth Annual ACM Symposium on Theory of Computing,
pages 557--570, Victoria, British Columbia, May 1992.
Soma Chaudhuri. More choices allow more faults: Set consensus problems
in totally asynchronous systems. Technical Memo MIT/LCS/TM-475,
Laboratory for Computer Science, Massachusetts Institute of of Technology,
November 1992.
Ranjan Das. A formalization of distributed commit in data-processing
systems. Bachelors Thesis, Department of Electrical Engineering
and Computer Science, Massachusetts Institute of Technology, Cambridge,
MA 02139, June 1992.
Alan Fekete, Nancy Lynch, and William Weihl. Hybrid atomicity for
nested transactions. In Database Theory - ICDT'92, Fourth International
Conference, volume 646 of Lecture Notes in Computer Science, pages 216--230,
Berlin, Germany, October 1992. Springer-Verlag. .pdf
Alan Fekete, Nancy Lynch, Yishay Mansour, and John Spinelli. The
impossibility of implementing reliable communication in the face of crashes.
Technical Memo MIT/LCS/TM-355.d, Massachusetts Institute of Technology,
Laboratory for Computer Science, Cambridge, MA 02139, April 1992. .pdf
Alan Fekete, Nancy Lynch, and William Weihl. Hybrid atomicity for
nested transactions. Technical Memo MIT/LCS/TM-476, Laboratory for
Computer Science, Massachusetts Institute of Technology, October 1992.
.pdf
Michael J. Fischer, Leoindas Guibas, Nancy D. Griffeth, and Nancy A.
Lynch. Optimal placement of identical resources in a tree. Information
and Computation, 91(1), January 1992. .pdf
Rainer Gawlick. Bounded concurrent time-stamping made simple.
Master's thesis, Department of Electrical Engineering and Computer Science,
Massachusetts Institute of Technology, June 1992. Also, Technical Report MIT/LCS/TR-556, Laboratory for Computer
Science, Massachusetts Institute of Technology, Cambridge, MA 02139, October
1992.
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)
S. Ponzio and R. Strong. Semisynchrony and real time. In Proceedings
of the Sixth International Workshop on Distributed Algorithms (WDAG), Lecture
Notes in Computer Science, Haifa, Israel, November 1992. Springer-Verlag.
Stephen Ponzio. Bounds on the time to detect failures using bounded-capacity
message links. In Proceedings of the Real-time Systems Symposium,
pages 236--245, Phoenix, Arizona, December 1992. IEEE.
Isaac Saias. Proving probabilistic correctness statements: the case
of Rabin's algorithm for mutual exclusion. In 11th Annual Symposium
on Principles of Distributed Systems, pages 263--274, Vancouver, B.C.,
Canada, August 1992. .pdf
Roberto Segala. A process algebraic view of I/O automata. Masters
Thesis, Department of Electrical Engineering and Computer Science, Massachusetts
Institute of Technology, May 1992. Also, Technical Memo MIT/LCS/TR-557,
Laboratory for Computer Science, Massachusetts Institute of Technology,
October 1992.
Roberto Segala. A
Process Algebraic View of I/O Automata. Technical Report MIT/LCS/TR-557,
Laboratory for Computer Science, Massachusetts Institute Technology, October
1992. (compressed
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
George Varghese. Self-Stabilization by Local Checking and Correction.
Ph.D thesis, Department of Electrical Engineering and Computer Science,
Massachusetts Institute of Technology, Cambridge, MA 02139, October 1992.
Also, MIT/LCS/TR-583.
Jennifer Welch and Nancy Lynch. A modular drinking philosophers algorithm.
Technical Memo MIT/LCS/TM-417.b, Laboratory for Computer Science, Massachusetts
Institute of Technology, Cambridge, MA, October, 1992.
1991
James
Aspnes, Maurice
Herlihy, and Nir Shavit.
Counting Networks and Multi-Processor Coordination. Proceedings of the 23rd Annual ACM Symposium
on Theory of Computing (STOC'91, New Orleans, Louisiana), pages 348-358,
May 1991.
James Aspnes, Maurice Herlihy, and Nir Shavit. Counting networks.
Technical Memo MIT/LCS/TM-451, Laboratory for Computer Science, Massachusetts
Institute of Technology, Cambridge, MA 02139, June 1991.
Hagit Attiya, Nancy Lynch, and Nir Shavit. Are wait-free algorithms
fast? Technical Memo MIT/LCS/TM-442, Laboratory for Computer Science,
Massachusetts Institute of Technology, Cambridge, MA, 02139, March 1991.
.pdf
Hagit Attiya and Jennifer Welch. Sequential consistency versus linearizability.
In Proceedings of the 3rd ACM Symposium on Parallel Algorithms and Architectures
(SPAA3), 1991.
H. Attiya and J.L. Welch. Sequential consistency versus linearizability.Technical Report #674, Technion - Israel Institute of Technology,
Department of Computer Science, Haifa, Israel, October 1991.
Hagit Attiya, Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. Bounds
on the time to reach agreement in the presence of timing uncertainty.
In Proceedings of the Twenty-third Annual ACM Symposium on Theory of
Computing, pages 359--369, New Orleans, Louisiana, May 1991, and in Real-time Systems Newsletter, 7(1/2):4--16, Winter/Spring 1991. .pdf
Hagit Attiya, Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. Bounds
on the time to reach agreement in the presence of timing uncertainty.
Real-time Systems Newsletter, 7(1/2):4--16, Winter/Spring 1991.
Hagit Attiya and Nancy Lynch. Theory of real-time systems - project
survey. In Andre M. Van Tilborg and Gary M. Koob, editors, Foundations
of Real-Time Computing: Formal Specifications and Methods, chapter 5, pages
111--138. Kluwer Academic Publishers, 1991. Office of Naval Research Workshop,
October, 1990. .pdf
Hagit Attiya and Nancy Lynch. Time bounds for real-time process control
in the presence of timing uncertainty. Technical Memo MIT/LCS/TM-403.b,
Laboratory for Computer Science, Massachusetts Institute of Technology,
Cambridge, MA, 02139, November 1991. .pdf
Hagit Attiya and Marc Snir. Better computing on the anonymous ring.
Journal of Algorithms, 12:204--238, June 1991.
Baruch Awerbuch and George Varghese. Distributed program checking:
a paradigm for building self-stabilizing distributed protocols. In
32nd Symposium on Foundations of Computer Science, pages 258--267, San
Juan, PR, October 1991. IEEE.
Baruch Awerbuch, Boaz Patt-Shamir, and George Varghese. Self-stabilization
by local checking and correction. In 32nd Symposium on Foundations
of Computer Science, pages 268--277, San Juan, PR, October 1991. IEEE.
Alan Fekete, Nancy Lynch, Yishay Mansour, and John Spinelli.
The Impossibility of Implementing Reliable Communication in the
Face of Crashes. Technical Memo MIT/LCS/TM-355.c, Massachusetts Institute of Technology, Laboratory for
Computer Science, September 1991.
Kenneth J. Goldman. Highly concurrent logically synchronous multicast.
Distributed Computing, 6(4):189--207, 1991.
Maurice Herlihy, Nir Shavit, and Orli Waarts. Low contention linearizable
counting. In Proceedings of the 32nd Annual Symposium on the Foundations
of Computer Science (FOCS), pages 526--535, San Juan, Puerto Rico, October
1991. IEEE. Detailed version with empirical results appeared as Technical
Memo MIT/LCS/TM-459, Laboratory for Computer Science, Massachusetts Institute
of Technology, Cambridge, MA, 02139, November 1991.
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
Yishay Mansour and Boaz Patt-Shamir. Greedy packet scheduling on
shortest paths. In Proceedings of the Tenth Annual ACM Symposium
on Principles of Distributed Computing, Montreal, Canada, August 1991.
Stephen J. Ponzio. The real-time cost of timing uncertainty: Consensus
and failure detection. (Masters Thesis) Technical Report MIT/LCS/TR-518,
Laboratory for Computer Science, Massachusetts Institute of Technology,
Cambridge, MA 02139, October 1991.
Stephen Ponzio. Consensus in the presence of timing uncertainty:
Omission and Byzantine failures. In Proceedings of the Tenth Annual
ACM Symposium on Principles of Distributed Computing, pages 125--138, Montreal,
Quebec, Canada, August 1991.
M. Saks, N. Shavit, and H. Woll. Optimal time randomized consensus
-- making resilient algorithms fast in practice. In Proceedings
of the 2nd ACM Symposium on Discrete Algorithms (SODA), pages 351--362,
San Francisco, January 1991.
F. W. Vaandrager. On the relationship between process algebra and
input/output automata (extended abstract). In 6th Annual Symposium
on Logic in Computer Science, pages 387--398, Amsterdam, 1991. IEEE Computer
Society Press.
F. W. Vaandrager. Determinism > (Event Structure Isomorphism =
Step Sequence Equivalence). Theoretical Computer Science, 79:275--294,
1991.
1990
Yehuda Afek, Hagit Attiya, Danny Dolev, Eli Gafni, Michael Merritt,
and Nir Shavit. Atomic snapshots of shared memory. In Proceedings
of the Ninth Annual ACM Symposium on Principles of Distributed Computing,
Quebec, Canada, August 1990.
Yehuda Afek, Hagit Attiya, Danny Dolev, Eli Gafni, Michael Merritt,
and Nir Shavit. Atomic snapshots of shared memory. Technical
Memo MIT/LCS/TM-429, Laboratory for Computer Science, Massachusetts Institute
of Technology, Cambridge, MA, 02139, May 1990.
Hagit Attiya, Amotz Bar-Noy, and Danny Dolev. Sharing memory robustly
in message-passing systems. In Proceedings of the Ninth Annual ACM
Symposium on Principles of Distributed Computing, Quebec, Canada, August
1990.
Hagit Attiya, Amotz Bar-Noy, and Danny Dolev. Sharing memory robustly
in message-passing systems. Technical Memo MIT/LCS/TM-423, Laboratory
for Computer Science, Massachusetts Institute of Technology, Cambridge,
MA, 02139, February 1990.
Hagit Attiya, Amotz Bar-Noy, Danny Dolev, David Peleg, and Rudiger Reischuk.
Renaming in an asynchronous environment. Journal of the ACM,
37(3):524--548, July 1990.
Hagit Attiya, Cynthia Dwork, Nancy A. Lynch, and Larry J. Stockmeyer.
Bounds on the time to reach agreement in the presence of timing uncertainty.
Technical Memo MIT/LCS/TM-435, Laboratory for Computer Science, Massachusetts
Institute of Technology, Cambridge, MA 02139, November 1990. .pdf
Hagit Attiya, Nancy Lynch, and Nir Shavit. Are wait-free algorithms
fast? In 31st Annual Symposium on Foundations of Computer Science,
volume 1, pages 55--64. IEEE, October 1990. .pdf
R. De Nicola and F.W. Vaandrager. Three logics for branching bisimulation.
Appeared as CWI Report CS-R9012,Amersterdam, 1990.
R. De Nicola and F. W. Vaandrager. Action versus state based logics
for transition systems. In I. Guessarian, editor, Semantics of Systems
of Concurrent Processes, Proceedings LITP Spring School on Theoretical
Computer Science, volume 469 of Lecture Notes in Computer Science, pages
407--419, La Roche Posay, France, 1990. Springer-Verlag.
A. D. Fekete. Asymptotically optimal algorithms for approximate agreement.
Distributed Computing, 4(1):9--29, March 1990.
Alan Fekete, Nancy Lynch, Michael Merritt, and William Weihl. Commutativity-based
locking for nested transactions. Journal of Computer and System
Sciences, 41(1):65--156, August 1990. .pdf
Alan Fekete, Nancy Lynch, Michael Merritt, and William Weihl.
Commutativity-based locking for nested transactions.
In John Rosenberg and David Koch, editors, Persistent Object
Systems, Newcastle, Australia (Proceedings of the 3rd International
Workshop on Persistent Object Systems, January 1989), pages
319-340, Workshops in Computing, Springer-Verlag, 1990. .pdf
Alan Fekete and Nancy Lynch. The need for headers: an impossibility
result for communication over unreliable channels. In G. Goos and J.
Hartmanis, editors, CONCUR '90, Theories of Concurrency: Unification
and Extension, volume 458 of Lecture Notes in Computer Science, pages 199--216.
Springer-Verlag, August 1990. .pdf
Alan Fekete and Nancy Lynch. The need for headers: an impossibility
result for communication over unreliable channels. Technical Memo
MIT/LCS/TM-428, Laboratory for Computer Science, Massachusetts Institute
of Technology, Cambridge, MA, 02139, May 1990. .pdf
Alan Fekete, Nancy Lynch, and William Weihl. A serialization graph
construction for nested transactions. In Proceedings of the Ninth
Annual ACM Symposium on Principles of Database Systems, pages 94--108,
Nashville, TN, April 1990. .pdf
Alan Fekete and Nancy Lynch and William Weihl. A Serialization
Graph Construction for Nested Transactions. Technical Memo
MIT/LCS/TM-421, Laboratory for Computer Science, Massachusetts
Institute of Technology, Cambridge, MA 02139, February 1990. .pdf
Michael J. Fischer, Nancy A. Lynch, and Michael Merritt. Easy
impossibility proofs for distributed consensus problems.In
B. Simons and A. Spector, editors, Fault-tolerant Distributed
Computing (Proceedings of of the Asilomar Workshop on Fault-Tolerant
Distributed Computing, March, 1986), volume 448 of Lecture
Notes in Computer Science, pages 147-170, 1990. Springer-Verlag. pdf
Kennth J. Goldman and Nancy A. Lynch. Modelling shared state in a
shared action model. In Proceedings of the 5th Annual IEEE Symposium
on Logic in Computer Science, pages 450--463, Philadelphia, Pennyslvania,
June 1990. pdf
Kenneth J. Goldman and Nancy Lynch. Modelling shared state in a shared
action model. Technical Memo MIT/LCS/TM-427, Laboratory for Computer
Science, Massachusetts Institute of Technology, Cambridge, MA, 02139, March
1990. pdf
Kenneth J. Goldman. Distributed algorithm simulation using input/output
automata. Ph.D thesis, Department of Electrical Engineering and
Computer Science, Massachusetts Institute of Technology, Cambridge,
MA, July 1990. Technical Report MIT/LCS/TR-490, Cambridge, MA, September
1990.
M. Gupta. I/O automaton based simulation of selected distributed
algorithms. Bachelor Thesis, MIT Dept. of Electrical Engineering
and Computer Science, June, 1990.
Joseph Y. Halpern and Yoram Moses. Knowledge and common knowledge
in a distributed environment. Journal of the ACM, 37(3):549--587,
1990.
Leslie Lamport and Nancy Lynch. Distributed computing: Models and
methods. In Jan Van Leeuwen, editor, Formal Models and Semantics,
volume B of Handbook of Theoretical Computer Science, chapter 18, pages
1157--1199. Elsevier Science Publishers B. V. and MIT Press, 1990.
John Leo. Dynamic process creation in a static model. Master's
thesis, Department of Electrical Engineering and Computer Science, Cambridge,
MA 02139, May 1990.
Nancy Lynch and Hagit Attiya. Using mappings to prove timing properties.
In Proceedings of the Ninth Annual ACM Symposium on Principles of Distributed
Computing, Quebec, Canada, August 1990. pdf
Expanded version in earlier Technical memo, TM412.d.
Nancy A. Lynch. Multivalued possibilities mappings. In J.W. de
Bakker, W.P. de Roever, and G. Rozenberg, editors, Stepwise Refinement
of Distributed Systems: Models, Formalisms, Correctness (REX Workshop,
Mook, The Netherlands, May/June 1989), volume 430 of Lecture Notes in Computer
Science, pages 519--543. Springer-Verlag, 1990. .pdf
Nancy Lynch. Multivalued possibilities mappings. Technical
Memo MIT/LCS/TM-422, Laboratory for Computer Science, Massachusetts Institute
of Technology, Cambridge, MA, 02139, August 1990. .pdf
B. Simons, Jennifer L. Welch, and Nancy Lynch. An overview of
clock synchronization. In B. Simons and A. Spector, editors,
Fault-tolerant Distributed Computing (Proceedings of of the Asilomar
Workshop on Fault-Tolerant Distributed Computing, March, 1986),
volume 448 of Lecture Notes in Computer Science, pages 84-96,
1990. Springer-Verlag. .pdf
Ken Streeter. A partitioned computation machine. Master's thesis,
Department of Electrical Engineering and Computer Science, Massachusetts
Institute of Technology, Cambridge, MA 02139, August 1990.
Greg Troxel. A hierarchical proof of an algorithm for deadlock recovery
in a system using remote procedure calls. Master's thesis, Department
of Electrical Engineering and Computer Science, Massachusetts Institute
of Technology, Cambridge, MA 02139, January 1990. Technical Report
MIT/LCS/TR-474, Cambridge, MA 02139, 1990.
Mark R. Tuttle. Knowledge and distributed computation. Technical
Memo MIT/LCS/TR-477, Laboratory for Computer Science, Massachusetts
Institute of Technology, Cambridge, MA, 02139, 1990.
1989
Hagit Attiya, Danny Dolev, and Nir Shavit.
Bounded polynomial randomized consensus.
In Proceedings of the Eighth Annual ACM Symposium on Principles
of Distributed Computing, pages 281--293, Edmonton, Alberta, Canada, August
1989.
Hagit Attiya, Danny Dolev, and Nir Shavit.
Bounded polynomial randomized consensus. Technical Memo
MIT-LCS-TM-392, MIT Laboratory for Computer Science, Cambridge, MA
02139, June 1989.
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.
Hagit Attiya and Mark Tuttle.
Bounds for slotted $ell-exclusion$.
Unpublished manuscript, February 1989.
Christopher P. Colby. Correctness Proofs of the
Peterson-Fischer Mutual Exclusion Algorithms. Technical Memo
MIT/LCS/TM-399, Laboratory for Computer Science, Massachusetts
Institute of Technology Cambridge, MA, June 1989. Bachelors thesis.
Danny Dolev and Nir Shavit.
Bounded concurrent time-stamp systems are constructible.
In Proceedings of the Twenty-first Annual ACM Symposium on
Theory of Computing, pages 454--466, Seattle, Washington, May 1989.
Danny Dolev and Nir Shavit. Bounded concurrent time-stamp
systems are constructible. Technical Memo
MIT/LCS/TM-393, Laboratory for Computer Science, Massachusetts
Institute of Technology Cambridge, MA, June 1989.
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
Kenneth J. Goldman.
Highly concurrent logically synchronous multicast.
In Proceedings of the 3rd International Workshop on Distributed
Algorithms, volume 392 of Lecture Notes in Computer Science, Nice,
France, September 1989. Springer-Verlag.
Kenneth J. Goldman.
Highly concurrent logically synchronous multicast.
Technical Memo MIT/LCS/TM-401, Laboratory for Computer Science,
Massachusetts Institute of Technology, Cambridge, MA, July 1989.
Kenneth J. Goldman.
Paralation views: Abstractions for efficient scientific computing on
the connection machine.
Technical Memo MIT/LCS/TM-398, Laboratory for Computer Science,
Massachusetts Institute of Technology, Cambridge, MA, August 1989.
Joseph Halpern and Mark Tuttle.
Knowledge, probability, and adversaries.
In Proceedings of the Eighth Annual ACM Symposium on Principles
of Distributed Computing, pages 103--118, August 1989.
Also, IBM Research Report RJ 7045, September 1989.
Maurice Herlihy, Nancy Lynch, Michael Merritt, and William Weihl.
On the correctness of orphan management algorithms.
Technical Memo MIT/LCS/TM-406, Laboratory for Computer Science,
Massachusetts Institute of Technology, Cambridge, MA 02139, August
1989. pdf
Leslie Lamport and Nancy Lynch.
Chapter on distributed computing.
Technical Memo MIT/LCS/TM-384, Laboratory for Computer Science,
Massachusetts Institute of Technology, Cambridge, MA, 02139,
February 1989. pdf
Nancy Lynch.
A hundred impossiblility proofs for distributed computing.
In Proceedings of the Eighth Annual ACM Symposium on Principles
of Distributed Computing, Edmonton, Alberta, Canada, August
1989. PDF
Nancy Lynch.
A hundred impossiblility proofs for distributed computing.
Technical Memo MIT/LCS/TM-394, Laboratory for Computer Science,
Massachusetts Institute of Technology, Cambridge, MA, 02139, 1989. PDF
Nancy Lynch and Hagit Attiya. Using mappings to prove timing properties.
Technical Memo MIT/LCS/TM-412.b, Laboratory for Computer Science,
Massachusetts Institute of Technology, Cambridge, MA, 02139,
December 1989.
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)
Magda F. Nour. An Automata-Theoretic Model for Unity.
Technical Memo MIT/LCS/TM-400, Laboratory for Computer Science,
Massachusetts Institute of Technology, Cambridge, MA 02139, June
1989. Bachelors thesis.
Mark R. Tuttle.
Knowlege and Distributed Computation.
Ph.D thesis, Department of Electrical Engineering and Computer
Science, Massachusetts Institute of Technolgy, September 1989.
Jennifer Welch and Nancy Lynch.
Synthesis of efficient drinking philosophers algorithms.
Technical Memo MIT/LCS/TM-417, Laboratory for Computer Science,
Massachusetts Institute of Technology, Cambridge, MA, November,
1989. .pdf
1988
James Aspnes, Alan Fekete, Nancy Lynch, Michael Merritt, and William Weihl.
A theory of timestamp-based concurrency control for nested
transactions.
In Proceedings of 14th International Conference on Very Large
Data Bases, pages 431--444, Los Angeles, CA., August 1988. .pdf
Bard Bloom.
Constructing two-writer registers.
IEEE Transactions on Computers, 37(12):1506--1514,
December 1988.
Brian A. Coan.
A compiler that increases the fault-tolerance of asynchronous
protocols.
IEEE Transactions on Computers, (Special Issue on Parallel and
Distributed Algorithms), 37(12):1541--1553, December 1988.
Brian Coan and Jennifer Lundelius.
Transaction commit in a realistic timing model.
Technical Memo MIT/LCS/TM-360, Laboratory for Computer Science,
Massachuetts Institute of Technology, Cambridge, MA, June 1988.
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
Joseph Halpern, Yoram Moses, and Mark Tuttle.
A knowledge-based analysis of zero knowledge.
In Proceedings of the Twentieth Annual ACM Symposium on Theory
of Computing, pages 132--147, May 1988.
Nancy Lynch.
Modelling real-time systems.
In Foundations of Real-Time Computing Research Initiative, Fall
Church, Virginia, November 1988. Office of Naval Research Kickoff
Workshop. pdf
Nancy Lynch.
I/O Automata: A model for discrete event systems.
In 22nd Annual Conference on Information Sciences and Systems,
pages 29-38, Princeton University, Princeton, N.J., March 1988. pdf
Nancy Lynch.
I/O Automata: A model for discrete event systems.
Technical Memo MIT/LCS/TM-351, Laboratory for Computer Science,
Massachusetts Institute of Technology, Cambridge, MA, 02139, March
1988. pdf
Nancy Lynch, Yishay Mansour, and Alan Fekete.
The data link layer: Two impossibility results.
In Proceedings of the Seventh Annual ACM Symposium on Principles
of Distributed Computing, pages 149--170, Toronto, Ontario, Canada, August
1988. .pdf
Nancy Lynch, Michael Merritt, William Weihl, and Alan Fekete.
A theory of atomic transactions. In M. Gyssens, J. Paredaens,
D. Van Gucht, editors ICDT'88 (Proceedings of the 2nd
International Conference on Database Theory, Bruges, Belgium,
August/September 1988), volume 326 of Lecture Notes in
Computer Science, pages 41--71, Springer-Verlag, 1988. .pdf
Nancy Lynch, Michael Merritt, William Weihl, and Alan Fekete.
A theory of atomic transactions.
Technical Memo MIT/LCS/TM-362, Laboratory for Computer Science,
Massachusetts Institute of Technology, Cambridge, MA, 02139, June
1988. .pdf
Nancy Lynch and Michael Merritt.
Introduction to the theory of nested transactions.
Theoretical Computer Science, 62(1,2):123--186, December 1988.
.pdf
Nancy Lynch and Eugene Stark.
A proof of the Kahn principle for Input/Output automata.
Technical Memo MIT/LCS/TM-349, Laboratory for Computer Science,
Massachusetts Institute of Technology, Cambridge, MA, 02139, January
1988. .pdf
Nancy Lynch and Mark Tuttle.
An introduction to Input/Output automata.
Technical Memo MIT/LCS/TM-373, Laboratory for Computer Science,
Massachusetts Institute of Technology, Cambridge, MA, 02139, November 1988.
Yoram Moses and Mark R. Tuttle.
Programming simultaneous actions using common knowledge.
Algorithmica, 3(1):121--169, 1988.
Special Issue on Parallel and Distributed Computing, Part 1.
S. Mullender and P.M.B. Vitanyi.
Distributed match-making.
Algorithmica, 3:367--391, 1988.
Special issue on Distributed Computing.
Russel Schaffer.
On the correctness of atomic multi-writer registers.
Technical Memo MIT/LCS/TM-364, Laboratory for Computer Science,
Massachusetts Institute of Technology, Cambridge, MA, 02139, June
1988. (Revised January 1989).
Russel W. Schaffer.
Peterson-burns multi-writer, multi-reader atomic register algorithm.
Bachelor's Thesis, June 1988, Department of Electrical Engineering
and Computer Science, Massachusetts Institute of Technology, Cambridge, MA
02139.
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.
E. W. Stark.
Proving entailment between conceptual state specifications.
Theoretical Computer Science, 56(1):135--154, January 1988.
Mark R. Tuttle.
A game-theoretic characterization of eventual common knowledge.
Unpublished manuscript., October 1988.
P.M.B. Vitanyi.
Locality, communication and interconnect length in multicomputers.
SIAM Journal on Computing, 17:659--672, 1988.
Jennifer Lundelius Welch and Nancy Lynch.
A new fault-tolerant algorithm for clock synchronization.
Information and Computation, 77(1):1--36, April 1988. .pdf
Jennifer Lundelius Welch. Simulating Synchronous Processors.
Technical Memo MIT/LCS/TM-359, MIT Laboratory for Computer Science, Massachusetts Institute
of Technology, Cambridge, MA, June 1988.
Jennifer Lundelius Welch.
Topics in Distributed Computing: The Impact of Partial
Synchrony, and Modular Decomposition of Algorithms.
Ph.D thesis, Department of Electrical Engineering and Computer
Science, Massachusetts Institute of Technology, Cambridge, MA 02139, March
1988.
Jennifer Lundelius Welch, Leslie Lamport, and Nancy Lynch.
A lattice-structured proof technique applied to a minimum spanning
tree algorithm.
In Proceedings of the Seventh Annual ACM Symposium on Principles
of Distributed Computing, pages 28--43, Toronto, Ontario, Canada, August
1988. .pdf
Jennifer Lundelius Welch, Leslie Lamport, and Nancy Lynch.
A lattice-structured proof technique applied to a minimum spanning
tree algorithm.
Technical Memo MIT/LCS/TM-361, Laboratory for Computer Science,
Massachusetts Institute of Technology, Cambridge, MA, 02139, June
1988. .pdf
1987
James Aspnes.
Timestamp ordering and nested transactions.
Master's thesis, Department of Electrical Engineering and Computer
Science, Massachusetts Institute of Technology, Cambridge, MA 02139, May
1987.
Bard Bloom.
Constructing two-writer atomic registers.
In Proceedings of the Sixth Annual ACM Symposium on Principles
of Distributed Computing, pages 249--259, Vancouver, British Columbia,
Canada, August 1987.
James E. Burns and Nancy A. Lynch.
The Byzantine firing squad problem. Advances in Computing
Research, 4:147--161, 1987. .pdf
Brian A. Coan.
Achieving Consensus in Fault-Tolerant Distributed Computer
Systems: Protocols, Lower Bounds, and Simulations.
Ph.D thesis, Department of Electrical Engineering and Computer
Science, Massachusetts Institute of Technology, Cambridge, MA 02139, June
1987.
A. P. DiPesa Jr.
Real-time extensions to a relational database.
Master's thesis, Department of Electrical Engineering and Computer
Science, Massachusetts Institute of Technology, Cambridge, MA 02139, June
1987.
Danny Dolev, Cynthia Dwork, and Larry Stockmeyer.
On the minimal synchronism needed for distributed consensus.
Journal of the ACM, 34(1):77--97, January 1987.
Alan Fekete.
Topics in Distributed Algorithms.
Ph.D thesis, Department of Mathematics, Harvard University, Cambridge,
MA, August 1987.
Alan Fekete.
Asynchronous approximate agreement.
In Proceedings of the Sixth Annual ACM Symposium on Principles
of Distributed Computing, pages 64--76, August 1987.
Alan Fekete.
Approximate agreement.
Technical Memo MIT/LCS/TM-342, Laboratory for Computer Science,
Massachusetts Institute of Technology, Cambridge, MA 02139, September 1987.
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
Kenneth J. Goldman.
Data replication in nested transaction systems.
Masters Thesis. Technical Report MIT/LCS/TR-390, MIT Laboratory for Computer Science,
Massachusetts Institute of Technology, Cambridge, MA, May 1987.
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)
Yoram Moses and Mark R. Tuttle.
Programming simultaneous actions using common knowledge.
Technical Report MIT/LCS/TR-369, Laboratory for Computer Science,
Massachusetts Institute of Technology, Cambridge, MA 02139, February 1987.
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
C. Clifton.
Dynamic load balancing.
Master's thesis, Department of Electrical Engineering and Computer
Science, Massachusetts Institute of Technology, Cambridge, MA 02139, June
1986.
Brian Coan and Cynthia Dwork. Simultaneity is harder than
agreement. In Proceedings of the 5th Symposium on Reliability in
Distributed Software and Database Systems, pages 141--150, Los
Angeles, CA, January 1986.
Brian A. Coan. A communication-efficient canonical form for
fault-tolerant distributed protocols. In Proceedings of the
Fifth Annual ACM Symposium on Principles of Distributed
Computing, pages 63--72, Calgary, Alberta, Canada, August 1986.
B. Coan, B. Oki, and E. Kolodner. Limitations on database
availability when networks partition. In Proceedings of the 5th
Annual ACM Symposium on Principles of Distributed Computing,
pages 187--194, Calgary, Alberta, Canada, August 1986. Also,
Programming Methodology Group Memo 49, MIT Laboratory for Computer
Science, Cambridge, MA 02139.
Brian Coan and Jennifer Welch. Transaction commit in a realistic
fault model. In Proceedings of the Fifth Annual ACM Symposium
on Principles of Distributed Computing, pages 40--51, Calgary,
Alberta, Canada, August 1986.
Danny Dolev, Nancy A. Lynch, Shlomit S. Pinter, Eugene W. Stark, and
William E. Weihl. Reaching approximate agreement in the presence of
faults. Journal of the ACM, 33(3):499--516, July
1986. pdf
Cynthia Dwork and Yoram Moses. Knowledge and Common Knowledge in a
Byzantine Environment: Crash Failures. Technical Memo, MIT/LCS/TM-300,
Laboratory for Computer Science, Massachusetts Institute
of Technology, Cambridge, MA, July 1986.
Cynthia Dwork and Yoram Moses. Knowledge and common knowledge in a
Byzantine Environment I: Crash failures. In Proceedings of
Conference on Theoretical Aspects of Reasoning about Knowledge,
1986.
Alan Fekete. Asymptotically optimal algorithms for approximate
agreement. In Proceedings of the Fifth Annual ACM Symposium on
Principles of Distributed Computing, pages 73--87, Calgary,
Alberta, Canada, August 1986.
Michael J. Fischer, Nancy A. Lynch, and Michael Merritt. Easy
impossibility proofs for distributed consensus problems.
Distributed Computing, 1(1):26--39, January 1986. pdf
Maurice Herlihy, Nancy Lynch, Michael Merritt, and William Weihl.
On the correctness of orphan elimination algorithms.
Programming Methodology Group Memo 50, Laboratory for Computer Science,
Massachusetts Institute of Technology, Cambridge, MA, December
1986. pdf
E. Kranakis and P.M.B. Vitanyi. Distributed control in computer
networks and cross-sections of multidimensional bodies. Technical
Memo MIT/LCS/TM-304, Laboratory for Computer Science, Massachusetts
Institute of Technology, Cambridge, MA 02139, March 1986.
M. Li, L. Longpre, and P.M.B. Vitanyi. The power of the queue. In
Structure in Complexity Theory Conference, pages 219--233,
Berlin, April 1986. Spring Verlag.
M. Li, L. Longpre, and P.M.B. Vitanyi. The power of the queue.
Technical Memo MIT/LCS/TM-303, Laboratory for Computer Science,
Massachusetts Institute of Technology, Cambridge, MA, 02139, April
1986.
Nancy Lynch, Barbara Blaustein, and Michael Siegel. Correctness
conditions for highly available replicated databases. In
Proceedings of the Fifth Annual ACM Symposium on Principles of
Distributed Computing, pages 11--28, Calgary, Alberta, Canada,
August 1986. .pdf
Nancy Lynch, Barbara Blaustein, and Michael Siegel. Correctness
conditions for highly available replicated databases. Technical
Report MIT/LCS/TR-364, Laboratory for Computer Science, Massachusetts
Institute of Technology, Cambridge, MA, 02139, June 1986. .pdf
Nancy A. Lynch, Nancy D. Griffeth, Michael J. Fischer, and Leonidas
J. Guibas. Probabilistic analysis of a network resource allocation
algorithm. Information and Computation, 68(1-3):47--85,
January-February-March 1986. .pdf (Note, abstract in AMS Workshop on Probabilistic Algorithms, June 1985).
Nancy Lynch and Michael Merritt. Introduction to the theory of
nested transactions. In Giorgio Ausiello and Paolo Atzeni,
editors, ICDT'86 (Proceedings of the International Conference on
Database Theory, Rome, Italy, September 1986), volume 243 of Lecture
Notes in Computer Science, pages 278-305, 1986.
Springer-Verlag. .pdf
Nancy Lynch and Michael Merritt. Introduction to the theory of
nested transactions. Technical Memo MIT/LCS/TM-367, Laboratory for
Computer Science, Massachusetts Institute of of Technology, July
1986. pdf
Nancy A. Lynch. Concurrency control for resilient nested
transactions. Advances in Computing Research, 3:335--373,
1986. .pdf
Yoram Moses and Mark R. Tuttle. Programming simultaneous actions
using common knowledge. In Proceedings of the 27th Annual
Symposium on Foundations of Computer Science, pages 208--221,
Toronto, Ontario, Canada, October 1986.
S. Mullender and P.M.B. Vitanyi. Distributed match-making for
processes in computer networks. In Proceedings of the Fourth
Annual ACM Symposium on Principles of Distributed Computing,
pages 261--271, Minaki, Ontario, Canada, August 1985. Also, CWI
Report CS-R8513. Reprinted in Operating Systems Review, 1986.
E. W. Stark. Proving entailment between conceptual state
specifications. In Proceedings of the 1986 European Symposium
on Programming, volume 213 of Lecture Notes in Computer
Science, pages 197--209, Saarbrucken, West Germany, March
1986. Springer-Verlag.
Paul Vitanyi. Non-sequential computation and laws of nature. In
Proceedings of Aegean Workshop on Computing, VLSI Algorithms and
Architectures(2nd International Workshop on Parallel Processing and
VLSI), 1986.
Paul Vitanyi. Non-sequential computation and laws of nature.
Technical Memo MIT/LCS/TM-306, Laboratory for Computer Science,
Massachusetts Institute of Technology, Cambridge, MA, 02139, May
1986.
P.M.B. Vitanyi. Archirithmics or algotecture? Mathematics
and Computer Science II, 4:139--161, 1986. CWI Monographs,
M. Hazewinkel, J.K. Lenstra and L.G.L.T. Meertens, Eds.,
North-Holland.
1985
Baruch Awerbuch and Robert G. Gallager. Distributed BFS algorithms.
In 26th Annual Symposium on Foundations of Computer Science.
IEEE, October 1985.
Baruch Awerbuch. Complexity of network synchronization.
Journal of the ACM, 32(4):804--823, October 1985.
Baruch Awerbuch. A new distributed depth-first-search algorithm.
Information Processing Letters, 20:147--150, April 1985.
James Burns and Nancy Lynch. The Byzantine firing squad problem.
Technical Memo MIT/LCS/TM-275, Laboratory for Computer Science,
Massachusetts Institute of of Technology, Cambridge, MA, 02139, April
1985. pdf
Benny Chor and Brian A. Coan. A simple and efficient randomized
Byzantine agreement algorithm. IEEE Transactions on Software
Engineering, SE-11(6):531--539, June 1985. Reprinted from IEEE 1984
Proceedings of the Fourth Symposium on Reliability in
Distributed Software and Database Systems.
B. Chor, M. Merritt, and D. B. Shmoys. Simple constant-time consensus
protocols in realistic failure models. In Proceedings of the
Fourth Annual ACM Symposium on Principles of Distributed Computing,
pages 152--162, 1985.
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
N. Dershowitz and S. Zaks. Patterns in trees.
Technical Memo MIT/LCS/TM-271, Laboratory for
Computer Science, Massachusetts Institute of Technology, Cambridge,
MA, January 1985.
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. (Earlier version in 1983.)
Danny Dolev, Nancy A. Lynch, Shlomit S. Pinter, Eugene W. Stark, and
William E. Weihl. Reaching approximate agreement in the presence
of faults. Technical Memo MIT/LCS/TM-276, Laboratory for Computer
Science, Massachusetts Institute of Technology, Cambridge MA 02139,
February 1985. .pdf
Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. Consensus in the
presence of partial synchrony. Technical Memo MIT/LCS/TM-270,
Laboratory for Computer Science, Massachusetts Institute of
Technology, October 1985. Revision of MIT/LCS/TM-270 (October 1984). .pdf
Michael J. Fischer, Nancy D. Griffeth, Leonidas J. Guibas, and
Nancy A. Lynch.
Probabilistic analysis of a network resource allocation algorithm.
Technical Memo MIT/LCS/TM-278, Laboratory for Computer Science,
Massachusetts Institute of Technology, Cambridge, MA, 02139, April
1985. .pdf
Michael Fischer, Nancy Lynch, James Burns, and Allan Borodin.
Distributed FIFO allocation of identical resources using small
shared space. Technical Memo MIT/LCS/TM-290, Laboratory for Computer
Science, Massachusetts Institute of Technology, June 1985. .pdf
Michael Fischer, Nancy Lynch, and Michael Merritt. Easy impossibility
proofs for distributed consensus problems. In Proceedings of
the Fourth Annual ACM Symposium on Principles of Distributed
Computing, pages 59--70, August 1985. pdf
Michael Fischer, Nancy Lynch, and Michael Merritt.
Easy impossibility proofs for distributed consensus problems.
Technical Memo MIT/LCS/TM-279, Laboratory for Computer Science,
Massachusetts Institute of Technology, Cambridge, MA, 02139, June
1985. pdf
Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson.
Impossibility of distributed consensus with one faulty process.
Journal of the ACM, 32(2):374--382, April 1985. pdf
Greg N. Frederickson and Nancy Lynch. Electing a leader in a
synchronous ring. Technical Memo MIT/LCS/TM-277, Laboratory for
Computer Science, Massachusetts Institute of of Technology,
Cambridge, MA 02139, July 1985. Earlier version dated March, 1985
entitled ``A General Lower Bound for Electing a Leader in a
Ring''. pdf
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
P.C. Kanellakis and S.S. Cosmadakis.
Equational theories and database constraints.
In Proceedings of the Seventeenth Annual ACM Symposium on Theory
of Computing, May 1985.
P.C. Kanellakis and S.S. Cosmadakis. Two applications of
equational theories to database theory. In Proceedings of
First International Conference on Rewriting Techniques and
Applications, May 1985.
P.C. Kanellakis, S.S. Cosmadakis, and N. Spyratos. Partition
semantics for relations. In Proceedings of the Fourth Annual
ACM Symposium on Principles of Distributed Computing, May 1985.
Submitted to J. COMP. AND SYST. SCI., special issue on the 4th PODS
conference (J.D. Ullman, editor).
P.C. Kanellakis, K.J. Goldman, S.A. Goldman, and S.B. Zdonik.
ISIS: Interface for a semantic information system. In
Proceedings of ACM SIGMOD, May 1985.
P.C. Kanellakis and C.H. Papadimitriou. The complexity of
distributed concurrency control. SIAM Journal on
Computing, 14(1):52--75, February 1985.
P.C. Kanellakis and S.A. Smolka. On the analysis of cooperation
and antagonism in networks of communicating processes. In
Proceedings of the Fourth Annual ACM Symposium on Principles of
Distributed Computing, August 1985.
Nancy A. Lynch. Concurrency control for resilient nested
transactions. Technical Report MIT/LCS/TR-285, Laboratory for
Computer Science, Massachusetts Institute of Technology, Cambridge,
MA 02139, October 1985.
Nancy Lynch and Greg N. Frederickson.
Electing a leader in a synchronous ring.
Technical Memo MIT/LCS/TM-277, Laboratory for Computer Science,
Massachusetts Institute of of Technology, Cambridge, MA 02139, July 1985.
Note earlier version dated March, 1985 entitled ``A General Lower Bound
for Electing a Leader in a Ring''.
E. N. McKay. A methodology for software implemented transient error
recovery in spacecraft computation. SB/SM thesis, MIT, Department of
Electrical Engineering and Computer Science, Cambridge, MA, January
1985.
S. Mullender and P.M.B. Vitanyi. Distributed match-making for
processes in computer networks. In Proceedings of the Fourth
Annual ACM Symposium on Principles of Distributed Computing, pages
261--271, Minaki, Ontario, Canada, August 1985. Also, CWI Report
CS-R8513. Reprinted in Operating Systems Review, 1986.
E. W. Stark. A proof technique for rely/guarantee properties. In
Proceedings of the 5th Conference on Foundations of Software
Technology and Theoretical Computer Science, volume 206 of
Lecture Notes in Computer Science, pages 369--391, New Delhi, India,
December 1985. Springer-Verlag.
1984
Benny Chor and Brian A. Coan. A simple and efficient randomized
Byzantine agreement algorithm. Technical Memo MIT/LCS/TM-266, Laboratory for Computer Science,
Massachusetts Institute of Technology, Cambridge, MA 02139, August 1984.
Brian A. Coan and Russell Turpin. Extending Binary Byzantine
Agreement to Multivalued Byzantine agreement. Technical Memo
MIT/LCS/TR-315, Laboratory for Computer Science, Massachusetts
Institute of Technology, Cambridge, MA, 02139, April 1984.
Cynthia Dwork, Paris C. Kanellakis, and John C. Mitchell. On the
sequential nature of unification. Technical Memo MIT/LCS/TM-257,
Massachusetts Institute of Technology, Cambridge, MA 02139, March
1984.
C. Dwork, P. Kanellakis, and J. Mitchell. On the sequential nature of
unification. Journal of Logic Programming, 1(1),
pages 35-50, 1984.
Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. Consensus in the
presence of partial synchrony(preliminary version). Technical Memo
MIT/LCS/TM-270, Laboratory for Computer Science, Massachusetts
Institute of Technology, October 1984. Revised MIT/LCS/TM-270
(October 1985).
Cynthia Dwork and Dale Skeen. Patterns of communication in
consensus protocols. In Proceedings of the Third Annual ACM
Symposium on Principles of Distributed Computing, pages 143-153,
Vancouver, BC,
Canada, August 1984.
N. Dershowitz and S. Zaks. Patterns in trees. In Proceedings
of the 9th Colloquium on Trees in Algebra and Programming, Bordeaux,
France, March 1984.
Greg N. Frederickson and Nancy Lynch. The impact of synchronous
communication on the problem of electing a leader in a ring. In
Proceedings of the Sixteenth Annual ACM Symposium on Theory of
Computing, pages 493--503, April 1984. .pdf
Joseph Y. Halpern and Yoram Moses. Knowledge and common
knowledge in a distributed environment. Proceedings of the 3rd ACM
Symposium on Principles of Distributed Computing, pages 50-61,
Vancouver, BC, Canada, August 1984. Preliminary version.
Jennifer Lundelius. Synchronizing Clocks in a Distributed
System. Masters thesis, Department of Electrical
Engineering and Computer Science, Massachusetts Institute of
Technology, Cambridge, MA 02139. Technical
Report MIT/LCS/TR-335, Cambridge, MA, August 1984. tar file
Jennifer Lundelius and Nancy Lynch. An upper and lower bound for
clock synchronization. Information and Control,
62(2-3):190--204, August/September 1984. .pdf
Jennifer Lundelius and Nancy Lynch. A new fault-tolerant algorithm
for clock synchronization. In Proceedings of the Third Annual
ACM Symposium on Principles of Distributed Computing, pages
75--88, Vancouver, B.C., Canada, August 1984. .pdf
Jennifer Lundelius and Nancy Lynch. A new fault-tolerant algorithm
for clock synchronization. Technical Memo MIT/LCS/TM-265, Laboratory
for Computer Science, Massachusetts Institute of Technology,
Cambridge, MA, 02139, July 1984. .pdf
Nancy Lynch and Greg N. Frederickson. The impact of synchronous
communication on the problem of electing a leader in a ring.
Technical Memo MIT/LCS/TM-259, Laboratory for Computer Science,
Massachusetts Institute of Technology, April 1984. .pdf
Michael Merritt. Elections in the presence of faults. In
Proceedings of the Third Annual ACM Symposium on Principles of
Distributed Computing, pages 134--142, Vancouver, B.C., Canada,
August 1984.
M. Merritt and J. Mitchell. A distributed algorithm for deadlock
detection and resolution. In Proceedings of the Third Annual
ACM Symposium on Principles of Distributed Computing, pages
282--284, Vancouver, B.C., Canada, August 1984.
N. Savasta. Implementation of a compiler-compiler. Bachelor's
Thesis, June 1984, Massachusetts Institute of Technology.
E. W. Stark. Foundations of a Theory of Specification for
Distributed Systems. Ph.D thesis, Massachusetts Institute of
Technology, Laboratory for Computer Science, Cambridge, MA 02139,
August 1984. Technical Report MIT/LCS/TR-342, Massachusetts
Institute of Technology, Laboratory for Computer Science, Cambridge,
MA 02139, August 1984.
Russell Turpin and Brian A. Coan. Extending binary Byzantine
agreement to multivalued Byzantine agreement. Information
Processing Letters, 18(2):73--76, February 1984.
1983
Baruch Awerbuch and Shimon Even. A formal approach to a
communication-network protocol; broadcast as a case study. Technical
Report TR-459, Electrical Engineering Department, Technion-I.I.T.,
Haifa, December 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, Cynthia Dwork, and Larry Stockmeyer. On the minimal
synchronism needed for distributed consensus. In 24th Annual
Symposium on Foundations of Computer Science, pages 393--402,
Tucson, Arizona, 1983.
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
Danny Dolev and Nancy A. Lynch and Shlomit S. Pinter and
Eugene W. Stark and William E. Weihl. Reaching Approximate Agreement
in the Presence of Faults, Technical Memo MIT/LCS/TM-251,
Massachusetts Institute of Technology, Laboratory for Computer Science,
Cambridge, MA 02139, December 1983. pdf
Cynthia Dwork and Dale Skeen. The inherent cost of nonblocking
commitment. In Proceedings of the Second Annual ACM Symposium
on Principles of Distributed Computing, pages 1--11, Montreal,
Quebec, Canada, August 1983.
Michael Fischer, Nancy Lynch, James Burns, and Allan Borodin. The
colored ticket algorithm. Technical Memo MIT/LCS/TM-269, Laboratory
for Computer Science, Massachusetts Institute of Technology, August
1983. .pdf
Michael Fischer, Nancy Lynch, and Michael S. Paterson.
Impossibility of distributed consensus with one faulty process. In
Proceedings of the 2nd ACM Symposium on Principles of Database
Systems, pages 1--7, Atlanta, GA, March 1983. .pdf
J. Goree. Internal consistency of a distributed transaction system
with orphan detection. Master's thesis, Department of Electrical
Engineering and Computer Science, Massachusetts Institute of
Technology, Cambridge, MA 02139, January 1983. Technical Memo
MIT/LCS/TR-286, Laboratory for Computer Science, Massachusetts
Institute of Technology, Cambridge, MA, 1983.
Nancy Lynch and Michael Fischer. A technique for decomposing
algorithms which use a single shared variable. Journal of
Computer and System Sciences, 27(3):350--377, December 1983. .pdf
Nancy Lynch. Concurrency control for resilient nested
transactions. In Proceedings of the Second ACM SIGACT-SIGMOD
Symposium on Principles of Database Systems, pages 166--181,
Atlanta, Georgia, March 1983. .pdf
Nancy A. Lynch. Concurrency control for resilient nested
transactions. MIT Laboratory for Computer Science Technical
Report MIT/LCS/TR-285, Cambridge, MA 02139, February 1983. (Note,
same TR number was used in 1985). .pdf
Nancy Lynch. Multilevel atomicity--a correctness criterion for
database concurrency control. ACM Transactions on Database
Systems, 8(4):484--502, December 1983. .pdf
1982
James E. Burns, Paul Jackson, Nancy A. Lynch, Michael J. Fischer,
and Gary L. Peterson. Data requirements for implementation of
N-process mutual exclusion using a single shared variable.
Journal of the ACM, 29(1):183--205, January 1982.pdf
Danny Dolev, Michael J. Fischer, Rob Fowler, Nancy A. Lynch, and
H. Raymond Strong. An efficient algorithm for Byzantine agreement
without authentication. Information and Control,
52(3):257--274, March 1982. .pdf
Danny Dolev, Michael J. Fischer, Rob Fowler, Nancy A. Lynch, and
H. Raymond Strong. An efficient Byzantine agreement
without authentication. IBM Research Report RJ3428 (40914),
Computer Science, IBM Research Division, Yorktown Heights, NY, March
22, 1982. .pdf
Richard A. DeMillo, Nancy A. Lynch, and Michael J. Merritt.
Cryptographic protocols. In Proceedings of the Fourteenth
Annual ACM Symposium on Theory of Computing, pages 383--400, San
Francisco, California, May 1982. pdf
Michael J. Fischer, Nancy D. Griffeth, and Nancy A. Lynch. Global
states of a distributed system. IEEE Transactions on Software
Engineering, SE-8(3):198--202, May 1982..pdf
Michael J. Fischer and Nancy A. Lynch. A lower bound for the time
to assure interactive consistency. Information Processing
Letters, 14(4):183--186, June 1982. .pdf
Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson.
Impossibility of distributed consensus with one faulty process.
Technical Report MIT/LCS/TR-282, Laboratory for Computer Science,
Massachusetts Institute of Technology, Cambridge, MA, 02139, September 1982.
pdf
Nancy Lynch, Michael Fischer, and Rob Fowler. A simple and efficient
Byzantine generals algorithm. In Proceedings of the 2nd
Symposium on Reliability in Distributed Software and Database
Systems, pages 46--52, Pittsburgh, PA, July 1982. .pdf
Nancy Lynch, Michael Fischer, and Rob Fowler. A simple and efficient
Byzantine generals algorithm. Technical Report GIT-ICS-82/02,
School of Information and Computer Science, Georgia Institute of
Technology, February, 1982. pdf
Nancy Lynch. Accessibility of values as a determinant of relative
complexity of algebras. Journal of Computer and System
Sciences, 24(1):101--113, February 1982. pdf
Nancy Lynch. Multilevel atomicity--a correctness criterion for
database concurrency control. Technical Report MIT/LCS/TR-281,
Laboratory for Computer Science, Massachusetts Institute of
Technology, Cambridge, MA, 02139, August 1982. pdf
Nancy A. Lynch. Multilevel atomicity. In
Proceedings of the First ACM SIGACT-SIGMOD Symposium on Principles of
Database Systems, pages 63--69, Los Angeles, CA, March 1982. .pdf
1981
Eshrat Arjomandi, Michael J. Fischer, and Nancy A. Lynch. A
difference in efficiency between synchronous and asynchronous
systems. Technical Report GIT-ICS-81/07, School of Information and
Computer Science, Georgia Institute of Technology, June, 1981. .pdf
Allan Borodin, Michael J. Fischer, David G. Kirkpatrick, Nancy
A. Lynch, and Martin Tompa. A time-space tradeoff for sorting on
non-oblivious machines. Journal of Computer and System
Sciences, 22(3):351--364, June 1981. .pdf
A. Borodin, L. Guibas, N. Lynch, and A. Yao. Efficient
searching using partial ordering. Information Processing
Letters, 12(2):71--75, April 1981. .pdf
Michael J. Fischer, Leonidas Guibas, Nancy D. Griffeth, and Nancy
Lynch. Optimal placement of identical resources in a distributed network. In
Proceedings of the 2nd IEEE International Conference on Distributed Computing
Systems, pages 324--336, April 1981. .pdf
Michael Fischer, Nancy Griffeth, and Nancy Lynch. Global states of a
distributed system. In Proceedings of IEEE Symposium on
Reliability in Distributed Software and Database Systems, pages 33--38,
Pittsburgh, PA, July 1981. .pdf
Nancy Lynch. Multilevel atomicity--a correctness criterion for
database concurrency control. Technical Report GIT-ICS-81/05,
School of Information and Computer Science, Georgia Institute of
Technology, May, 1981. .pdf
Michael Fischer, Nancy Griffeth, and Nancy Lynch. Global states of a
distributed system. Technical Report
GIT-ICS-81/06, School of Information and Computer Science, Georgia
Institute of Technology, June, 1981. .pdf
Michael J. Fischer and Nancy A. Lynch. A lower bound for the time
to assure interactive consistency. Technical Report
GIT-ICS-81/13, School of Information and Computer Science, Georgia
Institute of Technology, September, 1981. .pdf
Nancy A. Lynch. Upper bounds for static resource allocation in a
distributed system. Journal of Computer and System
Sciences, 23(2):254--278, October 1981. .pdf
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 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. A. Lynch and E. K. Blum. Relative complexity of operations on
numeric and bit-string algebras. Mathematical Systems Theory
13, pages 187--207, 1980. .pdf
