Principles of Distributed Computing (SS 2007)

(Network Algorithms)

This page is no longer maintained. Up-to-date 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. We study the fundamental issues underlying the design of distributed systems: communication, coordination, synchronization, uncertainty. We explore essential algorithmic ideas and lower bound techniques.

One of the main themes of recent research in distributed algorithms is "locality" (as utilized by decentralized/peer-to-peer systems). 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 (e.g. Vernetzte Systeme), and fundamentals of algorithms & complexity (e.g. Theoretische Informatik). Note that this course is in both the theory and the distributed systems major.

Course language: English.

News
Written exam: HG F5, 14:00-15:30, August 23, 2006.
Previous exams: SS 03, SS 04.

Lecture by Roger Wattenhofer, Peter Widmayer, Subhash Suri,
Wednesday 8.15-10.00 @ CAB G51.

Exercises by Thomas Locher, Yvonne Anne Oswald, Davide Bilo,
Wednesday 10.15-11.00 @ CAB G52. No exercise meeting: March 21, 2007.

Useful references

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 or 0-262-03141-8
[hkpru]	Disseminatin of Information in Communication Networks Juraj Hromkovic, Ralf Klasing, Andrzej Pelc, Peter Ruzicka, Walter Unger. Springer-Verlag, Berlin Heidelberg, 2005, ISBN 3-540-00846-2
[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.
• N. Lineal. Locality in Distributed Graph Algorithms. In SIAM Journal on Computing 21(1), pages 193-201, 1992.

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: Distributed MST

• Z. Lotker, B. Patt-Shamir, and D. Peleg. Distributed MST for Constant Diamter Graphs. In Proc. 20th Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 63-71, 2001.
• Z. Lotker, E. Pavlov, B. Patt-Shamir, and D. Peleg. MST Construction in O(log log n) Communication Rounds. In Proc. 15th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pages 94-100, 2003.

Chapter 5: Small World

• J. Kleinberg. The Small World Phenomenon: An Algorithmic Perspective. In Proc. 32nd ACM Symposium on Theory of Computing (STOC), 2000.

Chapter 6: 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), p ages 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 7: Shared Variables

• 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), pag es 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 Paral lelism 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 8: 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 9: 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 2 9, 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 CM U-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 Sympo sium on Parallel Algorithms and Architectures, pages 31-36, July 1990.

Chapter 10 - 12: Network Flows I - III

• J. Kleinberg. Detecting a Network Failure. Internet Mathematics , Volume 1(1), pages 37-56, 2003.
• N. Shrivastava, S. Suri, and C. Toth. Detecting Cuts in Sensor Networks. In IPSN '05 , April 25-27, Los Angeles

© 2024 DISCO, TIK, ETH Zurich | Imprint | Last updated: Mon, 31 Aug 2020 21:07.