%0 Generic
%A Asthana, H
%A Cox, IJ
%D 2013
%F discovery:1388032
%T Retrieval of highly dynamic information in an unstructured peer-to-peer network
%U https://discovery.ucl.ac.uk/id/eprint/1388032/
%X We present a framework for the retrieval of highly dynamic information in an unstructured peer-to-peer network. Non- exhaustive search in an unstructured network is necessar- ily probabilistic, and we utilize the probably approximately correct (PAC) search architecture to determine the required replication rate for a document in order to guarantee a high probability of retrieval. Once this replication rate is deter- mined, the problem becomes how to replicate a new docu- ment across the network to meet this requirement, without overloading the communication capacity of the network. To solve this, we model the problem as rumour spreading, and use techniques from this field to propagate new documents. Our document spreading algorithm is designed such that a document has a very high probability of being replicated to the required number of nodes, but the probability of spread- ing to fewer or more nodes is small. Apart from facilitating rapid and restrained dissemination, our proposed method also withstands sudden spikes in the data creation rate. We illustrate the utility of the framework in the context of a micro-blogging social network. However it could also be used to index dynamic web pages in a distributed search engine or for a system which indexes newly created BitTorrents in a de-centralized environment. Simulations performed on net- work of 100,000 nodes validate our proposed framework.