CS 542: Distributed Database Systems, Spring 2013

Time: T, Th 10:30-11:45AM

Room: LWSN 1106

Instructor: Prof. Bharat Bhargava (Office: LWSN 2116F, Tel: 494-6013, Email: bbshail@purdue.edu, Office hours: Tuesday 11:45-1:00 PM) Available in Lawson Commons after class.

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 5, 2013 in “Lawson B155” (8-10PM).

Final Exam: TBD. (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.

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 ....5 (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 16, 2013. (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) .... (10% of grade) You should attend all classes for highest class contribution credit.

e) You can expect a grade of A if you score close to 87% or higher. If you do not do the project or home works or score less than 75%, a C grade is possible.

f) To pass the qualifier, a grade of high B in class and 75% in qualifier questions is expected.

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.

Comprehensive Reading list (Read at least one paper)

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.

Cloud Computing

· http://www.cs.purdue.edu/homes/bb/cs590/

· Hey, You, Get Off of My Cloud

· Amazon's response to "Hey, you, get off my cloud"

· An Entity-centric Approach for Privacy and Identity Management in Cloud Computing
A Mobile-Cloud Collaborative Traffic Lights Detector for Blind Navigation

· Paper- Above the Clouds: A Berkeley View of Cloud Computing
PPT- Above the Clouds: A Berkeley View of Cloud Computing

· NIST Cloud Computing
NIST Cloud Computing Slides

· Chunxiao Li, Anand Raghunathan, Niraj K. Jha, Secure Virtual Machine Execution under an Untrusted Management OS(Slides) (Presenter: Pelin Angin or Prof Raghunathan of ECE)

· Security and Privacy in Cloud Computing http://www.cs.purdue.edu/homes/bb/cloud.html

· Mehdi Azarmi, et. al., End to End security in Service Oriented Architecture (Slides) (Presenter: Mehdi Azarmi)

Homework

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

· Homework 1 [Link]

· Homework 2 [Link]

· Homework 3 [Link]

· Homework 4 [Link]

· Homework 5

Projects [Link]

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.