本研究主要探討的問題是如何有效管理與維護資料更新檔，這類更新檔內包含某個client在離線時對共享資料所做的更新資訊，這些更新資訊必須反映給其他相關的client。更新檔一般是由server預備，而在client連線時傳送出去，本研究主要目的是要簡化更新檔，以便節省儲存空間和縮短網路傳輸的時間。我們利用類似代數運算觀念來簡化更新檔的指令，藉由交換與簡化法則來減少作業數量，達到減少更新檔的容量、節省存放空間，並縮短傳輸時間。另外我們用group的概念，將client之間共同分享的資料分成數個group，如此server不須再為每個client準備一個單獨的更新檔，而只要為每個group產生一個更新檔，因而降低server的工作負荷。

　　This research addresses the problem of efficiently managing and maintaining update logs in an intermittently connected environment. Such update logs contain updates done to shared data when clients disconnect. These updates must be made known to other clients that use shared data. Typically, update logs are prepared by server, and are transmitted when a client connects. Our research considers ways to simplify these logs so as to save storage and reduce transmission time. We make use of algebraic rules to perform the simplification. Via commutative and simplifying rules, we reduce operations in these logs. We also present a data-centric approach which clusters data into groups, and assign one or more of these groups to each client. As a result, server only needs to prepare one update file for each group, thereby reducing server workload and improving system scalability.

1.Norman Ramsey and Elod Csirmaz, “An Algebraic Approach to File Synchronization”, Technical Report TR-05-01, Harvard University Dept. of Computer Science, Cambridge MA (USA), May 2001.

2.Sameer Mahajan, Michael J. Donahoo, Shamkant B. Navathe, and Mostafa Ammar. “Grouping techniques for update propagation in intermittently connected databases”, In Fourteenth Internation Conference on Data Engineering, pages 46--53. IEEE, February 1997.

3.S. Balasubramaniam and B. C. Pierce. ”What is a file synchronizer? ”,In International Conference on Mobile Computing and Networking (MobiCom '98).page 98-108 ACM/IEEE, Oct. 1998.

4.Wai Gen Yee, Michael J. Donahoo, and Shamkant B. Navathe. “A framework for server data fragment grouping to improve scalability in intermittently synchronized databases”. Conference On Information And Knowledge Management, Nov. 2000.

5.S. Agarwal, D. Starobinski, and A. Trachtenberg,“On the Scalability of Data Synchronization Protocols for PDAs and Mobile Devices”, IEEE Network (Special Issue on Scalability in Communication Networks), Vol. 16, No.4, pp.2228, July/August 2002.

6.A. Trachtenberg, D. Starobinski, and S. Agarwal, “Fast PDA synchronization using characteristic polynomial interpolation”. Proc. INFOCOM (June 2002).

7.Alan Demers, Dan Greene, Carl Hauser, Wes Irish, John Larson, Scott Shenker, Howard Sturgis, Dan Swinehart, and Doug Terry. “Epidemic algorithms for replicated database maintenance”. Operating Systems Review, 22(1):8--32, January 1988.

8.Richard Guy, Peter Reicher, David Ratner, Michial Gunter, Wilkie Ma, and Gerald Popek. “Rumor: Mobile Data Access Through Optimistic Peer-to-peer Replication”. In Proceedings: ER'98 Workshop on Mobile Data Access, 1998.

9.Beverly Yang and Hector Garcia-Molina. “Comparing Hybrid Peer-to-Peer Systems”. Technical report, Stanford University, February.

10.T. W. Page, Jr., R. G.. Guy, J. S. Heidemann, D. H. Ratner, P. L. Reiher, A. Goel, G. H. Kuenning, and G. Popek. Perspectives on optimistically replicated peer-to-peer filing. Software -- Practice and Experience, 11(1), December 1997.

11.L.B. Huston and P. Honeyman,”Peephole Log Optimization”.IEEE Workshop on Mobile Computing Systems and Applications, 1994.

12.Kam-Yiu Lam, Alan Kwan and Krithi Ramamritham,"RTMonitor: Real-Time Data Monitoring Using Mobile Agent Technologies", in Proceedings of 2002 Very Large Data Base Conference , August 2002, Hong Kong.

13.C. Lv, P. Cao, E. Cohen, K. Li, and S. Shenker. “Search and replication in unstructured peer-to-peer networks”. In ICS, 2002.

14.Ramakrishna Gummadi and Randy H. Katz,“The data management problem in post-pc devices and a solution”,ACM SIGOPS 2000.

15.W.G. Yee, E. Omiecinski, M.J. Donahoo, and S.B. Navathe. Scaling replica maintenance in intermittently synchronized mobile databases. In Proceedings of ACM CIKM, pages 450--457, 2001.