Uni-Logo
Algorithms and Complexity
 

Network Algorithms
Graduate Course - Summer Term 2012
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.

Based on the doodle poll, the two additional meetings to discuss exercises and questions about the course will be
  • Thursday 23.8.2012, 14:00 s.t., room 101-01-018
  • Tuesday 28.8.2012, 14:00 s.t., room 101-01-018
 For more urgent questions, feel free to contact me by email.

Lectures

  • Tuesday 8-10 c.t.: 101-01-018
  • Wednesday 12-13 c.t.: 101-01-018

Exercises

  • Wednesday 13-14 c.t.: 101-01-018

Lecture material

Date Lecture Notes References
24.04.2012 Introduction
24.04.2012 Chapter 1: Vertex Coloring [peleg] Chapter 7
08.05.2012 Chapter 2: Leader Election [aw] Chapter 3, [hkpru] Chapter 8
15.05.2012 Chapter 3: Tree Algorithms [peleg] Chapter 3-5, [hkpru] Chapter 7
22.05.2012 Chapter 4: Shared Objects
05.06.2012 Chapter 5: Distributed Sorting [leighton] Ch. 1.6 & 3.5, [clrs] Ch. 28
12.06.2012 Chapter 6: Maximal Independent Set [peleg] Chapter 8
19.06.2012 Chapter 7: Dominating Set ---
26.06.2012 Chapter 8: Locality Lower Bounds [peleg] Chapter 7.5
27.06.2012 Chapter 9: Social Networks ---
03.07.2012 Chapter 10: Wireless Protocols ---
24.07.2012 Chapter 11: Dynamic Networks ---

Exercises

Date Problem Set Solution
25.04.2012 Exercise 1: Vertex Coloring Sample Solution 1
09.05.2011 Exercise 2: Leader Election Sample Solution 2
16.05.2011 Exercise 3: Tree Algorithms Sample Solution 3
23.05.2011 Exercise 4: Shared Objects Sample Solution 4
06.06.2011 Exercise 5: Distributed Sorting Sample Solution 5
13.06.2011 Exercise 6: Maximal Independent Set Sample Solution 6
20.06.2011 Exercise 7: Dominating Set Sample Solution 7
03.07.2011 Exercise 8: Social Networks Sample Solution 8
24.07.2011 Exercise 9: Dynamic Networks Sample Solution 9

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: 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 5: 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 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 9: 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.

Chapter 10: Wireless Protocols

  • K. Nakano and S. Olariu. Randomized O(log log n)-Round Leader Election Protocols in Packet Radio Networks. In International Symposium on Algorithms and Computation (ISAAC), 1998
  • T. Hayashi, K. Nakano, and S. Olariu. Randomized Initialization Protocols for Packet Radio Networks. In International Parallel Processing Symposium, Symposium on Parallel and Distributed Processing (IPPS/SPDP), 1999.
  • K. Nakano and S. Olariu. Uniform Leader Election Protocols for Radio Networks. In IEEE Trans. Parallel Distrib. Syst., 2002, pages 516-526.
  • D. Willard. Log-Logarithmic Selection Resolution Protocols in a Multiple Access Channel. In SIAM J. Comput., 1986, pages 468-477

Chapter 11: Dynamic Networks

  • F. Kuhn, N. Lynch, and R. Oshman. Distributed Computation in Dynamic Networks. In Proceedings of the 42nd Symposium on Theory of Computing (STOC), Cambridge, MA, USA, June 2010.
  • 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.