CS 542: Distributed Database Systems, Spring 2006

Time: Tuesday and Thursday, 10:30-11:45am.

Room: REC 315.

Instructor: Prof. Bharat Bhargava (Office: CS 145, Tel: 494-6702, Email: bb@cs, Office hours: TTh 11:45-1:00)

Teaching Assistants:

Yicheng Tu (Office: MATH403, Tel: 494-5005, Email: tuyc@cs, Office hours: MW 12:30-1:30)

Gang Ding (Office: CS145, Tel: 494-6702, Email: dingg@cs, Office hours: by appointment)

Mail list: 542bb. I've added the email addresses of all students to this list. Let me know if you haven't received any messages yet.

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 Adhoc networks that can benefit from research ideas in distributed systems. Research related to Mobile Computing, Streaming databases, Video conferencing, Peer to Peer systems will be covered.

Textbooks:

Principles of Distributed Database Systems, Prentice Hall, Tamer Oszu and Patrick Valduriez, (Copy on reserve in Raid Lab, CS145) (MAIN TEXT)

Concurrency Control and Reliability in Distributed Systems, Van Nostrand and Reinhold Publishers by Bharat Bhargava (Ed.), 1987 (Copy on reserve in Raid lab, CS145)

Transaction Processing: Concepts and Techniques, Morgan Kaufmann, Jim Gray and Andreas Reuter, 1992 (Copy on reserve in Raid lab).

Course Outline:

a) Architecture, General Systems Issues, Example Systems ....(4 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 adhoc 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)

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 18, 2006. (30% of grade)

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

d) Class contributions (e.g., class participation, discussions, outside reading/presentation of research papers) ....1 (10% of grade)

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. You should attend all classes for highest class contribution credit.

Reading list

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.

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.

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.

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

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.

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.

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

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

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.

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

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.

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

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.

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

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

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

Homework

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

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.