CSE 498, Spring 2006

Real-Time and Responsive Systems

Instructor: Hank Korth

MO 110

Tues, Thurs: 1:10 – 2:25

Office: PA 350

Office hours: Tues, Thurs: 10 – 11, or by appt.

email: hfk@lehigh.edu

IM: hfk2@mac.com (works from AIM)

Required Text: J. W. S.Liu, Real-Time Systems, Prentice Hall, 2000.

For background material on database systems, I have placed a copy of my text “Database System Concepts” on reserve.

Grading:

· Attendance 5%

· Class discussion 5%

· Assigned items to present from text 15%

· Project 30%

· Midterm 20%

· Final 25%

The Project:

For your project, you will choose either to do a research paper, a survey paper, or a software project. You will need to propose a project to me. If you have trouble finding an idea, we can meet to come up with an idea together.

· Survey

The papers listed below may suggest starting points for a survey, which is what I expect most of you will select. Regardless of the nature of your project, you will give a presentation on it during one class period. Your presentation will be due one week before your scheduled class presentation. At that time, you will need to schedule an appointment with me to review your presentation in detail. Specifically, you will go through your entire presentation in my office, so you need have the presentation fully ready – not just plans. The remaining week before your actual presentation will be available for revisions based on my comments.

The content of your presentation is not restricted to specific paper(s) listed. The given references are not necessarily the “best” papers, but rather, a starting point for you to search the literature both backward and forward for other relevant work using such citation search tools as CiteSeer http://citeseer.nj.nec.com and DBLP http://www.acm.org/sigmod/dblp/db/index.html. Do not simply restate the contents of papers. You are expected to synthesize multiple papers into material that is easier for your classmates to follow. Take a critical view of the papers and be able to defend (or attack) the statements in the paper (i.e. “well that’s what the authors said…” won’t do as an answer).

Most likely, the classroom discussion will lead to questions that you cannot answer. These should be used as guidance for writing the term paper. The paper is due two weeks after your presentation or the last day of class, whichever comes first. I will “referee” your paper much as I would a submission to ACM Computing Surveys and will take into account completeness of the references, the synthesis of the collection of prior work into a unified whole, the quality of writing (including grammar, spelling, and organization), and the appearance of the paper (yes, typesetting counts). (Indeed, in a previous course that I have taught in this style a term paper actually did get published in ACM Computing Surveys.)

The paper is to be no longer than 20 pages in 12 point font with normal margins. The bibliography does not count against the 20 page limit. The paper is to be your own original writing with proper referencing of prior work. You may seek technical advice from others, but it must be cited properly as “personal communication.” You may get assistance with grammar and related language issues, but in such cases, include an acknowledgements section and cite this.

· Software Project

If you choose to do a software project, you will need to implement or simulate a real-time system in order to study the performance (in terms of the various issues relevant to a real-time system) of some algorithm or scheduler. In addition to submitting working, demonstrable code, you will need to submit a paper describing the experimental results including appropriate graphs. The remarks above for surveys apply to the presentation and paper for this type of project as well.

· Research Paper

A research paper presents novel contributions to the art. This could be a new algorithm for scheduling, a new technique for providing real-time services, or a theoretical result. I am intentionally less specific about length here, since the quality of the research contribution is a major factor in my evaluation of the worok

Accommodations for Students with Disabilities: If you have a disability for which you are or may be requesting accommodations, please contact both your instructor and the Office of Academic Support Services, University Center 212 (610-758-4152) as early as possible in the semester.  You must have documentation from the Academic Support Services office before accommodations can be granted.

References (those in blue are on blackboard, those in red are on reserve, those in green are an electronic resource):

1. J. Stankovic, S. H. Son, and J. Hansson, “Misconceptions About Real-Time Databases,” IEEE Computer, 32:6, Oct 1998. (N.B.: Other versions of this paper exist, including one in Lam and Kuo that is an abridged version, and an older version in IEEE Computer published in 1988).
3. K-Y Lam and T-W Kuo, eds., Real-Time Database Systems: Architecture and Technique, Kluwer, 2001.

3. A. Bestravos, “Advances in RTDB Systems Research,” ACM SIGMOD Record, 25:1, Mar 1996

4. O. Ulusoy, “An Annotated Bibliography on Real-Time Database Systems,” ACM SIGMOD Record, 24:4, Dec 1995
6. R. Alonso and H. F. Korth, “Database System Issues in Nomadic Computing,” Proc. ACM SIGMOD International Conference on the Management of Data, 1993
8. M. H. Dunham, “Mobile Computing and Databases: Anything New?” ACM SIGMOD Record, 24:4, Dec 1995
10. H. V. Jagadish, D. Lieuwen, R. Rastogi, A. Silberschatz and S. Sudarshan. Dali - a high performance main memory storage manager. In Proceedings of the Very Large Database Conference (VLDB), Chile, 1994.
12. P. Bohannon, J. Parker, R. Rastogi, S. Seshadri, A. Silberschatz and S. Sudarshan. “Distributed multi-level Recovery in main-memory Databases.” Proceedings of Parallel and Distributed Information Systems, Miami Beach, 1996.
14. P. Bohannon, D. Lieuwen, R. Rastogi, S. Seshadri, A. Silberschatz and S. Sudarshan. “The architecture of the Dali main-memory storage manager.” Journal of Multi-media Tools and Applications, 4:2, 1997.
16. H. Garcia-Molina and K. Salem, “Main-Memory Database Systems: An Overview,” IEEE Transactions on Knowledge and Data Engineering, 4:6, Dec 1992

11. S. Listgarten and M.-A. Neimat, “Modeling Costs for a MM-DBMS,” Proc. First International Workshop on Real-Time Databases: Issues and Applications, Mar 1996.

12. T. Imielinski and H. F. Korth, eds., Mobile Computing, Kluwer, 1996.

13. T. Imielinski and H. F. Korth, “Introduction to Mobile Computing,” in [12]

14. G. D. Baulier, P. Bohannon, S. Gogate, S. Joshi, C. Gupta, A. Khivesara, H. F. Korth, P. McIlroy, J. Miller, P. P. S. Narayan, M. Nemeth, R. Rastogi, A. Silberschatz, and S. Sudarshan, “DataBlitz: A High Performance Main-Memory Storage Manager”, Proc. International Conference on Very Large Databases, 1998 (demo)

15. M. J. Franklin, “Challenges in Ubiquitous Data Management,” Lecture Notes in Computer Science, Volume 2000, Springer-Verlag 2001

16. S. Chandrasekaran and M. J. Franklin, “Streaming Queries over Streaming Data,” Proc. International Conference on Very Large Data Bases, 2002.

17. S. Viglas and J. F. Naughton, “Rate-Based Query Optimization for Streaming Information Sources,” Proc. ACM SIGMOD International Conference on the Management of Data, 2002

18. D. Barbara, “Mobile Computing and Databases – A Survey,” IEEE Transactions on Knowledge and Data Engineering, 11:1, Jan/Feb 1999.

19. B. Barbara and T. Imielinski, “Sleepers and Workaholics: Caching Strategies in Mobile Environments,” ACM SIGMOD International Conference on the Management of Data, 1994

20. T. Imielinski and B. Nath (formerly B. R. Badrinath), “Wireless Graffiti – Data, Data Everywhere,” Proc. International Conference on Very Large Data Bases, 2002. 10-year Award Presentation for [21]

21. T. Imielinski and B. R. Badrinath, “Querying in Highly Mobile Distributed Environments,” Proc. International Conference on Very Large Data Bases, 1992. Winner in 2002 of the award for the “Best Paper from the Conference of Ten Years Ago.”

22. S. Acharya, R. Alonso, M. Franklin, and S. Zdonik, “Broadcast Disks: Data Management for Asymmetric Communication Environments,” Proc. ACM SIGMOD International Conference on the Management of Data, 1995

23. S. Acharya, H. F. Korth, and V. Poosala, “Systematic Multiresolution and Its Application to the World-Wide Web,” Proc. IEEE International Conference on Data Engineering, 1999

24. S. Ganguly, M. N. Garofalakis, and R. Rastogi, “Processing Set Expressions over Continuous Update Streams,” Proc. ACM SIGMOD International Conference on the Management of Data, 2003.

25. G. D. Baulier, S. M. Blott, H. F. Korth, and A. Silberschatz, “Sunrise: A Real-Time Event-Processing System, Bell Labs Technical Journal, Jan-Mar 1998

26. B. George and J. Haritsa, “Secure Buffering in Firm Real-Time Database Systems,” The VLDB Journal, 8:3, Feb 2000

27. C. Park, S. Park, and S. Son, “Multiversion Locking Protocol with Freezing for Secure Real-Time Database Systems,” IEEE Transactions on Knowledge and Data Engineering, 14:5, Sep-Oct 2002.

28. L. Lamport and P. M. Melliar-Smith, “Synchronizing Clocks in the Presence of Faults,” J. ACM, 32:1, Jan 1985

29. E. Levy, H. F. Korth, and A. Silberschatz, “An Optimistic Commit Protocol for Distributed Transaction Management,” Proc. ACM SIGMOD International Conference on the Management, 1991.

30. E. Levy, H. F. Korth, and A. Silberschatz, “A Theory of Relaxed Atomicity,” Proc. ACM Symposium on the Principles of Distributed Computing, 1991.

31. M. L. Scott, “Non-Blocking Timeout in Scalable Queue-Based Spin Locks,” Proc. ACM Symposium on the Principles of Distributed Computing, 2002.

32. J. A. Stankovic and K. Ramamritham, eds., Advances in Real-Time Systems, IEEE Computer Society Press, 1993.

33. S. Chandrasekaran, O. Cooper, A. Deshpande, M. J. Franklin, J. M. Hellerstein, W. Hong, S. Krishnamurthy, S. Madden, V. Raman, F. Reiss, and M. A. Shah, “TelegraphCQ: Continuous Dataflow Processing for an Uncertain World, Proc. First Biennial Conference on Innovative Data Systems Research, Jan 2003.

34. Y. Yao and J. Gerke, “Query Processing in Sensor Networks,” Proc. First Biennial Conference on Innovative Data Systems Research, Jan 2003.

35. M. Xiong, K. Ramamritham, J. Haritsa, and J. Stankovic, “MIRROR: A State-Conscious Concurrency Control Protocol for Replicated Real-Time Databases,” Proc. IEEE Real-Time Technology and Applications Symposium, 1999.

36. H. Pang, M. Carey, and M. Livney, “Multiclass Query Scheduling in Real-Time Database Systems,” IEEE Transactions on Knowledge and Data Engineering, 7:2, Aug 1995.

37. A. Datta and S. H. Son, “A Study of Concurrency Control in Real-Time Active Database Systems,” IEEE Transactions on Knowledge and Data Engineering, 14:3, Jun 2002

38. R. K. Abbott and H. Garcia-Molina, “Scheduling Real-Time Transactions: A Performance Evaluation,” ACM Transactions on Database Systems, 17:3, Sep 1992.

39. D. Nystrom, A. Tesanovic, C. Norstrom, J. Hansson, and N. Bankestad, “Data Management Issues in Vehicle Control Systems; A Case Study,” Proc. Euromicro International Conference on Real-Time Systems, 2002

40. M. Olson, “Selecting and Implementing an Embedded Database System,” IEEE Computer, 33:9, Sep 2000.

41. M. Seltzer and M. Olson, “Challenges in Embedded Database System Administration,” Proc. USENIX Embedded Systems Workshop, 1999

42. N. Soparkar, H. F, Korth, and A. Silberschatz, “Databases with Deadline and Contingency Constraints,” IEEE Transactions on Knowledge and Data Engineering, 7:4, Aug 1995.

43. N. Soparkar, H. F, Korth, and A. Silberschatz, Time-constrained transaction management : real-time constraints in database transaction systems, Kluwer.

44. H. F. Korth and G. Speegle, “Formal Aspects of Concurrency Control in Long-Duration Transactions Systems Using the NT/PV Model,” ACM Transactions on Database Systems, 19:3, Sep 1994, pp. 492-535.

45. S. Blott and H. F. Korth, “An Almost-Serial Protocol for Transaction Execution in Main-Memory Database Systems,” Proc. 28^th International Conference on Very Large Data Bases, 2002

46. Y-B. Lin and I. Chlamtac, Wireless and Mobile Network Architectures, Wiley, 2000.

Schedule (approximate):

Our pace will vary based on student interest and background. I will update this as we go along.

Date	Topics	Refs.	Events
Jan 17	Introduction	Liu 1.4, ch2
19	Introduction to real-time databases	Papers 1, 3, 4, 29, 30, 38, 42, 43, 44, 45
24	Main-memory databases	Papers 7, 8, 9, 10, 11, 14
26	Mobile Computing	Papers 5, 6, 18, 19, 20, 21, 23, 46
31		Ch 3 (not 3.5)
Feb 2		Ch 4.1 – 4.5
7		Ch 4.6 – 4.7
9		Ch 5.
14		Ch 5
16		Ch 5
21		Ch 6
23		Ch 6
28		Ch 6
Mar 2		Ch 6
Spring break
14		Ch 8
16		Ch 8
21		Ch 8
23	Take-home midterm, no class		HFK out of town
28		Ch 9
30		Ch 9
Apr 4	Security	Papers 26
6			Dishant presentation
11			Denis presentation
13			Supriya presentation
18			Sudhan presentation
20			Rami presentation
25	Review and overview, course evaluation
27	final		Last class