December 4, 2024

The section numbers listed here correspond to the writeup.

Section 3

3.1 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. Publisher site

3.2 James E. Burns and Nancy A. Lynch. Bounds on shared memory for mutual exclusion. Information and Computation, 107(2):171--184, December 1993. Publisher site Originally appeared in Jim Burns's thesis, in 1981.

3.3 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. Publisher site

3.4 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. Publisher site

3.5 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. Publisher site

Section 4

4.1 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. Publisher site

4.2 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. Publisher site

4.3 Jennifer Lundelius and Nancy Lynch. An upper and lower bound for clock synchronization. Information and Control, 62(2-3):190--204, August/September 1984. Publisher site

4.4 Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. Consensus in the presence of partial synchrony. Journal of the ACM, 35(2):288--323, April 1988. Publisher site

4.5 Michael J. Fischer, Nancy A. Lynch, and Michael Merritt. Easy impossibility proofs for distributed consensus problems. Distributed Computing, 1(1):26--39, January 1986. Publisher site

4.6 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. Publisher site

4.7 Nancy Lynch and Mark Tuttle. An introduction to Input/Output automata. CWI-Quarterly, 2(3):219--246, September 1989. Centrum voor Wiskunde en Informatica, Amsterdam, The Netherlands. Submitted version .pdf Publisher's version

4.8 Nancy Lynch, Michael Merritt, William Weihl, and Alan Fekete. Atomic Transactions. Morgan Kaufmann series in data management systems. Morgan Kaufmann Publishers, 1993. Publisher site.

Section 5

5.1 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. Publisher site

5.2 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. Publisher site

5.3 Seth Gilbert and Nancy Lynch. Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services. SIGACT News, 33(2):48-51, June 2002. Publisher site

5.4 Nancy Lynch. Distributed Algorithms. Morgan Kaufmann Publishers, San Mateo, CA, 1996. Publisher site ACM Digital Library

Section 6

6.1 Nancy Lynch, Roberto Segala, and Frits Vaandrager. Hybrid I/O Automata. Information and Computation, 185(1):105-157, August 2003. Publisher site

6.2 Dilsun Kaynar, Nancy Lynch, Roberto Segala, and Frits Vaandrager. The Theory of Timed I/O Automata. Synthesis Lectures on Computer Science, Morgan Claypool Publishers, 2010. Second Edition. Publisher site

6.3 Roberto Segala and Nancy Lynch. Probabilistic simulations for probabilistic processes. Nordic Journal of Computing, 2(2):250--273, August 1995. .pdf Also, 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. Publisher site Won the Test of Time Award at 31st International Conference on Concurrency Theory (CONCUR 2020), September 2020.

6.4 Nancy Lynch, Roberto Segala, and Frits Vaandrager. Observing Branching Structure through Probabilistic Contexts. Siam Journal on Computing, 37(4):977-1013, September 2007. Publisher site

6.5 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. Publisher site

6.6 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. Publisher site

Section 7

7.1 Seth Gilbert, Nancy Lynch, and Alex Shvartsman. RAMBO: A Robust, Reconfigurable Atomic Memory Service for Dynamic Networks. Distributed Computing, 23(4):225-272, December 2010. Publisher site Here is a slightly corrected version of the journal version. .pdf

7.2 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. Publisher site

7.3 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. Publisher site

7.4 Fabian Kuhn, Nancy Lynch and Rotem Oshman. Distributed Computation in Dynamic Networks. Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC 2010), Cambridge, MA, pages 513-522, June 2010. Publisher site

7.5 Alejandro Cornejo, Fabian Kuhn, Ruy Ley-Wild, and Nancy Lynch. Keeping Mobile Robot Swarms Connected. In Idit Keidar, editor, Distributed Computing, DISC 2009: 23rd International Symposium on Distributed Computing, Elche/Elx, Spain, September 23-25 2009, volume 5805 of Lecture Notes in Computer Science, pages 496-511, 2009. Springer. Publisher site