An efficient update propagation algorithm for P2P systems

As more and more applications with dynamic files are introduced in peer-to-peer (P2P) systems, file consistency maintenance becomes important. In this paper, we propose a novel file consistency maintenance algorithm, called Update Propagation Through Replica Chain (UPTReC), for decentralized and unstructured peer-to-peer (P2P) systems. UPTReC provides a probabilistically guaranteed file consistency. In UPTReC, each file has a logical replica chain composed of all replica peers (RPs) which are defined as peers that have a replica of the file. Each RP acquires partial knowledge of the bi-directional chain by keeping a list of information about k nearest RPs 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 chain information. An analytical model is derived to evaluate the performance of the UPTReC algorithm. The analytical results provide insights of the system design in choosing the parameters. 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 UPTReC can significantly reduce (up to 70%) overhead messages and also achieve smaller stale query ratio for files prone to frequent updates.