Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
P2P Replica Synchronization with Vector Sets

Dahlia Malkhi, Lev Novik, and Chris Purcell


This paper describes an enhanced replica synchronization mechanism built in Microsoft's WinFS replica management system. The system reconciles autonomously-operating replicas in a completely peer-to-peer manner, without employing a central master or locking. The main challenge is for two replicas to exchange meta-information efficiently about (potentially numerous) data objects in order to discover what updates they are missing, and detect conflicts. The paper introduces a novel bundling mechanisms called VS, that groups together multiple objects and represents their state in a single version-vector. VS provides improved storage and communication overheads over previously known optimistic replication schemes, in the following sense. Under normal, low-fault situations, it maintains and communicates as little as a single version vector in order to represent precedence ordering of the entire set of data objects. Moreover, under settings of severe communication disruptions, VS degenerates to no worse than a single vector per object. This dramatically improves the complexities described in a preliminary write-up of the WinFS replication scheme. The VS mechanism has potentially wide applicability as a mechanism for compactly handling synchronization of arbitrarily overlapping groups of objects.


Publication typeArticle
Published inACM Operating Systems Review
InstitutionMicrosoft Research
> Publications > P2P Replica Synchronization with Vector Sets