Optimism and consistency in partitioned distributed database systems

TLDR

The authors propose a protocol that guarantees mutual consistency between replicated data items after partition failures are repaired. The optimistic protocol processes transactions freely during failures, detects conflicts at repair time using a precedence graph, and resolves them by backing out transactions according to a cost‑aware strategy that minimizes total backout cost. Simulation and probabilistic analysis demonstrate that the protocol performs well in many scenarios, with the efficient backout strategy achieving near‑optimal results despite the underlying NP‑complete problem.

Abstract

A protocol for transaction processing during partition failures is presented which guarantees mutual consistency between copies of data-items after repair is completed. The protocol is “optimistic” in that transactions are processed without restrictions during failure; conflicts are then detected at repair time using a precedence graph , and are resolved by backing out transactions according to some backout strategy . The resulting database state then corresponds to a serial execution of some subset of transactions run during the failure. Results from simulation and probabilistic modeling show that the optimistic protocol is a reasonable alternative in many cases. Conditions under which the protocol performs well are noted, and suggestions are made as to how performance can be improved. In particular, a backout strategy is presented which takes into account individual transaction costs and attempts to minimize total backout cost. Although the problem of choosing transactions to minimize total backout cost is, in general, NP-complete, the backout strategy is efficient and produces very good results.