Massachusetts Institute of Technology Handout 16.852: Distributed AlgorithmsProf. Nancy Lynch February 5, 2008Course Description: 6.852, Distributed Algorithms1 People and placesInstructors: Prof. Nancy Lynch, 32-G668, MIT extension 3-7225, [email protected]; Availableby app ointment (Tuesday and Thursday afternoons are good.)Dr. Victor Luchangco, Sun Microsystems, 32-G628, MIT extension 3-0309, [email protected] by app ointment (Tuesday and Thursday afternoons are best).Teaching assistant: Calvin Newport, 32-G670, MIT extension 3-1922, [email protected] hours: T4:00-6:00; 32-G6 LoungeCourse secretary: Joanne Talbot Hanley, 32-G672A, MIT extension 3-6054Class meetings: Tuesdays and Thursdays, 11:00AM - 12:30PM in room 4-149Web site and mailing list: We will set up a course mailing list. Please send email right away to Calvin,at [email protected], to join this list.The course Web site is at URL http://courses.csail.mit.edu/6.852/08/ This site will contain downloadablecopies of course handouts and related research papers, and other information about the course.2 What this course is aboutThe field of distributed algorithms has become a well-develop e d research area over the past 25-30 years. Itsresults appear in specialized research conferences such as PODC (Principles Of Distributed Computing),DISC (International Symposium on DIStributed Computing), OPODIS (International Conference on Princi-ples of Distributed Systems), and SPAA(ACM Symposium on Parallelism in Algorithms and Architectures),in general theoretical computer science conferences such as FOCS (Foundations of Computer Science) andSTOC (Symposium on Theory of Computing), and in broad conferences involving distributed computing,such as ICDCS (International C onference on Distributed Computing Systems).Distributed algorithms researchers define various kinds of distributed computing environments, such asshared-memory or network-based environments, and identify problems to be solved in those environments.They design new algorithms for these problems, and analyze the correctness, performance, and fault-toleranceof their algorithms. They also sometimes prove lower bounds and other impossibility results, which explainwhy certain tasks cannot be carried out in certain kinds of distributed settings, or cannot be carried outwithin certain cost constraints. Researchers typically study problems that arise in practical distributedsystems, including problems of communication, data management, resource management, synchronization,and distributed agreem ent. Sometimes, the results have impact on practical distributed system design.This year, the course will be co-taught by Prof. Lynch and Dr. Victor Luchangco, a member of the ScalableSystems research group at Sun Microsystems Research. The “core” of the material will be the same asusual—basic distributed algorithms and impossibility results. However, we are adding a few new things thisyear:1. A unit on scalable shared-memory concurrent programming.Handout 1: Course Description: 6.852, Dis tributed Algorithms 22. Some supplementary material on topics such as self-stabilization, wait-free computability, and failuredetectors.3. The Tempo toolset, for writing distributed algorithm pseudocode.6.852 is a graduate-level course that is intended to do two things: provide an introduction to the mostimportant basic results in the area of distributed algorithms, and prepare interested students to beginindependent research or take a more advanced course in distributed algorithms. Usually, the students whotake the course are a mixture of PhD students and MEng students. Since the course is run at a PhD level,most MEng students should find it challenging (and time-consuming).3 PrerequisitesTo take 6.852, you should have:• “Mathematical maturity”. In particular, you should be very good at reading and writing mathematicalproofs.• General knowledge about some distributed systems. For instance, MIT’s undergraduate course 6.033,Computer Systems Engineering, would be good background.• Experience with sequential algorithms and their analysis. MIT’s undergrad course 6.046 is sufficient.• (Des irable, but not essential) Experience with formal models of computation. MIT’s course 6.045 onautomata theory would be fine for this.4 Source materialThe primary source will be the book Distributed Algorithms by Nancy Lynch. See the course Web site forsome information on finding and purchasing the book. Quantum Books has ordered copies for us. This bookhas gone through many printings, but we have made no changes since the fourth printing, so fourth or laterare just fine. (In fact, the fourth printing contains only a few corrections over the third printing, so using athird printing copy would also be OK.) Known errata for early printings are collected in errata lists, whichare accessible from the course Web page. The book refers to many papers from the research literature ondistributed algorithms; you might want to track down and read some of these.The secondary source will be the new book, T he Art of Multiprocessor Programming, by Profs. MauriceHerlihy and Nir Shavit (who work at Sun Research). This book is expec ted to be published (by Else-vier) mid-semester. However, the authors have, in the meantime, made a pdf of a book chapter availablefor download at courses.csail.mit.edu/6.852/08/papers/lists-book-chapter.pdf. Publisher info athttp://www.elsevier.com/wps/find/bookdescription.cws_home/714091/.Other books that you will find useful are:• Hagit Attiya and Jennifer Welch Distributed Computing: Fundamentals, Simulations, and AdvancedTopics. John Wiley and Sons, Inc., 2004. Second Edition.This is another textbook on distributed algorithms, initially published a little after the Lynch book.It now has a second edition. The material covered overlaps quite a lot with the Lynch book, thoughAttiya and Welch do cover some topics, like clock synchronization, that Lynch doesn’t cover. The styleis a little less formal.• Shlomi Dolev. Self-Stabilization, MIT Press, 2000. This gives a good description of self-stabilizingdistributed algorithms. Self-stabilization is a strong kind of fault-tolerance, which we will study nearthe end of the course.Handout 1: Course Description: 6.852, Dis tributed Algorithms 3Both books are on reserve in the CSAIL Reading Room, 32-G882 and at Barker Engineering Library, 10-500.In addition, some research papers that are not covered in the