Principles of Distributed Computing (FS 2012)
This page is no longer maintained. Uptodate versions of lecture and exercise material can be found here.Distributed computing is essential in modern computing and communications systems. Examples are on the one hand largescale networks such as the Internet, and on the other hand multiprocessors such as your new multicore laptop. This course introduces the principles of distributed computing, emphasizing the fundamental issues underlying the design of distributed systems and networks: communication, coordination, faulttolerance, locality, parallelism, selforganization, symmetry breaking, synchronization, uncertainty. We explore essential algorithmic ideas and lower bound techniques, basically the "pearls" of distributed computing. We will cover a fresh topic every week.
You can take a look at your corrected exam starting from the 3rd of September until the 21st of September. To do so, please visit our secretary Tanja Lantz (office ETZ G88) on Monday, Tuesday, or Friday mornings.
Course prerequisites: Interest in algorithmic problems. (No particular course needed.)
Course language: English.
Lecture by
Roger Wattenhofer, Wednesday 8.1510.00 @ CAB G 51.
Exercises organized by
Philipp Brandes, Wednesday 10.1512.00 @ CAB G 56.
Reading Assignment.
A reading assignment (PDF) complements the course.
The content covered in the assignment will be part of the exam.
Testat.
For the students whose exam question did not meet our criteria, we are offering a third and last chance.
Your task is to create an exam question including a solution for one of the topics. See here for detailed information.
29.05.2012: Revised versions of chapters 10, 11 and 13 are online.
Sample exams: 2003, 2004, 2005, 2006, 2007, 2009
Please note that the topics covered in this course change from year to year and thus some of the questions in those exams are not covered this year.
Lecture material
Title  Lecture Notes  Exercises  Responsible Assistant  References  
Chapter 0 Introduction 
PDF 1:1 PDF 2:1 


Chapter 1 Vertex Coloring 
PDF 1:1 PDF 2:1 
Exercises Solutions 
Philipp Brandes 


Chapter 2 Leader Election 
PDF 1:1 PDF 2:1 
Exercises Solutions 
Philipp Brandes 


Chapter 3 Tree Algorithms 
PDF 1:1 PDF 2:1 
Exercises Solutions 
KlausTycho Förster 


Chapter 4 Distributed Sorting 
PDF 1:1 PDF 2:1 
Exercises Solutions 
Jochen Seidel 


Chapter 5 Shared Memory 
PDF 1:1 PDF 2:1 
Exercises Solutions 
Stephan Holzer 


Chapter 6 Shared Objects 
PDF 1:1 PDF 2:1 
Exercises Solutions 
Jara Uitto 


Chapter 7 Maximal Independent Set 
PDF 1:1 PDF 2:1 
Exercises Solutions 
Stephan Holzer 


Chapter 8 Locality Lower Bounds 
PDF 1:1 PDF 2:1 
Exercises Solutions 
KlausTycho Förster 


Chapter 9 Social Networks 
PDF 1:1 PDF 2:1 
Exercises Solutions 
Philipp Brandes 


Chapter 10 Synchronizers 
PDF 1:1 PDF 2:1 
Exercises Solutions 
Jara Uitto 


Chapter 11 Hard Problems 
PDF 1:1 PDF 2:1 
Exercises Solutions 
Stephan Holzer 


Chapter 12 Stabilization 
PDF 1:1 PDF 2:1 
Exercises Solutions 
Barbara Keller 


Chapter 13 Wireless Protocols 
PDF 1:1 PDF 2:1 
Exercises Solutions 
Philipp Brandes 


Chapter 14 PeertoPeer Computing 
PDF 1:1 PDF 2:1 
Exercises Solutions 
KlausTycho Förster 


All Chapters Principles of Distributed Computing 
PDF 1:1 PDF 2:1 

References
Books:
Articles chapter by chapter:
 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.
 R. Cole and U. Vishkin. Deterministic coin tossing with applications to optimal parallel list ranking. Inform. Comput., volume 70(1), pages 3256, 1986.
 A.V. Goldberg and S. Plotkin. Parallel δ+1 coloring of constantdegree graphs. Inform. Process. Lett., volume 25, pages 241245, 1987.
 N. Linial. Locality in Distributed Graph Algorithms. In SIAM Journal on Computing 21(1), pages 193201, 1992.
 K. Kothapalli, M. Onus, C. Scheideler and C. Schindelhauer. Distributed coloring in O(sqrt{log n}) bit rounds. In IEEE International Parallel and Distributed Processing Symposium (IPDPS), 2006.
 D. Angluin. Local and global properties in networks of processors. In Proceedings of the 12th ACM Symposium on Theory of Computing, 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.
 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 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 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.
 E. W. Dijkstra. Solutions of a problem in concurrent programming control. Commun. ACM, 8(9):569, 1965.
 G. L. Peterson. Myths about the mutual exclusion problem. Inf. Process. Lett., 12:115116, June 1981.
 G. L. Peterson and M. J. Fischer. Economical solutions for the critical section problem in a distributed system. In Proceedings of the 9th ACM Symposium on Theory of Computing, pages 9197, 1977.
 H. Attiya, A. Fouren, E. Gafni. An Adaptive Collect Algorithm with Applications. Distributed Computing, 15(2), 2002.
 M. Moir and J.H. Anderson. WaitFree Algorithms for Fast, LongLived Renaming. Science of Computer Programming, 25(1), October 1995.
 H. Attiya, F. Kuhn, M. Tolksdorf, and Roger Wattenhofer. Efficient Adaptive Collect using Randomization. In Proceedings of the 18th Annual Conference on Distributed Computing (DISC), pages 159173, 2004.
 Y. Afek and Y. De Levie. Space and Step Complexity Efficient Adaptive Collect. In Proceedings of the 19th Annual Conference on Distributed Computing (DISC), pages 384398, 2005.
 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), pages 35, 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 Parallelism 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 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 7: 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 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.
 Jon Kleinberg. The smallworld phenomenon: an algorithm perspective. In Proceedings of the thirtysecond annual 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.
 B. Awerbuch. Complexity of Network Synchronization. Journal of the ACM (JACM), 32(4), October 1985.
 B. Awerbuch and D. Peleg. Network Synchronization with Polylogarithmic Overhead. In Proceedings of the 31st IEEE Symposium on Foundations of Computer Science (FOCS), October 1990.
 Stephan Holzer and Roger Wattenhofer. Optimal Distributed All Pairs Shortest Paths and Applications 31st Annual ACM SIGACTSIGOPS Symposium on Principles of Distributed Computing (PODC), July 2012.
 Silvio Frischknecht, Stephan Holzer, and Roger Wattenhofer. Networks Cannot Compute Their Diameter in Sublinear Time. In 23rd ACMSIAM Symposium on Discrete Algorithms (SODA), January 2012.
 Eyal Kushilevitz and Noam Nisan. Communication Complexity. Cambridge University Press, 1997
 E. W. Dijkstra. Selfstabilizing systems in spite of distributed control. In Communications of the ACM 17(11), 1974, pages 943644
 B. Awerbuch, B. PattShamir and G. Varghese. SelfStabilization By Local Checking and Correction (Extended Abstract). In Proceedings of IEEE Symposium on Foundations of Computer Science (FOCS), 1991, pages 268277.
 E. Goles and J. Olivos. Periodic behavior of generalized threshold functions. Discrete Mathematics 30, 1980, pages 187189.
 P. Winkler. Puzzled. In Communications of the ACM, August 2008.
 M. Gardner. Mathematical Games: The fantastic combinations of John Conway's new solitaire game "Life". Scientific American 223, October 1970, pages 120123.
Chapter 13: 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
Chapter 14: PeertoPeer Computing
 Peter Mahlmann, Christian Schindelhauer. PeertoPeer Networks, Springer, 2007.