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.This paper proposes 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 in this paper. Its running time is (O) (( e -v+1) ε ). 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 in this paper.
Replication Scalability and Distributed database system
Yang Zhao-Hong Gong Yun-Zhan Liu Hai-Yan Bi Xue-Jun
Department of Information Engineering Armored Force Engineering Institute, Beijing 100072, China
国际会议
成都
英文
923-926
2003-08-27（万方平台首次上网日期，不代表论文的发表时间）