Class Information

Lectures

Reading List

Class Information
Instructor Cristina Nita-Rotaru Email: crisn@cs.purdue.edu. Office hours: TBA. Class Schedule Tu Th 1:30 - 2:45 B134 Course Description This course is an introduction to distributed systems. The lectures will cover fundamental concepts in distributed systems showing how they are applied when building reliable distributed systems and services. Topics include: Internet communication protocols Client Server paradigm, RPC, Corba Web services, .net Java enterprise How and why computers systems fail. How to overcome failures in a distributed system. Failures models. The distributed commit problem. Dynamic membership. Replicating data with malicious failures. Impossibility of asynchronous consensus. Group communication systems, properties and dynamic group membership. Causal and total order. Virtual Synchrony and extended virtual synchrony. Virtually synchronous algorithms and tools: replicated data, state transfer, load-balancing, primary-backup and coordinator-cohort fault tolerance. Enhancing complex systems with reliability: fail-over TCP. Reliable distributed shared memory. Architectures for group communication systems. Clock synchronization and synchronous systems. Transactional model and implementation of a transactional storage systems. Distributed transactions and multiphase commit. Weak consistency models. Weak and strong consistency in partitioned database systems. Linearizability. Peer-to-peer file sharing. Peer-to-peer distributed indexing. Peer-to-peer data fusion and data mining. Building highly assured web services. Security issues in group communication systems. Security topics in overlay networks. Grade: The grade will be based on several written homework assignments (HW), programming projects (PP), one final project (FP) and class participation (CP), as follows: Grade = 20%*HW + 30%*PP + 40*FP + 10%*CP. Textbooks and reading list Reliable Distributed Systems: Technologies, Web Services and Applications. Ken Birman. 2005, XXXVI, 668 p. 145 illus., Hardcover ISBN: 0-387-21509-3 UNIX Network Programming, Volume 1, Second Edition: Networking APIs: Sockets and XTI, Prentice Hall, 1998, ISBN 0-13-490012-X. W. Richard Stevens Mailing list The class mailing list is cs603. To be added to the list sent an email to mailer@cs.purdue.edu, with the body containing the text 'add your_email to cs603'. Academic Integrity Academic Honesty and Ethical behavior are required in this course, as it is in all courses at Purdue University ( here is the guide for academic integrity). The class will be conducted according to the policy written by Professor Gene Spafford. Please take the time to read it carefully. This will be followed unless I provide written documentation of exceptions. You are encouraged to talk with the professor about any questions you have about what is permitted on any particular assignment.
Lectures
Lecture slides will be posted below. Homework and projects will be handed in class. This is a tentative schedule of the course. Week Tuesday Thursday Jan. 7-11 Lecture 1 - Introduction, Basic communication services. Lecture 2 - Client-Server Architecture, RPC, Corba Jan. 14-18 Lecture 3 -Web Services Lecture 4 - Ordering events. Failure detectors. Jan. 21-25 Lecture 5 - Global States. Consensus in Synchrnonous Systems. Lecture 6 - Consensus in Asynchronous Systems Jan. 28 - Feb. 1 Lecture 7 - Consensus with Byzantine Failures Lecture 8 - Onion routing. Feb. 4 - 8 Lecture 9 - Distributed Commit: 2PC and 3PC. Lecture 10 - Membership. Reliable multicast. Feb. 11 - 15 Lecture 11 - Virtual Synchrony. Lecture 12 - Byzantine-Resilient Replication (cont.) Feb. 18 - 22 Lecture 13 - Byzantine-resilient Replication (cont) Lecture 14 - Quorum Systems Feb. 25 - Feb. 29 Lecture 15 - Ben-Or Randomized Algorithm and Secure Group Communication. Lecture 16 - Secure Group Communication (cont.). Mar. 3 - 7 Lecture 17 - Gossip Protocols Lecture 18 - Distributed Hash Tables Mar. 10 - 14 Spring Break. Spring Break. Mar. 17 - 21 No class (makeup time for the project presentation during final week). Lecture 19 - Distributed Hash Tables Mar. 24 - 28 Lecture 20 - Security Issues in DHTs Lecture 21 - Security Issues in DHTs Mar. 31 - Apr. 4 Project proposals presentation Lecture 22 - Multicast Overlays. Apr. 7 - 11 Lecture 23 - P2P Streaming. Lecture 24 - Security Issues in Unstructured Overlays. Apr. 14 - 18 Project Progress Presentations. Architectures for reputations systems. No class (makeup time for the project presentation during final week). Apr. 21 - 25 Lecture 25 - Distributed File Systems. Lecture 26 - Distributed File Systems.
Reading List
Leslie Lamport for "Time, Clocks, and the Ordering of Events in a Distributed System," Communications of the ACM, July 1978, 21(7):558-565. Unreliable Failure Detectors for Reliable Distributed Systems, T. Chandra and S. Toueg. 1996. K. Mani Chandy and Leslie Lamport, Distributed Snapshots: Determining Global States of Distributed Systems. ACM Transactions on Computer Systems, Vol. 3, No. 1, February, 1985, pp. 63-75. M.J.Fischer, N.A.Lynch and M.S. Paterson. Impossibility of Distributed Consensus with One Faulty Process. ACM SPDS 1983. L. Lamport, R. Shostak, and M. Pease. The Byzantine Generals Problem ACM Transactions on Programming Languages and Systems 4(3):382-401, July 1982. K. P. Birman and T. A. Joseph. Exploiting virtual synchrony in distributed systems. In Proceedings of the ACM Symposium on OS Principles, pages 123--138, Austin, TX, 1987. L. E. Moser, Y. Amir, P. M. Melliar-Smith, D. A. Agarwal, Extended Virtual Synchrony, The 14th IEEE International Conference on Distributed Computing Systems (ICDCS) 1994. Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, H. Balakrishnan, Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications, SIGCOMM 2001. Security Considerations for Peer-to-Peer Distributed Hash Table. E. Sit, R. Morris Secure routing for structured peer-to-peer overlay networks. M. Castro, P. Druschel, A. Ganesh, A. Rowstron, D. S. Wallach Enabling Conferencing Applications on the Internet using an Overlay Multicast Architecture, Y.-h. Chu, S. Rao, S. Seshan and H. Zhang.