Update propagation through replica chain in decentralized and unstructured P2P systems

We propose a novel algorithm, called update propagation through replica chain (UPTReC), to maintain file consistency in decentralized and unstructured peer-to-peer (P2P) systems. In UPTReC, each file has a logical replica chain composed of all replica peers (RPs) which are defined as peers that have replicas of the file. Each RP acquires partial knowledge of the bi-directional chain by keeping a list of information about k nearest RPs, called probe peers, in each direction. When an RP initiates 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 and the information of the probe peers. An analytical model is derived to evaluate the performance of the UPTReC algorithm. The analytical results provide a better understanding of the system in choosing the system parameters for probabilistically guaranteed file consistency with minimum overheads. Simulation experiments are conducted to compare the performance with an existing update propagation algorithm based on the rumor spreading scheme. The experimental results show that the UPTReC can significantly reduce (up to 70%) overhead messages and also achieve smaller stale query ratio for files prone to frequent updates.