An algebraic approach to file synchronization

ABSTRACT

A file synchronizer restores consistency after multiple replicas of a filesystem have been changed independently. We present an algebra for reasoning about operations on filesystems and show that it is sound and complete with respect to a simple model. The algebra enables us to specify a file-synchronization algorithm that can be combined with several different conflict-resolution policies. By contrast, previous work builds the conflict-resolution policy into the specification, or worse, does not specify the synchronizer's behavior precisely. We classify synchronizers by asking whether conflicts can be resolved at a single disconnected replica and whether all replicas are identical after synchronization. We also discuss timestamps and argue that there is no good way to propagate timestamps when there is severe clock skew between replicas.

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: Broder, Andrei. 1993. Some applications of Rabin's fingerprinting method. In Capocelli, R.,A. De Santis, and U. Vaccaro, editors, Sequences II: Methods in Communications, Security, and Computer Science, pages 143-152. Springer-Verlag.
• 3: 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]
• 4: Cox, Russ and William Josephson. 2001 (January). Communication timestamps for file system synchronization. Technical Report 01-01, Computer Science, Harvard University.
• 5: Fidge, Colin J. 1988 (February). Timestamps in messagepassing systems that preserve the partial ordering. Australian Computer Science Communications, 10(1).
• 6: Howard, John H. 1999. Reconcile user's guide. Technical Report TR99-14, Mitsubishi Electronics Research Lab.
• 7: 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]
• 8: Ernst Lippe , Norbert van Oosterom, Operation-based merging, Proceedings of the fifth ACM SIGSOFT symposium on Software development environments, p.78-87, December 09-11, 1992, Tyson's Corner, Virginia, United States
• 9: Mattern, Friedemann. 1989. Virtual time and global states of distributed systems. In Cosnard, Michel, Yves Robert, Patrice Quinton, and Michel Raynal, editors, Parallel and Distributed Algorithms, pages 215-226. Amsterdam: Elsevier Science Publishers B. V. (North Holland).
• 10: Microsoft. 1998. Microsoft Windows 95: Vision for mobile computing. http://www.microsoft.com/windows95/ info/w95mobile.htm.
• 11: Puma. Designing effective synchronization solutions: A White Paper on Synchronization from Puma Technology. http://www.pumatech.com/syncwp.html.
• 12: ___. A white paper on DSXtm Technology - Data Synchronization Extensions from Puma Technology. http://www.pumatech.com/dsxwp.html.
• 13: Reiher, P., J. Popek, M. Gunter, J. Salomone, and D. Ratner. 1996 (June). Peer-to-peer reconciliation based replication for mobile computers. In European Conference on Object Oriented Programming '96 Second Workshop on Mobility and Replication.
• 14: Schwartz, Stu. 1996 (May). The Briefcase|in brief. Windows 95 Professional. http://www.cobb.com/w9p/ 9605/w9p9651.htm.
• 15: Thompson, Ken. 1995. The Plan 9 file server. In Plan 9: The Documents, pages 313-320. Murray Hill, New Jersey: Computing Sciences Research Center, AT&T Bell Laboratories.
• 16: Bernhard Westfechtel, Structure-oriented merging of revisions of software documents, Proceedings of the 3rd international workshop on Software configuration management, p.68-79, June 12-14, 1991, Trondheim, Norway [doi>10.1145/111062.111071]

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.3 File Systems Management

General Terms:
Algorithms