Bounded ignorance: a technique for increasing concurrency in a replicated system

Reviewer: Asuman Dogac

The authors present a method to increase concurrency in a replicated database system. For this purpose, the notion of N -ignorance is introduced. An N -ignorant transaction does not need to see the results of at most N prior transactions that it would have seen if serializability had been enforced as the correctness criterion. By relaxing the correctness criterion and allowing bounded violations of the integrity constraints, concurrency can be increased N+1 -fold compared to a serializable system. In an N -ignorant system, each transaction enforces a set of integrity constraints on its view of the database, but only the weakened constraint set needs to be enforced globally. This allows a transaction executing at a replica site to be unaware of N concurrently executing transactions at other sites. Thus, by relaxing the integrity constraint, N+1 transactions can run concurrently in the system, as against just one in the serializable case. Violations of the integrity constraints are formalized as a function of the number of conflicting transactions that can execute concurrently. To increase the autonomy of sites in executing transactions, the work aims at reducing the number of sites that a site has to communicate with after a transaction is submitted. The algorithms to guarantee that a transaction is no more than N -ignorant, and hence the relaxed constraints always hold, are presented in section 4. In these algorithms, quorum locking controls the number of transactions that can simultaneously access replicas of the same data object. Gossip messages are used to limit the extent to which a site may be ignorant of the effects of prior transactions executed at nonquorum sites. An extension to the algorithms is given to allow transactions that access disjoint data sets to run concurrently. The authors argue that, to verify that a given N -ignorant system is correct according to their relaxed definition of correctness, it is necessary to determine its reachable states and demonstrate that they do not violate the relaxed constraints. A systematic analysis of reachable states of the system is provided in section 5. The technique is useful in systems where transactions make incremental changes to the database state. How the system behaves in the case of failures or deadlock is not clear, however. Also, a performance comparison of an N -ignorant system with other systems would have been useful to give an idea of how well the technique proposed performs in real life.