Nancy Lynch. Distributed Algorithms, Morgan Kaufmann Publishers, Inc., San Mateo, CA, March 1996. Course Reserve
Hagit Attiya and Jennifer Welch. Distributed Computing: Fundamentals, Simulations, and Advanced Topics, John Wiley and Sons, Inc., 2004. Second Edition. Course Reserve
Michael Ben-Or. Another advantage of free choice: Completely asynchronous agreement protocols. Proceedings of the Second Annual ACM symposium on Principles of Distributed Computing (PODC 1983), pages 27-30, Montreal, Quebec, Canada, 1983. .pdf
James Aspnes and Maurice Herlihy. Fast randomized consensus using shared memory. Journal of Algorithms, 11(3):441--461, 1990. .pdf
Michael Saks, Nir Shavit, and Heather Woll. Optimal time randomized consensus---making resilient algorithms fast in practice. In Proceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, pages 351--362, 1991. .pdf
Hagit Attiya and Keren Censor. Tight bounds for asynchronous randomized consensus. Journal of the ACM, 55(5), 2008. .pdf
Gabi Bracha and Ophir Rachman. Randomized consensus in expected O(n^2\log{n}) operations. In Proceedings of the 5th International Workshop on Distributed Algorithms (WDAG), pages 143--150, 1991. .pdf
James Aspnes and Orli Waarts. Randomized consensus in expected O(n \log^2{n}) operations per processor. SIAM journal on Computing, 25(5):1024--1044, 1996. .pdf
James Aspnes, Hagit Attiya, and Keren Censor. Max registers, counters, and monotone circuits. In Proceedings of the 28th ACM Symposium on Distributed Computing (PODC 2009), pages 36--45, August 2009. .pdf
Prasad Jayanti, King Tan, and Sam Toueg. Time and space lower bounds for nonblocking implementations. SIAM Journal on Computing, 30(2):438--456, 2000. .pdf
Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson. Impossibility of distributed consensus with one faulty process. Journal of the ACM, 32(2):374--382, April 1985. .pdf
Michael C. Loui and Hosame H. Abu-Amara. Memory requirements for agreement among unreliable asynchronous processes. Advances in Computing Research, pages 163--183, 1987. .pdf
Hagit Attiya and Keren Censor. Lower bounds for randomized consensus under a weak adversary. In Proceedings of the 27th Annual ACM Symposium on Distributed Computing (PODC 2008), pages 315--324, 2008. .pdf
Benny Chor, Michael Merritt, and David B. Shmoys. Simple constant-time consensus protocols in realistic failure models. Journal of the ACM, 36(3):591--614, 1989. .pdf .
R. Karp, C. Schindelhauer, S. Shenker, and B. Vocking. Randomized rumor spreading. In Proceedings of the 41st Annual Symposium on Foundations of Computer Science, pages 565-574, Washington, DC, USA, 2000. IEEE Computer Society. .pdf
Flavio Chierichetti, Silvio Lattanzi, and Alessandro Panconesi. Almost tight bounds for rumour spreading with conductance. In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC), pages 399--408, 2010. .pdf
Damon Mosk-Aoyama and Devavrat Shah. Computing separable functions via gossip. In Proceedings of the Twenty-fifth Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 113--122, New York, NY, USA, 2006. ACM. .pdf
Keren Censor-Hillel and Hadas Shachnai. Fast information spreading in graphs with large weak conductance. In Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms (SODA), 2011. .pdf
Baruch Awerbuch. Complexity of network synchronization. Journal of the ACM, 32(4):804--823, 1985. .pdf
Surender Baswana, Telikepalli Kavitha, Kurt Mehlhorn, and Seth Pettie. New constructions of (alpha, beta)-spanners and purely additive spanners. In SODA, pages 672--681, 2005. .pdf
Surender Baswana and Sandeep Sen. A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs. Random Struct. Algorithms, 30(4):532--563, 2007. .pdf
Jon M. Kleinberg, Aleksandrs Slivkins, and Tom Wexler. Triangulation and embedding using small sets of beacons. Journal of the ACM, 56(6), 2009. .pdf
J. Schiller. Mobile Communications. Addison-Wesley, 2003. Course Reserve
Nitin H. Vaidya. Wireless networks. Draft. (Paper copies of notes to be distributed during class).
J. Hastad, F. T. Leighton, and B. Rogoff. Analysis of backoff protocols for multiple access channels. SIAM Journal on Computing, 25(4):740--774, 1996. .pdf
Majid Khabbazian, Dariusz Kowalski, Fabian Kuhn, and Nancy Lynch. Decomposing broadcast algorithms using abstract MAC layers. In Proceedings of Sixth ACM SIGACT/SIGMOBILE International Workshop on Foundations of Mobile Computing (DIALM-POMC 2010), Cambridge, MA, September 2010. .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 Artifical Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA, February 2011. Also, submitted for publication. .pdf
Majid Khabbazian, Fabian Kuhn, Nancy Lynch, Muriel Medard, and Ali ParandehGheibi. MAC design for analog network. Technical Report MIT-CSAIL-TR-2010-036, Cambridge, MA, July 2010. .pdf
Fabian Kuhn, Nancy Lynch, and Calvin Newport. The Abstract MAC layer. Distributed Computing, 2010. To appear. Special Issue. .pdf
J. Komlos and A. Greenberg. An asymptotically nonadaptive algorithm for conflict resolution in multiple-access channels. IEEE Transactions on Information Theory, IT-31:302--306, 1985. .pdf
R. Bar-Yehuda, O. Goldreich, and A. Itai. Efficient emulation of single-hop radio network with collision detection on multi-hop radio network with no collision detection. Distributed Computing, 5:67--71, 1991. .pdf
R. Bar-Yehuda, O. Goldreich, and A. Itai. On the time complexity of broadcast in multi-hop radio networks: An exponential gap between determinism and randomization. Journal of Computer and System Sciences, 45(1):104--126, 1992. .pdf
Majid Khabbazian, Dariusz Kowalski, Fabian Kuhn, and Nancy Lynch. Decomposing Broadcast Algorithms Using Abstract MAC Layers. To appear as MIT Technical Report, February 2011. Also, submitted for publication. .pdf
Majid Khabbazian, Dariusz Kowalski, Fabian Kuhn, and Nancy Lynch. Decomposing broadcast algorithms using abstract MAC layers. In Proceedings of Sixth ACM SIGACT/SIGMOBILE International Workshop on Foundations of Mobile Computing (DIALM-POMC 2010), Cambridge, MA, September 2010. .pdf
D. Kowalski and A. Pelc. Time of deterministic broadcasting in radio networks with local knowledge. SIAM Journal on Computing, 33(4):870--891, 2004. .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 2009. .pdf
Fabian Kuhn, Nancy Lynch, Calvin Newport, Rotem Oshman, and Andrea Richa. Broadcasting in unreliable radio networks. In Proceedings of the 29th ACM Symposium on Principles of Distributed Computing, Zurich, Switzerland, July 2010. .pdf
H. Attiya, D. Hay, and J. Welch. Optimal clock synchronization under energy constraints in wireless ad hoc networks. In Principles of Distributed Systems: 9th International Conference, OPODIS 2005, Pisa, Italy, December 2005, volume 3974 of Lecture Notes in Computer Science, pages 221--234. Springer, 2006. .pdf
W. Su and I.F. Akyildiz. Time-diffusion synchronization protocol for wireless sensor networks. IEEE/ACM Transactions on Networking, 13(2):384--397, 2005. .pdf
J. Elson, L. Girod, and D. Estrin. Fine-grained network time synchronization using reference broadcasts. ACM SIGOPS Operating Systems Review, 36(SI):147--163, 2002. .pdf
R. M. Karp, J. Elson, C. Papadimitriou, and S. Shenker. Global synchronization in sensornets. In Proceedings of the 6th Latin American Symposium on Theoretical Informatics (LATIN'04), Buenos Aires, Argentina, volume 2976 of Lecture Notes in Computer Science, pages 609--624. Springer, 2004. .pdf
Rui Fan. Lower Bounds in Distributed Computing. PhD thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA, February 2008. .pdf
Rui Fan and Nancy Lynch. Gradient clock synchronization. Distributed Computing, 18(4):255--266, November 2006. .pdf
Fabian Kuhn, Thomas Locher, and Rotem Oshman. Gradient clock synchronization in dynamic networks. In Proceedings of the 21st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA'09), Calgary, Alberta, Canada, August 2009. .pdf
Fabian Kuhn, Thomas Locher, and Rotem Oshman. Gradient clock synchronization in dynamic networks. Theory of Computing Systems, 2011. Special issue of SPAA'09. To appear. .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
C. Lenzen, T. Locher, and R. Wattenhofer. Clock synchronization with bounded global and local skew. In Proceedings of 49th Annual IEEE Symposium on Foundations of Computer Science, Philadelphia, PA, October 2008. .pdf
Fabian Kuhn, Nancy Lynch, and Rotem Oshman. Distributed computation in dynamic networks. In 42th ACM Symposium on Theory of Computing (STOC 2010), Cambridge, MA, June 2010. .pdf
Nitin H. Vaidya. Wireless networks. Draft. (Paper copies of notes to be distributed during class).
J. Schiller. Mobile Communications. Addison-Wesley, 2003. Course Reserve
X. Chen and A. Murphy. Enabling disconnected transitive communication in mobile ad hoc networks. In POMC 2001: Workshop on Principles of Mobile Computing, Newport, Rhode Island, August 2001. .pdf
D. B. Johnson and D A. Maltz. Dynamic source routing in ad hoc wireless networks. In T. Imielinski and H. Korth, editors, Mobile Computing, pages 153--181. Kluwer, 1996. .ps
C. Perkins and E. Royer. Ad hoc on-demand distance-vector routing. In 2nd Workshop on Mobile Computing Systems and Applications (WMCSA'99), pages 90--100, New Orleans, Lousiana, February 1999. .pdf
Q. Fang, J. Gao, L. Guibas, V. de Silva, and L. Zhang. GLIDER: Gradient landmark-based distributed routing for sensor networks. In INFOCOM 2005: 24th Annual Conference of the IEEE Computer and Communications Societies, pages 339--350, Miami, Florida, March 2005. ..pdf
Y. B. Ko and N. Vaidya. Geocasting in mobile ad-hoc networks: location-based multicast algorithms. In WMCSA'99: 2nd IEEE Workshop on Mobile Computing Systems and Applications, New Orleans, Lousiana, February 1999. .pdf
A. Rao, C. Papadimitiou, S. Shenker, and I. Stoica. Geographical routing without location information. In Mobicom 2003: The Ninth Annual International Conference on Mobile Computing and Networking, pages 96--108, San Diego, California, September 2003. .pdf
B. Karp and H. T. Kung. GPSR: Greedy perimeter stateless routing for wireless networks. In Mobicom 2000: The Sixth International Conference on Mobile Computing and Networking, Boston, Massachusetts, August 2000. .pdf
E. Kranakis, H. Singh, and J. Urrutia. Compass routing on geometric networks. In Proceedings of the 11th Canadian Conference on Computational Geometry (CCCG'99), Vancouver, BC, Canada, August 1999. .pdf
Fabian Kuhn, Roger Wattenhofer, and Aaron Zollinger. Asymptotically optimal geometric mobile ad-hoc routing. In 6th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIALM), Atlanta, Georgia, September 2002. .pdf
Fabian Kuhn, Roger Wattenhofer, and Aaron Zollinger. An algorithmic approach to geographic routing in ad hoc and sensor networks. IEEE/ACM Transactions on Networking, 16(1), February 2008. .pdf
E. Gafni and D. Bertsekas. Distributed algorithms for generating loop-free routes in networks with frequently changing topology. IEEE Transactions on Communications, January 1981. .pdf
C. Busch, S. Surapaneni, and S. Tirthapura. Analysis of link reversal routing algorithms. SIAM Journal on Computing, 35(2):305--326, October 2005. .pdf
V. Park and M. Corson. A highly adaptive distributed routing algorithm for mobile ad hoc networks. In Proceedings IEEE INFOCOM '97, The Conference on Computer Communications, Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies, Driving the Information Revolution, pages 1405--1413, Kobe, Japan, April 1997. .pdf
Jennifer Walter and Jennifer Welch. Link Reversal Algorithms. Synthesis Lectures on Distributed Computing Theory. Morgan Claypool Publishers. To appear.
D. Dubhashi, A. Mei, A. Panconesi, J. Radhakrishnan, and A. Srinivasan. Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 717--724, Baltimore, Maryland, 2003. .pdf
L. Jia, R. Rajaraman, and T. Suel. An efficient distributed algorithm for constructing small dominating sets. Distributed Computing, 15(4):193--205, December 2002. Special Issue: Selected papers from PODC'01. .pdf
F. Kuhn, T. Moscibroda, and R. Wattenhofer. What cannot be computed locally! In Proceedings of the 23rd ACM Symposium on the Principles of Distributed Computing (PODC'04), pages 300--309, St. John's, Newfoundland, Canada, July 2004. .pdf
F. Kuhn and R. Wattenhofer. Constant-time distributed dominating set approximation. Distributed Computing, 17(4):303--310, May 2005. .pdf
Fabian Kuhn. The Price of Locality: Exploring the Complexity of Distributed Coordination Primitives. PhD thesis, ETH Zurich, December 2005. Diss. ETH No. 16213. .pdf
F. Kuhn, T. Nieberg, T. Moscibroda, and R. Wattenhofer. Local approximation schemes for ad hoc and sensor networks. In Proceedings of the 2005 Joint Workshop on Foundations of Mobile Computing, pages 97--103, Cologne, Germany, 2005. .pdf
J. Schneider and R. Wattenhofer. A log-star distributed maximal independent set algorithm for growth bounded graphs. In Proceedings of 27th Annual ACM Symposium on Principles of Distributed Computing (PODC), Toronto, Canada, 2008. .pdf
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
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 2002), Toulouse, France, October 2002, volume 2508 of Lecture Notes in Computer Science, pages 173--190. Springer-Verlag, 2002. Also, Technical Report MIT-LCS-TR-856, MIT Laboratory for Computer Science, Cambridge, MA. .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 DISC 2003, 18(2):125--155, 2005. Also, Technical Report MIT-LCS-TR-900a, CSAIL, Massachusetts Institute of Technology, Cambridge, MA, 2004. .pdf
Shlomi Dolev, Seth Gilbert, Limor Lahiani, Nancy Lynch, and Tina Nolte. Timed virtual stationary automata for mobile networks. In Principles of Distributed systems: 9th International Conference on Principles of Distributed Systems (OPODIS 2005), Pisa, Italy, December 12-14, 2005, volume 3974 of Lecture Notes in Computer Science, pages 130--145. Springer, 2006. Also, Technical Report MIT-LCS-TR-979a, MIT CSAIL, Cambridge, MA 02139, August 2005. .pdf
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, 18th International Symposium on Distributed Computing (DISC 2004), Trippenhuis, Amsterdam, the Netherlands, October, 2004, volume 3274 of Lecture Notes in Computer Science, pages 230--244. Springer, December 2004. .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 DISC 2003, 18(2):125--155, 2005. Also, Technical Report MIT-LCS-TR-900a, CSAIL, Massachusetts Institute of Technology, Cambridge, MA, 2004. .pdf
Shlomi Dolev, Limor Lahiani, Nancy Lynch, and Tina Nolte. Self-stabilizing mobile node location management and message routing. In Sebastien Tixeuil Ted Herman, editor, Self-Stabilizing Systems: Seventh International Symposium on Self-Stabilizing Systems (SSS 2005), Barcelona, Spain, October 26-27, volume 3764 of Lecture Notes in Computer Science, pages 96--112. Springer, 2005. Also, Technical Report MIT-LCS-TR-999, MIT Computer Science and Artificial Intelligence Laboratory, Cambridge, MA, August 2005. .pdf
Seth Gilbert. Virtual Infrastructure for Wireless Ad Hoc Networks. PhD thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA, August 2007. .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
Nancy Lynch, Sayan Mitra, and Tina Nolte. Motion coordination using virtual nodes. In Forty-Fourth IEEE Conference on Decision and Control and European Control Conference (CDC-ECC 2005), Seville, Spain, December 2005. .pdf
Tina Nolte. Virtual Stationary Timed Automata for Mobile Networks. PhD thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA, February 2009. .pdf
Alejandro Cornejo, Majid Khabbazian, Nancy Lynch, and James McLurkin. Angle-constrained graph rigidity. Submitted for Publication.
Alejandro Cornejo, Fabian Kuhn, Ruy Ley-Wild, and Nancy Lynch. Keeping mobile robot swarms connected. Technical Report MIT-CSAIL-TR-2009-027, Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA,, June 2009. .pdf
Alejandro Cornejo and Nancy Lynch. Brief announcement: Minimum spanning trees and cone-based topology control. In Proceedings of the 28th Annual ACM Symposium on Principles of Distributed Computing, Calgary, Canada, August 2009. .pdf
Alejandro Cornejo and Nancy Lynch. Fault-tolerance through k-connectivity. In 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
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
Nancy Lynch, Sayan Mitra, and Tina Nolte. Motion coordination using virtual nodes. In Forty-Fourth IEEE Conference on Decision and Control and European Control Conference (CDC-ECC 2005), Seville, Spain, December 2005. .pdf
James McLurkin. Analysis and Implementation of Distributed Algorithms for Multi-Robot Systems. PhD thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA, 2008. .pdf