Principles of Distributed Computing (SS 2004)
This page is no longer maintained. Uptodate versions of lecture and exercise material can be found here.
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
peertopeer computing). Networks grow fast, thus locality and
scalability become firstclass issues. We discuss some of the most
fascinating local distributed algorithms in the second part of the
course.
Course prerequisites: Basic networking knowledge (Vernetzte Systeme
37019), and fundamentals of algorithms & complexity
(Theoretische Informatik 37402). Note that this course is in both
the theory and the distributed systems major.
Course language: English
Lecture by
Roger Wattenhofer,
Wednesday 8.1510.00 @ HRS F5.
A corrected version of Chapter 11 is now online.
Exercises by
Fabian Kuhn,
Regina O'Dell,
Wednesday 10.1511.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.
Books:
[attiya]

Distributed Computing: Fundamentals, Simulations and Advanced Topics
Hagit Attiya, Jennifer Welch.
McGrawHill Publishing, 1998, ISBN 007709352 6


[clr]

Introduction to Algorithms
Thomas Cormen, Charles Leiserson, Ronald Rivest.
The MIT Press, 1998, ISBN 0262530910 oder 0262031418


[leighton]

Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes
Frank Thomson Leighton.
Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991, ISBN 1558601171


[peleg]

Distributed Computing: A LocalitySensitive Approach
David Peleg.
Society for Industrial and Applied Mathematics (SIAM), 2000, ISBN 0898714648

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 3256, 1986.
 A.V. Goldberg and S. Plotkin. Parallel δ+1 coloring of constantdegree graphs. Inform. Process. Lett., volume 25, pages 241245, 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 8293, 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 extremafinding in circular configurations of processors. In Communications of the ACM 23(11), pages 627628, November 1980.
 G. LeLann. Distributed systems, towards a formal approach. In IFIP Congress Proceedings, pages 155160, 1977.
Chapter 3: Tree Algorithms
 D. Bertsekas and R. Gallager. Data Networks. 2nd Edition. PrenticeHall International, London, 1992.
 Y.K. Dalal and R.M. Metcalfe. Reverse path forwarding of broadcast packets. Communications of the ACM, volume 12, pages 10401048, 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 79133, 1994.
 R.G. Gallager. Distributed minimum hop algorithms. Technical Report LIDSP1175, Lab. for Information and Decision Systems, MIT, Cambridge, MA, January 1982.
Chapter 4: Routing
 C. Busch, M. Herlihy, and R. Wattenhofer. HardPotato 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 HotPotato Routing. In Proceedings of the 11th Annual ACMSIAM Symposium on Discrete Algorithms (SODA), pages 458466, San Francisco, California, January 2000. For a copy, see Publications.
 D. Krizanc, S. Rajasekaran, and T. Tsantilas. Optimal routing algorithms for meshconnected 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 411422. SpringerVerlag, 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 210, 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 263277, May 1981.
Chapter 5: Basic Network Topologies
 F. Preparata and J. Vuillemin. The cubeconnected cycles: a versatile network for parallel computation. In Communications of the ACM, 24(5), pages 300309, May 1981.
 J. Schwartz. Ultracomputers. In ACM Transactions on Programming Languages and Systems, 2(4):484521, 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 130145, 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 CMUCS96152, 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 3136, 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 35, 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 321359, 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: FaultTolerant 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 685722, 1996.
 T.D. Chandra, and S. Toueg. Unreliable failure detectors for reliable distributed systems. In Journal of the ACM, volume 43(2), pages 225267, 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 374382, 1985.
 V. Hadzilacos, and S. Toueg. Faulttolerant broadcasts and related problems. In Distributed Systems ed. S.J. Mullender, ACM Press & AddisonWesley, New York, 1993. Expanded version appeared as a Technical Report TR941425, 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 154162. 1984.
 S. Toueg. Randomized Byzantine agreements, In Proceedings of the 3rd ACM Symposium on Principles of Distributed Computing (PODC), pages 163178. 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 19, April 1983.
 J. Aspnes, M.P. Herlihy, and N. Shavit. Counting Networks. In Journal of the ACM, 41(5): pages 10201048, September 1994.
 K. Batcher. Sorting networks and their applications. In Proceedings of the AFIPS Spring Joint Computing Conference, volume 32, pages 307314, 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 neighborsort (or the glory of the induction principle). Technical Report AD759 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 3136, July 1990.
 M. Klugerman, C. Greg Plaxton: SmallDepth Counting Networks.In STOC 1992. pages 417428.
 K. Sado and Y. Igarashi. Some parallel sorts on a meshconnected processor array and their time efficiency. In Journal of Parallel and Distributed Computing, volume 3, pages 398410, 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 7780. 1986.
 F. Kuhn and R. Wattenhofer. ConstantTime 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 3342, 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. ConstantTime Distributed Dominating Set Approximation. In Proceedings of the 22nd ACM Symposium on Principles of Distributed Computing (PODC), pages 2532, 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.