Uni-Logo
Algorithms and Complexity
 

Network Algorithms
Graduate Course - Summer Term 2013
Fabian Kuhn

 


Course description

Networks and distributed computing are essential in modern computing and information systems. Examples are on the one hand large-scale networks such as the Internet, and on the other hand multiprocessors such as the one in your new multi-core laptop. This course introduces the fundamental principles underlying the design of networks and distributed systems: communication, coordination, fault-tolerance, locality, parallelism, self-organization, symmetry breaking, synchronization, uncertainty. We explore essential algorithmic ideas and lower bound techniques.

Lectures and Exercises

  • Tuesday 10-12 c.t.: 052-02-017
  • Thursday 10-12 c.t.: 052-02-017
Lectures will be on Tuesdays and partly on Thursdays. The rest of the time on Thursdays will be devoted to the discussion of the exercises.

Lecture material

Slides / Recordings

Recordings of the lectures can be found on our webserver.

Date Lecture Notes References
18.04.2013 Introduction
18.04.2013 Chapter 1: Vertex Coloring [peleg] Chapter 7
25.04.2013 Chapter 2: Leader Election [aw] Chapter 3, [hkpru] Chapter 8
30.04.2013 Chapter 3: Tree Algorithms [peleg] Chapter 3-5, [hkpru] Chapter 7
07.05.2013 Chapter 4: Distributed Sorting [leighton] Ch. 1.6 & 3.5, [clrs] Ch. 28
14.05.2013 Chapter 5: Shared Objects
28.05.2013 Chapter 6: Maximal Independent Set [peleg] Chapter 8
11.06.2013 Chapter 7: Dominating Set ---
18.06.2013 Chapter 8: Locality Lower Bounds [peleg] Chapter 7.5
25.06.2013 Chapter 9: Synchronizers [peleg] Ch. 6 & 25, [aw] Ch. 11
02.07.2013 Chapter 10: Social Networks ---
09.07.2013 Chapter 11: Dynamic Networks ---

Exercises

Date Problem Set Solution
25.04.2013 Exercise 1: Vertex Coloring Sample Solution 1
02.05.2013 Exercise 2: Leader Election and Tree Algorithms Sample Solution 2
09.05.2013 Exercise 3: Sorting Networks Sample Solution 3
16.05.2013 Exercise 4: Shared Objects Sample Solution 4
30.05.2011 Exercise 5: Maximal Independent Set Sample Solution 5
13.06.2013 Exercise 6: Dominating Set Sample Solution 6
20.06.2013 Exercise 7: Coloring Rings Sample Solution 7
27.06.2013 Exercise 8: Distributed Network Partitioning Sample Solution 8
11.07.2013 Exercise 9: Dynamic Networks

Books

[peleg] Distributed Computing: A Locality-Sensitive Approach
David Peleg.
Society for Industrial and Applied Mathematics (SIAM), 2000, ISBN 0-89871-464-8
[aw] Distributed Computing: Fundamentals, Simulations and Advanced Topics
Hagit Attiya, Jennifer Welch.
McGraw-Hill Publishing, 1998, ISBN 0-07-709352 6
[hkpru] Dissemination 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
[clrs] Introduction to Algorithms (3rd edition)
Thomas Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein.
The MIT Press, 2009, ISBN 0-262-03384-4

Additional References

Chapter 1: Coloring

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

Chapter 2: Leader Election

  • D. Angluin. Local and global properties in networks of processors. In Proc. 12th ACM Symposium on Theory of Computing (STOC), 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 Objects

  • 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 20th ACM Symposium on Principles of Distributed Computing (PODC), Newport, Rhode Island, August 2001.
  • 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.
  • 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 6: 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) 2009.

Chapter 7: 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. Distributed Computing 17(4), May 2005.
  • F. Kuhn, T. Moscibroda, and R. Wattenhofer. The Price of Being Near-Sighted. 17th ACM-SIAM Symposium on Discrete Algorithms (SODA) 2006.

Chapter 8: 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 10: Social Networks

  • Jon Kleinberg. The small-world phenomenon: an algorithm perspective. In Proceedings of 32nd 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.