Patent ID: 8150802

Claim:
A method of synchronizing replicas in a system in which a collection of items are replicated fully or partially at two or more replicas, comprising: arranging the replicas into a tree having a predefined synchronization hierarchy among the replicas; recording item-set knowledge of which each replica is aware at each replica; maintaining hierarchical information at each replica in the predefined synchronization hierarchy, wherein the hierarchical information maintained by at least one replica identifies a parent replica and a child replica of the at least one replica; sending the item-set knowledge from a target replica to a source replica; receiving, at the target replica, items that are previously unknown by the target replica and learned knowledge from the source replica, wherein the items that are previously unknown include items that are outside of an interest set of the source replica, and wherein the interest set comprises items that satisfy a filter; assuming authority for the items that are outside of the interest set of the source replica by the target replica; discarding the items that are outside of the interest set by the source replica after the target replica assumes authority for the items; adding the items that are unknown by the target replica, and the learned knowledge to the target replica's item-set knowledge; informing the target replica of versions of items for which the source replica is authoritative; constructing star knowledge at the target replica from authoritative information from the source replica, wherein the star knowledge is a knowledge fragment that refers to a set of all items in the system; combining star knowledge from source replicas into a star knowledge fragment with a knowledge vector containing an entry for all replicas; reducing the overall size of the target replica's knowledge by discarding knowledge fragments that are covered by the star knowledge fragment; creating a full replica at a root of the tree by providing the star knowledge fragment at the root of the tree in accordance with the hierarchical information; and propagating the full replica to the predefined synchronization hierarchy in accordance with the hierarchical information maintained at each replica.