September 27, 2017

Yulian Yang: On Efficiency of peer Rewriting in Semantic Overlay Networks


Semantic overlay networks~(SONs) are a type of network overlay where peers with similar contents are clustered together, typically for improving the search performance in distributed networks, specially P2P networks. In order to generate and maintain SON in unstructured P2P networks, each peer periodically performs a peer discovery and rewiring process whose aim is to improve the overall clustering of peers holding similar contents. This task is non trivial since each peer has only a partial/local view of the network. The lack of global knowledge often results in a blind/gradient peer discovery process. However, as peers in the network become gradually clustered, the efficiency of blind and gradient peer discovery process changes. This can be recast into a problem of distributed combinatorial optimization and the solution can be found from stochastic optimization approach due to Metropolis, Hastings and Glauber. By modeling the task as a combinatorial problem, we guide a walker to discover peers by accepting/rejecting the better/worse walk with some probability which changes as the network evolves. We study this approach in a simulated P2P network with 25000 peers, and compare it to the standard approach of random/gradient walk with equal probability: the results show that our approach is more efficient.