, May 2019.
Pooja Vyavahare, Lili Su, and Nitin H. Vaidya. Distributed Learning over Time-Varying Graphs with Adversarial Agents. 22nd International Conference on Information Fusion (Fusion 2019), IEEE, Ottawa, Canada, July 2019. Also, ArXiv:1901.01943, Jan. 2019.
Pooja Vyavahare, Lili Su, and Nitin H. Vaidya. Distributed Learning with Adversarial Agents Under Relaxed Network Condition. ArXiv:1901.01943, January, 2019.
Brabeeba Wang and Nancy Lynch. Brief Announcement: Integrating Temporal Information to Spatial Information in a Neural Circuit. 33rd International Symposium on Distributed Computing (DISC), Budapest, Hungary, October 2019. .pdf
Mien Brabeeba Wang and Nancy Lynch. Integrating Temporal Information to Spatial Information in a Neural Circuit. 7th Workshop on Biological Distributed Algorithms (BDA), Toronto, Canada, July 2019. .pdf
Brabeeba Wang and Nancy Lynch.
Integrating Temporal Information to Spatial Information in a Neural Circuit. arXiv:1903.01217v2, July 2019.
2018
Petra Berenbrink, Tom Friedetzky, Peter Kling, Frederik Mallmann-Trenn, Lars Nagel, and Chris Wastell. Self-stabilizing Balls & Bins in Batches: The Power of Leaky Bins. Algorithmica, 80(12):3673-3703, December 2018. .pdf
Gregory Bodwin, Michael Dinitz, Merav Parter and Virginia Vassilevska Williams. Optimal Vertex Fault Tolerant Spanners (for fixed stretch). ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), New Orleans, Louisiana, January 2018. .pdf
Ran Canetti, Ling Cheung, Dilsun Kaynar, Moses Liskov, Nancy Lynch, Olivier Pereira, and Roberto Segala. Task-Structured Probabilistic I/O Automata. Journal of Computer and System Sciences, volume 94, pages 63-97, 2018. .pdf
Viveck R. Cadambe, Nicolas C. Nicolaou, Kishori M. Konwar, N. Prakash, Nancy A. Lynch, and Muriel Medard. ARES: Adaptive, Reconfigurable, Erasure coded, Atomic Storage. arXiv:1805.03727v1, 2018.
Vincent Cohen-Addad, Varun Kanade, and Frederik Mallmann-Trenn. Clustering Redemption-Beyond the Impossibility of Kleinberg's Axioms. 32nd Conference on Neural Information Processing Systems (NIPS 2018), Montreal, Canada, December 2018. .pdf
Vincent Cohen-Addad, Varun Kanade, and Frederik Mallmann-Trenn, and Claire Mathieu. Hierarchical Clustering: Objective Functions and Algorithms. ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), New Orleans, Louisiana, January 2018. .pdf
Anna R. Dornhaus, Nancy A. Lynch, Frederik Mallmann-Trenn, Dominik
Pajak, and Tsvetomira Radeva. Self-Stabilizing Task Allocation In Spite of
Noise. 6th Workshop on Biological Distributed Algorithms (BDA), London, UK, July 2018. .pdf
Anna R. Dornhaus, Nancy A. Lynch, Frederik Mallmann-Trenn, Dominik
Pajak, and Tsvetomira Radeva. Self-Stabilizing Task Allocation In Spite of
Noise. arxiv 1805.03691v2, May 2018.
Seth Gilbert, Nancy Lynch, Calvin Newport, and Dominik Pajak. On Simple
Back-Off in Unreliable Radio Networks. The 22nd International
Conference on Principles of Distributed Systems (OPODIS 2018), Hong
Kong, December 2018. .pdf Best Paper Award.
Seth Gilbert, Nancy A. Lynch, Calvin Newport, and Dominik Pajak. Brief Announcement: On Simple Back-Off in Unreliable Radio Networks. 32nd International Symposium on Distributed Computing (DISC 2018), New Orleans, LA, October 2018. .pdf
Seth Gilbert, Nancy A. Lynch, Calvin Newport, and Dominik Pajak. On Simple Back-Off in Unreliable Radio Networks. arxiv 1803.02216v1, March 2018.
Seth Gilbert, Nancy A. Lynch, Calvin Newport, and Dominik Pajak. On Simple Back-Off in Unreliable Radio Networks. arxiv 1803.02216v2, May 2018.
Seth Gilbert, Nancy A. Lynch, Calvin Newport, and Dominik Pajak. On Simple Back-Off in Unreliable Radio Networks. arxiv 1803.02216v3, December 2018.
Bernhard Haeupler, Jeet Mohapatra, and Hsin-Hao Su.
Optimal Gossip Algorithms for Exact and Approximate Quantile Computations. In Proceedings of Principles of Distributed Computing (PODC 2018), Egham, United Kingdom, pages 179-188, July 2018. .pdf
Marek Klonowski and Dominik Pajak. Brief Announcement: Broadcast in
radio networks, time vs. energy tradeoffs. Proceedings of Principles of Distributed Computing (PODC 2018), Egham, United Kingdom, July 2018. .pdf
Marek Klonowski and Dominik Pajak. Broadcast in
radio networks, time vs. energy tradeoffs. arxiv 1711.04149v2, May 2018.
Kishori Konwar, Wyatt Lloyd, Haonan Lu, and Nancy Lynch. The SNOW Theorem Revisited. arXiv 1811.10577v1, November 2018.
Nancy Lynch and Cameron Musco. A Basic Compositional Model for Spiking Neural Networks. arXiv:1808.03884v1, August 2018.
Frederik Mallmann-Trenn, Cameron Musco, and Christopher Musco. Eigenvector Computation and Community Detection in Asynchronous Gossip Models. In Proceedings of the the 45th International Colloquium on Automata, Languages, and Programming (ICALP), Prague, Czech Republic, July 2018. .pdf
Frederik Mallmann-Trenn, Cameron Musco, and Christopher Musco. Eigenvector Computation and Community Detection in Asynchronous Gossip Models. arXiv:1804.08548, 2018.
Evangelia Anna Markatou. The Loudest one Wins: Efficient Communication in Theoretical Wireless Networks. Master of Engineering in Computer Science and Electrical Engineering thesis, Massachusetts Institute of Technology, Cambridge, MA, June 2018. .pdf
Cameron Musco. The Power of Randomized Algorithms: From Numerical Linear Algebra to Biological Systems. Ph.D thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA 02139, June 2018. .pdf
Cameron Musco, Christopher Musco, and Charalampos E. Tsourakakis. Minimizing Polarization and Disagreement in Social Networks. The Web Conference (WWW), Lyon, France, 2018. .pdf
Cameron Musco, Christopher Musco and Aaron Sidford. Stability of the Lanczos Method for Matrix Function Approximation. ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), New Orleans, Louisiana, January 2018. .pdf
Cameron Musco, Praneeth Netrapalli, Aaron Sidford, Shashanka Ubaru, David P. Woodruff. Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness. Innovations in Theoretical Computer Science (ITCS), Cambridge, MA, January 2018. .pdf
Cameron Musco, Praneeth Netrapalli, Aaron Sidford, Shashanka Ubaru, David P. Woodruff. Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness. arxiv:1704.04163, 2018.
Lili Su. On the Convergence Rate of Average Consensus and Distributed Optimization over Unreliable Networks. Proceedings of the 52nd Asilomar Conference on Signals, Systems and Computers (ACSSC 2018), Pacific Grove, CA, October 2018. .pdf
Lili Su and Shahin Shahrampour. Finite-time Guarantees for Byzantine-resilient Distributed State Estimation with Noisy Measurements. arxiv 1810.10086, October 2018.
Lili Su and Jiaming Xu. Securing Distributed Machine Learning in High Dimensions. arxiv 1804.10140v2, June 2018.
Lili Su and Jiaming Xu. Securing Distributed Machine Learning in High Dimensions. arxiv 1804.10140v1, April 2018.
Lili Su, Martin Zubeldia, and Nancy Lynch. Collaboratively Learning the Best Option on Graphs, Using Bounded Local Memory. arXiv:1811.03968v3, December 2018.
Lili Su, Martin Zubeldia, and Nancy Lynch. Collaboratively Learning the Best Option, Using Bounded Memory. arXiv:1802.08159v2, March 2018.
Lili Su, Martin Zubeldia, and Nancy Lynch. Collaboratively Learning the Best Option, Using Bounded Memory. arXiv:1802.08159v3, November 2018.
2017
Haim Avron, Michael Kapralov, Cameron Musco, Christopher Musco, Ameya Velingker and Amir Zandieh. Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees. International Conference on Machine Learning (ICML), Sydney, Australia, July 2017. .pdf
Reuven Bar-Yehuda, Keren Censor-Hillel, Mohsen Ghaffari, and Gregory Schwartzman. Distributed Approximation of Maximum Independent Set and Maximum Matching. ACM Symposium on the Principles of Distributed Computing (PODC 2017), Washington, DC, July 2017. .pdf
Greg Bodwin, Fabrizio Grandoni, Merav Parter and Virginia Vassilevska Williams. Preserving Distances in Very Faulty Graphs. International Colloquium on Automata, Languages, and Programming (ICALP), Track A, University of Warsaw, July 2017. .pdf
Gregory Bodwin, Michael Dinitz, Merav Parter and Virginia Vassilevska Williams. Optimal Vertex Fault Tolerant Spanners (for fixed stretch). arXiv 1710.03164, 2017.
Viveck R. Cadambe, Nancy Lynch, Muriel Medard and Peter Musial. A Coded Shared Atomic Memory Algorithm for Message Passing Architectures. Distributed Computing, 30(1):49-73, February 2017. .pdf
Keren Censor-Hillel, Merav Parter and Gregory Schwartzman. Derandomizing Local Distributed Algorithms under Bandwidth Restrictions. 31st International Symposium on Distributed Computing (DISC 2017), Vienna Austria, October 2017. arXiv: 1608.01689
Michael Cohen, Cameron Musco, and Christopher Musco. Input Sparsity Time Low-Rank Approximation via Ridge Leverage Score Sampling. Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, Barcelona, Spain (SODA'17). See arXiv:1511.07263.
Vincent Cohen-Addad, Varun Kanade, and Frederik Mallmann-Trenn. Hierarchical Clustering Beyond the Worst-Case. 31th Annual Conference on Neural Information Processing Systems (NIPS), Long Beach, California, December 2017. .pdf
Mohsen Ghaffari and Merav Parter. Near-Optimal Distributed DFS in Planar Graphs. 31st International Symposium on Distributed Computing (DISC 2017), Vienna Austria, October 2017. .pdf
Mohsen Ghaffari. Improved Distributed Algorithms for Fundamental Graph Problems. Ph.D. Thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA, February 2017. .pdf
Mohsen Ghaffari and Hsin-Hao Su. Distributed Degree Splitting, Edge Coloring, and Orientations. ACM-SIAM Symposium on Discrete Algorithms (SODA 2017) Barcelona, Spain, January 2017. .pdf Also, arXiv:1608.03220
Mohsen Ghaffari, David Karger, and Debmalya Panigrahi. Random Contractions and Sampling for Hypergraph and Hedge Connectivity. ACM-SIAM Symposium on Discrete Algorithms (SODA 2017) Barcelona, Spain, January 2017. .pdf
Mohsen Ghaffari. Distributed MIS via All-to-All Communication. ACM Symposium on the Principles of Distributed Computing (PODC 2017), Washington, DC, July 2017. .pdf
Mohsen Ghaffari, Fabian Kuhn, and Hsin-Hao Su. Distributed MST and Routing in Almost Mixing Time. ACM Symposium on the Principles of Distributed Computing (PODC 2017), Washington, DC, July 2017. .pdf
Ofer Grossman and Merav Parter. Improved Deterministic Distributed Construction of Spanners. 31st International Symposium on Distributed Computing (DISC 2017), Vienna Austria, October 2017. arXiv: 1708.01011
Bernhard Haeupler, Jeet Mohapatra, and Hsin-Hao Su.
Optimal Gossip Algorithms for Exact and Approximate Quantile Computations. CoRR abs/1711.09258, 2017. arxiv.1711.09258
Magnus Halldorsson, Fabian Kuhn, Nancy Lynch, and Calvin Newport.
An Efficient Communication Abstraction for Dense Wireless Networks.
31st International Symposium on Distributed Computing (DISC 2017), Vienna Austria, October, 2017. .pdf
Magnus Halldorsson, Stephan Holzer, Pradipta Mitra and Roger Wattenhofer. The Power of Non-Uniform Wireless Power. SIAM J. Comput., 46(3):1062-1086, June 2017. .pdf
Magnus Halldorsson, Stephan Holzer and Evangelia Anna Markatou. Leader Election in SINR Model with Arbitrary Power Control. 24th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2017), Porquerolles, France, June 2017. Best Paper Award. .pdf
Magnus Halldorsson, Stephan Holzer and Evangelia Anna Markatou. Brief Announcement: Leader Election in SINR Model with Arbitrary Power Control. ACM Symposium on the Principles of Distributed Computing (PODC 2017), Washington, DC, July 2017. .pdf
Stephan Holzer and Nancy Lynch. Beeping a Maximal Independent Set Fast. arXiv:1704.07133, 2017. Slightly revised version, May 8th, 2017 .pdf
Stephan Holzer, Thomas Locher, Yvonne Anne Pignolet and Roger Wattenhofer. Deterministic Multi-Channel Information Exchange. Journal of Computer and System Science, volume 87, pages 84-103, August 2017. ScienceDirect
Marek Klonowski and Dominik Pajak. Broadcast in
radio networks, time vs. energy tradeoffs. arxiv 1711.04149, November 2017.
Kishori M Konwar, N. Prakash, Muriel Medard and Nancy Lynch. A Layered Architecture for Erasure-Coded Consistent Distributed Storage. ACM Symposium on the Principles of Distributed Computing (PODC 2017), Washington, DC, July 2017. .pdf
Christoph Lenzen, Nancy Lynch, Calvin Newport, and Tsvetomira Radeva. Searching without Communicating: Tradeoffs Between Performance and Selection Complexity. Distributed Computing, 30(3):169-191, 2017. .pdf
Nancy Lynch, Cameron Musco, and Merav Parter. Neuro-RAM Unit with Applications to Similarity Testing and Compression in Spiking Neural Networks. 31st International Symposium on Distributed Computing (DISC 2017), Vienna Austria, October 2017. arXiv:1706.01382
Nancy Lynch, Cameron Musco, and Merav Parter. Neuro-RAM Unit with Applications to Similarity Testing and Compression in Spiking Neural Networks. arXiv:1706.01382v2, August 2017.
Nancy Lynch, Cameron Musco, and Merav Parter. Computational Tradeoffs in Biological Neural Networks: Self-Stabilizing Winner-Take-All Networks. Innovations in Theoretical Computer Science (ITCS'17), Berkeley, CA, January 2017. .pdf Also, arXiv 1610.02084.
Cameron Musco, Christopher Musco and Aaron Sidford. Stability of the Lanczos Method for Matrix Function Approximation. arXiv:1708.07788, 2017.
Cameron Musco, Christopher Musco, and Charalampos E. Tsourakakis. Minimizing Polarization and Disagreement in Social Networks. arxiv 1712.09948, 2017.
Cameron Musco, Hsin-Hao Su, and Nancy A. Lynch. Ant-Inspired Density Estimation via Random Walks. Proceedings of the National Academy of Sciences, 114(40):10534-10541, October, 2017. Final submission version .pdf PNAS version.
Nancy Lynch, Cameron Musco, and Merav Parter. Spiking Neural Networks: An Algorithmic Perspective. 5th Workshop on Biological Distributed Algorithms (BDA 2017), Washington, DC, July 2017. .pdf
Cameron Musco and Christopher Musco. Recursive Sampling for the Nystrom Method. 31th Annual Conference on Neural Information Processing Systems (NIPS), Long Beach, California, December 2017. .pdf Also, arXiv:1605.07583
Cameron Musco and David P. Woodruff. Is Input Sparsity Time Possible for Kernel Low-Rank Approximation? 31th Annual Conference on Neural Information Processing Systems (NIPS), Long Beach, California, December 2017. .pdf
Cameron Musco and David P. Woodruff. Sublinear Time Low-Rank Approximation of Positive Semidefinite Matrices. 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2017), Berkeley, CA, October 2017. .pdf Also, ArXiv:1704.03371.
Cameron Musco and David P. Woodruff. Sublinear Time Low-Rank Approximation of Positive Semidefinite Matrices. ArXiv:1704.03371.
Tsvetomira Radeva. A Symbiotic Perspective on Distributed Algorithms
and Social Insects. Ph.D Thesis, Electrial Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA 02139, June 2017. .pdf
Tsvetomira Radeva, Anna Dornhaus, Nancy Lynch, Radhika Nagpal, and
Hsin-Hao Su. Costs of task allocation with local feedback: effects of colony size and extra workers in social insects and other multi-agent systems. PLOS Computational Biology, 13(12):e1005904, December 2017. .pdf. Also,
https://doi.org/10.1371/journal.pcbi.1005904
Tsvetomira Radeva, Cameron Musco, and Nancy Lynch. New Perspectives on Algorithmic Robustness Inspired by Ant Colony House-Hunting. 5th Workshop on Biological Distributed Algorithms (BDA 2017), Washington, DC, July 2017. .pdf
Hsin-Hao Su, Lili Su, Anna Dornhaus, and Nancy Lynch. Ant-Inspired Dynamic Task Allocation via Gossiping. In Paul G. Spirakis, Philippas Tsigas, 19th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2017), Boston, MA, November 2017, volume 10616 of Lecture Notes in Computer Science, pages 157-171, Springer 2017. .pdf
Hsin-Hao Su, Lili Su, Anna Dornhaus, and Nancy Lynch. Ant-Inspired Dynamic Task Allocation via Gossiping. 5th Workshop on Biological Distributed Algorithms (BDA 2017), Washington, DC, July 2017. (Short-version) .pdf
2016
James Aspnes, Hagit Attiya, Keren Censor-Hillel, and Danny
Hendler. Lower Bounds for Restricted-Use Objects. SIAM Journal on Computing, 45(3):734-762, 2016.
Earlier version in
Proceedings of the 24th Symposium on Parallelism in Algorithms and
Architectures (SPAA), Pittsburgh, PA, pages 172-181, June 2012. .pdf ACM Copyright
Paul C. Attie and Nancy A. Lynch. Dynamic Input/Output Automata: a Formal and Compositional Model for Dynamic Systems. Information and Computation, volume 249, pages 28-75, August 2016. Accepted.pdf ElsevierAcceptedManuscript.pdf. Also, Arxiv 1604.06030.
Earlier version in Technical Report MIT-CSAIL-TR-2013-015, Computer Science and Artificial Intelligence Laboratory, Cambridge, MA 02139, July 2013. .pdf
Viveck R. Cadambe, Zhiying Wang, and Nancy Lynch. Information-Theoretic Lower Bounds on the Storage Cost of Shared Memory Emulation. Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), Chicago, Illinois, pages 305-313, July 2016. .pdf Also, arXiv:1605.06844v2, May 2016.
Viveck R. Cadambe, Zhiying Wang, and Nancy Lynch. Information-Theoretic Lower Bounds on the Storage Cost of Shared Memory Emulation. arXiv:1605.06844v2, May 2016.
Michael B. Cohen, Cameron Musco, and Jakub Pachocki. Online Row Sampling. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) 2016, Paris, France, September 2016. See http://arxiv.org/abs/1604.05448
Benjamin Dissler, Stephan Holzer and Roger Wattenhofer. Distributed Local Multi-Aggregation and Centrality Approximation. Preprint arXiv:1605.06882. .pdf
Roy Frostig, Cameron Musco, Christopher Musco, and Aaron Sidford. Principal Component Projection Without Principal Component Analysis. International Conference on Machine Learning (ICML 2016), New York, NY, June 2016. See http://arxiv.org/abs/1602.06872.
Mohsen Ghaffari and Hsin-Hao Su. Distributed Degree Splitting, Edge Coloring, and Orientations. arXiv:1608.03220, 2016.
Mohsen Ghaffari and Calvin Newport. How to Discreetly Spread a Rumor in a Crowd. 30th International Symposium on Distributed Computing (DISC 2016), Paris, France, September 2016. .pdf
Mohsen Ghaffari. An Improved Distributed Algorithm for Maximal Independent Set. ACM-SIAM Symposium on Discrete Algorithms (SODA 2016), Arlington, VA, pages 270-277, January 2016. Best Paper Award and Best Student Paper Award. .pdf. Also, .arXiv:1506.05093v2
Mohsen Ghaffari. An Improved Distributed Algorithm for Maximal Independent Set. .arXiv:1506.05093v2
Mohsen Ghaffari and Bernhard Haeupler. Distributed Algorithms for Planar Networks I: Planar Embedding. Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), Chicago, Illinois, pages 29-38, July 2016. .pdf
Mohsen Ghaffari and Bernhard Haeupler. Distributed Algorithms for Planar Networks II: Low-Congestion Shortcuts, MST, and Min-Cut. ACM-SIAM Symposium on Discrete Algorithms (SODA 2016), Arlington, VA, pages 202-219, January 2016. .pdf
Mohsen Ghaffari and Calvin Newport. Leader Election in Unreliable Radio Networks. International Colloquium on Automata, Languages, and Programming (ICALP), Rome Italy, July 2016. .pdf
Mohsen Ghaffari and Merav Parter. A Polylogarithmic Gossip Algorithm for Plurality Consensus. Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), Chicago, Illinois, pages 117-126, July 2016. .pdf
Mohsen Ghaffari and Merav Parter. MST in Log-Star Rounds of Congested Clique. Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), Chicago, Illinois, pages 19-28, July 2016. .pdf
Mohsen Ghaffari and Merav Parter. Near-Optimal Distributed
Algorithms for Fault-Tolerant Tree Structures. ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), Asilomar State Beach, California, pages 387-396, July 2016. .pdf
David G. Harris, Johannes Schneider, and Hsin-Hao Su. Distributed (A+1)-coloring in Sublogarithmic Rounds. Proceedings of the 48th Annual Symposium on the Theory of Computing (STOC 2016), Cambridge, MA, pages 465-478, June 2016. .pdf Also, http://arxiv.org/pdf/1603.01486v1.pdf
David G. Harris, Johannes Schneider, and Hsin-Hao Su. Distributed (A+1)-coloring in Sublogarithmic Rounds. http://arxiv.org/pdf/1603.01486v1.pdf
Elad Hazan, Daniel Garber, Chi Jin, Sham M. Kakade, Cameron Musco, Praneeth Netrapalli, and Aaron Sidford. Faster Eigenvector Computation via Shift-and-Invert Preconditioning. International Conference on Machine Learning (ICML 2016), New York, NY, June 2016. .pdf
Stephan Holzer and Nancy Lynch. Brief Announcement - Beeping a Maximal Independent Set Fast. 30th International Symposium on Distributed Computing (DISC 2016), Paris, France, September 2016. .pdf
Erez Kantor, Zvi Lotker, Merav Parter, and David Peleg. Fault Tolerant Logical Network Structures. Bulletin of the EATCS, 118, 2016.
Erez Kantor and David Peleg. Efficient $k$-shot Broadcasting in Radio Networks. Journal of Discrete Applied Mathematics, 202:79-94, 2016. .pdf
Kishori Konwar, Nancy Lynch, Muriel Medard and Prakash Narayana Moorthy.
RADON: Repairable Atomic Data Object in Networks. Proceedings of the 20th International Conference on Principles of Distributed Systems (OPODIS 2016), Madrid, Spain, December 2016. .pdf Also, arXiv:1605.05717v2, November 2016.
Kishori Konwar, Nancy Lynch, Muriel Medard and Prakash Narayana Moorthy.
RADON: Repairable Atomic Data Object in Networks. arXiv:1605.05717v2, November 2016.
Kishori Konwar, Nancy Lynch, Muriel Medard and Prakash Narayana Moorthy.
RADON: Repairable Atomic Data Object in Networks. arXiv:1605.05717v1, May 2016.
Kishori M Konwar, N. Prakash, Erez Kantor, Muriel Medard, Nancy Lynch, and Alexander A. Schwarzmann. Storage-Optimized Data-Atomic Algorithms for Handling Erasures and Errors in Distributed Storage Systems. 30th IEEE International Parallel & Distributed Processing Symposium (IPDPS), pages 720-729, May 2016. .pdf Also, arXiv:1605.01748.
Kishori M Konwar, N. Prakash, Erez Kantor, Muriel Medard, Nancy Lynch, and Alexander A. Schwarzmann. Storage-Optimized Data-Atomic Algorithms for Handling Erasures and Errors in Distributed Storage Systems. arXiv:1605.01748.
Christoph Lenzen and Roger Wattenhofer.
Tight Bounds for Parallel Randomized Load Balancing. Distributed Computing, 29(2):127-142, 2016. .pdf
Nancy Lynch, Cameron Musco, and Merav Parter. Computational Tradeoffs in Biological Neural Networks: Self-Stabilizing Winner-Take-All Networks. arXiv 1610.02084, October 2016.
Cameron Musco, Hsin-Hao Su, and Nancy Lynch. Ant-Inspired Density Estimation via Random Walks. Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), Chicago, Illinois, pages 469-478, July 2016. .pdf Also, arxiv:1603.02981v1, March 2016.
Cameron Musco, Hsin-Hao Su, and Nancy Lynch. Ant-Inspired Density Estimation via Random Walks. arxiv:1603.02981v1, March 2016.
Cameron Musco, Hsin-Hao Su, and Nancy Lynch. Ant-Inspired Density Estimation via Random Walks (Extended Abstract). 4th Workshop on Biological Distributed Algorithms, Chicago, IL, July 2016.
.pdf
Cameron Musco and Christopher Musco. Recursive Sampling for the Nystrom Method. arXiv:1605.07583, May 2016.
2015
James Aspnes, Hagit Attiya, Keren Censor-Hillel, and Faith
Ellen. Limited-use atomic snapshots with polylogarithmic step complexity. Journal of the ACM, 62(1), February 2015.
.pdf
Pierre Bertrand and Christoph Lenzen. The 1-2-3-Toolkit for Building Your Own Balls-into-Bins Algorithm. Meeting on Algorithm Engineering and Experiments (ALENEX), San Diego, CA, pages 44-54, January 2015. .pdf
Keren Censor-Hillel, Erez Kantor, Nancy Lynch and Merav Parter. Computing in Additive Networks with Bounded-Information Codes. In Yoram Moses, editor, Distributed Computing: 29th International Symposium (DISC 2015), Tokyo Japan, October 2015, volume 9363 of Lecture Notes in Computer Science, pages 405-519, 2015. Springer. .pdf Also, arXiv:1508.03660, August 2015.
Keren Censor-Hillel, Erez Kantor, Nancy Lynch and Merav Parter. Computing in Additive Networks with Bounded-Information Codes. arXiv:1508.03660, August 2015.
Keren Censor-Hillel, Bernhard Haeupler, Nancy Lynch, and Muriel Medard. Bounded-Contention Coding for the Additive Network Model. Distributed Computing, 28(5):297-308, 2015. .pdf Earlier version appeared as title "Bounded-Contention Coding for Wireless Networks in the in High SNR Regime" in Marcos K. Aguilera, editor, Distributed Computing: Proceedings of the 26th International Symposium (DISC 2012), Salvador, Brazil, October 2012,
volume 7611 of Lecture Notes in Computer Science, pages 91-105, 2012. Springer. .pdf ArXiv submission, available at arxiv:1208.6125, and MIT Technical Report MIT-CSAIL-TR-2012-026, Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA 02139, August 2012. .pdf
Keren Censor-Hillel, Mohsen Ghaffari, George Giakkoupis, Bernhard Haeupler, and Fabian Kuhn.
Tight Bounds on Vertex Connectivity under Vertex Sampling.
ACM-SIAM Symposium on Discrete Algorithms (SODA), San Diego, CA, pages 2006-2018, January 2015. .pdf
Michael B. Cohen, Sam Elder, Cameron Musco, Christopher Musco, and Madalina Persu. Dimensionality Reduction for k-Means Clustering and Low Rank Approximation. Proceedings of the 47th Annual Symposium on the Theory of Computing (STOC 2015), Portland, OR, June 2015. .pdf
Michael B. Cohen, Yin Tat Lee, Cameron Musco, Christopher Musco, Richard Peng, and Aaron Sidford. Uniform Sampling For Matrix Approximation.
6th Innovations in Theoretical Computer Science (ITCS), Rehovot, Israel, pages 181-190, January 2015.
arxiv 1408.5099
Anna Dornhaus, Nancy Lynch, Tsvetomira Radeva, and Hsin-Hao Su. Brief Announcement: A Distributed Task Allocation in Ant Colonies. 29th International Symposium on Distributed Computing (DISC 2015), Tokyo, Japan, October 2015. .pdf
Mohsen Ghaffari, Cameron Musco, Tsvetomira Radeva, Nancy Lynch.
Distributed House-Hunting in Ant Colonies. ACM Symposium on Principles of Distributed Computing (PODC 2015), Donostia-San Sebastian, Spain, pages 57-66, July 2015. .pdf Also, arxiv:1505.03799, May 2015.
Mohsen Ghaffari, Cameron Musco, Tsvetomira Radeva, Nancy Lynch.
Distributed House-Hunting in Ant Colonies. arxiv:1505.03799, May 2015.
Mohsen Ghaffari. Near-Optimal Scheduling of Distributed Algorithms. ACM Symposium on Principles of Distributed Computing (PODC 2015), Donostia-San Sebastian, Spain, pages 3-12, July 2015. Best Student Paper Award at PODC'15.
.pdf
Mohsen Ghaffari, Andreas Karrenbauer, Fabian Kuhn, and Christoph Lenzen. Near-Optimal Distributed Maximum Flow. ACM Symposium on Principles of Distributed Computing (PODC 2015), Donostia-San Sebastian, Spain, pages 81-90, July 2015. .pdf
Mohsen Ghaffari and Rajan Udwani. Brief Announcement: Distributed Single-Source Reachability. ACM Symposium on Principles of Distributed Computing (PODC 2015), Donostia-San Sebastian, Spain, pages 163-165, July 2015. .pdf
Magnus Halldorsson, Stephan Holzer and Nancy Lynch. A Local Broadcast Layer for the SINR Network Model. ACM Symposium on Principles of Distributed Computing (PODC 2015), Donostia-San Sebastian, Spain, pages 129-138, July 2015. .pdf. Also, arxiv:1505.04514, May 2015.
Magnus Halldorsson, Stephan Holzer and Nancy Lynch. A Local Broadcast Layer for the SINR Network Model. arxiv:1505.04514, May 2015.
Stephan Holzer and Nathan Pinsker. Approximation of Distances and Shortest Paths in the Broadcast Congest Clique. 19th International Conference on Principles of Distributed Systems (OPODIS), Rennes, France, December 2015. .pdf Also, arXiv:1412.3445v2.
Stephan Holzer and Nathan Pinsker. Approximation of Distances and Shortest Paths in the Broadcast Congest Clique. arXiv:1412.3445v2.
Erez Kantor, Zvi Lotker, Merav Parter and David Peleg. Nonuniform SINR+Voronoi Diagrams are Effectively Uniform. In Yoram Moses, editor, Distributed Computing: 29th International Symposium (DISC 2015), Tokyo Japan, October 2015, volume 9363 of Lecture Notes in Computer Science, pages 588-601, 2015. Springer. .pdf
Erez Kantor, Zvi Lotker, Merav Parter and David Peleg. The Topology of Wireless Communication. Journal of the ACM, 62(5):37, 2015. .pdf
Erez Kantor, Zvi Lotker, Merav Parter and David Peleg. The Minimum Principle of SINR: A Useful Discretization Tool for Wireless Communication. 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2015), Berkeley, CA, pages 330-349, October 2015. .pdf
Erez Kantor and Shay Kutten. Optimal competitiveness for the Rectilinear Steiner Arborescence problem. In Magnus M. Halldorsson, Kazuo Iwama, Naoki Kobayashi, and Bettina Speckmann, editors, Automata, Languages, and Programming - 42nd International Colloquium (ICALP 2015) Part II, Kyoto, Japan, July 2015 volume 9135 of Lecture Notes in Computer Science, pages 675-687, 2015. Springer. .pdf Also, ArXiv: 1504.08265.
Erez Kantor and Shay Kutten. Optimal competitiveness for the Rectilinear Steiner Arborescence problem. ArXiv: 1504.08265.
Majid Khabbazian. Near-optimal multi-version codes. In Proceedings of the 53rd Annual Allerton Conference on Communication, Control and Computing, October 2015. .pdf
Christoph Lenzen, Philipp Sommer, and Roger Wattenhofer. PulseSync: An Efficient and Scalable Clock Synchronization Protocol. IEEE/ACM Transactions on Networking, 23(3):717-727, June 2015. .pdf
Nancy Lynch and Calvin Newport. A (Truly) Local Broadcast Layer for Unreliable Radio Networks.
ACM Symposium on Principles of Distributed Computing (PODC 2015), Donostia-San Sebastian, Spain, pages 109-118, July 2015. .pdf
Nancy Lynch and Calvin Newport. A (Truly) Local Broadcast Layer for Unreliable Radio Networks. Technical Report MIT-CSAIL-TR-016, Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA 02139, May 2015. .pdf
Nancy Lynch and Srikanth Sastry. Consensus using Asynchronous Failure Detectors. Technical Report MIT-CSAIL-TR-2015-006, Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA, 02139, March, 2015 .pdf
and arxiv:1502.02538v2, February 2015.
Nancy Lynch and Srikanth Sastry. Consensus using Asynchronous Failure Detectors. arxiv:1502.02538v2, February 2015.
Cameron Musco. Dimensionality Reduction for k-Means Clustering. Masters thesis, Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA, September 2015..pdf
Cameron Musco and Christopher Musco. Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decomposition. 29th Annual Conference on Neural Information Processing Systems (NIPS), Montreal, Canada, December 2015. arXiv:1504.05477.
Casey O'Brien. Solving ANTS with Loneliness Detection and Constant Memory. Masters of Engineering, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA 02139, September 2015. .pdf Simulation of the Algorithm
Zhiying Wang and Viveck R. Cadambe. Multi-Version Coding in Distributed Storage. arXiv:1506.00684v1 June 2015.
Zhiying Wang and Viveck Cadambe. Multi-Version Coding - An Information Theoretic Perspective of Consistent Distributed Storage arXiv:1506.00684v2, October 2015.
2014
Dan Alistarh, James Aspnes, Keren Censor-Hillel, Seth Gilbert, and Rachid Guerraoui. Tight bounds for asynchronous renaming. Journal of the ACM, 61(3):18.1-18.52, May 2014. .pdf
Noga Alon, Mohsen Ghaffari, Bernhard Haeupler, and Majid Khabbazian. Broadcast throughput in Radio Networks: Routing vs. Network Coding. Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2014), Portland, Oregon, pages 1831-1843, January 2014. .pdf
Pierre Bertrand and Christoph Lenzen. Brief Announcement: The 1-2-3-Toolkit for Building Your Own Balls-into-Bins Algorithm. In Fabian Kuhn, editor, Distributed Computing - 28th Symposium (DISC 2014), Austin, TX, October 2014,, volume 8784 of Lecture Notes in Computer Science, page 557, 2014. Springer. .pdf Also,
arXiv:1407.8433, 2014.
Pierre Bertrand and Christoph Lenzen. The 1-2-3-Toolkit for Building Your Own Balls-into-Bins Algorithm. arXiv:1407.8433, 2014.
Giuseppe Bianchi, Lorenzo Bracciale, Keren Censor-Hillel, Andrea Lincoln, and Muriel Medard. The one-out-of-k retrieval problem and Linear Network Coding. 4th International Castle Meeting on Coding Theory and Applications (ICMCTA 2014), Castle of Palmela, Portugal, September 2014.
.pdf
Viveck R. Cadambe, Nancy Lynch, Muriel Medard, and Peter Musial. A Coded Shared Atomic Memory Algorithm for Message Passing Architectures. The 13th IEEE International Symposium on Network Computing and Applications (IEEE NCA14), Cambridge, MA, pages 253-260, August 2014. Best Paper Award. .pdf
Viveck R. Cadambe, Nancy Lynch, Muriel Medard, and Peter Musial. A Coded Shared Atomic Memory Algorithm for Message Passing Architectures. Technical Report MIT-CSAIL-TR-2014-015, Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA 02139, August 2014. .pdf Also, arXiv:1407.4167.
Viveck R. Cadambe, Nancy Lynch, Muriel Medard, and Peter Musial. A Coded Shared Atomic Memory Algorithm for Message Passing Architectures. arXiv:1407.4167, July 2014.
Keren Censor Hillel, Mohsen Ghaffari, and Fabian Kuhn.
Distributed Connectivity Decomposition. Proceedings of the 33nd Annual ACM Symposium on Principles of Distributed Computing (PODC'14), Paris, France, pages 156-165, July 2014. Best Student Paper Award. .pdf
Keren Censor-Hillel, Seth Gilbert, Fabian Kuhn, Nancy Lynch and Calvin Newport. Structuring Unreliable Radio Networks. Distributed Computing, 27(1):1-19, February 2014. .pdf
Keren Censor-Hillel, Mohsen Ghaffari, Fabian Kuhn. A New Perspective on Vertex Connectivity. Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2014), Portland, Oregon, pages 546-561, January 2014. .pdf
Hyun Chul Chung, Srikanth Sastry, and Jennifer L. Welch. Stabilizing Dining with Failure Locality 1. In Mainak Chatterjee, Jian-Nong Cao, Kishore Kothapalli, Sergio Rajsbaum, editors, Distributed Computing and Networking - 15th International Conference (ICDCN 2014), Coimbatore, India, January 2014, volume 8314 of Lecture Notes in Computer Science, pages 532-537, 2014. Springer. .pdf
Michael B. Cohen, Yin Tat Lee, Cameron Musco, Christopher Musco, Richard Peng, and Aaron Sidford. Uniform Sampling For Matrix Approximation.
arxiv 1408.5099, August 2014.
Alejandro Cornejo, Anna Dornhaus, Nancy Lynch, and Radhika Nagpal. Task Allocation in Ant Colonies. In Fabian Kuhn, editor, Distributed Computing: 28th International Symposium on Distributed Computing (DISC'14), Austin, TX, October 2014, volume 8784 of Lecture Notes in Computer Science, pages 46-60, 2014. Springer. .pdf
Danny Dolev, Matthias Fuegger, Christoph Lenzen, and Ulrich
Schmid. Fault-tolerant Algorithms for Tick-Generation in
Asynchronous Logic: Robust Pulse Generation. Journal of the ACM, 61(5):860-900, August 2014. .pdf
Danny Dolev, Matthias Fuegger, Christoph Lenzen, Markus Posch, Ulrich Schmid,
and Andreas Steininger. Rigorously Modeling Self-Stabilizing Fault-Tolerant Circuits: An Ultra-Robust Clocking Scheme for Systems-on-Chip. Journal of Computer and System Sciences, 80(4):860-900, 2014. .pdf
Yuval Emek, Stephan Holzer, Roger Wattenhofer. The Power of a Leader in the Stone Age. 2nd Workshop on Biological Distributed Algorithms (BDA'14), Austin, TX, October 2014. .pdf
Mohsen Ghaffari and Bernhard Haeupler.
Optimal Error Rates for Interactive Coding II: Efficiency and List Decoding. IEEE Symposium on Foundations of Computer Science (FOCS), Philadelphia, PA, October 2014. .pdf
Mohsen Ghaffari and Christoph Lenzen. Near-Optimal Distributed Tree Embedding. In Fabian Kuhn, editor, Distributed Computing - 28th International Symposium (DISC'14), Austin, TX, October 2014, volume 8784 of Lecture Notes in Computer Science, pages 197-211, 2014. Springer. .pdf
Mohsen Ghaffari and Bernhard Haeupler. Brief Announcement: Near-Optimal BFS Computation in Radio Networks. Proceedings of the 33nd Annual ACM Symposium on Principles of Distributed Computing (PODC'14), Paris, France, July 2014. .pdf
Mohsen Ghaffari and Bernhard Haeupler, and Madhu Sudan.
Optimal Error Rates for Interactive Coding I: Adaptivity and Other Settings. Proceedings of the 46th Annual Symposium on the Theory of Computing (STOC 2014), New York, NY, pages 794-803, May 31-June 3, 2014. .pdf
Mohsen Ghaffari, Erez Kantor, Nancy Lynch, and Calvin Newport. Multi-Message Broadcast with Abstract MAC Layers and Unreliable Links. Proceedings of the 33nd Annual ACM Symposium on Principles of Distributed Computing (PODC'14), Paris, France, pages 56-65, July 2014. .pdf
Mohsen Ghaffari, Erez Kantor, Nancy A. Lynch and Calvin C. Newport. Multi-Message Broadcasting with Abstract MAC Layers and Unreliable Links. arxiv:1405.1671, May 2014.
Mohsen Ghaffari. Near-Optimal Distributed Approximation of Minimum-Weight Connected Dominating Set. In Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, Elias Koutsoupias, editors, Automata, Languages, and Programming - 41st International Colloquium (ICALP'14), Copenhagen, Denmark, July 2014, volume 8573 of Lecture Notes in Computer Science, pages 483-494, 2014. Springer. Best Student Paper Award. .pdf
Miikka Hilke, Christoph Lenzen and Jukka Suomela. Brief Announcement: Local Approximability of Minimum Dominating Set on Planar Graphs. Proceedings of the 33nd Annual ACM Symposium on Principles of Distributed Computing (PODC'14), Paris, France, July 2014. .pdf
Alexandra Hochuli, Stephan Holzer and Roger Wattenhofer. Efficient Approximation of Minimum Routing Cost Trees. In Magnus M. Halldorsson, editor, Proceedings of the 21st International Colloquium on Structural Information and Communication Complexity (SIROCCO'14), Hida Takayama, Japan, July 2014, volume 8576 of Lecture Notes in Computer Science, pages 121-136, 2014. Springer. .pdf
Stephan Holzer. Distance Computation, Information Dissemination, and Wireless Capacity in Networks. In Roger Wattenhofer, editor, volume 19 in the Series in Distributed Computing, pages 1-247, 2014. Hartung-Gorre. amazon
Stephan Holzer, Sebastian Kohler and Roger Wattenhofer. Brief Announcement: k-Selection and Sorting in the SINR Model. In Fabian Kuhn, editor, Distributed Computing - 28th International Symposium (DISC'14), Austin, TX, October 2014, volume 8784 of Lecture Notes in Computer Science, page 559, 2014. Springer. .pdf
Stephan Holzer and Nathan Pinsker. Approximation of Distances and Shortest Paths in the Broadcast Congest Clique. CoRR abs/1412.3445, December 2014. .pdf
Stephan Holzer, David Peleg, Liam Roditty and Roger Wattenhofer. Brief Announcement: Distributed 3/2-Approximation of the Diameter. In Fabian Kuhn, editor, Distributed Computing - 28th International Symposium (DISC'14), Austin, TX, October 2014, volume 8784 of Lecture Notes in Computer Science, page 562, 2014. Springer. .pdf
Erez Kantor and Shay Kutten. Optimal competitiveness for Symmetric
Rectilinear Steiner Arborescence and related problems. In Javier Esparza and Pierre Fraigniaud and Thore Husfeldt and Elias Koutsoupias, editors, Automata, Languages, and Programming - 41st International Colloquium (ICALP'14), Copenhagen, Denmark, July 2014, volume 8573 of Lecture Notes in Computer Science, pages 520-531, 2014. Springer. .pdf
Michael Kapralov, Yin Tat Lee, Cameron Musco, Christopher Musco, and Aaron Sidford. Single Pass Spectral Sparsification in Dynamic Streams. Proceedings of the 55th Annual Symposium on Foundations of Computer Science (FOCS'14), Philadelphia, PA, October 2014. .pdf
Majid Khabbazian, Dariusz Kowalski, Fabian Kuhn, and Nancy Lynch.
Decomposing Broadcast Algorithms Using Abstract MAC Layers. Ad Hoc Networks, volume 12, pages 219-242, 2014. Elsevier. .pdf
Christoph Lenzen and Boaz Patt-Shamir. Improved Distributed Steiner Forest Construction (Extended Abstract). Proceedings of the 33nd Annual ACM Symposium on Principles of Distributed Computing (PODC'14), Paris, France, pages 262-271, July 2014. .pdf
Christoph Lenzen, Nancy Lynch, Calvin Newport, and Tsvetomira Radeva. Trade-offs between Selection Complexity and Performance when Searching the Plane without Communication. Proceedings of the 33nd Annual ACM Symposium on Principles of Distributed Computing (PODC'14), Paris, France, pages 252-261, July 2014. .pdf
Zhiying Wang, Viveck Cadambe. On multi-version coding for distributed storage. In Proceedings of the 52nd Annual Allerton Conference on Communication, Control and Computing, Monticello, IL, pages 569-575, October, 2014.
.pdf
Zhiying Wang and Viveck Cadambe. Multi-Version Coding in Distributed Storage. Proceedings of 2014 IEEE International Symposium on Information Theory (ISIT), Honolulu, USA, pages 871-875, June, 2014.
.pdf Also, arXiv:1506.00684..
2013
Yehuda Afek, Noga Alon, Ziv Bar-Joseph, Alejandro Cornejo,
Bernhard Haeupler, and Fabian Kuhn. Beeping a Maximal Independent Set. Distributed Computing, 26(4):195-208, 2013. Special issue for DISC 2011. .pdf
Dan Alistarh, Alejandro Cornejo, Mohsen Ghaffari, and Nancy Lynch. Firefly Synchronization with Asynchronous Wake-up. First Workshop on Biological Distributed Algorithms (BDA 2013), Jerusalem, Israel, October 2013. .pdf slides
James Aspnes and Keren Censor-Hillel. Atomic snapshots in expected $O(\log^³n)$ steps using randomized helping. In Yehuda Afek, editor, 27th International Symposium on DIStributed Computing (DISC'13), Jerusalem Israel, October 2013, volume 8205 of Lecture Notes in Computer Science, pages 254-268, 2013. Springer. .pdf
Viveck R. Cadambe, Nancy Lynch, Muriel Medard, and Peter Musial. Coded Emulation of Shared Atomic Memory for Message Passage Architectures. Technical Report MIT-CSAIL-TR-2013-016, Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA 02139. .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-2013-006, Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA, April 2013. This paper was completed in May 2009. .pdf
Israel Cidon, Erez Kantor and Shay Kutten. Prudent Opportunistic Cognitive Radio Access Protocols. In Yehuda Afek, editor, 27th International Symposium on DIStributed Computing (DISC'13), Jerusalem Israel, October 2013,
volume 8205 of Lecture Notes in Computer Science, pages 462-476, 2013. Springer. .pdf
Alejandro Cornejo, Calvin Newport, Subha Gollakota, Jayanthi Rao, and
T.J. Giuli. Prioritized Gossip in Vehicular Networks. Ad-Hoc Networks, 11(1):397-409, 2013. Elsevier. .pdf
Alejandro Cornejo, Nancy Lynch, and Srikanth
Sastry. Asynchronous Failure Detectors. Technical Report,
MIT-CSAIL-TR-2013-025, Computer Science and Artificial Intelligence
Laboratory, Massachusetts Institute of Technology, October 2013. This report supersedes MIT-CSAIL-TR-2013-002 (below). .pdf
Alejandro Cornejo, Nancy Lynch, and Srikanth
Sastry. Asynchronous Failure Detectors. Technical Report,
MIT-CSAIL-TR-2013-002, Computer Science and Artificial Intelligence
Laboratory, Massachusetts Institute of Technology, January 2013. .pdf. This report has been superseded by MIT-CSAIL-TR-2013-025 (above).
Sebastian Daum, Mohsen Ghaffari, Seth Gilbert, Fabian Kuhn and Calvin Newport. Maximal Independent Sets in Multichannel Radio Networks. Proceedings of the 32nd Annual ACM Symposium on Principles of Distributed Computing (PODC'13), Montreal Canada, pages 335-344, July 2013. .pdf
Danny Dolev, Janne H. Korhonen, Christoph Lenzen, Joel Rybicki, and Jukka Suomela. Synchronous Counting and Computational Algorithm Design. In Teruo Higashino and Yoshiaki Katayama and Toshimitsu Masuzawa and Maria Potop-Butucaru and Masafumi Yamashita, editor, 15th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2013), Osaka, Japan, November 2013, volume 8255 of Lecture Notes in Computer Science, pages 237-250, 2013. Springer. .pdf
Danny Dolev and Christoph Lenzen. Brief Announcement: Communication-Efficient Byzantine Consensus Without a Common Clock. In Yehuda Afek, editor, 27th International Symposium on DIStributed Computing (DISC'13), Jerusalem Israel, October 2013, volume 8205 of Lecture Notes in Computer Science, page 569, 2013. Springer. .pdf
Danny Dolev and Christoph Lenzen. Early-Deciding Consensus is Expensive. Proceedings of the 32nd Annual ACM Symposium on Principles of Distributed Computing (PODC'13), Montreal Canada, July 2013. .pdf
Danny Dolev, Matthias Fuegger, Christoph Lenzen, Martin Perner and Ulrich Schmid. HEX: Scaling Honeycombs is Easier than Scaling Clock Trees. Proceedings of the 25th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA'13), Montreal, Canada, July 2013. .pdf
Matthias Fuegger, Markus Hofstaetter, Christoph Lenzen, and Ulrich Schmid.
Efficient Construction of Global Time in SoC's Despite Arbitrary Faults.
Proceedings of the 16th Euromicro Conference on Digital System Design (DSD), Santander, Spain, September 2013. .pdf
Mohsen Ghaffari and Fabian Kuhn. Distributed Minimum Cut Approximation. In Yehuda Afek, editor, 27th International Symposium on DIStributed Computing (DISC'13), Jerusalem, Israel, October 2013, volume 8205 of Lecture Notes in Computer Science, pages 1-15, 2013. Springer. Best Paper Award. .pdf
Mohsen Ghaffari, Nancy Lynch, and Calvin Newport. The Cost of Radio Network Broadcast for Different Models of Unreliable Links. Proceedings of the 32nd Annual ACM Symposium on Principles of Distributed Computing (PODC'13), Montreal Canada, pages 345-354, July 2013. .pdf
Mohsen Ghaffari, Bernhard Haeupler and Majid Khabbazian. Randomized Broadcast in Radio Networks with Collision Detection. Proceedings of the 32nd Annual ACM Symposium on Principles of Distributed Computing (PODC'13), Montreal Canada, pages 325-334, July 2013. .pdf
Mohsen Ghaffari and Bernhard Haeupler. Fast Structuring of Radio Networks for Multi-Message Communications. In Yehuda Afek, editor, 27th International Symposium on DIStributed Computing (DISC'13), Jerusalem Israel, October 2013, volume 8205 of Lecture Notes in Computer Science, pages 492-506, 2013. Springer. .pdf
Mohsen Ghaffari. Bounds on Contention Management in Radio Networks. Masters thesis, Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA, February 2013. .pdf
Mohsen Ghaffari and Bernhard Haeupler. Near Optimal Leader Election in Multi-Hop Radio Networks. Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA'13), New Orleans, Louisiana, pages 748-766, January, 2013. .pdf
Rebecca Ingram, Tsvetomira Radeva, Patrick Shields, Saira Viqar, Jennifer. E. Walter, and Jennifer L. Welch. A Leader Election Algorithm for Dynamic Networks with Causal Clocks. Distributed Computing, 26(2):75-97, 2013.
.pdf
Christoph Lenzen. Optimal Deterministic Routing, and Sorting on the Congested Clique. Proceedings of the 32nd Annual ACM Symposium on Principles of Distributed Computing (PODC'13), Montreal Canada, July 2013. .pdf
Christoph Lenzen and David Peleg. Efficient Distributed Source Detection with Limited Bandwidth. Proceedings of the 32nd Annual ACM Symposium on Principles of Distributed Computing (PODC'13), Montreal Canada, July 2013. .pdf
Christoph Lenzen, Yvonne-Anne Pignolet, and Roger Wattenhofer. Distributed Minimum Dominating Set Approximations in Restricted Families of Graphs.
Distributed Computing, 26(2):119-137, 2013. .pdf
Christoph Lenzen and Boaz Patt-Shamir. Fast Routing Table Construction Using Small Messages. Proceedings of the 45th Symposium on the Theory of Computing (STOC), Palo Alto, California, pages 381-390, June 2013. .pdf
Christoph Lenzen, Martin Perner, Ulrich Schmid, and Martin Sigl. Byzantine Self-Stabilizing Clock Distribution with HEX: Implementation, Simulation, Clock Multiplication. Sixth International Conference on Dependability (DEPEND 2013), Barcelona, Spain, August 2013. .pdf
Christoph Lenzen and Tsvetomira Radeva. The Power of Phermones in Ant Foraging. 1st Workshop on Biological Distributed Algorithms (BDA), Jerusalem, Israel, October 2013. .pdf
Rotem Oshman and Nir Shavit. The SkipTrie: Low-Depth Concurrent Search without Rebalancing. Proceedings of the 32nd Annual ACM Symposium on Principles of Distributed Computing (PODC'13), Montreal Canada, July 2013. .pdf
Tsvetomira Radeva. Properties of Link Reversal Algorithms for Routing and Leader Election. Masters thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA, June 2013. .pdf
Srikanth Sastry, Tsvetomira Radeva, Jianer Chen, and Jennifer L. Welch. Reliable Networks With Unreliable Sensors. Pervasive and Mobile Computing, 9(2):311-323, 2013. .pdf
2012
James Aspnes, Hagit Attiya, and Keren Censor-Hillel. Polylogarithmic
Concurrent Data Structures from Monotone Circuits. Journal of the ACM, 59(1):2:1-2:24, February 2012. .pdf
James Aspnes, Hagit Attiya, Keren Censor-Hillel, and Danny
Hendler. Lower Bounds for Restricted-Use Objects.
Proceedings of the 24th Symposium on Parallelism in Algorithms and
Architectures (SPAA), Pittsburgh, PA, pages 172-181, June 2012. .pdf ACM Copyright
James Aspnes, Hagit Attiya, Keren Censor-Hillel, and Faith
Ellen. Faster than Optimal Snapshots (for a While). Proceedings of the 31st Annual ACM Symposiumon Distributed Computing, Madeira, Portugal, pages 375-384, July, 2012. .pdf
ACM Copyright
Keren Censor-Hillel, Bernhard Haeupler, Nancy Lynch, and Muriel Medard. Bounded-Contention Coding for Wireless Networks in the High SNR Regime. In Marcos K. Aguilera, editor, Distributed Computing: Proceedings of the 26th International Symposium (DISC 2012), Salvador, Brazil, October 2012,
volume 7611 of Lecture Notes in Computer Science, pages 91-105, 2012. Springer. .pdf
Keren Censor-Hillel, Bernhard Haeupler, Nancy Lynch, and Muriel Medard. Bounded-Contention Coding for Wireless Networks in the High SNR Regime. Technical Report MIT-CSAIL-TR-2012-026, Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA 02139, August 2012. .pdf ArXiv submission available at arxiv:1208.6125, August 2012.
Keren Censor-Hillel, Bernhard Haeupler, Nancy Lynch, and Muriel Medard. Bounded-Contention Coding for Wireless Networks in the High SNR Regime. arxiv:1208.6125, August 2012.
Keren Censor-Hillel and Hadas Shachnai. Fast Information Spreading in Graphs with Large Weak Conductance. SIAM Journal on Computing, 41(6): 1451-1465, 2012. .pdf
Keren Censor-Hillel, Bernhard Haeupler, Jonathan A. Kelner, and
Petar Maymounkov. Global Computation in a Poorly Connected World: Fast Rumor Spreading with No Dependence on Conductance.
Proceedings of the 44th ACM Symposium on Theory of Computing (STOC 2012), New York, NY, pages 961-970, May 2012. .pdf ACM Copyright
Alejandro Cornejo. Local Distributed Algorithms for Multi-Robot Systems. Ph.D. thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, September 2012. .pdf
Alejandro Cornejo, Seth Gilbert and Calvin Newport. Aggregation in Dynamic Networks. Proceedings of the 31st Annual ACM Symposium on Distributed Computing, Madeira, Portugal, pages 195-204, July, 2012. .pdf ACM Copyright
Alejandro Cornejo, Andrew J. Lynch, Elizabeth Fudge, Siegfried
Bilstein, Majid Khabbazian, and James McLurkin. Scale-Free
Coordinates for Multi-Robot Systems with Bearing-only Sensors. Workshop on the Algorithmic Foundations of Robotics (WAFR), Cambridge, MA, June 2012. .pdf
Alejandro Cornejo, Nancy Lynch and Srikanth Sastry.
Asynchronous Failure Detectors. Proceedings of the 31st Annual ACM Symposium on Distributed Computing, Madeira, Portugal, pages 243-252, July 2012. .pdf .ACM copyright
Andrew Drucker, Fabian Kuhn and Rotem Oshman. The Communication Complexity of Distributed Task Allocation. Proceedings of the 31st Annual ACM Symposium on Distributed Computing, Madeira, Portugal, pages 67-76, July 2012. .pdf .ACM copyright
Mohsen Ghaffari, Bernhard Haeupler, Nancy Lynch, Calvin Newport.
Bounds on Contention Management in Radio Networks. In Marcos K. Aguilera, editor, Distributed Computing: 26th International Symposium (DISC 2012), Salvador, Brazil, October, 2012, volume 7611 of Lecture Notes in Computer Science, pages 223-237, 2012. Springer. .pdf
Mohsen Ghaffari, Seth Gilbert, Calvin Newport, Henry Tan. Optimal Broadcast in Shared Spectrum Radio Networks. In Roberto Baldoni, Paola Flocchini, and Binoy Ravindran, editors, Proceedings of the 16th International Conference On Principles Of DIstributed Systems (OPODIS'12), Rome, Italy, December 2012, volume 7702 of Lecture Notes in Computer Science,pages 181-195, 2012. Springer.
.pdf
Mohsen Ghaffari, Nancy Lynch, and Srikanth Sastry.
Leader Election Using Loneliness Detection. Distributed Computing, 25(6): 427-450, 2012. Special issue for DISC 2011. .pdf
Seth Gilbert and Nancy A. Lynch. Perspectives on the CAP Theorem. Computer, 45(2):30-35, 2012. IEEE. .pdf
Alexander W. Heinisch, Jean-Christophe Lapeyre, and Peter M.
Musial. There is no 'I' in Consensus. Manuscript, 2012.
Majid Khabbazian, Ian Blake and Vijay Bhargava. Local Broadcast Algorithms in Wireless Ad Hoc Networks: Reducing the Number of Transmissions. IEEE Transactions on Mobile Computing, 11(3):402-413, March 2012. .pdf
Peter M. Musial. From Formal Methods to Executable Code. Technical Report MIT-CSAIL-TR-2012-027, Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA, September 2012. .pdf
Peter M. Musial. From Formal Methods to Executable Code.
Languages for Distributed Algorithms (LADA) Workshop, January
2012. Invited paper. .pdf
Nancy Lynch, Tsvetomira Radeva, and Srikanth Sastry. Asynchronous Leader
Election and MIS Using Abstract MAC Layer. Proceedings of FOMC 2012 (8th ACM International Workshop on the Foundations of Mobile Computing), Madeira, Portugal, page 3, July 2012. .pdf ACM Copyright
Rotem Oshman. Distributed Computation in Wireless and Dynamic Networks. Ph.D. thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA 02139, September 2012. .pdf
Scott M. Pike, Srikanth Sastry, and Jennifer L. Welch. Failure Detectors Encapsulate Fairness. Distributed Computing, 25(4):313-333, 2012.
.pdf
Srikanth Sastry, Jennifer Welch, and Josef Widder. Wait-Free Stabilizing Dining Using Regular Registers. Proceedings of the 16th International Conference On Principles Of DIstributed Systems, Rome, Italy, December 2012. .pdf
2011
Yehuda Afek, Noga Alon, Ziv Bar-Joseph, Alejandro Cornejo, Bernhard Haeupler and Fabian Kuhn. Beeping a Maximal Independent Set. In David Peleg, editor, Distributed Computing: 25th International Symposium on DIStributed Computing (DISC), Rome, Italy, September 2011, volume 6950 of Lecture Notes in Computer Science, pages 32-50, 2011. Springer. .pdf
Dan Alistarh, James Aspnes, Keren Censor-Hillel, Seth Gilbert and
Morteza Zadimoghaddam.
Optimal-Time Adaptive Strong Renaming, with Applications to Counting. In Proceedings of the 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, San Jose, California, June 6-8, 2011. .pdf
Paul Attie, Rachid Guerraoui, Petr Kouznetsov, Nancy Lynch, and Sergio Rajsbuam. The Impossibility of Boosting Distributed Service Resilience.
Information and Computation, 209(6):927-950, June 2011.
.pdf
Chen Avin, Michael Borokhovich, Keren Censor-Hillel and Zvi Lotker.
Order Optimal Information Spreading Using Algebraic Gossip. In Proceedings of the 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, San Jose, California, June 6-8, 2011. .pdf
Yossi Azar, Aviv Nisgav and Boaz Patt-Shamir.
Recommender Systems With Non-Binary Grades.
In Proceedings of the 23rd ACM Symposium on Parallel Algorithms and Architectures (SPAA), June 2011. .pdf
Zvika Brakerski and Boaz Patt-Shamir. Distributed Discovery of Large Near-Cliques. Distributed Computing, 24(2):79-89, 2011.
.pdf
Keren Censor-Hillel, Seth Gilbert, Fabian Kuhn, Nancy Lynch and Calvin Newport. Structuring Unreliable Radio Networks. In Proceedings of the 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, San Jose, California, June 6-8, 2011. .pdf
Keren Censor-Hillel, Seth Gilbert, Fabian Kuhn, Nancy Lynch and Calvin Newport. Structuring Unreliable Radio Networks. Technical Report MIT-CSAIL-TR-2011-053, Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA, December, 2011. .pdf
Keren Censor-Hillel and Hadas Shachnai. Fast Information Spreading in Graphs
with Large Weak Conductance. Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2011), San Francisco, CA, January, 2011. .pdf
Shlomi Dolev, Seth Gilbert, Majid Khabbazian and Calvin Newport.
Leveraging channel diversity to gain efficiency and robustness for wireless broadcast. In David Peleg, editor, Distributed Computing: 25th International Symposium on DIStributed Computing (DISC), Rome, Italy, September 2011, volume 6950 of Lecture Notes in Computer Science, pages 252-267, 2011. Springer. .pdf
Mohsen Ghaffari, Nancy Lynch, and Srikanth Sastry.
Leader Election Using Loneliness Detection. Technical Report MIT-CSAIL-TR-2011-045, Computer Science and Artificial and Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA, October 2011. .pdf
Mohsen Ghaffari, Nancy Lynch, and Srikanth Sastry.
Leader Election Using Loneliness Detection. In David Peleg, editor, Distributed Computing: 25th International Symposium on DIStributed Computing (DISC 2011), Rome, Italy, September 2011, volume 6950 of Lecture Notes in Computer Science, pages 268-282, 2011. Springer. .pdf
Magnus M. Halldorsson, Boaz Patt-Shamir and Dror Rawitz.
Online Scheduling with Interval Conflicts.
28th Int. Symp. on Theoretical Aspects of Computer Science (STACS), Tu Dortmund, Germany, March 2011. .pdf
Majid Khabbazian and Dariusz Kowalski. Time-efficient randomized multiple-message broadcast in radio networks. In Proceedings of the 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, San Jose, California, pages 373-380, June 6-8, 2011. .pdf
Majid Khabbazian, Fabian Kuhn, Nancy Lynch, Muriel Medard, and
Ali ParandehGheibi. MAC Design for Analog Network Coding. In FOMC 2011: The Seventh ACM SIGACT/SIGMOBILE International Workshop on Foundations of Mobile Computing, San Jose, CA, pages 42-51, June 2011. .pdf
Majid Khabbazian, Dariusz Kowalski, Fabian Kuhn, and Nancy Lynch.
Decomposing Broadcast Algorithms Using Abstract MAC Layers. Technical Report MIT-CSAIL-TR-2011-010, Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambrige, MA, February 2011. .pdf
Fabian Kuhn, Thomas Locher, and Rotem Oshman. Gradient Clock
Synchronization in Dynamic Networks. Theory of
Computing Systems, 49(4):781-816, July 2011. Special issue of SPAA'09.
.pdf
Fabian Kuhn, Nancy Lynch, and Calvin Newport. The Abstract MAC
Layer. Distributed Computing, 24(3):187-206, 2011. Special issue for DISC 2009: 23rd International Symposium on Distributed Computing.
.pdf
Fabian Kuhn and Rotem Oshman. The Complexity of Data Aggregation in Directed Networks. In David Peleg, editor, Distributed Computing: 25th International Symposium on Distributed Computing (DISC 2011), Rome, Italy, September 2011, volume 6950 of Lecture Notes in Computer Science, pages 416-431, 2011. Springer. .pdf
Fabian Kuhn, Yoram Moses and Rotem Oshman. Coordinated Consensus in Dynamic Networks. In Proceedings of the 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, San Jose, California, pages 1-10, June 6-8, 2011. .pdf
Nancy A. Lynch, Stephen J. Garland, Dilsun Kaynar, Laurent Michel, and Alex Shvartsman. The Tempo Language User Guide and Reference Manual, October 2011. .pdf
Yishay Mansour, Boaz Patt-Shamir and Dror Rawitz. Competitive Router Scheduling
with Structured Data. Proceedings of the 9th International Workshop on Approximation and Online Algorithms (WAOA 2011), Saarbrucken, Germany, September 2011. .pdf
Yishay Mansour, Boaz Patt-Shamir and Dror Rawitz. Overflow Management with Multipart Packets. 30th IEEE INFOCOM, April 2011. .pdf
Thomas Moscibroda and Rotem Oshman. Resilience of Mutual Exclusion Algorithms to Transient Memory Faults. In Proceedings of the 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, San Jose, California, June 6-8, 2011. .pdf
Calvin Newport and Nancy Lynch.
Modeling Radio Networks.
Distributed Computing, 24(2):101-118, October, 2011. .pdf
Aviv Nisgav and Boaz Patt-Shamir. Finding Similar Users in Social Networks. Theory of Computing Systems, 49(4):720-838, 2011. Special issue devoted to selected papers from SPAA 2009. .pdf
Aviv Nisgav and Boaz Patt-Shamir. Improved Collaborative Filtering. In T. Asano, S-I. Nakano, Y. Okamoto, O. Watanabe, editors, Algorithms and Computation - 22nd International Symposium (ISAAC 2011), Yokohama, Japan, December 2011, volume 7074 of Lecture Notes in Computer Science, pages 425-434, 2011. Springer. .pdf
Boaz Patt-Shamir and Dror Rawitz. Video Distribution Under Multiple Constraints. Theoretical Computer Science, 412(29):3717-3730, 2011. .pdf
Boaz Patt-Shamir and Marat Teplitsky. The Round Complexity of Distributed Sorting. In Proceedings of the 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, San Jose, California, June 6-8, 2011. .pdf
Tsvetomira Radeva and Nancy Lynch. Brief Announcement: Partial
Reversal Acyclicity. In Proceedings of the 30th Annual
ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC),
San Jose, California, pages 353-354, June 6-8, 2011. .pdf
Tsvetomira Radeva and Nancy Lynch. Partial Reversal Acyclicity.
Technical Report MIT-CSAIL-TR-2011-022, Computer Science and Artificial and Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA, April 2011. .pdf
Mikhail Volkov, Alejandro Cornejo, Daniela Rus and Nancy Lynch. Environment Characterization for Non-Recontaminating Frontier-Based Robotic Exploration.
4th International Conference on Principles and Practice of Multi-Agent Systems (PRIMA 2011), Wollongong, Australia, November 2011. Best Student Paper Award. .pdf
Jiang Wu. A Simulation Study on using the Virtual Node Layer to Implement Efficient and Reliable MANET Protocols. Ph.D. thesis, The City University of New York, Department of Computer Science, 2011. .pdf
Jiang Wu, Nancy Griffeth, Nancy Lynch, and Calvin Newport.
Engineering the Virtual Node Layer for Reactive MANET Routing. Proceedings of the 10th International Symposium on Network Computing
and Applications (NCA11), Cambridge, MA, August 2011. .pdf
2010
Dan Alistarh, Seth Gilbert, Rachid Guerraoui, Zarko Milosevic
and Calvin Newport. Securing Every Bit: Authenticated Broadcast in
Radio Networks. Proceedings of the ACM Symposium on
Parallelism in Algorithms and Architectures (SPAA), Santorini, Greece, pages 50-59, June 2010. .pdf
Hagit Attiya and Keren Censor-Hillel. Lower Bounds for Randomized
Consensus under a Weak Adversary. SIAM Journal on Computing, 39(8):3885-3904, December 2010. .pdf
Alejandro Cornejo and Fabian Kuhn. Deploying Wireless Networks with
Beeps. In N. Lynch, A. Shvartsman, editors, Distributed Computing: Proceedings of the 24th International
Symposium on Distributed Computing (DISC 2010), Cambridge, MA, September 2010., volume 6343 of Lecture Notes in Computer Science, pages 148-162, 2010. Springer. .pdf
Alejandro Cornejo and Nancy Lynch. Reliably Detecting Connectivity
Using Local Graph Traits. In Principles of Distributed Systems (OPODIS 2010), Tozeur, Tunisia, December 2010, volume 6490 of Lecture Notes in Computer Science, pages 87-102, 2010. Springer. .pdf
Alejandro Cornejo and Nancy Lynch. Fault-Tolerance Through k-Connectivity, IEEE International Conference on Robotics and Automation (ICRA 2010): Workshop on Network Science and System Issues in Multi-Robot Autonomy, Anchorage, Alaska, May 2010. .pdf
Alejandro Cornejo and Calvin Newport. Prioritized Gossip in
Vehicular Networks. Proceedings of Sixth ACM SIGACT/SIGMOBILE
International Workshop on Foundations of Mobile Computing
(DIALM-POMC 2010), Cambridge, MA, pages 53-62, September, 2010. .pdf
Alejandro Cornejo, Saira Viqar and Jennifer Welch. Reliable Neighbor
Discovery for Mobile Ad Hoc Networks. Proceedings of Sixth ACM
SIGACT/SIGMOBILE International Workshop on Foundations of Mobile
Computing (DIALM-POMC 2010), Cambridge, MA, pages 63-72, September, 2010. .pdf
S. Dolev, S. Gilbert, M. Khabbazian and C. Newport.
Broadcasting in Radio Networks with Multiple Channels.
Manuscript, 2010.
Seth Gilbert, Nancy Lynch, and Alex Shvartsman. RAMBO: A Robust, Reconfigurable Atomic Memory Service for Dynamic Networks. Distributed Computing, 23(4):225-272, December 2010. .pdf.
This is a slightly corrected version of the journal version, .pdf.
The changes are explained in the following errata sheet .pdf
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. .pdf
Majid Khabbazian, Dariusz Kowalski, Fabian Kuhn, and Nancy Lynch.
Decomposing Broadcast Algorithms Using Abstract MAC Layers.
Proceedings of Sixth ACM SIGACT/SIGMOBILE International Workshop on
Foundations of Mobile Computing (DIALM-POMC 2010), Cambridge, MA, pages 13-22, September, 2010. .pdf
Majid Khabbazian, Dariusz Kowalski, Fabian Kuhn, and Nancy Lynch.
The Cost of Global Broadcast using Abstract MAC Layers. Technical Report MIT-CSAIL-TR-2010-005, MIT Computer Science and Artificial Intelligence Laboratory, Cambridge, MA, February 9, 2010. .pdf
Majid Khabbazian, Fabian Kuhn, Nancy Lynch, Muriel Medard, and Ali ParandehGheibi. MAC Design for Analog Network Coding. Technical Report MIT-CSAIL-TR-2010-036, MIT Computer Science and Artificial Intelligence Laboratory, Cambridge, MA, July, 2010. .pdf
Fabian Kuhn, Christoph Lenzen, Thomas Locher, and Rotem Oshman.
Optimal Gradient Clock Synchronization in Dynamic Networks.
Proceedings of the 29th ACM Symposium on Principles of Distributed Computing, Zurich, Switzerland, pages 430-439, July 2010. .pdf
Fabian Kuhn, Nancy Lynch, and Calvin Newport. The Abstract MAC Layer. Technical Report MIT-CSAIL-TR-2010-040, Computer Science and Artificial Intelligence Laboratory, Cambridge, MA, August 2010. .pdf
Fabian Kuhn, Nancy Lynch, Calvin Newport, Rotem Oshman, Andrea Richa. Broadcasting in Unreliable Radio Networks. Proceedings of the 29th ACM Symposium on Principles of Distributed Computing, Zurich, Switzerland, pages 336-345, July 2010. .pdf
Fabian Kuhn, Nancy Lynch, Calvin Newport, Rotem Oshman, and Andrea
Richa. Broadcasting in Unreliable Radio Networks. Technical
Report MIT-CSAIL-TR-2010-029, MIT Computer Science and Artificial
Intelligence Laboratory, Cambridge, MA, June 2010. .pdf
Fabian Kuhn, Nancy Lynch and Rotem Oshman. Distributed Computation in
Dynamic Networks. Proceedings of the 42nd ACM Symposium on Theory of
Computing (STOC 2010), pages 513-522, Cambridge, MA, June 2010. .pdf
Shinya Umeno and Nancy Lynch.
Automated Formal Verification of the DHCP Failover Protocol Using
Timeout Order Abstraction.
Proceedings of 15th IEEE International Conference on
Engineering of Complex
Computer Systems (ICECCS 2010), Oxford, UK, March 22-26 2010. .pdf
2009
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. .pdf
Alejandro Cornejo, Fabian Kuhn, Ruy Ley-Wild, and Nancy Lynch.
Keeping mobile robot swarms connected. In Idit Keidar, editor, Distributed Computing, DISC 2009: 23rd International Symposium on Distributed
Computing, Elche/Elx, Spain, September 23-25 2009, volume 5805 of Lecture Notes in Computer Science, pages 496-511, 2009. Springer. .pdf
Also, Extended version is Technical Report MIT-CSAIL-TR-2009-027, MIT
CSAIL, Cambridge, MA, June 2009. .pdf
Alejandro Cornejo, Nancy Lynch, Saira Viqar, Jennifer Welch.
Neighbor Discovery in Mobile Ad Hoc Networks Using an Abstract MAC Layer. Forty-Seventh Annual Allerton Conference, Champaign-Urbana, IL, October, 2009. Invited paper. .pdf
Alejandro Cornejo and Nancy Lynch. Brief Announcement: Minimum Spanning Trees and
Cone-Based Topology Control. Proceedings of the 28th Annual ACM
Symposium on Principles of Distributed Computing, Calgary, Canada,
August 2009. .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. .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. .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. .pdf.
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
Rachid Guerraoui, Maurice Herlihy, Petr Kouznetsov, Nancy Lynch, and Calvin Newport. On the Weakest Failure Detector Ever. Distributed Computing, 21(5):353-366, February 2009. Special Issue PODC 2007. .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. .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. .pdf
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 Calvin Newport. The Abstract MAC Layer. In I. 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 48-62, 2009. Springer. .pdf
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. .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 and Rotem Oshman. Gradient clock synchronization using reference broadcasts.
In Principles of Dsitributed Systems (Proceedings of the 13th International Conference on Principle of DIstributed Systems (OPODIS), Nimes, France, December 2009, volume 5923 of Lecture Notes in Computer Science, pages 204-218, 2009. Springer. .pdf
Calvin Newport. Distributed Computation on Unreliable Radio Channels. Ph.D. thesis, MIT Department of Electrical Engineering and Computer Science, Cambridge, MA, September 2009. .pdf
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
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
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. .pdf
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. .pdf
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 and Nancy Lynch. Timeout Order Abstraction for Time-Parametric Verification of Loosely Synchronized Real-Time Distributed Systems. Proceedings of the 2nd Workshop on Compositional Theory and Technology for Real-Time
Embedded Systems (CTRS 2009), Washington, D.C., December 1, 2009, (Co-located with RTSS 2009). .pdf
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, Hongping 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 Protocols 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. .pdf
Alejandro Cornejo, Nancy Lynch. Connectivity Service for Mobile
Ad-Hoc Networks. Spatial Computing Workshop at 2nd IEEE
International Conference on Self-Adaptive and Self-Organizing Systems,
Venice, Italy, October 2008. .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. .pdf
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. .pdf
Matthew Brown, Seth Gilbert, Nancy Lynch, Calvin Newport, Tina
Nolte, and Michael Spindel. The Virtual Node Layer: A Programming
Abstraction for Wireless Sensor Networks. Proceedings of the
the International Workshop on Wireless Sensor Network Architecture
(WWSNA), Cambridge, MA, April, 2007. .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/102, 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.
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 for excitable cells. 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. .pdf
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. .pdf
Nancy Lynch, Roberto Segala, and Frits Vaandrager.
Observing Branching Structure through Probabilistic Contexts. Siam
Journal on Computing, 37(4):977-1013, September 2007. .pdf
Sayan Mitra. A Verification Framework for 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 implementations 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 for 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 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 for Sensor Networks. 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. In Alexander Shvartsman, editor, Proceedings
of the 10th International Conference On Principles Of Distributed
Systems (OPODIS), Bordeaux, France, December 12-15, 2006, volume 4305 of Lecture Notes in Computer Science, pages 215-229, 2006. Springer. .pdf
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. .pdf
Dilsun K. Kaynar, Nancy Lynch, Roberto Segala, and Frits Vaandrager.
The Theory of Timed I/O Automata. Synthesis Lectures on Computer Science, Morgan Claypool
Publishers, 2006. Revised and shortened version
of Technical Report MIT-LCS-TR-917a (from 2004). .pdf
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. Socratic Game Theory: Playing Games in Many Possible Worlds. Proceedings
of the Seventh ACM Conference on Electronic Commerce, June, 2006.
.pdf
Hongping Lim. Translating Timed I/O Automata Specifications for Theorem Proving in PVS. Masters thesis, MIT Department of Electrical
Engineering and Computer Science, Cambridge, MA, February 2006. .pdf
Sayan Mitra and Nancy Lynch. Approximate simulations for
task-structured probabilistic I/O automata.
LICS workshop on Probabilistic Automata and Logics
(PAul06), Seattle, WA, August 2006. .pdf
Sayan Mitra, Daniel Liberzon, and Nancy Lynch. Verifying average
dwell time by solving optimization problems. In Ashish Tiwari and
Joao P. Hespanha, editors, Hybrid Systems: Computation and
Control,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. .pdf
Shinya Umeno and Nancy Lynch.
Proving safety properties of an aircraft landing protocol
using I/O Automata and the PVS theorem prover: a case study.
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 and untimed 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. The 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. .pdf
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 Task-Structured Probabilistic I/O Automata to Analyze an Oblivious Transfer
Protocol.ePrint Report 2005/452, Cryptology ePrint Archive, 2005. .pdf
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. .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 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. .pdf
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.
.pdf
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. .pdf
Also, Technical Report MIT-LCS-TR-900a,
CSAIL, Massachusetts Institute of Technology, Cambridge, MA, 2004. .pdf .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. .pdf .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. .pdf
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. .pdf
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. .pdf
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. .pdf
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. .pdf
Nancy Lynch, Sayan Mitra, and Tina Nolte. Motion coordination
using virtual nodes. Technical Report MIT-LCS-TR-986, MIT CSAIL, Cambridge, MA,
April 2005. .pdf
Nancy Lynch, Sayan Mitra, and Tina Nolte. Using Virtual Nodes to Coordinate the Motion of Mobile 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 of automata.
In Electronic Notes in Theoretical Computer Science, volume 125(2),
2005, pages 45-65. .pdf
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
Paul C. Attie, Anish Arora, and E. Allen Emerson. Synthesis of Fault-Tolerant Concurrent Programs.
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. .pdf .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. .pdf.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. .pdf
.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. .pdf .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. .pdf.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. .pdf .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 Lynch, Elad Schiller, Alex
Shvartsman, Jennifer Welch. Virtual Mobile Nodes for Mobile Ad Hoc Networks (Extended Abstract). 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. .pdf
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.
In Rastislav Kralovic, Ondrej Sykora, editors, 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. .pdf
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. .pdf
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. .pdf
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
Ch. Georgiou, A. Russell and A. Shvartsman.
The Complexity of Synchronous Iterative Do-All with Crashes.
Distributed Computing, 17(1):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. .pdf
Seth Gilbert and Gregory Malewicz. The Quorum Deployment Problem.
In Teruo Higashino, editor, 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 316-333, 2004. Springer. .pdf
Also, full version in MIT CSAIL Technical Report MIT-LCS-TR-972,
October 2004. .pdf
Seth Gilbert, Nancy Lynch, and Alex Shvartsman. RAMBO II:
Rapidly Reconfigurable atomic memory for dynamic networks. Technical Report MIT-CSAIL-TR-890, CSAIL,
Massachusetts Institute Technology, Cambridge, MA, 2004. .pdf
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. .pdf
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. .pdf
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. .pdf
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. .pdf .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. .pdf .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. .pdf .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. .pdf .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. .pdf
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. .pdf .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. .pdf .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 and Compositional 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. Latest version is dated November 2003 .pdf
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
Murat Demirbas, Anish Arora, Tina Nolte, and Nancy 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. .pdf .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. .pdf
Rui Fan and Nancy Lynch. Brief Announcement: 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.
Stephen J. Garland, Nancy A. Lynch, Joshua A. Tauber, and Mandana Vaziri. IOA User Guide and Reference Manual. Technical Report MIT-LCS-TR-961, MIT Laboratory for Computer Science, Cambridge, Massachusetts, August 14, 2003. .pdf
Ch. Georgiou. Robust Distributed Cooperation in the
Presence of Quantified Adversity. Ph.D. thesis, University of
Connecticut, 2003. .pdf .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. .pdf .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. .pdf .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. .pdf
.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. .pdf .ps
(Full version available as Technical Report MIT/LCS/TR-917. .pdf .ps
Dilsun K. Kaynar, Nancy Lynch, Roberto Segala, and Frits Vaandrager.
The Theory of Timed I/O Automata. Technical Report
MIT-LCS-TR-917, MIT Laboratory for Computer Science, Cambridge, MA, 2003. .pdf .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. .pdf
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. .pdf .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. .pdf
Nancy Lynch, Roberto Segala, and Frits Vaandrager.
Compositionality for Probabilistic Automata. In
Roberto Amadio and Denis Lugiez, editors, CONCUR 2003 - Concurrency
Theory (14th International Conference on Concurrency Theory, Marseille,
France, September, 2003), volume 2761 of Lecture Notes in Computer Science,
pages 208-221, Springer-Verlag, 2003. .pdf
Nancy Lynch, Roberto Segala, and Frits Vaandrager. Hybrid I/O Automata.
Information and Computation, 185(1):105-157, August 2003. .pdf Also, Technical Report MIT-LCS-TR-827d.pdf.ps 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
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. .pdf.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. .pdf .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. .pdf .ps
Edward Solovey. Simulation of Composite I/O Automata.
Masters of Engineering Thesis, MIT Department of Electrical
Engineering and Computer Science, Cambridge, MA, August 2003. .pdf .ps
2002
P. C. Attie. Wait-free Byzantine Consensus.
Information Processing Letters, 83(4):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. .pdf.
Roberto De Prisco, Nancy Lynch, Alexander Shvartsman, Nicole Immorlica, and Toh Ne Win. A Formal Treatment of Lamport's Paxos Algorithm. Manuscript, October 2002. .pdf
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. .pdf .ps
Dilsun Kirli Kaynar, Anna Chefter, Laura Dean, Stephen J. Garland,
Nancy A. Lynch, Toh Ne Win, and Antonio Ramirez-Robredo.
Simulating Nondeterministic Systems at Multiple Levels of
Abstraction. In Tools Day held in conjunction with CONCUR'02, Brno, Czech
Republic, August 2002. .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), Bertinoro, Italy, June 2002. 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. A One-Round Algorithm for Virtually Synchronous Group Communication in 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. .pdf
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 Distributed Hash Tables. In
P. Druschel, F. Kaashoek, and A. Rowstron, editors, Peer-to-Peer
Systems (First International Workshop on
Peer-to-Peer Computing, Cambridge, MA, March 2002), volume 2429 of
Lecture Notes in Computer Science, pages 295-305, Springer, 2002.
.pdf
Nancy Lynch and Alex Shvartsman. 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. .pdf .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. .pdf .ps
Michael J. Tsai. Code Generation for the IOA Language. Master of Engineering Thesis, Massachusetts Institute of
Technology, Cambridge, MA, June 2002. .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. .pdf
Paul C. Attie and Nancy A. Lynch. Brief Announcement: Dynamic Input/Output Automata, a Formal Model for Dynamic Systems. Proceedings of the Twentieth ACM Annual Symposium on Principles of Distributed Computing, Newport, RI, pages 314-316, 2001. .pdf
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. .pdf
Alan Fekete, Nancy Lynch
, and Alex Shvartsman. 