Portal de Periódicos da CAPES

P2P replica synchronization with vector sets

2007; Association for Computing Machinery; Volume: 41; Issue: 2 Linguagem: Inglês

10.1145/1243418.1243427

1943-586X

Dahlia Malkhi, Lev Novik, Chris Purcell,

Distributed and Parallel Computing Systems

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.