Massachusetts Institute of Technology Handout 16.852: Distributed AlgorithmsProf. Nancy L ynch Septembe r 8, 2005Course Description: 6.852, Distributed Algorithms1 People and placesInstructor: Prof. Nancy L ynch, 32-G668, MIT extension 3-7225, [email protected] after class a nd by appointment.Teaching assistant: Tina Nolte, 32-G670, MIT extension 3-1 922, [email protected] hours: W4:30-6:30; 32-G670Course secretary: Joanne Talbo t Hanley, 3 2-G672A, MIT extension 3-6054Class meetings: Tuesdays and Thursdays, 9:30-11:00AM in roo m 2-190.Web site and mailing list: We will set up a course mailing list. Please send email right away to Tina,at [email protected], to join this lis t.The course Web site is at URL http://theory.lcs.mit.edu/cla sses/6.852/05. This site will contain download-able co pies of course handouts and re lated research papers, and other informa tio n about the course.2 What this course is aboutThe field of distributed algorithms has become a well-developed research area over the past 25 years. Itsresults appear in specialized research conferences such as PODC (Principles Of Distributed Computing)and DISC (International Sympos ium on DIStributed Computing), a nd in general conferences involving dis-tributed computing.Distributed algorithms researchers define models for various kinds o f distributed computing environments,define problems to be solved in those environments, including performance and fault-tolerance requirements,design new distributed algorithms to solve these problems, and analyze the correctness and performance ofthese algorithms. They also sometimes prove lower bounds and other impossibility results, which explainwhy certain tasks canno t 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 distr ibutedsystems, including problems of communication, data management, res ource management, synchronization,and distributed agreement.Because distributed computing theory is a branch of theoretical computer science, the work is suppo sed tobe mathematically rigoro us ; however, you will find that preliminary papers in this area are often writtensomewhat informally.6.852 is a graduate-level co urse that is intended to do two things:1. Provide an introduction to the most important basic results in the area of distributed algorithms.2. Prepare interested students to begin independent research or take a more a dvanced course in distributedalgorithms.Usually, the students who take the course are a mixture of PhD students and MEng students. The courseis run at a graduate level, which means that most MEng students will probably find it challenging (andtime-consuming).Handout 1: Course Description: 6.852, Distributed Algorithms 23 PrerequisitesTo take 6.852, you should have:• “Mathematical maturity”. In particular, you s hould 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.• (Desirable, but not essential) Experience with formal mo dels of computation. MIT’s course 6.045 onautomata theory would be fine for this.4 Source materialThe main source will be the book Distribut ed Algorithms by Nancy Lynch. See the course Web site for someinformation on finding and purchasing the book. Quantum Books has ordered copies for us.The latest printing of the book is the fifth printing, but this is identical to the fourth printing. The fourthprinting contains only a few corrections over the third printing, so using a third printing copy would also beOK. Known errata for early printings are c ollected in err ata lists, which are accessible from the course Webpage. The boo k refers to many papers from the research literatur e on distributed algorithms; you mightwant to track down and read some of these.Other boo ks 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 styleof Attiya and Welch’s book is less formal.• Shlomi Dolev . Self-Stabilization, MIT Press , 2000. This gives a good description of self-stabilizingdistributed alg orithms. Self-sta bilization is one kind of fault-toler ance, which we will study near theend of the course.Both books are on reserve in the CSAIL Rea ding Room, 32-G882 and at B arker Engineering Library, 10-500.In addition, some rese arch papers that are not covered in the textbook will be covered in class and on problemsets. They will cover a variety of topics, for example, computability a nd relative computability results fordifferent kinds of objects and services, in the presence of various numbers of fa ilures. These papers are listedin Ha ndout 3. We will put instructions for obtaining these on the course Web site.5 Course requirements5.1 ReadingsReadings that cover the material for each cla ss will be announced ahead of time. For most cla sses, these willbe sec tio ns from the textbook. For some classes, however, these will be research papers from the readinglist, Handout 3. Reading a research paper will generally take more time than reading sections fro m thetextbook—so be prepared to put in the extra time.We expect students to read the as signed material ahead of time, and to come to class prepared with questionsand discussion ideas.Handout 1: Course Description: 6.852, Distributed Algorithms 35.2 Problem setsThese are intended to help you to under stand the material being covered in class. Most problems will involvethinking about algorithms a nd problems already covered in class; some will be designed to get you startedthinking ab out ideas to be discussed in later classes.Specifically, approximately five problems will be given out approximately every Thursday. The problems willbe batched and due every two weeks, at the beginning of class on alternate Thursdays. (Note exceptionsto these rules on the