Principles of Distributed Computing (SS 2004)

In the last two decades, we have experienced an unprecedented growth in the area of distributed systems and networks; distributed computing now encompasses many of the activities occurring in today's computer and communications world. This course introduces the basics of distributed computing, highlighting common themes and techniques. It reaches the fundamental issues underlying the design of distributed systems communication, coordination, synchronization, uncertainty, and essential algorithmic ideas and lower bound techniques.

One of the main themes of recent research in distributed algorithms is "locality" (also known as decentralized computing, or peer-to-peer computing). Networks grow fast, thus locality and scalability become first-class issues. We discuss some of the most fascinating local distributed algorithms in the second part of the course.

Course pre-requisites: Basic networking knowledge (Vernetzte Systeme 37-019), and fundamentals of algorithms & complexity (Theoretische Informatik 37-402). Note that this course is in both the theory and the distributed systems major.

Course language: English

Lecture by Roger Wattenhofer, Wednesday 8.15-10.00 @ HRS F5.

A corrected version of Chapter 11 is now online.

Exercises by Fabian Kuhn, Regina O'Dell, Wednesday 10.15-11.00 @ HRS F5.

Useful references

New: The exam will take place on Monday, October 4th. Here is a copy of last year's exam to help in your preparation. The exam will last 90 minutes, no aids allowed.

Lecture material

Exercises material

References

Books:

[attiya]	Distributed Computing: Fundamentals, Simulations and Advanced Topics Hagit Attiya, Jennifer Welch. McGraw-Hill Publishing, 1998, ISBN 0-07-709352 6
[clr]	Introduction to Algorithms Thomas Cormen, Charles Leiserson, Ronald Rivest. The MIT Press, 1998, ISBN 0-262-53091-0 oder 0-262-03141-8
[leighton]	Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes Frank Thomson Leighton. Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991, ISBN 1-55860-117-1
[peleg]	Distributed Computing: A Locality-Sensitive Approach David Peleg. Society for Industrial and Applied Mathematics (SIAM), 2000, ISBN 0-89871-464-8

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, 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.

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 Apppl. Mathematics, volume 53, pages 79-133, 1994.
• R.G. Gallager. Distributed minimum hop algorithms. Technical Report LIDS-P-1175, Lab. for Information and Decision Systems, MIT, Cambridge, MA, January 1982.

Chapter 4: 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. In 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 5: Basic Network Topologies

• F. Preparata and J. Vuillemin. The cube-connected cycles: a versatile network for parallel computation. In Communications of the ACM, 24(5), pages 300-309, May 1981.
• J. Schwartz. Ultracomputers. In ACM Transactions on Programming Languages and Systems, 2(4):484-521, October 1980.

Chapter 6: 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.

Chapter 7: Shared Variables

• M. Demmer and M. Herlihy. The arrow directory protocol. In Proceedings of 12th International Symposium on Distributed Computing, Sept. 1998.
• 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. To appear 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-359, 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 8: Fault-Tolerant Distributed Systems

• T.D. Chandra, V. Hadzilacos, and S. Toueg. The weakest failure detector for solving consensus. In Journal of the ACM, volume 43(4), pages 685-722, 1996.
• T.D. Chandra, and S. Toueg. Unreliable failure detectors for reliable distributed systems. In Journal of the ACM, volume 43(2), pages 225-267, 1996.
• M.J. Fischer, N.A. Lynch, and M.S. Paterson. Impossibility of distributed consensus with one faulty process. In Journal of the ACM, volume 32(2), pages 374-382, 1985.
• V. Hadzilacos, and S. Toueg. Fault-tolerant broadcasts and related problems. In Distributed Systems ed. S.J. Mullender, ACM Press & Addison-Wesley, New York, 1993. Expanded version appeared as a Technical Report TR94-1425, Department of Computer Science, Cornell University, Ithaca, NY, 1994.

Chapter 9: Asynchronous Byzantine Agreement

• G. Bracha. An asynchronous [(n_1)=3]-resilient consensus protocol. In Proceedings of the 3rd ACM Symposium on Principles of Distributed Computing (PODC), pages 154-162. 1984.
• S. Toueg. Randomized Byzantine agreements, In Proceedings of the 3rd ACM Symposium on Principles of Distributed Computing (PODC), pages 163-178. 1984.

Chapter 10: 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 11: Graph Algorithms

• 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.
• F. Kuhn and R. Wattenhofer. Constant-Time Distributed Dominating Set Approximation. In Principles of Distributed Computing (PODC), Boston, Massachusetts, USA, July 2003. For a copy, see Publications.

Chapter 12: Distributed Dominating Set Approximation

• L. Jia, R. Rajaraman, and R. Suel. An Efficient Distributed Algorithm for Constructing Small Dominating Sets. In Proceedings of the 20th ACM Symposium on Principles of Distributed Computing (PODC), pages 33-42, 2001.
• F. Kuhn, T. Moscibroda, and R. Wattenhofer. What Cannot Be Computed Locally! In Proceedings of the 23rd ACM Symposium on Principles of Distributed Computing (PODC), 2004. For a copy, see Publications.
• F. Kuhn and R. Wattenhofer. Constant-Time Distributed Dominating Set Approximation. In Proceedings of the 22nd ACM Symposium on Principles of Distributed Computing (PODC), pages 25-32, 2003. For a copy, see Publications.
• F. Kuhn and R. Wattenhofer. Distributed Combinatorial Optimization. Technical Report 426, ETH Zurich, Dept. of Computer Science, 2003. For a copy, see Publications.