1UPTReC: Update Propagation Through Replica Chain in Decentralized Unstructured P2P Systems

Abstract In this paper, we propose a novel algorithm, called update propagation through replica chain (UP-TReC), to maintain le consistency in decentralized and unstructured peer-to-peer (P2P) systems. In UPTReC, each le has a logical replica chain composed of all replica peers (RPs), where an RP is dened as a peer that has a replica of the le. Each RP has partial knowledge of the chain by keeping a list of k nearest RPs ’ information in each direction. The replica chain is naturally built and easily maintained during the le replica process. When an RP ini-tiates an update, it pushes the update to all possible online (active) RPs through the replica chain. A reconnected RP pulls an online RP to synchronize the replica status. An an-alytical model is derived to evaluate the performance of UP-TReC algorithm. Simulation experiments are conducted to compare the performance with an existing update prop-agation algorithm based on the rumor spreading scheme. The experimental results show that the UPTReC can sig-nicantly reduce (up to 70%) overhead messages and also achieve smaller stale query ratio for frequently updating les. I