Chinese Journal of Computers   Full Text
Title	PATCOM: Partition Tree-Based Consistency Maintenance for Unstructured P2P Systems
Authors	LI Zhen-Yu1),2) XIE Gao-Gang1) LI Zhong-Cheng1)
Address	1)(Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100080) 2)(Graduate University of Chinese Academy of Sciences, Beijing 100039)
Year	2007
Issue	No.9(1500—1510)
Abstract &   Background	Abstract Unstructured P2P technique is gradually applied in newly-developed cooperative computing systems. These applications support the dynamical updates of data, and require not only strong consistency but also fast propagation of update messages. An efficient consistency maintenance method is the basis for the developing of newly-developed applications. Based on intensive analysis and comparisons for existing methods, the authors propose a partition tree-based consistency maintenance scheme for unstructured P2P systems, PATCOM. PATCOM uses Chord as the group management protocol and propagates update messages along with the Update Message Propagation Tree(UMPT), which is built dynamically on top of the Chord ring composed of replica nodes. The authors theoretically analyze the average height of UMPT, the performance of PATCOM, the failure tolerance and the overhead of the proposed scheme. Then, the authors compare PATCOM with the Gossip-based consistency maintenance method. Finally, they verify the theoretical results and the performance of PATCOM by simulation experiments. The performance analysis and simulation results show that PATCOM not only maintains a strict consistence, but also brings fewer redundant update messages. keywords P2P systems; consistency maintenance; partition tree; Chord; performance analysis background This work is supported by the National Natural Science Foundation of China under grant No.60403031 and No.90604015, by the National High Technology Research and Development Program (863 Program) of China under grant No.2005AA121560.