The Dangers of Replication and a Solution
📜 Abstract
Update anywhere-anytime-anyway transactional replication has unstable behavior as the workload scales up: a ten-fold increase in nodes and traffic gives a thousand fold increase in deadlocks or reconciliations. Master copy replication (primary copy) schemes reduce this problem. A simple analytic model demonstrates these results. A new two-tier replication algorithm is proposed that allows mobile (disconnected) applications to propose tentative update transactions that are later applied to a master copy. Commutative update transactions avoid the instability of other replication schemes.
✨ Summary
The paper analyzes eager and lazy replication under transactional consistency and argues that update-anywhere replication becomes unstable as the number of nodes, transaction rates, and transaction sizes increase. Its model predicts particularly rapid growth in deadlocks and reconciliation failures, while showing that master-copy schemes reduce conflicts but do not support disconnected updates. The proposed two-tier design separates continuously connected base nodes from intermittently connected mobile nodes: mobile nodes execute tentative updates locally, while base nodes validate and apply updates to master copies. Commutative transactions and explicit acceptance or rejection preserve consistency without requiring every mobile operation to commit globally. (ics.uci.edu)
The paper was subsequently cited by research on lazy database replication and snapshot isolation. Daudjee and Salem’s work uses stronger session-level isolation criteria to address consistency problems in lazy replicated systems, directly continuing the paper’s examination of replication, concurrency, and reconciliation trade-offs. (cs.uwaterloo.ca) The Borealis stream-processing system cites the paper in connection with tentative results, reconciliation, and eventual consistency for fault-tolerant distributed processing. (cs.brown.edu) Google’s Megastore paper also cites this work while presenting a production storage architecture based on partitioning and synchronous replication, illustrating an industry approach that limits coordination to smaller data partitions rather than applying global transactional coordination indiscriminately. (research.google.com)