Update anywhere-anytime-anyway transactional replication hasunstable behavior as the workload scales up. To reduce this problem, atwo-tier replication algorithm is proposed in (Gray et al., 1996) thatallows mobile applications to propose tentative transactions that arelater applied to a master copy. However it can suffer from heavyreprocessing overhead in many circumstances. We present the method ofmerging histories instead of reprocessing to reduce the overhead oftwo-tier replication. The basic idea is when a mobile node connects tothe base nodes merging the tentative history into the base history sothat substantial work of tentative transactions could be saved. As aresult, a set of undesirable transactions (denoted B) have to be backedout to resolve the conflicts between the two histories. Desirabletransactions that are affected directly or indirectly, by thetransactions in B complicate the process of backing out B. We present afamily of novel rewriting algorithms for the purpose of backing out B.By incorporating transaction semantics, our rewriting methods arestrictly better at saving desirable tentative transactions than thetraditional reads-from transitive-closure based approach. In most casesour rewriting methods are better at saving desirable tentativetransactions than an approach which is based only on commutativity
展开▼