Why Can't I Update My Replicated Database?

Dr. Jim Gray

Microsoft Research
Email: gray@microsoft.com


Many products offer a replicated database technology which is update anything, anytime, anywhere. If concurrent changes by two different agents conflict, a magic reconciliation process (typically people) resolves the problem. These systems demo very well -- two nodes and a few users can run without problems or conflicts. But, a problem lurks behind the scenes: the probability of conflict rises as the 3rd power of the number of nodes: 10x more nodes means 1,000x more conflicts. It also rises as the 5th power of the transaction size. Mobile (disconnected) applications may create very long-running transactions. This could ruin your day if you are the person responsible for resolving these problems. One way to reduce this problem is to appoint an "owner" for each data item. This avoids much of the polynomial explosion. This talk sketches the problem, presents an analytic model to estimate deadlock and reconciliation rates, and proposes a solution that minimizes such events.


Jim Gray, Pat Helland, Patrick O'Neil, Dennis Shasha, The Dangers of Replication and a Solution. 10 pages, October 1995.