Using the transformational approach to build a safe and generic data synchronizer

ABSTRACT

Reconciliating divergent data is an important issue in concurrent engineering, mobile computing and software configuration management. Currently, a lot of synchronizers or merge tools perform reconciliations. However, they do not define what is the correctness of their synchronisation. In this paper, we propose to use a transformational approach as the basic model for reasonning about synchronisation. We propose an algorithm and specific transformation functions that realize a file system synchronisation. Unlike classic synchronizers, our synchronizer ensures properties of convergence, causality and intention preservation and is extensible to new data types.

REFERENCES

• 1: S. Balasubramaniam , Benjamin C. Pierce, What is a file synchronizer?, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.98-108, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288261]
• 2: B. Berliner, Parallelizing Software Development. In Proceedings of USENIX, Washigton D. C., 1990.
• 3: Sudarshan S. Chawathe , Hector Garcia-Molina, Meaningful change detection in structured data, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.26-37, May 11-15, 1997, Tucson, Arizona, United States
• 4: Reidar Conradi , Bernhard Westfechtel, Version models for software configuration management, ACM Computing Surveys (CSUR), v.30 n.2, p.232-282, June 1998 [doi>10.1145/280277.280280]
• 5: Dean Daniels , Lip Boon Doo , Alan Downing , Curtis Elsbernd , Gary Hallmark , Sandeep Jain , Bob Jenkins , Peter Lim , Gordon Smith , Benny Souder , Jim Stamos, Oracle's symmetric replication technology and implications for application design, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.467, May 24-27, 1994, Minneapolis, Minnesota, United States
• 6: C. A. Ellis , S. J. Gibbs, Concurrency control in groupware systems, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.399-407, June 1989, Portland, Oregon, United States
• 7: Jacky Estublier, Software configuration management: a roadmap, Proceedings of the Conference on The Future of Software Engineering, p.279-289, June 04-11, 2000, Limerick, Ireland [doi>10.1145/336512.336576]
• 8: Jim Gray , Pat Helland , Patrick O'Neil , Dennis Shasha, The dangers of replication and a solution, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.173-182, June 04-06, 1996, Montreal, Quebec, Canada
• 9: A. Imine, P. Molli, G. Oster, and M. Rusinowitch. Development of transformation functions assisted by a theorem prover. In Fourth International Workshop on Collaborative Editing , New Orleans, Louisiana, USA, November 2002.
• 10: A. Imine, P. Molli, G. Oster, and M. Rusinowitch. Proving correctness of transformation functions in real-time groupware. In Proceedings of the 8th European Conference on Computer-Supported Cooperative Work, Helsinki, Finland, September 2003.
• 11: A. Imine, P. Molli, G. Oster, and P. Urso. Vote: Group editors analyzing tool. In International Workshop on First-Order Theorem Proving, June 2003.
• 12: Anne-Marie Kermarrec , Antony Rowstron , Marc Shapiro , Peter Druschel, The IceCube approach to the reconciliation of divergent replicas, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.210-218, August 2001, Newport, Rhode Island, United States [doi>10.1145/383962.384020]
• 13: P. Kumar and M. Satyanarayanan. Flexible and safe resolution of file conflicts. In USENIX Winter, pages 95--106, 1995.
• 14: Jonathan P. Munson , Prasun Dewan, A flexible object merging framework, Proceedings of the 1994 ACM conference on Computer supported cooperative work, p.231-242, October 22-26, 1994, Chapel Hill, North Carolina, United States [doi>10.1145/192844.193016]
• 15: Karin Petersen , Mike J. Spreitzer , Douglas B. Terry , Marvin M. Theimer , Alan J. Demers, Flexible update propagation for weakly consistent replication, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.288-301, October 05-08, 1997, Saint Malo, France
• 16: Michael Rabinovich , Narain H. Gehani , Alex Kononov, Scalable Update Propagation in Epidemic Replicated Databases, Proceedings of the 5th International Conference on Extending Database Technology: Advances in Database Technology, p.207-222, March 25-29, 1996
• 17: P. L. Reiher, J. S. Heidemann, D. Ratner, G. Skinner, and G. J. Popek. Resolving file conflicts in the ficus file system. In USENIX Summer , pages 183--195, 1994.
• 18: Yasushi Saito , Henry M. Levy, Optimistic Replication for Internet Data Services, Proceedings of the 14th International Conference on Distributed Computing, p.297-314, October 04-06, 2000
• 19: Haifeng Shen , Chengzheng Sun, A Log Compression Algorithm for Operation-based Version Control Systems, Proceedings of the 26th International Computer Software and Applications Conference on Prolonging Software Life: Development and Redevelopment, p.867-872, August 26-19, 2002
• 20: Sorin Stratulat, A general framework to build contextual cover set, Journal of Symbolic Computation, v.32 n.4, p.403-445, October 2001 [doi>10.1006/jsco.2000.0469]
• 21: Maher Suleiman , Michèle Cart , Jean Ferrié, Concurrent Operations in a Distributed and Mobile Collaborative Environment, Proceedings of the Fourteenth International Conference on Data Engineering, p.36-45, February 23-27, 1998
• 22: Maher Suleiman , Michèle Cart , Jean Ferrié, Serialization of concurrent operations in a distributed collaborative environment, Proceedings of the international ACM SIGGROUP conference on Supporting group work: the integration challenge, p.435-445, November 16-19, 1997, Phoenix, Arizona, United States [doi>10.1145/266838.267369]
• 23: Chengzheng Sun, Undo as concurrent inverse in group editors, ACM Transactions on Computer-Human Interaction (TOCHI), v.9 n.4, p.309-361, December 2002 [doi>10.1145/586081.586085]
• 24: Chengzheng Sun , David Chen, Consistency maintenance in real-time collaborative graphics editing systems, ACM Transactions on Computer-Human Interaction (TOCHI), v.9 n.1, p.1-41, March 2002 [doi>10.1145/505151.505152]
• 25: Chengzheng Sun , Xiaohua Jia , Yanchun Zhang , Yun Yang , David Chen, Achieving convergence, causality preservation, and intention preservation in real-time cooperative editing systems, ACM Transactions on Computer-Human Interaction (TOCHI), v.5 n.1, p.63-108, March 1998 [doi>10.1145/274444.274447]
• 26: Walter F. Tichy, RCS—a system for version control, Software—Practice & Experience, v.15 n.7, p.637-654, July 1985 [doi>10.1002/spe.4380150703]
• 27: André van der Hoek, International workshop on software configuration management (SCM-10): new practices, new challenges, and new boundaries, ACM SIGSOFT Software Engineering Notes, v.26 n.6, November 2001 [doi>10.1145/505532.505545]
• 28: Nicolas Vidot , Michelle Cart , Jean Ferrié , Maher Suleiman, Copies convergence in a distributed real-time collaborative environment, Proceedings of the 2000 ACM conference on Computer supported cooperative work, p.171-180, December 2000, Philadelphia, Pennsylvania, United States [doi>10.1145/358916.358988]

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.7 Distribution, Maintenance, and Enhancement

General Terms:
Algorithms, Reliability

Keywords:
operational transformation, synchronization