Distributed computing systems have become pervasive. From clusters to internet-worked computers, to mobile machines, distributed systems are being used to support a wide variety of applications. This course will focus on the fundamental concepts in distributed computing systems enabling such applications. The following are the objectives of this course:
These goals are achieved as follows. First, class sessions cover a set of
papers that discuss basic principles in distributed systems. Principles covered
in the course include global states of distributed computations, logical and
physical clocks, and failure models. Distributed algorithms for consensus,
replicated state management, and resource finding are also covered. Midterm and
final exams feature questions on the papers covered in class. A second element
of the class exposes students to representative development environments and
infrastructures for distributed systems. This includes wide area applications
and infrastructures (e.g., using Websphere or its open source counterparts on
Internet-linked systems), high performance applications or algorithms across
high end machines and network links (e.g., using Georgia Tech's cluster
machines and facilities), mobile applications running on pervasive platforms
(e.g., using representative pervasive systems at Georgia Tech or the MobiEmu
emulation platform), and peer to peer systems or applications running on PlanetLab.
Programming projects evaluate students' knowledge for this class component. A
third element of the class introduces students to rigorous academic research,
where for a specific topic and some set of papers covered in class, each
student selects a set of recent papers in a certain area, and produces a short
term paper describing the problems and results discussed in those papers. These
summaries are shared with all students, and they are presented in class. There
is considerable flexibility in defining class projects and topics for term
papers. Concerning projects, students can formulate their own, and depending on
the nature of the project, they can work in groups. Term papers are worked on
individually, but their topics may be linked to class projects.
After successfully completing this course, students should be ready to explore research problems in distributed systems and on emerging applications deployed in such systems. This rigorous course requires strong class participation, and part of a student's grade is derived from class presentations.
CS 4210 or equivalent. Graduate standing strongly suggested.
30% Examinations
15% Term Paper
40% Programming Project
15% Class Participation
Note that a passing grade is required in each of the above components in
order to pass the class.
กก
Term Paper Requirement: 6 pages min, 8 pages max, due Wednesday April 26th
Journal and conference papers listed above will be made available. Some useful background appears in the Mullender and Singhal textbooks on distributed computing.
The following papers on the listed topics will be discussed in class. Other related papers will be assigned for reading. Homework will include material from papers assigned for reading. For papers without links, you should be able to download them from ACM Digital Library or IEEE Xplore through GATech Library.
1. M. Raynal and M. Singhal. Logical Time: A Way to Capture Causality in Distributed Systems. IRISA Technical Report.
2. David Mills. Network Time Protocol, RFC 1305.
3. Jeremy Elson, Lewis Girod, and Deborah Estrin, Fine-Grained Network Time Synchronization Using Reference Broadcasts, OSDI 2002.
4. Chandy, M. and Lamport, L., Distributed Snapshots: Determining Global States of Distributed Systems, ACM Trans. on Computer Systems, February 1985.
5. Schwarz, R. and Mattern, F., Detecting Causal Relationships in Distributed Systems: In Search of the Holy Grain, Distributed Computing, 1994.
Term Paper Topics: Distributed Checkpointing/Recovery, Clock Synchronization Algorithms.
Background reading: Danny Dolev, Cynthia Dwork and Larry Stockmeyer, On the Minimal Synchronism Needed for Distributed Consensus, JACM, January 1987.
1. Survey of failures in distributed systems (ch. 2, Mullender)
2. M. J. Fischer, N. Lynch and M. S. Patterson, Impossibility of distributed consensus with one faulty process, JACM 32, 1985.
3. Tushar Deepak Chandra, Vassos Hadzilacos and Sam Toueg; The weakest failure detector for solving consensus, JACM 43, 4 (Jul. 1996), Pages 685 - 722.
4. M. Castro, B. Liskov, Practical Byzantine Fault Tolerance, OSDI, Feb. 1999.
Sample systems: we
will study one of them in some detail:
Cox et al., Pastiche:
Making Backup Cheap and Easy, OSDI 2002.
Abd-El-Malek, Ganger, Fault-Scalable
Byzantine Fault-Tolerant Services, SOSP 2005.
Dunagan et al, Fuse:
Light-weight Distributed Failure Notification, OSDI 2004.
Term Paper Topics: Byzantine Failures, Costs of Consensus in Synchronous Systems, Probabilistic Consensus.
1. Ken Birman, Andre Schiper and Pat Stephenson, Lightweight Causal and Atomic Multicast, ACM TOCS, August 1991.
2. David Cheriton and Dale Skeen, Understanding the Limitations of Causally and Totally Ordered Communication, ACM SOSP, December 1993.
Systems:
K. Birman et. al., Bimodal Multicast,
ACM TOCS.
Papers on DHTs, gossiping algorithms and their implementation:
Trickle/Stanford, PlanetP/Rutgers, and DHTs:
Frank Dabek, M. Frans Kaashoek, David Karger, Robert Morris, Ion Stoica. Wide-area cooperative
storage with CFS, SOSP 2001.
Muthitacharoen et al., Ivy: A Read/Write
Peer-to-Peer File System, OSDI 2002.
Term Paper Topics: Reliable Multicast Protocols, Virtual Synchrony, Group Communication Systems, Real-time or other constraints. Publish/subscribe systems (e.g., Gryphon)
Background: F.
Torres, M. Ahamad and M. Raynal, Timed Consistency
for Shared Distributed Objects , PODC 1999.
1. F. B. Schneider, Implementing Fault-tolerant Services Using the State Machine Approach: A Tutorial, Computing Surveys, 1990.
2. Gifford, D., Weighted Voting for Replicated Data, ACM Symp. on Operating Systems Principles, December 1979.
3. Malkhi, D. and Reiter, M. Byzantine Quorum Systems , Journal of Distributed Computing, 1998.
4. Terry, D. B. et. al., Session guarantees for weakly consistent replicated data, 1994 PDIS.
5.
Ahamad, M. and Kordale, R. Scalable
Consistency Protocols for Distributed Services IEEE Transaction on Parallel
and Distributed Systems. 1999.
(Background reading: Mustaque Ahamad, Jim Burns, Phillip Hutto, Prince Kohli
and Gil Neiger, Causal Memory, Distributed Computing, 1995.)
Systems using such services:
H. Yu and A. Vahdat. The Costs and
Limits of Availability of Replicated Services , SOSP 2001.
Danco Davcev and W.A. Burkhard. Consistency and Recovery Control for
Replicated Files. In Proc. 10th ACM SOSP 1985. (likely to be skipped).
Karin Petersen, Mike J. Spreitzer, Douglas B. Terry, Marvin M. Theimer and
Alan J. Demers, Flexible update propagation for weakly consistent
replication.
SOSP 1997 Pages 288-301.
Term Paper Topics: Scalable Consistency Protocols, Update conflict detection/resolution, consistency protocols with constraints (e.g., timing, location, ...).
1. Mullender, S., Vitany, P., Distributed Match-Making, Algorithmica, No.3, 1988.
2. Steen, M., Hauck, F., Homburg, P. and Tanenbaum, A. Locating objects in wide-area systems. IEEE Communications Magazine.
3.
Stoica,
4. David G. Andersen, Hari Balakrishnan, M. Frans Kaashoek, Robert Morris. Resilient Overlay Networks. Proc. 18th ACM SOSP, Banff, Canada, October 2001.
5.
Landon P. Cox, Christopher D. Murray, and Brian D. Noble,
Pastiche: Making Backup Cheap and Easy, OSDI 2002.
Other P2P Systems:
P2P
( Farsite,
Samsara,
Eigentrust
and Strategyproof
Mechanisms)
กก
Term Paper Topics: Naming, Infrastructures
for P2P, Structured and Unstructured Overlays, Constructing Distributed Systems
and Applications (e.g., Pastry, Tapestry), FreeNet, Gnutella spec, P2P
1. Badrinath et. al., Designing Distributed Algorithms for Mobile Computing Networks. ICDCS.
2. M. Satyanarayanan, Fundamental Challenges in Mobile Computing, PODC 1995.
3. L. B. Mummert, M. R. Ebling and M. Satyanarayanan, Exploiting weak connectivity for mobile file access. SOSP 1995 Pages 143-155.
Term Paper Topics: Algorithms adapted to mobile systems (e.g., radio issues, connectivity (e.g., reliable multi-hop routing), coordination in sensor networks, real-time communication and coordination, location managem ent, end-to-end connectivity, structured (i.e., topologies) vs. unstructured (gossiping) communication, incentive-based approaches, ...).
1. Lampson, B., Abadi, M. and Burrows, M, Authentication in Distributed Systems: Theory and Practice , ACM Transactions on Computer Systems, 1992.
2. M. Kaminsky, G. Saviddes, D. Mazieres and M. F. Kaashoek, Decentralized User Authentication in a Global File System , SOSP 2003.
Fine-Grained Network Time Synchronization Using Reference Broadcasts
Logical Time: A Way to Capture Causality in Distributed Systems
Fuse: Light-weight Distributed Failure Notification
Lightweight Casual and Atomic Multicast
Understanding the Limitations of Causally and Totally Ordered Communication
Session guarantees for weakly consistent replicated data
Pastiche: Making Backup Cheap and Easy
Guidelines
The purpose of a student-defined project is to (1) involve you in ongoing research projects, (2) leverage your unique background in some way, and/or (3) leverage other work in which you are involved. In general, any special project should be of a caliber that can generate results publishable in reviewed outlets like workshops or conferences (often requiring some additional work beyond the time spent in this class). You may link your project work with the topics investigated in the term papers, but both are separate deliverables.
Proposals
To propose your project for this class, you must submit the following materials:
The first step must include both development (e.g., coding, experimentation) and background work, such as producing a bibliography of relevant papers and having read them, having designed suitable algorithms/approaches, and having learned or looked at suitable tools to be used for your project, including target platforms.
The second step, typically after the class midterm, should involve having produced much of the software necessary and having debugged it.
The third step should include not only software testing but also evaluation, on the platforms you have chosen. Such evaluations may include theoretical results if you choose to develop or experiment with a novel algorithm, for instance, but it should also include experimental results.
The final deliverable not only includes the actual software but also a report, which is outlined next.
Final Report
The on-line final report regarding your project should have the following parts:
Facilities Available for CS7210 Projects
1. 'Hack' cluster (physically part of the NetLab facility described under 2. below):
Contact Sanjay Kumar (ksanjay) or Ivan Ganev (ganev@cc) for details on hardware/software setup.
2. NetLab cluster machine: cluster of over 40 machines, able to emulate arbitrary Internet topologies and able to run multiple operating systems. Also able to run mobile system emulations using the MobiEmu support infrastructure.
Contact Himanshu Raj (rhim@cc) or Sanjay Kumar (ksanjay@cc) for more information and machine access.
3. High end cluster facilities, one comprised of 30 dual Itanium IIs, the other comprised of over 50 dual 64-bit PIVs.
Contact Matt Wolf (mwolf@cc) for more information and machine access.
4. 'Enterprise' computing clusters: a typical 3-tier setup using an IBM blade server as a backend and HP and IBM and workstations as frontends.
Contact Mohammed Mansour (mansour@cc) for more detail and/or for hardware access.
5. Handheld computers using wireless links, including Compaq iPAQ and XScale-based (Sitsang) machines.
Contact Ripal Nathuji (rnathuji@cc) for additional information.
6. Embedded communication subsystems, using Intel's IXP2400 network routers on a small cluster machine:
Contact Ada Gavrilovska (ada@cc) for more information on IXPs.
7. For research involving high performance systems or graphics, large-scale visualization media, including an Immersadesk, a video wall, an Access Grid node, and potential access to high end network links connecting Georgia Tech with remote institutions.
Contact Matt Wolf (mwolf@cc) for more information.
8. Special hardware, including virtualization-capable (VT instruction set) and multi-core machines.
Contact Himanshu Raj (rhim@cc) or Matt Wolf (mwolf@cc) for more information.
Sample Projects
These are simply some ideas that came to my mind. You are NOT bound by these ideas. In fact, I'd welcome alternative ideas, especially those involving other infrastructures like Chord, Pastry, ... or those involving innovative distributed algorithms or methods:
1. Experiment/work with Microsoft's .net infrastructure. For instance, first use its SOAP remote invocation functionality, then enhance it to improve SOAP performance. Enhancements are possible along two directions: 1) work with other students to design a new implementation of the SOAP protocol based on an open source release associated with Apache (contact bala@cc for more information), then (2) further extend its ability to deal with larger application data.
2. Work with realistic enterprise system infrastructures, such as IBM's Websphere or open source products like JBOSS, or SOAP implementations. Sample work with such infrastructures involves changing their key communication primitives (e.g., making RMI network aware) or developing or enhancing applications that require their rich functionality (contact mansour@cc or sandip@cc).
3. Industry developments in middleware involve three different support infrastructures, one being the Java-based approaches like Websphere, another centered around .net, and a third focused the publish/subscribe model of communication. Our research group has been developing a high performance pub/sub infrastructure, termed ECho, which has recently been extended to make it easier to create efficient very large scale pub/sub applications and to create new failure recovery methods. The extensions makes it easier to dynamically create overlay networks mapped to appropriate machines and network links. They also make it easy to create new methods for dealing with failures, including those studied in this class. Students can perform a wide variety of projects, including (1) automatic generation of and management of certain pub/sub functionality (e.g., the operators applied to the events traversing the overlay network) (contact lofstead@cc or vibhore@cc, the former experimenting with XML-based representations of such operators and the latter involved with database operator-like formulation; (2) algorithms to create and update overlay networks, based on network feedback (contact ztcai@cc) or based on other resource monitoring (contact sandip@cc) or formulations of distributed trust (contact ramesh@cc) or dealing with failures (contact vibhore@cc); and (3) new applications that utilize the rich middleware functionality provided by the overlay or pub/sub models (contact the instructor). Also of interest are uses of infrastructures like these in mobile systems (e.g., with the robotics applications we are studying jointly with Tucker Balch) (contact kjohara@cc for more information).
4. Develop sample distributed applications. Most interesting are: (1) ubiquitous or embedded applications that involve both real-time sensing and reactions to sensor data and/or use portable or mobile machines, (2) experimentation with adaptive applications, including video transfers (raw video or MPEG/SPEG encoded) and evaluating their ability to run on wireless and embedded devices and systems, (3) innovative distributed applications including video games, remote robot control, immersive systems, using real-time feeds (e.g., gotten from Atlanta's traffic web pages or from sports actions) and/or large data sets (e.g., earth observational data). Propose to instructors and also contact mwolf@cc or eisen@cc for information or project ideas.