Random walks in peer-to-peer networks. Gkantsidis, C., Mihail, M., & Saberi, A. In INFOCOM 2004. Twenty-third łdots, pages 120--130, Hong Kong, China, 2004. ![Random walks in peer-to-peer networks [pdf]](https://bibbase.org/img/filetypes/pdf.svg "pdf")
Paper abstract bibtex We quantify the effectiveness of random walks for searching and construction of unstructured peer-to-peer (P2P) networks. We have identified two cases where the use of random walks for searching achierrs better results than Hooding: a) when the overlay topology is clustered, and h) when a client re-issues the same query while its liorizon does not change much. For construction, we arpe that an expander can he maintained dynamically with constant operations per addition. The key teelinical ingredient of our approach is a deep result of stnehastic processes indicating that samples taken from consecutive steps of a random walk can achieve statistical prnperties similar to independent sampling (if the second eigenvalue of the transition matrix is hounded away from 1, which translates to good expansion of the network; such cannectivity is desired, and helieved to Iiold, in every reasonable network and network model). This property has heen previously used in coniplexity theory for constrnction of pseudorandom number generators. We reveal another facet of this theory and translate savings in random hits to savings in processing overhead.
@inproceedings{ Gkantsidis2004,
abstract = {We quantify the effectiveness of random walks for searching and construction of unstructured peer-to-peer (P2P) networks. We have identified two cases where the use of random walks for searching achierrs better results than Hooding: a) when the overlay topology is clustered, and h) when a client re-issues the same query while its liorizon does not change much. For construction, we arpe that an expander can he maintained dynamically with constant operations per addition. The key teelinical ingredient of our approach is a deep result of stnehastic processes indicating that samples taken from consecutive steps of a random walk can achieve statistical prnperties similar to independent sampling (if the second eigenvalue of the transition matrix is hounded away from 1, which translates to good expansion of the network; such cannectivity is desired, and helieved to Iiold, in every reasonable network and network model). This property has heen previously used in coniplexity theory for constrnction of pseudorandom number generators. We reveal another facet of this theory and translate savings in random hits to savings in processing overhead.},
address = {Hong Kong, China},
author = {Gkantsidis, Christos and Mihail, Milena and Saberi, A},
booktitle = {INFOCOM 2004. Twenty-third łdots},
file = {:home/ecem/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Gkantsidis, Mihail, Saberi - 2004 - Random walks in peer-to-peer networks.pdf:pdf},
isbn = {0780383559},
keywords = {p2p,peer-to-peer networks,random walk,random walks,statistics},
mendeley-tags = {p2p,random walk},
pages = {120--130},
title = {{Random walks in peer-to-peer networks}},
url = {http://www.utdallas.edu/~emrah.cem/references/RandomWalksinP2PNetworks.pdf},
year = {2004}
}
Downloads: 0
{"_id":{"_str":"534211116d78590a0600006b"},"__v":1,"authorIDs":[],"author_short":["Gkantsidis, C.","Mihail, M.","Saberi, A."],"bibbaseid":"gkantsidis-mihail-saberi-randomwalksinpeertopeernetworks-2004","bibdata":{"abstract":"We quantify the effectiveness of random walks for searching and construction of unstructured peer-to-peer (P2P) networks. We have identified two cases where the use of random walks for searching achierrs better results than Hooding: a) when the overlay topology is clustered, and h) when a client re-issues the same query while its liorizon does not change much. For construction, we arpe that an expander can he maintained dynamically with constant operations per addition. The key teelinical ingredient of our approach is a deep result of stnehastic processes indicating that samples taken from consecutive steps of a random walk can achieve statistical prnperties similar to independent sampling (if the second eigenvalue of the transition matrix is hounded away from 1, which translates to good expansion of the network; such cannectivity is desired, and helieved to Iiold, in every reasonable network and network model). This property has heen previously used in coniplexity theory for constrnction of pseudorandom number generators. We reveal another facet of this theory and translate savings in random hits to savings in processing overhead.","address":"Hong Kong, China","author":["Gkantsidis, Christos","Mihail, Milena","Saberi, A"],"author_short":["Gkantsidis, C.","Mihail, M.","Saberi, A."],"bibtex":"@inproceedings{ Gkantsidis2004,\n abstract = {We quantify the effectiveness of random walks for searching and construction of unstructured peer-to-peer (P2P) networks. We have identified two cases where the use of random walks for searching achierrs better results than Hooding: a) when the overlay topology is clustered, and h) when a client re-issues the same query while its liorizon does not change much. For construction, we arpe that an expander can he maintained dynamically with constant operations per addition. The key teelinical ingredient of our approach is a deep result of stnehastic processes indicating that samples taken from consecutive steps of a random walk can achieve statistical prnperties similar to independent sampling (if the second eigenvalue of the transition matrix is hounded away from 1, which translates to good expansion of the network; such cannectivity is desired, and helieved to Iiold, in every reasonable network and network model). This property has heen previously used in coniplexity theory for constrnction of pseudorandom number generators. We reveal another facet of this theory and translate savings in random hits to savings in processing overhead.},\n address = {Hong Kong, China},\n author = {Gkantsidis, Christos and Mihail, Milena and Saberi, A},\n booktitle = {INFOCOM 2004. Twenty-third łdots},\n file = {:home/ecem/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Gkantsidis, Mihail, Saberi - 2004 - Random walks in peer-to-peer networks.pdf:pdf},\n isbn = {0780383559},\n keywords = {p2p,peer-to-peer networks,random walk,random walks,statistics},\n mendeley-tags = {p2p,random walk},\n pages = {120--130},\n title = {{Random walks in peer-to-peer networks}},\n url = {http://www.utdallas.edu/~emrah.cem/references/RandomWalksinP2PNetworks.pdf},\n year = {2004}\n}","bibtype":"inproceedings","booktitle":"INFOCOM 2004. Twenty-third łdots","file":":home/ecem/.local/share/data/Mendeley Ltd./Mendeley Desktop/Downloaded/Gkantsidis, Mihail, Saberi - 2004 - Random walks in peer-to-peer networks.pdf:pdf","id":"Gkantsidis2004","isbn":"0780383559","key":"Gkantsidis2004","keywords":"p2p,peer-to-peer networks,random walk,random walks,statistics","mendeley-tags":"p2p,random walk","pages":"120--130","title":"Random walks in peer-to-peer networks","type":"inproceedings","url":"http://www.utdallas.edu/~emrah.cem/references/RandomWalksinP2PNetworks.pdf","year":"2004","bibbaseid":"gkantsidis-mihail-saberi-randomwalksinpeertopeernetworks-2004","role":"author","urls":{"Paper":"http://www.utdallas.edu/~emrah.cem/references/RandomWalksinP2PNetworks.pdf"},"keyword":["p2p","peer-to-peer networks","random walk","random walks","statistics"],"downloads":0,"html":""},"bibtype":"inproceedings","biburl":"http://www.utdallas.edu/~emrah.cem/refs3.bib","downloads":0,"keywords":["p2p","peer-to-peer networks","random walk","random walks","statistics"],"search_terms":["random","walks","peer","peer","networks","gkantsidis","mihail","saberi"],"title":"Random walks in peer-to-peer networks","year":2004,"dataSources":["JMB96mDcw3SKthRdt"]}