Network Algorithms
Graduate Course - Summer Term 2018
Fabian Kuhn

 

Course description

Most of today's and tomorrow's computer systems are distributed and many of them are built on top of large-scale networks such as, e.g., the Internet, the world wide web, wireless ad hoc and sensor networks, or peer-to-peer networks. This course introduces the fundamental algorithmic principles underlying the design of networks and large-scale (decentralized) 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

• Lecture: Friday 10:15 - 11:45, 101-00-010/14
• Exercise Tutorial: Wednesday 16:15 - 18:00, 101-01-016

To encourage participation and a more interactive lecture, we will not record the lectures. There are however rather detailed written lecture notes for all lectures.

Lecture Notes

Exercises

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 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: 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 3: 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 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.