H. Asthana
Ingemar J. Cox
ABSTRACT
We describe a framework for a micro-blogging social network implemented in an unstructured peer-to-peer network. A micro-blogging social network must provide capabilities for users to (i) publish, (ii) follow and (iii) search. Our retrieval mechanism is based on a probably approximately correct (PAC) search architecture in which a query is sent to a fixed number of nodes in the network. In PAC, the probability of attaining a particular accuracy is a function of the number of nodes queried (fixed) and the replication rate of documents (micro-blog). Publishing a micro-blog then becomes a matter of replicating the micro-blog to the required number of random nodes without any central coordination. To solve this, we use techniques from the field of rumour spreading (gossip protocols) to propagate new documents. Our document spreading algorithm is designed such that a document has a very high probability of being copied to only the required number of nodes. Results from simulations performed on networks of 10,000, 100,000 and 500,000 nodes verify our mathematical models. The framework is also applicable for indexing dynamic web pages in a distributed search engine or for a system which indexes newly created BitTorrents in a decentralized environment.
- Asthana, H., Fu, R., and Cox, I. J. On the feasibility of unstructured peer-to-peer information retrieval. In ICTIR (2011). Google Scholar
Digital Library
- Bortnikov, E., Gurevich, M., Keidar, I., Kliot, G., and Shraer, A. Brahms: Byzantine resilient random membership sampling. Computer Networks 53, 13 (2009), 2340--2359. Google ScholarDigital Library
- Cox, I. J., Fu, R., and Hansen, L. K. Probably approximately correct search. In ICTIR (2009). Google ScholarDigital Library
- Demers, A., Greene, D., Hauser, C., Irish, W., Larson, J., Shenker, S., and Sturgis, H. Epidemic algorithms for replicated database maintenance. In Proceedings of the 6th annual ACM Symposium on Principles of distributed computing (1987). Google ScholarDigital Library
- Urdaneta, G., Pierre, G., and Steen, M. A survey of dht security techniques. ACM Computing Surveys (CSUR) 43, 2 (2011), 8. Google ScholarDigital Library
Index Terms
- PAC'nPost: a framework for a micro-blogging social network in an unstructured P2P network
Recommendations
Analysis of TTL-Based Consistency in Unstructured Peer-to-Peer Networks
Consistency maintenance is important to the sharing of dynamic contents in peer-to-peer (P2P) networks. The TTL-based mechanism is a natural choice for maintaining freshness in P2P content sharing. This paper investigates TTL-based consistency ...
Research and analysis of the optimization of the unstructured P2P overlay networks
WiCOM'09: Proceedings of the 5th International Conference on Wireless communications, networking and mobile computingUnstructured P2P systems are self-organized and decentralized. However, the mechanism of a peer randomly joining and leaving a P2P network, loose overlay structure, and little control over resources causes topology mismatching between the P2P logical ...
Ranked accuracy and unstructured distributed search
ECIR'13: Proceedings of the 35th European conference on Advances in Information RetrievalNon-uniformly distributing documents in an unstructured peer-to-peer (P2P) network has been shown to improve both the expected search length and search accuracy, where accuracy is defined as the size of the intersection of the documents retrieved by a ...
Comments