Principles of Distributed Computing (lecture collection)

Distributed computing is essential in modern computing and communications systems. Examples are on the one hand large-scale networks such as the Internet, and on the other hand multiprocessors such as your new multi-core laptop. The lecture notes on this webpage introduce the principles of distributed computing, emphasizing the fundamental issues underlying the design of distributed systems and networks: communication, coordination, fault-tolerance, locality, parallelism, self-organization, symmetry breaking, synchronization, uncertainty. We explore essential algorithmic ideas and lower bound techniques, basically the "pearls" of distributed computing. Each chapter covers a fresh topic.

Note that the order of the chapters is more or less arbitrary. Each chapter is mostly independent, with the occasional reference to another chapter.

Useful references

Lecture material

References

Books:

Articles chapter by chapter:

Chapter 0: Introduction

• G. Tel. Introduction to Distributed Algorithms. Cambridge University Press, England, 1994.
• N. Lynch. Distributed Algorithms. Morgan Kaufmann Publishers, Inc., San Mateo, CA, 1995.
• V.C. Barbosa. An Introduction to Distributed Algorithms. MIT Press, Cambridge, MA, 1996.

Chapter 1: Vertex Coloring

• R. Cole and U. Vishkin. Deterministic coin tossing with applications to optimal parallel list ranking. Inform. Comput., volume 70(1), pages 32-56, 1986.
• A.V. Goldberg and S. Plotkin. Parallel δ+1 coloring of constant-degree graphs. Inform. Process. Lett., volume 25, pages 241-245, 1987.
• N. Linial. Locality in Distributed Graph Algorithms. In SIAM Journal on Computing 21(1), pages 193-201, 1992.
• K. Kothapalli, M. Onus, C. Scheideler and C. Schindelhauer. Distributed coloring in O(sqrt{log n}) bit rounds. In IEEE International Parallel and Distributed Processing Symposium (IPDPS), 2006.

Chapter 2: Leader Election

• D. Angluin. Local and global properties in networks of processors. In Proceedings of the 12th ACM Symposium on Theory of Computing, pages 82-93, 1980.
• J.E. Burns. A formal model for message passing systems. Technical Report 91, Indiana University, September 1980.
• D.S. Hirschberg, and J.B. Sinclair. Decentralized extrema-finding in circular configurations of processors. In Communications of the ACM 23(11), pages 627-628, November 1980.
• G. LeLann. Distributed systems, towards a formal approach. In IFIP Congress Proceedings, pages 155-160, 1977.

Chapter 3: Tree Algorithms

• D. Bertsekas and R. Gallager. Data Networks. 2nd Edition. Prentice-Hall International, London, 1992.
• Y.K. Dalal and R.M. Metcalfe. Reverse path forwarding of broadcast packets. Communications of the ACM, volume 12, pages 1040-1048, 1978.
• S. Even. Graph Algorithms. Computer Science Press, Rockville, MD, 1979.
• P. Fraigniaud and E. Lazard. Methods and problems of communication in ususal networks. Discrete Appl. Mathematics, volume 53, pages 79-133, 1994.
• R. G. Gallager, P. A. Humblet, and P. M. Spira. Distributed Algorithm for Minimum-Weight Spanning Trees. In ACM Transactions on Programming Languages and Systems (TOPLAS), 5(1):66-77, January 1983.

Chapter 4: Distributed Sorting

• M. Ajtai, J. Komlos, and E. Szemeredi. An 0 (n log n) sorting network. In Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, pages 1-9, April 1983.
• J. Aspnes, M.P. Herlihy, and N. Shavit. Counting Networks. In Journal of the ACM, 41(5): pages 1020-1048, September 1994.
• K. Batcher. Sorting networks and their applications. In Proceedings of the AFIPS Spring Joint Computing Conference, volume 32, pages 307-314, 1968.
• C. Busch and M. Herlihy. A Survey on Counting Networks. In Proceedings of Workshop on Distributed Data and Structures, Orlando, Florida, March 30, 1998.
• N. Haberman. Parallel neighbor-sort (or the glory of the induction principle). Technical Report AD-759 248, National Technical Information Service, US Department of Commerce, 5285 Port Royal Road, Springfield VA 22151, 1972.
• C. Kaklamanis, D. Krizanc, and T. Tsantilas. Tight bounds for oblivious routing in the hypercube. In Proceedings of the 2nd Annual ACM Symposium on Parallel Algorithms and Architectures, pages 31-36, July 1990.
• M. Klugerman, C. Greg Plaxton: Small-Depth Counting Networks. In STOC 1992. pages 417-428.
• K. Sado and Y. Igarashi. Some parallel sorts on a mesh-connected processor array and their time efficiency. In Journal of Parallel and Distributed Computing, volume 3, pages 398-410, September 1986.

Chapter 5: Shared Memory

• E. W. Dijkstra. Solutions of a problem in concurrent programming control. Commun. ACM, 8(9):569, 1965.
• G. L. Peterson. Myths about the mutual exclusion problem. Inf. Process. Lett., 12:115--116, June 1981.
• G. L. Peterson and M. J. Fischer. Economical solutions for the critical section problem in a distributed system. In Proceedings of the 9th ACM Symposium on Theory of Computing, pages 91-97, 1977.
• H. Attiya, A. Fouren, E. Gafni. An Adaptive Collect Algorithm with Applications. Distributed Computing, 15(2), 2002.
• M. Moir and J.H. Anderson. Wait-Free Algorithms for Fast, Long-Lived Renaming. Science of Computer Programming, 25(1), October 1995.
• H. Attiya, F. Kuhn, M. Tolksdorf, and Roger Wattenhofer. Efficient Adaptive Collect using Randomization. In Proceedings of the 18th Annual Conference on Distributed Computing (DISC), pages 159-173, 2004.
• Y. Afek and Y. De Levie. Space and Step Complexity Efficient Adaptive Collect. In Proceedings of the 19th Annual Conference on Distributed Computing (DISC), pages 384-398, 2005.

Chapter 6: Shared Objects

• M. Demmer and M. Herlihy. The arrow directory protocol. In Proceedings of 12th International Symposium on Distributed Computing, Sept. 1 998.
• D. Ginat, D. D. Sleator, R. Endre Tarjan. A Tight Amortized Bound for Path Reversal. In Information Processing Letters volume 31(1), pages 3-5, 1989.
• M. Herlihy, S. Tirthapura, and R. Wattenhofer. Competitive Concurrent Distributed Queuing. In Proceedings of the Twentieth ACM Symposium on Principles of Distributed Computing (PODC), Newport, Rhode Island, August 2001. For a copy, see Publications.
• F. Kuhn and R. Wattenhofer. Dynamic Analysis of the Arrow Distributed Protocol. In Proceedings of the 16th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), Barcelona, Spain, June 2004. For a copy, see Publications.
• K. Li, and P. Hudak, Memory coherence in shared virtual memory systems. In ACM Transactions on Computer Systems volume 7(4), pages 321-3 59, Nov. 1989.
• B. M. Maggs, F. Meyer auf der Heide, B. Vöcking, M. Westermann. Exploiting Locality for Data Management in Systems of Limited Bandwidth. In IEEE Symposium on Foundations of Computer Science (FOCS), 1997.

Chapter 7: Dynamic Networks

• F. Kuhn, N. Lynch, and R. Oshman. Distributed Computation in Dynamic Networks. To appear in Proceedings of the 42nd Symposium on Theory of Computing (STOC), Cambridge, MA, USA, June 2010.
• F. Kuhn, N. Lynch, and R. Oshman. Distributed Computation in Dynamic Networks. MIT techreport no. MIT-CSAIL-TR-2009-058., Massachusetts Institute of Technology, November 2009.
• Regina O'Dell and Roger Wattenhofer. Information Dissemination in Highly Dynamic Graphs. 3rd ACM Joint Workshop on Foundations of Mobile Computing (DIALM-POMC), Cologne, Germany, September 2005.

Chapter 8: Peer-to-Peer Computing

• Peter Mahlmann, Christian Schindelhauer. Peer-to-Peer Networks, Springer, 2007.

Chapter 9: Social Networks

• Jon Kleinberg. The small-world phenomenon: an algorithm perspective. In Proceedings of the thirty-second annual ACM symposium on Theory of computing (STOC), Portland, Oregon, United States, 2000.
• David Easley and Jon Kleinberg. Networks, Crowds, and Markets: Reasoning About a Highly Connected World, Cambridge University Press, 2010.

Chapter 10: Maximal Independent Set

• M. Luby. A Simple Parallel Algorithm for the Maximal Independent Set Problem. In SIAM Journal on Computing, November 1986.
• A. Israeli, A. Itai. A Fast and Simple Randomized Parallel Algorithm for Maximal Matching. In Information Processing Letters volume 22(2), pages 77-80, 1986.
• N. Alon, L. Babai, and A. Itai. A fast and simple randomized parallel algorithm for the maximal independent set problem. Journal of Algorithms, 7(4):567-583, 1986.
• Y. Métivier, J.M. Robson, N. Saheb-Djahromi, and A. Zemmari. An Optimal Bit Complexity Randomised Distributed MIS Algorithm. 16th International Colloquium on Structural Information and Communication Complexity (SIROCCO), to appear, 2009.

Chapter 11: Locality Lower Bounds

• N. Linial. Locality in Distributed Graph Algorithms. SIAM Journal on Computing 21(1), 1992.
• A. Czygrinow, M. Hańćkowiak, and W. Wawrzyniak. Fast Distributed Approximations in Planar Graphs. In Proceedings of the 22nd International Symposium on Distributed Computing (DISC), September 2008.
• F. Kuhn, T. Moscibroda, R. Wattenhofer. What Cannot Be Computed Locally! In Proceedings of the 23rd ACM Symposium on Principles of Distributed Computing (PODC), July 2004.

Chapter 12: Synchronizers

• B. Awerbuch. Complexity of Network Synchronization. Journal of the ACM (JACM), 32(4), October 1985.
• B. Awerbuch and D. Peleg. Network Synchronization with Polylogarithmic Overhead. In Proceedings of the 31st IEEE Symposium on Foundations of Computer Science (FOCS), October 1990.

Chapter 13: Stabilization

• E. W. Dijkstra. Self-stabilizing systems in spite of distributed control. In Communications of the ACM 17(11), 1974, pages 943-644
• B. Awerbuch, B. Patt-Shamir and G. Varghese. Self-Stabilization By Local Checking and Correction (Extended Abstract). In Proceedings of IEEE Symposium on Foundations of Computer Science (FOCS), 1991, pages 268-277.
• E. Goles and J. Olivos. Periodic behavior of generalized threshold functions. Discrete Mathematics 30, 1980, pages 187-189.
• P. Winkler. Puzzled. In Communications of the ACM, August 2008.
• M. Gardner. Mathematical Games: The fantastic combinations of John Conway's new solitaire game "Life". Scientific American 223, October 1970, pages 120-123.

Chapter 14: Multi-Core Computing

• M. Herlihy and V. Luchangco. Distributed Computing and the Multicore Revolution. In ACM SIGACT News, 39, 2008.
• H. Attiya. Needed: Foundations for Transactional Memory. In ACM SIGACT News, 39:59?61, 2008.
• J. Schneider, R. Wattenhofer. Improved Contention Management Algorithms, in submission, 2009.
• D. Hasenfratz, J. Schneider, R. Wattenhofer. Transactional memory: How to Perform Load Adaption in a Simple and Distributed Manner, in submission, 2009.

Chapter 15: Dominating Set

• L. Jia, R. Rajaraman, T. Suel. An Efficient Distributed Algorithm for Computing Small Dominating Sets. Distributed Computing 15(4), December 2002.
• F. Kuhn and R. Wattenhofer. Constant-Time Distributed Dominating Set Approximation. In Principles of Distributed Computing (PODC), Boston, Mssachusetts, USA, July 2003.

Chapter 16: Consensus

• L. Lamport, R. Shostak, and M. Pease. The Byzantine generals problem. ACM Trans. Program. Lang. Syst., 4(3):382-401, July 1982.
• M. J. Fischer, N. A. Lynch, and M. S. Paterson. Impossibility of distributed consensus with one faulty processor. Journal of the ACM (JACM), 32(2):374-382, April 1985.
• M. Ben-Or. Another advantage of free choice: Completely asynchronous agreement protocols. In Proceedings of the 2nd Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 27-30, 1983.
• P. Feldman and S. Micali. Optimal algorithms for Byzantine agreement. In Proceedings of the 20th Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 162-172, 1988.

Chapter 17: All-to-All Communication

• Z. Lotker, B. Patt-Shamir, Elan Pavlov, and David Peleg. MST Construction in O(log log n) Communication Rounds. In Proceedings of the 15th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), 2003.

Chapter 18: Routing

• C. Busch, M. Herlihy, and R. Wattenhofer. Hard-Potato Routing. In Proceedings of the 32nd Annual ACM Symposium on Theory of Computing (STOC), Portland, Oregon, May 2000. For a copy, see Publications.
• C. Busch, M. Herlihy, and R. Wattenhofer. Randomized Greedy Hot-Potato Routing. Iee Publications.
• Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 458-466, San Francisco, California, January 2000. For a copy, see Publications.
• D. Krizanc, S. Rajasekaran, and T. Tsantilas. Optimal routing algorithms for mesh-connected processor arrays. In J. Reif, editor, Proceedings, 3rd Aegean Workshop on Computing: VLSI Algorithms and Architectures, volume 319 of Lecture Notes in Computer Science, pages 411-422. Springer-Verlag, July 1988.
• T. Leighton. Average case analysis of greedy routing algorithms on arrays. In Proceedings of the 2nd Annual ACM Symposium on Parallel Algorithms and Architectures, pages 2-10, July 1990.
• L. Valiant and G. Brebner. Universal schemes for parallel communication. In Proceedings of the Thirteenth Annual ACM Symposium on Theory of Computing, pages 263-277, May 1981.

Chapter 19: Routing Strikes Back

• A. Borodin and J. Hopcroft. Routing, merging, and sorting on parallel models of computation. Journal of Computer and System Sciences, Volume 30(1), pages 130-145, February 1985.
• F.T. Leighton, B. Maggs, and S. Rao. Universal Packet Routing Algorithms. In IEEE Symposium on Foundations of Computer Science, volume 29, pages 256 - 269, 1988.
• F.T. Leighton, B. M. Maggs, and A. W. Richa. Fast algorithms for finding O(congestion + dilation) packet routing schedules. Technical report CMU-CS-96-152, Carnegie Mellon University, 1996.
• C. Kaklamanis, D. Krizanc, and T. Tsantilas. Tight bounds for oblivious routing in the hypercube. In Proceedings of the 2nd Annual ACM Symposium on Parallel Algorithms and Architectures, pages 31-36, July 1990.