CS 542: Distributed Database Systems, Spring 2011

Time: MWF, 2:30-3:20

Room: LWSN 1106

Instructor: Prof. Bharat Bhargava (Office: LWSN 2116F, Tel: 494-6013, Email: bbshail@purdue.edu, Office hours: W 1-2 PM)

Teaching Assistant: Mehdi Azarmi (Office: HAAS 145, Tel: 494-6702, Email: mazarmi@purdue.edu, Office hours: Mon 1:30-2:30 PM / Tue 10:30-11:30 AM)

Mail list: cs542@cs.purdue.edu. I've added the email addresses of all students to this list. Let me know if you haven't received any messages yet.

Midterm: Tuesday March 1, 2011 in “Lawson B155” (8-10PM). (Preparing for Midterm)

Final Exam: Wednesday May 4, 2011 in “UNIV 003” (1-3PM). (Qualifying exam will be held after the final exam for 45 minutes in the same place)

Teaching Material

This course will deal with the fundamental issues in large distributed systems which are motivated by the computer networking and distribution of processors, and control. The theory, design, specification, implementation, and performance large systems will be discussed. Concurrency, Consistency, Integrity, Reliability, Privacy, and Security in distributed systems will be included.

A special feature of the course includes interesting problems in Mobile Ad hoc networks and Cloud Computing that can benefit from research ideas in distributed systems. Research related to Mobile Computing, Streaming databases, Video conferencing, Peer to Peer systems, Cloud computing will be covered.

Students will be encouraged to read research papers and learn about latest developments and present to class.

Textbooks:

Principles of Distributed Database Systems, Prentice Hall, Tamer Oszu and Patrick Valduriez, (Copy on reserve in LWSN reception office book shelf) (MAIN TEXT)

Concurrency Control and Reliability in Distributed Systems, Van Nostrand and Reinhold Publishers by Bharat Bhargava (Ed.), 1987 (Copy on reserve in LWSN reception office book shelf)

Transaction Processing: Concepts and Techniques, Morgan Kaufmann, Jim Gray and Andreas Reuter, 1992 (Copy on reserve in LWSN reception office book shelf)

Course Outline:

a) Architecture, General Systems Issues, Example Systems ....(3 Hrs.)

b) Distributed control for synchronization and concurrency (will include the models for concurrent processing and transactions, theory of serializability, classes of concurrency control approaches, performance evaluation of these classes, centralized control vs. decentralized control).........(12 Hrs.)

c) Distributed commitment/termination (involves preservation of atomicity of transaction execution, blocking/non-blocking protocols).........(6 Hrs.)

d) Resiliency in distributed systems (involves design of protocols for site failure, network partitioning, loss of messages or variable transmission delays, consistent recovery)..........(3-6 hours.)

e) Security in distributed systems. (involves study of a variety of attacks on the components of system (such as on routing protocols in ad hoc networks), privacy issues in Peer to Peer systems, trusted collaboration and dissemination of data among cooperative entities)...............(9-12 hours)

f) Design and Implementation of Prototype/commercial systems, Experimental Evaluations. Details of peer to peer system developed at Purdue and several commercial systems .....(9 Hrs)

g) Research Issues in Cloud Computing (see web site under CS 590: http://www.cs.purdue.edu/homes/bb/#teaching)

Assignments and Grading Policy:

The following assignments/exams etc. are planned.

a) Non programming assignments ....6 (Once every two weeks: 20% of grade)

b) Programming assignments in the form of a project that you select from a choice of 6-8 projects. You may suggest a project based on your interest. Demonstration of project is scheduled on April 19, 2011. (30% of grade)

c) Mid Term and Final Exams ....2 (20% of grade each)

d) Class contributions (e.g., class attendance and participation, discussions, outside reading/presentation of research papers) ....1 (10% of grade) You should attend all classes for highest class contribution credit.

Your programming projects can involve implementing some component for integrity, security, reliability, or privacy policy. Or communication facility for LAN,or routing in mobile adhoc networks can be developed.

You can conduct experiments on ns2, or peer to peer system prototype, JAVA RMI (I suggest using java and java RMI for communications. If you haven't used RMI, the Hello World tutorial at http://java.sun.com is a good starting point.

Reading list

Implementation

· Building Distributed Database Systems, Bharat Bhargava.

· The Raid Distributed Database System, Bharat Bhargava and John Riedl, IEEE Trans on Software Engineering, 15(6), June 1989.

· PROMISE: Peer-to-Peer Media Streaming Using CollectCast, M. Hefeeda, A. Habib, B.Botey, D. Xu, and B. Bhargava, in Proc. of ACM Multimedia, 45-54, Berkeley, CA, November 2003.

Concurrency

· Concurrency Control in Database Systems Bharat Bhargava, IEEE Trans on Knowledge and Data Engineering,11(1), Jan.-Feb. 1999

· A Model for Adaptable Systems for Transaction Processing, Bharat Bhargava and John Riedl, IEEE Transactions on Knowledge and Data Engineering, 1(4), Dec 1989.

· A Causal Model for Analyzing Distributed Concurrency Control Algorithms, B. Bhargava and C. Hua, IEEE Trans. on Software Engineering, SE-9, 470-486, 1983.

· Global scheduling for flexible transactions in heterogeneous distributed database systems, A. Zhang, M. Nodine, and B. Bhargava. IEEE TKDE, 13(3), 2001.

· Concurrency Control in Distributed Database Systems , P. Bernstein, N. Goodman, ACM Computer Survey, 13(2), 1981.

· Concurrency control in a system for distributed databases (SDD-1), P. Bernstein, D. Shipman, J. Rothnie, ACM Transactions on Database Systems, 5(1), 1980.

· The Transaction Concept: Virtues and Limitations , Jim Gray, VLDB, 1981.

· On Optimistic Methods for Concurrency Control , H.T. Kung and John T. Robinson, ACM Trans. Database Systems, 6(2), 1981.

· The serializability of concurrent database updates, C. Papadimitriou, Journal of the ACM (JACM), 26(4), 1979.

Communication Network

· Communication Facilities for Distributed Transaction Processing Systems, E. Mafla, and B. Bhargava, IEEE Computer, 24(8), 1991.

· A framework for communication software and meaurements for digital library , B. Bhargava and M. Annanalai, Journal of Multimedia systems, 2000.

· Evolution of a communication system for distributed transaction processing in RAID, B. Bhargava, Y. Zhang, and E. Mafla, Computing Systems Journal, 4(3), 1991.

· Communication Facilities for Distributed Transaction Processing.

· WANCE: Wide area network communication emulation systems, Y. Zhang and B. Bhargava, IEEE workshop on Parallel and Distributed Systems, 1993. (Slides)

Security

· Trust-Based Privacy Preservation for Peer-to-peer Media Streaming, Y. Lu, W, Wang, D. Xu, and B. Bhargava, in Proceedings of Secure Knowledge Management (SKM) Amherst, NY, September 2004. slide

· Private and Trusted Collaborations, B. Bhargava and L. Lilien, in Proceedings of Secure Knowledge Management (SKM) Amherst, NY, Septemeber 2004.

Reliability

· An Experimental Analysis of Replicated Copy Control During Site Failure and Recovery, B. Bhargava, P. Noll, and D. Sabo. In Proceedings of International Conference on Data Engineering, p.82-91, Feb. 1988.

· Transaction Processing and Consistency Control of Replicated Copies during Failures in Distributed Databases, B. Bhargava, in Proceedings of Conference on Current Issues in Database Systems, Newark, May 1986.

· Resilient Concurrency Control in Distributed Database Systems, B. Bhargava, IEEE Trans. on Reliability, R-31(5): 437-443, 1984.

· Optimism and Consistency in partitioned distributed database systems, S. B. Davidson, ACM Trans. on Database Systems, 9(3): 456-481, 1984.

· Consistency in Partitioned Networks, S. B. Davidson, H. Garcia-Molina, and D. Skeen, ACM Computer Survey, 17(3): 341-370, 1985.

· Nonblocking commit protocols, D. Skeen, ACM SIGMOD, 1981.

· A Decentralized Termination Protocol, D. Skeen, IEEE Symposium on Reliability in Distributed Software and Database Systems, July, 1981.

· A Formal Model of Crash Recovery in a Distributed System, D. Skeen and M. Stonebraker, IEEE Trans. on Software Engineering, 9(3): 219-228, 1983.

· Detection of Mutual Inconsistency in Distributed Systems, Jr. D. Parker, et al., IEEE Trans. on Software Engineering, SE-9, 1983.

· How to Assign Votes in a Distributed System, Hector Garcia-Molina, Daniel Barbara, J. ACM 32(4): 841-860, 1985.

· A History of the Virtual Synchrony Replication Model, Ken Birman. Appears in Replication:Theory and Practice. B. Charron-Bost, F. Pedone, A. Schiper (Eds), Replication, LNCS 5959, pp. 91–120, 2010.

· Reliable communication in the presence of failures, K.Birman, T. Joseph, ACM Transactions on Computer Systems (TOCS), Volume 5 Issue 1, Feb. 1987.

Mobile

· Peer-to-Peer File-sharing over Mobile Ad Hoc Networks, G. Ding and B. Bhargava, in the first International Workshop on Mobile Peer-to-Peer Computing, Orlando, Florida, March 2004.

· Data Consistency in Intermittently Connected Distributed Systems, E. Pitouri and B. Bhargava, IEEE TKDE, 11(6), 1999.

· Maintaining Consistency of Data in Mobile Distributed Environments, Evaggelia Pitoura, Bharat Bhargava, ICDCS, 1995.

· Optimal File Allocation in Multiple Computer System, W. W. Chu, IEEE Transaction on Computers, 885-889, October 1969.

Homework

Homework assignments are generally due on a Thursday in class. Check individual homeworks for exact due date.

· Homework 1

· Homework 2

· Homework 3

· Homework 4

· Homework 5

Projects

The programming projects may involve using a mini version of the RAID system or the other systems to implement some algorithm or communication facility for transaction processing.