Scalability analysis of distributed search in large peer-to-peer networks
Weimao Ke, Javed Mostafa · 2016
We study decentralized searches in large-scale, self-organized peer-to-peer networks and investigate the influences of network size and degree distribution (neighborhood size) on search efficiency. Experimental results show that searches are efficient and scalable in large networks, especially with large neighborhood sizes (degrees). Analysis of the data supports a proposed scalability model, in which search path length L (efficiency) is proportional to a poly-logarithmic function of network size N, with degree dm(majority neighborhood size) as the log base. The model explains 90% (R2) of variances in search path lengths. Search time (search path length) predicted by the model shows great potential for efficient searches in real-scale networks of up to a billion distributed systems.