|
|
MIT Electrical Engineering and Computer Science
Fall 2002 Catalogue Supplement |
L TR9:30-11, Room 36-155
Prof. Nancy Lynch, Room NE43-365, 3-7225
Prereq.: 6.852 or Permission of Instructor
3-0-9
Qualifies as a subject in Theoretical Computer Science Engineering Concentration
This course is intended for students with some interest in research in the area of distributed algorithms. It presumes that students already know the basics of distributed algorithms, as represented, for example, by the regular MIT distributed algorithms course, 6.852.
The new course will focus on recent research results, with emphasis on distributed algorithms for highly "dynamic" environments such as the Internet or mobile computing systems. In such environments, processes and channels may fail and recover, and may exhibit variations in their timing behavior. Participants in the algorithms may join and leave the system (as well as fail) during the course of computation. Algorithms must adapt to such changes, for example, reconfiguring on-the-fly.
The problem areas that we will emphasize most strongly are:
(1) Communication, including various kinds of multicast (e.g., causal, totally-ordered, atomic), gossiping protocols, and view-oriented group communication.
(2) Distributed data management, including weak and strong consistency guarantees, replicated data management, and quorum-based computing. Other problems we will consider may include failure detection, reaching consensus, resource allocation, performing distributed work, clock synchronization, and namespace management.
This will be a theory course, so we will focus on algorithms for which it is possible to make definite, precise claims about what they do. These claims will include correctness, performance, and fault-tolerance results. We will also consider impossibility results, especially those that express inherent limitations on what can be accomplished in dynamic settings.
The class will meet twice weekly for hour-and-a-half meetings. The course will be based mostly on a series of recent research papers, with each class devoted to discussing one or more papers. Students will be expected to read all the papers, and to help present some of them.