Minimizing the copy graph to improve scalability

Data is replicated at multiple network nodes for performance and availability. Primary lazy replica update protocols have become popular for their superior performance characteristics. A common problem with those lazy replication protocols is that the number of exchanged messages and the deadlock probability drastically increase when the number of sites increases. We propose a method to minimize the copy graph, which can improve the scalability of the replicated system. The copy graph can be decomposed into blocks. If the serializability of each blocks of the copy graph is guaranteed, the serializability of the copy graph is also guaranteed. An algorithm to discover the cut vertices and the blocks of G is introduced. Its running time is /spl Theta/((/spl epsiv/-v+1)/spl epsiv/). For each block of G, if it contains a directed circle, the primary transaction may need to wait to get serializable schedules, and then it will lose the main advantage of the lazy replica update protocols. Therefore it is important to discover the directed circles in the blocks of G. A linear-time algorithm to compute the strongly connected components is also introduced.