Network Algorithms
Graduate Course  Summer Term 2015
Fabian Kuhn
Course description
Most of today's and tomorrow's computer systems are distributed and many of them are built on top of largescale networks such as, e.g., the Internet, the world wide web, wireless ad hoc and sensor networks, or peertopeer networks. This course introduces the fundamental algorithmic principles underlying the design of networks and largescale (decentralized) distributed systems: communication, coordination, faulttolerance, locality, parallelism, selforganization, symmetry breaking, synchronization, uncertainty. We explore essential algorithmic ideas and lower bound techniques.
Exam
Chapter 12 (on network coding) will not part of the exam.
A Q&A session will be held on Friday, Sep. 4, 2015. The session will take place from 10:15  12:00 in room 10600007.
Lectures and Exercises
 Tuesday 10:15  14:00, 10101016 Lectures will typically be between 10:15 and 12:30, exercise tutorials will take place afterwards.
To encourage participation and a more interactive lecture, we will not record the lectures this year. There are however rather detailed written lecture notes for all lectures.
It is not mandatory to hand in exercise solutions or to attend the exercise tutorials in order to be admitted to the exam. However, it is of course highly recommended to carefully do the exercises! If you plan to hand in your solutions, they are supposed to be handed in either as hard copied or electronically by sending an Email to Hamid Ghodselahi (hghods@cs.unifreiburg.de) in the week following the release date of exercise sheet.
Lecture Notes
Date  Lecture Notes  References  
21.04.2015  Introduction  
21.04.2015  Chapter 1: Vertex Coloring  [peleg] Chapter 7  
28.04.2015  Chapter 2: Tree Algorithms  [peleg] Chapter 35, [hkpru] Chapter 7  
05.05.2015  Chapter 3: Leader Election  [aw] Chapter 3, [hkpru] Chapter 8  
12.05.2015  Chapter 4: Shared Objects  
19.05.2015  Chapter 5: Distributed Sorting  [leighton] Ch. 1.6 & 3.5, [clrs] Ch. 28  
02.06.2015  Chapter 6: Maximal Independent Set  [peleg] Chapter 8  
09.06.2015  Chapter 7: Locality Lower Bounds  [peleg] Chapter 7.5, Linial's Lower Bound Made Easy 

16.06.2015  Chapter 8: Synchronization  [peleg] Ch. 6 & 25, [aw] Ch. 11  
23.06.2015  Chapter 9: Hard Problems  
30.06.2015  Chapter 10: Wireless Protocols  
07.07.2015  Chapter 11: Dynamic Networks  
14.07.2015  Chapter 12: Network Coding  
Exercises
Date  Problem Set  Solution  
22.04.2015  (updated) Exercise 1: Vertex Coloring  Sample Solution 1  
28.04.2015  Exercise 2: Tree Algorithms  Sample Solution 2  
05.05.2015  Exercise 3: Leader Election  Sample Solution 3  
12.05.2015  Exercise 4: Shared Objects  Sample Solution 4  
20.05.2015  Exercise 5: Distributed Sorting  Sample Solution 5  
02.06.2015  Exercise 6: Maximal Independent Set  Sample Solution 6  
09.06.2015  Exercise 7: Locality Lower Bounds  Sample Solution 7  
16.06.2015  Exercise 8: Synchronization  Sample Solution 8  
23.06.2015  Exercise 9: Hard Problems  Sample Solution 9  
30.06.2015  Exercise 10: Wireless Protocols  Sample Solution 10  
07.07.2015  Exercise 11: Dynamic Networks  Sample Solution 11  
Books
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 3256, 1986.
 A.V. Goldberg and S. Plotkin. Parallel (Δ+1)coloring of constantdegree graphs. In Inform. Process. Lett. 25, pages 241245, 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 193201, 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: 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 Appl. Mathematics, volume 53, pages 79133, 1994.
 R. G. Gallager, P. A. Humblet, and P. M. Spira. Distributed Algorithm for MinimumWeight Spanning Trees. In ACM Transactions on Programming Languages and Systems (TOPLAS), 5(1):6677, January 1983.
Chapter 3: Leader Election
 D. Angluin. Local and global properties in networks of processors. In Proc. 12th ACM Symposium on Theory of Computing (STOC), 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 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 35, 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 3213 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 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 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 7780, 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):567583, 1986.
 Y. Métivier, J.M. Robson, N. SahebDjahromi, and A. Zemmari. An Optimal Bit Complexity Randomised Distributed MIS Algorithm. 16th International Colloquium on Structural Information and Communication Complexity (SIROCCO) 2009.
Chapter 7: 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: 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 516526.
 D. Willard. LogLogarithmic Selection Resolution Protocols in a Multiple Access Channel. In SIAM J. Comput., 1986, pages 468477